1
2// Copyright 2008-2009 Daniel James.
3// Distributed under the Boost Software License, Version 1.0. (See accompanying
4// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5
6// Gratuitous single linked list.
7//
8// Sadly some STL implementations aren't up to scratch and I need a simple
9// cross-platform container. So here it is.
10
11#if !defined(UNORDERED_TEST_LIST_HEADER)
12#define UNORDERED_TEST_LIST_HEADER
13
14#include <boost/limits.hpp>
15#include <functional>
16#include <iterator>
17
18namespace test {
19 template <typename It1, typename It2>
20 bool equal(It1 begin, It1 end, It2 compare)
21 {
22 for (; begin != end; ++begin, ++compare)
23 if (*begin != *compare)
24 return false;
25 return true;
26 }
27
28 template <typename It1, typename It2, typename Pred>
29 bool equal(It1 begin, It1 end, It2 compare, Pred predicate)
30 {
31 for (; begin != end; ++begin, ++compare)
32 if (!predicate(*begin, *compare))
33 return false;
34 return true;
35 }
36
37 template <typename T> class list;
38
39 namespace test_detail {
40 template <typename T> class list_node;
41 template <typename T> class list_data;
42 template <typename T> class list_iterator;
43 template <typename T> class list_const_iterator;
44
45 template <typename T> class list_node
46 {
47 list_node(list_node const&);
48 list_node& operator=(list_node const&);
49
50 public:
51 T value_;
52 list_node* next_;
53
54 list_node(T const& v) : value_(v), next_(0) {}
55 list_node(T const& v, list_node* n) : value_(v), next_(n) {}
56 };
57
58 template <typename T> class list_data
59 {
60 public:
61 typedef list_node<T> node;
62 typedef unsigned int size_type;
63
64 node* first_;
65 node** last_ptr_;
66 size_type size_;
67
68 list_data() : first_(0), last_ptr_(&first_), size_(0) {}
69
70 ~list_data()
71 {
72 while (first_) {
73 node* tmp = first_;
74 first_ = first_->next_;
75 delete tmp;
76 }
77 }
78
79 private:
80 list_data(list_data const&);
81 list_data& operator=(list_data const&);
82 };
83
84 template <typename T> class list_iterator
85 {
86 friend class list_const_iterator<T>;
87 friend class test::list<T>;
88 typedef list_node<T> node;
89 typedef list_const_iterator<T> const_iterator;
90
91 node* ptr_;
92
93 public:
94 typedef T value_type;
95 typedef T* pointer;
96 typedef T& reference;
97 typedef int difference_type;
98 typedef std::forward_iterator_tag iterator_category;
99
100 list_iterator() : ptr_(0) {}
101 explicit list_iterator(node* x) : ptr_(x) {}
102
103 T& operator*() const { return ptr_->value_; }
104 T* operator->() const { return &ptr_->value_; }
105 list_iterator& operator++()
106 {
107 ptr_ = ptr_->next_;
108 return *this;
109 }
110 list_iterator operator++(int)
111 {
112 list_iterator tmp = *this;
113 ptr_ = ptr_->next_;
114 return tmp;
115 }
116
117 bool operator==(list_iterator y) const { return ptr_ == y.ptr_; }
118 bool operator!=(list_iterator y) const { return ptr_ != y.ptr_; }
119
120 bool operator==(const_iterator y) const { return ptr_ == y.ptr_; }
121 bool operator!=(const_iterator y) const { return ptr_ != y.ptr_; }
122 };
123
124 template <typename T> class list_const_iterator
125 {
126 friend class list_iterator<T>;
127 friend class test::list<T>;
128 typedef list_node<T> node;
129 typedef list_iterator<T> iterator;
130 typedef list_const_iterator<T> const_iterator;
131
132 node* ptr_;
133
134 public:
135 typedef T value_type;
136 typedef T const* pointer;
137 typedef T const& reference;
138 typedef int difference_type;
139 typedef std::forward_iterator_tag iterator_category;
140
141 list_const_iterator() : ptr_(0) {}
142 list_const_iterator(list_iterator<T> const& x) : ptr_(x.ptr_) {}
143
144 T const& operator*() const { return ptr_->value_; }
145 T const* operator->() const { return &ptr_->value_; }
146
147 list_const_iterator& operator++()
148 {
149 ptr_ = ptr_->next_;
150 return *this;
151 }
152
153 list_const_iterator operator++(int)
154 {
155 list_const_iterator tmp = *this;
156 ptr_ = ptr_->next_;
157 return tmp;
158 }
159
160 bool operator==(const_iterator y) const { return ptr_ == y.ptr_; }
161
162 bool operator!=(const_iterator y) const { return ptr_ != y.ptr_; }
163 };
164 }
165
166 template <typename T> class list
167 {
168 typedef test::test_detail::list_data<T> data;
169 typedef test::test_detail::list_node<T> node;
170 data data_;
171
172 public:
173 typedef T value_type;
174 typedef value_type& reference;
175 typedef value_type const& const_reference;
176 typedef unsigned int size_type;
177
178 typedef test::test_detail::list_iterator<T> iterator;
179 typedef test::test_detail::list_const_iterator<T> const_iterator;
180
181 list() : data_() {}
182
183 list(list const& other) : data_() { insert(other.begin(), other.end()); }
184
185 template <class InputIterator>
186 list(InputIterator i, InputIterator j) : data_()
187 {
188 insert(i, j);
189 }
190
191 list& operator=(list const& other)
192 {
193 clear();
194 insert(other.begin(), other.end());
195 return *this;
196 }
197
198 iterator begin() { return iterator(data_.first_); }
199 iterator end() { return iterator(); }
200 const_iterator begin() const { return iterator(data_.first_); }
201 const_iterator end() const { return iterator(); }
202 const_iterator cbegin() const { return iterator(data_.first_); }
203 const_iterator cend() const { return iterator(); }
204
205 template <class InputIterator> void insert(InputIterator i, InputIterator j)
206 {
207 for (; i != j; ++i)
208 push_back(v: *i);
209 }
210
211 void push_front(value_type const& v)
212 {
213 data_.first_ = new node(v, data_.first_);
214 if (!data_.size_)
215 data_.last_ptr_ = &(*data_.last_ptr_)->next_;
216 ++data_.size_;
217 }
218
219 void push_back(value_type const& v)
220 {
221 *data_.last_ptr_ = new node(v);
222 data_.last_ptr_ = &(*data_.last_ptr_)->next_;
223 ++data_.size_;
224 }
225
226 void clear()
227 {
228 while (data_.first_) {
229 node* tmp = data_.first_;
230 data_.first_ = data_.first_->next_;
231 --data_.size_;
232 delete tmp;
233 }
234 data_.last_ptr_ = &data_.first_;
235 }
236
237 void erase(const_iterator i, const_iterator j)
238 {
239 node** ptr = &data_.first_;
240
241 while (*ptr != i.ptr_) {
242 ptr = &(*ptr)->next_;
243 }
244
245 while (*ptr != j.ptr_) {
246 node* to_delete = *ptr;
247 *ptr = (*ptr)->next_;
248 --data_.size_;
249 delete to_delete;
250 }
251
252 if (!*ptr)
253 data_.last_ptr_ = ptr;
254 }
255
256 bool empty() const { return !data_.size_; }
257
258 size_type size() const { return data_.size_; }
259
260 void sort() { sort(std::less<T>()); }
261
262 template <typename Less> void sort(Less less = Less())
263 {
264 if (!empty())
265 merge_sort(
266 &data_.first_, (std::numeric_limits<size_type>::max)(), less);
267 }
268
269 bool operator==(list const& y) const
270 {
271 return size() == y.size() && test::equal(begin(), end(), y.begin());
272 }
273
274 bool operator!=(list const& y) const { return !(*this == y); }
275
276 private:
277 template <typename Less>
278 node** merge_sort(node** l, size_type recurse_limit, Less less)
279 {
280 node** ptr = &(*l)->next_;
281 for (size_type count = 0; count < recurse_limit && *ptr; ++count) {
282 ptr = merge_adjacent_ranges(l, ptr, merge_sort(ptr, count, less), less);
283 }
284 return ptr;
285 }
286
287 template <typename Less>
288 node** merge_adjacent_ranges(
289 node** first, node** second, node** third, Less less)
290 {
291 for (;;) {
292 for (;;) {
293 if (first == second)
294 return third;
295 if (less((*second)->value_, (*first)->value_))
296 break;
297 first = &(*first)->next_;
298 }
299
300 swap_adjacent_ranges(first, second, third);
301 first = &(*first)->next_;
302
303 // Since the two ranges we just swapped, the order is now:
304 // first...third...second
305
306 for (;;) {
307 if (first == third)
308 return second;
309 if (!less((*first)->value_, (*third)->value_))
310 break;
311 first = &(*first)->next_;
312 }
313
314 swap_adjacent_ranges(first, second: third, third: second);
315 first = &(*first)->next_;
316 }
317 }
318
319 void swap_adjacent_ranges(node** first, node** second, node** third)
320 {
321 node* tmp = *first;
322 *first = *second;
323 *second = *third;
324 *third = tmp;
325 if (!*second)
326 data_.last_ptr_ = second;
327 }
328 };
329}
330
331#endif
332

source code of boost/libs/unordered/test/helpers/list.hpp