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