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		{    // construct a node with value
39		}
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		{    // construct traits from _Parg and allocator from _Al
53		}
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		{    // construct base, and allocator from _Al
79		}
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		{    // construct base, and allocator from _Al
98		}
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		{    // return reference to color in node
152		return ((_Charref)(*_Pnode)._Color);
153		}
154
155		static _Charref _Isnil(_Nodeptr _Pnode)
156		{    // return reference to nil flag in node
157		return ((_Charref)(*_Pnode)._Isnil);
158		}
159
160		static _Keyref _Key(_Nodeptr _Pnode)
161		{    // return reference to key in node
162		return (_Mybase::_Kfn(_Myval(_Pnode)));
163		}
164
165		static _Nodepref _Left(_Nodeptr _Pnode)
166		{    // return reference to left pointer in node
167		return ((_Nodepref)(*_Pnode)._Left);
168		}
169
170		static _Nodepref _Parent(_Nodeptr _Pnode)
171		{    // return reference to parent pointer in node
172		return ((_Nodepref)(*_Pnode)._Parent);
173		}
174
175		static _Nodepref _Right(_Nodeptr _Pnode)
176		{    // return reference to right pointer in node
177		return ((_Nodepref)(*_Pnode)._Right);
178		}
179
180		static _Vref _Myval(_Nodeptr _Pnode)
181		{    // return reference to value in node
182		return ((_Vref)(*_Pnode)._Myval);
183		}
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		{    // construct with null node pointer
218		}
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		{    // construct with node pointer _Pnode
226		this->_Adopt(_Plist);
227		}
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		{    // return designated value
250
251		#if _HAS_ITERATOR_DEBUGGING
252		if (this->_Mycont == 0
253		|| _Ptr == 0
254		|| _Ptr == ((_Myt *)this->_Mycont)->_Myhead)
255		{
256		_DEBUG_ERROR("map/set iterator not dereferencable");
257		_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		return (_Myval(_Ptr));
265		}
266
267		_Ctptr operator->() const
268		{    // return pointer to class object
269		return (&**this);
270		}
271
272		const_iterator& operator++()
273		{    // preincrement
274		_Inc();
275		return (*this);
276		}
277
278		const_iterator operator++(int)
279		{    // postincrement
280		const_iterator _Tmp = *this;
281		++*this;
282		return (_Tmp);
283		}
284
285		const_iterator& operator--()
286		{    // predecrement
287		_Dec();
288		return (*this);
289		}
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		{    // test for iterator equality
300
301		#if _HAS_ITERATOR_DEBUGGING
302		if (this->_Mycont == 0 || this->_Mycont != _Right._Mycont)
303		{
304		_DEBUG_ERROR("map/set iterators incompatible");
305		_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		return (_Ptr == _Right._Ptr);
312		}
313
314		bool operator!=(const const_iterator& _Right) const
315		{    // test for iterator inequality
316		return (!(*this == _Right));
317		}
318
319		void _Dec()
320		{    // move to node with next smaller value
321
322		#if _HAS_ITERATOR_DEBUGGING
323		if (this->_Mycont == 0
324		|| _Ptr == 0)
325		{
326		_DEBUG_ERROR("map/set iterator not decrementable");
327		_SCL_SECURE_INVALID_ARGUMENT;
328		}
329		#else
330		_SCL_SECURE_VALIDATE(this->_Has_container());
331		#endif /* _HAS_ITERATOR_DEBUGGING */
332
333		if (_Isnil(_Ptr))
334		{
335		_Ptr = _Right(_Ptr);    // end() ==> rightmost
336		if (_Isnil(_Ptr))
337		#if _HAS_ITERATOR_DEBUGGING
338		{
339		_DEBUG_ERROR("map/set iterator not decrementable");
340		_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		}
350		else if (!_Isnil(_Left(_Ptr)))
351		_Ptr = _Max(_Left(_Ptr));    // ==> largest of left subtree
352		else
353		{    // climb looking for left subtree
354		_Nodeptr _Pnode;
355		while (!_Isnil(_Pnode = _Parent(_Ptr))
356		&& _Ptr == _Left(_Pnode))
357		_Ptr = _Pnode;    // ==> parent while left subtree
358		if (_Isnil(_Ptr))
359		#if _HAS_ITERATOR_DEBUGGING
360		{
361		_DEBUG_ERROR("map/set iterator not decrementable");
362		_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		else
372		_Ptr = _Pnode;    // ==> parent if not head
373		}
374		}
375
376		void _Inc()
377		{    // move to node with next larger value
378
379		#if _HAS_ITERATOR_DEBUGGING
380		if (this->_Mycont == 0
381		|| _Ptr == 0
382		|| _Isnil(_Ptr))
383		{
384		_DEBUG_ERROR("map/set iterator not incrementable");
385		_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		else if (!_Isnil(_Right(_Ptr)))
397		_Ptr = _Min(_Right(_Ptr));    // ==> smallest of right subtree
398		else
399		{    // climb looking for right subtree
400		_Nodeptr _Pnode;
401		while (!_Isnil(_Pnode = _Parent(_Ptr))
402		&& _Ptr == _Right(_Pnode))
403		_Ptr = _Pnode;    // ==> parent while right subtree
404		_Ptr = _Pnode;    // ==> parent (head if end())
405		}
406		}
407
408		_Nodeptr _Mynode() const
409		{    // return node pointer
410		return (_Ptr);
411		}
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		{    // construct with node pointer _Pnode
444		}
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		{    // return designated value
465		return ((reference)**(const_iterator *)this);
466		}
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		{    // predecrement
488		--(*(const_iterator *)this);
489		return (*this);
490		}
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		{    // construct empty tree
510		_Init();
511		}
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		{    // destroy tree
540		_Tidy();
541		}
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		{    // return iterator for beginning of mutable sequence
556		return (_TREE_ITERATOR(_Lmost()));
557		}
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		{    // return iterator for end of mutable sequence
566		return (_TREE_ITERATOR(_Myhead));
567		}
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		{    // make iterator from const_iterator
576		return (iterator(_TREE_ITERATOR(_Where._Ptr)));
577		}
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		{    // return length of sequence
601		return (_Mysize);
602		}
603
604		size_type max_size() const
605		{    // return maximum possible length of sequence
606		return (this->_Alval.max_size());
607		}
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		{    // try to insert node with value _Val
631		_Nodeptr _Trynode = _Root();
632		_Nodeptr _Wherenode = _Myhead;
633		bool _Addleft = true;    // add to left of head if tree empty
634		while (!_Isnil(_Trynode))
635		{    // look for leaf to insert before (_Addleft) or after
636		_Wherenode = _Trynode;
637		_Addleft = _DEBUG_LT_PRED(this->comp,
638		this->_Kfn(_Val), _Key(_Trynode));
639		_Trynode = _Addleft ? _Left(_Trynode) : _Right(_Trynode);
640		}
641
642		if (this->_Multi)
643		return (_Pairib(_Insert(_Addleft, _Wherenode, _Val), true));
644		else
645		{    // insert only if unique
646		iterator _Where = _TREE_ITERATOR(_Wherenode);
647		if (!_Addleft)
648		;    // need to test if insert after is okay
649		else if (_Where == begin())
650		return (_Pairib(_Insert(true, _Wherenode, _Val), true));
651		else
652		--_Where;    // need to test if insert before is okay
653
654		if (_DEBUG_LT_PRED(this->comp,
655		_Key(_Where._Mynode()), this->_Kfn(_Val)))
656		return (_Pairib(_Insert(_Addleft, _Wherenode, _Val), true));
657		else
658		return (_Pairib(_Where, false));
659		}
660		}
661
662		iterator insert(const_iterator _Where,
663		const value_type& _Val)
664		{    // try to insert node with value _Val using _Where as a hint
665
666		#if _HAS_ITERATOR_DEBUGGING
667		if (_Where._Mycont != this)
668		_DEBUG_ERROR("map/set insert iterator outside range");
669		#endif /* _HAS_ITERATOR_DEBUGGING */
670
671		const_iterator _Next;
672
673		if (size() == 0)
674		return (_Insert(true, _Myhead, _Val));    // insert into empty tree
675		else if (this->_Multi)
676		{    // insert even if duplicate
677		if (_Where == begin())
678		{    // insert at beginning if before first element
679		if (!_DEBUG_LT_PRED(this->comp,
680		_Key(_Where._Mynode()), this->_Kfn(_Val)))
681		return (_Insert(true, _Where._Mynode(), _Val));
682		}
683		else if (_Where == end())
684		{    // insert at end if after last element
685		if (!_DEBUG_LT_PRED(this->comp,
686		this->_Kfn(_Val), _Key(_Rmost())))
687		return (_Insert(false, _Rmost(), _Val));
688		}
689		else if (!_DEBUG_LT_PRED(this->comp,
690		_Key(_Where._Mynode()), this->_Kfn(_Val))
691		&& !_DEBUG_LT_PRED(this->comp,
692		this->_Kfn(_Val), _Key((--(_Next = _Where))._Mynode())))
693		{    // insert before _Where
694		if (_Isnil(_Right(_Next._Mynode())))
695		return (_Insert(false, _Next._Mynode(), _Val));
696		else
697		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		|| !_DEBUG_LT_PRED(this->comp,
703		_Key(_Next._Mynode()), this->_Kfn(_Val))))
704		{    // insert after _Where
705		if (_Isnil(_Right(_Where._Mynode())))
706		return (_Insert(false, _Where._Mynode(), _Val));
707		else
708		return (_Insert(true, _Next._Mynode(), _Val));
709		}
710		}
711		else
712		{    // insert only if unique
713		if (_Where == begin())
714		{    // insert at beginning if before first element
715		if (_DEBUG_LT_PRED(this->comp,
716		this->_Kfn(_Val), _Key(_Where._Mynode())))
717		return (_Insert(true, _Where._Mynode(), _Val));
718		}
719		else if (_Where == end())
720		{    // insert at end if after last element
721		if (_DEBUG_LT_PRED(this->comp,
722		_Key(_Rmost()), this->_Kfn(_Val)))
723		return (_Insert(false, _Rmost(), _Val));
724		}
725		else if (_DEBUG_LT_PRED(this->comp,
726		this->_Kfn(_Val), _Key(_Where._Mynode()))
727		&& _DEBUG_LT_PRED(this->comp,
728		_Key((--(_Next = _Where))._Mynode()), this->_Kfn(_Val)))
729		{    // insert before _Where
730		if (_Isnil(_Right(_Next._Mynode())))
731		return (_Insert(false, _Next._Mynode(), _Val));
732		else
733		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		|| _DEBUG_LT_PRED(this->comp,
739		this->_Kfn(_Val), _Key(_Next._Mynode()))))
740		{    // insert after _Where
741		if (_Isnil(_Right(_Where._Mynode())))
742		return (_Insert(false, _Where._Mynode(), _Val));
743		else
744		return (_Insert(true, _Next._Mynode(), _Val));
745		}
746		}
747
748		return (insert(_Val).first);    // try usual insert if all else fails
749		}
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		{    // erase element at _Where
765
766		#if _HAS_ITERATOR_DEBUGGING
767		if (_Where._Mycont != this || _Isnil(_Where._Mynode()))
768		_DEBUG_ERROR("map/set erase iterator outside range");
769		_Nodeptr _Erasednode = _Where._Mynode();    // node to erase
770		++_Where;    // save successor iterator for return
771		_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		_Nodeptr _Pnode = _Erasednode;
783
784		if (_Isnil(_Left(_Pnode)))
785		_Fixnode = _Right(_Pnode);    // must stitch up right subtree
786		else if (_Isnil(_Right(_Pnode)))
787		_Fixnode = _Left(_Pnode);    // must stitch up left subtree
788		else
789		{    // two subtrees, must lift successor node to replace erased
790		_Pnode = _Where._Mynode();    // _Pnode is successor node
791		_Fixnode = _Right(_Pnode);    // _Fixnode is its only subtree
792		}
793
794		if (_Pnode == _Erasednode)
795		{    // at most one subtree, relink it
796		_Fixnodeparent = _Parent(_Erasednode);
797		if (!_Isnil(_Fixnode))
798		_Parent(_Fixnode) = _Fixnodeparent;    // link up
799
800		if (_Root() == _Erasednode)
801		_Root() = _Fixnode;    // link down from root
802		else if (_Left(_Fixnodeparent) == _Erasednode)
803		_Left(_Fixnodeparent) = _Fixnode;    // link down to left
804		else
805		_Right(_Fixnodeparent) = _Fixnode;    // link down to right
806
807		if (_Lmost() == _Erasednode)
808		_Lmost() = _Isnil(_Fixnode)
809		? _Fixnodeparent    // smallest is parent of erased node
810		: _Min(_Fixnode);    // smallest in relinked subtree
811
812		if (_Rmost() == _Erasednode)
813		_Rmost() = _Isnil(_Fixnode)
814		? _Fixnodeparent    // largest is parent of erased node
815		: _Max(_Fixnode);    // largest in relinked subtree
816		}
817		else
818		{    // erased has two subtrees, _Pnode is successor to erased
819		_Parent(_Left(_Erasednode)) = _Pnode;    // link left up
820		_Left(_Pnode) = _Left(_Erasednode);    // link successor down
821
822		if (_Pnode == _Right(_Erasednode))
823		_Fixnodeparent = _Pnode;    // successor is next to erased
824		else
825		{    // successor further down, link in place of erased
826		_Fixnodeparent = _Parent(_Pnode);    // parent is successor's
827		if (!_Isnil(_Fixnode))
828		_Parent(_Fixnode) = _Fixnodeparent;    // link fix up
829		_Left(_Fixnodeparent) = _Fixnode;    // link fix down
830		_Right(_Pnode) = _Right(_Erasednode);    // link successor down
831		_Parent(_Right(_Erasednode)) = _Pnode;    // link right up
832		}
833
834		if (_Root() == _Erasednode)
835		_Root() = _Pnode;    // link down from root
836		else if (_Left(_Parent(_Erasednode)) == _Erasednode)
837		_Left(_Parent(_Erasednode)) = _Pnode;    // link down to left
838		else
839		_Right(_Parent(_Erasednode)) = _Pnode;    // link down to right
840
841		_Parent(_Pnode) = _Parent(_Erasednode);    // link successor up
842		_STD swap(_Color(_Pnode), _Color(_Erasednode));    // recolor it
843		}
844
845		if (_Color(_Erasednode) == _Black)
846		{    // erasing black link, must recolor/rebalance tree
847		for (; _Fixnode != _Root() && _Color(_Fixnode) == _Black;
848		_Fixnodeparent = _Parent(_Fixnode))
849		if (_Fixnode == _Left(_Fixnodeparent))
850		{    // fixup left subtree
851		_Pnode = _Right(_Fixnodeparent);
852		if (_Color(_Pnode) == _Red)
853		{    // rotate red up from right subtree
854		_Color(_Pnode) = _Black;
855		_Color(_Fixnodeparent) = _Red;
856		_Lrotate(_Fixnodeparent);
857		_Pnode = _Right(_Fixnodeparent);
858		}
859
860		if (_Isnil(_Pnode))
861		_Fixnode = _Fixnodeparent;    // shouldn't happen
862		else if (_Color(_Left(_Pnode)) == _Black
863		&& _Color(_Right(_Pnode)) == _Black)
864		{    // redden right subtree with black children
865		_Color(_Pnode) = _Red;
866		_Fixnode = _Fixnodeparent;
867		}
868		else
869		{    // must rearrange right subtree
870		if (_Color(_Right(_Pnode)) == _Black)
871		{    // rotate red up from left sub-subtree
872		_Color(_Left(_Pnode)) = _Black;
873		_Color(_Pnode) = _Red;
874		_Rrotate(_Pnode);
875		_Pnode = _Right(_Fixnodeparent);
876		}
877
878		_Color(_Pnode) = _Color(_Fixnodeparent);
879		_Color(_Fixnodeparent) = _Black;
880		_Color(_Right(_Pnode)) = _Black;
881		_Lrotate(_Fixnodeparent);
882		break;    // tree now recolored/rebalanced
883		}
884		}
885		else
886		{    // fixup right subtree
887		_Pnode = _Left(_Fixnodeparent);
888		if (_Color(_Pnode) == _Red)
889		{    // rotate red up from left subtree
890		_Color(_Pnode) = _Black;
891		_Color(_Fixnodeparent) = _Red;
892		_Rrotate(_Fixnodeparent);
893		_Pnode = _Left(_Fixnodeparent);
894		}
895		if (_Isnil(_Pnode))
896		_Fixnode = _Fixnodeparent;    // shouldn't happen
897		else if (_Color(_Right(_Pnode)) == _Black
898		&& _Color(_Left(_Pnode)) == _Black)
899		{    // redden left subtree with black children
900		_Color(_Pnode) = _Red;
901		_Fixnode = _Fixnodeparent;
902		}
903		else
904		{    // must rearrange left subtree
905		if (_Color(_Left(_Pnode)) == _Black)
906		{    // rotate red up from right sub-subtree
907		_Color(_Right(_Pnode)) = _Black;
908		_Color(_Pnode) = _Red;
909		_Lrotate(_Pnode);
910		_Pnode = _Left(_Fixnodeparent);
911		}
912
913		_Color(_Pnode) = _Color(_Fixnodeparent);
914		_Color(_Fixnodeparent) = _Black;
915		_Color(_Left(_Pnode)) = _Black;
916		_Rrotate(_Fixnodeparent);
917		break;    // tree now recolored/rebalanced
918		}
919		}
920
921		_Color(_Fixnode) = _Black;    // ensure stopping node is black
922		}
923
924		this->_Alnod.destroy(_Erasednode);    // destroy, free erased node
925		this->_Alnod.deallocate(_Erasednode, 1);
926
927		if (0 < _Mysize)
928		--_Mysize;
929
930		return (_Make_iter(_Where));    // return successor iterator
931		}
932
933		iterator erase(const_iterator _First, const_iterator _Last)
934		{    // erase [_First, _Last)
935		if (_First == begin() && _Last == end())
936		{    // erase all
937		clear();
938		return (begin());
939		}
940		else
941		{    // partial erase, one at a time
942		while (_First != _Last)
943		erase(_First++);
944		return (_Make_iter(_First));
945		}
946		}
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		{    // erase all
966
967		#if _HAS_ITERATOR_DEBUGGING
968		this->_Orphan_ptr(*this, 0);
969		#endif /* _HAS_ITERATOR_DEBUGGING */
970
971		_Erase(_Root());
972		_Root() = _Myhead, _Mysize = 0;
973		_Lmost() = _Myhead, _Rmost() = _Myhead;
974		}
975
976		iterator find(const key_type& _Keyval)
977		{    // find an element in mutable sequence that matches _Keyval
978		iterator _Where = lower_bound(_Keyval);
979		return (_Where == end()
980		|| _DEBUG_LT_PRED(this->comp,
981		_Keyval, _Key(_Where._Mynode()))
982		? end() : _Where);
983		}
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		{    // count all elements that match _Keyval
996		_Paircc _Ans = equal_range(_Keyval);
997		size_type _Num = 0;
998		_Distance(_Ans.first, _Ans.second, _Num);
999		return (_Num);
1000		}
1001
1002		iterator lower_bound(const key_type& _Keyval)
1003		{    // find leftmost node not less than _Keyval in mutable tree
1004		return (_TREE_ITERATOR(_Lbound(_Keyval)));
1005		}
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		{    // find range equivalent to _Keyval in nonmutable tree
1029		return (_Eqrange(_Keyval));
1030		}
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

Lines 1090 ... 1315 are skipped.

1316		}
1317
1318		_Nodeptr& _Rmost() const
1319		{    // return rightmost node in nonmutable tree
1320		return (_Right(_Myhead));
1321		}
1322
1323		_Nodeptr& _Root() const
1324		{    // return root of nonmutable tree
1325		return (_Parent(_Myhead));
1326		}
1327
1328		void _Rrotate(_Nodeptr _Wherenode)
1329		{    // promote left node to root of subtree
1330		_Nodeptr _Pnode = _Left(_Wherenode);
1331		_Left(_Wherenode) = _Right(_Pnode);
1332
1333		if (!_Isnil(_Right(_Pnode)))
1334		_Parent(_Right(_Pnode)) = _Wherenode;
1335		_Parent(_Pnode) = _Parent(_Wherenode);
1336
1337		if (_Wherenode == _Root())
1338		_Root() = _Pnode;
1339		else if (_Wherenode == _Right(_Parent(_Wherenode)))
1340		_Right(_Parent(_Wherenode)) = _Pnode;
1341		else
1342		_Left(_Parent(_Wherenode)) = _Pnode;
1343
1344		_Right(_Pnode) = _Wherenode;
1345		_Parent(_Wherenode) = _Pnode;
1346		}
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		{    // orphan iterators with specified node pointers
1368		_Lockit _Lock(_LOCK_DEBUG);
1369		const_iterator **_Pnext = (const_iterator **)&_Cont._Myfirstiter;
1370		while (*_Pnext != 0)
1371		if ((*_Pnext)->_Ptr == _Myhead
1372		|| _Ptr != 0 && (*_Pnext)->_Ptr != _Ptr)
1373		_Pnext = (const_iterator **)&(*_Pnext)->_Mynextiter;
1374		else
1375		{    // orphan the iterator
1376		(*_Pnext)->_Mycont = 0;
1377		*_Pnext = (const_iterator *)(*_Pnext)->_Mynextiter;
1378		}
1379		}
1380		#endif /* _HAS_ITERATOR_DEBUGGING */
1381
1382		_Nodeptr _Buynode()
1383		{    // allocate a head/nil node
1384		_Nodeptr _Wherenode = this->_Alnod.allocate(1);
1385		int _Linkcnt = 0;
1386
1387		_TRY_BEGIN
1388		this->_Alptr.construct(&_Left(_Wherenode), 0);
1389		++_Linkcnt;
1390		this->_Alptr.construct(&_Parent(_Wherenode), 0);
1391		++_Linkcnt;
1392		this->_Alptr.construct(&_Right(_Wherenode), 0);
1393		_CATCH_ALL
1394		if (1 < _Linkcnt)
1395		this->_Alptr.destroy(&_Parent(_Wherenode));
1396		if (0 < _Linkcnt)
1397		this->_Alptr.destroy(&_Left(_Wherenode));
1398		this->_Alnod.deallocate(_Wherenode, 1);
1399		_RERAISE;
1400		_CATCH_END
1401		_Color(_Wherenode) = _Black;
1402		_Isnil(_Wherenode) = false;
1403		return (_Wherenode);
1404		}
1405
1406		_Nodeptr _Buynode(_Nodeptr _Larg, _Nodeptr _Parg,
1407		_Nodeptr _Rarg, const value_type& _Val, char _Carg)
1408		{    // allocate a node with pointers, value, and color
1409		_Nodeptr _Wherenode = this->_Alnod.allocate(1);
1410		_TRY_BEGIN
1411		new (_Wherenode) _Node(_Larg, _Parg, _Rarg, _Val, _Carg);
1412		_CATCH_ALL
1413		this->_Alnod.deallocate(_Wherenode, 1);
1414		_RERAISE;
1415		_CATCH_END
1416		return (_Wherenode);
1417		}
1418
1419		void _Tidy()
1420		{    // free all storage
1421		erase(begin(), end());
1422		this->_Alptr.destroy(&_Left(_Myhead));
1423		this->_Alptr.destroy(&_Parent(_Myhead));
1424		this->_Alptr.destroy(&_Right(_Myhead));
1425		this->_Alnod.deallocate(_Myhead, 1);
1426		_Myhead = 0, _Mysize = 0;
1427		}
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
1523