123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243 |
- ///////////////////////////////////////////////////////////////////////////////
- // list.hpp
- // A simple implementation of std::list that allows incomplete
- // types, does no dynamic allocation in the default constructor,
- // and has a guarnteed O(1) splice.
- //
- // Copyright 2009 Eric Niebler. Distributed under the Boost
- // Software License, Version 1.0. (See accompanying file
- // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- #ifndef BOOST_XPRESSIVE_DETAIL_CORE_LIST_HPP_EAN_10_26_2009
- #define BOOST_XPRESSIVE_DETAIL_CORE_LIST_HPP_EAN_10_26_2009
- // MS compatible compilers support #pragma once
- #if defined(_MSC_VER)
- # pragma once
- #endif
- #include <cstddef>
- #include <iterator>
- #include <algorithm>
- #include <boost/assert.hpp>
- #include <boost/iterator/iterator_facade.hpp>
- namespace boost { namespace xpressive { namespace detail
- {
- ///////////////////////////////////////////////////////////////////////////////
- // list
- //
- template<typename T>
- struct list
- {
- private:
- struct node_base
- {
- node_base *_prev;
- node_base *_next;
- };
- struct node : node_base
- {
- explicit node(T const &value)
- : _value(value)
- {}
- T _value;
- };
- node_base _sentry;
- template<typename Ref = T &>
- struct list_iterator
- : boost::iterator_facade<list_iterator<Ref>, T, std::bidirectional_iterator_tag, Ref>
- {
- list_iterator(list_iterator<> const &it) : _node(it._node) {}
- explicit list_iterator(node_base *n = 0) : _node(n) {}
- private:
- friend struct list<T>;
- friend class boost::iterator_core_access;
- Ref dereference() const { return static_cast<node *>(_node)->_value; }
- void increment() { _node = _node->_next; }
- void decrement() { _node = _node->_prev; }
- bool equal(list_iterator const &it) const { return _node == it._node; }
- node_base *_node;
- };
- public:
- typedef T *pointer;
- typedef T const *const_pointer;
- typedef T &reference;
- typedef T const &const_reference;
- typedef list_iterator<> iterator;
- typedef list_iterator<T const &> const_iterator;
- typedef std::size_t size_type;
- list()
- {
- _sentry._next = _sentry._prev = &_sentry;
- }
- list(list const &that)
- {
- _sentry._next = _sentry._prev = &_sentry;
- const_iterator it = that.begin(), e = that.end();
- for( ; it != e; ++it)
- push_back(*it);
- }
- list &operator =(list const &that)
- {
- list(that).swap(*this);
- return *this;
- }
- ~list()
- {
- clear();
- }
- void clear()
- {
- while(!empty())
- pop_front();
- }
- void swap(list &that) // throw()
- {
- list temp;
- temp.splice(temp.begin(), that); // move that to temp
- that.splice(that.begin(), *this); // move this to that
- splice(begin(), temp); // move temp to this
- }
- void push_front(T const &t)
- {
- node *new_node = new node(t);
- new_node->_next = _sentry._next;
- new_node->_prev = &_sentry;
- _sentry._next->_prev = new_node;
- _sentry._next = new_node;
- }
- void push_back(T const &t)
- {
- node *new_node = new node(t);
- new_node->_next = &_sentry;
- new_node->_prev = _sentry._prev;
- _sentry._prev->_next = new_node;
- _sentry._prev = new_node;
- }
- void pop_front()
- {
- BOOST_ASSERT(!empty());
- node *old_node = static_cast<node *>(_sentry._next);
- _sentry._next = old_node->_next;
- _sentry._next->_prev = &_sentry;
- delete old_node;
- }
- void pop_back()
- {
- BOOST_ASSERT(!empty());
- node *old_node = static_cast<node *>(_sentry._prev);
- _sentry._prev = old_node->_prev;
- _sentry._prev->_next = &_sentry;
- delete old_node;
- }
- bool empty() const
- {
- return _sentry._next == &_sentry;
- }
- void splice(iterator it, list &x)
- {
- if(x.empty())
- return;
- x._sentry._prev->_next = it._node;
- x._sentry._next->_prev = it._node->_prev;
- it._node->_prev->_next = x._sentry._next;
- it._node->_prev = x._sentry._prev;
- x._sentry._prev = x._sentry._next = &x._sentry;
- }
- void splice(iterator it, list &, iterator xit)
- {
- xit._node->_prev->_next = xit._node->_next;
- xit._node->_next->_prev = xit._node->_prev;
- xit._node->_next = it._node;
- xit._node->_prev = it._node->_prev;
- it._node->_prev = it._node->_prev->_next = xit._node;
- }
- reference front()
- {
- BOOST_ASSERT(!empty());
- return static_cast<node *>(_sentry._next)->_value;
- }
- const_reference front() const
- {
- BOOST_ASSERT(!empty());
- return static_cast<node *>(_sentry._next)->_value;
- }
- reference back()
- {
- BOOST_ASSERT(!empty());
- return static_cast<node *>(_sentry._prev)->_value;
- }
- const_reference back() const
- {
- BOOST_ASSERT(!empty());
- return static_cast<node *>(_sentry._prev)->_value;
- }
- iterator begin()
- {
- return iterator(_sentry._next);
- }
- const_iterator begin() const
- {
- return const_iterator(_sentry._next);
- }
- iterator end()
- {
- return iterator(&_sentry);
- }
- const_iterator end() const
- {
- return const_iterator(const_cast<node_base *>(&_sentry));
- }
- size_type size() const
- {
- return static_cast<size_type>(std::distance(begin(), end()));
- }
- };
- template<typename T>
- void swap(list<T> &lhs, list<T> &rhs)
- {
- lhs.swap(rhs);
- }
- }}} // namespace boost::xpressive::detail
- #endif
|