/*  Copyright (C) 2004 Garrett A. Kajmowicz
 *
 * This file is part of the uClibc++ Library.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#include <memory>
#include <iterator>
#include <algorithm>

#ifndef __STD_HEADER_LIST
#define __STD_HEADER_LIST 1

#pragma GCC visibility push(default)

extern "C++"
{

namespace std
{

  template <class T, class Allocator = allocator<T> > class _UCXXEXPORT list {
  public:
    typedef typename Allocator::reference reference;
    typedef typename Allocator::const_reference const_reference;
    typedef typename Allocator::size_type size_type;
    typedef typename Allocator::difference_type difference_type;
    typedef T value_type;
    typedef Allocator allocator_type;
    typedef typename Allocator::pointer pointer;
    typedef typename Allocator::const_pointer const_pointer;

  protected:
    class node;
    class iter_list;

    node * list_start;
    node * list_end;
    size_type elements;
    Allocator a;

  public:
    typedef iter_list        iterator;
    typedef iter_list        const_iterator;
    typedef std::reverse_iterator<iterator>    reverse_iterator;
    typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;

    explicit list(const Allocator& = Allocator());
    explicit list(size_type n, const T& value = T(), const Allocator& = Allocator());
    template <class InputIterator> list(InputIterator first, InputIterator last,
      const Allocator& al= Allocator());
    list(const list<T,Allocator>& x);
    ~list();

    list<T,Allocator>& operator=(const list<T,Allocator>& x)
    {
      if (&x == this)
      {
        return *this;
      }

      clear();
      iterator i = x.begin();
      while (i != x.end())
      {
        push_back(*i);
        ++i;
      }

      return *this;
    }

    template <class InputIterator> void assign(InputIterator first, InputIterator last);
    template <class Size, class U> void assign(Size n, const U& u = U());
    allocator_type get_allocator() const;

    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;
    reverse_iterator rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator rend();
    const_reverse_iterator rend() const;

    bool empty() const;
    size_type size() const;
    size_type max_size() const;
    void resize(size_type sz, T c = T());

    reference front();
    const_reference front() const;
    reference back();
    const_reference back() const;

    void push_front(const T& x);
    void pop_front();
    void push_back(const T& x);
    void pop_back();
    iterator insert(iterator position, const T& x = T());
    void insert(iterator position, size_type n, const T& x);
    template <class InputIterator> void insert(iterator position, InputIterator first, InputIterator last);
    iterator erase(iterator position);
    iterator erase(iterator position, iterator last);
    void swap(list<T,Allocator>&);
    void clear();

    void splice(iterator position, list<T,Allocator>& x);
    void splice(iterator position, list<T,Allocator>& x, iterator i);
    void splice(iterator position, list<T,Allocator>& x, iterator first, iterator last);
    void remove(const T& value);
    template <class Predicate> void remove_if (Predicate pred);
    void unique();
    template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
    void merge(list<T,Allocator>& x);
    template <class Compare> void merge(list<T,Allocator>& x, Compare comp);
    void sort();
    template <class Compare> void sort(Compare comp);
    void reverse();

  protected:
    void swap_nodes(node * x, node * y);
  };

  // Implementations of List

  // List node

  template <class T, class Allocator> class _UCXXEXPORT list<T, Allocator>::node
  {
  public:
    node * previous;
    node * next;
    T * val;

    node(): previous(0), next(0), val(0){ }

    node(const T & t): previous(0), next(0), val(0)
    {
      val = new T(t);
      //FIXME use allocator somehow but only call constructor once
    }

    node(const T & t, node * p, node * n): previous(p), next(n), val(0)
    {
      val = new T(t);
    }

    ~node(){ }
  };

  // List iterator

  template <class T, class Allocator> class _UCXXEXPORT list<T, Allocator>::iter_list
    : public std::iterator<
      bidirectional_iterator_tag,
      T,
      typename Allocator::difference_type,
      typename Allocator::pointer,
      typename Allocator::reference
    >
  {
  private:
    node * current;
  public:
    iter_list():current(0) { }
    iter_list(typename list<T, Allocator>::node * n): current(n) { }
    iter_list(const list<T, Allocator>::iter_list & l): current(l.current) { }
    ~iter_list(){ }

    iter_list & operator=(const list<T, Allocator>::iter_list & right)
    {
      current = right.current;
      return *this;
    }

    T & operator*()
    {
      return *(current->val);
    }

    T * operator->()
    {
      return current->val;
    }

    const T & operator*() const
    {
      return *current->val;
    }

    const T * operator->() const
    {
      return current->val;
    }

    bool operator==(const list<T, Allocator>::iter_list & right) const
    {
      return (current == right.current);
    }

    bool operator!=(const list<T, Allocator>::iter_list & right) const
    {
      return (current != right.current);
    }

    iter_list & operator++()
    {
      current = current->next;
      return *this;
    }

    iter_list operator++(int)
    {
      iter_list temp(current);
      current = current->next;
      return temp;
    }

    iter_list & operator--()
    {
      current = current->previous;
      return *this;
    }

    iter_list operator--(int)
    {
      iter_list temp(current);
      current = current->previous;
      return temp;
    }

    node *link_struct()
    {
      return current;
    }

    iter_list & operator+=(unsigned int n)
    {
      for (unsigned int i = 0; i < n; ++i)
      {
        current = current->next;
      }

      return *this;
    }

    iter_list & operator-=(unsigned int n)
    {
      for (unsigned int i = 0; i < n; ++i)
      {
        current = current->previous;
      }

      return *this;
    }
  };

  template<class T, class Allocator> list<T, Allocator>::list(const Allocator& al)
    :list_start(0), list_end(0), elements(0), a(al)
  {
    // End node

    list_start = new node();
    list_end = list_start;
    return;
  }

  template<class T, class Allocator> list<T, Allocator>::list
    (typename Allocator::size_type n, const T& value, const Allocator& al)
    :list_start(0), list_end(0), elements(0), a(al)
  {
    // End node

    list_start = new node();
    list_end = list_start;

    for (typename Allocator::size_type i = 0; i < n ; ++i)
    {
      push_back(value);
    }
  }

  template<class T, class Allocator> template <class InputIterator>
    list<T, Allocator>::list
    (InputIterator first, InputIterator last, const Allocator& al)
    : list_start(0), list_end(0), elements(0), a(al)
  {
    list_start = new node();
    list_end = list_start;
    while (first != last)
    {
      push_back(*first);
      ++first;
    }
  }

  template<class T, class Allocator> list<T, Allocator>::list(const list<T,Allocator>& x)
    : list_start(0), list_end(0), elements(0), a(x.a)
  {
    list_start = new node();
    list_end = list_start;

    iterator i = x.begin();
    while (i != x.end())
    {
      push_back(*i);
      ++i;
    }
  }

  template<class T, class Allocator> list<T, Allocator>::~list(){
    while (elements > 0)
    {
      pop_front();
    }

    delete list_start->val;
#ifdef CONFIG_DEBUG_LIB
    list_start->val = 0;
#endif
    delete list_start;
#ifdef CONFIG_DEBUG_LIB
    list_start = 0;
    list_end = 0;
#endif
  }

  template<class T, class Allocator> void list<T, Allocator>::swap_nodes(node * x, node * y)
  {
    T * v = x->val;
    x->val = y->val;
    y->val = v;
  }

  template<class T, class Allocator> typename list<T, Allocator>::iterator
    list<T, Allocator>::begin()
  {
    return iterator(list_start);
  }

  template<class T, class Allocator> typename list<T, Allocator>::const_iterator
    list<T, Allocator>::begin() const
  {
    return const_iterator(list_start);
  }

  template<class T, class Allocator> typename list<T, Allocator>::iterator
    list<T, Allocator>::end()
  {
    return iterator(list_end);
  }

  template<class T, class Allocator> typename list<T, Allocator>::const_iterator
    list<T, Allocator>::end() const
  {
    return const_iterator(list_end);
  }

  template<class T, class Allocator> typename list<T, Allocator>::reverse_iterator
    list<T, Allocator>::rbegin()
  {
    return reverse_iterator(end());
  }

  template<class T, class Allocator> typename list<T, Allocator>::const_reverse_iterator
    list<T, Allocator>::rbegin() const
  {
    return const_reverse_iterator(end());
  }

  template<class T, class Allocator> typename list<T, Allocator>::reverse_iterator
    list<T, Allocator>::rend()
  {
    return reverse_iterator(begin());
  }

  template<class T, class Allocator> typename list<T, Allocator>::const_reverse_iterator
    list<T, Allocator>::rend() const
  {
    return const_reverse_iterator(begin());
  }

  template<class T, class Allocator> bool list<T, Allocator>::empty() const{
    return (elements == 0);
  }

  template<class T, class Allocator> typename list<T, Allocator>::size_type list<T, Allocator>::size() const{
    return elements;
  }

  template<class T, class Allocator> typename list<T, Allocator>::size_type list<T, Allocator>::max_size() const
  {
    return ((size_type)(-1)) / (sizeof(T) + sizeof(node));
  }

  template<class T, class Allocator> void list<T, Allocator>::resize(typename Allocator::size_type sz, T c)
  {
//  if (sz > elements)
//  {
      for (typename Allocator::size_type i = elements; i < sz; ++i)
      {
        push_back(c);
      }
//  }
//  if (sz < elements)
//  {
      for (typename Allocator::size_type i = elements; i > sz; --i)
      {
        pop_back();
      }
//  }
  }

  template<class T, class Allocator> typename list<T, Allocator>::reference list<T, Allocator>::front(){
    return *(list_start->val);
  }

  template<class T, class Allocator> typename list<T, Allocator>::const_reference list<T, Allocator>::front() const
  {
    return *(list_start->val);
  }

  template<class T, class Allocator> typename list<T, Allocator>::reference list<T, Allocator>::back()
  {
    return *(list_end->previous->val);
  }

  template<class T, class Allocator> typename list<T, Allocator>::const_reference list<T, Allocator>::back() const
  {
    return *(list_end->previous->val);
  }

  template<class T, class Allocator> void list<T, Allocator>::push_front(const T& x)
  {
    node * temp = new node(x);
    list_start->previous = temp;
    temp->previous = 0;
    temp->next = list_start;
    list_start = temp;
    ++elements;
  }

  template<class T, class Allocator> void list<T, Allocator>::pop_front()
  {
    if (elements > 0)
    {
      list_start = list_start->next;
      delete list_start->previous->val;
#ifdef CONFIG_DEBUG_LIB
      list_start->previous->val = 0;
      list_start->previous->next = 0;
      list_start->previous->previous = 0;
#endif
      delete list_start->previous;
      list_start->previous = 0;
      --elements;
    }
  }

  template<class T, class Allocator> void list<T, Allocator>::push_back(const T& x)
  {
    if (elements == 0)
    {
      // The list is completely empty

      list_start = new node(x);
      list_end->previous = list_start;
      list_start->previous = 0;
      list_start->next = list_end;
      elements = 1;
    }
    else
    {
      node * temp = new node(x);
      temp->previous = list_end->previous;
      temp->next = list_end;
      list_end->previous->next = temp;
      list_end->previous = temp;
      ++elements;
    }
  }

  template<class T, class Allocator> void list<T, Allocator>::pop_back()
  {
    if (elements > 0)
    {
      node * temp = list_end->previous;
      if (temp == list_start)
      {
        list_end->previous = 0;
        list_start = list_end;
      }
      else
      {
        temp->previous->next = temp->next;
        list_end->previous = temp->previous;
      }

      delete temp->val;
#ifdef CONFIG_DEBUG_LIB
      temp->val = 0;
      temp->next = 0;
      temp->previous = 0;
#endif
      delete temp;
#ifdef CONFIG_DEBUG_LIB
      temp = 0;
#endif
      --elements;
    }
  }


  template<class T, class Allocator> typename list<T, Allocator>::iterator
    list<T, Allocator>::insert(iterator position, const T& x)
  {
    node * temp = new node(x);

    temp->previous = position.link_struct()->previous;
    temp->next = position.link_struct();

    if (temp->previous == 0)
    {
      list_start = temp;
    }
    else
    {
      position.link_struct()->previous->next = temp;
    }

    position.link_struct()->previous = temp;

    ++elements;
    --position;
    return position;
  }

  template<class T, class Allocator> void list<T, Allocator>::insert(iterator position, size_type n, const T& x)
  {
    for (typename list<T, Allocator>::size_type i = 0; i < n; ++i)
    {
      position = insert(position, x);
    }
  }

  template<class T, class Allocator> template <class InputIterator> void
    list<T, Allocator>::insert(iterator position, InputIterator first, InputIterator last)
  {
    while (first !=last)
    {
      insert(position, *first);
      ++first;
    }
  }

  template<class T, class Allocator> typename list<T, Allocator>::iterator
    list<T, Allocator>::erase(iterator position)
  {
    if (position != end())
    {
      node * temp = position.link_struct();
      if (temp == list_start)
      {
        ++position;
        temp->next->previous = 0;
        list_start = temp->next;
      }
      else
      {
        --position;
        temp->next->previous = temp->previous;
        temp->previous->next = temp->next;
        ++position;
      }

      delete temp->val;
#ifdef CONFIG_DEBUG_LIB
      temp->next = 0;
      temp->previous = 0;
      temp->val = 0;
#endif
      delete temp;
#ifdef CONFIG_DEBUG_LIB
      temp = 0;
#endif
      --elements;
    }

    return position;
  }

  template<class T, class Allocator> typename list<T, Allocator>::iterator
    list<T, Allocator>::erase(iterator position, iterator last)
  {
    iterator temp = position;
    while (position !=last)
    {
      position = erase(position);
    }

    return position;
  }

  template<class T, class Allocator> void list<T, Allocator>::swap(list<T,Allocator>& l)
  {
    node * temp;
    size_type tempel;

    temp = list_start;
    list_start = l.list_start;
    l.list_start = temp;

    temp = list_end;
    list_end = l.list_end;
    l.list_end = temp;

    tempel = elements;
    elements = l.elements;
    l.elements = tempel;
  }

  template<class T, class Allocator> void list<T, Allocator>::clear()
  {
    while (elements > 0)
    {
      pop_front();
    }
  }

  template<class T, class Allocator>
    void list<T, Allocator>::splice(iterator position, list<T,Allocator>& x)
  {
    // Can't add non-existant elements

    if (x.elements == 0)
    {
      return;
    }

    elements += x.elements;
    x.elements = 0;

    // Chaining to the begining

    if (position == begin())
    {
      x.list_end->previous->next = list_start;
      list_start->previous = x.list_end->previous;

      list_start = x.list_start;

      x.list_start = x.list_end;
      x.list_end->previous = 0;

      return;
    }

    // Link everything we need

    x.list_start->previous = position.link_struct()->previous;
    position.link_struct()->previous->next = x.list_start;

    position.link_struct()->previous = x.list_end->previous;
    x.list_end->previous->next = position.link_struct();

    // Clean up the other list

    x.list_start = x.list_end;
    x.list_end->previous=0;
  }

  template<class T, class Allocator>
    void list<T, Allocator>::splice(iterator position, list<T,Allocator>& x, iterator i)
  {
    // Invalid conditions

    if (x.elements == 0 || i == position || position.link_struct() == i.link_struct()->next)
    {
      return;
    }

    // Do we need to adjust the begining pointer?

    if (i == x.begin())
    {
      x.list_start = x.list_start->next;
      x.list_start->previous = 0;
    }

    // Insert at begining special case

    if (position == begin())
    {
      i.link_struct()->previous->next = i.link_struct()->next;
      i.link_struct()->next->previous = i.link_struct()->previous;

      i.link_struct()->previous = 0;
      i.link_struct()->next = position.link_struct();
      position.link_struct()->previous = i.link_struct();

      list_start = i.link_struct();

      --x.elements;
      ++elements;
      return;
    }

    if (i.link_struct()->previous != 0)
    {
      i.link_struct()->previous->next = i.link_struct()->next;
      i.link_struct()->next->previous = i.link_struct()->previous;
    }
    else
    {
      i.link_struct()->next->previous = 0;
      x.list_start = i.link_struct()->next;
    }

    i.link_struct()->previous = position.link_struct()->previous;
    position.link_struct()->previous->next = i.link_struct();

    i.link_struct()->next = position.link_struct();
    position.link_struct()->previous = i.link_struct();

    --x.elements;
    ++elements;
  }

  template<class T, class Allocator>
    void list<T, Allocator>::splice(iterator position, list<T,Allocator>& x,
      iterator first, iterator last)
  {
    if (x.elements == 0)
    {
      return;
    }

    iterator temp;
    while (first != last)
    {
      temp = first;
      ++first;
      splice(position, x, temp);
    }
  }

  template<class T, class Allocator> void list<T, Allocator>::remove(const T& value)
  {
    iterator temp = begin();
    while (temp != end())
    {
      if (*temp == value)
      {
        temp = erase(temp);
      }
      else
      {
        ++temp;
      }
    }
  }

  template<class T, class Allocator> template <class Predicate> void list<T, Allocator>::remove_if (Predicate pred)
  {
    iterator temp = begin();
    while (temp != end())
    {
      if (pred(*temp))
      {
        temp = erase(temp);
      }
      else
      {
        ++temp;
      }
    }
  }

  template<class T, class Allocator> void list<T, Allocator>::unique()
  {
    equal_to<typename iterator_traits<iterator>::value_type> p;
    unique(p);
  }

  template<class T, class Allocator> template <class BinaryPredicate>
    void list<T, Allocator>::unique(BinaryPredicate binary_pred)
  {
    iterator temp1 = begin();
    iterator temp2;
    ++temp1;
    while (temp1 != end())
    {
      temp2 = temp1;
      --temp2;
      if (binary_pred(*temp1, *temp2))
      {
        erase(temp1);
        temp1 = temp2;
      }

      ++temp1;
    }
  }

  template<class T, class Allocator> void list<T, Allocator>::merge(list<T,Allocator>& x)
  {
    less<typename iterator_traits<typename list<T, Allocator>::iterator>::value_type> c;
    merge(x, c);
  }

  template<class T, class Allocator> template <class Compare>
    void list<T, Allocator>::merge(list<T,Allocator>& x, Compare comp)
  {
    iterator source = x.begin();
    iterator temp;
    iterator dest  = begin();

    while (source != x.end())
    {
      while (dest != end() && comp (*dest, *source))
      {
        ++dest;
      }

      ++elements;
      --x.elements;

      temp = source;
      ++temp;

      if (dest == begin())
      {
        dest.link_struct()->previous = source.link_struct();
        source.link_struct()->next = dest.link_struct();
        source.link_struct()->previous = 0;
        list_start = source.link_struct();
      }
      else
      {
        source.link_struct()->previous = dest.link_struct()->previous;
        dest.link_struct()->previous->next = source.link_struct();
        source.link_struct()->next = dest.link_struct();
        dest.link_struct()->previous = source.link_struct();
      }

      source = temp;
    }

    // Fix up x;

    x.list_start = x.list_end;
    x.list_start->previous = 0;
  }

  template<class T, class Allocator> void list<T, Allocator>::sort()
  {
    less<typename iterator_traits<typename list<T, Allocator>::iterator>::value_type> c;
    sort(c);
  }

  template<class T, class Allocator> template <class Compare>
    void list<T, Allocator>::sort(Compare comp)
  {
    typename list<T, Allocator>::iterator i, j, k;

    // FIXME - bubble sort

    if (elements == 0)
    {
      return;
    }

    i = end();
    --i;
    while (i != begin())
    {
      j = begin();
      k = j;
      ++k;
      while (j != i)
      {
        if (comp(*k, *j))
        {
          swap_nodes(k.link_struct(), j.link_struct());
        }

        ++j;
        ++k;
      }

      --i;
    }
  }


  template<class T, class Allocator> void list<T, Allocator>::reverse()
  {
    if (elements == 0)
    {
      return;
    }

    node * current;
    node * following;
    node * temp;

    // Need to move the list_end element to the begining

    temp = list_end;
    list_end = temp->previous;
    list_end->next = 0;

    list_start->previous = temp;
    temp->previous = 0;
    temp->next = list_start;
    list_start = temp;

    current = list_start;

    while (current != list_end)
    {
      following = current->next;

      // Swap the values pointed to/at with the current node

      temp = current->next;
      current->next = current->previous;
      current->previous = temp;

      current = following;
    }

    // Swap pointers on the end node

    temp = list_end->next;
    list_end->next = list_end->previous;
    list_end->previous = temp;

    //Swap the fixed pointers

    temp = list_start;
    list_start = list_end;
    list_end = temp;
  }

  template <class T, class Allocator>
  bool operator==(const list<T,Allocator>& x, const list<T,Allocator>& y)
  {
    if (x.size() != y.size())
    {
      return false;
    }

    typename list<T,Allocator>::const_iterator i = x.begin();
    typename list<T,Allocator>::const_iterator j = y.begin();

    while (i != x.end())
    {
      if (*i != *j)
      {
        return false;
      }

      ++i;
      ++j;
    }

    return true;
  }

  template <class T, class Allocator>
  bool operator< (const list<T,Allocator>& x, const list<T,Allocator>& y)
  {
    typename list<T,Allocator>::const_iterator i = x.begin();
    typename list<T,Allocator>::const_iterator j = y.begin();
    while (i != x.end() && j != y.end())
    {
      if (*i < *j)
      {
        return true;
      }

      if (*j < *i)
      {
        return false;
      }

      ++i;
      ++j;
    }

    return (i == x.end() && j != y.end());
  }

  template <class T, class Allocator>
  bool operator!=(const list<T,Allocator>& x, const list<T,Allocator>& y)
  {
    return !(x == y);
  }

  template <class T, class Allocator>
  bool operator> (const list<T,Allocator>& x, const list<T,Allocator>& y)
  {
    typename list<T,Allocator>::const_iterator i = x.begin();
    typename list<T,Allocator>::const_iterator j = y.begin();
    while (i != x.end() && j != y.end())
    {
      if (*i > *j)
      {
        return true;
      }

      if (*j > *i)
      {
        return false;
      }

      ++i;
      ++j;
    }

    return (i != x.end() && j == y.end());
  }

  template <class T, class Allocator>
  bool operator>=(const list<T,Allocator>& x, const list<T,Allocator>& y)
  {
    typename list<T,Allocator>::const_iterator i = x.begin();
    typename list<T,Allocator>::const_iterator j = y.begin();
    while (i != x.end() && j != y.end())
    {
      if (*i >= *j)
      {
        return true;
      }

      if (*j >= *i)
      {
        return false;
      }

      ++i;
      ++j;
    }

    return (i != x.end() && j == y.end());
  }

  template <class T, class Allocator>
  bool operator<=(const list<T,Allocator>& x, const list<T,Allocator>& y)
  {
    typename list<T,Allocator>::const_iterator i = x.begin();
    typename list<T,Allocator>::const_iterator j = y.begin();
    while (i != x.end() && j != y.end())
    {
      if (*i <= *j)
      {
        return true;
      }

      if (*j <= *i)
      {
        return false;
      }

      ++i;
      ++j;
    }

    return (i == x.end());
  }

  template <class T, class Allocator>
  void swap(list<T,Allocator>& x, list<T,Allocator>& y)
  {
    x.swap(y);
  }

} // namespace
} // extern "C++"

#pragma GCC visibility pop

#endif


