1 /////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2006-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_set_code
13 #include <boost/intrusive/treap_set.hpp>
14 #include <vector>
15 #include <functional>
16 #include <cassert>
17
18 using namespace boost::intrusive;
19
20 class MyClass : public bs_set_base_hook<> //This is a base hook
21 {
22 int int_;
23 unsigned int prio_;
24
25 public:
26 //This is a member hook
27 bs_set_member_hook<> member_hook_;
28
MyClass(int i,unsigned int prio)29 MyClass(int i, unsigned int prio) : int_(i), prio_(prio)
30 {}
31
get_priority() const32 unsigned int get_priority() const
33 { return this->prio_; }
34
35 //Less and greater operators
operator <(const MyClass & a,const MyClass & b)36 friend bool operator< (const MyClass &a, const MyClass &b)
37 { return a.int_ < b.int_; }
operator >(const MyClass & a,const MyClass & b)38 friend bool operator> (const MyClass &a, const MyClass &b)
39 { return a.int_ > b.int_; }
40 //Default priority compare
priority_order(const MyClass & a,const MyClass & b)41 friend bool priority_order (const MyClass &a, const MyClass &b)
42 { return a.prio_ < b.prio_; } //Lower value means higher priority
43 //Inverse priority compare
priority_inverse_order(const MyClass & a,const MyClass & b)44 friend bool priority_inverse_order (const MyClass &a, const MyClass &b)
45 { return a.prio_ > b.prio_; } //Higher value means higher priority
46 };
47
48 struct inverse_priority
49 {
operator ()inverse_priority50 bool operator()(const MyClass &a, const MyClass &b) const
51 { return priority_inverse_order(a, b); }
52 };
53
54
55 //Define an treap_set using the base hook that will store values in reverse order
56 typedef treap_set< MyClass, compare<std::greater<MyClass> > > BaseSet;
57
58 //Define an multiset using the member hook that will store
59 typedef member_hook<MyClass, bs_set_member_hook<>, &MyClass::member_hook_> MemberOption;
60 typedef treap_multiset
61 < MyClass, MemberOption, priority<inverse_priority> > MemberMultiset;
62
main()63 int main()
64 {
65 typedef std::vector<MyClass>::iterator VectIt;
66
67 //Create several MyClass objects, each one with a different value
68 std::vector<MyClass> values;
69 for(int i = 0; i < 100; ++i) values.push_back(MyClass(i, (i % 10)));
70
71 BaseSet baseset;
72 MemberMultiset membermultiset;
73
74 //Now insert them in the sets
75 for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
76 baseset.insert(*it);
77 membermultiset.insert(*it);
78 }
79
80 //Now test treap_sets
81 {
82 BaseSet::reverse_iterator rbit(baseset.rbegin());
83 MemberMultiset::iterator mit(membermultiset.begin());
84 VectIt it(values.begin()), itend(values.end());
85
86 //Test the objects inserted in the base hook treap_set
87 for(; it != itend; ++it, ++rbit)
88 if(&*rbit != &*it) return 1;
89
90 //Test the objects inserted in the member hook treap_set
91 for(it = values.begin(); it != itend; ++it, ++mit)
92 if(&*mit != &*it) return 1;
93
94 //Test priority order
95 for(int i = 0; i < 100; ++i){
96 if(baseset.top()->get_priority() != static_cast<unsigned int>(i/10))
97 return 1;
98 if(membermultiset.top()->get_priority() != 9u - static_cast<unsigned int>(i/10))
99 return 1;
100 baseset.erase(baseset.top());
101 membermultiset.erase(membermultiset.top());
102 }
103 }
104 return 0;
105 }
106 //]
107