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