| |
| // Copyright 2008-2009 Daniel James. |
| // Distributed under the Boost Software License, Version 1.0. (See accompanying |
| // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
| |
| // Gratuitous single linked list. |
| // |
| // Sadly some STL implementations aren't up to scratch and I need a simple |
| // cross-platform container. So here it is. |
| |
| #if !defined(UNORDERED_TEST_LIST_HEADER) |
| #define UNORDERED_TEST_LIST_HEADER |
| |
| #include <boost/iterator.hpp> |
| #include <boost/limits.hpp> |
| #include <functional> |
| |
| namespace test |
| { |
| template <typename It1, typename It2> |
| bool equal(It1 begin, It1 end, It2 compare) |
| { |
| for(;begin != end; ++begin, ++compare) |
| if(*begin != *compare) return false; |
| return true; |
| } |
| |
| template <typename It1, typename It2, typename Pred> |
| bool equal(It1 begin, It1 end, It2 compare, Pred predicate) |
| { |
| for(;begin != end; ++begin, ++compare) |
| if(!predicate(*begin, *compare)) return false; |
| return true; |
| } |
| |
| |
| template <typename T> class list; |
| |
| namespace test_detail |
| { |
| template <typename T> class list_node; |
| template <typename T> class list_data; |
| template <typename T> class list_iterator; |
| template <typename T> class list_const_iterator; |
| |
| template <typename T> |
| class list_node |
| { |
| list_node(list_node const&); |
| list_node& operator=(list_node const&); |
| public: |
| T value_; |
| list_node* next_; |
| |
| list_node(T const& v) : value_(v), next_(0) {} |
| list_node(T const& v, list_node* n) : value_(v), next_(n) {} |
| }; |
| |
| template <typename T> |
| class list_data |
| { |
| public: |
| typedef list_node<T> node; |
| typedef unsigned int size_type; |
| |
| node* first_; |
| node** last_ptr_; |
| size_type size_; |
| |
| list_data() : first_(0), last_ptr_(&first_), size_(0) {} |
| |
| ~list_data() { |
| while(first_) { |
| node* tmp = first_; |
| first_ = first_->next_; |
| delete tmp; |
| } |
| } |
| private: |
| list_data(list_data const&); |
| list_data& operator=(list_data const&); |
| }; |
| |
| template <typename T> |
| class list_iterator |
| : public boost::iterator< |
| std::forward_iterator_tag, T, |
| int, T*, T&> |
| { |
| friend class list_const_iterator<T>; |
| friend class test::list<T>; |
| typedef list_node<T> node; |
| typedef list_const_iterator<T> const_iterator; |
| |
| node* ptr_; |
| public: |
| list_iterator() : ptr_(0) {} |
| explicit list_iterator(node* x) : ptr_(x) {} |
| |
| T& operator*() const { return ptr_->value_; } |
| T* operator->() const { return &ptr_->value_; } |
| list_iterator& operator++() { |
| ptr_ = ptr_->next_; return *this; } |
| list_iterator operator++(int) { |
| list_iterator tmp = *this; ptr_ = ptr_->next_; return tmp; } |
| bool operator==(const_iterator y) const { return ptr_ == y.ptr_; } |
| bool operator!=(const_iterator y) const { return ptr_ != y.ptr_; } |
| }; |
| |
| template <typename T> |
| class list_const_iterator |
| : public boost::iterator< |
| std::forward_iterator_tag, T, |
| int, T const*, T const&> |
| { |
| friend class list_iterator<T>; |
| friend class test::list<T>; |
| typedef list_node<T> node; |
| typedef list_iterator<T> iterator; |
| typedef list_const_iterator<T> const_iterator; |
| |
| node* ptr_; |
| public: |
| list_const_iterator() : ptr_(0) {} |
| list_const_iterator(list_iterator<T> const& x) : ptr_(x.ptr_) {} |
| |
| T const& operator*() const { return ptr_->value_; } |
| T const* operator->() const { return &ptr_->value_; } |
| |
| list_const_iterator& operator++() |
| { |
| ptr_ = ptr_->next_; |
| return *this; |
| } |
| |
| list_const_iterator operator++(int) |
| { |
| list_const_iterator tmp = *this; |
| ptr_ = ptr_->next_; |
| return tmp; |
| } |
| |
| bool operator==(const_iterator y) const |
| { |
| return ptr_ == y.ptr_; |
| } |
| |
| bool operator!=(const_iterator y) const |
| { |
| return ptr_ != y.ptr_; |
| } |
| }; |
| } |
| |
| template <typename T> |
| class list |
| { |
| typedef test::test_detail::list_data<T> data; |
| typedef test::test_detail::list_node<T> node; |
| data data_; |
| public: |
| typedef T value_type; |
| typedef value_type& reference; |
| typedef value_type const& const_reference; |
| typedef unsigned int size_type; |
| |
| typedef test::test_detail::list_iterator<T> iterator; |
| typedef test::test_detail::list_const_iterator<T> const_iterator; |
| |
| list() : data_() {} |
| |
| list(list const& other) : data_() { |
| insert(other.begin(), other.end()); |
| } |
| |
| template <class InputIterator> |
| list(InputIterator i, InputIterator j) : data_() { |
| insert(i, j); |
| } |
| |
| list& operator=(list const& other) { |
| clear(); |
| insert(other.begin(), other.end()); |
| return *this; |
| } |
| |
| iterator begin() { return iterator(data_.first_); } |
| iterator end() { return iterator(); } |
| const_iterator begin() const { return iterator(data_.first_); } |
| const_iterator end() const { return iterator(); } |
| const_iterator cbegin() const { return iterator(data_.first_); } |
| const_iterator cend() const { return iterator(); } |
| |
| template <class InputIterator> |
| void insert(InputIterator i, InputIterator j) { |
| for(; i != j; ++i) |
| push_back(*i); |
| } |
| |
| void push_front(value_type const& v) { |
| data_.first_ = new node(v, data_.first_); |
| if(!data_.size_) data_.last_ptr_ = &(*data_.last_ptr_)->next_; |
| ++data_.size_; |
| } |
| |
| void push_back(value_type const& v) { |
| *data_.last_ptr_ = new node(v); |
| data_.last_ptr_ = &(*data_.last_ptr_)->next_; |
| ++data_.size_; |
| } |
| |
| void clear() { |
| while(data_.first_) { |
| node* tmp = data_.first_; |
| data_.first_ = data_.first_->next_; |
| --data_.size_; |
| delete tmp; |
| } |
| data_.last_ptr_ = &data_.first_; |
| } |
| |
| void erase(const_iterator start, const_iterator end) { |
| node** ptr = &data_.first_; |
| |
| while(*ptr != start.ptr_) { |
| ptr = &(*ptr)->next_; |
| } |
| |
| while(*ptr != end.ptr_) { |
| node* to_delete = *ptr; |
| *ptr = (*ptr)->next_; |
| --data_.size_; |
| delete to_delete; |
| } |
| |
| if(!*ptr) data_.last_ptr_ = ptr; |
| } |
| |
| bool empty() const { |
| return !data_.size_; |
| } |
| |
| size_type size() const { |
| return data_.size_; |
| } |
| |
| void sort() { |
| sort(std::less<T>()); |
| } |
| |
| template <typename Less> |
| void sort(Less less = Less()) { |
| if(!empty()) merge_sort(&data_.first_, |
| (std::numeric_limits<size_type>::max)(), less); |
| } |
| |
| bool operator==(list const& y) const { |
| return size() == y.size() && |
| test::equal(begin(), end(), y.begin()); |
| } |
| |
| bool operator!=(list const& y) const { |
| return !(*this == y); |
| } |
| |
| private: |
| template <typename Less> |
| node** merge_sort(node** l, size_type recurse_limit, Less less) |
| { |
| node** ptr = &(*l)->next_; |
| for(size_type count = 0; count < recurse_limit && *ptr; ++count) |
| { |
| ptr = merge_adjacent_ranges(l, ptr, |
| merge_sort(ptr, count, less), less); |
| } |
| return ptr; |
| } |
| |
| template <typename Less> |
| node** merge_adjacent_ranges(node** first, node** second, |
| node** third, Less less) |
| { |
| for(;;) { |
| for(;;) { |
| if(first == second) return third; |
| if(less((*second)->value_, (*first)->value_)) break; |
| first = &(*first)->next_; |
| } |
| |
| swap_adjacent_ranges(first, second, third); |
| first = &(*first)->next_; |
| |
| // Since the two ranges we just swapped, the order is now: |
| // first...third...second |
| |
| for(;;) { |
| if(first == third) return second; |
| if(!less((*first)->value_, (*third)->value_)) break; |
| first = &(*first)->next_; |
| } |
| |
| swap_adjacent_ranges(first, third, second); |
| first = &(*first)->next_; |
| } |
| } |
| |
| void swap_adjacent_ranges(node** first, node** second, node** third) |
| { |
| node* tmp = *first; |
| *first = *second; |
| *second = *third; |
| *third = tmp; |
| if(!*second) data_.last_ptr_ = second; |
| } |
| }; |
| } |
| |
| #endif |