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