]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
7c673cae | 15 | #include <functional> |
b32b8144 FG |
16 | #include <iterator> |
17 | ||
18 | namespace 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 | ||
11fdf7f2 | 84 | template <typename T> class list_iterator |
b32b8144 FG |
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: | |
11fdf7f2 TL |
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 | ||
b32b8144 FG |
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 | } | |
1e59de90 TL |
116 | |
117 | bool operator==(list_iterator y) const { return ptr_ == y.ptr_; } | |
118 | bool operator!=(list_iterator y) const { return ptr_ != y.ptr_; } | |
119 | ||
b32b8144 FG |
120 | bool operator==(const_iterator y) const { return ptr_ == y.ptr_; } |
121 | bool operator!=(const_iterator y) const { return ptr_ != y.ptr_; } | |
122 | }; | |
123 | ||
11fdf7f2 | 124 | template <typename T> class list_const_iterator |
b32b8144 FG |
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: | |
11fdf7f2 TL |
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 | ||
b32b8144 FG |
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; | |
7c673cae | 177 | |
b32b8144 FG |
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_() | |
7c673cae | 187 | { |
b32b8144 | 188 | insert(i, j); |
7c673cae FG |
189 | } |
190 | ||
b32b8144 | 191 | list& operator=(list const& other) |
7c673cae | 192 | { |
b32b8144 FG |
193 | clear(); |
194 | insert(other.begin(), other.end()); | |
195 | return *this; | |
7c673cae FG |
196 | } |
197 | ||
b32b8144 FG |
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(); } | |
7c673cae | 204 | |
b32b8144 FG |
205 | template <class InputIterator> void insert(InputIterator i, InputIterator j) |
206 | { | |
207 | for (; i != j; ++i) | |
208 | push_back(*i); | |
209 | } | |
7c673cae | 210 | |
b32b8144 | 211 | void push_front(value_type const& v) |
7c673cae | 212 | { |
b32b8144 FG |
213 | data_.first_ = new node(v, data_.first_); |
214 | if (!data_.size_) | |
215 | data_.last_ptr_ = &(*data_.last_ptr_)->next_; | |
216 | ++data_.size_; | |
7c673cae FG |
217 | } |
218 | ||
b32b8144 | 219 | void push_back(value_type const& v) |
7c673cae | 220 | { |
b32b8144 FG |
221 | *data_.last_ptr_ = new node(v); |
222 | data_.last_ptr_ = &(*data_.last_ptr_)->next_; | |
223 | ++data_.size_; | |
224 | } | |
7c673cae | 225 | |
b32b8144 FG |
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 | } | |
7c673cae | 236 | |
b32b8144 FG |
237 | void erase(const_iterator i, const_iterator j) |
238 | { | |
239 | node** ptr = &data_.first_; | |
7c673cae | 240 | |
b32b8144 FG |
241 | while (*ptr != i.ptr_) { |
242 | ptr = &(*ptr)->next_; | |
243 | } | |
7c673cae | 244 | |
b32b8144 FG |
245 | while (*ptr != j.ptr_) { |
246 | node* to_delete = *ptr; | |
247 | *ptr = (*ptr)->next_; | |
248 | --data_.size_; | |
249 | delete to_delete; | |
250 | } | |
7c673cae | 251 | |
b32b8144 FG |
252 | if (!*ptr) |
253 | data_.last_ptr_ = ptr; | |
254 | } | |
7c673cae | 255 | |
b32b8144 | 256 | bool empty() const { return !data_.size_; } |
7c673cae | 257 | |
b32b8144 | 258 | size_type size() const { return data_.size_; } |
7c673cae | 259 | |
b32b8144 | 260 | void sort() { sort(std::less<T>()); } |
7c673cae | 261 | |
b32b8144 FG |
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 | } | |
7c673cae | 268 | |
b32b8144 FG |
269 | bool operator==(list const& y) const |
270 | { | |
271 | return size() == y.size() && test::equal(begin(), end(), y.begin()); | |
272 | } | |
7c673cae | 273 | |
b32b8144 | 274 | bool operator!=(list const& y) const { return !(*this == y); } |
7c673cae | 275 | |
b32b8144 FG |
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 | } | |
7c673cae | 286 | |
b32b8144 FG |
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_; | |
7c673cae FG |
298 | } |
299 | ||
b32b8144 FG |
300 | swap_adjacent_ranges(first, second, third); |
301 | first = &(*first)->next_; | |
7c673cae | 302 | |
b32b8144 FG |
303 | // Since the two ranges we just swapped, the order is now: |
304 | // first...third...second | |
7c673cae | 305 | |
b32b8144 FG |
306 | for (;;) { |
307 | if (first == third) | |
308 | return second; | |
309 | if (!less((*first)->value_, (*third)->value_)) | |
310 | break; | |
311 | first = &(*first)->next_; | |
7c673cae FG |
312 | } |
313 | ||
b32b8144 FG |
314 | swap_adjacent_ranges(first, third, second); |
315 | first = &(*first)->next_; | |
316 | } | |
317 | } | |
7c673cae | 318 | |
b32b8144 FG |
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 | }; | |
7c673cae FG |
329 | } |
330 | ||
331 | #endif |