// Singly-linked list container
#ifndef SLIST_H
#define SLIST_H

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <limits>
#include <memory>
#include "isinteger.h"

// Simple container for singly-linked lists.
template<typename T, typename Alloc = ::std::allocator<T> >
class slist {

  // Private type for a link (node) in the list.
  template<typename U>
  struct link {
    link* next;
    U value;
  };
  typedef link<T> link_type;

  class iterator_base : public std::iterator< ::std::forward_iterator_tag, T> {
    friend class slist;
  public:
    bool operator==(const iterator_base& i) const { return node_ == i.node_; }
    bool operator!=(const iterator_base& i) const { return ! (*this == i); }
  protected:
    iterator_base(const iterator_base& i) : prev_(i.prev_), node_(i.node_) {}
    iterator_base(typename slist::link_type* prev, typename slist::link_type* node)
    : prev_(prev), node_(node) {}
    // If node_ == 0, the iterator == end().
    typename slist::link_type* node_;
    // A pointer to the node before node_ is needed to support erase().
    // If prev_ == 0, the iterator points to the head of the list.
    typename slist::link_type* prev_;
  private:
    iterator_base();
  };

public:
  typedef typename Alloc::reference reference;
  typedef typename Alloc::pointer pointer;
  typedef Alloc allocator_type;
  typedef T value_type;
  typedef std::size_t size_type;
  typedef std::ptrdiff_t difference_type;

  class iterator : public iterator_base {
    friend class slist;
  public:
    iterator(const iterator& i) : iterator_base(i) {}
    iterator& operator++()                   { this->prev_ = this->node_; this->node_ = this->node_->next; return *this; }
    iterator  operator++(int)                { iterator tmp = *this; operator++(); return tmp; }
    T& operator*()                           { return this->node_->value; }
    T* operator->()                          { return &this->node_->value; }
  private:
    iterator(typename slist::link_type* prev, typename slist::link_type* node)
    : iterator_base(prev, node) {}
  };
  class const_iterator : public iterator_base {
    friend class slist;
  public:
    const_iterator(const iterator& i) : iterator_base(i) {}
    const_iterator(const const_iterator& i) : iterator_base(i) {}
    const_iterator& operator++()            { this->prev_ = this->node_; this->node_ = this->node_->next; return *this; }
    const_iterator  operator++(int)         { iterator tmp = *this; operator++(); return tmp; }
    T operator*()                           { return this->node_->value; }
    const T* operator->()                   { return &this->node_->value; }
  private:
    const_iterator(typename slist::link_type* prev, typename slist::link_type* node)
    : iterator_base(prev, node) {}
  };

  friend class iterator_base;
  friend class iterator;
  friend class const_iterator;

  slist(const slist& that);
  slist(const Alloc& alloc = Alloc());
  slist(size_type n, const T& x, const Alloc& alloc = Alloc());
  template<typename InputIter>
  slist(InputIter first, InputIter last, const Alloc& alloc = Alloc());
  ~slist()                             { clear(); }

  slist& operator=(const slist& that)  { return assign(that); }
  slist& assign(const slist& that)     { return assign(that.begin(), that.end()); }
  template<typename InputIter>
  slist& assign(InputIter first, InputIter last);

  allocator_type get_allocator() const { return alloc_; }

  iterator begin()                   { return iterator(0, head_); }
  const_iterator begin()       const { return const_iterator(0, head_); }
  iterator end()                     { return iterator(0, 0); }
  const_iterator end()         const { return const_iterator(0, 0); }

  void pop_front()                   { erase(begin()); }
  void push_front(const T& x)        { insert(begin(), x); }
  T front()                    const { return head_->value; }
  T& front()                         { return head_->value; }

  iterator insert(iterator p, const T& x);
  void insert(iterator p, size_type n, const T& x);
  template<typename InputIter>
  void insert(iterator p, InputIter first, InputIter last);

  iterator erase(iterator p);
  iterator erase(iterator first, iterator last);

