1 : // xtree internal header
2 : #pragma once
3 : #ifndef _XTREE_
4 : #define _XTREE_
5 : #ifndef RC_INVOKED
6 : #include <functional>
7 : #include <memory>
8 : #include <stdexcept>
9 :
10 : #ifdef _MSC_VER
11 : #pragma pack(push,_CRT_PACKING)
12 : #pragma warning(push,3)
13 : #pragma warning(disable:4127)
14 : #endif /* _MSC_VER */
15 :
16 : _STD_BEGIN
17 :
18 : // TEMPLATE CLASS _Tree_nod
19 : template<class _Traits>
20 : class _Tree_nod
21 : : public _Traits // traits form ultimate base
22 : { // base class for _Tree_ptr to hold allocator _Alnod
23 : protected:
24 : struct _Node;
25 : friend struct _Node;
26 : typedef _Node *_Nodeptr; // _Node allocator must have ordinary pointers
27 :
28 : typedef typename _Traits::allocator_type allocator_type;
29 : typedef typename _Traits::key_compare key_compare;
30 : typedef typename _Traits::value_type value_type;
31 :
32 : struct _Node
33 : { // tree node
34 : _Node(_Nodeptr _Larg, _Nodeptr _Parg, _Nodeptr _Rarg,
35 : const value_type& _Val, char _Carg)
36 : : _Left(_Larg), _Parent(_Parg), _Right(_Rarg),
37 : _Myval(_Val), _Color(_Carg), _Isnil(false)
38 2 : { // construct a node with value
39 2 : }
40 :
41 : _Nodeptr _Left; // left subtree, or smallest element if head
42 : _Nodeptr _Parent; // parent, or root of tree if head
43 : _Nodeptr _Right; // right subtree, or largest element if head
44 : value_type _Myval; // the stored value, unused if head
45 : char _Color; // _Red or _Black, _Black if head
46 : char _Isnil; // true only if head (also nil) node
47 : };
48 :
49 : _Tree_nod(const key_compare& _Parg,
50 : allocator_type _Al)
51 : : _Traits(_Parg, _Al), _Alnod(_Al)
52 2 : { // construct traits from _Parg and allocator from _Al
53 2 : }
54 :
55 : typename allocator_type::template rebind<_Node>::other
56 : _Alnod; // allocator object for nodes
57 : };
58 :
59 : // TEMPLATE CLASS _Tree_ptr
60 : template<class _Traits>
61 : class _Tree_ptr
62 : : public _Tree_nod<_Traits>
63 : { // base class for _Tree_val to hold allocator _Alptr
64 : #if _HAS_ITERATOR_DEBUGGING
65 : public:
66 : #else /* _HAS_ITERATOR_DEBUGGING */
67 : protected:
68 : #endif /* _HAS_ITERATOR_DEBUGGING */
69 : typedef _Tree_nod<_Traits> _Mybase;
70 : typedef typename _Mybase::_Node _Node;
71 : typedef typename _Mybase::_Nodeptr _Nodeptr;
72 : typedef typename _Traits::allocator_type allocator_type;
73 : typedef typename _Traits::key_compare key_compare;
74 :
75 : _Tree_ptr(const key_compare& _Parg,
76 : allocator_type _Al)
77 : : _Tree_nod<_Traits>(_Parg, _Al), _Alptr(_Al)
78 2 : { // construct base, and allocator from _Al
79 2 : }
80 :
81 : typename allocator_type::template rebind<_Nodeptr>::other
82 : _Alptr; // allocator object for pointers to nodes
83 : };
84 :
85 : // TEMPLATE CLASS _Tree_val
86 : template<class _Traits>
87 : class _Tree_val
88 : : public _Tree_ptr<_Traits>
89 : { // base class for _Tree to hold allocator _Alval
90 : protected:
91 : typedef typename _Traits::allocator_type allocator_type;
92 : typedef typename _Traits::key_compare key_compare;
93 :
94 : _Tree_val(const key_compare& _Parg,
95 : allocator_type _Al)
96 : : _Tree_ptr<_Traits>(_Parg, _Al), _Alval(_Al)
97 2 : { // construct base, and allocator from _Al
98 2 : }
99 :
100 : allocator_type _Alval; // allocator object for values stored in nodes
101 : };
102 :
103 : // TEMPLATE CLASS _Tree
104 : template<class _Traits>
105 : class _Tree
106 : : public _Tree_val<_Traits>
107 : { // ordered red-black tree for [multi_]{map set}
108 : public:
109 : typedef _Tree<_Traits> _Myt;
110 : typedef _Tree_val<_Traits> _Mybase;
111 : typedef typename _Traits::key_type key_type;
112 : typedef typename _Traits::key_compare key_compare;
113 : typedef typename _Traits::value_compare value_compare;
114 : typedef typename _Traits::value_type value_type;
115 : typedef typename _Traits::allocator_type allocator_type;
116 :
117 : #if _HAS_IMMUTABLE_SETS
118 : typedef typename _Traits::_ITptr _ITptr;
119 : typedef typename _Traits::_IReft _IReft;
120 :
121 : #else /* _HAS_IMMUTABLE_SETS */
122 : typedef typename allocator_type::pointer _ITptr;
123 : typedef typename allocator_type::reference _IReft;
124 : #endif /* _HAS_IMMUTABLE_SETS */
125 :
126 : protected:
127 :
128 : typedef typename _Mybase::_Node _Node;
129 : typedef typename _Mybase::_Nodeptr _Nodeptr;
130 :
131 : typedef typename allocator_type::template rebind<_Nodeptr>::other
132 : _Nodeptr_alloc;
133 : typedef typename _Nodeptr_alloc::reference _Nodepref;
134 :
135 : typedef typename allocator_type::template rebind<key_type>::other
136 : _Key_alloc;
137 : typedef typename _Key_alloc::const_reference _Keyref;
138 :
139 : typedef typename allocator_type::template rebind<char>::other
140 : _Char_alloc;
141 : typedef typename _Char_alloc::reference _Charref;
142 :
143 :
144 : typedef typename allocator_type::reference _Vref;
145 :
146 : enum _Redbl
147 : { // colors for link to parent
148 : _Red, _Black};
149 :
150 : static _Charref _Color(_Nodeptr _Pnode)
151 2 : { // return reference to color in node
152 2 : return ((_Charref)(*_Pnode)._Color);
153 2 : }
154 :
155 : static _Charref _Isnil(_Nodeptr _Pnode)
156 2 : { // return reference to nil flag in node
157 2 : return ((_Charref)(*_Pnode)._Isnil);
158 2 : }
159 :
160 : static _Keyref _Key(_Nodeptr _Pnode)
161 2 : { // return reference to key in node
162 2 : return (_Mybase::_Kfn(_Myval(_Pnode)));
163 2 : }
164 :
165 : static _Nodepref _Left(_Nodeptr _Pnode)
166 2 : { // return reference to left pointer in node
167 2 : return ((_Nodepref)(*_Pnode)._Left);
168 2 : }
169 :
170 : static _Nodepref _Parent(_Nodeptr _Pnode)
171 2 : { // return reference to parent pointer in node
172 2 : return ((_Nodepref)(*_Pnode)._Parent);
173 2 : }
174 :
175 : static _Nodepref _Right(_Nodeptr _Pnode)
176 2 : { // return reference to right pointer in node
177 2 : return ((_Nodepref)(*_Pnode)._Right);
178 2 : }
179 :
180 : static _Vref _Myval(_Nodeptr _Pnode)
181 2 : { // return reference to value in node
182 2 : return ((_Vref)(*_Pnode)._Myval);
183 2 : }
184 :
185 : public:
186 : typedef typename allocator_type::size_type size_type;
187 : typedef typename allocator_type::difference_type _Dift;
188 : typedef _Dift difference_type;
189 : typedef typename allocator_type::pointer _Tptr;
190 : typedef typename allocator_type::const_pointer _Ctptr;
191 : typedef typename allocator_type::reference _Reft;
192 : typedef _Tptr pointer;
193 : typedef _Ctptr const_pointer;
194 : typedef _Reft reference;
195 : typedef typename allocator_type::const_reference const_reference;
196 :
197 : // CLASS const_iterator
198 : class const_iterator;
199 : friend class const_iterator;
200 :
201 : class const_iterator
202 : : public _Bidit<value_type, _Dift, _Ctptr, const_reference>
203 : { // iterator for nonmutable _Tree
204 : public:
205 : friend class _Tree<_Traits>;
206 : typedef bidirectional_iterator_tag iterator_category;
207 : typedef _Dift difference_type;
208 : typedef _Ctptr pointer;
209 : typedef const_reference reference;
210 :
211 : #if _SECURE_SCL
212 : typedef _Range_checked_iterator_tag _Checked_iterator_category;
213 : #endif
214 :
215 : const_iterator()
216 : : _Ptr(0)
217 1 : { // construct with null node pointer
218 1 : }
219 :
220 : #if _HAS_ITERATOR_DEBUGGING
221 : #define _TREE_CONST_ITERATOR(ppnode) const_iterator(ppnode, this)
222 :
223 : const_iterator(_Nodeptr _Pnode, const _Myt *_Plist=NULL)
224 : : _Ptr(_Pnode)
225 2 : { // construct with node pointer _Pnode
226 2 : this->_Adopt(_Plist);
227 2 : }
228 :
229 : #elif _SECURE_SCL
230 : #define _TREE_CONST_ITERATOR(ppnode) const_iterator(ppnode, this)
231 :
232 : const_iterator(_Nodeptr _Pnode, const _Myt *_Plist)
233 : : _Ptr(_Pnode)
234 : { // construct with node pointer _Pnode
235 : _SCL_SECURE_VALIDATE(_Plist != NULL);
236 : this->_Set_container(_Plist);
237 : }
238 :
239 : #else
240 : #define _TREE_CONST_ITERATOR(ppnode) const_iterator(ppnode)
241 :
242 : explicit const_iterator(_Nodeptr _Pnode)
243 : : _Ptr(_Pnode)
244 : { // construct with node pointer _Pnode
245 : }
246 : #endif /* _HAS_ITERATOR_DEBUGGING */
247 :
248 : const_reference operator*() const
249 1 : { // return designated value
250 :
251 : #if _HAS_ITERATOR_DEBUGGING
252 : if (this->_Mycont == 0
253 : || _Ptr == 0
254 1 : || _Ptr == ((_Myt *)this->_Mycont)->_Myhead)
255 : {
256 0 : _DEBUG_ERROR("map/set iterator not dereferencable");
257 0 : _SCL_SECURE_OUT_OF_RANGE;
258 : }
259 : #else
260 : _SCL_SECURE_VALIDATE(this->_Has_container());
261 : _SCL_SECURE_VALIDATE_RANGE(_Ptr != ((_Myt *)(this->_Getmycont()))->_Myhead);
262 : #endif /* _HAS_ITERATOR_DEBUGGING */
263 :
264 1 : return (_Myval(_Ptr));
265 1 : }
266 :
267 : _Ctptr operator->() const
268 1 : { // return pointer to class object
269 1 : return (&**this);
270 1 : }
271 :
272 : const_iterator& operator++()
273 1 : { // preincrement
274 1 : _Inc();
275 1 : return (*this);
276 1 : }
277 :
278 : const_iterator operator++(int)
279 0 : { // postincrement
280 0 : const_iterator _Tmp = *this;
281 0 : ++*this;
282 0 : return (_Tmp);
283 0 : }
284 :
285 : const_iterator& operator--()
286 0 : { // predecrement
287 0 : _Dec();
288 0 : return (*this);
289 0 : }
290 :
291 : const_iterator operator--(int)
292 : { // postdecrement
293 : const_iterator _Tmp = *this;
294 : --*this;
295 : return (_Tmp);
296 : }
297 :
298 : bool operator==(const const_iterator& _Right) const
299 2 : { // test for iterator equality
300 :
301 : #if _HAS_ITERATOR_DEBUGGING
302 2 : if (this->_Mycont == 0 || this->_Mycont != _Right._Mycont)
303 : {
304 0 : _DEBUG_ERROR("map/set iterators incompatible");
305 0 : _SCL_SECURE_INVALID_ARGUMENT;
306 : }
307 : #else
308 : _SCL_SECURE_VALIDATE(this->_Has_container() && this->_Same_container(_Right));
309 : #endif /* _HAS_ITERATOR_DEBUGGING */
310 :
311 2 : return (_Ptr == _Right._Ptr);
312 2 : }
313 :
314 : bool operator!=(const const_iterator& _Right) const
315 1 : { // test for iterator inequality
316 1 : return (!(*this == _Right));
317 1 : }
318 :
319 : void _Dec()
320 0 : { // move to node with next smaller value
321 :
322 : #if _HAS_ITERATOR_DEBUGGING
323 : if (this->_Mycont == 0
324 0 : || _Ptr == 0)
325 : {
326 0 : _DEBUG_ERROR("map/set iterator not decrementable");
327 0 : _SCL_SECURE_INVALID_ARGUMENT;
328 : }
329 : #else
330 : _SCL_SECURE_VALIDATE(this->_Has_container());
331 : #endif /* _HAS_ITERATOR_DEBUGGING */
332 :
333 0 : if (_Isnil(_Ptr))
334 : {
335 0 : _Ptr = _Right(_Ptr); // end() ==> rightmost
336 0 : if (_Isnil(_Ptr))
337 : #if _HAS_ITERATOR_DEBUGGING
338 : {
339 0 : _DEBUG_ERROR("map/set iterator not decrementable");
340 0 : _SCL_SECURE_OUT_OF_RANGE;
341 : }
342 : #elif _SECURE_SCL
343 : {
344 : _SCL_SECURE_OUT_OF_RANGE;
345 : }
346 : #else
347 : return; // begin() shouldn't be incremented, don't move
348 : #endif
349 0 : }
350 0 : else if (!_Isnil(_Left(_Ptr)))
351 0 : _Ptr = _Max(_Left(_Ptr)); // ==> largest of left subtree
352 0 : else
353 : { // climb looking for left subtree
354 : _Nodeptr _Pnode;
355 : while (!_Isnil(_Pnode = _Parent(_Ptr))
356 0 : && _Ptr == _Left(_Pnode))
357 0 : _Ptr = _Pnode; // ==> parent while left subtree
358 0 : if (_Isnil(_Ptr))
359 : #if _HAS_ITERATOR_DEBUGGING
360 : {
361 0 : _DEBUG_ERROR("map/set iterator not decrementable");
362 0 : _SCL_SECURE_OUT_OF_RANGE;
363 : }
364 : #elif _SECURE_SCL
365 : {
366 : _SCL_SECURE_OUT_OF_RANGE;
367 : }
368 : #else
369 : return; // begin() shouldn't be incremented, don't move
370 : #endif
371 0 : else
372 0 : _Ptr = _Pnode; // ==> parent if not head
373 : }
374 0 : }
375 :
376 : void _Inc()
377 1 : { // move to node with next larger value
378 :
379 : #if _HAS_ITERATOR_DEBUGGING
380 : if (this->_Mycont == 0
381 : || _Ptr == 0
382 1 : || _Isnil(_Ptr))
383 : {
384 0 : _DEBUG_ERROR("map/set iterator not incrementable");
385 0 : _SCL_SECURE_OUT_OF_RANGE;
386 : }
387 : #else
388 : _SCL_SECURE_VALIDATE(this->_Has_container());
389 : if (_Isnil(_Ptr))
390 : {
391 : _SCL_SECURE_OUT_OF_RANGE;
392 : // end() shouldn't be incremented, don't move if _SCL_SECURE is not turned on
393 : }
394 : #endif /* _HAS_ITERATOR_DEBUGGING */
395 :
396 1 : else if (!_Isnil(_Right(_Ptr)))
397 0 : _Ptr = _Min(_Right(_Ptr)); // ==> smallest of right subtree
398 0 : else
399 : { // climb looking for right subtree
400 : _Nodeptr _Pnode;
401 : while (!_Isnil(_Pnode = _Parent(_Ptr))
402 1 : && _Ptr == _Right(_Pnode))
403 0 : _Ptr = _Pnode; // ==> parent while right subtree
404 1 : _Ptr = _Pnode; // ==> parent (head if end())
405 : }
406 1 : }
407 :
408 : _Nodeptr _Mynode() const
409 1 : { // return node pointer
410 1 : return (_Ptr);
411 1 : }
412 :
413 : #if _HAS_ITERATOR_DEBUGGING
414 : public:
415 : #else /* _HAS_ITERATOR_DEBUGGING */
416 : protected:
417 : #endif /* _HAS_ITERATOR_DEBUGGING */
418 : _Nodeptr _Ptr; // pointer to node
419 : };
420 :
421 : // CLASS iterator
422 : class iterator;
423 : friend class iterator;
424 :
425 : class iterator
426 : : public const_iterator
427 : { // iterator for mutable _Tree
428 : public:
429 : typedef bidirectional_iterator_tag iterator_category;
430 : typedef _Dift difference_type;
431 : typedef _ITptr pointer;
432 : typedef _IReft reference;
433 :
434 : iterator()
435 : { // construct with null node pointer
436 : }
437 :
438 : #if _HAS_ITERATOR_DEBUGGING
439 : #define _TREE_ITERATOR(ppnode) iterator(ppnode, this)
440 :
441 : iterator(_Nodeptr _Pnode, const _Myt *_Plist=NULL)
442 : : const_iterator(_Pnode, _Plist)
443 2 : { // construct with node pointer _Pnode
444 2 : }
445 :
446 : #elif _SECURE_SCL
447 : #define _TREE_ITERATOR(ppnode) iterator(ppnode, this)
448 :
449 : iterator(_Nodeptr _Pnode, const _Myt *_Plist)
450 : : const_iterator(_Pnode, _Plist)
451 : { // construct with node pointer _Pnode
452 : }
453 :
454 : #else /* _HAS_ITERATOR_DEBUGGING */
455 : #define _TREE_ITERATOR(ppnode) iterator(ppnode)
456 :
457 : explicit iterator(_Nodeptr _Pnode)
458 : : const_iterator(_Pnode)
459 : { // construct with node pointer _Pnode
460 : }
461 : #endif /* _HAS_ITERATOR_DEBUGGING */
462 :
463 : reference operator*() const
464 1 : { // return designated value
465 1 : return ((reference)**(const_iterator *)this);
466 1 : }
467 :
468 : pointer operator->() const
469 : { // return pointer to class object
470 : return (&**this);
471 : }
472 :
473 : iterator& operator++()
474 : { // preincrement
475 : ++(*(const_iterator *)this);
476 : return (*this);
477 : }
478 :
479 : iterator operator++(int)
480 : { // postincrement
481 : iterator _Tmp = *this;
482 : ++*this;
483 : return (_Tmp);
484 : }
485 :
486 : iterator& operator--()
487 0 : { // predecrement
488 0 : --(*(const_iterator *)this);
489 0 : return (*this);
490 0 : }
491 :
492 : iterator operator--(int)
493 : { // postdecrement
494 : iterator _Tmp = *this;
495 : --*this;
496 : return (_Tmp);
497 : }
498 : };
499 :
500 : typedef std::reverse_iterator<iterator> reverse_iterator;
501 : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
502 : typedef pair<iterator, bool> _Pairib;
503 : typedef pair<iterator, iterator> _Pairii;
504 : typedef pair<const_iterator, const_iterator> _Paircc;
505 :
506 : explicit _Tree(const key_compare& _Parg,
507 : const allocator_type& _Al)
508 : : _Mybase(_Parg, _Al)
509 2 : { // construct empty tree
510 2 : _Init();
511 2 : }
512 :
513 : _Tree(const value_type *_First, const value_type *_Last,
514 : const key_compare& _Parg, const allocator_type& _Al)
515 : : _Mybase(_Parg, _Al)
516 : { // construct tree from [_First, _Last) array
517 : _Init();
518 : _TRY_BEGIN
519 : insert(_First, _Last);
520 : _CATCH_ALL
521 : _Tidy();
522 : _RERAISE;
523 : _CATCH_END
524 : }
525 :
526 : _Tree(const _Myt& _Right)
527 : : _Mybase(_Right.key_comp(), _Right.get_allocator())
528 : { // construct tree by copying _Right
529 : _Init();
530 : _TRY_BEGIN
531 : _Copy(_Right);
532 : _CATCH_ALL
533 : _Tidy();
534 : _RERAISE;
535 : _CATCH_END
536 : }
537 :
538 : ~_Tree()
539 1 : { // destroy tree
540 1 : _Tidy();
541 1 : }
542 :
543 : _Myt& operator=(const _Myt& _Right)
544 : { // replace contents from _Right
545 : if (this != &_Right)
546 : { // worth doing
547 : erase(begin(), end());
548 : this->comp = _Right.comp;
549 : _Copy(_Right);
550 : }
551 : return (*this);
552 : }
553 :
554 : iterator begin()
555 2 : { // return iterator for beginning of mutable sequence
556 2 : return (_TREE_ITERATOR(_Lmost()));
557 2 : }
558 :
559 : const_iterator begin() const
560 : { // return iterator for beginning of nonmutable sequence
561 : return (_TREE_CONST_ITERATOR(_Lmost()));
562 : }
563 :
564 : iterator end()
565 2 : { // return iterator for end of mutable sequence
566 2 : return (_TREE_ITERATOR(_Myhead));
567 2 : }
568 :
569 : const_iterator end() const
570 : { // return iterator for end of nonmutable sequence
571 : return (_TREE_CONST_ITERATOR(_Myhead));
572 : }
573 :
574 : iterator _Make_iter(const_iterator _Where) const
575 0 : { // make iterator from const_iterator
576 0 : return (iterator(_TREE_ITERATOR(_Where._Ptr)));
577 0 : }
578 :
579 : reverse_iterator rbegin()
580 : { // return iterator for beginning of reversed mutable sequence
581 : return (reverse_iterator(end()));
582 : }
583 :
584 : const_reverse_iterator rbegin() const
585 : { // return iterator for beginning of reversed nonmutable sequence
586 : return (const_reverse_iterator(end()));
587 : }
588 :
589 : reverse_iterator rend()
590 : { // return iterator for end of reversed mutable sequence
591 : return (reverse_iterator(begin()));
592 : }
593 :
594 : const_reverse_iterator rend() const
595 : { // return iterator for end of reversed nonmutable sequence
596 : return (const_reverse_iterator(begin()));
597 : }
598 :
599 : size_type size() const
600 1 : { // return length of sequence
601 1 : return (_Mysize);
602 1 : }
603 :
604 : size_type max_size() const
605 2 : { // return maximum possible length of sequence
606 2 : return (this->_Alval.max_size());
607 2 : }
608 :
609 : bool empty() const
610 : { // return true only if sequence is empty
611 : return (size() == 0);
612 : }
613 :
614 : allocator_type get_allocator() const
615 : { // return allocator object for values
616 : return (this->_Alval);
617 : }
618 :
619 : key_compare key_comp() const
620 : { // return object for comparing keys
621 : return (this->comp);
622 : }
623 :
624 : value_compare value_comp() const
625 : { // return object for comparing values
626 : return (value_compare(key_comp()));
627 : }
628 :
629 : _Pairib insert(const value_type& _Val)
630 1 : { // try to insert node with value _Val
631 1 : _Nodeptr _Trynode = _Root();
632 1 : _Nodeptr _Wherenode = _Myhead;
633 1 : bool _Addleft = true; // add to left of head if tree empty
634 1 : while (!_Isnil(_Trynode))
635 : { // look for leaf to insert before (_Addleft) or after
636 0 : _Wherenode = _Trynode;
637 0 : _Addleft = _DEBUG_LT_PRED(this->comp,
638 : this->_Kfn(_Val), _Key(_Trynode));
639 0 : _Trynode = _Addleft ? _Left(_Trynode) : _Right(_Trynode);
640 0 : }
641 :
642 1 : if (this->_Multi)
643 0 : return (_Pairib(_Insert(_Addleft, _Wherenode, _Val), true));
644 : else
645 : { // insert only if unique
646 1 : iterator _Where = _TREE_ITERATOR(_Wherenode);
647 1 : if (!_Addleft)
648 : ; // need to test if insert after is okay
649 1 : else if (_Where == begin())
650 1 : return (_Pairib(_Insert(true, _Wherenode, _Val), true));
651 : else
652 0 : --_Where; // need to test if insert before is okay
653 :
654 0 : if (_DEBUG_LT_PRED(this->comp,
655 : _Key(_Where._Mynode()), this->_Kfn(_Val)))
656 0 : return (_Pairib(_Insert(_Addleft, _Wherenode, _Val), true));
657 : else
658 0 : return (_Pairib(_Where, false));
659 : }
660 1 : }
661 :
662 : iterator insert(const_iterator _Where,
663 : const value_type& _Val)
664 1 : { // try to insert node with value _Val using _Where as a hint
665 :
666 : #if _HAS_ITERATOR_DEBUGGING
667 1 : if (_Where._Mycont != this)
668 0 : _DEBUG_ERROR("map/set insert iterator outside range");
669 : #endif /* _HAS_ITERATOR_DEBUGGING */
670 :
671 1 : const_iterator _Next;
672 :
673 1 : if (size() == 0)
674 1 : return (_Insert(true, _Myhead, _Val)); // insert into empty tree
675 1 : else if (this->_Multi)
676 : { // insert even if duplicate
677 0 : if (_Where == begin())
678 : { // insert at beginning if before first element
679 0 : if (!_DEBUG_LT_PRED(this->comp,
680 : _Key(_Where._Mynode()), this->_Kfn(_Val)))
681 0 : return (_Insert(true, _Where._Mynode(), _Val));
682 0 : }
683 0 : else if (_Where == end())
684 : { // insert at end if after last element
685 0 : if (!_DEBUG_LT_PRED(this->comp,
686 : this->_Kfn(_Val), _Key(_Rmost())))
687 0 : return (_Insert(false, _Rmost(), _Val));
688 : }
689 0 : else if (!_DEBUG_LT_PRED(this->comp,
690 : _Key(_Where._Mynode()), this->_Kfn(_Val))
691 0 : && !_DEBUG_LT_PRED(this->comp,
692 : this->_Kfn(_Val), _Key((--(_Next = _Where))._Mynode())))
693 : { // insert before _Where
694 0 : if (_Isnil(_Right(_Next._Mynode())))
695 0 : return (_Insert(false, _Next._Mynode(), _Val));
696 : else
697 0 : return (_Insert(true, _Where._Mynode(), _Val));
698 : }
699 : else if (!_DEBUG_LT_PRED(this->comp,
700 : this->_Kfn(_Val), _Key(_Where._Mynode()))
701 : && (++(_Next = _Where) == end()
702 0 : || !_DEBUG_LT_PRED(this->comp,
703 : _Key(_Next._Mynode()), this->_Kfn(_Val))))
704 : { // insert after _Where
705 0 : if (_Isnil(_Right(_Where._Mynode())))
706 0 : return (_Insert(false, _Where._Mynode(), _Val));
707 : else
708 0 : return (_Insert(true, _Next._Mynode(), _Val));
709 : }
710 : }
711 0 : else
712 : { // insert only if unique
713 1 : if (_Where == begin())
714 : { // insert at beginning if before first element
715 0 : if (_DEBUG_LT_PRED(this->comp,
716 : this->_Kfn(_Val), _Key(_Where._Mynode())))
717 0 : return (_Insert(true, _Where._Mynode(), _Val));
718 0 : }
719 1 : else if (_Where == end())
720 : { // insert at end if after last element
721 1 : if (_DEBUG_LT_PRED(this->comp,
722 : _Key(_Rmost()), this->_Kfn(_Val)))
723 1 : return (_Insert(false, _Rmost(), _Val));
724 : }
725 0 : else if (_DEBUG_LT_PRED(this->comp,
726 : this->_Kfn(_Val), _Key(_Where._Mynode()))
727 0 : && _DEBUG_LT_PRED(this->comp,
728 : _Key((--(_Next = _Where))._Mynode()), this->_Kfn(_Val)))
729 : { // insert before _Where
730 0 : if (_Isnil(_Right(_Next._Mynode())))
731 0 : return (_Insert(false, _Next._Mynode(), _Val));
732 : else
733 0 : return (_Insert(true, _Where._Mynode(), _Val));
734 : }
735 : else if (_DEBUG_LT_PRED(this->comp,
736 : _Key(_Where._Mynode()), this->_Kfn(_Val))
737 : && (++(_Next = _Where) == end()
738 0 : || _DEBUG_LT_PRED(this->comp,
739 : this->_Kfn(_Val), _Key(_Next._Mynode()))))
740 : { // insert after _Where
741 0 : if (_Isnil(_Right(_Where._Mynode())))
742 0 : return (_Insert(false, _Where._Mynode(), _Val));
743 : else
744 0 : return (_Insert(true, _Next._Mynode(), _Val));
745 : }
746 : }
747 :
748 0 : return (insert(_Val).first); // try usual insert if all else fails
749 1 : }
750 :
751 : template<class _Iter>
752 : void insert(_Iter _First, _Iter _Last)
753 : { // insert [_First, _Last) one at a time
754 :
755 : #if _HAS_ITERATOR_DEBUGGING
756 : _DEBUG_RANGE(_First, _Last);
757 : #endif /* _HAS_ITERATOR_DEBUGGING */
758 :
759 : for (; _First != _Last; ++_First)
760 : insert(*_First);
761 : }
762 :
763 : iterator erase(const_iterator _Where)
764 0 : { // erase element at _Where
765 :
766 : #if _HAS_ITERATOR_DEBUGGING
767 0 : if (_Where._Mycont != this || _Isnil(_Where._Mynode()))
768 0 : _DEBUG_ERROR("map/set erase iterator outside range");
769 0 : _Nodeptr _Erasednode = _Where._Mynode(); // node to erase
770 0 : ++_Where; // save successor iterator for return
771 0 : _Orphan_ptr(*this, _Erasednode);
772 :
773 : #else /* _HAS_ITERATOR_DEBUGGING */
774 : if (_Isnil(_Where._Mynode()))
775 : _THROW(out_of_range, "invalid map/set<T> iterator");
776 : _Nodeptr _Erasednode = _Where._Mynode(); // node to erase
777 : ++_Where; // save successor iterator for return
778 : #endif /* _HAS_ITERATOR_DEBUGGING */
779 :
780 : _Nodeptr _Fixnode; // the node to recolor as needed
781 : _Nodeptr _Fixnodeparent; // parent of _Fixnode (which may be nil)
782 0 : _Nodeptr _Pnode = _Erasednode;
783 :
784 0 : if (_Isnil(_Left(_Pnode)))
785 0 : _Fixnode = _Right(_Pnode); // must stitch up right subtree
786 0 : else if (_Isnil(_Right(_Pnode)))
787 0 : _Fixnode = _Left(_Pnode); // must stitch up left subtree
788 0 : else
789 : { // two subtrees, must lift successor node to replace erased
790 0 : _Pnode = _Where._Mynode(); // _Pnode is successor node
791 0 : _Fixnode = _Right(_Pnode); // _Fixnode is its only subtree
792 : }
793 :
794 0 : if (_Pnode == _Erasednode)
795 : { // at most one subtree, relink it
796 0 : _Fixnodeparent = _Parent(_Erasednode);
797 0 : if (!_Isnil(_Fixnode))
798 0 : _Parent(_Fixnode) = _Fixnodeparent; // link up
799 :
800 0 : if (_Root() == _Erasednode)
801 0 : _Root() = _Fixnode; // link down from root
802 0 : else if (_Left(_Fixnodeparent) == _Erasednode)
803 0 : _Left(_Fixnodeparent) = _Fixnode; // link down to left
804 0 : else
805 0 : _Right(_Fixnodeparent) = _Fixnode; // link down to right
806 :
807 0 : if (_Lmost() == _Erasednode)
808 : _Lmost() = _Isnil(_Fixnode)
809 : ? _Fixnodeparent // smallest is parent of erased node
810 0 : : _Min(_Fixnode); // smallest in relinked subtree
811 :
812 0 : if (_Rmost() == _Erasednode)
813 : _Rmost() = _Isnil(_Fixnode)
814 : ? _Fixnodeparent // largest is parent of erased node
815 0 : : _Max(_Fixnode); // largest in relinked subtree
816 : }
817 0 : else
818 : { // erased has two subtrees, _Pnode is successor to erased
819 0 : _Parent(_Left(_Erasednode)) = _Pnode; // link left up
820 0 : _Left(_Pnode) = _Left(_Erasednode); // link successor down
821 :
822 0 : if (_Pnode == _Right(_Erasednode))
823 0 : _Fixnodeparent = _Pnode; // successor is next to erased
824 0 : else
825 : { // successor further down, link in place of erased
826 0 : _Fixnodeparent = _Parent(_Pnode); // parent is successor's
827 0 : if (!_Isnil(_Fixnode))
828 0 : _Parent(_Fixnode) = _Fixnodeparent; // link fix up
829 0 : _Left(_Fixnodeparent) = _Fixnode; // link fix down
830 0 : _Right(_Pnode) = _Right(_Erasednode); // link successor down
831 0 : _Parent(_Right(_Erasednode)) = _Pnode; // link right up
832 : }
833 :
834 0 : if (_Root() == _Erasednode)
835 0 : _Root() = _Pnode; // link down from root
836 0 : else if (_Left(_Parent(_Erasednode)) == _Erasednode)
837 0 : _Left(_Parent(_Erasednode)) = _Pnode; // link down to left
838 0 : else
839 0 : _Right(_Parent(_Erasednode)) = _Pnode; // link down to right
840 :
841 0 : _Parent(_Pnode) = _Parent(_Erasednode); // link successor up
842 0 : _STD swap(_Color(_Pnode), _Color(_Erasednode)); // recolor it
843 : }
844 :
845 0 : if (_Color(_Erasednode) == _Black)
846 : { // erasing black link, must recolor/rebalance tree
847 : for (; _Fixnode != _Root() && _Color(_Fixnode) == _Black;
848 0 : _Fixnodeparent = _Parent(_Fixnode))
849 0 : if (_Fixnode == _Left(_Fixnodeparent))
850 : { // fixup left subtree
851 0 : _Pnode = _Right(_Fixnodeparent);
852 0 : if (_Color(_Pnode) == _Red)
853 : { // rotate red up from right subtree
854 0 : _Color(_Pnode) = _Black;
855 0 : _Color(_Fixnodeparent) = _Red;
856 0 : _Lrotate(_Fixnodeparent);
857 0 : _Pnode = _Right(_Fixnodeparent);
858 : }
859 :
860 0 : if (_Isnil(_Pnode))
861 0 : _Fixnode = _Fixnodeparent; // shouldn't happen
862 0 : else if (_Color(_Left(_Pnode)) == _Black
863 0 : && _Color(_Right(_Pnode)) == _Black)
864 : { // redden right subtree with black children
865 0 : _Color(_Pnode) = _Red;
866 0 : _Fixnode = _Fixnodeparent;
867 : }
868 0 : else
869 : { // must rearrange right subtree
870 0 : if (_Color(_Right(_Pnode)) == _Black)
871 : { // rotate red up from left sub-subtree
872 0 : _Color(_Left(_Pnode)) = _Black;
873 0 : _Color(_Pnode) = _Red;
874 0 : _Rrotate(_Pnode);
875 0 : _Pnode = _Right(_Fixnodeparent);
876 : }
877 :
878 0 : _Color(_Pnode) = _Color(_Fixnodeparent);
879 0 : _Color(_Fixnodeparent) = _Black;
880 0 : _Color(_Right(_Pnode)) = _Black;
881 0 : _Lrotate(_Fixnodeparent);
882 0 : break; // tree now recolored/rebalanced
883 : }
884 : }
885 0 : else
886 : { // fixup right subtree
887 0 : _Pnode = _Left(_Fixnodeparent);
888 0 : if (_Color(_Pnode) == _Red)
889 : { // rotate red up from left subtree
890 0 : _Color(_Pnode) = _Black;
891 0 : _Color(_Fixnodeparent) = _Red;
892 0 : _Rrotate(_Fixnodeparent);
893 0 : _Pnode = _Left(_Fixnodeparent);
894 : }
895 0 : if (_Isnil(_Pnode))
896 0 : _Fixnode = _Fixnodeparent; // shouldn't happen
897 0 : else if (_Color(_Right(_Pnode)) == _Black
898 0 : && _Color(_Left(_Pnode)) == _Black)
899 : { // redden left subtree with black children
900 0 : _Color(_Pnode) = _Red;
901 0 : _Fixnode = _Fixnodeparent;
902 : }
903 0 : else
904 : { // must rearrange left subtree
905 0 : if (_Color(_Left(_Pnode)) == _Black)
906 : { // rotate red up from right sub-subtree
907 0 : _Color(_Right(_Pnode)) = _Black;
908 0 : _Color(_Pnode) = _Red;
909 0 : _Lrotate(_Pnode);
910 0 : _Pnode = _Left(_Fixnodeparent);
911 : }
912 :
913 0 : _Color(_Pnode) = _Color(_Fixnodeparent);
914 0 : _Color(_Fixnodeparent) = _Black;
915 0 : _Color(_Left(_Pnode)) = _Black;
916 0 : _Rrotate(_Fixnodeparent);
917 0 : break; // tree now recolored/rebalanced
918 : }
919 0 : }
920 :
921 0 : _Color(_Fixnode) = _Black; // ensure stopping node is black
922 : }
923 :
924 0 : this->_Alnod.destroy(_Erasednode); // destroy, free erased node
925 0 : this->_Alnod.deallocate(_Erasednode, 1);
926 :
927 0 : if (0 < _Mysize)
928 0 : --_Mysize;
929 :
930 0 : return (_Make_iter(_Where)); // return successor iterator
931 0 : }
932 :
933 : iterator erase(const_iterator _First, const_iterator _Last)
934 1 : { // erase [_First, _Last)
935 1 : if (_First == begin() && _Last == end())
936 : { // erase all
937 1 : clear();
938 1 : return (begin());
939 : }
940 : else
941 : { // partial erase, one at a time
942 0 : while (_First != _Last)
943 0 : erase(_First++);
944 0 : return (_Make_iter(_First));
945 : }
946 1 : }
947 :
948 : size_type erase(const key_type& _Keyval)
949 : { // erase and count all that match _Keyval
950 : _Pairii _Where = equal_range(_Keyval);
951 : size_type _Num = 0;
952 : _Distance(_Where.first, _Where.second, _Num);
953 : erase(_Where.first, _Where.second);
954 : return (_Num);
955 : }
956 :
957 : void erase(const key_type *_First, const key_type *_Last)
958 : { // erase all that match array of keys [_First, _Last)
959 : _DEBUG_RANGE(_First, _Last);
960 : while (_First != _Last)
961 : erase(*_First++);
962 : }
963 :
964 : void clear()
965 1 : { // erase all
966 :
967 : #if _HAS_ITERATOR_DEBUGGING
968 1 : this->_Orphan_ptr(*this, 0);
969 : #endif /* _HAS_ITERATOR_DEBUGGING */
970 :
971 1 : _Erase(_Root());
972 1 : _Root() = _Myhead, _Mysize = 0;
973 1 : _Lmost() = _Myhead, _Rmost() = _Myhead;
974 1 : }
975 :
976 : iterator find(const key_type& _Keyval)
977 1 : { // find an element in mutable sequence that matches _Keyval
978 1 : iterator _Where = lower_bound(_Keyval);
979 : return (_Where == end()
980 : || _DEBUG_LT_PRED(this->comp,
981 : _Keyval, _Key(_Where._Mynode()))
982 1 : ? end() : _Where);
983 1 : }
984 :
985 : const_iterator find(const key_type& _Keyval) const
986 : { // find an element in nonmutable sequence that matches _Keyval
987 : const_iterator _Where = lower_bound(_Keyval);
988 : return (_Where == end()
989 : || _DEBUG_LT_PRED(this->comp,
990 : _Keyval, _Key(_Where._Mynode()))
991 : ? end() : _Where);
992 : }
993 :
994 : size_type count(const key_type& _Keyval) const
995 1 : { // count all elements that match _Keyval
996 1 : _Paircc _Ans = equal_range(_Keyval);
997 1 : size_type _Num = 0;
998 1 : _Distance(_Ans.first, _Ans.second, _Num);
999 1 : return (_Num);
1000 1 : }
1001 :
1002 : iterator lower_bound(const key_type& _Keyval)
1003 1 : { // find leftmost node not less than _Keyval in mutable tree
1004 1 : return (_TREE_ITERATOR(_Lbound(_Keyval)));
1005 1 : }
1006 :
1007 : const_iterator lower_bound(const key_type& _Keyval) const
1008 : { // find leftmost node not less than _Keyval in nonmutable tree
1009 : return (_TREE_CONST_ITERATOR(_Lbound(_Keyval)));
1010 : }
1011 :
1012 : iterator upper_bound(const key_type& _Keyval)
1013 : { // find leftmost node greater than _Keyval in mutable tree
1014 : return (_TREE_ITERATOR(_Ubound(_Keyval)));
1015 : }
1016 :
1017 : const_iterator upper_bound(const key_type& _Keyval) const
1018 : { // find leftmost node greater than _Keyval in nonmutable tree
1019 : return (_TREE_CONST_ITERATOR(_Ubound(_Keyval)));
1020 : }
1021 :
1022 : _Pairii equal_range(const key_type& _Keyval)
1023 : { // find range equivalent to _Keyval in mutable tree
1024 : return (_Eqrange(_Keyval));
1025 : }
1026 :
1027 : _Paircc equal_range(const key_type& _Keyval) const
1028 1 : { // find range equivalent to _Keyval in nonmutable tree
1029 1 : return (_Eqrange(_Keyval));
1030 1 : }
1031 :
1032 : void swap(_Myt& _Right)
1033 : { // exchange contents with _Right
1034 : if (this == &_Right)
1035 : ; // same object, do nothing
1036 : else if (get_allocator() == _Right.get_allocator())
1037 : { // same allocator, swap control information
1038 :
1039 : #if _HAS_ITERATOR_DEBUGGING
1040 : this->_Swap_all(_Right);
1041 : #endif /* _HAS_ITERATOR_DEBUGGING */
1042 :
1043 : this->_Swap_aux(_Right);
1044 :
1045 : _STD _Swap_adl(this->comp, _Right.comp);
1046 : _STD swap(_Myhead, _Right._Myhead);
1047 : _STD swap(_Mysize, _Right._Mysize);
1048 : }
1049 : else
1050 : { // different allocator, do multiple assigns
1051 : this->_Swap_aux(_Right);
1052 :
1053 : _Myt _Tmp = *this;
1054 :
1055 : *this = _Right;
1056 : _Right = _Tmp;
1057 : }
1058 : }
1059 :
1060 : protected:
1061 : void _Copy(const _Myt& _Right)
1062 : { // copy entire tree from _Right
1063 : _Root() = _Copy(_Right._Root(), _Myhead);
1064 : _Mysize = _Right.size();
1065 : if (!_Isnil(_Root()))
1066 : { // nonempty tree, look for new smallest and largest
1067 : _Lmost() = _Min(_Root());
1068 : _Rmost() = _Max(_Root());
1069 : }
1070 : else
1071 : _Lmost() = _Myhead, _Rmost() = _Myhead; // empty tree
1072 : }
1073 :
1074 : _Nodeptr _Copy(_Nodeptr _Rootnode, _Nodeptr _Wherenode)
1075 : { // copy entire subtree, recursively
1076 : _Nodeptr _Newroot = _Myhead; // point at nil node
1077 :
1078 : if (!_Isnil(_Rootnode))
1079 : { // copy a node, then any subtrees
1080 : _Nodeptr _Pnode = _Buynode(_Myhead, _Wherenode, _Myhead,
1081 : _Myval(_Rootnode), _Color(_Rootnode));
1082 : if (_Isnil(_Newroot))
1083 : _Newroot = _Pnode; // memorize new root
1084 :
1085 : _TRY_BEGIN
1086 : _Left(_Pnode) = _Copy(_Left(_Rootnode), _Pnode);
1087 : _Right(_Pnode) = _Copy(_Right(_Rootnode), _Pnode);
1088 : _CATCH_ALL
1089 : _Erase(_Newroot); // subtree copy failed, bail out
1090 : _RERAISE;
1091 : _CATCH_END
1092 : }
1093 :
1094 : return (_Newroot); // return newly constructed tree
1095 : }
1096 :
1097 : _Paircc _Eqrange(const key_type& _Keyval) const
1098 1 : { // find leftmost node not less than _Keyval
1099 1 : _Nodeptr _Pnode = _Root();
1100 1 : _Nodeptr _Lonode = _Myhead; // end() if search fails
1101 1 : _Nodeptr _Hinode = _Myhead; // end() if search fails
1102 :
1103 1 : while (!_Isnil(_Pnode))
1104 1 : if (_DEBUG_LT_PRED(this->comp, _Key(_Pnode), _Keyval))
1105 1 : _Pnode = _Right(_Pnode); // descend right subtree
1106 1 : else
1107 : { // _Pnode not less than _Keyval, remember it
1108 : if (_Isnil(_Hinode)
1109 1 : && _DEBUG_LT_PRED(this->comp, _Keyval, _Key(_Pnode)))
1110 1 : _Hinode = _Pnode; // _Pnode greater, remember it
1111 1 : _Lonode = _Pnode;
1112 1 : _Pnode = _Left(_Pnode); // descend left subtree
1113 1 : }
1114 :
1115 : _Pnode = _Isnil(_Hinode) ? _Root()
1116 1 : : _Left(_Hinode); // continue scan for upper bound
1117 1 : while (!_Isnil(_Pnode))
1118 1 : if (_DEBUG_LT_PRED(this->comp, _Keyval, _Key(_Pnode)))
1119 : { // _Pnode greater than _Keyval, remember it
1120 0 : _Hinode = _Pnode;
1121 0 : _Pnode = _Left(_Pnode); // descend left subtree
1122 : }
1123 0 : else
1124 1 : _Pnode = _Right(_Pnode); // descend right subtree
1125 :
1126 1 : const_iterator _First = _TREE_CONST_ITERATOR(_Lonode);
1127 1 : const_iterator _Last = _TREE_CONST_ITERATOR(_Hinode);
1128 1 : return (_Paircc(_First, _Last));
1129 1 : }
1130 :
1131 : _Pairii _Eqrange(const key_type& _Keyval)
1132 : { // find leftmost node not less than _Keyval
1133 : _Nodeptr _Pnode = _Root();
1134 : _Nodeptr _Lonode = _Myhead; // end() if search fails
1135 : _Nodeptr _Hinode = _Myhead; // end() if search fails
1136 :
1137 : while (!_Isnil(_Pnode))
1138 : if (_DEBUG_LT_PRED(this->comp, _Key(_Pnode), _Keyval))
1139 : _Pnode = _Right(_Pnode); // descend right subtree
1140 : else
1141 : { // _Pnode not less than _Keyval, remember it
1142 : if (_Isnil(_Hinode)
1143 : && _DEBUG_LT_PRED(this->comp, _Keyval, _Key(_Pnode)))
1144 : _Hinode = _Pnode; // _Pnode greater, remember it
1145 : _Lonode = _Pnode;
1146 : _Pnode = _Left(_Pnode); // descend left subtree
1147 : }
1148 :
1149 : _Pnode = _Isnil(_Hinode) ? _Root()
1150 : : _Left(_Hinode); // continue scan for upper bound
1151 : while (!_Isnil(_Pnode))
1152 : if (_DEBUG_LT_PRED(this->comp, _Keyval, _Key(_Pnode)))
1153 : { // _Pnode greater than _Keyval, remember it
1154 : _Hinode = _Pnode;
1155 : _Pnode = _Left(_Pnode); // descend left subtree
1156 : }
1157 : else
1158 : _Pnode = _Right(_Pnode); // descend right subtree
1159 :
1160 : iterator _First = _TREE_ITERATOR(_Lonode);
1161 : iterator _Last = _TREE_ITERATOR(_Hinode);
1162 : return (_Pairii(_First, _Last));
1163 : }
1164 :
1165 : void _Erase(_Nodeptr _Rootnode)
1166 1 : { // free entire subtree, recursively
1167 1 : for (_Nodeptr _Pnode = _Rootnode; !_Isnil(_Pnode); _Rootnode = _Pnode)
1168 : { // free subtrees, then node
1169 1 : _Erase(_Right(_Pnode));
1170 1 : _Pnode = _Left(_Pnode);
1171 1 : this->_Alnod.destroy(_Rootnode); // destroy, free erased node
1172 1 : this->_Alnod.deallocate(_Rootnode, 1);
1173 1 : }
1174 1 : }
1175 :
1176 : void _Init()
1177 2 : { // create head/nil node and make tree empty
1178 2 : _Myhead = _Buynode();
1179 2 : _Isnil(_Myhead) = true;
1180 2 : _Root() = _Myhead;
1181 2 : _Lmost() = _Myhead, _Rmost() = _Myhead;
1182 2 : _Mysize = 0;
1183 2 : }
1184 :
1185 : iterator _Insert(bool _Addleft, _Nodeptr _Wherenode,
1186 : const value_type& _Val)
1187 2 : { // add node with value next to _Wherenode, to left if _Addnode
1188 2 : if (max_size() - 1 <= _Mysize)
1189 0 : _THROW(length_error, "map/set<T> too long");
1190 : _Nodeptr _Newnode = _Buynode(_Myhead, _Wherenode, _Myhead,
1191 2 : _Val, _Red);
1192 :
1193 2 : ++_Mysize;
1194 2 : if (_Wherenode == _Myhead)
1195 : { // first node in tree, just set head values
1196 2 : _Root() = _Newnode;
1197 2 : _Lmost() = _Newnode, _Rmost() = _Newnode;
1198 : }
1199 1 : else if (_Addleft)
1200 : { // add to left of _Wherenode
1201 0 : _Left(_Wherenode) = _Newnode;
1202 0 : if (_Wherenode == _Lmost())
1203 0 : _Lmost() = _Newnode;
1204 : }
1205 0 : else
1206 : { // add to right of _Wherenode
1207 1 : _Right(_Wherenode) = _Newnode;
1208 1 : if (_Wherenode == _Rmost())
1209 1 : _Rmost() = _Newnode;
1210 : }
1211 :
1212 2 : for (_Nodeptr _Pnode = _Newnode; _Color(_Parent(_Pnode)) == _Red; )
1213 1 : if (_Parent(_Pnode) == _Left(_Parent(_Parent(_Pnode))))
1214 : { // fixup red-red in left subtree
1215 0 : _Wherenode = _Right(_Parent(_Parent(_Pnode)));
1216 0 : if (_Color(_Wherenode) == _Red)
1217 : { // parent has two red children, blacken both
1218 0 : _Color(_Parent(_Pnode)) = _Black;
1219 0 : _Color(_Wherenode) = _Black;
1220 0 : _Color(_Parent(_Parent(_Pnode))) = _Red;
1221 0 : _Pnode = _Parent(_Parent(_Pnode));
1222 : }
1223 0 : else
1224 : { // parent has red and black children
1225 0 : if (_Pnode == _Right(_Parent(_Pnode)))
1226 : { // rotate right child to left
1227 0 : _Pnode = _Parent(_Pnode);
1228 0 : _Lrotate(_Pnode);
1229 : }
1230 0 : _Color(_Parent(_Pnode)) = _Black; // propagate red up
1231 0 : _Color(_Parent(_Parent(_Pnode))) = _Red;
1232 0 : _Rrotate(_Parent(_Parent(_Pnode)));
1233 : }
1234 : }
1235 0 : else
1236 : { // fixup red-red in right subtree
1237 1 : _Wherenode = _Left(_Parent(_Parent(_Pnode)));
1238 1 : if (_Color(_Wherenode) == _Red)
1239 : { // parent has two red children, blacken both
1240 1 : _Color(_Parent(_Pnode)) = _Black;
1241 1 : _Color(_Wherenode) = _Black;
1242 1 : _Color(_Parent(_Parent(_Pnode))) = _Red;
1243 1 : _Pnode = _Parent(_Parent(_Pnode));
1244 : }
1245 1 : else
1246 : { // parent has red and black children
1247 1 : if (_Pnode == _Left(_Parent(_Pnode)))
1248 : { // rotate left child to right
1249 0 : _Pnode = _Parent(_Pnode);
1250 0 : _Rrotate(_Pnode);
1251 : }
1252 1 : _Color(_Parent(_Pnode)) = _Black; // propagate red up
1253 1 : _Color(_Parent(_Parent(_Pnode))) = _Red;
1254 1 : _Lrotate(_Parent(_Parent(_Pnode)));
1255 : }
1256 1 : }
1257 :
1258 2 : _Color(_Root()) = _Black; // root is always black
1259 2 : return (_TREE_ITERATOR(_Newnode));
1260 2 : }
1261 :
1262 : _Nodeptr _Lbound(const key_type& _Keyval) const
1263 1 : { // find leftmost node not less than _Keyval
1264 1 : _Nodeptr _Pnode = _Root();
1265 1 : _Nodeptr _Wherenode = _Myhead; // end() if search fails
1266 :
1267 1 : while (!_Isnil(_Pnode))
1268 1 : if (_DEBUG_LT_PRED(this->comp, _Key(_Pnode), _Keyval))
1269 1 : _Pnode = _Right(_Pnode); // descend right subtree
1270 1 : else
1271 : { // _Pnode not less than _Keyval, remember it
1272 1 : _Wherenode = _Pnode;
1273 1 : _Pnode = _Left(_Pnode); // descend left subtree
1274 1 : }
1275 :
1276 1 : return (_Wherenode); // return best remembered candidate
1277 1 : }
1278 :
1279 : _Nodeptr& _Lmost() const
1280 2 : { // return leftmost node in nonmutable tree
1281 2 : return (_Left(_Myhead));
1282 2 : }
1283 :
1284 : void _Lrotate(_Nodeptr _Wherenode)
1285 1 : { // promote right node to root of subtree
1286 1 : _Nodeptr _Pnode = _Right(_Wherenode);
1287 1 : _Right(_Wherenode) = _Left(_Pnode);
1288 :
1289 1 : if (!_Isnil(_Left(_Pnode)))
1290 0 : _Parent(_Left(_Pnode)) = _Wherenode;
1291 1 : _Parent(_Pnode) = _Parent(_Wherenode);
1292 :
1293 1 : if (_Wherenode == _Root())
1294 1 : _Root() = _Pnode;
1295 0 : else if (_Wherenode == _Left(_Parent(_Wherenode)))
1296 0 : _Left(_Parent(_Wherenode)) = _Pnode;
1297 0 : else
1298 0 : _Right(_Parent(_Wherenode)) = _Pnode;
1299 :
1300 1 : _Left(_Pnode) = _Wherenode;
1301 1 : _Parent(_Wherenode) = _Pnode;
1302 1 : }
1303 :
1304 : static _Nodeptr _Max(_Nodeptr _Pnode)
1305 0 : { // return rightmost node in subtree at _Pnode
1306 0 : while (!_Isnil(_Right(_Pnode)))
1307 0 : _Pnode = _Right(_Pnode);
1308 0 : return (_Pnode);
1309 0 : }
1310 :
1311 : static _Nodeptr _Min(_Nodeptr _Pnode)
1312 0 : { // return leftmost node in subtree at _Pnode
1313 0 : while (!_Isnil(_Left(_Pnode)))
1314 0 : _Pnode = _Left(_Pnode);
1315 0 : return (_Pnode);
1316 0 : }
1317 :
1318 : _Nodeptr& _Rmost() const
1319 2 : { // return rightmost node in nonmutable tree
1320 2 : return (_Right(_Myhead));
1321 2 : }
1322 :
1323 : _Nodeptr& _Root() const
1324 2 : { // return root of nonmutable tree
1325 2 : return (_Parent(_Myhead));
1326 2 : }
1327 :
1328 : void _Rrotate(_Nodeptr _Wherenode)
1329 0 : { // promote left node to root of subtree
1330 0 : _Nodeptr _Pnode = _Left(_Wherenode);
1331 0 : _Left(_Wherenode) = _Right(_Pnode);
1332 :
1333 0 : if (!_Isnil(_Right(_Pnode)))
1334 0 : _Parent(_Right(_Pnode)) = _Wherenode;
1335 0 : _Parent(_Pnode) = _Parent(_Wherenode);
1336 :
1337 0 : if (_Wherenode == _Root())
1338 0 : _Root() = _Pnode;
1339 0 : else if (_Wherenode == _Right(_Parent(_Wherenode)))
1340 0 : _Right(_Parent(_Wherenode)) = _Pnode;
1341 0 : else
1342 0 : _Left(_Parent(_Wherenode)) = _Pnode;
1343 :
1344 0 : _Right(_Pnode) = _Wherenode;
1345 0 : _Parent(_Wherenode) = _Pnode;
1346 0 : }
1347 :
1348 : _Nodeptr _Ubound(const key_type& _Keyval) const
1349 : { // find leftmost node greater than _Keyval
1350 : _Nodeptr _Pnode = _Root();
1351 : _Nodeptr _Wherenode = _Myhead; // end() if search fails
1352 :
1353 : while (!_Isnil(_Pnode))
1354 : if (_DEBUG_LT_PRED(this->comp, _Keyval, _Key(_Pnode)))
1355 : { // _Pnode greater than _Keyval, remember it
1356 : _Wherenode = _Pnode;
1357 : _Pnode = _Left(_Pnode); // descend left subtree
1358 : }
1359 : else
1360 : _Pnode = _Right(_Pnode); // descend right subtree
1361 :
1362 : return (_Wherenode); // return best remembered candidate
1363 : }
1364 :
1365 : #if _HAS_ITERATOR_DEBUGGING
1366 : void _Orphan_ptr(_Myt& _Cont, _Nodeptr _Ptr) const
1367 1 : { // orphan iterators with specified node pointers
1368 1 : _Lockit _Lock(_LOCK_DEBUG);
1369 1 : const_iterator **_Pnext = (const_iterator **)&_Cont._Myfirstiter;
1370 1 : while (*_Pnext != 0)
1371 : if ((*_Pnext)->_Ptr == _Myhead
1372 1 : || _Ptr != 0 && (*_Pnext)->_Ptr != _Ptr)
1373 1 : _Pnext = (const_iterator **)&(*_Pnext)->_Mynextiter;
1374 1 : else
1375 : { // orphan the iterator
1376 1 : (*_Pnext)->_Mycont = 0;
1377 1 : *_Pnext = (const_iterator *)(*_Pnext)->_Mynextiter;
1378 1 : }
1379 1 : }
1380 : #endif /* _HAS_ITERATOR_DEBUGGING */
1381 :
1382 : _Nodeptr _Buynode()
1383 2 : { // allocate a head/nil node
1384 2 : _Nodeptr _Wherenode = this->_Alnod.allocate(1);
1385 2 : int _Linkcnt = 0;
1386 :
1387 2 : _TRY_BEGIN
1388 2 : this->_Alptr.construct(&_Left(_Wherenode), 0);
1389 2 : ++_Linkcnt;
1390 2 : this->_Alptr.construct(&_Parent(_Wherenode), 0);
1391 2 : ++_Linkcnt;
1392 2 : this->_Alptr.construct(&_Right(_Wherenode), 0);
1393 : _CATCH_ALL
1394 0 : if (1 < _Linkcnt)
1395 0 : this->_Alptr.destroy(&_Parent(_Wherenode));
1396 0 : if (0 < _Linkcnt)
1397 0 : this->_Alptr.destroy(&_Left(_Wherenode));
1398 0 : this->_Alnod.deallocate(_Wherenode, 1);
1399 0 : _RERAISE;
1400 0 : _CATCH_END
1401 2 : _Color(_Wherenode) = _Black;
1402 2 : _Isnil(_Wherenode) = false;
1403 2 : return (_Wherenode);
1404 2 : }
1405 :
1406 : _Nodeptr _Buynode(_Nodeptr _Larg, _Nodeptr _Parg,
1407 : _Nodeptr _Rarg, const value_type& _Val, char _Carg)
1408 2 : { // allocate a node with pointers, value, and color
1409 2 : _Nodeptr _Wherenode = this->_Alnod.allocate(1);
1410 2 : _TRY_BEGIN
1411 2 : new (_Wherenode) _Node(_Larg, _Parg, _Rarg, _Val, _Carg);
1412 : _CATCH_ALL
1413 0 : this->_Alnod.deallocate(_Wherenode, 1);
1414 0 : _RERAISE;
1415 0 : _CATCH_END
1416 2 : return (_Wherenode);
1417 2 : }
1418 :
1419 : void _Tidy()
1420 1 : { // free all storage
1421 1 : erase(begin(), end());
1422 1 : this->_Alptr.destroy(&_Left(_Myhead));
1423 1 : this->_Alptr.destroy(&_Parent(_Myhead));
1424 1 : this->_Alptr.destroy(&_Right(_Myhead));
1425 1 : this->_Alnod.deallocate(_Myhead, 1);
1426 1 : _Myhead = 0, _Mysize = 0;
1427 1 : }
1428 :
1429 : static void _Xran()
1430 : { // report an out_of_range error
1431 : _THROW(out_of_range, "invalid map/set<T> iterator");
1432 : }
1433 :
1434 : static void _Xinvarg()
1435 : { // report an invalid_argument error
1436 : _THROW(invalid_argument, "invalid map/set<T> argument");
1437 : }
1438 :
1439 : _Nodeptr _Myhead; // pointer to head node
1440 : size_type _Mysize; // number of elements
1441 : };
1442 :
1443 : // _Tree implements a performant swap
1444 : template <class _Traits>
1445 : class _Move_operation_category<_Tree<_Traits> >
1446 : {
1447 : public:
1448 : typedef _Swap_move_tag _Move_cat;
1449 : };
1450 :
1451 : // _Tree TEMPLATE OPERATORS
1452 : template<class _Traits> inline
1453 : bool operator==(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right)
1454 : { // test for _Tree equality
1455 : return (_Left.size() == _Right.size()
1456 : && equal(_Left.begin(), _Left.end(), _Right.begin()));
1457 : }
1458 :
1459 : template<class _Traits> inline
1460 : bool operator!=(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right)
1461 : { // test for _Tree inequality
1462 : return (!(_Left == _Right));
1463 : }
1464 :
1465 : template<class _Traits> inline
1466 : bool operator<(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right)
1467 : { // test if _Less < _Right for _Trees
1468 : return (lexicographical_compare(_Left.begin(), _Left.end(),
1469 : _Right.begin(), _Right.end()));
1470 : }
1471 :
1472 : template<class _Traits> inline
1473 : bool operator>(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right)
1474 : { // test if _Less > _Right for _Trees
1475 : return (_Right < _Left);
1476 : }
1477 :
1478 : template<class _Traits> inline
1479 : bool operator<=(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right)
1480 : { // test if _Less <= _Right for _Trees
1481 : return (!(_Right < _Left));
1482 : }
1483 :
1484 : template<class _Traits> inline
1485 : bool operator>=(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right)
1486 : { // test if _Less >= _Right for _Trees
1487 : return (!(_Left < _Right));
1488 : }
1489 : _STD_END
1490 :
1491 : #ifdef _MSC_VER
1492 : #pragma warning(default:4127)
1493 : #pragma warning(pop)
1494 : #pragma pack(pop)
1495 : #endif /* _MSC_VER */
1496 :
1497 : #endif /* RC_INVOKED */
1498 : #endif /* _XTREE_ */
1499 :
1500 : /*
1501 : * This file is derived from software bearing the following
1502 : * restrictions:
1503 : *
1504 : * Copyright (c) 1994
1505 : * Hewlett-Packard Company
1506 : *
1507 : * Permission to use, copy, modify, distribute and sell this
1508 : * software and its documentation for any purpose is hereby
1509 : * granted without fee, provided that the above copyright notice
1510 : * appear in all copies and that both that copyright notice and
1511 : * this permission notice appear in supporting documentation.
1512 : * Hewlett-Packard Company makes no representations about the
1513 : * suitability of this software for any purpose. It is provided
1514 : * "as is" without express or implied warranty.
1515 : */
1516 :
1517 : /*
1518 : * Copyright (c) 1992-2007 by P.J. Plauger. ALL RIGHTS RESERVED.
1519 : * Consult your license regarding permissions and restrictions.
1520 : V5.03:0009 */
1521 :
1522 :
|
