epoc32/include/stdapis/boost/graph/detail/list_base.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:27:01 +0100
branchSymbian2
changeset 3 e1b950c65cb4
permissions -rw-r--r--
Attempt to represent the S^2->S^3 header reorganisation as a series of "hg rename" operations
     1 //=======================================================================
     2 // Copyright 2002 Indiana University.
     3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
     4 //
     5 // Distributed under the Boost Software License, Version 1.0. (See
     6 // accompanying file LICENSE_1_0.txt or copy at
     7 // http://www.boost.org/LICENSE_1_0.txt)
     8 //=======================================================================
     9 
    10 #ifndef BOOST_LIST_BASE_HPP
    11 #define BOOST_LIST_BASE_HPP
    12 
    13 #include <boost/iterator_adaptors.hpp>
    14 
    15 // Perhaps this should go through formal review, and move to <boost/>.
    16 
    17 /*
    18   An alternate interface idea:
    19     Extend the std::list functionality by creating remove/insert
    20     functions that do not require the container object!
    21  */
    22 
    23 namespace boost {
    24   namespace detail {
    25 
    26     //=========================================================================
    27     // Linked-List Generic Implementation Functions
    28 
    29     template <class Node, class Next>
    30     inline Node
    31     slist_insert_after(Node pos, Node x, 
    32                        Next next)
    33     {
    34       next(x) = next(pos);
    35       next(pos) = x;
    36       return x;
    37     }
    38 
    39     // return next(pos) or next(next(pos)) ?
    40     template <class Node, class Next>
    41     inline Node
    42     slist_remove_after(Node pos, 
    43                        Next next)
    44     {
    45       Node n = next(pos);
    46       next(pos) = next(n);
    47       return n;
    48     }
    49 
    50     template <class Node, class Next>
    51     inline Node
    52     slist_remove_range(Node before_first, Node last, 
    53                        Next next)
    54     {
    55       next(before_first) = last;
    56       return last;
    57     }
    58 
    59     template <class Node, class Next>
    60     inline Node
    61     slist_previous(Node head, Node x, Node nil, 
    62                    Next next)
    63     {
    64       while (head != nil && next(head) != x)
    65         head = next(head);
    66       return head;
    67     }
    68 
    69     template<class Node, class Next>
    70     inline void
    71     slist_splice_after(Node pos, Node before_first, Node before_last, 
    72                        Next next)
    73     {
    74       if (pos != before_first && pos != before_last) {
    75         Node first = next(before_first);
    76         Node after = next(pos);
    77         next(before_first) = next(before_last);
    78         next(pos) = first;
    79         next(before_last) = after;
    80       }
    81     }
    82 
    83     template <class Node, class Next>
    84     inline Node
    85     slist_reverse(Node node, Node nil, 
    86                   Next next)
    87     {
    88       Node result = node;
    89       node = next(node);
    90       next(result) = nil;
    91       while(node) {
    92         Node next = next(node);
    93         next(node) = result;
    94         result = node;
    95         node = next;
    96       }
    97       return result;
    98     }
    99 
   100     template <class Node, class Next>
   101     inline std::size_t
   102     slist_size(Node head, Node nil, 
   103                Next next)
   104     {
   105       std::size_t s = 0;
   106       for ( ; head != nil; head = next(head))
   107         ++s;
   108       return s;
   109     }
   110 
   111     template <class Next, class Data>
   112     class slist_iterator_policies
   113     {
   114     public:
   115       explicit slist_iterator_policies(const Next& n, const Data& d)
   116         : m_next(n), m_data(d) { }
   117 
   118       template <class Reference, class Node>
   119       Reference dereference(type<Reference>, const Node& x) const
   120         { return m_data(x); }
   121 
   122       template <class Node>
   123       void increment(Node& x) const
   124         { x = m_next(x); }
   125 
   126       template <class Node>
   127       bool equal(Node& x, Node& y) const
   128         { return x == y; }
   129 
   130     protected:
   131       Next m_next;
   132       Data m_data;
   133     };
   134 
   135   //===========================================================================
   136   // Doubly-Linked List Generic Implementation Functions
   137 
   138     template <class Node, class Next, class Prev>
   139     inline void
   140     dlist_insert_before(Node pos, Node x, 
   141                         Next next, Prev prev)
   142     {
   143       next(x) = pos;
   144       prev(x) = prev(pos);
   145       next(prev(pos)) = x;
   146       prev(pos) = x;
   147     }
   148 
   149     template <class Node, class Next, class Prev>
   150     void
   151     dlist_remove(Node pos, 
   152                  Next next, Prev prev)
   153     {
   154       Node next_node = next(pos);
   155       Node prev_node = prev(pos);
   156       next(prev_node) = next_node;
   157       prev(next_node) = prev_node;
   158     }
   159 
   160     // This deletes every node in the list except the
   161     // sentinel node.
   162     template <class Node, class Delete>
   163     inline void
   164     dlist_clear(Node sentinel, Delete del)
   165     {
   166       Node i, tmp;
   167       i = next(sentinel);
   168       while (i != sentinel) {
   169         tmp = i;
   170         i = next(i);
   171         del(tmp);
   172       }
   173     }
   174     
   175     template <class Node>
   176     inline bool
   177     dlist_empty(Node dummy)
   178     {
   179       return next(dummy) == dummy;
   180     }
   181 
   182     template <class Node, class Next, class Prev>  
   183     void
   184     dlist_transfer(Node pos, Node first, Node last, 
   185                    Next next, Prev prev)
   186     {
   187       if (pos != last) {
   188         // Remove [first,last) from its old position
   189         next(prev(last)) = pos;
   190         next(prev(first)) = last;
   191         next(prev(pos)) = first;
   192 
   193         // Splice [first,last) into its new position
   194         Node tmp = prev(pos);
   195         prev(pos) = prev(last);
   196         prev(last) = prev(first);
   197         prev(first) = tmp;
   198       }
   199     }  
   200 
   201     template <class Next, class Prev, class Data>
   202     class dlist_iterator_policies
   203       : public slist_iterator_policies<Next, Data>
   204     {
   205       typedef slist_iterator_policies<Next, Data> Base;
   206     public:
   207       template <class Node>
   208       void decrement(Node& x) const
   209         { x = m_prev(x); }
   210 
   211       dlist_iterator_policies(Next n, Prev p, Data d) 
   212         : Base(n,d), m_prev(p) { }
   213     protected:
   214       Prev m_prev;
   215     };
   216 
   217   } // namespace detail
   218 } // namespace boost
   219 
   220 #endif // BOOST_LIST_BASE_HPP