graph/detail/list_base.hpp

0001 //=======================================================================
0002 // Copyright 2002 Indiana University.
0003 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009
0010 #ifndef BOOST_LIST_BASE_HPP
0011 #define BOOST_LIST_BASE_HPP
0012
0013 #include <boost/iterator_adaptors.hpp>
0014
0015 // Perhaps this should go through formal review, and move to <boost/>.
0016
0017 /*
0018   An alternate interface idea:
0019     Extend the std::list functionality by creating remove/insert
0020     functions that do not require the container object!
0021  */
0022
0023 namespace boost
0024 {
0025 namespace detail
0026 {
0027
0028     //=========================================================================
0029     // Linked-List Generic Implementation Functions
0030
0031     template < class Node, class Next >
0032     inline Node slist_insert_after(Node pos, Node x, Next next)
0033     {
0034         next(x) = next(pos);
0035         next(pos) = x;
0036         return x;
0037     }
0038
0039     // return next(pos) or next(next(pos)) ?
0040     template < class Node, class Next >
0041     inline Node slist_remove_after(Node pos, Next next)
0042     {
0043         Node n = next(pos);
0044         next(pos) = next(n);
0045         return n;
0046     }
0047
0048     template < class Node, class Next >
0049     inline Node slist_remove_range(Node before_first, Node last, Next next)
0050     {
0051         next(before_first) = last;
0052         return last;
0053     }
0054
0055     template < class Node, class Next >
0056     inline Node slist_previous(Node head, Node x, Node empty, Next next)
0057     {
0058         while (head != empty && next(head) != x)
0059             head = next(head);
0060         return head;
0061     }
0062
0063     template < class Node, class Next >
0064     inline void slist_splice_after(
0065         Node pos, Node before_first, Node before_last, Next next)
0066     {
0067         if (pos != before_first && pos != before_last)
0068         {
0069             Node first = next(before_first);
0070             Node after = next(pos);
0071             next(before_first) = next(before_last);
0072             next(pos) = first;
0073             next(before_last) = after;
0074         }
0075     }
0076
0077     template < class Node, class Next >
0078     inline Node slist_reverse(Node node, Node empty, Next next)
0079     {
0080         Node result = node;
0081         node = next(node);
0082         next(result) = empty;
0083         while (node)
0084         {
0085             Node next = next(node);
0086             next(node) = result;
0087             result = node;
0088             node = next;
0089         }
0090         return result;
0091     }
0092
0093     template < class Node, class Next >
0094     inline std::size_t slist_size(Node head, Node empty, Next next)
0095     {
0096         std::size_t s = 0;
0097         for (; head != empty; head = next(head))
0098             ++s;
0099         return s;
0100     }
0101
0102     template < class Next, class Data > class slist_iterator_policies
0103     {
0104     public:
0105         explicit slist_iterator_policies(const Next& n, const Data& d)
0106         : m_next(n), m_data(d)
0107         {
0108         }
0109
0110         template < class Reference, class Node >
0111         Reference dereference(type< Reference >, const Node& x) const
0112         {
0113             return m_data(x);
0114         }
0115
0116         template < class Node > void increment(Node& x) const { x = m_next(x); }
0117
0118         template < class Node > bool equal(Node& x, Node& y) const
0119         {
0120             return x == y;
0121         }
0122
0123     protected:
0124         Next m_next;
0125         Data m_data;
0126     };
0127
0128     //===========================================================================
0129     // Doubly-Linked List Generic Implementation Functions
0130
0131     template < class Node, class Next, class Prev >
0132     inline void dlist_insert_before(Node pos, Node x, Next next, Prev prev)
0133     {
0134         next(x) = pos;
0135         prev(x) = prev(pos);
0136         next(prev(pos)) = x;
0137         prev(pos) = x;
0138     }
0139
0140     template < class Node, class Next, class Prev >
0141     void dlist_remove(Node pos, Next next, Prev prev)
0142     {
0143         Node next_node = next(pos);
0144         Node prev_node = prev(pos);
0145         next(prev_node) = next_node;
0146         prev(next_node) = prev_node;
0147     }
0148
0149     // This deletes every node in the list except the
0150     // sentinel node.
0151     template < class Node, class Delete >
0152     inline void dlist_clear(Node sentinel, Delete del)
0153     {
0154         Node i, tmp;
0155         i = next(sentinel);
0156         while (i != sentinel)
0157         {
0158             tmp = i;
0159             i = next(i);
0160             del(tmp);
0161         }
0162     }
0163
0164     template < class Node > inline bool dlist_empty(Node dummy)
0165     {
0166         return next(dummy) == dummy;
0167     }
0168
0169     template < class Node, class Next, class Prev >
0170     void dlist_transfer(Node pos, Node first, Node last, Next next, Prev prev)
0171     {
0172         if (pos != last)
0173         {
0174             // Remove [first,last) from its old position
0175             next(prev(last)) = pos;
0176             next(prev(first)) = last;
0177             next(prev(pos)) = first;
0178
0179             // Splice [first,last) into its new position
0180             Node tmp = prev(pos);
0181             prev(pos) = prev(last);
0182             prev(last) = prev(first);
0183             prev(first) = tmp;
0184         }
0185     }
0186
0187     template < class Next, class Prev, class Data >
0188     class dlist_iterator_policies : public slist_iterator_policies< Next, Data >
0189     {
0190         typedef slist_iterator_policies< Next, Data > Base;
0191
0192     public:
0193         template < class Node > void decrement(Node& x) const { x = m_prev(x); }
0194
0195         dlist_iterator_policies(Next n, Prev p, Data d) : Base(n, d), m_prev(p)
0196         {
0197         }
0198
0199     protected:
0200         Prev m_prev;
0201     };
0202
0203 } // namespace detail
0204 } // namespace boost
0205
0206 #endif // BOOST_LIST_BASE_HPP