]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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_treap_algorithms_code | |
13 | #include <boost/intrusive/treap_algorithms.hpp> | |
14 | #include <cassert> | |
15 | ||
16 | struct my_node | |
17 | { | |
18 | my_node(int i = 0, unsigned int priority = 0) | |
19 | : prio_(priority), int_(i) | |
20 | {} | |
21 | my_node *parent_, *left_, *right_; | |
22 | int prio_; | |
23 | //other members | |
24 | int int_; | |
25 | }; | |
26 | ||
27 | //Define our own treap_node_traits | |
28 | struct my_treap_node_traits | |
29 | { | |
30 | typedef my_node node; | |
31 | typedef my_node * node_ptr; | |
32 | typedef const my_node * const_node_ptr; | |
33 | ||
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; } | |
40 | }; | |
41 | ||
42 | struct node_ptr_compare | |
43 | { bool operator()(const my_node *a, const my_node *b) { return a->int_ < b->int_; } }; | |
44 | ||
45 | struct node_ptr_priority | |
46 | { bool operator()(const my_node *a, const my_node *b) { return a->prio_ < b->prio_;} }; | |
47 | ||
48 | int main() | |
49 | { | |
50 | typedef boost::intrusive::treap_algorithms<my_treap_node_traits> algo; | |
51 | my_node header, two(2, 5), three(3, 1); | |
52 | ||
53 | //Create an empty treap container: | |
54 | //"header" will be the header node of the tree | |
55 | algo::init_header(&header); | |
56 | ||
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()); | |
59 | ||
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()); | |
62 | ||
63 | //Now take the first node (the left node of the header) | |
64 | my_node *n = header.left_; | |
65 | assert(n == &two); | |
66 | ||
67 | //Now go to the next node | |
68 | n = algo::next_node(n); | |
69 | assert(n == &three); | |
70 | ||
71 | //Erase a node just using a pointer to it | |
72 | algo::unlink(&two, node_ptr_priority()); | |
73 | ||
74 | //Erase a node using also the header (faster) | |
75 | algo::erase(&header, &three, node_ptr_priority()); | |
76 | return 0; | |
77 | } | |
78 | ||
79 | //] |