boost/xpressive/detail/core/list.hpp

   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