///////////////////////////////////////////////////////////////////////////////
|
// 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
|
