]>
git.proxmox.com Git - ceph.git/blob - ceph/src/boost/libs/intrusive/example/doc_treap_algorithms.cpp
1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Ion Gaztanaga 2007-2013
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)
9 // See http://www.boost.org/libs/intrusive for documentation.
11 /////////////////////////////////////////////////////////////////////////////
12 //[doc_treap_algorithms_code
13 #include <boost/intrusive/treap_algorithms.hpp>
18 my_node(int i
= 0, unsigned int priority
= 0)
19 : prio_(priority
), int_(i
)
21 my_node
*parent_
, *left_
, *right_
;
27 //Define our own treap_node_traits
28 struct my_treap_node_traits
31 typedef my_node
* node_ptr
;
32 typedef const my_node
* const_node_ptr
;
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
; }
42 struct node_ptr_compare
43 { bool operator()(const my_node
*a
, const my_node
*b
) { return a
->int_
< b
->int_
; } };
45 struct node_ptr_priority
46 { bool operator()(const my_node
*a
, const my_node
*b
) { return a
->prio_
< b
->prio_
;} };
50 typedef boost::intrusive::treap_algorithms
<my_treap_node_traits
> algo
;
51 my_node header
, two(2, 5), three(3, 1);
53 //Create an empty treap container:
54 //"header" will be the header node of the tree
55 algo::init_header(&header
);
57 //Now insert node "two" in the tree using the sorting functor
58 algo::insert_equal_upper_bound(&header
, &two
, node_ptr_compare(), node_ptr_priority());
60 //Now insert node "three" in the tree using the sorting functor
61 algo::insert_equal_lower_bound(&header
, &three
, node_ptr_compare(), node_ptr_priority());
63 //Now take the first node (the left node of the header)
64 my_node
*n
= header
.left_
;
67 //Now go to the next node
68 n
= algo::next_node(n
);
71 //Erase a node just using a pointer to it
72 algo::unlink(&two
, node_ptr_priority());
74 //Erase a node using also the header (faster)
75 algo::erase(&header
, &three
, node_ptr_priority());