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