foobar2000 SDK  2015-08-03
avltree.h
Go to the documentation of this file.
1 namespace pfc {
2 
3  template<typename t_storage>
4  class _avltree_node : public _list_node<t_storage> {
5  public:
8  template<typename t_param> _avltree_node(t_param const& param) : t_node(param), m_left(), m_right(), m_depth() {}
9 
11  typedef t_self* t_rawptr;
12 
13  t_ptr m_left, m_right;
14  t_rawptr m_parent;
15 
17 
18  void link_left(t_self* ptr) throw() {
19  m_left = ptr;
20  if (ptr != NULL) ptr->m_parent = this;
21  }
22  void link_right(t_self* ptr) throw() {
23  m_right = ptr;
24  if (ptr != NULL) ptr->m_parent = this;
25  }
26 
27  void link_child(bool which,t_self* ptr) throw() {
28  (which ? m_right : m_left) = ptr;
29  if (ptr != NULL) ptr->m_parent = this;
30  }
31 
32  void unlink() throw() {
33  m_left.release(); m_right.release(); m_parent = NULL; m_depth = 0;
34  }
35 
36  inline void add_ref() throw() {this->refcount_add_ref();}
37  inline void release() throw() {this->refcount_release();}
38 
39  inline t_rawptr child(bool which) const throw() {return which ? m_right.get_ptr() : m_left.get_ptr();}
40  inline bool which_child(const t_self* ptr) const throw() {return ptr == m_right.get_ptr();}
41 
42 
43 
44  t_rawptr step(bool direction) throw() {
45  t_self* walk = this;
46  for(;;) {
47  t_self* t = walk->child(direction);
48  if (t != NULL) return t->peakchild(!direction);
49  for(;;) {
50  t = walk->m_parent;
51  if (t == NULL) return NULL;
52  if (t->which_child(walk) != direction) return t;
53  walk = t;
54  }
55  }
56  }
57  t_rawptr peakchild(bool direction) throw() {
58  t_self* walk = this;
59  for(;;) {
60  t_rawptr next = walk->child(direction);
61  if (next == NULL) return walk;
62  walk = next;
63  }
64  }
65  t_node * prev() throw() {return step(false);}
66  t_node * next() throw() {return step(true);}
67  private:
68  ~_avltree_node() throw() {}
69  };
70 
71 
72  template<typename t_storage,typename t_comparator = comparator_default>
73  class avltree_t {
74  public:
78  typedef t_storage t_item;
79  private:
81 #if 1//MSVC8 bug fix
83  typedef t_node * t_noderawptr;
84 #else
85  typedef typename t_node::t_ptr t_nodeptr;
86  typedef typename t_node::t_rawptr t_noderawptr;
87 #endif
88 
89  static bool is_ptr_valid(t_nodeptr const & p) { return p.is_valid(); }
90  static bool is_ptr_valid(t_node const * p) { return p != NULL; }
91 
92  template<typename t_item1,typename t_item2>
93  inline static int compare(const t_item1 & p_item1, const t_item2 & p_item2) {
94  return t_comparator::compare(p_item1,p_item2);
95  }
96 
97  t_nodeptr m_root;
98 
99  static t_size calc_depth(const t_nodeptr & ptr)
100  {
101  return ptr.is_valid() ? 1+ptr->m_depth : 0;
102  }
103 
104  static void recalc_depth(t_nodeptr const& ptr) {
105  ptr->m_depth = pfc::max_t(calc_depth(ptr->m_left), calc_depth(ptr->m_right));
106  }
107 
108  static void assert_children(t_nodeptr ptr) {
109  PFC_ASSERT(ptr->m_depth == pfc::max_t(calc_depth(ptr->m_left),calc_depth(ptr->m_right)) );
110  }
111 
112  static t_ssize test_depth(t_nodeptr const& ptr)
113  {
114  if (ptr==0) return 0;
115  else return calc_depth(ptr->m_right) - calc_depth(ptr->m_left);
116  }
117 
118  static t_nodeptr extract_left_leaf(t_nodeptr & p_base) {
119  if (is_ptr_valid(p_base->m_left)) {
120  t_nodeptr ret = extract_left_leaf(p_base->m_left);
121  recalc_depth(p_base);
122  g_rebalance(p_base);
123  return ret;
124  } else {
125  t_nodeptr node = p_base;
126  p_base = node->m_right;
127  if (p_base.is_valid()) p_base->m_parent = node->m_parent;
128  node->m_right.release();
129  node->m_depth = 0;
130  node->m_parent = NULL;
131  return node;
132  }
133  }
134 
135  static t_nodeptr extract_right_leaf(t_nodeptr & p_base) {
136  if (is_ptr_valid(p_base->m_right)) {
137  t_nodeptr ret = extract_right_leaf(p_base->m_right);
138  recalc_depth(p_base);
139  g_rebalance(p_base);
140  return ret;
141  } else {
142  t_nodeptr node = p_base;
143  p_base = node->m_left;
144  if (p_base.is_valid()) p_base->m_parent = node->m_parent;
145  node->m_left.release();
146  node->m_depth = 0;
147  node->m_parent = NULL;
148  return node;
149  }
150  }
151 
152  static void remove_internal(t_nodeptr & p_node) {
153  t_nodeptr oldval = p_node;
154  if (p_node->m_left.is_empty()) {
155  p_node = p_node->m_right;
156  if (p_node.is_valid()) p_node->m_parent = oldval->m_parent;
157  } else if (p_node->m_right.is_empty()) {
158  p_node = p_node->m_left;
159  if (p_node.is_valid()) p_node->m_parent = oldval->m_parent;
160  } else {
161  t_nodeptr swap = extract_left_leaf(p_node->m_right);
162 
163  swap->link_left(oldval->m_left.get_ptr());
164  swap->link_right(oldval->m_right.get_ptr());
165  swap->m_parent = oldval->m_parent;
166  recalc_depth(swap);
167  p_node = swap;
168  }
169  oldval->unlink();
170  }
171 
172  template<typename t_nodewalk,typename t_callback>
173  static void __enum_items_recur(t_nodewalk * p_node,t_callback & p_callback) {
174  if (is_ptr_valid(p_node)) {
175  __enum_items_recur<t_nodewalk>(p_node->m_left.get_ptr(),p_callback);
176  p_callback (p_node->m_content);
177  __enum_items_recur<t_nodewalk>(p_node->m_right.get_ptr(),p_callback);
178  }
179  }
180  template<typename t_search>
181  static t_node * g_find_or_add_node(t_nodeptr & p_base,t_node * parent,t_search const & p_search,bool & p_new)
182  {
183  if (p_base.is_empty()) {
184  p_base = new t_node(p_search);
185  p_base->m_parent = parent;
186  p_new = true;
187  return p_base.get_ptr();
188  }
189 
190  PFC_ASSERT( p_base->m_parent == parent );
191 
192  int result = compare(p_base->m_content,p_search);
193  if (result > 0) {
194  t_node * ret = g_find_or_add_node<t_search>(p_base->m_left,p_base.get_ptr(),p_search,p_new);
195  if (p_new) {
196  recalc_depth(p_base);
197  g_rebalance(p_base);
198  }
199  return ret;
200  } else if (result < 0) {
201  t_node * ret = g_find_or_add_node<t_search>(p_base->m_right,p_base.get_ptr(),p_search,p_new);
202  if (p_new) {
203  recalc_depth(p_base);
204  g_rebalance(p_base);
205  }
206  return ret;
207  } else {
208  p_new = false;
209  return p_base.get_ptr();
210  }
211  }
212 
213 
214 
215  template<typename t_search>
216  static t_storage * g_find_or_add(t_nodeptr & p_base,t_node * parent,t_search const & p_search,bool & p_new) {
217  return &g_find_or_add_node(p_base,parent,p_search,p_new)->m_content;
218  }
219 
220 
221  static void g_rotate_right(t_nodeptr & oldroot) {
222  t_nodeptr newroot ( oldroot->m_right );
223  oldroot->link_child(true, newroot->m_left.get_ptr());
224  newroot->m_left = oldroot;
225  newroot->m_parent = oldroot->m_parent;
226  oldroot->m_parent = newroot.get_ptr();
227  recalc_depth(oldroot);
228  recalc_depth(newroot);
229  oldroot = newroot;
230  }
231 
232  static void g_rotate_left(t_nodeptr & oldroot) {
233  t_nodeptr newroot ( oldroot->m_left );
234  oldroot->link_child(false, newroot->m_right.get_ptr());
235  newroot->m_right = oldroot;
236  newroot->m_parent = oldroot->m_parent;
237  oldroot->m_parent = newroot.get_ptr();
238  recalc_depth(oldroot);
239  recalc_depth(newroot);
240  oldroot = newroot;
241  }
242 
243  static void g_rebalance(t_nodeptr & p_node) {
244  t_ssize balance = test_depth(p_node);
245  if (balance > 1) {
246  //right becomes root
247  if (test_depth(p_node->m_right) < 0) {
248  g_rotate_left(p_node->m_right);
249  }
250  g_rotate_right(p_node);
251  } else if (balance < -1) {
252  //left becomes root
253  if (test_depth(p_node->m_left) > 0) {
254  g_rotate_right(p_node->m_left);
255  }
256  g_rotate_left(p_node);
257  }
258  selftest(p_node);
259  }
260 
261  template<typename t_search>
262  static bool g_remove(t_nodeptr & p_node,t_search const & p_search) {
263  if (p_node.is_empty()) return false;
264 
265  int result = compare(p_node->m_content,p_search);
266  if (result == 0) {
267  remove_internal(p_node);
268  if (is_ptr_valid(p_node)) {
269  recalc_depth(p_node);
270  g_rebalance(p_node);
271  }
272  return true;
273  } else {
274  if (g_remove<t_search>(result > 0 ? p_node->m_left : p_node->m_right,p_search)) {
275  recalc_depth(p_node);
276  g_rebalance(p_node);
277  return true;
278  } else {
279  return false;
280  }
281  }
282  }
283 
284  static void selftest(t_nodeptr const& p_node) {
285  #if 0 //def _DEBUG//SLOW!
286  if (is_ptr_valid(p_node)) {
287  selftest(p_node->m_left);
288  selftest(p_node->m_right);
289  assert_children(p_node);
290  t_ssize delta = test_depth(p_node);
291  PFC_ASSERT(delta >= -1 && delta <= 1);
292 
293  if (p_node->m_left.is_valid()) {
294  PFC_ASSERT( p_node.get_ptr() == p_node->m_left->m_parent );
295  }
296  if (p_node->m_right.is_valid()) {
297  PFC_ASSERT( p_node.get_ptr() == p_node->m_right->m_parent );
298  }
299 
300  if (is_ptr_valid(p_node->m_parent)) {
301  PFC_ASSERT(p_node == p_node->m_parent->m_left || p_node == p_node->m_parent->m_right);
302  }
303  }
304  #endif
305  }
306 
307 
308  static t_size calc_count(const t_node * p_node) throw() {
309  if (is_ptr_valid(p_node)) {
310  return 1 + calc_count(p_node->m_left.get_ptr()) + calc_count(p_node->m_right.get_ptr());
311  } else {
312  return 0;
313  }
314  }
315 
316  template<typename t_param>
317  t_storage * _find_item_ptr(t_param const & p_item) const {
318  t_node* ptr = m_root.get_ptr();
319  while(is_ptr_valid(ptr)) {
320  int result = compare(ptr->m_content,p_item);
321  if (result > 0) ptr=ptr->m_left.get_ptr();
322  else if (result < 0) ptr=ptr->m_right.get_ptr();
323  else return &ptr->m_content;
324  }
325  return NULL;
326  }
327 
328  template<typename t_param>
329  t_node * _find_node_ptr(t_param const & p_item) const {
330  t_node* ptr = m_root.get_ptr();
331  while(is_ptr_valid(ptr)) {
332  int result = compare(ptr->m_content,p_item);
333  if (result > 0) ptr=ptr->m_left.get_ptr();
334  else if (result < 0) ptr=ptr->m_right.get_ptr();
335  else return ptr;
336  }
337  return NULL;
338  }
339 
340  template<bool inclusive,bool above,typename t_search> t_storage * __find_nearest(const t_search & p_search) const {
341  t_node * ptr = m_root.get_ptr();
342  t_storage * found = NULL;
343  while(is_ptr_valid(ptr)) {
344  int result = compare(ptr->m_content,p_search);
345  if (above) result = -result;
346  if (inclusive && result == 0) {
347  //direct hit
348  found = &ptr->m_content;
349  break;
350  } else if (result < 0) {
351  //match
352  found = &ptr->m_content;
353  ptr = ptr->child(!above);
354  } else {
355  //mismatch
356  ptr = ptr->child(above);
357  }
358  }
359  return found;
360  }
361  public:
362  avltree_t() : m_root(NULL) {}
363  ~avltree_t() {reset();}
364  const t_self & operator=(const t_self & p_other) {__copy(p_other);return *this;}
365  avltree_t(const t_self & p_other) : m_root(NULL) {try{__copy(p_other);} catch(...) {remove_all(); throw;}}
366 
367  template<typename t_other> const t_self & operator=(const t_other & p_other) {copy_list_enumerated(*this,p_other);return *this;}
368  template<typename t_other> avltree_t(const t_other & p_other) : m_root(NULL) {try{copy_list_enumerated(*this,p_other);}catch(...){remove_all(); throw;}}
369 
370 
371  template<bool inclusive,bool above,typename t_search> const t_storage * find_nearest_item(const t_search & p_search) const {
372  return __find_nearest<inclusive,above>(p_search);
373  }
374 
375  template<bool inclusive,bool above,typename t_search> t_storage * find_nearest_item(const t_search & p_search) {
376  return __find_nearest<inclusive,above>(p_search);
377  }
378 
379  template<typename t_param>
380  t_storage & add_item(t_param const & p_item) {
381  bool dummy;
382  return add_item_ex(p_item,dummy);
383  }
384 
385  template<typename t_param>
386  t_self & operator+=(const t_param & p_item) {add_item(p_item);return *this;}
387 
388  template<typename t_param>
389  t_self & operator-=(const t_param & p_item) {remove_item(p_item);return *this;}
390 
392  template<typename t_param>
393  bool add_item_check(t_param const & item) {
394  bool isNew = false;
395  g_find_or_add(m_root,NULL,item,isNew);
396  selftest(m_root);
397  return isNew;
398  }
399  template<typename t_param>
400  t_storage & add_item_ex(t_param const & p_item,bool & p_isnew) {
401  t_storage * ret = g_find_or_add(m_root,NULL,p_item,p_isnew);
402  selftest(m_root);
403  return *ret;
404  }
405 
406  template<typename t_param>
407  void set_item(const t_param & p_item) {
408  bool isnew;
409  t_storage & found = add_item_ex(p_item,isnew);
410  if (isnew) found = p_item;
411  }
412 
413  template<typename t_param>
414  const t_storage * find_item_ptr(t_param const & p_item) const {return _find_item_ptr(p_item);}
415 
417  template<typename t_param>
418  t_storage * find_item_ptr(t_param const & p_item) { return _find_item_ptr(p_item); }
419 
420  template<typename t_param> const_iterator find(t_param const & item) const { return _find_node_ptr(item);}
421 
423  template<typename t_param> iterator find(t_param const & item) { return _find_node_ptr(item);}
424 
425 
426  template<typename t_param>
427  bool contains(const t_param & p_item) const {
428  return find_item_ptr(p_item) != NULL;
429  }
430 
432  template<typename t_param>
433  bool have_item(const t_param & p_item) const {return contains(p_item);}
434 
435  void remove_all() throw() {
436  _unlink_recur(m_root);
437  m_root.release();
438  }
439 
440  bool remove(const_iterator const& iter) {
441  PFC_ASSERT(iter.is_valid());
442  return remove_item(*iter);//OPTIMIZEME
443  //should never return false unless there's a bug in calling code
444  }
445 
446  template<typename t_param>
447  bool remove_item(t_param const & p_item) {
448  bool ret = g_remove<t_param>(m_root,p_item);
449  selftest(m_root);
450  return ret;
451  }
452 
453  t_size get_count() const throw() {
454  return calc_count(m_root.get_ptr());
455  }
456 
457  template<typename t_callback>
458  void enumerate(t_callback & p_callback) const {
459  __enum_items_recur<const t_node>(m_root.get_ptr(),p_callback);
460  }
461 
464  template<typename t_callback>
465  void _enumerate_var(t_callback & p_callback) { __enum_items_recur<t_node>(m_root.get_ptr(),p_callback); }
466 
467  template<typename t_param> iterator insert(const t_param & p_item) {
468  bool isNew;
469  t_node * ret = g_find_or_add_node(m_root,NULL,p_item,isNew);
470  selftest(m_root);
471  return ret;
472  }
473 
474  //deprecated backwards compatibility method wrappers
475  template<typename t_param> t_storage & add(const t_param & p_item) {return add_item(p_item);}
476  template<typename t_param> t_storage & add_ex(const t_param & p_item,bool & p_isnew) {return add_item_ex(p_item,p_isnew);}
477  template<typename t_param> const t_storage * find_ptr(t_param const & p_item) const {return find_item_ptr(p_item);}
478  template<typename t_param> t_storage * find_ptr(t_param const & p_item) {return find_item_ptr(p_item);}
479  template<typename t_param> bool exists(t_param const & p_item) const {return have_item(p_item);}
480  void reset() {remove_all();}
481 
482 
483 
484 
485  const_iterator first() const throw() {return _firstlast(false);}
486  const_iterator last() const throw() {return _firstlast(true);}
488  iterator _first_var() { return _firstlast(false); }
490  iterator _last_var() { return _firstlast(true); }
491 
492  template<typename t_param> bool get_first(t_param & p_item) const throw() {
493  const_iterator iter = first();
494  if (!iter.is_valid()) return false;
495  p_item = *iter;
496  return true;
497  }
498  template<typename t_param> bool get_last(t_param & p_item) const throw() {
499  const_iterator iter = last();
500  if (!iter.is_valid()) return false;
501  p_item = *iter;
502  return true;
503  }
504 
505  static bool equals(const t_self & v1, const t_self & v2) {
506  return listEquals(v1,v2);
507  }
508  bool operator==(const t_self & other) const {return equals(*this,other);}
509  bool operator!=(const t_self & other) const {return !equals(*this,other);}
510 
511  private:
512  static void _unlink_recur(t_nodeptr & node) {
513  if (node.is_valid()) {
514  _unlink_recur(node->m_left);
515  _unlink_recur(node->m_right);
516  node->unlink();
517  }
518  }
519  t_node* _firstlast(bool which) const throw() {
520  if (m_root.is_empty()) return NULL;
521  for(t_node * walk = m_root.get_ptr(); ; ) {
522  t_node * next = walk->child(which);
523  if (next == NULL) return walk;
524  PFC_ASSERT( next->m_parent == walk );
525  walk = next;
526  }
527  }
528  static t_nodeptr __copy_recur(t_node * p_source,t_node * parent) {
529  if (p_source == NULL) {
530  return NULL;
531  } else {
532  t_nodeptr newnode = new t_node(p_source->m_content);
533  newnode->m_depth = p_source->m_depth;
534  newnode->m_left = __copy_recur(p_source->m_left.get_ptr(),newnode.get_ptr());
535  newnode->m_right = __copy_recur(p_source->m_right.get_ptr(),newnode.get_ptr());
536  newnode->m_parent = parent;
537  return newnode;
538  }
539  }
540 
541  void __copy(const t_self & p_other) {
542  reset();
543  m_root = __copy_recur(p_other.m_root.get_ptr(),NULL);
544  selftest(m_root);
545  }
546  };
547 
548 
549  template<typename t_storage,typename t_comparator>
550  class traits_t<avltree_t<t_storage,t_comparator> > : public traits_default_movable {};
551 }
bool add_item_check(t_param const &item)
Returns true when the list has been altered, false when the item was already present before...
Definition: avltree.h:393
Base class for list nodes. Implemented by list implementers.
Definition: iterators.h:3
bool exists(t_param const &p_item) const
Definition: avltree.h:479
t_storage & add(const t_param &p_item)
Definition: avltree.h:475
bool get_first(t_param &p_item) const
Definition: avltree.h:492
refcounted_object_ptr_t< t_self > t_ptr
Definition: avltree.h:10
static bool listEquals(const t_list1 &p_list1, const t_list2 &p_list2)
Definition: iterators.h:105
void _enumerate_var(t_callback &p_callback)
Allows callback to modify the tree content. Unsafe! Caller must not modify items in a way that change...
Definition: avltree.h:465
t_size get_count() const
Definition: avltree.h:453
bool operator!=(const t_self &other) const
Definition: avltree.h:509
t_node * _firstlast(bool which) const
Definition: avltree.h:519
t_self * t_rawptr
Definition: avltree.h:11
void copy_list_enumerated(t_receiver &p_receiver, const t_giver &p_giver)
Definition: primitives.h:819
const t_storage * find_nearest_item(const t_search &p_search) const
Definition: avltree.h:371
void link_child(bool which, t_self *ptr)
Definition: avltree.h:27
static bool is_ptr_valid(t_nodeptr const &p)
Definition: avltree.h:89
refcounted_object_ptr_t< t_node > t_nodeptr
Definition: avltree.h:82
t_rawptr child(bool which) const
Definition: avltree.h:39
void set_item(const t_param &p_item)
Definition: avltree.h:407
int compare(t1 const &p1, t2 const &p2)
Definition: pathUtils.h:29
t_storage * __find_nearest(const t_search &p_search) const
Definition: avltree.h:340
const t_self & operator=(const t_self &p_other)
Definition: avltree.h:364
iterator _first_var()
Unsafe! Caller must not modify items in a way that changes sort order!
Definition: avltree.h:488
static void recalc_depth(t_nodeptr const &ptr)
Definition: avltree.h:104
static bool equals(const t_self &v1, const t_self &v2)
Definition: avltree.h:505
void reset()
Definition: avltree.h:480
t_node * _find_node_ptr(t_param const &p_item) const
Definition: avltree.h:329
void __copy(const t_self &p_other)
Definition: avltree.h:541
static t_size calc_count(const t_node *p_node)
Definition: avltree.h:308
static bool g_remove(t_nodeptr &p_node, t_search const &p_search)
Definition: avltree.h:262
t_rawptr m_parent
Definition: avltree.h:14
t_self * walk(bool forward)
Definition: iterators.h:14
bool is_valid() const
Definition: iterators.h:24
static void selftest(t_nodeptr const &p_node)
Definition: avltree.h:284
static t_size calc_depth(const t_nodeptr &ptr)
Definition: avltree.h:99
t_self & operator+=(const t_param &p_item)
Definition: avltree.h:386
bool have_item(const t_param &p_item) const
Same as contains().
Definition: avltree.h:433
static void remove_internal(t_nodeptr &p_node)
Definition: avltree.h:152
t_storage & add_ex(const t_param &p_item, bool &p_isnew)
Definition: avltree.h:476
_avltree_node< t_storage > t_self
Definition: avltree.h:7
t_node::t_rawptr t_noderawptr
Definition: avltree.h:86
t_node * next()
Definition: avltree.h:66
t_storage * find_ptr(t_param const &p_item)
Definition: avltree.h:478
pfc::iterator< t_storage > iterator
Definition: avltree.h:77
static void g_rebalance(t_nodeptr &p_node)
Definition: avltree.h:243
t_node * prev()
Definition: avltree.h:65
t_rawptr peakchild(bool direction)
Definition: avltree.h:57
t_storage * _find_item_ptr(t_param const &p_item) const
Definition: avltree.h:317
t_size m_depth
Definition: avltree.h:16
iterator _last_var()
Unsafe! Caller must not modify items in a way that changes sort order!
Definition: avltree.h:490
const_iterator find(t_param const &item) const
Definition: avltree.h:420
const_iterator first() const
Definition: avltree.h:485
void enumerate(t_callback &p_callback) const
Definition: avltree.h:458
static void __enum_items_recur(t_nodewalk *p_node, t_callback &p_callback)
Definition: avltree.h:173
size_t t_size
Definition: int_types.h:48
iterator find(t_param const &item)
Unsafe! Caller must not modify items in a way that changes sort order!
Definition: avltree.h:423
avltree_t(const t_self &p_other)
Definition: avltree.h:365
static t_ssize test_depth(t_nodeptr const &ptr)
Definition: avltree.h:112
static t_nodeptr __copy_recur(t_node *p_source, t_node *parent)
Definition: avltree.h:528
t_node::t_ptr t_nodeptr
Definition: avltree.h:85
_avltree_node< t_storage > t_node
Definition: avltree.h:80
avltree_t(const t_other &p_other)
Definition: avltree.h:368
pfc::const_iterator< t_storage > const_iterator
Definition: avltree.h:76
static t_storage * g_find_or_add(t_nodeptr &p_base, t_node *parent, t_search const &p_search, bool &p_new)
Definition: avltree.h:216
t_nodeptr m_root
Definition: avltree.h:97
void selftest()
Definition: selftest.cpp:79
bool which_child(const t_self *ptr) const
Definition: avltree.h:40
void link_left(t_self *ptr)
Definition: avltree.h:18
static void g_rotate_left(t_nodeptr &oldroot)
Definition: avltree.h:232
t_node * t_noderawptr
Definition: avltree.h:83
t_self & operator-=(const t_param &p_item)
Definition: avltree.h:389
iterator insert(const t_param &p_item)
Definition: avltree.h:467
_avltree_node(t_param const &param)
Definition: avltree.h:8
static void assert_children(t_nodeptr ptr)
Definition: avltree.h:108
void release()
Definition: avltree.h:37
t_storage & add_item(t_param const &p_item)
Definition: avltree.h:380
t_storage & add_item_ex(t_param const &p_item, bool &p_isnew)
Definition: avltree.h:400
pfc::sized_int_t< sizeof(size_t) >::t_signed t_ssize
Definition: int_types.h:49
static int compare(const t_item1 &p_item1, const t_item2 &p_item2)
Definition: avltree.h:93
const t_storage * find_ptr(t_param const &p_item) const
Definition: avltree.h:477
static void _unlink_recur(t_nodeptr &node)
Definition: avltree.h:512
avltree_t< t_storage, t_comparator > t_self
Definition: avltree.h:75
t_rawptr step(bool direction)
Definition: avltree.h:44
static t_nodeptr extract_left_leaf(t_nodeptr &p_base)
Definition: avltree.h:118
t_storage t_item
Definition: avltree.h:78
const t_storage * find_item_ptr(t_param const &p_item) const
Definition: avltree.h:414
static t_nodeptr extract_right_leaf(t_nodeptr &p_base)
Definition: avltree.h:135
bool operator==(const t_self &other) const
Definition: avltree.h:508
void add_ref()
Definition: avltree.h:36
t_storage * find_item_ptr(t_param const &p_item)
Unsafe! Caller must not modify items in a way that changes sort order!
Definition: avltree.h:418
static void g_rotate_right(t_nodeptr &oldroot)
Definition: avltree.h:221
static bool is_ptr_valid(t_node const *p)
Definition: avltree.h:90
T max_t(const T &item1, const T &item2)
Definition: primitives.h:553
_list_node< t_storage > t_node
Definition: avltree.h:6
bool get_last(t_param &p_item) const
Definition: avltree.h:498
const_iterator last() const
Definition: avltree.h:486
static t_node * g_find_or_add_node(t_nodeptr &p_base, t_node *parent, t_search const &p_search, bool &p_new)
Definition: avltree.h:181
t_storage * find_nearest_item(const t_search &p_search)
Definition: avltree.h:375
void link_right(t_self *ptr)
Definition: avltree.h:22
void remove_all()
Definition: avltree.h:435
const t_self & operator=(const t_other &p_other)
Definition: avltree.h:367
bool contains(const t_param &p_item) const
Definition: avltree.h:427
bool remove_item(t_param const &p_item)
Definition: avltree.h:447
bool equals(const t1 &v1, const t2 &v2)
Definition: pathUtils.h:27