1 ///////////////////////////////////////////////////////////////////////////////
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.
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)
11 #ifndef BOOST_XPRESSIVE_DETAIL_CORE_LIST_HPP_EAN_10_26_2009
12 #define BOOST_XPRESSIVE_DETAIL_CORE_LIST_HPP_EAN_10_26_2009
14 // MS compatible compilers support #pragma once
22 #include <boost/assert.hpp>
23 #include <boost/iterator/iterator_facade.hpp>
25 namespace boost { namespace xpressive { namespace detail
28 ///////////////////////////////////////////////////////////////////////////////
41 struct node : node_base
43 explicit node(T const &value)
52 template<typename Ref = T &>
54 : boost::iterator_facade<list_iterator<Ref>, T, std::bidirectional_iterator_tag, Ref>
56 list_iterator(list_iterator<> const &it) : _node(it._node) {}
57 explicit list_iterator(node_base *n = 0) : _node(n) {}
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; }
70 typedef T const *const_pointer;
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;
79 _sentry._next = _sentry._prev = &_sentry;
82 list(list const &that)
84 _sentry._next = _sentry._prev = &_sentry;
85 const_iterator it = that.begin(), e = that.end();
90 list &operator =(list const &that)
92 list(that).swap(*this);
107 void swap(list &that) // throw()
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
115 void push_front(T const &t)
117 node *new_node = new node(t);
119 new_node->_next = _sentry._next;
120 new_node->_prev = &_sentry;
122 _sentry._next->_prev = new_node;
123 _sentry._next = new_node;
126 void push_back(T const &t)
128 node *new_node = new node(t);
130 new_node->_next = &_sentry;
131 new_node->_prev = _sentry._prev;
133 _sentry._prev->_next = new_node;
134 _sentry._prev = new_node;
139 BOOST_ASSERT(!empty());
140 node *old_node = static_cast<node *>(_sentry._next);
141 _sentry._next = old_node->_next;
142 _sentry._next->_prev = &_sentry;
148 BOOST_ASSERT(!empty());
149 node *old_node = static_cast<node *>(_sentry._prev);
150 _sentry._prev = old_node->_prev;
151 _sentry._prev->_next = &_sentry;
157 return _sentry._next == &_sentry;
160 void splice(iterator it, list &x)
165 x._sentry._prev->_next = it._node;
166 x._sentry._next->_prev = it._node->_prev;
168 it._node->_prev->_next = x._sentry._next;
169 it._node->_prev = x._sentry._prev;
171 x._sentry._prev = x._sentry._next = &x._sentry;
174 void splice(iterator it, list &, iterator xit)
176 xit._node->_prev->_next = xit._node->_next;
177 xit._node->_next->_prev = xit._node->_prev;
179 xit._node->_next = it._node;
180 xit._node->_prev = it._node->_prev;
182 it._node->_prev = it._node->_prev->_next = xit._node;
187 BOOST_ASSERT(!empty());
188 return static_cast<node *>(_sentry._next)->_value;
191 const_reference front() const
193 BOOST_ASSERT(!empty());
194 return static_cast<node *>(_sentry._next)->_value;
199 BOOST_ASSERT(!empty());
200 return static_cast<node *>(_sentry._prev)->_value;
203 const_reference back() const
205 BOOST_ASSERT(!empty());
206 return static_cast<node *>(_sentry._prev)->_value;
211 return iterator(_sentry._next);
214 const_iterator begin() const
216 return const_iterator(_sentry._next);
221 return iterator(&_sentry);
224 const_iterator end() const
226 return const_iterator(const_cast<node_base *>(&_sentry));
229 size_type size() const
231 return static_cast<size_type>(std::distance(begin(), end()));
236 void swap(list<T> &lhs, list<T> &rhs)
241 }}} // namespace boost::xpressive::detail