  void clear()               { erase(begin(), end()); }
  bool empty()         const { return size() == 0; }
  size_type max_size() const { return ::std::numeric_limits<size_type>::max(); }
  void resize(size_type sz, const T& x = T());
  size_type size()     const { return count_; }
  void swap(slist& that);

private:
  typedef typename allocator_type::template rebind<link_type>::other link_allocator_type;

  link_type* newitem(const T& x, link_type* next = 0);
  void delitem(link_type* item);

  template<typename InputIter>
  void construct(InputIter first, InputIter last, is_integer_tag);

  template<typename InputIter>
  void construct(InputIter first, InputIter last, is_not_integer_tag);

  link_type* head_;
  link_type* tail_;
  allocator_type alloc_;
  link_allocator_type linkalloc_;
  std::size_t count_;
};

// Constructors
template<typename T, typename A>
slist<T,A>::slist(const slist& that)
: alloc_(that.get_allocator()), linkalloc_(link_allocator_type()),
  head_(0), tail_(0), count_(0)
{
  insert(begin(), that.begin(), that.end());
}

template<typename T, typename A>
slist<T,A>::slist(const A& alloc)
: alloc_(alloc), linkalloc_(link_allocator_type()),
  head_(0), tail_(0), count_(0)
{}

// Constructor
template<typename T, typename A>
slist<T,A>::slist(size_type n, const T& x, const A& alloc)
: alloc_(alloc), linkalloc_(link_allocator_type()),
  head_(0), tail_(0), count_(0)
{
  insert(begin(), n, x);
}

// Constructor. If InputIter is an integral type, the standard requires
// the constructor to interpret first and last as a count and value,
// and perform the slist(size_type, T) constructor. Use the is_integer
// trait to dispatch to the appropriate construct function, which does
// the real work.
template<typename T, typename A>
template<typename InputIter>
slist<T,A>::slist(InputIter first, InputIter last, const A& alloc)
: alloc_(alloc), linkalloc_(link_allocator_type()),
  head_(0), tail_(0), count_(0)
{
  construct(first, last, typename is_integer<InputIter>::tag());
}

template<typename T, typename A>
template<typename InputIter>
void slist<T,A>::construct(InputIter first, InputIter last, is_integer_tag)
{
  insert(begin(), static_cast<size_type>(first), static_cast<T>(last));
}

template<typename T, typename A>
template<typename InputIter>
void slist<T,A>::construct(InputIter first, InputIter last, is_not_integer_tag)
{
  insert(begin(), first, last);
}

// Assignment function.
template<typename T, typename A>
template<typename InputIter>
slist<T,A>& slist<T,A>::assign(InputIter first, InputIter last)
{
  clear();
  insert(begin(), first, last);
  return *this;
}

// Private function to allocate a new link node.
template<typename T, typename A>
typename slist<T,A>::link_type* slist<T,A>::newitem(const T& x, link_type* next)
{
  link_type* item = linkalloc_.allocate(1);
  item->next = next;
  alloc_.construct(&item->value, x);
  return item;
}

// Private function to release a link node.
template<typename T, typename A>
void slist<T,A>::delitem(link_type* item)
{
  alloc_.destroy(&item->value);
  linkalloc_.deallocate(item, 1);
}

// Basic insertion function. All insertions eventually find their way here.
// Inserting at the head of the list (p == begin()) must set the head_ member.
// Inserting at the end of the list (p == end()) means appending to the list,
// which updates the tail_'s next member, and then sets tail_.
// Anywhere else in the list requires updating p.prev_->next.
// Note that inserting into an empty list looks like inserting at end().
// Return an iterator that points to the newly inserted node.
template<typename T, typename A>
typename slist<T,A>::iterator slist<T,A>::insert(iterator p, const T& x)
{
  // Allocate the new link before changing any pointers.
  // If newitem throws an exception, the list is not affected.
  link_type* item = newitem(x, p.node_);
  if (p.node_ == 0) {
    p.prev_ = tail_;
    // at end
    if (tail_ == 0)
      head_ = tail_ = item; // empty list
    else {
      tail_->next = item;
      tail_ = item;
    }
  }
  else if (p.prev_ == 0)
    head_ = item;          // new head of list
  else
    p.prev_->next = item;
  p.node_ = item;
  ++count_;
  return p;
}

