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