Main Page Modules Class Hierarchy Data Structures File List Data Fields Globals Related Pages

# oscl_tree.h

Go to the documentation of this file.

    00001 // -*- c++ -*-
    00002 // = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
    00003
    00004 //                     O S C L _ T R E E
    00005
    00006 // = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
    00007
    00018 #ifndef OSCL_TREE_H_INCLUDED
    00019 #define OSCL_TREE_H_INCLUDED
    00020
    00021 #ifndef OSCL_DEFALLOC_H_INCLUDED
    00022 #include "oscl_defalloc.h"
    00023 #endif
    00024
    00025 #ifndef OSCL_BASE_H_INCLUDED
    00026 #include "oscl_base.h"
    00027 #endif
    00028
    00029 #define OSCL_DISABLE_WARNING_TRUNCATE_DEBUG_MESSAGE
    00030 #include "osclconfig_compiler_warnings.h"
    00031
    00032 template <class T1, class T2>
    00033 struct Oscl_Pair
    00034 {
    00035     T1 first;
    00036     T2 second;
    00037     Oscl_Pair() : first(T1()), second(T2()) {}
    00038     Oscl_Pair(const T1& a, const T2& b) : first(a), second(b) {}
    00039 };
    00040
    00041
    00042 struct Oscl_Rb_Tree_Node_Base
    00043 {
    00044     typedef Oscl_Rb_Tree_Node_Base* base_link_type;
    00045     typedef enum RedBl {red, black} color_type;
    00046
    00047     color_type color;
    00048     base_link_type parent;
    00049     base_link_type left;
    00050     base_link_type right;
    00051
    00052     static base_link_type minimum(base_link_type x)
    00053     {
    00054         if (x)
    00055         {
    00056             while (x->left != 0) x = x->left;
    00057         }
    00058         return x;
    00059     }
    00060     static base_link_type maximum(base_link_type x)
    00061     {
    00062         if (x)
    00063         {
    00064             while (x->right != 0) x = x->right;
    00065         }
    00066         return x;
    00067     }
    00068 };
    00069
    00070 template <class Value>
    00071 struct Oscl_Rb_Tree_Node : public Oscl_Rb_Tree_Node_Base
    00072 {
    00073     typedef Value value_type;
    00074     typedef Oscl_Rb_Tree_Node<Value>* link_type;
    00075     value_type value;
    00076 };
    00077
    00078
    00079 template <class Value>
    00080 struct Oscl_Rb_Tree_Iterator
    00081 {
    00082     typedef Value value_type;
    00083     typedef value_type& reference;
    00084     typedef value_type* pointer;
    00085     typedef Oscl_Rb_Tree_Iterator<Value> iterator;
    00086     typedef Oscl_Rb_Tree_Iterator<Value> self;
    00087     typedef Oscl_Rb_Tree_Node_Base* base_link_type;
    00088     typedef Oscl_Rb_Tree_Node<Value>* link_type;
    00089
    00090     base_link_type node;
    00091
    00092     Oscl_Rb_Tree_Iterator() {}
    00093     Oscl_Rb_Tree_Iterator(link_type x)
    00094     {
    00095         node = x;
    00096     }
    00097     Oscl_Rb_Tree_Iterator(const iterator& it)
    00098     {
    00099         node = it.node;
    00100     }
    00101
    00102     reference operator*() const
    00103     {
    00104         return link_type(node)->value;
    00105     }
    00106     pointer operator->() const
    00107     {
    00108         return &(operator*());
    00109     }
    00110
    00111     bool operator==(const self& x)
    00112     {
    00113         return node == x.node;
    00114     }
    00115
    00116     bool operator!=(const self& x)
    00117     {
    00118         return node != x.node;
    00119     }
    00120
    00121     self& operator++()
    00122     {
    00123         if (node->right != 0)
    00124         {
    00125             node = node->right;
    00126             while (node->left != 0)
    00127             {
    00128                 node = node->left;
    00129             }
    00130         }
    00131         else
    00132         {
    00133             base_link_type y = node->parent;
    00134             while (node == y->right)
    00135             {
    00136                 node = y;
    00137                 y = y->parent;
    00138             }
    00139             if (node->right != y) node = y;
    00140         }
    00141         return *this;
    00142     }
    00143
    00144     self operator++(int)
    00145     {
    00146         self tmp = *this;
    00147         ++*this;
    00148         return tmp;
    00149     }
    00150
    00151     self& operator--()
    00152     {
    00153         if (node->color == Oscl_Rb_Tree_Node_Base::red && (node->parent)->parent == node)
    00154         {
    00155             node = node->right;   // return rightmost
    00156         }
    00157         else if (node->left != 0)
    00158         {
    00159             base_link_type y = node->left;
    00160             while (y->right != 0)
    00161                 y = y->right;
    00162             node = y;
    00163         }
    00164         else
    00165         {
    00166             base_link_type y = node->parent;
    00167             while (node == y->left)
    00168             {
    00169                 node = y;
    00170                 y = y->parent;
    00171             }
    00172             node = y;
    00173         }
    00174         return *this;
    00175     }
    00176
    00177     self operator--(int)
    00178     {
    00179         self tmp = *this;
    00180         --*this;
    00181         return tmp;
    00182     }
    00183 };
    00184
    00185
    00186 template <class Value>
    00187 struct Oscl_Rb_Tree_Const_Iterator
    00188 {
    00189     typedef Value value_type;
    00190     typedef const value_type& reference;
    00191     typedef const value_type* pointer;
    00192     typedef Oscl_Rb_Tree_Const_Iterator<Value> const_iterator;
    00193     typedef Oscl_Rb_Tree_Const_Iterator<Value> self;
    00194     typedef Oscl_Rb_Tree_Node_Base* base_link_type;
    00195     typedef Oscl_Rb_Tree_Node<Value>* link_type;
    00196
    00197     base_link_type node;
    00198
    00199     Oscl_Rb_Tree_Const_Iterator() {}
    00200     Oscl_Rb_Tree_Const_Iterator(link_type x)
    00201     {
    00202         node = x;
    00203     }
    00204     Oscl_Rb_Tree_Const_Iterator(const const_iterator& it)
    00205     {
    00206         node = it.node;
    00207     }
    00208
    00209     reference operator*() const
    00210     {
    00211         return link_type(node)->value;
    00212     }
    00213     pointer operator->() const
    00214     {
    00215         return &(operator*());
    00216     }
    00217
    00218     bool operator==(const self& x)
    00219     {
    00220         return node == x.node;
    00221     }
    00222
    00223     bool operator!=(const self& x)
    00224     {
    00225         return node != x.node;
    00226     }
    00227
    00228     self& operator++()
    00229     {
    00230         if (node->right != 0)
    00231         {
    00232             node = node->right;
    00233             while (node->left != 0)
    00234             {
    00235                 node = node->left;
    00236             }
    00237         }
    00238         else
    00239         {
    00240             base_link_type y = node->parent;
    00241             while (node == y->right)
    00242             {
    00243                 node = y;
    00244                 y = y->parent;
    00245             }
    00246             if (node->right != y) node = y;
    00247         }
    00248         return *this;
    00249     }
    00250
    00251     self operator++(int)
    00252     {
    00253         self tmp = *this;
    00254         ++*this;
    00255         return tmp;
    00256     }
    00257
    00258     self& operator--()
    00259     {
    00260         if (node->color == Oscl_Rb_Tree_Node_Base::red && (node->parent)->parent == node)
    00261         {
    00262             node = node->right;   // return rightmost
    00263         }
    00264         else if (node->left != 0)
    00265         {
    00266             base_link_type y = node->left;
    00267             while (y->right != 0)
    00268                 y = y->right;
    00269             node = y;
    00270         }
    00271         else
    00272         {
    00273             base_link_type y = node->parent;
    00274             while (node == y->left)
    00275             {
    00276                 node = y;
    00277                 y = y->parent;
    00278             }
    00279             node = y;
    00280         }
    00281         return *this;
    00282     }
    00283
    00284     self operator--(int)
    00285     {
    00286         self tmp = *this;
    00287         --*this;
    00288         return tmp;
    00289     }
    00290 };
    00291
    00292
    00293 class Oscl_Rb_Tree_Base
    00294 {
    00295
    00296     public:
    00297         typedef Oscl_Rb_Tree_Node_Base::base_link_type base_link_type;
    00298
    00299         OSCL_IMPORT_REF void rotate_left(base_link_type x, base_link_type& root);
    00300         OSCL_IMPORT_REF void rotate_right(base_link_type x, base_link_type& root);
    00301         OSCL_IMPORT_REF void rebalance(base_link_type x, base_link_type& root);
    00302         OSCL_IMPORT_REF base_link_type rebalance_for_erase(base_link_type z,
    00303                 base_link_type& root,
    00304                 base_link_type& leftmost,
    00305                 base_link_type& rightmost);
    00306 };
    00307
    00308
    00309 template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
    00310 class Oscl_Rb_Tree : public Oscl_Rb_Tree_Base
    00311 {
    00312
    00313     public:
    00314         typedef Key key_type;
    00315         typedef Value value_type;
    00316         typedef value_type* pointer;
    00317         typedef const value_type* const_pointer;
    00318         typedef value_type& reference;
    00319         typedef const value_type& const_reference;
    00320         typedef typename Oscl_Rb_Tree_Node<Value>::link_type link_type;
    00321         typedef Oscl_Rb_Tree_Iterator<value_type> iterator;
    00322         typedef Oscl_Rb_Tree_Const_Iterator<value_type> const_iterator;
    00323         typedef uint32 size_type;
    00324         typedef int32 difference_type;
    00325     private:
    00326         typedef typename Oscl_Rb_Tree_Node<Value>::color_type color_type;
    00327         typedef Oscl_Rb_Tree_Node<Value> node_type;
    00328
    00329     private:
    00330         link_type header;
    00331         size_type node_count;
    00332         Compare key_compare;
    00333         Oscl_TAlloc<node_type, Alloc> node_allocator;
    00334
    00335     public:
    00336         Oscl_Rb_Tree(const Compare& comp = Compare())
    00337                 : node_count(0), key_compare(comp)
    00338         {
    00339             header = get_node();
    00340             header->color = Oscl_Rb_Tree_Node_Base::red;
    00341             leftmost() = header;
    00342             rightmost() = header;
    00343             root() = 0;
    00344         }
    00345
    00346         Oscl_Rb_Tree(const Oscl_Rb_Tree<Key, Value, KeyOfValue, Compare, Alloc>& x)
    00347                 : node_count(0), key_compare(x.key_compare)
    00348         {
    00349             header = get_node();
    00350             header->color = Oscl_Rb_Tree_Node_Base::red;
    00351             if (x.root() == 0)
    00352             {
    00353                 leftmost() = header;
    00354                 rightmost() = header;
    00355                 root() = 0;
    00356             }
    00357             else
    00358             {
    00359                 root() = copy(x.root(), header);
    00360                 leftmost() = minimum(root());
    00361                 rightmost() = maximum(root());
    00362             }
    00363             node_count = x.node_count;
    00364         }
    00365
    00366         ~Oscl_Rb_Tree()
    00367         {
    00368             clear();
    00369             release_node(header);
    00370         }
    00371
    00372         Oscl_Rb_Tree<Key, Value, KeyOfValue, Compare, Alloc>&
    00373         operator=(const Oscl_Rb_Tree<Key, Value, KeyOfValue, Compare, Alloc>& x)
    00374         {
    00375             if (this != &x)
    00376             {
    00377                 clear();
    00378                 node_count = 0;
    00379                 key_compare = x.key_compare;
    00380
    00381                 if (x.root() == 0)
    00382                 {
    00383                     root() = 0;
    00384                     leftmost() = header;
    00385                     rightmost() = header;
    00386                 }
    00387                 else
    00388                 {
    00389                     root() = copy(x.root(), header);
    00390                     leftmost() = minimum(root());
    00391                     rightmost() = maximum(root());
    00392                     node_count = x.node_count;
    00393                 }
    00394             }
    00395             return *this;
    00396         }
    00397
    00398     public:
    00399         iterator begin()
    00400         {
    00401             return leftmost();
    00402         }
    00403         const_iterator begin() const
    00404         {
    00405             return leftmost();
    00406         }
    00407         iterator end()
    00408         {
    00409             return header;
    00410         }
    00411         const_iterator end() const
    00412         {
    00413             return header;
    00414         }
    00415         bool empty() const
    00416         {
    00417             return node_count == 0;
    00418         }
    00419         size_type size() const
    00420         {
    00421             return node_count;
    00422         }
    00423         size_type max_size() const
    00424         {
    00425             return size_type(-1);
    00426         }
    00427
    00428         Oscl_Pair<iterator, bool> insert_unique(const value_type& v)
    00429         {
    00430             link_type y = header;
    00431             link_type x = root();
    00432             bool comp = true;
    00433             while (x != 0)
    00434             {
    00435                 y = x;
    00436                 comp = key_compare(KeyOfValue()(v), key(x));
    00437                 x = comp ? left(x) : right(x);
    00438             }
    00439             iterator j = iterator(y);
    00440             if (comp)
    00441             {
    00442                 if (j == begin())
    00443                     return Oscl_Pair<iterator, bool>(insert(x, y, v), true);
    00444                 else
    00445                     --j;
    00446             }
    00447             if (key_compare(key(j.node), KeyOfValue()(v)))
    00448                 return Oscl_Pair<iterator, bool>(insert(x, y, v), true);
    00449
    00450             return Oscl_Pair<iterator, bool>(j, false);
    00451         }
    00452
    00453         iterator insert_unique(iterator position, const value_type& v)
    00454         {
    00455             if (position.node == header->left)   // begin()
    00456             {
    00457                 if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node)))
    00458                     return insert((link_type)position.node, (link_type)position.node, v);
    00459                 // first argument just needs to be non-null
    00460                 else
    00461                     return insert_unique(v).first;
    00462             }
    00463             else if (position.node == header)   // end()
    00464             {
    00465                 if (key_compare(key(rightmost()), KeyOfValue()(v)))
    00466                     return insert(0, rightmost(), v);
    00467                 else
    00468                     return insert_unique(v).first;
    00469             }
    00470             else
    00471             {
    00472                 iterator before = position;
    00473                 --before;
    00474                 if (key_compare(key(before.node), KeyOfValue()(v))
    00475                         && key_compare(KeyOfValue()(v), key(position.node)))
    00476                 {
    00477                     if (right(before.node) == 0)
    00478                         return insert(0, (link_type)before.node, v);
    00479                     else
    00480                         return insert((link_type)position.node, (link_type)position.node, v);
    00481                     // first argument just needs to be non-null
    00482                 }
    00483                 else
    00484                     return insert_unique(v).first;
    00485             }
    00486         }
    00487
    00488         void insert_unique(const_iterator first, const_iterator last)
    00489         {
    00490             for (; first != last; ++first)
    00491                 insert_unique(*first);
    00492         }
    00493
    00494         void insert_unique(const value_type* first, const value_type* last)
    00495         {
    00496             for (; first != last; ++first)
    00497                 insert_unique(*first);
    00498         }
    00499
    00500         void erase(iterator position)
    00501         {
    00502             link_type y = (link_type) rebalance_for_erase(position.node,
    00503                           header->parent,
    00504                           header->left,
    00505                           header->right);
    00506
    00507             destroy_node(y);
    00508             --node_count;
    00509         }
    00510
    00511         size_type erase(const key_type& x)
    00512         {
    00513             Oscl_Pair<iterator, iterator> p = equal_range(x);
    00514             size_type n = 0;
    00515             distance(p.first, p.second, n);
    00516             erase(p.first, p.second);
    00517             return n;
    00518         }
    00519
    00520         void erase(iterator first, iterator last)
    00521         {
    00522             if (first == begin() && last == end())
    00523                 clear();
    00524             else
    00525                 while (first != last) erase(first++);
    00526         }
    00527
    00528         void erase(const key_type* first, const key_type* last)
    00529         {
    00530             while (first != last) erase(*first++);
    00531         }
    00532
    00533         void clear()
    00534         {
    00535             if (node_count != 0)
    00536             {
    00537                 erase_without_rebalance(root());
    00538                 leftmost() = header;
    00539                 root() = 0;
    00540                 rightmost() = header;
    00541                 node_count = 0;
    00542             }
    00543         }
    00544
    00545         iterator find(const Key& k)
    00546         {
    00547             link_type y = header;        // Last node which is not less than k.
    00548             link_type x = root();        // Current node.
    00549
    00550             while (x != 0)
    00551             {
    00552                 if (!key_compare(key(x), k))
    00553                     y = x, x = left(x);
    00554                 else
    00555                     x = right(x);
    00556             }
    00557             iterator j = iterator(y);
    00558             return (j == end() || key_compare(k, key(j.node))) ? end() : j;
    00559         }
    00560
    00561         const_iterator find(const Key& k) const
    00562         {
    00563             link_type y = header; /* Last node which is not less than k. */
    00564             link_type x = root(); /* Current node. */
    00565
    00566             while (x != 0)
    00567             {
    00568                 if (!key_compare(key(x), k))
    00569                     y = x, x = left(x);
    00570                 else
    00571                     x = right(x);
    00572             }
    00573             const_iterator j = const_iterator(y);
    00574             return (j == end() || key_compare(k, key(j.node))) ? end() : j;
    00575         }
    00576
    00577         size_type count(const Key& k) const
    00578         {
    00579             Oscl_Pair<const_iterator, const_iterator> p = equal_range(k);
    00580             size_type n = 0;
    00581             distance(p.first, p.second, n);
    00582             return n;
    00583         }
    00584
    00585         iterator lower_bound(const Key& k)
    00586         {
    00587             link_type y = header; /* Last node which is not less than k. */
    00588             link_type x = root(); /* Current node. */
    00589
    00590             while (x != 0)
    00591             {
    00592                 if (!key_compare(key(x), k))
    00593                 {
    00594                     y = x;
    00595                     x = left(x);
    00596                 }
    00597                 else
    00598                     x = right(x);
    00599             }
    00600             return iterator(y);
    00601         }
    00602
    00603         const_iterator lower_bound(const Key& k) const
    00604         {
    00605             link_type y = header; /* Last node which is not less than k. */
    00606             link_type x = root(); /* Current node. */
    00607
    00608             while (x != 0)
    00609             {
    00610                 if (!key_compare(key(x), k))
    00611                 {
    00612                     y = x;
    00613                     x = left(x);
    00614                 }
    00615                 else
    00616                     x = right(x);
    00617             }
    00618             return const_iterator(y);
    00619         }
    00620
    00621         iterator upper_bound(const Key& k)
    00622         {
    00623             link_type y = header; /* Last node which is greater than k. */
    00624             link_type x = root(); /* Current node. */
    00625
    00626             while (x != 0)
    00627             {
    00628                 if (key_compare(k, key(x)))
    00629                 {
    00630                     y = x;
    00631                     x = left(x);
    00632                 }
    00633                 else
    00634                     x = right(x);
    00635             }
    00636             return iterator(y);
    00637         }
    00638
    00639         const_iterator upper_bound(const Key& k) const
    00640         {
    00641             link_type y = header; /* Last node which is greater than k. */
    00642             link_type x = root(); /* Current node. */
    00643
    00644             while (x != 0)
    00645             {
    00646                 if (key_compare(k, key(x)))
    00647                 {
    00648                     y = x;
    00649                     x = left(x);
    00650                 }
    00651                 else
    00652                     x = right(x);
    00653             }
    00654             return const_iterator(y);
    00655         }
    00656
    00657         Oscl_Pair<iterator, iterator> equal_range(const Key& k)
    00658         {
    00659             return Oscl_Pair<iterator, iterator>(lower_bound(k), upper_bound(k));
    00660         }
    00661
    00662         Oscl_Pair<const_iterator, const_iterator> equal_range(const Key& k) const
    00663         {
    00664             return Oscl_Pair<const_iterator, const_iterator>(lower_bound(k), upper_bound(k));
    00665         }
    00666
    00667     private:
    00668         // this helper function performs a downcast from base_link_type& to link_type&
    00669         // under C99 (gcc 3.x) this breaks aliasing rules so we have to go via a void** instead
    00670         inline static link_type& cast_to_link_type(base_link_type &node)
    00671         {
    00672             void** ptr = (void**) & node;
    00673             link_type* base = (link_type*) ptr;
    00674             return *base;
    00675         }
    00676
    00677         link_type& root() const
    00678         {
    00679             return cast_to_link_type(header->parent);
    00680         }
    00681         link_type& leftmost() const
    00682         {
    00683             return cast_to_link_type(header->left);
    00684         }
    00685         link_type& rightmost() const
    00686         {
    00687             return cast_to_link_type(header->right);
    00688         }
    00689
    00690         const Key& key(link_type x) const
    00691         {
    00692             return KeyOfValue()(value(x));
    00693         }
    00694         static reference value(link_type x)
    00695         {
    00696             return x->value;
    00697         }
    00698         static link_type& left(link_type x)
    00699         {
    00700             return cast_to_link_type(x->left);
    00701         }
    00702         static link_type& right(link_type x)
    00703         {
    00704             return cast_to_link_type(x->right);
    00705         }
    00706         static link_type& parent(link_type x)
    00707         {
    00708             return cast_to_link_type(x->parent);
    00709         }
    00710
    00711         const Key& key(base_link_type x) const
    00712         {
    00713             return KeyOfValue()(value(x));
    00714         }
    00715         static reference value(base_link_type x)
    00716         {
    00717             return ((link_type)x)->value;
    00718         }
    00719         static link_type& left(base_link_type x)
    00720         {
    00721             return cast_to_link_type(x->left);
    00722         }
    00723         static link_type& right(base_link_type x)
    00724         {
    00725             return cast_to_link_type(x->right);
    00726         }
    00727         static link_type& parent(base_link_type x)
    00728         {
    00729             return cast_to_link_type(x->parent);
    00730         }
    00731
    00732         static link_type minimum(link_type x)
    00733         {
    00734             return (link_type) Oscl_Rb_Tree_Node_Base::minimum(x);
    00735         }
    00736         static link_type maximum(link_type x)
    00737         {
    00738             return (link_type) Oscl_Rb_Tree_Node_Base::maximum(x);
    00739         }
    00740
    00741         iterator insert(link_type x, link_type y, const value_type& v)
    00742         {
    00743             link_type z;
    00744
    00745             if (y == header || x != 0 || key_compare(KeyOfValue()(v), key(y)))
    00746             {
    00747                 z = create_node(v);
    00748                 left(y) = z;                // also makes leftmost() = z when y == header
    00749                 if (y == header)
    00750                 {
    00751                     root() = z;
    00752                     rightmost() = z;
    00753                 }
    00754                 else if (y == leftmost())
    00755                     leftmost() = z;           // maintain leftmost() pointing to min node
    00756             }
    00757             else
    00758             {
    00759                 z = create_node(v);
    00760                 right(y) = z;
    00761                 if (y == rightmost())
    00762                     rightmost() = z;          // maintain rightmost() pointing to max node
    00763             }
    00764             parent(z) = y;
    00765             left(z) = 0;
    00766             right(z) = 0;
    00767             rebalance(z, header->parent);
    00768             ++node_count;
    00769             return iterator(z);
    00770
    00771         }
    00772
    00773         void erase_without_rebalance(link_type x)
    00774         {
    00775             while (x != 0)
    00776             {
    00777                 erase_without_rebalance((link_type)x->right);
    00778                 link_type y = (link_type)x->left;
    00779                 destroy_node(x);
    00780                 x = y;
    00781             }
    00782         }
    00783
    00784         link_type copy(link_type x, link_type p)
    00785         {
    00786             // structural copy.  x and p must be non-null.
    00787             link_type top = clone_node(x);
    00788             top->parent = p;
    00789
    00790             if (x->right)
    00791             {
    00792                 top->right = copy(right(x), top);
    00793             }
    00794             p = top;
    00795             x = left(x);
    00796
    00797             while (x != 0)
    00798             {
    00799                 link_type y = clone_node(x);
    00800                 p->left = y;
    00801                 y->parent = p;
    00802                 if (x->right)
    00803                 {
    00804                     y->right = copy(right(x), y);
    00805                 }
    00806                 p = y;
    00807                 x = left(x);
    00808             }
    00809
    00810             return top;
    00811         }
    00812
    00813         link_type get_node()
    00814         {
    00815             return node_allocator.ALLOCATE(1);
    00816         }
    00817         void release_node(link_type node)
    00818         {
    00819             node_allocator.deallocate(node);
    00820         }
    00821
    00822         link_type create_node(const value_type& v)
    00823         {
    00824             link_type x = get_node();
    00825             new(&x->value) value_type(v);
    00826             return x;
    00827         }
    00828
    00829         void destroy_node(link_type x)
    00830         {
    00831             x->value.~Value();
    00832             release_node(x);
    00833         }
    00834
    00835         link_type clone_node(link_type x)
    00836         {
    00837             link_type tmp = create_node(x->value);
    00838             tmp->color = x->color;
    00839             tmp->left = 0;
    00840             tmp->right = 0;
    00841             return tmp;
    00842         }
    00843
    00844         void distance(const_iterator first, const_iterator last, size_type& n) const
    00845         {
    00846             while (first != last)
    00847             {
    00848                 n++;
    00849                 first++;
    00850             }
    00851         }
    00852
    00853         void distance(iterator first, iterator last, size_type& n) const
    00854         {
    00855             while (first != last)
    00856             {
    00857                 n++;
    00858                 first++;
    00859             }
    00860         }
    00861 };
    00862
    00863
    00867 #endif
    00868