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