123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327 |
- // 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/limits.hpp>
- #include <functional>
- #include <iterator>
- 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
- {
- 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:
- typedef T value_type;
- typedef T* pointer;
- typedef T& reference;
- typedef int difference_type;
- typedef std::forward_iterator_tag iterator_category;
- 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
- {
- 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:
- typedef T value_type;
- typedef T const* pointer;
- typedef T const& reference;
- typedef int difference_type;
- typedef std::forward_iterator_tag iterator_category;
- 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 i, const_iterator j)
- {
- node** ptr = &data_.first_;
- while (*ptr != i.ptr_) {
- ptr = &(*ptr)->next_;
- }
- while (*ptr != j.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
|