]>
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 | ||
84 | template <typename T> | |
85 | class list_iterator | |
86 | : public std::iterator<std::forward_iterator_tag, T, int, T*, T&> | |
87 | { | |
88 | friend class list_const_iterator<T>; | |
89 | friend class test::list<T>; | |
90 | typedef list_node<T> node; | |
91 | typedef list_const_iterator<T> const_iterator; | |
92 | ||
93 | node* ptr_; | |
94 | ||
95 | public: | |
96 | list_iterator() : ptr_(0) {} | |
97 | explicit list_iterator(node* x) : ptr_(x) {} | |
98 | ||
99 | T& operator*() const { return ptr_->value_; } | |
100 | T* operator->() const { return &ptr_->value_; } | |
101 | list_iterator& operator++() | |
102 | { | |
103 | ptr_ = ptr_->next_; | |
104 | return *this; | |
105 | } | |
106 | list_iterator operator++(int) | |
107 | { | |
108 | list_iterator tmp = *this; | |
109 | ptr_ = ptr_->next_; | |
110 | return tmp; | |
111 | } | |
112 | bool operator==(const_iterator y) const { return ptr_ == y.ptr_; } | |
113 | bool operator!=(const_iterator y) const { return ptr_ != y.ptr_; } | |
114 | }; | |
115 | ||
116 | template <typename T> | |
117 | class list_const_iterator : public std::iterator<std::forward_iterator_tag, | |
118 | T, int, T const*, T const&> | |
119 | { | |
120 | friend class list_iterator<T>; | |
121 | friend class test::list<T>; | |
122 | typedef list_node<T> node; | |
123 | typedef list_iterator<T> iterator; | |
124 | typedef list_const_iterator<T> const_iterator; | |
125 | ||
126 | node* ptr_; | |
127 | ||
128 | public: | |
129 | list_const_iterator() : ptr_(0) {} | |
130 | list_const_iterator(list_iterator<T> const& x) : ptr_(x.ptr_) {} | |
131 | ||
132 | T const& operator*() const { return ptr_->value_; } | |
133 | T const* operator->() const { return &ptr_->value_; } | |
134 | ||
135 | list_const_iterator& operator++() | |
136 | { | |
137 | ptr_ = ptr_->next_; | |
138 | return *this; | |
139 | } | |
140 | ||
141 | list_const_iterator operator++(int) | |
142 | { | |
143 | list_const_iterator tmp = *this; | |
144 | ptr_ = ptr_->next_; | |
145 | return tmp; | |
146 | } | |
147 | ||
148 | bool operator==(const_iterator y) const { return ptr_ == y.ptr_; } | |
149 | ||
150 | bool operator!=(const_iterator y) const { return ptr_ != y.ptr_; } | |
151 | }; | |
152 | } | |
153 | ||
154 | template <typename T> class list | |
155 | { | |
156 | typedef test::test_detail::list_data<T> data; | |
157 | typedef test::test_detail::list_node<T> node; | |
158 | data data_; | |
159 | ||
160 | public: | |
161 | typedef T value_type; | |
162 | typedef value_type& reference; | |
163 | typedef value_type const& const_reference; | |
164 | typedef unsigned int size_type; | |
7c673cae | 165 | |
b32b8144 FG |
166 | typedef test::test_detail::list_iterator<T> iterator; |
167 | typedef test::test_detail::list_const_iterator<T> const_iterator; | |
168 | ||
169 | list() : data_() {} | |
170 | ||
171 | list(list const& other) : data_() { insert(other.begin(), other.end()); } | |
172 | ||
173 | template <class InputIterator> | |
174 | list(InputIterator i, InputIterator j) : data_() | |
7c673cae | 175 | { |
b32b8144 | 176 | insert(i, j); |
7c673cae FG |
177 | } |
178 | ||
b32b8144 | 179 | list& operator=(list const& other) |
7c673cae | 180 | { |
b32b8144 FG |
181 | clear(); |
182 | insert(other.begin(), other.end()); | |
183 | return *this; | |
7c673cae FG |
184 | } |
185 | ||
b32b8144 FG |
186 | iterator begin() { return iterator(data_.first_); } |
187 | iterator end() { return iterator(); } | |
188 | const_iterator begin() const { return iterator(data_.first_); } | |
189 | const_iterator end() const { return iterator(); } | |
190 | const_iterator cbegin() const { return iterator(data_.first_); } | |
191 | const_iterator cend() const { return iterator(); } | |
7c673cae | 192 | |
b32b8144 FG |
193 | template <class InputIterator> void insert(InputIterator i, InputIterator j) |
194 | { | |
195 | for (; i != j; ++i) | |
196 | push_back(*i); | |
197 | } | |
7c673cae | 198 | |
b32b8144 | 199 | void push_front(value_type const& v) |
7c673cae | 200 | { |
b32b8144 FG |
201 | data_.first_ = new node(v, data_.first_); |
202 | if (!data_.size_) | |
203 | data_.last_ptr_ = &(*data_.last_ptr_)->next_; | |
204 | ++data_.size_; | |
7c673cae FG |
205 | } |
206 | ||
b32b8144 | 207 | void push_back(value_type const& v) |
7c673cae | 208 | { |
b32b8144 FG |
209 | *data_.last_ptr_ = new node(v); |
210 | data_.last_ptr_ = &(*data_.last_ptr_)->next_; | |
211 | ++data_.size_; | |
212 | } | |
7c673cae | 213 | |
b32b8144 FG |
214 | void clear() |
215 | { | |
216 | while (data_.first_) { | |
217 | node* tmp = data_.first_; | |
218 | data_.first_ = data_.first_->next_; | |
219 | --data_.size_; | |
220 | delete tmp; | |
221 | } | |
222 | data_.last_ptr_ = &data_.first_; | |
223 | } | |
7c673cae | 224 | |
b32b8144 FG |
225 | void erase(const_iterator i, const_iterator j) |
226 | { | |
227 | node** ptr = &data_.first_; | |
7c673cae | 228 | |
b32b8144 FG |
229 | while (*ptr != i.ptr_) { |
230 | ptr = &(*ptr)->next_; | |
231 | } | |
7c673cae | 232 | |
b32b8144 FG |
233 | while (*ptr != j.ptr_) { |
234 | node* to_delete = *ptr; | |
235 | *ptr = (*ptr)->next_; | |
236 | --data_.size_; | |
237 | delete to_delete; | |
238 | } | |
7c673cae | 239 | |
b32b8144 FG |
240 | if (!*ptr) |
241 | data_.last_ptr_ = ptr; | |
242 | } | |
7c673cae | 243 | |
b32b8144 | 244 | bool empty() const { return !data_.size_; } |
7c673cae | 245 | |
b32b8144 | 246 | size_type size() const { return data_.size_; } |
7c673cae | 247 | |
b32b8144 | 248 | void sort() { sort(std::less<T>()); } |
7c673cae | 249 | |
b32b8144 FG |
250 | template <typename Less> void sort(Less less = Less()) |
251 | { | |
252 | if (!empty()) | |
253 | merge_sort( | |
254 | &data_.first_, (std::numeric_limits<size_type>::max)(), less); | |
255 | } | |
7c673cae | 256 | |
b32b8144 FG |
257 | bool operator==(list const& y) const |
258 | { | |
259 | return size() == y.size() && test::equal(begin(), end(), y.begin()); | |
260 | } | |
7c673cae | 261 | |
b32b8144 | 262 | bool operator!=(list const& y) const { return !(*this == y); } |
7c673cae | 263 | |
b32b8144 FG |
264 | private: |
265 | template <typename Less> | |
266 | node** merge_sort(node** l, size_type recurse_limit, Less less) | |
267 | { | |
268 | node** ptr = &(*l)->next_; | |
269 | for (size_type count = 0; count < recurse_limit && *ptr; ++count) { | |
270 | ptr = merge_adjacent_ranges(l, ptr, merge_sort(ptr, count, less), less); | |
271 | } | |
272 | return ptr; | |
273 | } | |
7c673cae | 274 | |
b32b8144 FG |
275 | template <typename Less> |
276 | node** merge_adjacent_ranges( | |
277 | node** first, node** second, node** third, Less less) | |
278 | { | |
279 | for (;;) { | |
280 | for (;;) { | |
281 | if (first == second) | |
282 | return third; | |
283 | if (less((*second)->value_, (*first)->value_)) | |
284 | break; | |
285 | first = &(*first)->next_; | |
7c673cae FG |
286 | } |
287 | ||
b32b8144 FG |
288 | swap_adjacent_ranges(first, second, third); |
289 | first = &(*first)->next_; | |
7c673cae | 290 | |
b32b8144 FG |
291 | // Since the two ranges we just swapped, the order is now: |
292 | // first...third...second | |
7c673cae | 293 | |
b32b8144 FG |
294 | for (;;) { |
295 | if (first == third) | |
296 | return second; | |
297 | if (!less((*first)->value_, (*third)->value_)) | |
298 | break; | |
299 | first = &(*first)->next_; | |
7c673cae FG |
300 | } |
301 | ||
b32b8144 FG |
302 | swap_adjacent_ranges(first, third, second); |
303 | first = &(*first)->next_; | |
304 | } | |
305 | } | |
7c673cae | 306 | |
b32b8144 FG |
307 | void swap_adjacent_ranges(node** first, node** second, node** third) |
308 | { | |
309 | node* tmp = *first; | |
310 | *first = *second; | |
311 | *second = *third; | |
312 | *third = tmp; | |
313 | if (!*second) | |
314 | data_.last_ptr_ = second; | |
315 | } | |
316 | }; | |
7c673cae FG |
317 | } |
318 | ||
319 | #endif |