Boost_1_39_0/libs/intrusive/example/doc_rbtree_algorithms.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2006-2008
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // See http://www.boost.org/libs/intrusive for documentation.
  10 //
  11 /////////////////////////////////////////////////////////////////////////////
  12 //[doc_rbtree_algorithms_code
  13 #include <boost/intrusive/rbtree_algorithms.hpp>
  14 #include <cassert>
  15
  16 struct my_node
  17 {
  18    my_node(int i = 0)
  19       :  int_(i)
  20    {}
  21    my_node *parent_, *left_, *right_;
  22    int      color_;
  23    //other members
  24    int      int_;
  25 };
  26
  27 //Define our own rbtree_node_traits
  28 struct my_rbtree_node_traits
  29 {
  30    typedef my_node                                    node;
  31    typedef my_node *                                  node_ptr;
  32    typedef const my_node *                            const_node_ptr;
  33    typedef int                                        color;
  34    static node_ptr get_parent(const_node_ptr n)       {  return n->parent_;   }
  35    static void set_parent(node_ptr n, node_ptr parent){  n->parent_ = parent; }
  36    static node_ptr get_left(const_node_ptr n)         {  return n->left_;     }
  37    static void set_left(node_ptr n, node_ptr left)    {  n->left_ = left;     }
  38    static node_ptr get_right(const_node_ptr n)        {  return n->right_;    }
  39    static void set_right(node_ptr n, node_ptr right)  {  n->right_ = right;   }
  40    static color get_color(const_node_ptr n)           {  return n->color_;    }
  41    static void set_color(node_ptr n, color c)         {  n->color_ = c;       }
  42    static color black()                               {  return color(0);     }
  43    static color red()                                 {  return color(1);     }
  44 };
  45
  46 struct node_ptr_compare
  47 {
  48    bool operator()(const my_node *a, const my_node *b)
  49    {  return a->int_ < b->int_;  }
  50 };
  51
  52 int main()
  53 {
  54    typedef boost::intrusive::rbtree_algorithms<my_rbtree_node_traits> algo;
  55    my_node header, two(2), three(3);
  56
  57    //Create an empty rbtree container:
  58    //"header" will be the header node of the tree
  59    algo::init_header(&header);
  60
  61    //Now insert node "two" in the tree using the sorting functor
  62    algo::insert_equal_upper_bound(&header, &two, node_ptr_compare());
  63
  64    //Now insert node "three" in the tree using the sorting functor
  65    algo::insert_equal_lower_bound(&header, &three, node_ptr_compare());
  66
  67    //Now take the first node (the left node of the header)
  68    my_node *n = header.left_;
  69    assert(n == &two);
  70
  71    //Now go to the next node
  72    n = algo::next_node(n);
  73    assert(n == &three);
  74
  75    //Erase a node just using a pointer to it
  76    algo::unlink(&two);
  77
  78    //Erase a node using also the header (faster)
  79    algo::erase(&header, &three);
  80    return 0;
  81 }
  82
  83 //]