source: NonGTP/Boost/boost/graph/detail/list_base.hpp @ 857

Revision 857, 5.7 KB checked in by igarcia, 19 years ago (diff)
Line 
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
23namespace 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
Note: See TracBrowser for help on using the repository browser.