| ///////////////////////////////////////////////////////////////////////////// |
| // |
| // (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; |
| } |
| |
| //] |