GetFEM++  5.3
dal_tree_sorted.h
Go to the documentation of this file.
1 /* -*- c++ -*- (enables emacs c++ mode) */
2 /*===========================================================================
3 
4  Copyright (C) 1995-2017 Yves Renard
5 
6  This file is a part of GetFEM++
7 
8  GetFEM++ is free software; you can redistribute it and/or modify it
9  under the terms of the GNU Lesser General Public License as published
10  by the Free Software Foundation; either version 3 of the License, or
11  (at your option) any later version along with the GCC Runtime Library
12  Exception either version 3.1 or (at your option) any later version.
13  This program is distributed in the hope that it will be useful, but
14  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
16  License and GCC Runtime Library Exception for more details.
17  You should have received a copy of the GNU Lesser General Public License
18  along with this program; if not, write to the Free Software Foundation,
19  Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
20 
21  As a special exception, you may use this file as it is a part of a free
22  software library without restriction. Specifically, if other files
23  instantiate templates or use macros or inline functions from this file,
24  or you compile this file and link it with other files to produce an
25  executable, this file does not by itself cause the resulting executable
26  to be covered by the GNU Lesser General Public License. This exception
27  does not however invalidate any other reasons why the executable file
28  might be covered by the GNU Lesser General Public License.
29 
30 ===========================================================================*/
31 
32 /**@file dal_tree_sorted.h
33  @author Yves Renard <Yves.Renard@insa-lyon.fr>
34  @date June 01, 1995
35  @brief a balanced tree stored in a dal::dynamic_array
36 
37  Oneday this will be replaced with a std::map.
38 */
39 #ifndef DAL_TREE_SORTED_H__
40 #define DAL_TREE_SORTED_H__
41 
42 #include "dal_tas.h"
43 
44 namespace dal {
45 
46  /* ********************************************************************* */
47  /* Definitition des iterateurs. */
48  /* ********************************************************************* */
49  /* Attention, l'iterateur n'est plus valide apres une operation */
50  /* d'insertion ou de suppression. */
51  /* ********************************************************************* */
52 
53  static const size_t DEPTHMAX__ = 64;
54  static const size_t ST_NIL = size_t(-1);
55 
56  template<typename T, typename COMP = gmm::less<T>, unsigned char pks = 5>
57  class dynamic_tree_sorted;
58 
59  template<typename T, typename COMP, unsigned char pks> struct tsa_iterator {
60  typedef T value_type;
61  typedef value_type& reference;
62  typedef value_type* pointer;
63  typedef size_t size_type;
64  typedef ptrdiff_t difference_type;
65  typedef std::bidirectional_iterator_tag iterator_category;
66  typedef gmm::int8_type short_type;
67 
68  dynamic_tree_sorted<T, COMP, pks> *p;
69  size_type path[DEPTHMAX__];
70  short_type dir[DEPTHMAX__];
71  size_type depth;
72 
73  tsa_iterator(void) {}
74  tsa_iterator(dynamic_tree_sorted<T, COMP, pks> &tsa)
75  { p = &tsa; depth = 0; }
76  void copy(const tsa_iterator<T, COMP, pks> &it);
77  tsa_iterator(const tsa_iterator &it) { copy(it); }
78  tsa_iterator &operator =(const tsa_iterator &it)
79  { copy(it); return *this;}
80 
81  inline size_type index(void) const
82  { return (depth==0) ? ST_NIL : path[depth-1];}
83  inline size_type father(void) const
84  { return (depth<=1) ? ST_NIL : path[depth-2];}
85  inline size_type index_(void) const
86  { return path[(depth-1) & 63]; }
87  inline short_type direction(void) const
88  { return (depth==0) ? 0 : dir[depth-1];}
89  inline void up(void) { if (depth > 0) depth--; }
90  void down_left(void);
91  void down_right(void);
92  void down_left_all(void);
93  void down_right_all(void);
94  void root(void) { path[0] = p->root_elt(); dir[0] = 0; depth = 1; }
95  void first(void) { root(); down_left_all(); }
96  void last(void) { root(); down_right_all(); }
97  void end(void) { depth = 0; }
98 
99  tsa_iterator &operator ++();
100  tsa_iterator &operator --();
101  tsa_iterator operator ++(int)
102  { tsa_iterator tmp = *this; ++(*this); return tmp; }
103  tsa_iterator operator --(int)
104  { tsa_iterator tmp = *this; --(*this); return tmp; }
105 
106  reference operator *() const { return (*p)[index()]; }
107  pointer operator->() const { return &(operator*()); }
108 
109  bool operator ==(const tsa_iterator &i) const
110  { return ((i.depth == 0 && depth == 0) || (i.index_() == index_())); }
111  bool operator !=(const tsa_iterator &i) const
112  { return !((i.depth == 0 && depth == 0) || (i.index_() == index_())); }
113  };
114 
115  template<typename T, typename COMP, unsigned char pks>
116  void tsa_iterator<T, COMP, pks>::copy(const tsa_iterator<T, COMP, pks> &it) {
117  p = it.p; depth = it.depth;
118  size_type *p1it=&(path[0]), *pend=&path[depth];
119  const size_type *p2it=&(it.path[0]);
120  short_type *d1it=&(dir[0]);
121  const short_type *d2it=&(it.dir[0]);
122  while (p1it != pend) { *p1it++ = *p2it++; *d1it++ = *d2it++; }
123  }
124 
125  template<typename T, typename COMP, unsigned char pks>
126  void tsa_iterator<T, COMP, pks>::down_left(void) {
127  GMM_ASSERT3(depth > 0 && depth < DEPTHMAX__ && index() != ST_NIL,
128  "internal error");
129  path[depth] = p->left_elt(index_()); dir[depth++] = -1;
130  }
131 
132  template<typename T, typename COMP, unsigned char pks>
133  void tsa_iterator<T, COMP, pks>::down_right(void) {
134  GMM_ASSERT3(depth > 0 && depth < DEPTHMAX__ && index() != ST_NIL,
135  "internal error");
136  path[depth] = p->right_elt(index_()); dir[depth++] = 1;
137  }
138 
139  template<typename T, typename COMP, unsigned char pks>
140  void tsa_iterator<T, COMP, pks>::down_left_all(void)
141  { while (index_() != ST_NIL) down_left(); up(); }
142 
143  template<typename T, typename COMP, unsigned char pks>
144  void tsa_iterator<T, COMP, pks>::down_right_all(void)
145  { while (index_() != ST_NIL) down_right(); up();}
146 
147  template<typename T, typename COMP, unsigned char pks>
148  tsa_iterator<T, COMP, pks> &tsa_iterator<T, COMP, pks>::operator ++() {
149  if (depth == 0) first();
150  if (p->right_elt(index_()) != ST_NIL) { down_right(); down_left_all(); }
151  else { up(); while (dir[depth] == 1) up(); }
152  return *this;
153  }
154 
155  template<typename T, typename COMP, unsigned char pks>
156  tsa_iterator<T, COMP, pks> &tsa_iterator<T, COMP, pks>::operator --() {
157  if (depth == 0) last();
158  if (p->left_elt(index_()) != ST_NIL) { down_left(); down_right_all(); }
159  else { up(); while (dir[depth] == -1) up(); }
160  return *this;
161  }
162 
163 
164  template<typename T, typename COMP, unsigned char pks> struct const_tsa_iterator {
165  typedef T value_type;
166  typedef const value_type& reference;
167  typedef const value_type* pointer;
168  typedef size_t size_type;
169  typedef ptrdiff_t difference_type;
170  typedef std::bidirectional_iterator_tag iterator_category;
171  typedef gmm::int8_type short_type;
172 
173  const dynamic_tree_sorted<T, COMP, pks> *p;
174  size_type path[DEPTHMAX__];
175  short_type dir[DEPTHMAX__];
176  size_type depth;
177 
178  const_tsa_iterator(void) {}
179  const_tsa_iterator(const dynamic_tree_sorted<T, COMP, pks> &tsa)
180  { p = &tsa; depth = 0; }
181  void copy(const const_tsa_iterator<T, COMP, pks> &it);
182  const_tsa_iterator(const const_tsa_iterator &it) { this->copy(it); }
183  const_tsa_iterator(const tsa_iterator<T, COMP, pks> &it);
184  const_tsa_iterator &operator =(const const_tsa_iterator &it)
185  { copy(it); return *this; }
186 
187  inline size_type index(void) const
188  { return (depth==0) ? ST_NIL : path[depth-1];}
189  inline size_type father(void) const
190  { return (depth<=1) ? ST_NIL : path[depth-2];}
191  inline size_type index_(void) const { return path[depth-1]; }
192  inline short_type direction(void) const
193  { return (depth==0) ? short_type(0) : dir[depth-1];}
194  inline void up(void) { if (depth > 0) depth--; }
195  void down_left(void);
196  void down_right(void);
197  void down_left_all(void);
198  void down_right_all(void);
199  void root(void) { path[0] = p->root_elt(); dir[0] = 0; depth = 1; }
200  void first(void) { root(); down_left_all(); }
201  void last(void) { root(); down_right_all(); }
202  void end(void) { depth = 0; }
203 
204  const_tsa_iterator &operator ++();
205  const_tsa_iterator &operator --();
206  const_tsa_iterator operator ++(int)
207  { const_tsa_iterator tmp = *this; ++(*this); return tmp; }
208  const_tsa_iterator operator --(int)
209  { const_tsa_iterator tmp = *this; --(*this); return tmp; }
210 
211  reference operator *() const { return (*p)[index()]; }
212  pointer operator->() const { return &(operator*()); }
213 
214  bool operator ==(const const_tsa_iterator &i) const
215  { return ((i.depth == 0 && depth == 0) || (i.index_() == index_())); }
216  bool operator !=(const const_tsa_iterator &i) const
217  { return !((i.depth == 0 && depth == 0) || (i.index_() == index_())); }
218  };
219 
220  template<typename T, typename COMP, unsigned char pks>
221  std::ostream& operator<<(std::ostream& o,
222  const const_tsa_iterator<T,COMP,pks>& it) {
223  o << "const_tsa_iterator : depth=" << it.depth << ", path/dir=[";
224  for (unsigned i=0; i < it.depth; ++i)
225  o << "{" << it.path[i] << ", " << int(it.dir[i]) << "} ";
226  o << "]";
227  return o;
228  }
229 
230  template<typename T, typename COMP, unsigned char pks>
231  void const_tsa_iterator<T, COMP, pks>::copy
232  (const const_tsa_iterator<T, COMP, pks> &it) {
233  p = it.p; depth = it.depth;
234  size_type *p1it=&(path[0]), *pend=&path[depth];
235  const size_type *p2it=&(it.path[0]);
236  short_type *d1it=&(dir[0]);
237  const short_type *d2it=&(it.dir[0]);
238  while (p1it != pend) { *p1it++ = *p2it++; *d1it++ = *d2it++; }
239  }
240 
241  template<typename T, typename COMP, unsigned char pks>
242  const_tsa_iterator<T, COMP, pks>::const_tsa_iterator
243  (const tsa_iterator<T, COMP, pks> &it) {
244  p = it.p; depth = it.depth;
245  size_type *p1it=&(path[0]), *pend=&path[depth];
246  const size_type *p2it=&(it.path[0]);
247  short_type *d1it=&(dir[0]);
248  const short_type *d2it=&(it.dir[0]);
249  while (p1it != pend) { *p1it++ = *p2it++; *d1it++ = *d2it++; }
250  }
251 
252  template<typename T, typename COMP, unsigned char pks>
253  void const_tsa_iterator<T, COMP, pks>::down_left(void) {
254  GMM_ASSERT3(depth > 0 && depth < DEPTHMAX__ && index() != ST_NIL,
255  "internal error");
256  path[depth] = p->left_elt(index_()); dir[depth++] = -1;
257  }
258 
259  template<typename T, typename COMP, unsigned char pks>
260  void const_tsa_iterator<T, COMP, pks>::down_right(void) {
261  GMM_ASSERT3(depth > 0 && depth < DEPTHMAX__ && index() != ST_NIL,
262  "internal error");
263  path[depth] = p->right_elt(index_()); dir[depth++] = 1;
264  }
265 
266  template<typename T, typename COMP, unsigned char pks>
267  void const_tsa_iterator<T, COMP, pks>::down_left_all(void)
268  { while (index_() != ST_NIL) down_left(); up(); }
269 
270  template<typename T, typename COMP, unsigned char pks>
271  void const_tsa_iterator<T, COMP, pks>::down_right_all(void)
272  { while (index_() != ST_NIL) down_right(); up();}
273 
274  template<typename T, typename COMP, unsigned char pks>
275  const_tsa_iterator<T, COMP, pks> &
276  const_tsa_iterator<T, COMP, pks>::operator ++() {
277  if (depth == 0) last();
278  if (p->right_elt(index_()) != ST_NIL) { down_right(); down_left_all(); }
279  else { up(); while (dir[depth] == 1) up(); }
280  return *this;
281  }
282 
283  template<typename T, typename COMP, unsigned char pks>
284  const_tsa_iterator<T, COMP, pks> &
285  const_tsa_iterator<T, COMP, pks>::operator --() {
286  if (depth == 0) last();
287  if (p->left_elt(index_()) != ST_NIL) { down_left(); down_right_all(); }
288  else { up(); while (dir[depth] == -1) up(); }
289  return *this;
290  }
291 
292  /* ********************************************************************* */
293  /* Definitition of dynamic_tree_sorted. */
294  /* ********************************************************************* */
295 
296  template<typename T, typename COMP, unsigned char pks>
297  class dynamic_tree_sorted : public dynamic_tas<T, pks> {
298  public :
299 
300  typedef typename dynamic_tas<T, pks>::tas_iterator tas_iterator;
301  typedef typename dynamic_tas<T, pks>::const_tas_iterator const_tas_iterator;
302  typedef typename dynamic_tas<T, pks>::iterator iterator;
303  typedef typename dynamic_tas<T, pks>::const_iterator const_iterator;
304  typedef typename dynamic_tas<T, pks>::size_type size_type;
305 
306  typedef gmm::int8_type short_type;
307  typedef tsa_iterator<T, COMP, pks> sorted_iterator;
308  typedef const_tsa_iterator<T, COMP, pks> const_sorted_iterator;
309  typedef std::reverse_iterator<const_iterator> const_reverse_sorted_iterator;
310  typedef std::reverse_iterator<iterator> reverse_sorted_iterator;
311 
312  protected :
313 
314  COMP compar;
315  struct tree_elt {
316  size_type r, l;
317  short_type eq;
318  inline void init(void) { eq = 0; r = l = ST_NIL; }
319  tree_elt(void) { init(); }
320  };
321 
322  dynamic_array<tree_elt, pks> nodes;
323  size_type first_node;
324 
325  size_type rotate_right(size_type i);
326  size_type rotate_left(size_type i);
327  size_type rotate_left_right(size_type i);
328  size_type rotate_right_left(size_type i);
329  size_type balance_again(size_type i);
330 
331  void add_index(size_type i, const_sorted_iterator &it);
332  void sup_index(size_type i, const_sorted_iterator &it);
333 
334  public :
335 
336  int verify_balance(size_type i = size_type(-2)) const { // for debugging
337  if (i == size_type(-2)) i = first_node;
338  if (i == ST_NIL) return 0;
339  int l = verify_balance(nodes[i].l);
340  int r = verify_balance(nodes[i].r);
341  GMM_ASSERT3(short_type(r - l) == nodes[i].eq &&
342  (nodes[i].eq <= 1 && nodes[i].eq>=-1), "internal error");
343  return std::max(l,r) + 1;
344  }
345 
346  void insert_path(const T &elt, const_sorted_iterator &it) const;
347  void search_sorted_iterator(const T &elt,
348  const_sorted_iterator &it) const;
349  void find_sorted_iterator(size_type i, const_sorted_iterator &it) const;
350  COMP &comparator(void) { return compar; }
351  const COMP &comparator(void) const { return compar; }
352 
353  dynamic_tree_sorted(COMP cp = COMP())
354  { first_node = ST_NIL; compar = cp; }
355 
356  size_type root_elt(void) const { return first_node; }
357  size_type right_elt(size_type n) const { return nodes[n].r; }
358  size_type left_elt(size_type n) const { return nodes[n].l; }
359  short_type balance(size_type n) const
360  { return short_type((n == ST_NIL) ? 0 : nodes[n].eq); }
361  size_type search(const T &elt) const {
362  const_sorted_iterator it(*this);
363  search_sorted_iterator(elt,it);
364  return it.index();
365  }
366  size_type search_ge(const T &) const;
367  size_type memsize(void) const;
368  void clear(void)
369  { first_node = ST_NIL; nodes.clear(); dynamic_tas<T,pks>::clear(); }
370  size_type add(const T &);
371  void add_to_index(size_type, const T &);
372  size_type add_norepeat(const T &, bool replace = false,
373  bool *present = NULL);
374  void resort(void);
375  void sup(size_type);
376  void swap(size_type, size_type);
377  void compact(void);
378 
379  sorted_iterator sorted_begin(void)
380  { sorted_iterator it(*this); it.first(); return it; }
381  const_sorted_iterator sorted_begin(void) const
382  { const_sorted_iterator it(*this); it.first(); return it; }
383  sorted_iterator sorted_end(void)
384  { sorted_iterator it(*this); it.end(); return it; }
385  const_sorted_iterator sorted_end(void) const
386  { const_sorted_iterator it(*this); it.end(); return it; }
387  reverse_sorted_iterator rbegin(void)
388  { return reverse_sorted_iterator(this->end()); }
389  const_reverse_sorted_iterator rbegin(void) const
390  { return const_reverse_sorted_iterator(this->end()); }
391  reverse_sorted_iterator rend(void)
392  { return reverse_sorted_iterator(this->begin()); }
393  const_reverse_sorted_iterator rend(void) const
394  { return const_reverse_sorted_iterator(this->begin()); }
395  sorted_iterator sorted_first(void)
396  { sorted_iterator it(*this); it.first(); return it; }
397  const_sorted_iterator sorted_first(void) const
398  { const_sorted_iterator it(*this); it.first(); return it; }
399  sorted_iterator sorted_last(void)
400  { sorted_iterator it(*this); it.last(); return it; }
401  const_sorted_iterator sorted_last(void) const
402  { const_sorted_iterator it(*this); it.last(); return it; }
403 // sorted_iterator sorted_ge(const T &elt);
404  const_sorted_iterator sorted_ge(const T &elt) const;
405  };
406 
407  template<typename T, typename COMP, unsigned char pks>
408  std::ostream& operator <<(std::ostream& o,
409  dynamic_tree_sorted<T, COMP, pks> &m) {
410  o << "Nomber of elt :" << m.card() << '\n';
411  o << "Index du noeud racine :" << m.root_elt() << '\n';
412  for (size_t i = 0; i < m.size(); ++i)
413  o << "elt " << i << " left :" << int(m.left_elt(i)) << " right : "
414  << int(m.right_elt(i)) << " balance :" << int(m.balance(i)) << '\n';
415  return o;
416  }
417 
418  template<typename T, typename COMP, unsigned char pks>
419  typename dynamic_tree_sorted<T, COMP, pks>::size_type
420  dynamic_tree_sorted<T, COMP, pks>::rotate_right(size_type i) {
421  tree_elt *pni = &(nodes[i]);
422  size_type f = pni->l;
423  tree_elt *pnf = &(nodes[f]);
424  pni->l = pnf->r; pnf->r = i; pnf->eq = pni->eq = 0;
425  return f;
426  }
427 
428  template<typename T, typename COMP, unsigned char pks>
429  typename dynamic_tree_sorted<T, COMP, pks>::size_type
430  dynamic_tree_sorted<T, COMP, pks>::rotate_left(size_type i) {
431  tree_elt *pni = &(nodes[i]);
432  size_type f = pni->r;
433  tree_elt *pnf = &(nodes[f]);
434  pni->r = pnf->l; pnf->l = i; pnf->eq = pni->eq = 0;
435  return f;
436  }
437 
438  template<typename T, typename COMP, unsigned char pks>
439  typename dynamic_tree_sorted<T, COMP, pks>::size_type
440  dynamic_tree_sorted<T, COMP, pks>::rotate_left_right(size_type i) {
441  tree_elt *pni = &(nodes[i]);
442  size_type f = pni->l;
443  tree_elt *pnf = &(nodes[f]);
444  short_type uba = pnf->eq, ubb = nodes[pnf->r].eq;
445  pni->l = rotate_left(f); f = rotate_right(i);
446  pnf = &(nodes[f]);
447  pnf->eq = short_type(uba - 1);
448  nodes[pnf->l].eq = short_type(uba - 1 - ((ubb == 1) ? 1 : 0));
449  nodes[pnf->r].eq = short_type(((ubb == -1) ? 1 : 0));
450 
451  if (uba == 0 && ubb == 1)
452  {
453  pnf->l = balance_again(pnf->l);
454  if (nodes[pnf->l].eq == 0) pnf->eq = 0;
455  }
456  return f;
457  }
458 
459  template<typename T, typename COMP, unsigned char pks>
460  typename dynamic_tree_sorted<T, COMP, pks>::size_type
461  dynamic_tree_sorted<T, COMP, pks>::rotate_right_left(size_type i) {
462  size_type f = nodes[i].r;
463  short_type uba = nodes[f].eq, ubb = nodes[nodes[f].l].eq;
464  nodes[i].r = rotate_right(f); f = rotate_left(i);
465  nodes[f].eq = short_type(uba + 1);
466  nodes[nodes[f].r].eq = short_type(uba + 1 + ((ubb == -1) ? 1 : 0));
467  nodes[nodes[f].l].eq = short_type(((ubb == +1) ? -1 : 0));
468 
469  if (uba == 0 && ubb == -1) {
470  nodes[f].r = balance_again(nodes[f].r);
471  if (nodes[nodes[f].r].eq == 0) nodes[f].eq = 0;
472  }
473  return f;
474  }
475 
476  template<typename T, typename COMP, unsigned char pks>
477  typename dynamic_tree_sorted<T, COMP, pks>::size_type
478  dynamic_tree_sorted<T, COMP, pks>::balance_again(size_type i) {
479  tree_elt *pn = &(nodes[i]);
480  switch (pn->eq) {
481  case -2 : if (nodes[pn->l].eq == -1) return rotate_right(i);
482  else return rotate_left_right(i);
483  case +2 : if (nodes[pn->r].eq == 1) return rotate_left(i);
484  else return rotate_right_left(i);
485  case 0 : case -1 : case 1 : return i;
486  default : GMM_ASSERT3(false, "internal error");
487  }
488  return ST_NIL;
489  }
490 
491  template<typename T, typename COMP, unsigned char pks>
492  void dynamic_tree_sorted<T, COMP, pks>::search_sorted_iterator
493  (const T &elt, const_sorted_iterator &it) const{
494  it.root();
495  while (it.index() != ST_NIL) {
496  int cp = compar(elt, (*this)[it.index()]);
497  if (cp < 0) it.down_left();
498  else if (cp > 0) it.down_right(); else break;
499  }
500  }
501 
502  template<typename T, typename COMP, unsigned char pks>
503  void dynamic_tree_sorted<T, COMP, pks>::find_sorted_iterator
504  (size_type i, const_sorted_iterator &it) const {
505  const T *pelt = &((*this)[i]);
506  it.root();
507  while (it.index() != ST_NIL) {
508  int cp = compar(*pelt, (*this)[it.index()]);
509  if (cp == 0) { if (it.index() == i) break; else it.down_left(); }
510  else if (cp < 0) it.down_left(); else it.down_right();
511  }
512  if (it.index() == ST_NIL) it.up();
513  while (it.index() != i && it.index() != ST_NIL) ++it;
514  /* peut etre il faudrait controler dans la boucle le depacement */
515  /* pour eviter de faire tout le tableau en cas de faux indice. */
516  }
517 
518  template<typename T, typename COMP, unsigned char pks>
519  void dynamic_tree_sorted<T, COMP, pks>::insert_path
520  (const T &elt, const_sorted_iterator &it) const {
521  it.root();
522  while (it.index() != ST_NIL) {
523  int cp = compar(elt, (*this)[it.index()]);
524  if (cp <= 0) it.down_left(); else it.down_right();
525  }
526  }
527 
528  template<typename T, typename COMP, unsigned char pks>
529  typename dynamic_tree_sorted<T, COMP, pks>::size_type
530  dynamic_tree_sorted<T, COMP, pks>::search_ge(const T &elt) const {
531  const_sorted_iterator it(*this); insert_path(elt, it);
532  short_type dir = it.direction();
533  if (it.index() == ST_NIL)
534  { it.up(); if (it.index() != ST_NIL && dir == +1) ++it; }
535  return it.index();
536  }
537 
538 // template<typename T, typename COMP, unsigned char pks>
539 // typename dynamic_tree_sorted<T, COMP, pks>::sorted_iterator
540 // dynamic_tree_sorted<T, COMP, pks>::sorted_ge(const T &elt)
541 // {
542 // sorted_iterator it(*this); insert_path(elt, it);
543 // short_type dir = it.direction();
544 // it.up(); if (it.index() != ST_NIL && dir == +1) ++it;
545 // return it;
546 // }
547 
548  template<typename T, typename COMP, unsigned char pks>
549  typename dynamic_tree_sorted<T, COMP, pks>::const_sorted_iterator
550  dynamic_tree_sorted<T, COMP, pks>::sorted_ge(const T &elt) const {
551  const_sorted_iterator it(*this); insert_path(elt, it);
552  short_type dir = it.direction();
553  it.up();
554  if (it.index() != ST_NIL && dir == +1) ++it;
555  return it;
556  }
557 
558 
559  template<typename T, typename COMP, unsigned char pks>
560  typename dynamic_tree_sorted<T, COMP, pks>::size_type
561  dynamic_tree_sorted<T, COMP, pks>::memsize(void) const {
562  return dynamic_tas<T, pks>::memsize() + nodes.memsize()
563  + sizeof(dynamic_tree_sorted<T, COMP, pks>);
564  }
565 
566  template<typename T, typename COMP, unsigned char pks>
567  void dynamic_tree_sorted<T, COMP, pks>::compact(void) {
568  if (!this->empty())
569  while (this->ind.last_true() >= this->ind.card())
570  swap(this->ind.first_false(), this->ind.last_true());
571  }
572 
573  template<typename T, typename COMP, unsigned char pks>
574  void dynamic_tree_sorted<T, COMP, pks>::add_index
575  (size_type i, const_sorted_iterator &it) {
576  nodes[i].init();
577  if (first_node == ST_NIL)
578  first_node = i;
579  else {
580  short_type dir = it.direction();
581  it.up();
582  if (dir == -1) nodes[it.index()].l = i; else nodes[it.index()].r = i;
583 
584  while(it.index() != ST_NIL) {
585  short_type *peq = &(nodes[it.index()].eq);
586  if (*peq == 0) *peq = short_type(*peq + dir);
587  else {
588  *peq = short_type(*peq + dir);
589  size_type f = balance_again(it.index());
590  dir = it.direction();
591  it.up();
592  switch (dir) {
593  case 0 : first_node = f; break;
594  case -1 : nodes[it.index()].l = f; break;
595  case +1 : nodes[it.index()].r = f; break;
596  }
597  break;
598  }
599  dir = it.direction();
600  it.up();
601  }
602  }
603  }
604 
605  template<typename T, typename COMP, unsigned char pks>
606  typename dynamic_tree_sorted<T, COMP, pks>::size_type
607  dynamic_tree_sorted<T, COMP, pks>::add(const T &f) {
608  const_sorted_iterator it(*this); insert_path(f, it);
609  size_type num = dynamic_tas<T,pks>::add(f);
610  add_index(num, it);
611  return num;
612  }
613 
614  template<typename T, typename COMP, unsigned char pks> void
615  dynamic_tree_sorted<T, COMP, pks>::add_to_index(size_type i,const T &f) {
616  if (!(this->index_valid(i) && compar(f, (*this)[i]) == 0)) {
617  if (this->index_valid(i)) sup(i);
618  dynamic_tas<T,pks>::add_to_index(i, f);
619  const_sorted_iterator it(*this); insert_path(f, it);
620  add_index(i, it);
621  }
622  }
623 
624  template<typename T, typename COMP, unsigned char pks>
625  typename dynamic_tree_sorted<T, COMP, pks>::size_type
626  dynamic_tree_sorted<T, COMP, pks>::add_norepeat
627  (const T &f, bool replace, bool *present) {
628  const_sorted_iterator it(*this); search_sorted_iterator(f, it);
629  size_type num = it.index();
630  if (num == ST_NIL) {
631  if (present != NULL) *present = false;
632  num = dynamic_tas<T,pks>::add(f); add_index(num, it);
633  }
634  else {
635  if (present != NULL) *present = true;
636  if (replace) (*this)[num] = f;
637  }
638  return num;
639  }
640 
641  template<typename T, typename COMP, unsigned char pks>
642  void dynamic_tree_sorted<T, COMP, pks>::resort(void) {
643  const_tas_iterator itb
644  = ((const dynamic_tree_sorted<T, COMP, pks> *)(this))->tas_begin();
645  const_tas_iterator ite
646  = ((const dynamic_tree_sorted<T, COMP, pks> *)(this))->tas_end();
647  const_sorted_iterator it(*this);
648  first_node = ST_NIL;
649  while (itb != ite)
650  { insert_path(*itb, it); add_index(itb.index(), it); ++itb; }
651  }
652 
653  template<typename T, typename COMP, unsigned char pks>
654  void dynamic_tree_sorted<T, COMP, pks>::sup_index
655  (size_type i, const_sorted_iterator &it) {
656  size_type f, ni = i, ic;
657  short_type dir;
658  tree_elt *pni = &(nodes[i]), *pnc = 0;
659 
660  if (pni->l == ST_NIL || pni->r == ST_NIL) {
661  f = (pni->l != ST_NIL) ? pni->l : pni->r;
662  dir = it.direction(); it.up(); ic = it.index();
663  if (ic != ST_NIL) pnc = &(nodes[ic]);
664  switch (dir) {
665  case 0 : first_node = f; break;
666  case -1 : pnc->l = f; break;
667  case +1 : pnc->r = f; break;
668  }
669  }
670  else {
671  f = it.father();
672  dir = it.direction();
673  it--; ni = it.index();
674  switch (dir) {
675  case 0 : first_node = ni; break;
676  case -1 : nodes[f].l = ni; break;
677  case +1 : nodes[f].r = ni; break;
678  }
679  pnc = &(nodes[ni]); f = pnc->l; *pnc = *pni;
680  dir = it.direction();
681  it.up(); ic = it.index(); if (ic == i) ic = ni; pnc = &(nodes[ic]);
682  if (dir == -1) pnc->l = f; else pnc->r = f;
683  }
684 
685  while (it.index() != ST_NIL) {
686  short_type ub = pnc->eq;
687  pnc->eq = short_type(pnc->eq - dir);
688  if (ub == 0) break;
689  f = balance_again(ic);
690  ub = nodes[f].eq;
691  dir = it.direction();
692  it.up(); ic = it.index(); if (ic == i) ic = ni;
693  if (ic != ST_NIL) pnc = &(nodes[ic]);
694  switch (dir) {
695  case 0 : first_node = f; break;
696  case -1 : pnc->l = f; break;
697  case +1 : pnc->r = f; break;
698  }
699  if (ub != 0) break;
700  }
701  }
702 
703  template<typename T, typename COMP, unsigned char pks>
704  void dynamic_tree_sorted<T, COMP, pks>::sup(size_type i) {
705  GMM_ASSERT2(i < INT_MAX, "out of range");
706  const_sorted_iterator it(*this); find_sorted_iterator(i, it);
707  if (it.index() != ST_NIL)
708  { sup_index(i, it); dynamic_tas<T, pks>::sup(i); }
709  }
710 
711  template<typename T, typename COMP, unsigned char pks>
712  void dynamic_tree_sorted<T, COMP, pks>::swap(size_type i, size_type j) {
713  GMM_ASSERT2(i < INT_MAX && j < INT_MAX, "out of range");
714 
715  if (i != j) {
716  const_sorted_iterator it1(*this), it2(*this); it1.end(); it2.end();
717 
718  if (this->index_valid(i)) find_sorted_iterator(i, it1);
719  if (this->index_valid(j)) find_sorted_iterator(j, it2);
720 
721  short_type dir1 = it1.direction(), dir2 = it2.direction();
722  it1.up(); it2.up();
723  size_type f1 = it1.index(), f2 = it2.index();
724 
725  if (f1!=ST_NIL) { if (dir1==-1) nodes[f1].l = j; else nodes[f1].r = j; }
726  if (f2!=ST_NIL) { if (dir2==-1) nodes[f2].l = i; else nodes[f2].r = i; }
727  if (first_node==i) first_node=j; else if (first_node==j) first_node=i;
728 
729  std::swap(nodes[i], nodes[j]);
730  dynamic_tas<T,pks>::swap(i,j);
731  }
732  }
733 
734  /* ********************************************************************* */
735  /* Definitition d'un dynamic_tree_sorted utilise comme index sur tableau.*/
736  /* ********************************************************************* */
737  /* pas completement satisfaisant. A utiliser avec precautions. */
738 
739  template<typename T, typename TAB, typename COMP> struct less_index
740  : public std::binary_function<size_t, size_t, int> {
741  const TAB *tab;
742  COMP compare;
743  mutable const T *search_elt;
744 
745  int operator()(size_t i, size_t j) const {
746  return compare( (i == ST_NIL) ? *search_elt : (*tab)[i],
747  (j == ST_NIL) ? *search_elt : (*tab)[j] );
748  }
749 
750  less_index(const TAB &t, const COMP &c)
751  { compare = c; tab = &t; }
752  less_index(void) {}
753 
754  };
755 
756 
757  template<typename T, typename TAB, typename COMP = gmm::less<T>, unsigned char pks = 5>
758  class dynamic_tree_sorted_index : public
759  dynamic_tree_sorted<size_t, less_index<T,TAB,COMP>, pks> {
760  public :
761 
762  typedef typename
763  dynamic_tree_sorted<size_t, less_index<T,TAB,COMP>, pks>::size_type
764  size_type;
765 
766  protected :
767 
768  typedef dynamic_tree_sorted<size_t, less_index<T,TAB,COMP>, pks> dts_type;
769 
770  public :
771 
772  dynamic_tree_sorted_index(TAB &t, COMP cp = COMP())
773  : dts_type(less_index<T,TAB,COMP>(t, cp)) { }
774 
775  void change_tab(TAB &t, COMP cp = COMP())
776  { this->comparator() = less_index<T,TAB,COMP>(t, cp); }
777 
778  size_type search(const T &elt) const {
779  this->compar.search_elt = &elt;
780  return dts_type::search(ST_NIL);
781  }
782  size_type search_ge(const T &elt) const {
783  this->compar.search_elt = &elt;
784  return dts_type::search_ge(ST_NIL);
785  }
786  size_type add(size_type i) {
787  typename dts_type::const_sorted_iterator it(*this); (*this)[i] = i;
788  this->ind[i] = true; insert_path(i, it); add_index(i, it); return i;
789  }
790 
791  };
792 
793 }
794 
795 #endif /* DAL_TREE_SORTED_H__ */
dal_tas.h
Heap implementation.
bgeot::operator<<
std::ostream & operator<<(std::ostream &o, const convex_structure &cv)
Print the details of the convex structure cvs to the output stream o.
Definition: bgeot_convex_structure.cc:71
bgeot::size_type
size_t size_type
used as the common size type in the library
Definition: bgeot_poly.h:49
gmm::copy
void copy(const L1 &l1, L2 &l2)
*/
Definition: gmm_blas.h:977
dal
Dynamic Array Library.
Definition: dal_backtrace.cc:29
gmm::clear
void clear(L &l)
clear (fill with zeros) a vector or matrix.
Definition: gmm_blas.h:59
bgeot::short_type
gmm::uint16_type short_type
used as the common short type integer in the library
Definition: bgeot_config.h:79
gmm::add
void add(const L1 &l1, L2 &l2)
*/
Definition: gmm_blas.h:1268