]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
f67539c2 TL |
23 | namespace boost |
24 | { | |
25 | namespace detail | |
26 | { | |
7c673cae FG |
27 | |
28 | //========================================================================= | |
29 | // Linked-List Generic Implementation Functions | |
30 | ||
f67539c2 TL |
31 | template < class Node, class Next > |
32 | inline Node slist_insert_after(Node pos, Node x, Next next) | |
7c673cae | 33 | { |
f67539c2 TL |
34 | next(x) = next(pos); |
35 | next(pos) = x; | |
36 | return x; | |
7c673cae FG |
37 | } |
38 | ||
39 | // return next(pos) or next(next(pos)) ? | |
f67539c2 TL |
40 | template < class Node, class Next > |
41 | inline Node slist_remove_after(Node pos, Next next) | |
7c673cae | 42 | { |
f67539c2 TL |
43 | Node n = next(pos); |
44 | next(pos) = next(n); | |
45 | return n; | |
7c673cae FG |
46 | } |
47 | ||
f67539c2 TL |
48 | template < class Node, class Next > |
49 | inline Node slist_remove_range(Node before_first, Node last, Next next) | |
7c673cae | 50 | { |
f67539c2 TL |
51 | next(before_first) = last; |
52 | return last; | |
7c673cae FG |
53 | } |
54 | ||
f67539c2 TL |
55 | template < class Node, class Next > |
56 | inline Node slist_previous(Node head, Node x, Node empty, Next next) | |
7c673cae | 57 | { |
f67539c2 TL |
58 | while (head != empty && next(head) != x) |
59 | head = next(head); | |
60 | return head; | |
7c673cae FG |
61 | } |
62 | ||
f67539c2 TL |
63 | template < class Node, class Next > |
64 | inline void slist_splice_after( | |
65 | Node pos, Node before_first, Node before_last, Next next) | |
7c673cae | 66 | { |
f67539c2 TL |
67 | if (pos != before_first && pos != before_last) |
68 | { | |
69 | Node first = next(before_first); | |
70 | Node after = next(pos); | |
71 | next(before_first) = next(before_last); | |
72 | next(pos) = first; | |
73 | next(before_last) = after; | |
74 | } | |
7c673cae FG |
75 | } |
76 | ||
f67539c2 TL |
77 | template < class Node, class Next > |
78 | inline Node slist_reverse(Node node, Node empty, Next next) | |
7c673cae | 79 | { |
f67539c2 TL |
80 | Node result = node; |
81 | node = next(node); | |
82 | next(result) = empty; | |
83 | while (node) | |
84 | { | |
85 | Node next = next(node); | |
86 | next(node) = result; | |
87 | result = node; | |
88 | node = next; | |
89 | } | |
90 | return result; | |
7c673cae FG |
91 | } |
92 | ||
f67539c2 TL |
93 | template < class Node, class Next > |
94 | inline std::size_t slist_size(Node head, Node empty, Next next) | |
7c673cae | 95 | { |
f67539c2 TL |
96 | std::size_t s = 0; |
97 | for (; head != empty; head = next(head)) | |
98 | ++s; | |
99 | return s; | |
7c673cae FG |
100 | } |
101 | ||
f67539c2 | 102 | template < class Next, class Data > class slist_iterator_policies |
7c673cae FG |
103 | { |
104 | public: | |
f67539c2 TL |
105 | explicit slist_iterator_policies(const Next& n, const Data& d) |
106 | : m_next(n), m_data(d) | |
107 | { | |
108 | } | |
7c673cae | 109 | |
f67539c2 TL |
110 | template < class Reference, class Node > |
111 | Reference dereference(type< Reference >, const Node& x) const | |
112 | { | |
113 | return m_data(x); | |
114 | } | |
7c673cae | 115 | |
f67539c2 | 116 | template < class Node > void increment(Node& x) const { x = m_next(x); } |
7c673cae | 117 | |
f67539c2 TL |
118 | template < class Node > bool equal(Node& x, Node& y) const |
119 | { | |
120 | return x == y; | |
121 | } | |
7c673cae FG |
122 | |
123 | protected: | |
f67539c2 TL |
124 | Next m_next; |
125 | Data m_data; | |
7c673cae FG |
126 | }; |
127 | ||
f67539c2 TL |
128 | //=========================================================================== |
129 | // Doubly-Linked List Generic Implementation Functions | |
7c673cae | 130 | |
f67539c2 TL |
131 | template < class Node, class Next, class Prev > |
132 | inline void dlist_insert_before(Node pos, Node x, Next next, Prev prev) | |
7c673cae | 133 | { |
f67539c2 TL |
134 | next(x) = pos; |
135 | prev(x) = prev(pos); | |
136 | next(prev(pos)) = x; | |
137 | prev(pos) = x; | |
7c673cae FG |
138 | } |
139 | ||
f67539c2 TL |
140 | template < class Node, class Next, class Prev > |
141 | void dlist_remove(Node pos, Next next, Prev prev) | |
7c673cae | 142 | { |
f67539c2 TL |
143 | Node next_node = next(pos); |
144 | Node prev_node = prev(pos); | |
145 | next(prev_node) = next_node; | |
146 | prev(next_node) = prev_node; | |
7c673cae FG |
147 | } |
148 | ||
149 | // This deletes every node in the list except the | |
150 | // sentinel node. | |
f67539c2 TL |
151 | template < class Node, class Delete > |
152 | inline void dlist_clear(Node sentinel, Delete del) | |
7c673cae | 153 | { |
f67539c2 TL |
154 | Node i, tmp; |
155 | i = next(sentinel); | |
156 | while (i != sentinel) | |
157 | { | |
158 | tmp = i; | |
159 | i = next(i); | |
160 | del(tmp); | |
161 | } | |
7c673cae | 162 | } |
f67539c2 TL |
163 | |
164 | template < class Node > inline bool dlist_empty(Node dummy) | |
7c673cae | 165 | { |
f67539c2 | 166 | return next(dummy) == dummy; |
7c673cae FG |
167 | } |
168 | ||
f67539c2 TL |
169 | template < class Node, class Next, class Prev > |
170 | void dlist_transfer(Node pos, Node first, Node last, Next next, Prev prev) | |
7c673cae | 171 | { |
f67539c2 TL |
172 | if (pos != last) |
173 | { | |
174 | // Remove [first,last) from its old position | |
175 | next(prev(last)) = pos; | |
176 | next(prev(first)) = last; | |
177 | next(prev(pos)) = first; | |
178 | ||
179 | // Splice [first,last) into its new position | |
180 | Node tmp = prev(pos); | |
181 | prev(pos) = prev(last); | |
182 | prev(last) = prev(first); | |
183 | prev(first) = tmp; | |
184 | } | |
185 | } | |
186 | ||
187 | template < class Next, class Prev, class Data > | |
188 | class dlist_iterator_policies : public slist_iterator_policies< Next, Data > | |
7c673cae | 189 | { |
f67539c2 TL |
190 | typedef slist_iterator_policies< Next, Data > Base; |
191 | ||
7c673cae | 192 | public: |
f67539c2 TL |
193 | template < class Node > void decrement(Node& x) const { x = m_prev(x); } |
194 | ||
195 | dlist_iterator_policies(Next n, Prev p, Data d) : Base(n, d), m_prev(p) | |
196 | { | |
197 | } | |
7c673cae | 198 | |
7c673cae | 199 | protected: |
f67539c2 | 200 | Prev m_prev; |
7c673cae FG |
201 | }; |
202 | ||
f67539c2 | 203 | } // namespace detail |
7c673cae FG |
204 | } // namespace boost |
205 | ||
206 | #endif // BOOST_LIST_BASE_HPP |