//==========================================================================
//
// symlist.h
//
//==========================================================================
// $Id: symlist.h,v 1.11 2000/01/05 16:32:41 raitner Exp $
#ifndef SYMLIST_H
#define SYMLIST_H
#include <GTL/GTL.h>
#include <cassert>
__GTL_BEGIN_NAMESPACE
/**
* @internal
*/
template <class T>
struct GTL_EXTERN symnode
{
symnode () { };
symnode (const T& n) : data (n) { };
symnode* adj[2];
T data;
};
/**
* @internal
*/
template <class T, class Ref>
struct GTL_EXTERN symlist_iterator
{
typedef symlist_iterator<T, Ref> self;
typedef symnode<T>* linktype;
symlist_iterator () : act (0) { }
symlist_iterator (const self& it) : act (it.act), dir (it.dir) { }
symlist_iterator (linktype _act, int _dir) : act (_act), dir (_dir) { }
symlist_iterator (linktype _act, linktype _prev) : act (_act),
dir (where_not (_act, _prev)) { };
self& operator= (const self& it)
{ act = it.act; dir = it.dir; return *this; }
bool operator== (const self& it) const
{ return act == it.act; }
bool operator!= (const self& it) const
{ return act != it.act; }
Ref operator*()
{ return act->data;}
self& operator++ ();
self& operator-- ();
static int where (linktype _act, linktype _prev)
{ return _prev == _act->adj[0] ? 0 : 1; }
static int where_not (linktype _act, linktype _prev)
{ return _prev == _act->adj[1] ? 0 : 1; }
void turn ()
{ dir = 1 - dir; }
linktype& next ()
{ return act->adj[dir]; }
linktype& prev ()
{ return act->adj[1 - dir]; }
linktype act;
int dir;
};
/**
* @short list which can be reversed in O(1).
*
* The problem with the STL class list - as with most doubly linked lists --
* is that isn't possible to turn it in constant time, because each entry in
* the list contains next and prev pointer and turning the list means to switch
* these two in <em>each</em> element in the list. Another point is the splice operation
* in STL lists, which is constant time, but for the same reason as mentioned above it
* is not possible to splice a list in reverse order into another in constant
* time.
*
* <p> The problems arise from the fact that each element "knows" what its next
* and previous elements are. An element in a symlist only knows what its
* neighbors are, what is next and what previous depends on the direction of
* iteration. This of course imposes some overhead in iteration (one if-statement)
* but allows reversion and a splice in reversed order in constant time.
*/
template <class T>
class GTL_EXTERN symlist
{
public:
/**
* @internal
*/
typedef symlist_iterator<T, T&> iterator;
/**
* @internal
*/
typedef symlist_iterator<T, const T&> const_iterator;
/**
* Creates empty symlist.
*/
symlist ()
{ link = new symnode<T>; link->adj[0] = link->adj[1] = link; }
/**
* Makes the created list a copy of <code>li</code>.
*
* @param <code>li</code> symlist.
*/
symlist (const symlist<T>& li);
/**
* Assignes <code>li</code> to this list. Note: all elements in this
* list will be deleted.
*
* @param <code>li</code>
* @return this list
*/
symlist<T>& operator= (const symlist<T>& li);
/**
* Destructor
*/
~symlist ();
/**
* Checks whether list is empty. Takes constant time.
*
* @return true iff list is empty
*/
bool empty () const
{ return link->adj[0] == link && link->adj[1] == link; }
/**
* First element in list. Assumes that list ins't empty.
*
* @return first element.
*/
T& front ()
{ return link->adj[0]->data; }
/**
* Last element in list. Assumes that list ins't empty.
*
* @return last element.
*/
T& back ()
{ return link->adj[1]->data; }
/**
* Start iteration through elements of list
*
* @return start iterator
*/
iterator begin ()
{ return ++end(); }
/**
* End of iteration through elements of list
*
* @return end iterator
*/
iterator end ()
{ return iterator (link, 0); }
/**
* Start iteration through elements of list
*
* @return start iterator
*/
const_iterator begin () const
{ return ++end(); }
/**
* End of iteration through elements of list
*
* @return end iterator
*/
const_iterator end () const
{ return const_iterator (link, 0); }
/**
* Start iteration through element of list in reverse order
*
* @return start iterator
*/
iterator rbegin ()
{ return ++rend(); }
/**
* End of iteration through elements of list in reverse order
*
* @return end iterator
*/
iterator rend ()
{ return iterator (link, 1); }
/**
* Start iteration through element of list in reverse order
*
* @return start iterator
*/
const_iterator rbegin () const
{ return ++rend(); }
/**
* End of iteration through elements of list in reverse order
*
* @return end iterator
*/
const_iterator rend () const
{ return const_iterator (link, 1); }
/**
* Inserts <code>data</code> before <code>pos</code> in list.
*
* @param <code>pos</code> position
* @param <code>data</code> element to be inserted
* @return position of insertion
*/
iterator insert (iterator pos, const T& data);
/**
* Inserts the element <code>it</code> points to before <code>pos</code>
* into this list. It is assumed that the element <code>it</code> refers
* lies in a different list. All iterators to elements in either of the
* two lists stay valid. Takes constant time.
*
* @param <code>pos</code> position
* @param <code>it</code> position of element to be inserted
*/
void splice (iterator pos, iterator it);
/**
* Inserts the elements <code>[it,end)</code> refers to before <code>pos</code>
* into this list. It is assumed that <code>[it,end)</code>
* lies in a different list. All iterators to elements in either of the
* two lists stay valid. Takes constant time.
*
* @param <code>pos</code> position
* @param <code>it</code> position of first element to be inserted
* @param <code>it</code> position of one-past the last element to be inserted
*/
void splice (iterator pos, iterator it, iterator end);
/**
* Deletes element at position <code>pos</code> from list.
*
* @param <code>pos</code> position to be deleted
* @return position of next element.
*/
iterator erase (iterator pos);
/**
* Deletes the elements <code>[it, end)</code> from list.
*
* @param <code>it</code> first position to be deleted
* @param <code>end</code> one-past the last position to be deleted
* @return position of next element.
*/
iterator erase (iterator it, iterator end);
/**
* @internal
*/
void attach_sublist (iterator, iterator);
/**
* @internal
*/
void detach_sublist ();
/**
* Change the direction of list. Takes constant time.
*/
void turn ();
private:
symnode<T>* link;
// needed only when used as sublist.
iterator _prev;
iterator _next;
};
//--------------------------------------------------------------------------
// IMPLEMENTATION
//--------------------------------------------------------------------------
template <class T, class Ref>
symlist_iterator<T, Ref>& symlist_iterator<T, Ref>::operator++ ()
{
symnode<T>* prev = act;
act = act->adj[dir];
dir = where_not (act, prev);
return *this;
}
template <class T, class Ref>
symlist_iterator<T, Ref>& symlist_iterator<T, Ref>::operator-- ()
{
symnode<T>* prev = act;
act = act->adj[1 - dir];
dir = where (act, prev);
return *this;
}
template <class T>
symlist<T>::symlist (const symlist<T>& l)
{
link = new symnode<T>;
link->adj[0] = link->adj[1] = link;
const_iterator it = l.begin();
const_iterator e = l.end();
while (it != e) {
insert (end(), *it);
++it;
}
}
template <class T>
symlist<T>::~symlist ()
{
if (_next == iterator()) {
erase (begin(), end());
} else {
detach_sublist();
}
delete link;
}
template <class T>
symlist<T>& symlist<T>::operator= (const symlist<T>& l)
{
erase (begin(), end());
const_iterator it = l.begin();
const_iterator e = l.end();
while (it != e) {
insert (end(), *it);
++it;
}
return *this;
}
template <class T>
symlist_iterator<T, T&> symlist<T>::insert (symlist_iterator<T,T&> pos,
const T& ins)
{
iterator prev = pos;
--prev;
symnode<T>* n = new symnode<T> (ins);
n->adj[0] = pos.act;
n->adj[1] = prev.act;
if (pos == prev) {
pos = prev;
}
pos.prev() = n;
prev.next() = n;
return iterator (n, 0);
}
template <class T>
void symlist<T>::splice (symlist_iterator<T, T&> pos,
symlist_iterator<T, T&> beg, symlist_iterator<T, T&> end)
{
if (beg != end) {
iterator prev = beg;
--prev;
iterator last = end;
--last;
//
// The following seems to be rather senseless, but it is required
// since two iterator are equal, iff the point to the same element.
// This implies that they might have different directions. Suppose
// that prev == end is true and they have different directions,
// than prev.next() and end.prev() return the same element !! Thus
// the assignment prev = end corrects this, since the direction
// gets copied, too.
//
if (prev == end) {
prev = end;
}
prev.next() = end.act;
end.prev() = prev.act;
prev = pos;
--prev;
if (pos == prev) {
pos = prev;
}
if (last == beg) {
last = beg;
}
prev.next() = beg.act;
beg.prev() = prev.act;
pos.prev() = last.act;
last.next() = pos.act;
}
}
template <class T>
void symlist<T>::splice (symlist_iterator<T,T&> pos,
symlist_iterator<T,T&> beg)
{
iterator tmp = beg;
++tmp;
splice (pos, beg, tmp);
}
template <class T>
symlist_iterator<T,T&> symlist<T>::erase (symlist_iterator<T,T&> pos)
{
assert (pos.act != link);
iterator prev = pos;
--prev;
iterator next = pos;
++next;
if (next == prev) {
next = prev;
}
next.prev() = prev.act;
prev.next() = next.act;
delete (pos.act);
return next;
}
template <class T>
symlist_iterator<T,T&> symlist<T>::erase (symlist_iterator<T,T&> beg,
symlist_iterator<T,T&> end)
{
iterator prev = beg;
--prev;
iterator it = beg;
symnode<T>* act;
while (it != end) {
assert (it.act != link);
act = it.act;
++it;
delete (act);
}
if (prev == end) {
prev = end;
}
end.prev() = prev.act;
prev.next() = end.act;
return end;
}
template <class T>
void symlist<T>::attach_sublist (symlist_iterator<T,T&> it,
symlist_iterator<T,T&> end)
{
assert (empty());
iterator last = end;
--last;
_prev = it;
--_prev;
_next = end;
if (it == last) {
it = last;
}
link->adj[0] = it.act;
it.prev() = link;
link->adj[1] = last.act;
last.next() = link;
}
template <class T>
void symlist<T>::detach_sublist ()
{
if (_next != iterator()) {
iterator it (begin());
iterator e (end());
--e;
if (e == it) {
e = it;
}
_prev.next() = it.act;
it.prev() = _prev.act;
_next.prev() = e.act;
e.next() = _next.act;
link->adj[0] = link->adj[1] = link;
_next = iterator();
_prev = iterator();
}
}
template <class T>
inline void symlist<T>::turn ()
{
symnode<T>* tmp = link->adj[0];
link->adj[0] = link->adj[1];
link->adj[1] = tmp;
}
__GTL_END_NAMESPACE
#endif // SYMLIST_H
//--------------------------------------------------------------------------
// end of file
//--------------------------------------------------------------------------
Documentation generated by raitner@hyperion on Tue Mar 7 09:40:04 CET 2000
|
Kdoc |