1 /////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2007-2013
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_avltree_algorithms_code
13 #include <boost/intrusive/avltree_algorithms.hpp>
14 #include <cassert>
15
16 struct my_node
17 {
my_nodemy_node18 my_node(int i = 0)
19 : int_(i)
20 {}
21 my_node *parent_, *left_, *right_;
22 int balance_;
23 //other members
24 int int_;
25 };
26
27 //Define our own avltree_node_traits
28 struct my_avltree_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 balance;
34
get_parentmy_avltree_node_traits35 static node_ptr get_parent(const_node_ptr n) { return n->parent_; }
set_parentmy_avltree_node_traits36 static void set_parent(node_ptr n, node_ptr parent){ n->parent_ = parent; }
get_leftmy_avltree_node_traits37 static node_ptr get_left(const_node_ptr n) { return n->left_; }
set_leftmy_avltree_node_traits38 static void set_left(node_ptr n, node_ptr left) { n->left_ = left; }
get_rightmy_avltree_node_traits39 static node_ptr get_right(const_node_ptr n) { return n->right_; }
set_rightmy_avltree_node_traits40 static void set_right(node_ptr n, node_ptr right) { n->right_ = right; }
get_balancemy_avltree_node_traits41 static balance get_balance(const_node_ptr n) { return n->balance_; }
set_balancemy_avltree_node_traits42 static void set_balance(node_ptr n, balance b) { n->balance_ = b; }
negativemy_avltree_node_traits43 static balance negative() { return -1; }
zeromy_avltree_node_traits44 static balance zero() { return 0; }
positivemy_avltree_node_traits45 static balance positive() { return 1; }
46 };
47
48 struct node_ptr_compare
49 {
operator ()node_ptr_compare50 bool operator()(const my_node *a, const my_node *b)
51 { return a->int_ < b->int_; }
52 };
53
main()54 int main()
55 {
56 typedef boost::intrusive::avltree_algorithms<my_avltree_node_traits> algo;
57 my_node header, two(2), three(3);
58
59 //Create an empty avltree container:
60 //"header" will be the header node of the tree
61 algo::init_header(&header);
62
63 //Now insert node "two" in the tree using the sorting functor
64 algo::insert_equal_upper_bound(&header, &two, node_ptr_compare());
65
66 //Now insert node "three" in the tree using the sorting functor
67 algo::insert_equal_lower_bound(&header, &three, node_ptr_compare());
68
69 //Now take the first node (the left node of the header)
70 my_node *n = header.left_;
71 assert(n == &two);
72
73 //Now go to the next node
74 n = algo::next_node(n);
75 assert(n == &three);
76
77 //Erase a node just using a pointer to it
78 algo::unlink(&two);
79
80 //Erase a node using also the header (faster)
81 algo::erase(&header, &three);
82 return 0;
83 }
84
85 //]
86