| /////////////////////////////////////////////////////////////////////////////// |
| // 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) && (_MSC_VER >= 1020) |
| # 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 |