/* -*- c++ -*-
C++ Internal storage linked list container.
This file is part of the dpp library of C++ template classes
doc: http://diaxen.ssji.net/dpp/index.html
repo: https://www.ssji.net/svn/projets/trunk/libdpp
This program is free software: you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public License
as published by the Free Software Foundation, either version 3 of
the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this program. If not, see
.
(c) 2008-2011 Alexandre Becoulet
*/
#ifndef DPP_LINKED_LIST_HH_
#define DPP_LINKED_LIST_HH_
#include
#include
/** @file @module{Linked list container} */
namespace dpp {
class linked_list_node;
template
class linked_list_item;
template
class linked_list;
template
class linked_list_iterator;
//////////////////////////////////////////////////////////////////////
// linked_list node class
//////////////////////////////////////////////////////////////////////
/** @short Linked list internal node class
@module{Linked list container}
@header dpp/linked_list
@internal
*/
class linked_list_node
{
template friend class linked_list;
template friend class linked_list_item;
template friend class linked_list_iterator;
linked_list_node *m_next;
linked_list_node *m_prev;
linked_list_node(linked_list_node *next, linked_list_node *prev)
: m_next(next),
m_prev(prev)
{
}
linked_list_node()
{
}
linked_list_node(linked_list_node &l)
: m_next(l.m_next),
m_prev(l.m_prev)
{
}
};
//////////////////////////////////////////////////////////////////////
// linked_list iterator class
//////////////////////////////////////////////////////////////////////
/** @short Linked list iterator class
@module{Linked list container}
@header dpp/linked_list
@internal
*/
template
class linked_list_iterator
{
template friend class linked_list;
template friend class linked_list_item;
template friend class linked_list_iterator;
linked_list_iterator(Xnode *i)
: m_item(i)
{
}
Xnode *m_item;
public:
/** @multiple Standard STL container typedef. */
typedef linked_list_item item_type;
typedef X value_type;
typedef X & reference;
typedef X * pointer;
typedef ssize_t difference_type;
typedef std::bidirectional_iterator_tag iterator_category;
/** */
linked_list_iterator(const linked_list_iterator &i)
: m_item(i.m_item)
{
}
template
linked_list_iterator(const linked_list_iterator &i)
: m_item(i.m_item)
{
// raise error on invalid iterator convertion
static_cast((T*)0);
}
linked_list_iterator()
{
}
linked_list_iterator & operator++()
{
assert(m_item->m_next || !"iterator points to orphan item");
m_item = forward ? m_item->m_next : m_item->m_prev;
return *this;
}
linked_list_iterator operator++(int)
{
assert(m_item->m_next || !"iterator points to orphan item");
linked_list_iterator tmp(*this);
m_item = forward ? m_item->m_next : m_item->m_prev;
return tmp;
}
linked_list_iterator & operator--()
{
assert(m_item->m_next || !"iterator points to orphan item");
m_item = forward ? m_item->m_prev : m_item->m_next;
return *this;
}
linked_list_iterator operator--(int)
{
assert(m_item->m_next || !"iterator points to orphan item");
linked_list_iterator tmp(*this);
m_item = forward ? m_item->m_prev : m_item->m_next;
return tmp;
}
X & operator*() const
{
return const_cast(
static_cast(
static_cast(*m_item)));
}
X * operator->() const
{
return const_cast(
static_cast(
static_cast(m_item)));
}
bool operator==(const linked_list_iterator &i) const
{
return m_item == i.m_item;
}
bool operator!=(const linked_list_iterator &i) const
{
return m_item != i.m_item;
}
};
//////////////////////////////////////////////////////////////////////
// linked_list container class
//////////////////////////////////////////////////////////////////////
/** @short Linked list container class
@module{Linked list container}
@header dpp/linked_list
@main
@showvalue
@This implements the internal storage linked list container.
Item class must inherit from the @ref linked_list_item class
in order to be a valid @ref linked_list container item.
The @tt id template parameter may be used to define several
distinct list containers so that items can be part of more than
one list.
Linked list can be used in @tt smart mode. Smart lists will automatically
remove items from current list when inserting in an other list. Non-smart
list will raise false assertion if non-orphan items are used the
wrong way.
When the linked list contained class doesn't directly inherit from
@ref linked_list_item, the base class which inherits from @ref
linked_list_item must be passed as @tt ItemBase template parameter.
*/
template
class linked_list
{
template friend class linked_list_item;
typedef bool _predicate(const X &a, const X &b);
public:
/** @multiple Standard STL container typedef. */
typedef linked_list_item item_type;
typedef linked_list_iterator iterator;
typedef linked_list_iterator const_iterator;
typedef linked_list_iterator reverse_iterator;
typedef linked_list_iterator const_reverse_iterator;
typedef X value_type;
typedef X & reference;
typedef const X & const_reference;
typedef X * pointer;
typedef const X * const_pointer;
typedef size_t size_type;
typedef ssize_t difference_type;
/** */
private:
void _empty()
{
m_root.m_next = m_root.m_prev = &m_root;
}
static void _insert_post(linked_list_node *a, item_type *b)
{
static_cast(b)->linked_list_pre_insert();
b->_check_orphan();
b->m_prev = a;
a->m_next->m_prev = b;
b->m_next = a->m_next;
a->m_next = b;
}
static void _insert_pre(linked_list_node *a, item_type *b)
{
static_cast(b)->linked_list_pre_insert();
b->_check_orphan();
b->m_next = a;
a->m_prev->m_next = b;
b->m_prev = a->m_prev;
a->m_prev = b;
}
static void _remove(item_type *pos)
{
pos->_check_not_orphan();
pos->m_prev->m_next = pos->m_next;
pos->m_next->m_prev = pos->m_prev;
pos->_set_orphan();
static_cast(pos)->linked_list_post_remove();
}
static void _swap(item_type *a, item_type *b)
{
a->m_next->m_prev = a->m_prev->m_next = b;
b->m_next->m_prev = b->m_prev->m_next = a;
std::swap(a->m_prev, b->m_prev);
std::swap(a->m_next, b->m_next);
}
static void _replace(item_type *out, item_type *in)
{
if (out == in)
return;
out->_check_not_orphan();
static_cast(in)->linked_list_pre_insert();
in->_check_orphan();
out->m_prev->m_next = out->m_next->m_prev = in;
in->m_prev = out->m_prev;
in->m_next = out->m_next;
out->_set_orphan();
static_cast(out)->linked_list_post_remove();
}
// rebuild from a null terminated singly list
void _rebuild(linked_list_node *list)
{
linked_list_node *prev;
m_root.m_next = list;
for (prev = &m_root; list; list = list->m_next)
{
list->m_prev = prev;
prev = list;
}
prev->m_next = &m_root;
m_root.m_prev = prev;
}
// default sort predicate
static bool _default_predicate(const X &a, const X &b)
{
return a < b;
}
// sublist merging function
static linked_list_node * _merge(linked_list_node *a, linked_list_node *b, _predicate *func)
{
linked_list_node *first, *last;
/* choose list head */
if (func(static_cast(static_cast(*a)),
static_cast(static_cast(*b))))
a = (last = first = a)->m_next;
else
b = (last = first = b)->m_next;
/* merge lists */
while (a && b)
if (func(static_cast(static_cast(*a)),
static_cast(static_cast(*b))))
a = (last = last->m_next = a)->m_next;
else
b = (last = last->m_next = b)->m_next;
last->m_next = a ? a : b;
return first;
}
linked_list(const linked_list &l);
linked_list & operator=(const linked_list &);
linked_list_node m_root;
public:
/** @This creates an empty list. */
linked_list()
: m_root(&m_root, &m_root)
{
}
/** @This set all contained items as orphan. */
~linked_list()
{
for (linked_list_node *i = m_root.m_prev; i != &m_root; i = i->m_prev)
{
item_type *t = static_cast(i);
t->_set_orphan();
static_cast(t)->linked_list_post_remove();
}
}
/** @This creates a list from item iterators. */
template
linked_list(input_iterator first, input_iterator last)
: m_root(&m_root, &m_root)
{
for (input_iterator i = first; i != last; i++)
_insert_pre(&m_root, &*i);
}
/** @This push an item in front of this list. */
void push_front(X &i)
{
_insert_post(&m_root, static_cast(&i));
}
/** @This push an item at the end of this list.
@csee linked_list_item::push_back
*/
void push_back(X &i)
{
_insert_pre(&m_root, static_cast(&i));
}
/** @This removes first item from this list.
@csee linked_list_item::push_back
*/
void pop_front()
{
_remove(static_cast(m_root.m_next));
}
/** @This removes last item from this list. */
void pop_back()
{
_remove(static_cast(m_root.m_prev));
}
/** @This inserts an item at specified location in this list.
@return an iterator to inserted item */
iterator insert(const iterator &pos, X &i)
{
item_type *li = static_cast(&i);
_insert_pre(pos.m_item, li);
return iterator(li);
}
/** @This inserts multiple items at specified position in this list.
@return an iterator to first inserted item */
template
iterator insert(const iterator &pos, input_iterator first, input_iterator last)
{
for (input_iterator i = first; i != last; i++)
_insert_pre(pos.m_item, &*i);
return iterator(static_cast(&*first));
}
/** @This removes the item at specified position in this list.
@return an iterator to next item */
iterator erase(iterator pos)
{
linked_list_node *next = pos.m_item->m_next;
_remove(static_cast(pos.m_item));
return iterator(static_cast(next));
}
/** @This removes all items in specified [range) in this list.
@return an iterator to the next item */
iterator erase(iterator first, iterator last)
{
item_type *f = static_cast(&*first);
item_type *l = static_cast(&*last);
f->m_prev->m_next = l;
for (linked_list_node *i = l->m_prev; i != f->m_prev; i = i->m_prev)
{
item_type *t = static_cast(i);
t->_set_orphan();
static_cast(t)->linked_list_post_remove();
}
l->m_prev = f->m_prev;
return iterator(l);
}
/** @This swaps lists contents. */
void swap(linked_list &x)
{
_swap(static_cast(&m_root),
static_cast(&x.m_root));
}
/** @This removes all items from this list. */
void clear()
{
for (linked_list_node *i = m_root.m_prev; i != &m_root; i = i->m_prev)
{
item_type *t = static_cast(i);
t->_set_orphan();
static_cast(t)->linked_list_post_remove();
}
m_root.m_next = m_root.m_prev = &m_root;
}
/** @This removes all items matching specified value from this list
@csee linked_list_item::remove
*/
void remove(const X &v)
{
for (iterator i = begin(); i != end();)
{
if (*i == v)
i = erase(i);
else
++i;
}
}
/** @This replaces an item by an other item in this list.
@return an iterator to replacement item
@csee linked_list_item::replace */
static iterator replace(X &out, X &in)
{
item_type *i = static_cast(&in);
_replace(i, static_cast(&out));
return iterator(i);
}
/** @This tests if this list is empty */
bool empty() const
{
return m_root.m_next == &m_root;
}
/** @This returns list item count, takes O(n). */
size_type size() const
{
size_t s = 0;
for (const_iterator i = begin(); i != end(); ++i)
s++;
return s;
}
/** @This returns maximum container size */
size_type max_size() const
{
return (size_type)(-1);
}
/** @This appends all items from the given list to the end of this list */
void append(linked_list &list)
{
if (!list.empty())
{
list.m_root.m_prev->m_next = &m_root;
list.m_root.m_next->m_prev = m_root.m_prev;
m_root.m_prev->m_next = list.m_root.m_next;
m_root.m_prev = list.m_root.m_prev;
list._empty();
}
}
/** @This appends all item from the given list in front of this list */
void prepend(linked_list &list)
{
if (!list.empty())
{
list.m_root.m_next->m_prev = &m_root;
list.m_root.m_prev->m_next = m_root.m_next;
m_root.m_next->m_prev = list.m_root.m_prev;
m_root.m_next = list.m_root.m_next;
list._empty();
}
}
/** @This merges with specified ordered list according to specified sort predicate */
void merge(linked_list &list, _predicate *func)
{
_rebuild(_merge(m_root.m_next, list.m_root.m_next, func));
list._empty();
}
/** @This merges with specified ordered list using default predicate */
void merge(linked_list &list)
{
merge(list, _default_predicate);
}
/** @This sorts this list according to specified sort predicate */
void sort(_predicate *func)
{
/* Fast linked list stack based merge sort algorithm by Alexandre Becoulet */
if (m_root.m_prev == m_root.m_next)
return;
unsigned int n = 0; /* index of current node pair */
linked_list_node *tail = m_root.m_next; /* remaining unprocessed nodes */
linked_list_node *stack[41]; /* we are able to sort 2^40 nodes here */
linked_list_node **s = stack;
m_root.m_prev->m_next = 0;
while (tail)
{
unsigned int idx, tmp;
/* Pick 2 nodes */
linked_list_node *a = tail;
linked_list_node *b = tail->m_next;
if (!b)
{
*s++ = a;
break;
}
tail = b->m_next;
/* Create a sorted pair list and push it on stack */
if (func(static_cast(static_cast(*a)),
static_cast(static_cast(*b))))
((*s = a)->m_next = b)->m_next = 0;
else
((*s = b)->m_next = a)->m_next = 0;
s++;
/* Reduce stack by merging top lists as if we were building a
complete binary tree from leaf nodes. We compute needed
merge count from bits change in pair index. */
tmp = n++;
for (idx = n ^ tmp; idx &= idx - 1; s--)
s[-2] = _merge(s[-2], s[-1], func);
}
/* Merge all remaining lists */
while (s-- > stack + 1)
s[-1] = _merge(s[-1], s[0], func);
/* rebuild prev links and root */
_rebuild(stack[0]);
}
/** @This sorts this list using default predicate */
void sort()
{
sort(_default_predicate);
}
/** @This returns a reference to the first list item */
X & front() const
{
return static_cast(static_cast(*m_root.m_next));
}
/** @This returns a reference to the last list item */
X & back() const
{
return static_cast(static_cast(*m_root.m_prev));
}
/** @This returns list begin iterator */
iterator begin()
{
return iterator(m_root.m_next);
}
/** @This return list begin const iterator */
const_iterator begin() const
{
return const_iterator(m_root.m_next);
}
/** @This returns list end iterator */
iterator end()
{
return iterator(&m_root);
}
/** @This returns list end const iterator */
const_iterator end() const
{
return const_iterator(&m_root);
}
/** @This returns list begin reverse iterator */
reverse_iterator rbegin()
{
return reverse_iterator(m_root.m_prev);
}
/** @This returns list begin reverse const iterator */
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(m_root.m_prev);
}
/** @This returns list end reverse iterator */
reverse_iterator rend()
{
return reverse_iterator(&m_root);
}
/** @This returns list end reverse const iterator */
const_reverse_iterator rend() const
{
return const_reverse_iterator(&m_root);
}
/** @This clears this list and push a single item */
linked_list & operator=(X &i)
{
clear();
push_back(i);
return *this;
}
/** @This push an item at the end of this list */
linked_list & operator+=(X &i)
{
push_back(i);
return *this;
}
/** @This removes the given item from this list */
linked_list & operator-=(X &i)
{
_remove(static_cast(&i));
return *this;
}
};
//////////////////////////////////////////////////////////////////////
// linked_list item class
//////////////////////////////////////////////////////////////////////
/** @internal */
class linked_list_item_vbase
{
public:
/* These empty default implementations are defined in a virtual base
class to avoid ambiguity when user class inherits from multiple
linked_list_item bases */
void linked_list_post_remove()
{
}
void linked_list_pre_insert()
{
}
};
/** @short Linked list item class
@module{Linked list container}
@header dpp/linked_list
Item class must inherit from this class to be a valid @ref linked_list item.
Multiple inheritance with different @tt id values enables items to
be part of several distinct linked list containers simultaneously.
All membership management functions in this class are @tt
protected. They may still be selectively exposed publicly in the
item class by adding an associated @tt using directive
in the @tt public inherited class part.
*/
template
class linked_list_item
: public linked_list_node
, virtual public linked_list_item_vbase
{
template friend class linked_list;
template friend class linked_list_iterator;
protected:
/** Associated list container type */
typedef linked_list list_type;
private:
linked_list_item(linked_list_item *next, linked_list_item *prev)
: linked_list_node(next, prev)
{
}
void _check_not_orphan() const
{
assert(linked_list_node::m_next != 0 || !"bad operation, item is not part of a linked_list");
}
void _check_orphan()
{
if (smart)
{
// smartly remove from current container if any
if (linked_list_node::m_next != 0)
list_type::_remove(this);
}
else
{
assert(linked_list_node::m_next == 0 || !"bad operation, item is currently part of a linked_list");
}
}
void _set_orphan()
{
linked_list_node::m_next = 0;
}
protected:
typedef linked_list_iterator iterator;
typedef linked_list_iterator const_iterator;
/** @This constructs an orphan list item. */
linked_list_item()
{
_set_orphan();
}
~linked_list_item()
{
_check_orphan();
}
/** @This constructs a list item copy. Items copies are orphan. */
linked_list_item(const linked_list_item &i)
{
_set_orphan();
}
/** @This @b preserves list current membership */
linked_list_item & operator=(const linked_list_item &i)
{
// do not change list membership
return *this;
}
/** @This tests if item is part of a list */
bool orphan()
{
return linked_list_node::m_next == 0;
}
/** @This exchanges this item with specified item. Both items must
be part of a list.
@return an iterator to the replacement item.
*/
iterator swap(X &in)
{
linked_list_item *i = static_cast(&in);
_check_not_orphan();
i->_check_not_orphan();
list_type::_swap(this, i);
return iterator(i);
}
/** @This replaces this item in its list by the given orphan item.
@return an iterator to the replacement item.
*/
iterator replace(X &in)
{
linked_list_item *i = static_cast(&in);
list_type::_replace(this, static_cast(i));
return iterator(i);
}
/** @This removes item from its current list */
void remove()
{
list_type::_remove(this);
}
/** @This inserts an item after this item in the current list */
void push_back(linked_list_item &i)
{
_check_not_orphan();
list_type::_insert_post(this, static_cast(&i));
}
/** @This inserts an item before this item in the current list */
void push_front(linked_list_item &i)
{
_check_not_orphan();
list_type::_insert_pre(this, static_cast(&i));
}
/** @This returns an iterator to this item in the list */
iterator current()
{
_check_not_orphan();
return iterator(this);
}
/** @This returns a const iterator to this item in the list */
const_iterator current() const
{
_check_not_orphan();
return const_iterator(this);
}
/** @This returns an iterator to the next item in the list */
iterator next()
{
_check_not_orphan();
return iterator(linked_list_node::m_next);
}
/** @This returns a const iterator to the next item in the list */
const_iterator next() const
{
_check_not_orphan();
return const_iterator(linked_list_node::m_next);
}
/** @This returns an iterator to the previous item in the list */
iterator prev()
{
_check_not_orphan();
return iterator(linked_list_node::m_prev);
}
/** @This returns a const iterator to the previous item in the list */
const_iterator prev() const
{
_check_not_orphan();
return const_iterator(linked_list_node::m_prev);
}
#ifdef __MKDOC__
/* actual definitions are located in the linked_list_item_vbase class */
/** @This is called when the object has been removed from a linked
list. The call is performed on a reference to @tt X class so a
virtual prototype must be declared in the @tt X class to
override this function from further derived classes. This
default implementation is empty. */
inline void linked_list_post_remove();
/** @This is called when the object becomes part of a linked list. The
call is performed on a reference to @tt X class so a virtual
prototype must be declared in the @tt X class to override this
function from further derived classes. This default
implementation is empty. */
inline void linked_list_pre_insert();
#endif
};
}
#endif