]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /////////////////////////////////////////////////////////////////////////////// |
2 | // list.hpp | |
3 | // A simple implementation of std::list that allows incomplete | |
4 | // types, does no dynamic allocation in the default constructor, | |
5 | // and has a guarnteed O(1) splice. | |
6 | // | |
7 | // Copyright 2009 Eric Niebler. Distributed under the Boost | |
8 | // Software License, Version 1.0. (See accompanying file | |
9 | // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
10 | ||
11 | #ifndef BOOST_XPRESSIVE_DETAIL_CORE_LIST_HPP_EAN_10_26_2009 | |
12 | #define BOOST_XPRESSIVE_DETAIL_CORE_LIST_HPP_EAN_10_26_2009 | |
13 | ||
14 | // MS compatible compilers support #pragma once | |
15 | #if defined(_MSC_VER) | |
16 | # pragma once | |
17 | #endif | |
18 | ||
19 | #include <cstddef> | |
20 | #include <iterator> | |
21 | #include <algorithm> | |
22 | #include <boost/assert.hpp> | |
23 | #include <boost/iterator/iterator_facade.hpp> | |
24 | ||
25 | namespace boost { namespace xpressive { namespace detail | |
26 | { | |
27 | ||
28 | /////////////////////////////////////////////////////////////////////////////// | |
29 | // list | |
30 | // | |
31 | template<typename T> | |
32 | struct list | |
33 | { | |
34 | private: | |
35 | struct node_base | |
36 | { | |
37 | node_base *_prev; | |
38 | node_base *_next; | |
39 | }; | |
40 | ||
41 | struct node : node_base | |
42 | { | |
43 | explicit node(T const &value) | |
44 | : _value(value) | |
45 | {} | |
46 | ||
47 | T _value; | |
48 | }; | |
49 | ||
50 | node_base _sentry; | |
51 | ||
52 | template<typename Ref = T &> | |
53 | struct list_iterator | |
54 | : boost::iterator_facade<list_iterator<Ref>, T, std::bidirectional_iterator_tag, Ref> | |
55 | { | |
56 | list_iterator(list_iterator<> const &it) : _node(it._node) {} | |
57 | explicit list_iterator(node_base *n = 0) : _node(n) {} | |
58 | private: | |
59 | friend struct list<T>; | |
60 | friend class boost::iterator_core_access; | |
61 | Ref dereference() const { return static_cast<node *>(_node)->_value; } | |
62 | void increment() { _node = _node->_next; } | |
63 | void decrement() { _node = _node->_prev; } | |
64 | bool equal(list_iterator const &it) const { return _node == it._node; } | |
65 | node_base *_node; | |
66 | }; | |
67 | ||
68 | public: | |
69 | typedef T *pointer; | |
70 | typedef T const *const_pointer; | |
71 | typedef T &reference; | |
72 | typedef T const &const_reference; | |
73 | typedef list_iterator<> iterator; | |
74 | typedef list_iterator<T const &> const_iterator; | |
75 | typedef std::size_t size_type; | |
76 | ||
77 | list() | |
78 | { | |
79 | _sentry._next = _sentry._prev = &_sentry; | |
80 | } | |
81 | ||
82 | list(list const &that) | |
83 | { | |
84 | _sentry._next = _sentry._prev = &_sentry; | |
85 | const_iterator it = that.begin(), e = that.end(); | |
86 | for( ; it != e; ++it) | |
87 | push_back(*it); | |
88 | } | |
89 | ||
90 | list &operator =(list const &that) | |
91 | { | |
92 | list(that).swap(*this); | |
93 | return *this; | |
94 | } | |
95 | ||
96 | ~list() | |
97 | { | |
98 | clear(); | |
99 | } | |
100 | ||
101 | void clear() | |
102 | { | |
103 | while(!empty()) | |
104 | pop_front(); | |
105 | } | |
106 | ||
107 | void swap(list &that) // throw() | |
108 | { | |
109 | list temp; | |
110 | temp.splice(temp.begin(), that); // move that to temp | |
111 | that.splice(that.begin(), *this); // move this to that | |
112 | splice(begin(), temp); // move temp to this | |
113 | } | |
114 | ||
115 | void push_front(T const &t) | |
116 | { | |
117 | node *new_node = new node(t); | |
118 | ||
119 | new_node->_next = _sentry._next; | |
120 | new_node->_prev = &_sentry; | |
121 | ||
122 | _sentry._next->_prev = new_node; | |
123 | _sentry._next = new_node; | |
124 | } | |
125 | ||
126 | void push_back(T const &t) | |
127 | { | |
128 | node *new_node = new node(t); | |
129 | ||
130 | new_node->_next = &_sentry; | |
131 | new_node->_prev = _sentry._prev; | |
132 | ||
133 | _sentry._prev->_next = new_node; | |
134 | _sentry._prev = new_node; | |
135 | } | |
136 | ||
137 | void pop_front() | |
138 | { | |
139 | BOOST_ASSERT(!empty()); | |
140 | node *old_node = static_cast<node *>(_sentry._next); | |
141 | _sentry._next = old_node->_next; | |
142 | _sentry._next->_prev = &_sentry; | |
143 | delete old_node; | |
144 | } | |
145 | ||
146 | void pop_back() | |
147 | { | |
148 | BOOST_ASSERT(!empty()); | |
149 | node *old_node = static_cast<node *>(_sentry._prev); | |
150 | _sentry._prev = old_node->_prev; | |
151 | _sentry._prev->_next = &_sentry; | |
152 | delete old_node; | |
153 | } | |
154 | ||
155 | bool empty() const | |
156 | { | |
157 | return _sentry._next == &_sentry; | |
158 | } | |
159 | ||
160 | void splice(iterator it, list &x) | |
161 | { | |
162 | if(x.empty()) | |
163 | return; | |
164 | ||
165 | x._sentry._prev->_next = it._node; | |
166 | x._sentry._next->_prev = it._node->_prev; | |
167 | ||
168 | it._node->_prev->_next = x._sentry._next; | |
169 | it._node->_prev = x._sentry._prev; | |
170 | ||
171 | x._sentry._prev = x._sentry._next = &x._sentry; | |
172 | } | |
173 | ||
174 | void splice(iterator it, list &, iterator xit) | |
175 | { | |
176 | xit._node->_prev->_next = xit._node->_next; | |
177 | xit._node->_next->_prev = xit._node->_prev; | |
178 | ||
179 | xit._node->_next = it._node; | |
180 | xit._node->_prev = it._node->_prev; | |
181 | ||
182 | it._node->_prev = it._node->_prev->_next = xit._node; | |
183 | } | |
184 | ||
185 | reference front() | |
186 | { | |
187 | BOOST_ASSERT(!empty()); | |
188 | return static_cast<node *>(_sentry._next)->_value; | |
189 | } | |
190 | ||
191 | const_reference front() const | |
192 | { | |
193 | BOOST_ASSERT(!empty()); | |
194 | return static_cast<node *>(_sentry._next)->_value; | |
195 | } | |
196 | ||
197 | reference back() | |
198 | { | |
199 | BOOST_ASSERT(!empty()); | |
200 | return static_cast<node *>(_sentry._prev)->_value; | |
201 | } | |
202 | ||
203 | const_reference back() const | |
204 | { | |
205 | BOOST_ASSERT(!empty()); | |
206 | return static_cast<node *>(_sentry._prev)->_value; | |
207 | } | |
208 | ||
209 | iterator begin() | |
210 | { | |
211 | return iterator(_sentry._next); | |
212 | } | |
213 | ||
214 | const_iterator begin() const | |
215 | { | |
216 | return const_iterator(_sentry._next); | |
217 | } | |
218 | ||
219 | iterator end() | |
220 | { | |
221 | return iterator(&_sentry); | |
222 | } | |
223 | ||
224 | const_iterator end() const | |
225 | { | |
226 | return const_iterator(const_cast<node_base *>(&_sentry)); | |
227 | } | |
228 | ||
229 | size_type size() const | |
230 | { | |
231 | return static_cast<size_type>(std::distance(begin(), end())); | |
232 | } | |
233 | }; | |
234 | ||
235 | template<typename T> | |
236 | void swap(list<T> &lhs, list<T> &rhs) | |
237 | { | |
238 | lhs.swap(rhs); | |
239 | } | |
240 | ||
241 | }}} // namespace boost::xpressive::detail | |
242 | ||
243 | #endif |