/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga  2006-2009
//
// Distributed under the Boost Software License, Version 1.0.
//    (See accompanying file LICENSE_1_0.txt or copy at
//          http://www.boost.org/LICENSE_1_0.txt)
//
// See http://www.boost.org/libs/intrusive for documentation.
//
/////////////////////////////////////////////////////////////////////////////
//[doc_rbtree_algorithms_code
#include <boost/intrusive/rbtree_algorithms.hpp>
#include <cassert>

struct my_node
{
   my_node(int i = 0)
      :  int_(i)
   {}
   my_node *parent_, *left_, *right_;
   int      color_;
   //other members
   int      int_;
};

//Define our own rbtree_node_traits
struct my_rbtree_node_traits
{
   typedef my_node                                    node;
   typedef my_node *                                  node_ptr;
   typedef const my_node *                            const_node_ptr;
   typedef int                                        color;
   static node_ptr get_parent(const_node_ptr n)       {  return n->parent_;   }  
   static void set_parent(node_ptr n, node_ptr parent){  n->parent_ = parent; }  
   static node_ptr get_left(const_node_ptr n)         {  return n->left_;     }  
   static void set_left(node_ptr n, node_ptr left)    {  n->left_ = left;     }  
   static node_ptr get_right(const_node_ptr n)        {  return n->right_;    }  
   static void set_right(node_ptr n, node_ptr right)  {  n->right_ = right;   }  
   static color get_color(const_node_ptr n)           {  return n->color_;    }  
   static void set_color(node_ptr n, color c)         {  n->color_ = c;       }
   static color black()                               {  return color(0);     }
   static color red()                                 {  return color(1);     }
};

struct node_ptr_compare
{
   bool operator()(const my_node *a, const my_node *b)
   {  return a->int_ < b->int_;  }
};

int main()
{
   typedef boost::intrusive::rbtree_algorithms<my_rbtree_node_traits> algo;
   my_node header, two(2), three(3);

   //Create an empty rbtree container:
   //"header" will be the header node of the tree
   algo::init_header(&header);

   //Now insert node "two" in the tree using the sorting functor
   algo::insert_equal_upper_bound(&header, &two, node_ptr_compare());

   //Now insert node "three" in the tree using the sorting functor
   algo::insert_equal_lower_bound(&header, &three, node_ptr_compare());

   //Now take the first node (the left node of the header)
   my_node *n = header.left_;
   assert(n == &two);

   //Now go to the next node
   n = algo::next_node(n);
   assert(n == &three);      

   //Erase a node just using a pointer to it
   algo::unlink(&two);

   //Erase a node using also the header (faster)
   algo::erase(&header, &three);
   return 0;
}

//]