libs/intrusive/example/doc_splay_algorithms.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2006-2012
   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_splaytree_algorithms_code
  13 #include <boost/intrusive/splaytree_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 splaytree_node_traits
  28 struct my_splaytree_node_traits
  29 {
  30    typedef my_node                                    node;
  31    typedef my_node *                                  node_ptr;
  32    typedef const my_node *                            const_node_ptr;
  33
  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 };
  41
  42 struct node_ptr_compare
  43 {
  44    bool operator()(const my_node *a, const my_node *b)
  45    {  return a->int_ < b->int_;  }
  46 };
  47
  48 int main()
  49 {
  50    typedef boost::intrusive::splaytree_algorithms<my_splaytree_node_traits> algo;
  51    my_node header, two(2), three(3);
  52
  53    //Create an empty splaytree container:
  54    //"header" will be the header node of the tree
  55    algo::init_header(&header);
  56
  57    //Now insert node "two" in the tree using the sorting functor
  58    algo::insert_equal_upper_bound(&header, &two, node_ptr_compare());
  59
  60    //Now insert node "three" in the tree using the sorting functor
  61    algo::insert_equal_lower_bound(&header, &three, node_ptr_compare());
  62
  63    //Now take the first node (the left node of the header)
  64    my_node *n = header.left_;
  65    assert(n == &two);
  66
  67    //Now go to the next node
  68    n = algo::next_node(n);
  69    assert(n == &three);
  70
  71    //Erase a node just using a pointer to it
  72    algo::unlink(&two);
  73
  74    //Erase a node using also the header (faster)
  75    algo::erase(&header, &three);
  76    return 0;
  77 }
  78 //]