Sierra Toolkit Version of the Day
red_black_tree_eastl.h
00001 /*
00002 Copyright (C) 2005,2009-2010 Electronic Arts, Inc.  All rights reserved.
00003 
00004 Redistribution and use in source and binary forms, with or without
00005 modification, are permitted provided that the following conditions
00006 are met:
00007 
00008 1.  Redistributions of source code must retain the above copyright
00009     notice, this list of conditions and the following disclaimer.
00010 2.  Redistributions in binary form must reproduce the above copyright
00011     notice, this list of conditions and the following disclaimer in the
00012     documentation and/or other materials provided with the distribution.
00013 3.  Neither the name of Electronic Arts, Inc. ("EA") nor the names of
00014     its contributors may be used to endorse or promote products derived
00015     from this software without specific prior written permission.
00016 
00017 THIS SOFTWARE IS PROVIDED BY ELECTRONIC ARTS AND ITS CONTRIBUTORS "AS IS" AND ANY
00018 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
00019 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
00020 DISCLAIMED. IN NO EVENT SHALL ELECTRONIC ARTS OR ITS CONTRIBUTORS BE LIABLE FOR ANY
00021 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
00022 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00023 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
00024 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00025 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00026 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00027 */
00028 
00030 // EASTL/red_black_tree.h
00031 // Written by Paul Pedriana 2005.
00033 
00034 
00035 
00036 #ifndef EASTL_RED_BLACK_TREE_H
00037 #define EASTL_RED_BLACK_TREE_H
00038 
00039 
00040 
00041 #include <stk_util/util/config_eastl.h>
00042 #include <stk_util/util/type_traits_eastl.h>
00043 #include <stk_util/util/allocator_eastl.h>
00044 #include <stk_util/util/iterator_eastl.h>
00045 #include <stk_util/util/utility_eastl.h>
00046 #include <stk_util/util/algorithm_eastl.h>
00047 
00048 #ifdef _MSC_VER
00049     #pragma warning(push, 0)
00050     #include <new>
00051     #include <stddef.h>
00052     #pragma warning(pop)
00053 #else
00054     #include <new>
00055     #include <stddef.h>
00056 #endif
00057 
00058 
00059 #ifdef _MSC_VER
00060     #pragma warning(push)
00061     #pragma warning(disable: 4512)  // 'class' : assignment operator could not be generated
00062     #pragma warning(disable: 4530)  // C++ exception handler used, but unwind semantics are not enabled. Specify /EHsc
00063 #endif
00064 
00065 
00066 namespace eastl
00067 {
00068 
00073     #ifndef EASTL_RBTREE_DEFAULT_NAME
00074         #define EASTL_RBTREE_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " rbtree" // Unless the user overrides something, this is "EASTL rbtree".
00075     #endif
00076 
00077 
00080     #ifndef EASTL_RBTREE_DEFAULT_ALLOCATOR
00081         #define EASTL_RBTREE_DEFAULT_ALLOCATOR allocator_type(EASTL_RBTREE_DEFAULT_NAME)
00082     #endif
00083 
00084 
00085 
00088     enum RBTreeColor
00089     {
00090         kRBTreeColorRed,
00091         kRBTreeColorBlack
00092     };
00093 
00094 
00095 
00098     enum RBTreeSide
00099     {
00100         kRBTreeSideLeft,
00101         kRBTreeSideRight
00102     };
00103 
00104 
00105 
00116     struct rbtree_node_base
00117     {
00118         typedef rbtree_node_base this_type;
00119 
00120     public:
00121         this_type* mpNodeRight;  // Declared first because it is used most often.
00122         this_type* mpNodeLeft;
00123         this_type* mpNodeParent;
00124         char       mColor;       // We only need one bit here, would be nice if we could stuff that bit somewhere else.
00125     };
00126 
00127 
00130     template <typename Value>
00131     struct rbtree_node : public rbtree_node_base
00132     {
00133         Value mValue; // For set and multiset, this is the user's value, for map and multimap, this is a pair of key/value.
00134     };
00135 
00136 
00137 
00138 
00139     // rbtree_node_base functions
00140     //
00141     // These are the fundamental functions that we use to maintain the
00142     // tree. The bulk of the work of the tree maintenance is done in
00143     // these functions.
00144     //
00145     EASTL_API rbtree_node_base* RBTreeIncrement    (const rbtree_node_base* pNode);
00146     EASTL_API rbtree_node_base* RBTreeDecrement    (const rbtree_node_base* pNode);
00147     EASTL_API rbtree_node_base* RBTreeGetMinChild  (const rbtree_node_base* pNode);
00148     EASTL_API rbtree_node_base* RBTreeGetMaxChild  (const rbtree_node_base* pNode);
00149     EASTL_API size_t            RBTreeGetBlackCount(const rbtree_node_base* pNodeTop,
00150                                                     const rbtree_node_base* pNodeBottom);
00151     EASTL_API void              RBTreeInsert       (      rbtree_node_base* pNode,
00152                                                           rbtree_node_base* pNodeParent,
00153                                                           rbtree_node_base* pNodeAnchor,
00154                                                           RBTreeSide insertionSide);
00155     EASTL_API void              RBTreeErase        (      rbtree_node_base* pNode,
00156                                                           rbtree_node_base* pNodeAnchor);
00157 
00158 
00159 
00160 
00161 
00162 
00163 
00166     template <typename T, typename Pointer, typename Reference>
00167     struct rbtree_iterator
00168     {
00169         typedef rbtree_iterator<T, Pointer, Reference>      this_type;
00170         typedef rbtree_iterator<T, T*, T&>                  iterator;
00171         typedef rbtree_iterator<T, const T*, const T&>      const_iterator;
00172         typedef eastl_size_t                                size_type;     // See config.h for the definition of eastl_size_t, which defaults to uint32_t.
00173         typedef ptrdiff_t                                   difference_type;
00174         typedef T                                           value_type;
00175         typedef rbtree_node_base                            base_node_type;
00176         typedef rbtree_node<T>                              node_type;
00177         typedef Pointer                                     pointer;
00178         typedef Reference                                   reference;
00179         typedef EASTL_ITC_NS::bidirectional_iterator_tag    iterator_category;
00180 
00181     public:
00182         node_type* mpNode;
00183 
00184     public:
00185         rbtree_iterator();
00186         explicit rbtree_iterator(const node_type* pNode);
00187         rbtree_iterator(const iterator& x);
00188 
00189         reference operator*() const;
00190         pointer   operator->() const;
00191 
00192         rbtree_iterator& operator++();
00193         rbtree_iterator  operator++(int);
00194 
00195         rbtree_iterator& operator--();
00196         rbtree_iterator  operator--(int);
00197 
00198     }; // rbtree_iterator
00199 
00200 
00201 
00202 
00203 
00205     // rb_base
00206     //
00207     // This class allows us to use a generic rbtree as the basis of map, multimap,
00208     // set, and multiset transparently. The vital template parameters for this are
00209     // the ExtractKey and the bUniqueKeys parameters.
00210     //
00211     // If the rbtree has a value type of the form pair<T1, T2> (i.e. it is a map or
00212     // multimap and not a set or multiset) and a key extraction policy that returns
00213     // the first part of the pair, the rbtree gets a mapped_type typedef.
00214     // If it satisfies those criteria and also has unique keys, then it also gets an
00215     // operator[] (which only map and set have and multimap and multiset don't have).
00216     //
00218 
00219 
00220 
00225     template <typename Key, typename Value, typename Compare, typename ExtractKey, bool bUniqueKeys, typename RBTree>
00226     struct rb_base
00227     {
00228         typedef ExtractKey extract_key;
00229 
00230     public:
00231         Compare mCompare; // To do: Make sure that empty Compare classes go away via empty base optimizations.
00232 
00233     public:
00234         rb_base() : mCompare() {}
00235         rb_base(const Compare& compare) : mCompare(compare) {}
00236     };
00237 
00238 
00244     template <typename Key, typename Value, typename Compare, typename ExtractKey, typename RBTree>
00245     struct rb_base<Key, Value, Compare, ExtractKey, false, RBTree>
00246     {
00247         typedef ExtractKey extract_key;
00248 
00249     public:
00250         Compare mCompare; // To do: Make sure that empty Compare classes go away via empty base optimizations.
00251 
00252     public:
00253         rb_base() : mCompare() {}
00254         rb_base(const Compare& compare) : mCompare(compare) {}
00255     };
00256 
00257 
00261     template <typename Key, typename Pair, typename Compare, typename RBTree>
00262     struct rb_base<Key, Pair, Compare, eastl::use_first<Pair>, true, RBTree>
00263     {
00264         typedef eastl::use_first<Pair> extract_key;
00265 
00266     public:
00267         Compare mCompare; // To do: Make sure that empty Compare classes go away via empty base optimizations.
00268 
00269     public:
00270         rb_base() : mCompare() {}
00271         rb_base(const Compare& compare) : mCompare(compare) {}
00272     };
00273 
00274 
00278     template <typename Key, typename Pair, typename Compare, typename RBTree>
00279     struct rb_base<Key, Pair, Compare, eastl::use_first<Pair>, false, RBTree>
00280     {
00281         typedef eastl::use_first<Pair> extract_key;
00282 
00283     public:
00284         Compare mCompare; // To do: Make sure that empty Compare classes go away via empty base optimizations.
00285 
00286     public:
00287         rb_base() : mCompare() {}
00288         rb_base(const Compare& compare) : mCompare(compare) {}
00289     };
00290 
00291 
00292 
00293 
00294 
00343     template <typename Key, typename Value, typename Compare, typename Allocator,
00344               typename ExtractKey, bool bMutableIterators, bool bUniqueKeys>
00345     class rbtree
00346         : public rb_base<Key, Value, Compare, ExtractKey, bUniqueKeys,
00347                             rbtree<Key, Value, Compare, Allocator, ExtractKey, bMutableIterators, bUniqueKeys> >
00348     {
00349     public:
00350         typedef ptrdiff_t                                                                       difference_type;
00351         typedef eastl_size_t                                                                    size_type;     // See config.h for the definition of eastl_size_t, which defaults to uint32_t.
00352         typedef Key                                                                             key_type;
00353         typedef Value                                                                           value_type;
00354         typedef rbtree_node<value_type>                                                         node_type;
00355         typedef value_type&                                                                     reference;
00356         typedef const value_type&                                                               const_reference;
00357         typedef typename type_select<bMutableIterators,
00358                     rbtree_iterator<value_type, value_type*, value_type&>,
00359                     rbtree_iterator<value_type, const value_type*, const value_type&> >::type   iterator;
00360         typedef rbtree_iterator<value_type, const value_type*, const value_type&>               const_iterator;
00361         typedef eastl::reverse_iterator<iterator>                                               reverse_iterator;
00362         typedef eastl::reverse_iterator<const_iterator>                                         const_reverse_iterator;
00363 
00364         typedef Allocator                                                                       allocator_type;
00365         typedef Compare                                                                         key_compare;
00366         typedef typename type_select<bUniqueKeys, eastl::pair<iterator, bool>, iterator>::type  insert_return_type;  // map/set::insert return a pair, multimap/multiset::iterator return an iterator.
00367         typedef rbtree<Key, Value, Compare, Allocator,
00368                         ExtractKey, bMutableIterators, bUniqueKeys>                             this_type;
00369         typedef rb_base<Key, Value, Compare, ExtractKey, bUniqueKeys, this_type>                base_type;
00370         typedef integral_constant<bool, bUniqueKeys>                                            has_unique_keys_type;
00371         typedef typename base_type::extract_key                                                 extract_key;
00372 
00373         using base_type::mCompare;
00374 
00375         enum
00376         {
00377             kKeyAlignment         = EASTL_ALIGN_OF(key_type),
00378             kKeyAlignmentOffset   = 0,                          // To do: Make sure this really is zero for all uses of this template.
00379             kValueAlignment       = EASTL_ALIGN_OF(value_type),
00380             kValueAlignmentOffset = 0                           // To fix: This offset is zero for sets and >0 for maps. Need to fix this.
00381         };
00382 
00383     public:
00384         rbtree_node_base  mAnchor;      
00385         size_type         mnSize;       
00386         allocator_type    mAllocator;   // To do: Use base class optimization to make this go away.
00387 
00388     public:
00389         // ctor/dtor
00390         rbtree();
00391         rbtree(const allocator_type& allocator);
00392         rbtree(const Compare& compare, const allocator_type& allocator = EASTL_RBTREE_DEFAULT_ALLOCATOR);
00393         rbtree(const this_type& x);
00394 
00395         template <typename InputIterator>
00396         rbtree(InputIterator first, InputIterator last, const Compare& compare, const allocator_type& allocator = EASTL_RBTREE_DEFAULT_ALLOCATOR);
00397 
00398        ~rbtree();
00399 
00400     public:
00401         // properties
00402         allocator_type& get_allocator();
00403         void            set_allocator(const allocator_type& allocator);
00404 
00405         const key_compare& key_comp() const { return mCompare; }
00406         key_compare&       key_comp()       { return mCompare; }
00407 
00408         this_type& operator=(const this_type& x);
00409 
00410         void swap(this_type& x);
00411 
00412     public:
00413         // iterators
00414         iterator        begin();
00415         const_iterator  begin() const;
00416         iterator        end();
00417         const_iterator  end() const;
00418 
00419         reverse_iterator        rbegin();
00420         const_reverse_iterator  rbegin() const;
00421         reverse_iterator        rend();
00422         const_reverse_iterator  rend() const;
00423 
00424     public:
00425         bool      empty() const;
00426         size_type size() const;
00427 
00430         insert_return_type insert(const value_type& value);
00431 
00432         // C++ standard: inserts value if and only if there is no element with
00433         // key equivalent to the key of t in containers with unique keys; always
00434         // inserts value in containers with equivalent keys. Always returns the
00435         // iterator pointing to the element with key equivalent to the key of value.
00436         // iterator position is a hint pointing to where the insert should start
00437         // to search. However, there is a potential defect/improvement report on this behaviour:
00438         // LWG issue #233 (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html)
00439         // We follow the same approach as SGI STL/STLPort and use the position as
00440         // a forced insertion position for the value when possible.
00441         iterator insert(iterator position, const value_type& value);
00442 
00443         template <typename InputIterator>
00444         void insert(InputIterator first, InputIterator last);
00445 
00446         iterator erase(iterator position);
00447         iterator erase(iterator first, iterator last);
00448 
00449         reverse_iterator erase(reverse_iterator position);
00450         reverse_iterator erase(reverse_iterator first, reverse_iterator last);
00451 
00452         // For some reason, multiple STL versions make a specialization
00453         // for erasing an array of key_types. I'm pretty sure we don't
00454         // need this, but just to be safe we will follow suit.
00455         // The implementation is trivial. Returns void because the values
00456         // could well be randomly distributed throughout the tree and thus
00457         // a return value would be nearly meaningless.
00458         void erase(const key_type* first, const key_type* last);
00459 
00460         void clear();
00461         void reset();
00462 
00463         iterator       find(const key_type& key);
00464         const_iterator find(const key_type& key) const;
00465 
00477         template <typename U, typename Compare2>
00478         iterator       find_as(const U& u, Compare2 compare2);
00479 
00480         template <typename U, typename Compare2>
00481         const_iterator find_as(const U& u, Compare2 compare2) const;
00482 
00483         iterator       lower_bound(const key_type& key);
00484         const_iterator lower_bound(const key_type& key) const;
00485 
00486         iterator       upper_bound(const key_type& key);
00487         const_iterator upper_bound(const key_type& key) const;
00488 
00489         bool validate() const;
00490         int  validate_iterator(const_iterator i) const;
00491 
00492     protected:
00493         node_type*  DoAllocateNode();
00494         void        DoFreeNode(node_type* pNode);
00495 
00496         node_type* DoCreateNodeFromKey(const key_type& key);
00497         node_type* DoCreateNode(const value_type& value);
00498         node_type* DoCreateNode(const node_type* pNodeSource, node_type* pNodeParent);
00499 
00500         node_type* DoCopySubtree(const node_type* pNodeSource, node_type* pNodeDest);
00501         void       DoNukeSubtree(node_type* pNode);
00502 
00503         // Intentionally return a pair and not an iterator for DoInsertValue(..., true_type)
00504         // This is because the C++ standard for map and set is to return a pair and not just an iterator.
00505         eastl::pair<iterator, bool> DoInsertValue(const value_type& value, true_type);  // true_type means keys are unique.
00506         iterator DoInsertValue(const value_type& value, false_type);                    // false_type means keys are not unique.
00507 
00508         eastl::pair<iterator, bool> DoInsertKey(const key_type& key, true_type);
00509         iterator DoInsertKey(const key_type& key, false_type);
00510 
00511         iterator DoInsertValue(iterator position, const value_type& value, true_type);
00512         iterator DoInsertValue(iterator position, const value_type& value, false_type);
00513 
00514         iterator DoInsertKey(iterator position, const key_type& key, true_type);
00515         iterator DoInsertKey(iterator position, const key_type& key, false_type);
00516 
00517         iterator DoInsertValueImpl(node_type* pNodeParent, const value_type& value, bool bForceToLeft);
00518         iterator DoInsertKeyImpl(node_type* pNodeParent, const key_type& key, bool bForceToLeft);
00519 
00520     }; // rbtree
00521 
00522 
00523 
00524 
00525 
00527     // rbtree_node_base functions
00529 
00530     EASTL_API inline rbtree_node_base* RBTreeGetMinChild(const rbtree_node_base* pNodeBase)
00531     {
00532         while(pNodeBase->mpNodeLeft)
00533             pNodeBase = pNodeBase->mpNodeLeft;
00534         return const_cast<rbtree_node_base*>(pNodeBase);
00535     }
00536 
00537     EASTL_API inline rbtree_node_base* RBTreeGetMaxChild(const rbtree_node_base* pNodeBase)
00538     {
00539         while(pNodeBase->mpNodeRight)
00540             pNodeBase = pNodeBase->mpNodeRight;
00541         return const_cast<rbtree_node_base*>(pNodeBase);
00542     }
00543 
00544     // The rest of the functions are non-trivial and are found in
00545     // the corresponding .cpp file to this file.
00546 
00547 
00548 
00550     // rbtree_iterator functions
00552 
00553     template <typename T, typename Pointer, typename Reference>
00554     rbtree_iterator<T, Pointer, Reference>::rbtree_iterator()
00555         : mpNode(NULL) { }
00556 
00557 
00558     template <typename T, typename Pointer, typename Reference>
00559     rbtree_iterator<T, Pointer, Reference>::rbtree_iterator(const node_type* pNode)
00560         : mpNode(static_cast<node_type*>(const_cast<node_type*>(pNode))) { }
00561 
00562 
00563     template <typename T, typename Pointer, typename Reference>
00564     rbtree_iterator<T, Pointer, Reference>::rbtree_iterator(const iterator& x)
00565         : mpNode(x.mpNode) { }
00566 
00567 
00568     template <typename T, typename Pointer, typename Reference>
00569     typename rbtree_iterator<T, Pointer, Reference>::reference
00570     rbtree_iterator<T, Pointer, Reference>::operator*() const
00571         { return mpNode->mValue; }
00572 
00573 
00574     template <typename T, typename Pointer, typename Reference>
00575     typename rbtree_iterator<T, Pointer, Reference>::pointer
00576     rbtree_iterator<T, Pointer, Reference>::operator->() const
00577         { return &mpNode->mValue; }
00578 
00579 
00580     template <typename T, typename Pointer, typename Reference>
00581     typename rbtree_iterator<T, Pointer, Reference>::this_type&
00582     rbtree_iterator<T, Pointer, Reference>::operator++()
00583     {
00584         mpNode = static_cast<node_type*>(RBTreeIncrement(mpNode));
00585         return *this;
00586     }
00587 
00588 
00589     template <typename T, typename Pointer, typename Reference>
00590     typename rbtree_iterator<T, Pointer, Reference>::this_type
00591     rbtree_iterator<T, Pointer, Reference>::operator++(int)
00592     {
00593         this_type temp(*this);
00594         mpNode = static_cast<node_type*>(RBTreeIncrement(mpNode));
00595         return temp;
00596     }
00597 
00598 
00599     template <typename T, typename Pointer, typename Reference>
00600     typename rbtree_iterator<T, Pointer, Reference>::this_type&
00601     rbtree_iterator<T, Pointer, Reference>::operator--()
00602     {
00603         mpNode = static_cast<node_type*>(RBTreeDecrement(mpNode));
00604         return *this;
00605     }
00606 
00607 
00608     template <typename T, typename Pointer, typename Reference>
00609     typename rbtree_iterator<T, Pointer, Reference>::this_type
00610     rbtree_iterator<T, Pointer, Reference>::operator--(int)
00611     {
00612         this_type temp(*this);
00613         mpNode = static_cast<node_type*>(RBTreeDecrement(mpNode));
00614         return temp;
00615     }
00616 
00617 
00618     // The C++ defect report #179 requires that we support comparisons between const and non-const iterators.
00619     // Thus we provide additional template paremeters here to support this. The defect report does not
00620     // require us to support comparisons between reverse_iterators and const_reverse_iterators.
00621     template <typename T, typename PointerA, typename ReferenceA, typename PointerB, typename ReferenceB>
00622     inline bool operator==(const rbtree_iterator<T, PointerA, ReferenceA>& a,
00623                            const rbtree_iterator<T, PointerB, ReferenceB>& b)
00624     {
00625         return a.mpNode == b.mpNode;
00626     }
00627 
00628 
00629     template <typename T, typename PointerA, typename ReferenceA, typename PointerB, typename ReferenceB>
00630     inline bool operator!=(const rbtree_iterator<T, PointerA, ReferenceA>& a,
00631                            const rbtree_iterator<T, PointerB, ReferenceB>& b)
00632     {
00633         return a.mpNode != b.mpNode;
00634     }
00635 
00636 
00637     // We provide a version of operator!= for the case where the iterators are of the
00638     // same type. This helps prevent ambiguity errors in the presence of rel_ops.
00639     template <typename T, typename Pointer, typename Reference>
00640     inline bool operator!=(const rbtree_iterator<T, Pointer, Reference>& a,
00641                            const rbtree_iterator<T, Pointer, Reference>& b)
00642     {
00643         return a.mpNode != b.mpNode;
00644     }
00645 
00646 
00647 
00648 
00650     // rbtree functions
00652 
00653     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00654     inline rbtree<K, V, C, A, E, bM, bU>::rbtree()
00655         : mAnchor(),
00656           mnSize(0),
00657           mAllocator(EASTL_RBTREE_DEFAULT_NAME)
00658     {
00659         reset();
00660     }
00661 
00662 
00663     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00664     inline rbtree<K, V, C, A, E, bM, bU>::rbtree(const allocator_type& allocator)
00665         : mAnchor(),
00666           mnSize(0),
00667           mAllocator(allocator)
00668     {
00669         reset();
00670     }
00671 
00672 
00673     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00674     inline rbtree<K, V, C, A, E, bM, bU>::rbtree(const C& compare, const allocator_type& allocator)
00675         : base_type(compare),
00676           mAnchor(),
00677           mnSize(0),
00678           mAllocator(allocator)
00679     {
00680         reset();
00681     }
00682 
00683 
00684     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00685     inline rbtree<K, V, C, A, E, bM, bU>::rbtree(const this_type& x)
00686         : base_type(x.mCompare),
00687           mAnchor(),
00688           mnSize(0),
00689           mAllocator(x.mAllocator)
00690     {
00691         reset();
00692 
00693         if(x.mAnchor.mpNodeParent) // mAnchor.mpNodeParent is the rb_tree root node.
00694         {
00695             mAnchor.mpNodeParent = DoCopySubtree((const node_type*)x.mAnchor.mpNodeParent, (node_type*)&mAnchor);
00696             mAnchor.mpNodeRight  = RBTreeGetMaxChild(mAnchor.mpNodeParent);
00697             mAnchor.mpNodeLeft   = RBTreeGetMinChild(mAnchor.mpNodeParent);
00698             mnSize               = x.mnSize;
00699         }
00700     }
00701 
00702 
00703     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00704     template <typename InputIterator>
00705     inline rbtree<K, V, C, A, E, bM, bU>::rbtree(InputIterator first, InputIterator last, const C& compare, const allocator_type& allocator)
00706         : base_type(compare),
00707           mAnchor(),
00708           mnSize(0),
00709           mAllocator(allocator)
00710     {
00711         reset();
00712 
00713         #if EASTL_EXCEPTIONS_ENABLED
00714             try
00715             {
00716         #endif
00717                 for(; first != last; ++first)
00718                     insert(*first);
00719         #if EASTL_EXCEPTIONS_ENABLED
00720             }
00721             catch(...)
00722             {
00723                 clear();
00724                 throw;
00725             }
00726         #endif
00727     }
00728 
00729 
00730     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00731     inline rbtree<K, V, C, A, E, bM, bU>::~rbtree()
00732     {
00733         // Erase the entire tree. DoNukeSubtree is not a
00734         // conventional erase function, as it does no rebalancing.
00735         DoNukeSubtree((node_type*)mAnchor.mpNodeParent);
00736     }
00737 
00738 
00739     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00740     inline typename rbtree<K, V, C, A, E, bM, bU>::allocator_type&
00741     rbtree<K, V, C, A, E, bM, bU>::get_allocator()
00742     {
00743         return mAllocator;
00744     }
00745 
00746 
00747     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00748     inline void rbtree<K, V, C, A, E, bM, bU>::set_allocator(const allocator_type& allocator)
00749     {
00750         mAllocator = allocator;
00751     }
00752 
00753 
00754     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00755     inline typename rbtree<K, V, C, A, E, bM, bU>::size_type
00756     rbtree<K, V, C, A, E, bM, bU>::size() const
00757         { return mnSize; }
00758 
00759 
00760     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00761     inline bool rbtree<K, V, C, A, E, bM, bU>::empty() const
00762         { return (mnSize == 0); }
00763 
00764 
00765     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00766     inline typename rbtree<K, V, C, A, E, bM, bU>::iterator
00767     rbtree<K, V, C, A, E, bM, bU>::begin()
00768         { return iterator(static_cast<node_type*>(mAnchor.mpNodeLeft)); }
00769 
00770 
00771     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00772     inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator
00773     rbtree<K, V, C, A, E, bM, bU>::begin() const
00774         { return const_iterator(static_cast<node_type*>(const_cast<rbtree_node_base*>(mAnchor.mpNodeLeft))); }
00775 
00776 
00777     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00778     inline typename rbtree<K, V, C, A, E, bM, bU>::iterator
00779     rbtree<K, V, C, A, E, bM, bU>::end()
00780         { return iterator(static_cast<node_type*>(&mAnchor)); }
00781 
00782 
00783     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00784     inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator
00785     rbtree<K, V, C, A, E, bM, bU>::end() const
00786         { return const_iterator(static_cast<node_type*>(const_cast<rbtree_node_base*>(&mAnchor))); }
00787 
00788 
00789     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00790     inline typename rbtree<K, V, C, A, E, bM, bU>::reverse_iterator
00791     rbtree<K, V, C, A, E, bM, bU>::rbegin()
00792         { return reverse_iterator(end()); }
00793 
00794 
00795     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00796     inline typename rbtree<K, V, C, A, E, bM, bU>::const_reverse_iterator
00797     rbtree<K, V, C, A, E, bM, bU>::rbegin() const
00798         { return const_reverse_iterator(end()); }
00799 
00800 
00801     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00802     inline typename rbtree<K, V, C, A, E, bM, bU>::reverse_iterator
00803     rbtree<K, V, C, A, E, bM, bU>::rend()
00804         { return reverse_iterator(begin()); }
00805 
00806 
00807     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00808     inline typename rbtree<K, V, C, A, E, bM, bU>::const_reverse_iterator
00809     rbtree<K, V, C, A, E, bM, bU>::rend() const
00810         { return const_reverse_iterator(begin()); }
00811 
00812 
00813     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00814     inline typename rbtree<K, V, C, A, E, bM, bU>::this_type&
00815     rbtree<K, V, C, A, E, bM, bU>::operator=(const this_type& x)
00816     {
00817         if(this != &x)
00818         {
00819             clear();
00820 
00821             #if EASTL_ALLOCATOR_COPY_ENABLED
00822                 mAllocator = x.mAllocator;
00823             #endif
00824 
00825             base_type::mCompare = x.mCompare;
00826 
00827             if(x.mAnchor.mpNodeParent) // mAnchor.mpNodeParent is the rb_tree root node.
00828             {
00829                 mAnchor.mpNodeParent = DoCopySubtree((const node_type*)x.mAnchor.mpNodeParent, (node_type*)&mAnchor);
00830                 mAnchor.mpNodeRight  = RBTreeGetMaxChild(mAnchor.mpNodeParent);
00831                 mAnchor.mpNodeLeft   = RBTreeGetMinChild(mAnchor.mpNodeParent);
00832                 mnSize               = x.mnSize;
00833             }
00834         }
00835         return *this;
00836     }
00837 
00838 
00839     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00840     void rbtree<K, V, C, A, E, bM, bU>::swap(this_type& x)
00841     {
00842         if(mAllocator == x.mAllocator) // If allocators are equivalent...
00843         {
00844             // Most of our members can be exchaged by a basic swap:
00845             // We leave mAllocator as-is.
00846             eastl::swap(mnSize,              x.mnSize);
00847             eastl::swap(base_type::mCompare, x.mCompare);
00848 
00849             // However, because our anchor node is a part of our class instance and not
00850             // dynamically allocated, we can't do a swap of it but must do a more elaborate
00851             // procedure. This is the downside to having the mAnchor be like this, but
00852             // otherwise we consider it a good idea to avoid allocating memory for a
00853             // nominal container instance.
00854 
00855             // We optimize for the expected most common case: both pointers being non-null.
00856             if(mAnchor.mpNodeParent && x.mAnchor.mpNodeParent) // If both pointers are non-null...
00857             {
00858                 eastl::swap(mAnchor.mpNodeRight,  x.mAnchor.mpNodeRight);
00859                 eastl::swap(mAnchor.mpNodeLeft,   x.mAnchor.mpNodeLeft);
00860                 eastl::swap(mAnchor.mpNodeParent, x.mAnchor.mpNodeParent);
00861 
00862                 // We need to fix up the anchors to point to themselves (we can't just swap them).
00863                 mAnchor.mpNodeParent->mpNodeParent   = &mAnchor;
00864                 x.mAnchor.mpNodeParent->mpNodeParent = &x.mAnchor;
00865             }
00866             else if(mAnchor.mpNodeParent)
00867             {
00868                 x.mAnchor.mpNodeRight  = mAnchor.mpNodeRight;
00869                 x.mAnchor.mpNodeLeft   = mAnchor.mpNodeLeft;
00870                 x.mAnchor.mpNodeParent = mAnchor.mpNodeParent;
00871                 x.mAnchor.mpNodeParent->mpNodeParent = &x.mAnchor;
00872 
00873                 // We need to fix up our anchor to point it itself (we can't have it swap with x).
00874                 mAnchor.mpNodeRight  = &mAnchor;
00875                 mAnchor.mpNodeLeft   = &mAnchor;
00876                 mAnchor.mpNodeParent = NULL;
00877             }
00878             else if(x.mAnchor.mpNodeParent)
00879             {
00880                 mAnchor.mpNodeRight  = x.mAnchor.mpNodeRight;
00881                 mAnchor.mpNodeLeft   = x.mAnchor.mpNodeLeft;
00882                 mAnchor.mpNodeParent = x.mAnchor.mpNodeParent;
00883                 mAnchor.mpNodeParent->mpNodeParent = &mAnchor;
00884 
00885                 // We need to fix up x's anchor to point it itself (we can't have it swap with us).
00886                 x.mAnchor.mpNodeRight  = &x.mAnchor;
00887                 x.mAnchor.mpNodeLeft   = &x.mAnchor;
00888                 x.mAnchor.mpNodeParent = NULL;
00889             } // Else both are NULL and there is nothing to do.
00890         }
00891         else
00892         {
00893             const this_type temp(*this); // Can't call eastl::swap because that would
00894             *this = x;                   // itself call this member swap function.
00895             x     = temp;
00896         }
00897     }
00898 
00899 
00900     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00901     inline typename rbtree<K, V, C, A, E, bM, bU>::insert_return_type // map/set::insert return a pair, multimap/multiset::iterator return an iterator.
00902     rbtree<K, V, C, A, E, bM, bU>::insert(const value_type& value)
00903         { return DoInsertValue(value, has_unique_keys_type()); }
00904 
00905 
00906     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00907     typename rbtree<K, V, C, A, E, bM, bU>::iterator
00908     rbtree<K, V, C, A, E, bM, bU>::insert(iterator position, const value_type& value)
00909         { return DoInsertValue(position, value, has_unique_keys_type()); }
00910 
00911 
00912     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00913     eastl::pair<typename rbtree<K, V, C, A, E, bM, bU>::iterator, bool>
00914     rbtree<K, V, C, A, E, bM, bU>::DoInsertValue(const value_type& value, true_type) // true_type means keys are unique.
00915     {
00916         // This is the pathway for insertion of unique keys (map and set, but not multimap and multiset).
00917         // Note that we return a pair and not an iterator. This is because the C++ standard for map
00918         // and set is to return a pair and not just an iterator.
00919         extract_key extractKey;
00920 
00921         node_type* pCurrent    = (node_type*)mAnchor.mpNodeParent; // Start with the root node.
00922         node_type* pLowerBound = (node_type*)&mAnchor;             // Set it to the container end for now.
00923         node_type* pParent;                                        // This will be where we insert the new node.
00924 
00925         bool bValueLessThanNode = true; // If the tree is empty, this will result in an insertion at the front.
00926 
00927         // Find insertion position of the value. This will either be a position which
00928         // already contains the value, a position which is greater than the value or
00929         // end(), which we treat like a position which is greater than the value.
00930         while(EASTL_LIKELY(pCurrent)) // Do a walk down the tree.
00931         {
00932             bValueLessThanNode = mCompare(extractKey(value), extractKey(pCurrent->mValue));
00933             pLowerBound        = pCurrent;
00934 
00935             if(bValueLessThanNode)
00936             {
00937                 EASTL_VALIDATE_COMPARE(!mCompare(extractKey(pCurrent->mValue), extractKey(value))); // Validate that the compare function is sane.
00938                 pCurrent = (node_type*)pCurrent->mpNodeLeft;
00939             }
00940             else
00941                 pCurrent = (node_type*)pCurrent->mpNodeRight;
00942         }
00943 
00944         pParent = pLowerBound; // pLowerBound is actually upper bound right now (i.e. it is > value instead of <=), but we will make it the lower bound below.
00945 
00946         if(bValueLessThanNode) // If we ended up on the left side of the last parent node...
00947         {
00948             if(EASTL_LIKELY(pLowerBound != (node_type*)mAnchor.mpNodeLeft)) // If the tree was empty or if we otherwise need to insert at the very front of the tree...
00949             {
00950                 // At this point, pLowerBound points to a node which is > than value.
00951                 // Move it back by one, so that it points to a node which is <= value.
00952                 pLowerBound = (node_type*)RBTreeDecrement(pLowerBound);
00953             }
00954             else
00955             {
00956                 const iterator itResult(DoInsertValueImpl(pLowerBound, value, false));
00957                 return pair<iterator, bool>(itResult, true);
00958             }
00959         }
00960 
00961         // Since here we require values to be unique, we will do nothing if the value already exists.
00962         if(mCompare(extractKey(pLowerBound->mValue), extractKey(value))) // If the node is < the value (i.e. if value is >= the node)...
00963         {
00964             EASTL_VALIDATE_COMPARE(!mCompare(extractKey(value), extractKey(pLowerBound->mValue))); // Validate that the compare function is sane.
00965             const iterator itResult(DoInsertValueImpl(pParent, value, false));
00966             return pair<iterator, bool>(itResult, true);
00967         }
00968 
00969         // The item already exists (as found by the compare directly above), so return false.
00970         return pair<iterator, bool>(iterator(pLowerBound), false);
00971     }
00972 
00973 
00974     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
00975     typename rbtree<K, V, C, A, E, bM, bU>::iterator
00976     rbtree<K, V, C, A, E, bM, bU>::DoInsertValue(const value_type& value, false_type) // false_type means keys are not unique.
00977     {
00978         // This is the pathway for insertion of non-unique keys (multimap and multiset, but not map and set).
00979         node_type* pCurrent  = (node_type*)mAnchor.mpNodeParent; // Start with the root node.
00980         node_type* pRangeEnd = (node_type*)&mAnchor;             // Set it to the container end for now.
00981         extract_key extractKey;
00982 
00983         while(pCurrent)
00984         {
00985             pRangeEnd = pCurrent;
00986 
00987             if(mCompare(extractKey(value), extractKey(pCurrent->mValue)))
00988             {
00989                 EASTL_VALIDATE_COMPARE(!mCompare(extractKey(pCurrent->mValue), extractKey(value))); // Validate that the compare function is sane.
00990                 pCurrent = (node_type*)pCurrent->mpNodeLeft;
00991             }
00992             else
00993                 pCurrent = (node_type*)pCurrent->mpNodeRight;
00994         }
00995 
00996         return DoInsertValueImpl(pRangeEnd, value, false);
00997     }
00998 
00999 
01000     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01001     eastl::pair<typename rbtree<K, V, C, A, E, bM, bU>::iterator, bool>
01002     rbtree<K, V, C, A, E, bM, bU>::DoInsertKey(const key_type& key, true_type) // true_type means keys are unique.
01003     {
01004         // This code is essentially a slightly modified copy of the the rbtree::insert
01005         // function whereby this version takes a key and not a full value_type.
01006         extract_key extractKey;
01007 
01008         node_type* pCurrent    = (node_type*)mAnchor.mpNodeParent; // Start with the root node.
01009         node_type* pLowerBound = (node_type*)&mAnchor;             // Set it to the container end for now.
01010         node_type* pParent;                                        // This will be where we insert the new node.
01011 
01012         bool bValueLessThanNode = true; // If the tree is empty, this will result in an insertion at the front.
01013 
01014         // Find insertion position of the value. This will either be a position which
01015         // already contains the value, a position which is greater than the value or
01016         // end(), which we treat like a position which is greater than the value.
01017         while(EASTL_LIKELY(pCurrent)) // Do a walk down the tree.
01018         {
01019             bValueLessThanNode = mCompare(key, extractKey(pCurrent->mValue));
01020             pLowerBound        = pCurrent;
01021 
01022             if(bValueLessThanNode)
01023             {
01024                 EASTL_VALIDATE_COMPARE(!mCompare(extractKey(pCurrent->mValue), key)); // Validate that the compare function is sane.
01025                 pCurrent = (node_type*)pCurrent->mpNodeLeft;
01026             }
01027             else
01028                 pCurrent = (node_type*)pCurrent->mpNodeRight;
01029         }
01030 
01031         pParent = pLowerBound; // pLowerBound is actually upper bound right now (i.e. it is > value instead of <=), but we will make it the lower bound below.
01032 
01033         if(bValueLessThanNode) // If we ended up on the left side of the last parent node...
01034         {
01035             if(EASTL_LIKELY(pLowerBound != (node_type*)mAnchor.mpNodeLeft)) // If the tree was empty or if we otherwise need to insert at the very front of the tree...
01036             {
01037                 // At this point, pLowerBound points to a node which is > than value.
01038                 // Move it back by one, so that it points to a node which is <= value.
01039                 pLowerBound = (node_type*)RBTreeDecrement(pLowerBound);
01040             }
01041             else
01042             {
01043                 const iterator itResult(DoInsertKeyImpl(pLowerBound, key, false));
01044                 return pair<iterator, bool>(itResult, true);
01045             }
01046         }
01047 
01048         // Since here we require values to be unique, we will do nothing if the value already exists.
01049         if(mCompare(extractKey(pLowerBound->mValue), key)) // If the node is < the value (i.e. if value is >= the node)...
01050         {
01051             EASTL_VALIDATE_COMPARE(!mCompare(key, extractKey(pLowerBound->mValue))); // Validate that the compare function is sane.
01052             const iterator itResult(DoInsertKeyImpl(pParent, key, false));
01053             return pair<iterator, bool>(itResult, true);
01054         }
01055 
01056         // The item already exists (as found by the compare directly above), so return false.
01057         return pair<iterator, bool>(iterator(pLowerBound), false);
01058     }
01059 
01060 
01061     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01062     typename rbtree<K, V, C, A, E, bM, bU>::iterator
01063     rbtree<K, V, C, A, E, bM, bU>::DoInsertKey(const key_type& key, false_type) // false_type means keys are not unique.
01064     {
01065         // This is the pathway for insertion of non-unique keys (multimap and multiset, but not map and set).
01066         node_type* pCurrent  = (node_type*)mAnchor.mpNodeParent; // Start with the root node.
01067         node_type* pRangeEnd = (node_type*)&mAnchor;             // Set it to the container end for now.
01068         extract_key extractKey;
01069 
01070         while(pCurrent)
01071         {
01072             pRangeEnd = pCurrent;
01073 
01074             if(mCompare(key, extractKey(pCurrent->mValue)))
01075             {
01076                 EASTL_VALIDATE_COMPARE(!mCompare(extractKey(pCurrent->mValue), key)); // Validate that the compare function is sane.
01077                 pCurrent = (node_type*)pCurrent->mpNodeLeft;
01078             }
01079             else
01080                 pCurrent = (node_type*)pCurrent->mpNodeRight;
01081         }
01082 
01083         return DoInsertKeyImpl(pRangeEnd, key, false);
01084     }
01085 
01086 
01087     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01088     typename rbtree<K, V, C, A, E, bM, bU>::iterator
01089     rbtree<K, V, C, A, E, bM, bU>::DoInsertValue(iterator position, const value_type& value, true_type) // true_type means keys are unique.
01090     {
01091         // This is the pathway for insertion of unique keys (map and set, but not multimap and multiset).
01092         //
01093         // We follow the same approach as SGI STL/STLPort and use the position as
01094         // a forced insertion position for the value when possible.
01095         extract_key extractKey;
01096 
01097         if((position.mpNode != mAnchor.mpNodeRight) && (position.mpNode != &mAnchor)) // If the user specified a specific insertion position...
01098         {
01099             iterator itNext(position);
01100             ++itNext;
01101 
01102             // To consider: Change this so that 'position' specifies the position after
01103             // where the insertion goes and not the position before where the insertion goes.
01104             // Doing so would make this more in line with user expectations and with LWG #233.
01105             const bool bPositionLessThanValue = mCompare(extractKey(position.mpNode->mValue), extractKey(value));
01106 
01107             if(bPositionLessThanValue) // If (value > *position)...
01108             {
01109                 EASTL_VALIDATE_COMPARE(!mCompare(extractKey(value), extractKey(position.mpNode->mValue))); // Validate that the compare function is sane.
01110 
01111                 const bool bValueLessThanNext = mCompare(extractKey(value), extractKey(itNext.mpNode->mValue));
01112 
01113                 if(bValueLessThanNext) // if (value < *itNext)...
01114                 {
01115                     EASTL_VALIDATE_COMPARE(!mCompare(extractKey(itNext.mpNode->mValue), extractKey(value))); // Validate that the compare function is sane.
01116 
01117                     if(position.mpNode->mpNodeRight)
01118                         return DoInsertValueImpl(itNext.mpNode, value, true);
01119                     return DoInsertValueImpl(position.mpNode, value, false);
01120                 }
01121             }
01122 
01123             return DoInsertValue(value, has_unique_keys_type()).first;
01124         }
01125 
01126         if(mnSize && mCompare(extractKey(((node_type*)mAnchor.mpNodeRight)->mValue), extractKey(value)))
01127         {
01128             EASTL_VALIDATE_COMPARE(!mCompare(extractKey(value), extractKey(((node_type*)mAnchor.mpNodeRight)->mValue))); // Validate that the compare function is sane.
01129             return DoInsertValueImpl((node_type*)mAnchor.mpNodeRight, value, false);
01130         }
01131 
01132         return DoInsertValue(value, has_unique_keys_type()).first;
01133     }
01134 
01135 
01136     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01137     typename rbtree<K, V, C, A, E, bM, bU>::iterator
01138     rbtree<K, V, C, A, E, bM, bU>::DoInsertValue(iterator position, const value_type& value, false_type) // false_type means keys are not unique.
01139     {
01140         // This is the pathway for insertion of non-unique keys (multimap and multiset, but not map and set).
01141         //
01142         // We follow the same approach as SGI STL/STLPort and use the position as
01143         // a forced insertion position for the value when possible.
01144         extract_key extractKey;
01145 
01146         if((position.mpNode != mAnchor.mpNodeRight) && (position.mpNode != &mAnchor)) // If the user specified a specific insertion position...
01147         {
01148             iterator itNext(position);
01149             ++itNext;
01150 
01151             // To consider: Change this so that 'position' specifies the position after
01152             // where the insertion goes and not the position before where the insertion goes.
01153             // Doing so would make this more in line with user expectations and with LWG #233.
01154 
01155             if(!mCompare(extractKey(value), extractKey(position.mpNode->mValue)) && // If value >= *position &&
01156                !mCompare(extractKey(itNext.mpNode->mValue), extractKey(value)))     // if value <= *itNext...
01157             {
01158                 if(position.mpNode->mpNodeRight) // If there are any nodes to the right... [this expression will always be true as long as we aren't at the end()]
01159                     return DoInsertValueImpl(itNext.mpNode, value, true); // Specifically insert in front of (to the left of) itNext (and thus after 'position').
01160                 return DoInsertValueImpl(position.mpNode, value, false);
01161             }
01162 
01163             return DoInsertValue(value, has_unique_keys_type()); // If the above specified hint was not useful, then we do a regular insertion.
01164         }
01165 
01166         // This pathway shouldn't be commonly executed, as the user shouldn't be calling
01167         // this hinted version of insert if the user isn't providing a useful hint.
01168 
01169         if(mnSize && !mCompare(extractKey(value), extractKey(((node_type*)mAnchor.mpNodeRight)->mValue))) // If we are non-empty and the value is >= the last node...
01170             return DoInsertValueImpl((node_type*)mAnchor.mpNodeRight, value, false); // Insert after the last node (doesn't matter if we force left or not).
01171 
01172         return DoInsertValue(value, has_unique_keys_type()); // We are empty or we are inserting at the end.
01173     }
01174 
01175 
01176     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01177     typename rbtree<K, V, C, A, E, bM, bU>::iterator
01178     rbtree<K, V, C, A, E, bM, bU>::DoInsertKey(iterator position, const key_type& key, true_type) // true_type means keys are unique.
01179     {
01180         // This is the pathway for insertion of unique keys (map and set, but not multimap and multiset).
01181         //
01182         // We follow the same approach as SGI STL/STLPort and use the position as
01183         // a forced insertion position for the value when possible.
01184         extract_key extractKey;
01185 
01186         if((position.mpNode != mAnchor.mpNodeRight) && (position.mpNode != &mAnchor)) // If the user specified a specific insertion position...
01187         {
01188             iterator itNext(position);
01189             ++itNext;
01190 
01191             // To consider: Change this so that 'position' specifies the position after
01192             // where the insertion goes and not the position before where the insertion goes.
01193             // Doing so would make this more in line with user expectations and with LWG #233.
01194             const bool bPositionLessThanValue = mCompare(extractKey(position.mpNode->mValue), key);
01195 
01196             if(bPositionLessThanValue) // If (value > *position)...
01197             {
01198                 EASTL_VALIDATE_COMPARE(!mCompare(key, extractKey(position.mpNode->mValue))); // Validate that the compare function is sane.
01199 
01200                 const bool bValueLessThanNext = mCompare(key, extractKey(itNext.mpNode->mValue));
01201 
01202                 if(bValueLessThanNext) // If value < *itNext...
01203                 {
01204                     EASTL_VALIDATE_COMPARE(!mCompare(extractKey(itNext.mpNode->mValue), key)); // Validate that the compare function is sane.
01205 
01206                     if(position.mpNode->mpNodeRight)
01207                         return DoInsertKeyImpl(itNext.mpNode, key, true);
01208                     return DoInsertKeyImpl(position.mpNode, key, false);
01209                 }
01210             }
01211 
01212             return DoInsertKey(key, has_unique_keys_type()).first;
01213         }
01214 
01215         if(mnSize && mCompare(extractKey(((node_type*)mAnchor.mpNodeRight)->mValue), key))
01216         {
01217             EASTL_VALIDATE_COMPARE(!mCompare(key, extractKey(((node_type*)mAnchor.mpNodeRight)->mValue))); // Validate that the compare function is sane.
01218             return DoInsertKeyImpl((node_type*)mAnchor.mpNodeRight, key, false);
01219         }
01220 
01221         return DoInsertKey(key, has_unique_keys_type()).first;
01222     }
01223 
01224 
01225     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01226     typename rbtree<K, V, C, A, E, bM, bU>::iterator
01227     rbtree<K, V, C, A, E, bM, bU>::DoInsertKey(iterator position, const key_type& key, false_type) // false_type means keys are not unique.
01228     {
01229         // This is the pathway for insertion of non-unique keys (multimap and multiset, but not map and set).
01230         //
01231         // We follow the same approach as SGI STL/STLPort and use the position as
01232         // a forced insertion position for the value when possible.
01233         extract_key extractKey;
01234 
01235         if((position.mpNode != mAnchor.mpNodeRight) && (position.mpNode != &mAnchor)) // If the user specified a specific insertion position...
01236         {
01237             iterator itNext(position);
01238             ++itNext;
01239 
01240             // To consider: Change this so that 'position' specifies the position after
01241             // where the insertion goes and not the position before where the insertion goes.
01242             // Doing so would make this more in line with user expectations and with LWG #233.
01243             if(!mCompare(key, extractKey(position.mpNode->mValue)) && // If value >= *position &&
01244                !mCompare(extractKey(itNext.mpNode->mValue), key))     // if value <= *itNext...
01245             {
01246                 if(position.mpNode->mpNodeRight) // If there are any nodes to the right... [this expression will always be true as long as we aren't at the end()]
01247                     return DoInsertKeyImpl(itNext.mpNode, key, true); // Specifically insert in front of (to the left of) itNext (and thus after 'position').
01248                 return DoInsertKeyImpl(position.mpNode, key, false);
01249             }
01250 
01251             return DoInsertKey(key, has_unique_keys_type()); // If the above specified hint was not useful, then we do a regular insertion.
01252         }
01253 
01254         // This pathway shouldn't be commonly executed, as the user shouldn't be calling
01255         // this hinted version of insert if the user isn't providing a useful hint.
01256         if(mnSize && !mCompare(key, extractKey(((node_type*)mAnchor.mpNodeRight)->mValue))) // If we are non-empty and the value is >= the last node...
01257             return DoInsertKeyImpl((node_type*)mAnchor.mpNodeRight, key, false); // Insert after the last node (doesn't matter if we force left or not).
01258 
01259         return DoInsertKey(key, has_unique_keys_type()); // We are empty or we are inserting at the end.
01260     }
01261 
01262 
01263     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01264     typename rbtree<K, V, C, A, E, bM, bU>::iterator
01265     rbtree<K, V, C, A, E, bM, bU>::DoInsertValueImpl(node_type* pNodeParent, const value_type& value, bool bForceToLeft)
01266     {
01267         RBTreeSide side;
01268         extract_key extractKey;
01269 
01270         // The reason we may want to have bForceToLeft == true is that pNodeParent->mValue and value may be equal.
01271         // In that case it doesn't matter what side we insert on, except that the C++ LWG #233 improvement report
01272         // suggests that we should use the insert hint position to force an ordering. So that's what we do.
01273         if(bForceToLeft || (pNodeParent == &mAnchor) || mCompare(extractKey(value), extractKey(pNodeParent->mValue)))
01274             side = kRBTreeSideLeft;
01275         else
01276             side = kRBTreeSideRight;
01277 
01278         node_type* const pNodeNew = DoCreateNode(value); // Note that pNodeNew->mpLeft, mpRight, mpParent, will be uninitialized.
01279         RBTreeInsert(pNodeNew, pNodeParent, &mAnchor, side);
01280         mnSize++;
01281 
01282         return iterator(pNodeNew);
01283     }
01284 
01285 
01286     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01287     typename rbtree<K, V, C, A, E, bM, bU>::iterator
01288     rbtree<K, V, C, A, E, bM, bU>::DoInsertKeyImpl(node_type* pNodeParent, const key_type& key, bool bForceToLeft)
01289     {
01290         RBTreeSide side;
01291         extract_key extractKey;
01292 
01293         // The reason we may want to have bForceToLeft == true is that pNodeParent->mValue and value may be equal.
01294         // In that case it doesn't matter what side we insert on, except that the C++ LWG #233 improvement report
01295         // suggests that we should use the insert hint position to force an ordering. So that's what we do.
01296         if(bForceToLeft || (pNodeParent == &mAnchor) || mCompare(key, extractKey(pNodeParent->mValue)))
01297             side = kRBTreeSideLeft;
01298         else
01299             side = kRBTreeSideRight;
01300 
01301         node_type* const pNodeNew = DoCreateNodeFromKey(key); // Note that pNodeNew->mpLeft, mpRight, mpParent, will be uninitialized.
01302         RBTreeInsert(pNodeNew, pNodeParent, &mAnchor, side);
01303         mnSize++;
01304 
01305         return iterator(pNodeNew);
01306     }
01307 
01308 
01309     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01310     template <typename InputIterator>
01311     void rbtree<K, V, C, A, E, bM, bU>::insert(InputIterator first, InputIterator last)
01312     {
01313         for( ; first != last; ++first)
01314             DoInsertValue(*first, has_unique_keys_type()); // Or maybe we should call 'insert(end(), *first)' instead. If the first-last range was sorted then this might make some sense.
01315     }
01316 
01317 
01318     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01319     inline void rbtree<K, V, C, A, E, bM, bU>::clear()
01320     {
01321         // Erase the entire tree. DoNukeSubtree is not a
01322         // conventional erase function, as it does no rebalancing.
01323         DoNukeSubtree((node_type*)mAnchor.mpNodeParent);
01324         reset();
01325     }
01326 
01327 
01328     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01329     inline void rbtree<K, V, C, A, E, bM, bU>::reset()
01330     {
01331         // The reset function is a special extension function which unilaterally
01332         // resets the container to an empty state without freeing the memory of
01333         // the contained objects. This is useful for very quickly tearing down a
01334         // container built into scratch memory.
01335         mAnchor.mpNodeRight  = &mAnchor;
01336         mAnchor.mpNodeLeft   = &mAnchor;
01337         mAnchor.mpNodeParent = NULL;
01338         mAnchor.mColor       = kRBTreeColorRed;
01339         mnSize               = 0;
01340     }
01341 
01342 
01343     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01344     inline typename rbtree<K, V, C, A, E, bM, bU>::iterator
01345     rbtree<K, V, C, A, E, bM, bU>::erase(iterator position)
01346     {
01347         const iterator iErase(position);
01348         --mnSize; // Interleave this between the two references to itNext. We expect no exceptions to occur during the code below.
01349         ++position;
01350         RBTreeErase(iErase.mpNode, &mAnchor);
01351         DoFreeNode(iErase.mpNode);
01352         return position;
01353     }
01354 
01355 
01356     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01357     typename rbtree<K, V, C, A, E, bM, bU>::iterator
01358     rbtree<K, V, C, A, E, bM, bU>::erase(iterator first, iterator last)
01359     {
01360         // We expect that if the user means to clear the container, they will call clear.
01361         if(EASTL_LIKELY((first.mpNode != mAnchor.mpNodeLeft) || (last.mpNode != &mAnchor))) // If (first != begin or last != end) ...
01362         {
01363             // Basic implementation:
01364             while(first != last)
01365                 first = erase(first);
01366             return first;
01367 
01368             // Inlined implementation:
01369             //size_type n = 0;
01370             //while(first != last)
01371             //{
01372             //    const iterator itErase(first);
01373             //    ++n;
01374             //    ++first;
01375             //    RBTreeErase(itErase.mpNode, &mAnchor);
01376             //    DoFreeNode(itErase.mpNode);
01377             //}
01378             //mnSize -= n;
01379             //return first;
01380         }
01381 
01382         clear();
01383         return iterator((node_type*)&mAnchor); // Same as: return end();
01384     }
01385 
01386 
01387     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01388     inline typename rbtree<K, V, C, A, E, bM, bU>::reverse_iterator
01389     rbtree<K, V, C, A, E, bM, bU>::erase(reverse_iterator position)
01390     {
01391         return reverse_iterator(erase((++position).base()));
01392     }
01393 
01394 
01395     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01396     typename rbtree<K, V, C, A, E, bM, bU>::reverse_iterator
01397     rbtree<K, V, C, A, E, bM, bU>::erase(reverse_iterator first, reverse_iterator last)
01398     {
01399         // Version which erases in order from first to last.
01400         // difference_type i(first.base() - last.base());
01401         // while(i--)
01402         //     first = erase(first);
01403         // return first;
01404 
01405         // Version which erases in order from last to first, but is slightly more efficient:
01406         return reverse_iterator(erase((++last).base(), (++first).base()));
01407     }
01408 
01409 
01410     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01411     inline void rbtree<K, V, C, A, E, bM, bU>::erase(const key_type* first, const key_type* last)
01412     {
01413         // We have no choice but to run a loop like this, as the first/last range could
01414         // have values that are discontiguously located in the tree. And some may not
01415         // even be in the tree.
01416         while(first != last)
01417             erase(*first++);
01418     }
01419 
01420 
01421     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01422     typename rbtree<K, V, C, A, E, bM, bU>::iterator
01423     rbtree<K, V, C, A, E, bM, bU>::find(const key_type& key)
01424     {
01425         // To consider: Implement this instead via calling lower_bound and
01426         // inspecting the result. The following is an implementation of this:
01427         //    const iterator it(lower_bound(key));
01428         //    return ((it.mpNode == &mAnchor) || mCompare(key, extractKey(it.mpNode->mValue))) ? iterator(&mAnchor) : it;
01429         // We don't currently implement the above because in practice people tend to call
01430         // find a lot with trees, but very uncommonly call lower_bound.
01431         extract_key extractKey;
01432 
01433         node_type* pCurrent  = (node_type*)mAnchor.mpNodeParent; // Start with the root node.
01434         node_type* pRangeEnd = (node_type*)&mAnchor;             // Set it to the container end for now.
01435 
01436         while(EASTL_LIKELY(pCurrent)) // Do a walk down the tree.
01437         {
01438             if(EASTL_LIKELY(!mCompare(extractKey(pCurrent->mValue), key))) // If pCurrent is >= key...
01439             {
01440                 pRangeEnd = pCurrent;
01441                 pCurrent  = (node_type*)pCurrent->mpNodeLeft;
01442             }
01443             else
01444             {
01445                 EASTL_VALIDATE_COMPARE(!mCompare(key, extractKey(pCurrent->mValue))); // Validate that the compare function is sane.
01446                 pCurrent  = (node_type*)pCurrent->mpNodeRight;
01447             }
01448         }
01449 
01450         if(EASTL_LIKELY((pRangeEnd != &mAnchor) && !mCompare(key, extractKey(pRangeEnd->mValue))))
01451             return iterator(pRangeEnd);
01452         return iterator((node_type*)&mAnchor);
01453     }
01454 
01455 
01456     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01457     inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator
01458     rbtree<K, V, C, A, E, bM, bU>::find(const key_type& key) const
01459     {
01460         typedef rbtree<K, V, C, A, E, bM, bU> rbtree_type;
01461         return const_iterator(const_cast<rbtree_type*>(this)->find(key));
01462     }
01463 
01464 
01465     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01466     template <typename U, typename Compare2>
01467     typename rbtree<K, V, C, A, E, bM, bU>::iterator
01468     rbtree<K, V, C, A, E, bM, bU>::find_as(const U& u, Compare2 compare2)
01469     {
01470         extract_key extractKey;
01471 
01472         node_type* pCurrent  = (node_type*)mAnchor.mpNodeParent; // Start with the root node.
01473         node_type* pRangeEnd = (node_type*)&mAnchor;             // Set it to the container end for now.
01474 
01475         while(EASTL_LIKELY(pCurrent)) // Do a walk down the tree.
01476         {
01477             if(EASTL_LIKELY(!compare2(extractKey(pCurrent->mValue), u))) // If pCurrent is >= u...
01478             {
01479                 pRangeEnd = pCurrent;
01480                 pCurrent  = (node_type*)pCurrent->mpNodeLeft;
01481             }
01482             else
01483             {
01484                 EASTL_VALIDATE_COMPARE(!compare2(u, extractKey(pCurrent->mValue))); // Validate that the compare function is sane.
01485                 pCurrent  = (node_type*)pCurrent->mpNodeRight;
01486             }
01487         }
01488 
01489         if(EASTL_LIKELY((pRangeEnd != &mAnchor) && !compare2(u, extractKey(pRangeEnd->mValue))))
01490             return iterator(pRangeEnd);
01491         return iterator((node_type*)&mAnchor);
01492     }
01493 
01494 
01495     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01496     template <typename U, typename Compare2>
01497     inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator
01498     rbtree<K, V, C, A, E, bM, bU>::find_as(const U& u, Compare2 compare2) const
01499     {
01500         typedef rbtree<K, V, C, A, E, bM, bU> rbtree_type;
01501         return const_iterator(const_cast<rbtree_type*>(this)->find_as(u, compare2));
01502     }
01503 
01504 
01505     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01506     typename rbtree<K, V, C, A, E, bM, bU>::iterator
01507     rbtree<K, V, C, A, E, bM, bU>::lower_bound(const key_type& key)
01508     {
01509         extract_key extractKey;
01510 
01511         node_type* pCurrent  = (node_type*)mAnchor.mpNodeParent; // Start with the root node.
01512         node_type* pRangeEnd = (node_type*)&mAnchor;             // Set it to the container end for now.
01513 
01514         while(EASTL_LIKELY(pCurrent)) // Do a walk down the tree.
01515         {
01516             if(EASTL_LIKELY(!mCompare(extractKey(pCurrent->mValue), key))) // If pCurrent is >= key...
01517             {
01518                 pRangeEnd = pCurrent;
01519                 pCurrent  = (node_type*)pCurrent->mpNodeLeft;
01520             }
01521             else
01522             {
01523                 EASTL_VALIDATE_COMPARE(!mCompare(key, extractKey(pCurrent->mValue))); // Validate that the compare function is sane.
01524                 pCurrent  = (node_type*)pCurrent->mpNodeRight;
01525             }
01526         }
01527 
01528         return iterator(pRangeEnd);
01529     }
01530 
01531 
01532     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01533     inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator
01534     rbtree<K, V, C, A, E, bM, bU>::lower_bound(const key_type& key) const
01535     {
01536         typedef rbtree<K, V, C, A, E, bM, bU> rbtree_type;
01537         return const_iterator(const_cast<rbtree_type*>(this)->lower_bound(key));
01538     }
01539 
01540 
01541     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01542     typename rbtree<K, V, C, A, E, bM, bU>::iterator
01543     rbtree<K, V, C, A, E, bM, bU>::upper_bound(const key_type& key)
01544     {
01545         extract_key extractKey;
01546 
01547         node_type* pCurrent  = (node_type*)mAnchor.mpNodeParent; // Start with the root node.
01548         node_type* pRangeEnd = (node_type*)&mAnchor;             // Set it to the container end for now.
01549 
01550         while(EASTL_LIKELY(pCurrent)) // Do a walk down the tree.
01551         {
01552             if(EASTL_LIKELY(mCompare(key, extractKey(pCurrent->mValue)))) // If key is < pCurrent...
01553             {
01554                 EASTL_VALIDATE_COMPARE(!mCompare(extractKey(pCurrent->mValue), key)); // Validate that the compare function is sane.
01555                 pRangeEnd = pCurrent;
01556                 pCurrent  = (node_type*)pCurrent->mpNodeLeft;
01557             }
01558             else
01559                 pCurrent  = (node_type*)pCurrent->mpNodeRight;
01560         }
01561 
01562         return iterator(pRangeEnd);
01563     }
01564 
01565 
01566     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01567     inline typename rbtree<K, V, C, A, E, bM, bU>::const_iterator
01568     rbtree<K, V, C, A, E, bM, bU>::upper_bound(const key_type& key) const
01569     {
01570         typedef rbtree<K, V, C, A, E, bM, bU> rbtree_type;
01571         return const_iterator(const_cast<rbtree_type*>(this)->upper_bound(key));
01572     }
01573 
01574 
01575     // To do: Move this validate function entirely to a template-less implementation.
01576     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01577     bool rbtree<K, V, C, A, E, bM, bU>::validate() const
01578     {
01579         // Red-black trees have the following canonical properties which we validate here:
01580         //   1 Every node is either red or black.
01581         //   2 Every leaf (NULL) is black by defintion. Any number of black nodes may appear in a sequence.
01582         //   3 If a node is red, then both its children are black. Thus, on any path from
01583         //     the root to a leaf, red nodes must not be adjacent.
01584         //   4 Every simple path from a node to a descendant leaf contains the same number of black nodes.
01585         //   5 The mnSize member of the tree must equal the number of nodes in the tree.
01586         //   6 The tree is sorted as per a conventional binary tree.
01587         //   7 The comparison function is sane; it obeys strict weak ordering. If mCompare(a,b) is true, then mCompare(b,a) must be false. Both cannot be true.
01588 
01589         extract_key extractKey;
01590 
01591         if(mnSize)
01592         {
01593             // Verify basic integrity.
01594             //if(!mAnchor.mpNodeParent || (mAnchor.mpNodeLeft == mAnchor.mpNodeRight))
01595             //    return false;             // Fix this for case of empty tree.
01596 
01597             if(mAnchor.mpNodeLeft != RBTreeGetMinChild(mAnchor.mpNodeParent))
01598                 return false;
01599 
01600             if(mAnchor.mpNodeRight != RBTreeGetMaxChild(mAnchor.mpNodeParent))
01601                 return false;
01602 
01603             const size_t nBlackCount   = RBTreeGetBlackCount(mAnchor.mpNodeParent, mAnchor.mpNodeLeft);
01604             size_type    nIteratedSize = 0;
01605 
01606             for(const_iterator it = begin(); it != end(); ++it, ++nIteratedSize)
01607             {
01608                 const node_type* const pNode      = (const node_type*)it.mpNode;
01609                 const node_type* const pNodeRight = (const node_type*)pNode->mpNodeRight;
01610                 const node_type* const pNodeLeft  = (const node_type*)pNode->mpNodeLeft;
01611 
01612                 // Verify #7 above.
01613                 if(pNodeRight && mCompare(extractKey(pNodeRight->mValue), extractKey(pNode->mValue)) && mCompare(extractKey(pNode->mValue), extractKey(pNodeRight->mValue))) // Validate that the compare function is sane.
01614                     return false;
01615 
01616                 // Verify #7 above.
01617                 if(pNodeLeft && mCompare(extractKey(pNodeLeft->mValue), extractKey(pNode->mValue)) && mCompare(extractKey(pNode->mValue), extractKey(pNodeLeft->mValue))) // Validate that the compare function is sane.
01618                     return false;
01619 
01620                 // Verify item #1 above.
01621                 if((pNode->mColor != kRBTreeColorRed) && (pNode->mColor != kRBTreeColorBlack))
01622                     return false;
01623 
01624                 // Verify item #3 above.
01625                 if(pNode->mColor == kRBTreeColorRed)
01626                 {
01627                     if((pNodeRight && (pNodeRight->mColor == kRBTreeColorRed)) ||
01628                        (pNodeLeft  && (pNodeLeft->mColor  == kRBTreeColorRed)))
01629                         return false;
01630                 }
01631 
01632                 // Verify item #6 above.
01633                 if(pNodeRight && mCompare(extractKey(pNodeRight->mValue), extractKey(pNode->mValue)))
01634                     return false;
01635 
01636                 if(pNodeLeft && mCompare(extractKey(pNode->mValue), extractKey(pNodeLeft->mValue)))
01637                     return false;
01638 
01639                 if(!pNodeRight && !pNodeLeft) // If we are at a bottom node of the tree...
01640                 {
01641                     // Verify item #4 above.
01642                     if(RBTreeGetBlackCount(mAnchor.mpNodeParent, pNode) != nBlackCount)
01643                         return false;
01644                 }
01645             }
01646 
01647             // Verify item #5 above.
01648             if(nIteratedSize != mnSize)
01649                 return false;
01650 
01651             return true;
01652         }
01653         else
01654         {
01655             if((mAnchor.mpNodeLeft != &mAnchor) || (mAnchor.mpNodeRight != &mAnchor))
01656                 return false;
01657         }
01658 
01659         return true;
01660     }
01661 
01662 
01663     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01664     inline int rbtree<K, V, C, A, E, bM, bU>::validate_iterator(const_iterator i) const
01665     {
01666         // To do: Come up with a more efficient mechanism of doing this.
01667 
01668         for(const_iterator temp = begin(), tempEnd = end(); temp != tempEnd; ++temp)
01669         {
01670             if(temp == i)
01671                 return (isf_valid | isf_current | isf_can_dereference);
01672         }
01673 
01674         if(i == end())
01675             return (isf_valid | isf_current);
01676 
01677         return isf_none;
01678     }
01679 
01680 
01681     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01682     inline typename rbtree<K, V, C, A, E, bM, bU>::node_type*
01683     rbtree<K, V, C, A, E, bM, bU>::DoAllocateNode()
01684     {
01685         return (node_type*)allocate_memory(mAllocator, sizeof(node_type), kValueAlignment, kValueAlignmentOffset);
01686     }
01687 
01688 
01689     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01690     inline void rbtree<K, V, C, A, E, bM, bU>::DoFreeNode(node_type* pNode)
01691     {
01692         pNode->~node_type();
01693         EASTLFree(mAllocator, pNode, sizeof(node_type));
01694     }
01695 
01696 
01697     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01698     typename rbtree<K, V, C, A, E, bM, bU>::node_type*
01699     rbtree<K, V, C, A, E, bM, bU>::DoCreateNodeFromKey(const key_type& key)
01700     {
01701         // Note that this function intentionally leaves the node pointers uninitialized.
01702         // The caller would otherwise just turn right around and modify them, so there's
01703         // no point in us initializing them to anything (except in a debug build).
01704         node_type* const pNode = DoAllocateNode();
01705 
01706         #if EASTL_EXCEPTIONS_ENABLED
01707             try
01708             {
01709         #endif
01710                 ::new(&pNode->mValue) value_type(key);
01711 
01712         #if EASTL_EXCEPTIONS_ENABLED
01713             }
01714             catch(...)
01715             {
01716                 DoFreeNode(pNode);
01717                 throw;
01718             }
01719         #endif
01720 
01721         #if EASTL_DEBUG
01722             pNode->mpNodeRight  = NULL;
01723             pNode->mpNodeLeft   = NULL;
01724             pNode->mpNodeParent = NULL;
01725             pNode->mColor       = kRBTreeColorBlack;
01726         #endif
01727 
01728         return pNode;
01729     }
01730 
01731 
01732     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01733     typename rbtree<K, V, C, A, E, bM, bU>::node_type*
01734     rbtree<K, V, C, A, E, bM, bU>::DoCreateNode(const value_type& value)
01735     {
01736         // Note that this function intentionally leaves the node pointers uninitialized.
01737         // The caller would otherwise just turn right around and modify them, so there's
01738         // no point in us initializing them to anything (except in a debug build).
01739         node_type* const pNode = DoAllocateNode();
01740 
01741         #if EASTL_EXCEPTIONS_ENABLED
01742             try
01743             {
01744         #endif
01745                 ::new(&pNode->mValue) value_type(value);
01746         #if EASTL_EXCEPTIONS_ENABLED
01747             }
01748             catch(...)
01749             {
01750                 DoFreeNode(pNode);
01751                 throw;
01752             }
01753         #endif
01754 
01755         #if EASTL_DEBUG
01756             pNode->mpNodeRight  = NULL;
01757             pNode->mpNodeLeft   = NULL;
01758             pNode->mpNodeParent = NULL;
01759             pNode->mColor       = kRBTreeColorBlack;
01760         #endif
01761 
01762         return pNode;
01763     }
01764 
01765 
01766     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01767     typename rbtree<K, V, C, A, E, bM, bU>::node_type*
01768     rbtree<K, V, C, A, E, bM, bU>::DoCreateNode(const node_type* pNodeSource, node_type* pNodeParent)
01769     {
01770         node_type* const pNode = DoCreateNode(pNodeSource->mValue);
01771 
01772         pNode->mpNodeRight  = NULL;
01773         pNode->mpNodeLeft   = NULL;
01774         pNode->mpNodeParent = pNodeParent;
01775         pNode->mColor       = pNodeSource->mColor;
01776 
01777         return pNode;
01778     }
01779 
01780 
01781     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01782     typename rbtree<K, V, C, A, E, bM, bU>::node_type*
01783     rbtree<K, V, C, A, E, bM, bU>::DoCopySubtree(const node_type* pNodeSource, node_type* pNodeDest)
01784     {
01785         node_type* const pNewNodeRoot = DoCreateNode(pNodeSource, pNodeDest);
01786 
01787         #if EASTL_EXCEPTIONS_ENABLED
01788             try
01789             {
01790         #endif
01791                 // Copy the right side of the tree recursively.
01792                 if(pNodeSource->mpNodeRight)
01793                     pNewNodeRoot->mpNodeRight = DoCopySubtree((const node_type*)pNodeSource->mpNodeRight, pNewNodeRoot);
01794 
01795                 node_type* pNewNodeLeft;
01796 
01797                 for(pNodeSource = (node_type*)pNodeSource->mpNodeLeft, pNodeDest = pNewNodeRoot;
01798                     pNodeSource;
01799                     pNodeSource = (node_type*)pNodeSource->mpNodeLeft, pNodeDest = pNewNodeLeft)
01800                 {
01801                     pNewNodeLeft = DoCreateNode(pNodeSource, pNodeDest);
01802 
01803                     pNodeDest->mpNodeLeft = pNewNodeLeft;
01804 
01805                     // Copy the right side of the tree recursively.
01806                     if(pNodeSource->mpNodeRight)
01807                         pNewNodeLeft->mpNodeRight = DoCopySubtree((const node_type*)pNodeSource->mpNodeRight, pNewNodeLeft);
01808                 }
01809         #if EASTL_EXCEPTIONS_ENABLED
01810             }
01811             catch(...)
01812             {
01813                 DoNukeSubtree(pNewNodeRoot);
01814                 throw;
01815             }
01816         #endif
01817 
01818         return pNewNodeRoot;
01819     }
01820 
01821 
01822     template <typename K, typename V, typename C, typename A, typename E, bool bM, bool bU>
01823     void rbtree<K, V, C, A, E, bM, bU>::DoNukeSubtree(node_type* pNode)
01824     {
01825         while(pNode) // Recursively traverse the tree and destroy items as we go.
01826         {
01827             DoNukeSubtree((node_type*)pNode->mpNodeRight);
01828 
01829             node_type* const pNodeLeft = (node_type*)pNode->mpNodeLeft;
01830             DoFreeNode(pNode);
01831             pNode = pNodeLeft;
01832         }
01833     }
01834 
01835 
01836 
01838     // global operators
01840 
01841     template <typename K, typename V, typename A, typename C, typename E, bool bM, bool bU>
01842     inline bool operator==(const rbtree<K, V, C, A, E, bM, bU>& a, const rbtree<K, V, C, A, E, bM, bU>& b)
01843     {
01844         return (a.size() == b.size()) && eastl::equal(a.begin(), a.end(), b.begin());
01845     }
01846 
01847 
01848     // Note that in operator< we do comparisons based on the tree value_type with operator<() of the
01849     // value_type instead of the tree's Compare function. For set/multiset, the value_type is T, while
01850     // for map/multimap the value_type is a pair<Key, T>. operator< for pair can be seen by looking
01851     // utility.h, but it basically is uses the operator< for pair.first and pair.second. The C++ standard
01852     // appears to require this behaviour, whether intentionally or not. If anything, a good reason to do
01853     // this is for consistency. A map and a vector that contain the same items should compare the same.
01854     template <typename K, typename V, typename A, typename C, typename E, bool bM, bool bU>
01855     inline bool operator<(const rbtree<K, V, C, A, E, bM, bU>& a, const rbtree<K, V, C, A, E, bM, bU>& b)
01856     {
01857         return eastl::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
01858     }
01859 
01860 
01861     template <typename K, typename V, typename A, typename C, typename E, bool bM, bool bU>
01862     inline bool operator!=(const rbtree<K, V, C, A, E, bM, bU>& a, const rbtree<K, V, C, A, E, bM, bU>& b)
01863     {
01864         return !(a == b);
01865     }
01866 
01867 
01868     template <typename K, typename V, typename A, typename C, typename E, bool bM, bool bU>
01869     inline bool operator>(const rbtree<K, V, C, A, E, bM, bU>& a, const rbtree<K, V, C, A, E, bM, bU>& b)
01870     {
01871         return b < a;
01872     }
01873 
01874 
01875     template <typename K, typename V, typename A, typename C, typename E, bool bM, bool bU>
01876     inline bool operator<=(const rbtree<K, V, C, A, E, bM, bU>& a, const rbtree<K, V, C, A, E, bM, bU>& b)
01877     {
01878         return !(b < a);
01879     }
01880 
01881 
01882     template <typename K, typename V, typename A, typename C, typename E, bool bM, bool bU>
01883     inline bool operator>=(const rbtree<K, V, C, A, E, bM, bU>& a, const rbtree<K, V, C, A, E, bM, bU>& b)
01884     {
01885         return !(a < b);
01886     }
01887 
01888 
01889     template <typename K, typename V, typename A, typename C, typename E, bool bM, bool bU>
01890     inline void swap(rbtree<K, V, C, A, E, bM, bU>& a, rbtree<K, V, C, A, E, bM, bU>& b)
01891     {
01892         a.swap(b);
01893     }
01894 
01895 
01896 } // namespace eastl
01897 
01898 
01899 #ifdef _MSC_VER
01900     #pragma warning(pop)
01901 #endif
01902 
01903 
01904 #endif // Header include guard
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines