//=======================================================================

// Copyright 2002 Indiana University.

// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek

//

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

//=======================================================================

#ifndef BOOST_LIST_BASE_HPP

#define BOOST_LIST_BASE_HPP

#include <boost/iterator_adaptors.hpp>

// Perhaps this should go through formal review, and move to <boost/>.

/*

  An alternate interface idea:

    Extend the std::list functionality by creating remove/insert

    functions that do not require the container object!

 */

namespace boost {

  namespace detail {

    //=========================================================================

    // Linked-List Generic Implementation Functions

    template <class Node, class Next>

    inline Node

    slist_insert_after(Node pos, Node x, 

                       Next next)

    {

      next(x) = next(pos);

      next(pos) = x;

      return x;

    }

    // return next(pos) or next(next(pos)) ?

    template <class Node, class Next>

    inline Node

    slist_remove_after(Node pos, 

                       Next next)

    {

      Node n = next(pos);

      next(pos) = next(n);

      return n;

    }

    template <class Node, class Next>

    inline Node

    slist_remove_range(Node before_first, Node last, 

                       Next next)

    {

      next(before_first) = last;

      return last;

    }

    template <class Node, class Next>

    inline Node

    slist_previous(Node head, Node x, Node nil, 

                   Next next)

    {

      while (head != nil && next(head) != x)

        head = next(head);

      return head;

    }

    template<class Node, class Next>

    inline void

    slist_splice_after(Node pos, Node before_first, Node before_last, 

                       Next next)

    {

      if (pos != before_first && pos != before_last) {

        Node first = next(before_first);

        Node after = next(pos);

        next(before_first) = next(before_last);

        next(pos) = first;

        next(before_last) = after;

      }

    }

    template <class Node, class Next>

    inline Node

    slist_reverse(Node node, Node nil, 

                  Next next)

    {

      Node result = node;

      node = next(node);

      next(result) = nil;

      while(node) {

        Node next = next(node);

        next(node) = result;

        result = node;

        node = next;

      }

      return result;

    }

    template <class Node, class Next>

    inline std::size_t

    slist_size(Node head, Node nil, 

               Next next)

    {

      std::size_t s = 0;

      for ( ; head != nil; head = next(head))

        ++s;

      return s;

    }

    template <class Next, class Data>

    class slist_iterator_policies

    {

    public:

      explicit slist_iterator_policies(const Next& n, const Data& d)

        : m_next(n), m_data(d) { }

      template <class Reference, class Node>

      Reference dereference(type<Reference>, const Node& x) const

        { return m_data(x); }

      template <class Node>

      void increment(Node& x) const

        { x = m_next(x); }

      template <class Node>

      bool equal(Node& x, Node& y) const

        { return x == y; }

    protected:

      Next m_next;

      Data m_data;

    };

  //===========================================================================

  // Doubly-Linked List Generic Implementation Functions

    template <class Node, class Next, class Prev>

    inline void

    dlist_insert_before(Node pos, Node x, 

                        Next next, Prev prev)

    {

      next(x) = pos;

      prev(x) = prev(pos);

      next(prev(pos)) = x;

      prev(pos) = x;

    }

    template <class Node, class Next, class Prev>

    void

    dlist_remove(Node pos, 

                 Next next, Prev prev)

    {

      Node next_node = next(pos);

      Node prev_node = prev(pos);

      next(prev_node) = next_node;

      prev(next_node) = prev_node;

    }

    // This deletes every node in the list except the

    // sentinel node.

    template <class Node, class Delete>

    inline void

    dlist_clear(Node sentinel, Delete del)

    {

      Node i, tmp;

      i = next(sentinel);

      while (i != sentinel) {

        tmp = i;

        i = next(i);

        del(tmp);

      }

    }

    template <class Node>

    inline bool

    dlist_empty(Node dummy)

    {

      return next(dummy) == dummy;

    }

    template <class Node, class Next, class Prev>  

    void

    dlist_transfer(Node pos, Node first, Node last, 

                   Next next, Prev prev)

    {

      if (pos != last) {

        // Remove [first,last) from its old position

        next(prev(last)) = pos;

        next(prev(first)) = last;

        next(prev(pos)) = first;

        // Splice [first,last) into its new position

        Node tmp = prev(pos);

        prev(pos) = prev(last);

        prev(last) = prev(first);

        prev(first) = tmp;

      }

    }  

    template <class Next, class Prev, class Data>

    class dlist_iterator_policies

      : public slist_iterator_policies<Next, Data>

    {

      typedef slist_iterator_policies<Next, Data> Base;

    public:

      template <class Node>

      void decrement(Node& x) const

        { x = m_prev(x); }

      dlist_iterator_policies(Next n, Prev p, Data d) 

        : Base(n,d), m_prev(p) { }

    protected:

      Prev m_prev;

    };

  } // namespace detail

} // namespace boost

#endif // BOOST_LIST_BASE_HPP