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/iterator.hpp>
15 #include <boost/limits.hpp>
16 #include <functional>
17 
18 namespace test
19 {
20     template <typename It1, typename It2>
equal(It1 begin,It1 end,It2 compare)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>
equal(It1 begin,It1 end,It2 compare,Pred predicate)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 
list_node(T const & v)55             list_node(T const& v) : value_(v), next_(0) {}
list_node(T const & v,list_node * n)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 
list_data()70             list_data() : first_(0), last_ptr_(&first_), size_(0) {}
71 
~list_data()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 boost::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:
list_iterator()97             list_iterator() : ptr_(0) {}
list_iterator(node * x)98             explicit list_iterator(node* x) : ptr_(x) {}
99 
operator *() const100             T& operator*() const { return ptr_->value_; }
operator ->() const101             T* operator->() const { return &ptr_->value_; }
operator ++()102             list_iterator& operator++() {
103                 ptr_ = ptr_->next_; return *this; }
operator ++(int)104             list_iterator operator++(int) {
105                 list_iterator tmp = *this; ptr_ = ptr_->next_; return tmp; }
operator ==(const_iterator y) const106             bool operator==(const_iterator y) const { return ptr_ == y.ptr_; }
operator !=(const_iterator y) const107             bool operator!=(const_iterator y) const { return ptr_ != y.ptr_; }
108         };
109 
110         template <typename T>
111         class list_const_iterator
112             : public boost::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:
list_const_iterator()124             list_const_iterator() : ptr_(0) {}
list_const_iterator(list_iterator<T> const & x)125             list_const_iterator(list_iterator<T> const& x) : ptr_(x.ptr_) {}
126 
operator *() const127             T const& operator*() const { return ptr_->value_; }
operator ->() const128             T const* operator->() const { return &ptr_->value_; }
129 
operator ++()130             list_const_iterator& operator++()
131             {
132                 ptr_ = ptr_->next_;
133                 return *this;
134             }
135 
operator ++(int)136             list_const_iterator operator++(int)
137             {
138                 list_const_iterator tmp = *this;
139                 ptr_ = ptr_->next_;
140                 return tmp;
141             }
142 
operator ==(const_iterator y) const143             bool operator==(const_iterator y) const
144             {
145                 return ptr_ == y.ptr_;
146             }
147 
operator !=(const_iterator y) const148             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 
list()170         list() : data_() {}
171 
list(list const & other)172         list(list const& other) : data_() {
173             insert(other.begin(), other.end());
174         }
175 
176         template <class InputIterator>
list(InputIterator i,InputIterator j)177         list(InputIterator i, InputIterator j) : data_() {
178             insert(i, j);
179         }
180 
operator =(list const & other)181         list& operator=(list const& other) {
182             clear();
183             insert(other.begin(), other.end());
184             return *this;
185         }
186 
begin()187         iterator begin() { return iterator(data_.first_); }
end()188         iterator end() { return iterator(); }
begin() const189         const_iterator begin() const { return iterator(data_.first_); }
end() const190         const_iterator end() const { return iterator(); }
cbegin() const191         const_iterator cbegin() const { return iterator(data_.first_); }
cend() const192         const_iterator cend() const { return iterator(); }
193 
194         template <class InputIterator>
insert(InputIterator i,InputIterator j)195         void insert(InputIterator i, InputIterator j) {
196             for(; i != j; ++i)
197                 push_back(*i);
198         }
199 
push_front(value_type const & v)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 
push_back(value_type const & v)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 
clear()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 
erase(const_iterator i,const_iterator j)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 
empty() const239         bool empty() const {
240             return !data_.size_;
241         }
242 
size() const243         size_type size() const {
244             return data_.size_;
245         }
246 
sort()247         void sort() {
248             sort(std::less<T>());
249         }
250 
251         template <typename Less>
sort(Less less=Less ())252         void sort(Less less = Less()) {
253             if(!empty()) merge_sort(&data_.first_,
254                     (std::numeric_limits<size_type>::max)(), less);
255         }
256 
operator ==(list const & y) const257         bool operator==(list const& y) const {
258             return size() == y.size() &&
259                 test::equal(begin(), end(), y.begin());
260         }
261 
operator !=(list const & y) const262         bool operator!=(list const& y) const {
263             return !(*this == y);
264         }
265 
266     private:
267         template <typename Less>
merge_sort(node ** l,size_type recurse_limit,Less 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>
merge_adjacent_ranges(node ** first,node ** second,node ** third,Less 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 
swap_adjacent_ranges(node ** first,node ** second,node ** third)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
319