// 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