williamr@2: //=======================================================================
williamr@2: // Copyright 2002 Indiana University.
williamr@2: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
williamr@2: //
williamr@2: // Distributed under the Boost Software License, Version 1.0. (See
williamr@2: // accompanying file LICENSE_1_0.txt or copy at
williamr@2: // http://www.boost.org/LICENSE_1_0.txt)
williamr@2: //=======================================================================
williamr@2: 
williamr@2: #ifndef BOOST_LIST_BASE_HPP
williamr@2: #define BOOST_LIST_BASE_HPP
williamr@2: 
williamr@2: #include <boost/iterator_adaptors.hpp>
williamr@2: 
williamr@2: // Perhaps this should go through formal review, and move to <boost/>.
williamr@2: 
williamr@2: /*
williamr@2:   An alternate interface idea:
williamr@2:     Extend the std::list functionality by creating remove/insert
williamr@2:     functions that do not require the container object!
williamr@2:  */
williamr@2: 
williamr@2: namespace boost {
williamr@2:   namespace detail {
williamr@2: 
williamr@2:     //=========================================================================
williamr@2:     // Linked-List Generic Implementation Functions
williamr@2: 
williamr@2:     template <class Node, class Next>
williamr@2:     inline Node
williamr@2:     slist_insert_after(Node pos, Node x, 
williamr@2:                        Next next)
williamr@2:     {
williamr@2:       next(x) = next(pos);
williamr@2:       next(pos) = x;
williamr@2:       return x;
williamr@2:     }
williamr@2: 
williamr@2:     // return next(pos) or next(next(pos)) ?
williamr@2:     template <class Node, class Next>
williamr@2:     inline Node
williamr@2:     slist_remove_after(Node pos, 
williamr@2:                        Next next)
williamr@2:     {
williamr@2:       Node n = next(pos);
williamr@2:       next(pos) = next(n);
williamr@2:       return n;
williamr@2:     }
williamr@2: 
williamr@2:     template <class Node, class Next>
williamr@2:     inline Node
williamr@2:     slist_remove_range(Node before_first, Node last, 
williamr@2:                        Next next)
williamr@2:     {
williamr@2:       next(before_first) = last;
williamr@2:       return last;
williamr@2:     }
williamr@2: 
williamr@2:     template <class Node, class Next>
williamr@2:     inline Node
williamr@2:     slist_previous(Node head, Node x, Node nil, 
williamr@2:                    Next next)
williamr@2:     {
williamr@2:       while (head != nil && next(head) != x)
williamr@2:         head = next(head);
williamr@2:       return head;
williamr@2:     }
williamr@2: 
williamr@2:     template<class Node, class Next>
williamr@2:     inline void
williamr@2:     slist_splice_after(Node pos, Node before_first, Node before_last, 
williamr@2:                        Next next)
williamr@2:     {
williamr@2:       if (pos != before_first && pos != before_last) {
williamr@2:         Node first = next(before_first);
williamr@2:         Node after = next(pos);
williamr@2:         next(before_first) = next(before_last);
williamr@2:         next(pos) = first;
williamr@2:         next(before_last) = after;
williamr@2:       }
williamr@2:     }
williamr@2: 
williamr@2:     template <class Node, class Next>
williamr@2:     inline Node
williamr@2:     slist_reverse(Node node, Node nil, 
williamr@2:                   Next next)
williamr@2:     {
williamr@2:       Node result = node;
williamr@2:       node = next(node);
williamr@2:       next(result) = nil;
williamr@2:       while(node) {
williamr@2:         Node next = next(node);
williamr@2:         next(node) = result;
williamr@2:         result = node;
williamr@2:         node = next;
williamr@2:       }
williamr@2:       return result;
williamr@2:     }
williamr@2: 
williamr@2:     template <class Node, class Next>
williamr@2:     inline std::size_t
williamr@2:     slist_size(Node head, Node nil, 
williamr@2:                Next next)
williamr@2:     {
williamr@2:       std::size_t s = 0;
williamr@2:       for ( ; head != nil; head = next(head))
williamr@2:         ++s;
williamr@2:       return s;
williamr@2:     }
williamr@2: 
williamr@2:     template <class Next, class Data>
williamr@2:     class slist_iterator_policies
williamr@2:     {
williamr@2:     public:
williamr@2:       explicit slist_iterator_policies(const Next& n, const Data& d)
williamr@2:         : m_next(n), m_data(d) { }
williamr@2: 
williamr@2:       template <class Reference, class Node>
williamr@2:       Reference dereference(type<Reference>, const Node& x) const
williamr@2:         { return m_data(x); }
williamr@2: 
williamr@2:       template <class Node>
williamr@2:       void increment(Node& x) const
williamr@2:         { x = m_next(x); }
williamr@2: 
williamr@2:       template <class Node>
williamr@2:       bool equal(Node& x, Node& y) const
williamr@2:         { return x == y; }
williamr@2: 
williamr@2:     protected:
williamr@2:       Next m_next;
williamr@2:       Data m_data;
williamr@2:     };
williamr@2: 
williamr@2:   //===========================================================================
williamr@2:   // Doubly-Linked List Generic Implementation Functions
williamr@2: 
williamr@2:     template <class Node, class Next, class Prev>
williamr@2:     inline void
williamr@2:     dlist_insert_before(Node pos, Node x, 
williamr@2:                         Next next, Prev prev)
williamr@2:     {
williamr@2:       next(x) = pos;
williamr@2:       prev(x) = prev(pos);
williamr@2:       next(prev(pos)) = x;
williamr@2:       prev(pos) = x;
williamr@2:     }
williamr@2: 
williamr@2:     template <class Node, class Next, class Prev>
williamr@2:     void
williamr@2:     dlist_remove(Node pos, 
williamr@2:                  Next next, Prev prev)
williamr@2:     {
williamr@2:       Node next_node = next(pos);
williamr@2:       Node prev_node = prev(pos);
williamr@2:       next(prev_node) = next_node;
williamr@2:       prev(next_node) = prev_node;
williamr@2:     }
williamr@2: 
williamr@2:     // This deletes every node in the list except the
williamr@2:     // sentinel node.
williamr@2:     template <class Node, class Delete>
williamr@2:     inline void
williamr@2:     dlist_clear(Node sentinel, Delete del)
williamr@2:     {
williamr@2:       Node i, tmp;
williamr@2:       i = next(sentinel);
williamr@2:       while (i != sentinel) {
williamr@2:         tmp = i;
williamr@2:         i = next(i);
williamr@2:         del(tmp);
williamr@2:       }
williamr@2:     }
williamr@2:     
williamr@2:     template <class Node>
williamr@2:     inline bool
williamr@2:     dlist_empty(Node dummy)
williamr@2:     {
williamr@2:       return next(dummy) == dummy;
williamr@2:     }
williamr@2: 
williamr@2:     template <class Node, class Next, class Prev>  
williamr@2:     void
williamr@2:     dlist_transfer(Node pos, Node first, Node last, 
williamr@2:                    Next next, Prev prev)
williamr@2:     {
williamr@2:       if (pos != last) {
williamr@2:         // Remove [first,last) from its old position
williamr@2:         next(prev(last)) = pos;
williamr@2:         next(prev(first)) = last;
williamr@2:         next(prev(pos)) = first;
williamr@2: 
williamr@2:         // Splice [first,last) into its new position
williamr@2:         Node tmp = prev(pos);
williamr@2:         prev(pos) = prev(last);
williamr@2:         prev(last) = prev(first);
williamr@2:         prev(first) = tmp;
williamr@2:       }
williamr@2:     }  
williamr@2: 
williamr@2:     template <class Next, class Prev, class Data>
williamr@2:     class dlist_iterator_policies
williamr@2:       : public slist_iterator_policies<Next, Data>
williamr@2:     {
williamr@2:       typedef slist_iterator_policies<Next, Data> Base;
williamr@2:     public:
williamr@2:       template <class Node>
williamr@2:       void decrement(Node& x) const
williamr@2:         { x = m_prev(x); }
williamr@2: 
williamr@2:       dlist_iterator_policies(Next n, Prev p, Data d) 
williamr@2:         : Base(n,d), m_prev(p) { }
williamr@2:     protected:
williamr@2:       Prev m_prev;
williamr@2:     };
williamr@2: 
williamr@2:   } // namespace detail
williamr@2: } // namespace boost
williamr@2: 
williamr@2: #endif // BOOST_LIST_BASE_HPP