diff options
Diffstat (limited to 'src/boost/libs/intrusive/example/doc_rbtree_algorithms.cpp')
-rw-r--r-- | src/boost/libs/intrusive/example/doc_rbtree_algorithms.cpp | 83 |
1 files changed, 83 insertions, 0 deletions
diff --git a/src/boost/libs/intrusive/example/doc_rbtree_algorithms.cpp b/src/boost/libs/intrusive/example/doc_rbtree_algorithms.cpp new file mode 100644 index 000000000..db5cb2af4 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_rbtree_algorithms.cpp @@ -0,0 +1,83 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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; +} + +//] |