]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
29 | MyClass(int i, unsigned int prio) : int_(i), prio_(prio) | |
30 | {} | |
31 | ||
32 | unsigned int get_priority() const | |
33 | { return this->prio_; } | |
34 | ||
35 | //Less and greater operators | |
36 | friend bool operator< (const MyClass &a, const MyClass &b) | |
37 | { return a.int_ < b.int_; } | |
38 | friend bool operator> (const MyClass &a, const MyClass &b) | |
39 | { return a.int_ > b.int_; } | |
40 | //Default priority compare | |
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 | |
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 | { | |
50 | 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 | ||
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; | |
1e59de90 | 69 | for(std::size_t i = 0; i < 100u; ++i) values.push_back(MyClass((int)i, unsigned(i % 10))); |
7c673cae FG |
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 | //] |