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