//=======================================================================
|
// Copyright 2002 Indiana University.
|
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
|
//
|
// 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_LIST_BASE_HPP
|
#define BOOST_LIST_BASE_HPP
|
|
#include <boost/iterator_adaptors.hpp>
|
|
// Perhaps this should go through formal review, and move to <boost/>.
|
|
/*
|
An alternate interface idea:
|
Extend the std::list functionality by creating remove/insert
|
functions that do not require the container object!
|
*/
|
|
namespace boost
|
{
|
namespace detail
|
{
|
|
//=========================================================================
|
// Linked-List Generic Implementation Functions
|
|
template < class Node, class Next >
|
inline Node slist_insert_after(Node pos, Node x, Next next)
|
{
|
next(x) = next(pos);
|
next(pos) = x;
|
return x;
|
}
|
|
// return next(pos) or next(next(pos)) ?
|
template < class Node, class Next >
|
inline Node slist_remove_after(Node pos, Next next)
|
{
|
Node n = next(pos);
|
next(pos) = next(n);
|
return n;
|
}
|
|
template < class Node, class Next >
|
inline Node slist_remove_range(Node before_first, Node last, Next next)
|
{
|
next(before_first) = last;
|
return last;
|
}
|
|
template < class Node, class Next >
|
inline Node slist_previous(Node head, Node x, Node empty, Next next)
|
{
|
while (head != empty && next(head) != x)
|
head = next(head);
|
return head;
|
}
|
|
template < class Node, class Next >
|
inline void slist_splice_after(
|
Node pos, Node before_first, Node before_last, Next next)
|
{
|
if (pos != before_first && pos != before_last)
|
{
|
Node first = next(before_first);
|
Node after = next(pos);
|
next(before_first) = next(before_last);
|
next(pos) = first;
|
next(before_last) = after;
|
}
|
}
|
|
template < class Node, class Next >
|
inline Node slist_reverse(Node node, Node empty, Next next)
|
{
|
Node result = node;
|
node = next(node);
|
next(result) = empty;
|
while (node)
|
{
|
Node next = next(node);
|
next(node) = result;
|
result = node;
|
node = next;
|
}
|
return result;
|
}
|
|
template < class Node, class Next >
|
inline std::size_t slist_size(Node head, Node empty, Next next)
|
{
|
std::size_t s = 0;
|
for (; head != empty; head = next(head))
|
++s;
|
return s;
|
}
|
|
template < class Next, class Data > class slist_iterator_policies
|
{
|
public:
|
explicit slist_iterator_policies(const Next& n, const Data& d)
|
: m_next(n), m_data(d)
|
{
|
}
|
|
template < class Reference, class Node >
|
Reference dereference(type< Reference >, const Node& x) const
|
{
|
return m_data(x);
|
}
|
|
template < class Node > void increment(Node& x) const { x = m_next(x); }
|
|
template < class Node > bool equal(Node& x, Node& y) const
|
{
|
return x == y;
|
}
|
|
protected:
|
Next m_next;
|
Data m_data;
|
};
|
|
//===========================================================================
|
// Doubly-Linked List Generic Implementation Functions
|
|
template < class Node, class Next, class Prev >
|
inline void dlist_insert_before(Node pos, Node x, Next next, Prev prev)
|
{
|
next(x) = pos;
|
prev(x) = prev(pos);
|
next(prev(pos)) = x;
|
prev(pos) = x;
|
}
|
|
template < class Node, class Next, class Prev >
|
void dlist_remove(Node pos, Next next, Prev prev)
|
{
|
Node next_node = next(pos);
|
Node prev_node = prev(pos);
|
next(prev_node) = next_node;
|
prev(next_node) = prev_node;
|
}
|
|
// This deletes every node in the list except the
|
// sentinel node.
|
template < class Node, class Delete >
|
inline void dlist_clear(Node sentinel, Delete del)
|
{
|
Node i, tmp;
|
i = next(sentinel);
|
while (i != sentinel)
|
{
|
tmp = i;
|
i = next(i);
|
del(tmp);
|
}
|
}
|
|
template < class Node > inline bool dlist_empty(Node dummy)
|
{
|
return next(dummy) == dummy;
|
}
|
|
template < class Node, class Next, class Prev >
|
void dlist_transfer(Node pos, Node first, Node last, Next next, Prev prev)
|
{
|
if (pos != last)
|
{
|
// Remove [first,last) from its old position
|
next(prev(last)) = pos;
|
next(prev(first)) = last;
|
next(prev(pos)) = first;
|
|
// Splice [first,last) into its new position
|
Node tmp = prev(pos);
|
prev(pos) = prev(last);
|
prev(last) = prev(first);
|
prev(first) = tmp;
|
}
|
}
|
|
template < class Next, class Prev, class Data >
|
class dlist_iterator_policies : public slist_iterator_policies< Next, Data >
|
{
|
typedef slist_iterator_policies< Next, Data > Base;
|
|
public:
|
template < class Node > void decrement(Node& x) const { x = m_prev(x); }
|
|
dlist_iterator_policies(Next n, Prev p, Data d) : Base(n, d), m_prev(p)
|
{
|
}
|
|
protected:
|
Prev m_prev;
|
};
|
|
} // namespace detail
|
} // namespace boost
|
|
#endif // BOOST_LIST_BASE_HPP
|