// Insert n copies of x.
template<typename T, typename A>
void slist<T,A>::insert(iterator p, size_type n, const T& x)
{
  iterator start(p);
  size_type i;

  try {
    for (i = 0; i < n; ++i)
      p = insert(p, x);
  } catch(...) {
    // insert can throw an exception such as bad_alloc
    // Rollback all insertions performed so far.
    p = start;
    while (i-- > 0)
      p = erase(p);
    throw;
  }
}

// Insert everything in [first, last).
template<typename T, typename A>
template<typename InputIter>
void slist<T,A>::insert(iterator p, InputIter first, InputIter last)
{
  InputIter save(first);
  iterator start(p);

  try {
    for (; first != last; ++first)
      insert(p, *first);
  } catch(...) {
    // insert can throw an exception such as bad_alloc
    // Rollback all insertions performed so far.
    start = p;
    for (InputIter i(save) ; i != first; ++i)
      p = erase(p);
    throw;
  }
}

// Erase the item at p. All erasures come here eventually.
// If erasing begin(), update head_.
// If erasing the last item in the list, update tail_.
// Update the iterator to point to the node after the one begin deleted.
template<typename T, typename A>
typename slist<T,A>::iterator slist<T,A>::erase(iterator p)
{
  link_type* item = p.node_;
  p.node_ = item->next;
  if (p.prev_ == 0)
    head_ = item->next;
  else
    p.prev_->next = item->next;
  if (item->next == 0)
    tail_ = p.prev_;
  --count_;
  delitem(item);
  return p;
}

// Erase all nodes in [first, last).
template<typename T, typename A>
typename slist<T,A>::iterator slist<T,A>::erase(iterator first, iterator last)
{
  while (first != last)
    first = erase(first);
  return first;
}

template<typename T, typename A>
void slist<T,A>::resize(size_type sz, const T& x)
{
  if (sz > size())
    insert(end(), sz-size(), x);
  else if (sz < size()) {
    iterator i = begin();
    advance(i, sz);
    erase(i, end());
  }
}

// Swap two lists in constant time by swapping pointers.
template<typename T, typename A>
void slist<T,A>::swap(slist& that)
{
  link_type* tmp_head = head_;
  link_type* tmp_tail = tail_;
  size_type  tmp_count = count_;
  head_ = that.head_;
  tail_ = that.tail_;
  count_ = that.count_;
  that.head_ = tmp_head;
  that.tail_ = tmp_tail;
  that.count_ = tmp_count;
}

// Comparison functions are straightforward.
template<typename T>
bool operator==(const slist<T>& a, const slist<T>& b)
{
  return a.size() == b.size() && ::std::equal(a.begin(), a.end(), b.begin());
}

template<typename T>
inline bool operator!=(const slist<T>& a, const slist<T>& b)
{
  return ! (a == b);
}

template<typename T>
bool operator<(const slist<T>& a, const slist<T>& b)
{
  return ::std::lexicographical_compare(a.begin(), a.end(), b.begin());
}

template<typename T>
inline bool operator<=(const slist<T>& a, const slist<T>& b)
{
  return ! (b < a);
}

template<typename T>
inline bool operator>(const slist<T>& a, const slist<T>& b)
{
  return b < a;
}

template<typename T>
inline bool operator>=(const slist<T>& a, const slist<T>& b)
{
  return ! (a < b);
}

template<typename T, typename A>
inline void swap(slist<T,A>& a, slist<T,A>& b)
{
  a.swap(b);
}

#endif // SLIST_H