Ticket #10769: iterator-example.cpp

File iterator-example.cpp, 5.8 KB (added by Matei David <matei@…>, 8 years ago)

example file

Line 
1#include <boost/intrusive/set.hpp>
2#include <boost/intrusive/detail/tree_iterator.hpp>
3#include <boost/iterator/iterator_adaptor.hpp>
4
5// from: https__raw_githubusercontent_com/boostorg/intrusive/master/test/bounded_pointer.hpp
6#include "bounded_pointer.hpp"
7
8namespace bi = boost::intrusive;
9
10template < typename Value_Traits, bool Is_Const >
11class my_iterator
12 : public boost::iterator_adaptor< my_iterator< Value_Traits, Is_Const >,
13 bi::tree_iterator< Value_Traits, Is_Const >,
14 boost::use_default,
15 boost::forward_traversal_tag >
16{
17public:
18 typedef bi::tree_iterator< Value_Traits, Is_Const > base_iterator;
19
20 my_iterator()
21 : my_iterator::iterator_adaptor_() {}
22 explicit my_iterator(const base_iterator& other)
23 : my_iterator::iterator_adaptor_(other) {}
24 my_iterator(const my_iterator< Value_Traits, false >& other)
25 : my_iterator::iterator_adaptor_(other) {}
26
27 typedef typename base_iterator::pointer pointer; // WHY ???
28 base_iterator operator -> () const { return this->base(); } // WHY ???
29
30private:
31 friend class boost::iterator_core_access;
32 typedef bi::bstree_algorithms< typename Value_Traits::node_traits > node_algorithms;
33
34 void increment()
35 {
36 ++this->base_reference();
37 if (not node_algorithms::is_header(this->base().pointed_node()))
38 {
39 ++this->base_reference();
40 }
41 }
42}; // class my_iterator
43
44struct A;
45
46typedef bounded_allocator< A > alloc_type;
47typedef bounded_pointer< A > ptr_type;
48typedef bounded_pointer< const A > const_ptr_type;
49typedef bounded_reference< A > ref_type;
50typedef bounded_reference< const A > const_ref_type;
51
52struct A
53{
54 A(int val = 42) : _val(val) {}
55
56 friend bool operator == (const A& lhs, const A& rhs) { return lhs._val == rhs._val; }
57 friend bool operator != (const A& lhs, const A& rhs) { return not (lhs == rhs); }
58 friend bool operator < (const A& lhs, const A& rhs) { return lhs._val < rhs._val; }
59 friend bool operator <= (const A& lhs, const A& rhs) { return lhs < rhs or lhs == rhs; }
60 friend bool operator > (const A& lhs, const A& rhs) { return not (lhs <= rhs); }
61 friend bool operator >= (const A& lhs, const A& rhs) { return not (lhs < rhs); }
62
63 int _val;
64 ptr_type _parent;
65 ptr_type _l_child;
66 ptr_type _r_child;
67 int _col;
68}; // struct A
69
70struct A_Set_Node_Traits
71{
72 typedef A node;
73 typedef bounded_pointer< A > node_ptr;
74 typedef bounded_pointer< const A > const_node_ptr;
75 typedef int color;
76
77 static node_ptr get_parent(const_node_ptr n) { return n->_parent; }
78 static void set_parent(node_ptr n, node_ptr ptr) { n->_parent = ptr; }
79 static node_ptr get_left(const_node_ptr n) { return n->_l_child; }
80 static void set_left(node_ptr n, node_ptr ptr) { n->_l_child = ptr; }
81 static node_ptr get_right(const_node_ptr n) { return n->_r_child; }
82 static void set_right(node_ptr n, node_ptr ptr) { n->_r_child = ptr; }
83 static color get_color(const_node_ptr n) { return n->_col; }
84 static void set_color(node_ptr n, color c) { n->_col = c ; }
85 static color black() { return 0; }
86 static color red() { return 1; }
87}; // struct A_Set_Node_Traits
88
89struct A_Set_Value_Traits
90{
91 typedef A value_type;
92 typedef A_Set_Node_Traits node_traits;
93 typedef node_traits::node_ptr node_ptr;
94 typedef node_traits::const_node_ptr const_node_ptr;
95 typedef node_ptr pointer;
96 typedef const_node_ptr const_pointer;
97 typedef bounded_reference< A > reference;
98 typedef bounded_reference< const A > const_reference;
99 typedef A_Set_Value_Traits* value_traits_ptr;
100
101 static const bi::link_mode_type link_mode = bi::safe_link;
102
103 static node_ptr to_node_ptr (reference value) { return &value; }
104 static const_node_ptr to_node_ptr (const_reference value) { return &value; }
105 static pointer to_value_ptr(node_ptr n) { return n; }
106 static const_pointer to_value_ptr(const_node_ptr n) { return n; }
107}; // struct A_Set_Value_Traits
108
109typedef bi::set<
110 A,
111 bi::value_traits< A_Set_Value_Traits >,
112 bi::header_holder_type< bounded_pointer_holder< A > >
113 > set_type;
114
115typedef bi::tree_iterator< A_Set_Value_Traits, false > reg_iterator_type;
116typedef my_iterator< A_Set_Value_Traits, false > my_iterator_type;
117
118// check iterator inner types
119// reg_iterator_type
120static_assert(std::is_same< reg_iterator_type::value_type, A >::value, "reg_iterator_type::value_type != A");
121static_assert(std::is_same< reg_iterator_type::reference, ref_type >::value, "reg_iterator_type::value_type != ref_type");
122static_assert(std::is_same< reg_iterator_type::pointer, ptr_type >::value, "reg_iterator_type::value_type != ptr_type");
123// my_iterator_type
124static_assert(std::is_same< my_iterator_type::value_type, A >::value, "my_iterator_type::value_type != A");
125static_assert(std::is_same< my_iterator_type::reference, ref_type >::value, "my_iterator_type::value_type != ref_type");
126static_assert(std::is_same< my_iterator_type::pointer, ptr_type >::value, "my_iterator_type::value_type != ptr_type");
127
128template < typename Iterator >
129void print_set(std::ostream& os, set_type& s, const std::string& tag)
130{
131 os << "set using " << tag << ":";
132 Iterator it(s.begin());
133 Iterator it_end(s.end());
134 while (it != it_end)
135 {
136 os << " " << it->_val;
137 ++it;
138 }
139 os << std::endl;
140}
141
142int main()
143{
144 alloc_type a;
145 a.init();
146 ptr_type p;
147 {
148 set_type s;
149 for (size_t i = 0; i < 10; ++i)
150 {
151 p = a.allocate(1);
152 new (p.raw()) A(i);
153 s.insert(*p);
154 }
155 print_set< reg_iterator_type >(std::cout, s, "reg_iterator");
156 print_set< my_iterator_type >(std::cout, s, "my_iterator");
157 s.clear_and_dispose([&a] (ptr_type p) { a.deallocate(p, 1); });
158 }
159 assert(a.is_clear());
160 a.destroy();
161}