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 { my_nodemy_node18 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 get_parentmy_treap_node_traits34 static node_ptr get_parent(const_node_ptr n) { return n->parent_; } set_parentmy_treap_node_traits35 static void set_parent(node_ptr n, node_ptr parent){ n->parent_ = parent; } get_leftmy_treap_node_traits36 static node_ptr get_left(const_node_ptr n) { return n->left_; } set_leftmy_treap_node_traits37 static void set_left(node_ptr n, node_ptr left) { n->left_ = left; } get_rightmy_treap_node_traits38 static node_ptr get_right(const_node_ptr n) { return n->right_; } set_rightmy_treap_node_traits39 static void set_right(node_ptr n, node_ptr right) { n->right_ = right; } 40 }; 41 42 struct node_ptr_compare operator ()node_ptr_compare43 { bool operator()(const my_node *a, const my_node *b) { return a->int_ < b->int_; } }; 44 45 struct node_ptr_priority operator ()node_ptr_priority46 { bool operator()(const my_node *a, const my_node *b) { return a->prio_ < b->prio_;} }; 47 main()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 //] 80