list_base.hpp

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

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