/*
* $Revision: 2632 $
*
* last checkin:
* $Author: gutwenger $
* $Date: 2012-07-17 21:04:24 +0200 (Di, 17. Jul 2012) $
***************************************************************/
/** \file
* \brief Declaration of doubly linked lists and iterators
*
* \author Carsten Gutwenger and Sebastian Leipert
*
* \par License:
* This file is part of the Open Graph Drawing Framework (OGDF).
*
* \par
* Copyright (C)
* See README.txt in the root directory of the OGDF installation for details.
*
* \par
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* Version 2 or 3 as published by the Free Software Foundation;
* see the file LICENSE.txt included in the packaging of this file
* for details.
*
* \par
* 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 General Public License for more details.
*
* \par
* You should have received a copy of the GNU General Public
* License along with this program; if not, write to the Free
* Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
* Boston, MA 02110-1301, USA.
*
* \see http://www.gnu.org/copyleft/gpl.html
***************************************************************/
#ifdef _MSC_VER
#pragma once
#endif
#ifndef OGDF_LIST_H
#define OGDF_LIST_H
#include "../internal/basic/list_templates.h"
namespace ogdf {
template class List;
template class ListPure;
template class ListIterator;
template class ListConstIterator;
//! The parameterized class \a ListElement represents the structure for elements of doubly linked lists.
template
class ListElement {
friend class ListPure;
friend class List;
friend class ListIterator;
friend class ListConstIterator;
ListElement *m_next; //!< Pointer to successor element.
ListElement *m_prev; //!< Pointer to predecessor element.
E m_x; //!< Stores the content.
//! Constructs a ListElement.
ListElement() : m_next(0), m_prev(0) { }
//! Constructs a ListElement.
ListElement(const E &x) : m_next(0), m_prev(0), m_x(x) { }
//! Constructs a ListElement.
ListElement(const E &x, ListElement *next, ListElement *prev) :
m_next(next), m_prev(prev), m_x(x) { }
OGDF_NEW_DELETE
}; // class ListElement
//! The parameterized class \a ListIterator encapsulates a pointer to a dlist element.
/**
* It is used in order to iterate over doubly linked lists,
* and to specify a position in a doubly linked list. It is possible that
* an iterator encapsulates a null pointer.
*/
template class ListIterator {
ListElement *m_pX; // pointer to associated list element
friend class ListConstIterator;
friend class ListPure;
//! Conversion to pointer to list element.
operator ListElement *() { return m_pX; }
//! Conversion to pointer to list element.
operator const ListElement *() const { return m_pX; }
public:
//! Constructs an iterator pointing to no element.
ListIterator() : m_pX(0) { }
//! Constructs an iterator pointing to \a pX.
ListIterator(ListElement *pX) : m_pX(pX) { }
//! Constructs an iterator that is a copy of \a it.
ListIterator(const ListIterator &it) : m_pX(it.m_pX) { }
//! Returns true iff the iterator points to an element.
bool valid() const { return m_pX != 0; }
//! Equality operator.
bool operator==(const ListIterator &it) const {
return m_pX == it.m_pX;
}
//! Inequality operator.
bool operator!=(const ListIterator &it) const {
return m_pX != it.m_pX;
}
//! Returns successor iterator.
ListIterator succ() const { return m_pX->m_next; }
//! Returns predecessor iterator.
ListIterator pred() const { return m_pX->m_prev; }
//! Returns a reference to the element content.
E &operator*() const { return m_pX->m_x; }
//! Assignment operator.
ListIterator &operator=(const ListIterator &it) {
m_pX = it.m_pX;
return *this;
}
//! Increment operator (prefix).
ListIterator &operator++() {
m_pX = m_pX->m_next;
return *this;
}
//! Increment operator (postfix).
ListIterator operator++(int) {
ListIterator it = *this;
m_pX = m_pX->m_next;
return it;
}
//! Decrement operator (prefix).
ListIterator &operator--() {
m_pX = m_pX->m_prev;
return *this;
}
//! Decrement operator (postfix).
ListIterator operator--(int) {
ListIterator it = *this;
m_pX = m_pX->m_prev;
return it;
}
OGDF_NEW_DELETE
}; // class ListIterator
//---------------------------------------------------------
// ListConstIterator
// const iterator for doubly linked lists
//---------------------------------------------------------
//! The parameterized class \a ListIterator encapsulates a constant pointer to a list element.
/**
* It is used in order to iterate over doubly linked lists,
* and to specify a position in a doubly linked list. It is possible that
* an iterator encapsulates a null pointer. In contrast to ListIterator,
* it is not possible to change the list element pointed to.
*/
template class ListConstIterator {
const ListElement *m_pX; // pointer to list element
friend class ListPure;
//! Conversion to pointer to list element.
operator const ListElement *() { return m_pX; }
public:
//! Constructs an iterator pointing to no element.
ListConstIterator() : m_pX(0) { }
//! Constructs an iterator pointing to \a pX.
ListConstIterator(const ListElement *pX) : m_pX(pX) { }
//! Constructs an iterator that is a copy of \a it.
ListConstIterator(const ListIterator &it) : m_pX((const ListElement *)it) { }
//! Constructs an iterator that is a copy of \a it.
ListConstIterator(const ListConstIterator &it) : m_pX(it.m_pX) { }
//! Returns true iff the iterator points to an element.
bool valid() const { return m_pX != 0; }
//! Equality operator.
bool operator==(const ListConstIterator &it) const {
return m_pX == it.m_pX;
}
//! Inequality operator.
bool operator!=(const ListConstIterator &it) const {
return m_pX != it.m_pX;
}
//! Returns successor iterator.
ListConstIterator succ() const { return m_pX->m_next; }
//! Returns predecessor iterator.
ListConstIterator pred() const { return m_pX->m_prev; }
//! Returns a reference to the element content.
const E &operator*() const { return m_pX->m_x; }
//! Assignment operator.
ListConstIterator &operator=(const ListConstIterator &it) {
m_pX = it.m_pX;
return *this;
}
//! Increment operator (prefix).
ListConstIterator &operator++() {
m_pX = m_pX->m_next;
return *this;
}
//! Increment operator (postfix).
ListConstIterator operator++(int) {
ListConstIterator it = *this;
m_pX = m_pX->m_next;
return it;
}
//! Decrement operator (prefix).
ListConstIterator &operator--() {
m_pX = m_pX->m_prev;
return *this;
}
//! Decrement operator (postfix).
ListConstIterator operator--(int) {
ListConstIterator it = *this;
m_pX = m_pX->m_prev;
return it;
}
OGDF_NEW_DELETE
}; // class ListConstIterator
//! The parameterized class \a ListPure represents doubly linked lists with content type \a E.
/**
* Elements of the list are instances of type ListElement.
* Use ListConstIterator or ListIterator in order to iterate over the list.
*
* In contrast to List, instances of \a ListPure do not store the length of the list.
*
* @tparam E is the data type stored in list elements.
*/
template class ListPure {
protected:
ListElement *m_head; //!< Pointer to first element.
ListElement *m_tail; //!< Pointer to last element.
public:
//! Constructs an empty doubly linked list.
ListPure() : m_head(0), m_tail(0) { }
//! Constructs a doubly linked list that is a copy of \a L.
ListPure(const ListPure &L) : m_head(0), m_tail(0) {
copy(L);
}
// destruction
~ListPure() { clear(); }
typedef E value_type;
typedef ListElement element_type;
typedef ListConstIterator const_iterator;
typedef ListIterator iterator;
//! Returns true iff the list is empty.
bool empty() const { return m_head == 0; }
//! Returns the length of the list
/**
* Notice that this method requires to run through the whole list and takes linear running time!
*/
int size() const {
int count = 0;
for (ListElement *pX = m_head; pX; pX = pX->m_next)
++count;
return count;
}
//! Returns an iterator to the first element of the list.
/**
* If the list is empty, a null pointer iterator is returned.
*/
const ListConstIterator begin() const { return m_head; }
//! Returns an iterator to the first element of the list.
/**
* If the list is empty, a null pointer iterator is returned.
*/
ListIterator begin() { return m_head; }
//! Returns an iterator to one-past-last element of the list.
/**
* This is always a null pointer iterator.
*/
ListConstIterator end() const { return ListConstIterator(); }
//! Returns an iterator to one-past-last element of the list.
/**
* This is always a null pointer iterator.
*/
ListIterator end() { return ListIterator(); }
//! Returns an iterator to the last element of the list.
/**
* If the list is empty, a null pointer iterator is returned.
*/
const ListConstIterator rbegin() const { return m_tail; }
//! Returns an iterator to the last element of the list.
/**
* If the list is empty, a null pointer iterator is returned.
*/
ListIterator rbegin() { return m_tail; }
//! Returns an iterator to one-before-first element of the list.
/**
* This is always a null pointer iterator.
*/
ListConstIterator rend() const { return ListConstIterator(); }
//! Returns an iterator to one-before-first element of the list.
/**
* This is always a null pointer iterator.
*/
ListIterator rend() { return ListIterator(); }
//! Returns a reference to the first element.
/**
* \pre The list is not empty!
*/
const E &front() const {
OGDF_ASSERT(m_head != 0)
return m_head->m_x;
}
//! Returns a reference to the first element.
/**
* \pre The list is not empty!
*/
E &front() {
OGDF_ASSERT(m_head != 0)
return m_head->m_x;
}
//! Returns a reference to the last element.
/**
* \pre The list is not empty!
*/
const E &back() const {
OGDF_ASSERT(m_tail != 0)
return m_tail->m_x;
}
//! Returns a reference to the last element.
/**
* \pre The list is not empty!
*/
E &back() {
OGDF_ASSERT(m_tail != 0)
return m_tail->m_x;
}
//! Returns an iterator to the cyclic successor of \a it.
/**
* \pre \a it points to an element in this list!
*/
ListConstIterator cyclicSucc(ListConstIterator it) const {
const ListElement *pX = it;
return (pX->m_next) ? pX->m_next : m_head;
}
//! Returns an iterator to the cyclic successor of \a it.
/**
* \pre \a it points to an element in this list!
*/
ListIterator cyclicSucc(ListIterator it) {
OGDF_ASSERT(it.valid())
ListElement *pX = it;
return (pX->m_next) ? pX->m_next : m_head;
}
//! Returns an iterator to the cyclic predecessor of \a it.
/**
* \pre \a it points to an element in this list!
*/
ListConstIterator cyclicPred(ListConstIterator it) const {
OGDF_ASSERT(it.valid())
const ListElement *pX = it;
return (pX->m_prev) ? pX->m_prev : m_tail;
}
//! Returns an iterator to the cyclic predecessor of \a it.
/**
* \pre \a it points to an element in this list!
*/
ListIterator cyclicPred(ListIterator it) {
OGDF_ASSERT(it.valid())
ListElement *pX = it;
return (pX->m_prev) ? pX->m_prev : m_tail;
}
//! Returns an iterator pointing to the element at position \a pos.
/**
* The running time of this method is linear in \a pos.
*/
ListConstIterator get(int pos) const {
ListElement *pX;
for(pX = m_head; pX != 0; pX = pX->m_next)
if (pos-- == 0) break;
return pX;
}
//! Returns an iterator pointing to the element at position \a pos.
/**
* The running time of this method is linear in \a pos.
*/
ListIterator get(int pos) {
ListElement *pX;
for(pX = m_head; pX != 0; pX = pX->m_next)
if (pos-- == 0) break;
return pX;
}
//! Returns the position (starting with 0) of iterator \a it in the list.
/**
* \pre \a it is a valid iterator pointing to an element in this list!
*/
int pos(ListConstIterator it) const {
OGDF_ASSERT(it.valid())
int p = 0;
for(ListElement *pX = m_head; pX != 0; pX = pX->m_next, ++p)
if (pX == it) break;
return p;
}
//! Returns an iterator to a random element in the list (or an invalid iterator if the list is empty)
/**
* This method takes linear time.
*/
ListConstIterator chooseIterator() const {
return empty() ? ListConstIterator() : get(randomNumber(0,size()-1));
}
//! Returns an iterator to a random element in the list (or an invalid iterator if the list is empty)
/**
* This method takes linear time.
*/
ListIterator chooseIterator() {
return empty() ? ListIterator() : get(randomNumber(0,size()-1));
}
//! Returns a random element from the list.
/**
* \pre The list is not empty!
*
* This method takes linear time.
*/
const E chooseElement() const {
OGDF_ASSERT(m_head != 0)
return *chooseIterator();
}
//! Returns a random element from the list.
/**
* \pre The list is not empty!
*
* This method takes linear time.
*/
E chooseElement() {
return *chooseIterator();
}
//! Assignment operator.
ListPure &operator=(const ListPure &L) {
clear(); copy(L);
return *this;
}
//! Equality operator.
bool operator==(const ListPure &L) const {
ListElement *pX = m_head, *pY = L.m_head;
while(pX != 0 && pY != 0) {
if(pX->m_x != pY->m_x)
return false;
pX = pX->m_next;
pY = pY->m_next;
}
return (pX == 0 && pY == 0);
}
//! Inequality operator.
bool operator!=(const ListPure &L) const {
return !operator==(L);
}
//! Adds element \a x at the begin of the list.
ListIterator pushFront(const E &x) {
ListElement *pX = OGDF_NEW ListElement(x,m_head,0);
if (m_head)
m_head = m_head->m_prev = pX;
else
m_head = m_tail = pX;
return m_head;
}
//! Adds element \a x at the end of the list.
ListIterator pushBack(const E &x) {
ListElement *pX = OGDF_NEW ListElement(x,0,m_tail);
if (m_head)
m_tail = m_tail->m_next = pX;
else
m_tail = m_head = pX;
return m_tail;
}
//! Inserts element \a x before or after \a it.
/**
* @param x is the element to be inserted.
* @param it is a list iterator in this list.
* @param dir determines if \a x is inserted before or after \a it.
* Possible values are \c ogdf::before and \c ogdf::after.
* \pre \a it points to an element in this list.
*/
ListIterator insert(const E &x, ListIterator it, Direction dir = after) {
OGDF_ASSERT(it.valid())
OGDF_ASSERT(dir == after || dir == before)
ListElement *pY = it, *pX;
if (dir == after) {
ListElement *pYnext = pY->m_next;
pY->m_next = pX = OGDF_NEW ListElement(x,pYnext,pY);
if (pYnext) pYnext->m_prev = pX;
else m_tail = pX;
} else {
ListElement *pYprev = pY->m_prev;
pY->m_prev = pX = OGDF_NEW ListElement(x,pY,pYprev);
if (pYprev) pYprev->m_next = pX;
else m_head = pX;
}
return pX;
}
//! Inserts element \a x before \a it.
/**
* \pre \a it points to an element in this list.
*/
ListIterator insertBefore(const E &x, ListIterator it) {
OGDF_ASSERT(it.valid())
ListElement *pY = it, *pX;
ListElement *pYprev = pY->m_prev;
pY->m_prev = pX = OGDF_NEW ListElement(x,pY,pYprev);
if (pYprev) pYprev->m_next = pX;
else m_head = pX;
return pX;
}
//! Inserts element \a x after \a it.
/**
* \pre \a it points to an element in this list.
*/
ListIterator insertAfter(const E &x, ListIterator it) {
OGDF_ASSERT(it.valid())
ListElement *pY = it, *pX;
ListElement *pYnext = pY->m_next;
pY->m_next = pX = OGDF_NEW ListElement(x,pYnext,pY);
if (pYnext) pYnext->m_prev = pX;
else m_tail = pX;
return pX;
}
//! Removes the first element from the list.
/**
* \pre The list is not empty!
*/
void popFront() {
OGDF_ASSERT(m_head != 0)
ListElement *pX = m_head;
m_head = m_head->m_next;
delete pX;
if (m_head) m_head->m_prev = 0;
else m_tail = 0;
}
//! Removes the first element from the list and returns it.
/**
* \pre The list is not empty!
*/
E popFrontRet() {
E el = front();
popFront();
return el;
}
//! Removes the last element from the list.
/**
* \pre The list is not empty!
*/
void popBack() {
OGDF_ASSERT(m_tail != 0)
ListElement *pX = m_tail;
m_tail = m_tail->m_prev;
delete pX;
if (m_tail) m_tail->m_next = 0;
else m_head = 0;
}
//! Removes the last element from the list and returns it.
/**
* \pre The list is not empty!
*/
E popBackRet() {
E el = back();
popBack();
return el;
}
//! Removes \a it from the list.
/**
* \pre \a it points to an element in this list.
*/
void del(ListIterator it) {
OGDF_ASSERT(it.valid())
ListElement *pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
delete pX;
if (pPrev) pPrev->m_next = pNext;
else m_head = pNext;
if (pNext) pNext->m_prev = pPrev;
else m_tail = pPrev;
}
//! Exchanges the positions of \a it1 and \a it2 in the list.
/**
* \pre \a it1 and \a it2 point to elements in this list.
*/
void exchange(ListIterator it1, ListIterator it2) {
OGDF_ASSERT(it1.valid() && it2.valid() && it1 != it2)
ListElement *pX = it1, *pY = it2;
std::swap(pX->m_next,pY->m_next);
std::swap(pX->m_prev,pY->m_prev);
if(pX->m_next == pX) {
pX->m_next = pY; pY->m_prev = pX;
}
if(pX->m_prev == pX) {
pX->m_prev = pY; pY->m_next = pX;
}
if(pX->m_prev) pX->m_prev->m_next = pX;
else m_head = pX;
if(pY->m_prev) pY->m_prev->m_next = pY;
else m_head = pY;
if(pX->m_next) pX->m_next->m_prev = pX;
else m_tail = pX;
if(pY->m_next) pY->m_next->m_prev = pY;
else m_tail = pY;
}
//! Moves \a it to the begin of the list.
/**
* \pre \a it points to an element in this list.
*/
void moveToFront(ListIterator it) {
OGDF_ASSERT(it.valid())
// remove it
ListElement *pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
//already at front
if (!pPrev) return;
//update old position
if (pPrev) pPrev->m_next = pNext;
if (pNext) pNext->m_prev = pPrev;
else m_tail = pPrev;
// insert it at front
pX->m_prev = 0;
pX->m_next = m_head;
m_head = m_head->m_prev = pX;
}//move
//! Moves \a it to the end of the list.
/**
* \pre \a it points to an element in this list.
*/
void moveToBack(ListIterator it) {
OGDF_ASSERT(it.valid())
// remove it
ListElement *pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
//already at back
if (!pNext) return;
//update old position
if (pPrev) pPrev->m_next = pNext;
else m_head = pNext;
if (pNext) pNext->m_prev = pPrev;
// insert it at back
pX->m_prev = m_tail;
pX->m_next = 0;
m_tail = m_tail->m_next = pX;
}//move
//! Moves \a it after \a itBefore.
/**
* \pre \a it and \a itBefore point to elements in this list.
*/
void moveToSucc(ListIterator it, ListIterator itBefore) {
OGDF_ASSERT(it.valid() && itBefore.valid())
// move it
ListElement *pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
//the same of already in place
ListElement *pY = itBefore;
if(pX == pY || pPrev == pY) return;
// update old position
if (pPrev) pPrev->m_next = pNext;
else m_head = pNext;
if (pNext) pNext->m_prev = pPrev;
else m_tail = pPrev;
// move it after itBefore
ListElement *pYnext = pX->m_next = pY->m_next;
(pX->m_prev = pY)->m_next = pX;
if (pYnext) pYnext->m_prev = pX;
else m_tail = pX;
}//move
//! Moves \a it before \a itAfter.
/**
* \pre \a it and \a itAfter point to elements in this list.
*/
void moveToPrec(ListIterator it, ListIterator itAfter) {
OGDF_ASSERT(it.valid() && itAfter.valid())
// move it
ListElement *pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
//the same of already in place
ListElement *pY = itAfter;
if(pX == pY || pNext == pY) return;
// update old position
if (pPrev) pPrev->m_next = pNext;
else m_head = pNext;
if (pNext) pNext->m_prev = pPrev;
else m_tail = pPrev;
// move it before itAfter
ListElement *pYprev = pX->m_prev = pY->m_prev;
(pX->m_next = pY)->m_prev = pX;
if (pYprev) pYprev->m_next = pX;
else m_head = pX;
}//move
//! Moves \a it to the begin of \a L2.
/**
* \pre \a it points to an element in this list.
*/
void moveToFront(ListIterator it, ListPure &L2) {
OGDF_ASSERT(it.valid())
OGDF_ASSERT(this != &L2)
// remove it
ListElement *pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
if (pPrev) pPrev->m_next = pNext;
else m_head = pNext;
if (pNext) pNext->m_prev = pPrev;
else m_tail = pPrev;
// insert it at front of L2
pX->m_prev = 0;
if ((pX->m_next = L2.m_head) != 0)
L2.m_head = L2.m_head->m_prev = pX;
else
L2.m_head = L2.m_tail = pX;
}
//! Moves \a it to the end of \a L2.
/**
* \pre \a it points to an element in this list.
*/
void moveToBack(ListIterator it, ListPure &L2) {
OGDF_ASSERT(it.valid())
OGDF_ASSERT(this != &L2)
// remove it
ListElement *pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
if (pPrev) pPrev->m_next = pNext;
else m_head = pNext;
if (pNext) pNext->m_prev = pPrev;
else m_tail = pPrev;
// insert it at back of L2
pX->m_next = 0;
if ((pX->m_prev = L2.m_tail) != 0)
L2.m_tail = L2.m_tail->m_next = pX;
else
L2.m_head = L2.m_tail = pX;
}
//! Moves \a it to list \a L2 and inserts it after \a itBefore.
/**
* \pre \a it points to an element in this list, and \a itBefore
* points to an element in \a L2.
*/
void moveToSucc(ListIterator it, ListPure &L2, ListIterator itBefore) {
OGDF_ASSERT(it.valid() && itBefore.valid())
OGDF_ASSERT(this != &L2)
// remove it
ListElement *pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
if (pPrev) pPrev->m_next = pNext;
else m_head = pNext;
if (pNext) pNext->m_prev = pPrev;
else m_tail = pPrev;
// insert it in list L2 after itBefore
ListElement *pY = itBefore;
ListElement *pYnext = pX->m_next = pY->m_next;
(pX->m_prev = pY)->m_next = pX;
if (pYnext) pYnext->m_prev = pX;
else L2.m_tail = pX;
}
//! Moves \a it to list \a L2 and inserts it before \a itAfter.
/**
* \pre \a it points to an element in this list, and \a itAfter
* points to an element in \a L2.
*/
void moveToPrec(ListIterator it, ListPure &L2, ListIterator itAfter) {
OGDF_ASSERT(it.valid() && itAfter.valid())
OGDF_ASSERT(this != &L2)
// remove it
ListElement *pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
if (pPrev) pPrev->m_next = pNext;
else m_head = pNext;
if (pNext) pNext->m_prev = pPrev;
else m_tail = pPrev;
// insert it in list L2 after itBefore
ListElement *pY = itAfter;
ListElement *pYprev = pX->m_prev = pY->m_prev;
(pX->m_next = pY)->m_prev = pX;
if (pYprev) pYprev->m_next = pX;
else L2.m_head = pX;
}
//! Appends \a L2 to this list and makes \a L2 empty.
void conc(ListPure &L2) {
OGDF_ASSERT(this != &L2)
if (m_head)
m_tail->m_next = L2.m_head;
else
m_head = L2.m_head;
if (L2.m_head) {
L2.m_head->m_prev = m_tail;
m_tail = L2.m_tail;
}
L2.m_head = L2.m_tail = 0;
}
//! Prepends \a L2 to this list and makes \a L2 empty.
void concFront(ListPure &L2) {
OGDF_ASSERT(this != &L2)
if (m_head)
m_head->m_prev = L2.m_tail;
else
m_tail = L2.m_tail;
if (L2.m_head) {
L2.m_tail->m_next = m_head;
m_head = L2.m_head;
}
L2.m_head = L2.m_tail = 0;
}
//! Exchanges too complete lists in O(1).
/**
* The list's content is moved to L2 and vice versa.
*/
void exchange(ListPure& L2) {
ListElement* t;
t = this->m_head;
this->m_head = L2.m_head;
L2.m_head = t;
t = this->m_tail;
this->m_tail = L2.m_tail;
L2.m_tail = t;
}
//! Splits the list at element \a it into lists \a L1 and \a L2.
/**
* If \a it is not a null pointer and \a L = x1,...,x{k-1}, \a it,x_{k+1},xn, then
* \a L1 = x1,...,x{k-1} and \a L2 = \a it,x{k+1},...,xn if \a dir = \c before.
* If \a it is a null pointer, then \a L1 is made empty and \a L2 = \a L. Finally
* \a L is made empty if it is not identical to \a L1 or \a L2.
*
* \pre \a it points to an element in this list.
*/
void split(ListIterator it,ListPure &L1,ListPure &L2,Direction dir = before) {
if (&L1 != this) L1.clear();
if (&L2 != this) L2.clear();
if (it.valid()){
L1.m_head = m_head;
L2.m_tail = m_tail;
if (dir == before){
L2.m_head = it;
L1.m_tail = L2.m_head->m_prev;
}
else {
L1.m_tail = it;
L2.m_head = L1.m_tail->m_next;
}
L2.m_head->m_prev = L1.m_tail->m_next = 0;
} else {
L1.m_head = L1.m_tail = 0;
L2.m_head = m_head;
L2.m_tail = m_tail;
}
if (this != &L1 && this != &L2) {
m_head = m_tail = 0;
}
}
//! Splits the list after \a it.
void splitAfter(ListIterator it, ListPure &L2) {
OGDF_ASSERT(it.valid())
OGDF_ASSERT(this != &L2)
L2.clear();
ListElement *pX = it;
if (pX != m_tail) {
(L2.m_head = pX->m_next)->m_prev = 0;
pX->m_next = 0;
L2.m_tail = m_tail;
m_tail = pX;
}
}
//! Splits the list before \a it.
void splitBefore(ListIterator it, ListPure &L2) {
OGDF_ASSERT(it.valid())
OGDF_ASSERT(this != &L2)
L2.clear();
ListElement *pX = it;
L2.m_head = pX; L2.m_tail = m_tail;
if ((m_tail = pX->m_prev) == 0)
m_head = 0;
else
m_tail->m_next = 0;
pX->m_prev = 0;
}
//! Reverses the order of the list elements.
void reverse() {
ListElement *pX = m_head;
m_head = m_tail;
m_tail = pX;
while(pX) {
ListElement *pY = pX->m_next;
pX->m_next = pX->m_prev;
pX = pX->m_prev = pY;
}
}
//! Removes all elements from the list.
void clear() {
if (m_head == 0) return;
#if (_MSC_VER == 1100)
// workaround for bug in Visual Studio 5.0
while (!empty())
popFront();
#else
if (doDestruction((E*)0)) {
for(ListElement *pX = m_head; pX != 0; pX = pX->m_next)
pX->m_x.~E();
}
OGDF_ALLOCATOR::deallocateList(sizeof(ListElement),m_head,m_tail);
#endif
m_head = m_tail = 0;
}
//! Sorts the list using Quicksort.
void quicksort() {
ogdf::quicksortTemplate(*this);
}
//! Sorts the list using Quicksort and comparer \a comp.
template
void quicksort(const COMPARER &comp) {
ogdf::quicksortTemplate(*this,comp);
}
//! Sorts the list using bucket sort.
/**
* @param l is the lowest bucket that will occur.
* @param h is the highest bucket that will occur.
* @param f returns the bucket for each element.
* \pre The bucket function \a f will only return bucket values between \a l
* and \a h for this list.
*/
void bucketSort(int l, int h, BucketFunc &f);
//! Randomly permutes the elements in the list.
void permute() {
permute(size());
}
//! Scans the list for the specified element and returns its position in the list, or -1 if not found.
int search (const E& e) const {
int x = 0;
for(ListConstIterator i = begin(); i.valid(); ++i, ++x)
if(*i == e) return x;
return -1;
}
//! Scans the list for the specified element (using the user-defined comparer) and returns its position in the list, or -1 if not found.
template
int search (const E& e, const COMPARER &comp) const {
int x = 0;
for(ListConstIterator i = begin(); i.valid(); ++i, ++x)
if(comp.equal(*i,e)) return x;
return -1;
}
protected:
void copy(const ListPure &L) {
for(ListElement *pX = L.m_head; pX != 0; pX = pX->m_next)
pushBack(pX->m_x);
}
void permute(const int n);
OGDF_NEW_DELETE
}; // class ListPure
//! Iteration over all iterators \a it of a list \a L, where L is of Type \c List<\a type>.
/**
* Automagically creates a \c ListConstIterator<\a type> named \a it, and runs through the List \a L.
*
* Example
*
* The following code runs through the list \a L, and prints each item
* \code
* List L;
* ...
* forall_listiterators(double, it, L) {
* cout << *it << endl;
* }
* \endcode
*
* Note that this code is equivalent to the following tedious long version
*
* \code
* List L;
* ...
* for( ListConstIterator it = L.begin(); it.valid(); ++it) {
* cout << *it << endl;
* }
* \endcode
*/
#define forall_listiterators(type, it, L) \
for(ListConstIterator< type > it = (L).begin(); it.valid(); ++it)
//! Iteration over all iterators \a it of a list \a L, where L is of Type \c List<\a type>, in reverse order.
/**
* Automagically creates a \c ListConstIterator<\a type> named \a it, and runs through the List \a L, in reverse order.
* See \c #forall_listiterators for an example.
*/
#define forall_rev_listiterators(type, it, L) \
for(ListConstIterator< type > it = (L).rbegin(); it.valid(); --it)
//! Iteration over all non-const iterators \a it of a list \a L, where L is of Type \c List<\a type>.
/**
* Automagically creates a \c ListIterator<\a type> named \a it, and runs through the List \a L.
* See \c #forall_listiterators for an example.
*/
#define forall_nonconst_listiterators(type, it, L) \
for(ListIterator< type > it = (L).begin(); it.valid(); ++it)
//! Iteration over all non-const iterators \a it of a list \a L, where L is of Type \c List<\a type>, in reverse order.
/**
* Automagically creates a \c ListIterator<\a type> named \a it, and runs through the List \a L, in reverse order.
* See \c #forall_listiterators for an example.
*/
#define forall_rev_nonconst_listiterators(type, it, L) \
for(ListIterator< type > it = (L).rbegin(); it.valid(); --it)
//! Iteration over all iterators \a it of a list \a L, where L is of Type \c SList<\a type>.
/**
* Automagically creates a \c SListConstIterator<\a type> named \a it, and runs through the SList \a L.
* See \c #forall_listiterators for an example.
*/
#define forall_slistiterators(type, it, L) \
for(SListConstIterator< type > it = (L).begin(); it.valid(); ++it)
//! Iteration over all non-const iterators \a it of a list \a L, where L is of Type \c SList<\a type>.
/**
* Automagically creates a \c SListIterator<\a type> named \a it, and runs through the SList \a L.
* See \c #forall_listiterators for an example.
*/
#define forall_nonconst_slistiterators(type, it, L) \
for(SListIterator< type > it = (L).begin(); it.valid(); ++it)
//! The parameterized class \a ListPure represents doubly linked lists with content type \a E.
/**
* Elements of the list are instances of type ListElement.
* Use ListConstIterator or ListIterator in order to iterate over the list.
*
* In contrast to ListPure, instances of \a List store the length of the list.
*
* See the \c #forall_listiterators macros for the recommended way how to easily iterate through a
* list.
*
* @tparam E is the data type stored in list elements.
*/
template
class List : private ListPure {
int m_count; //!< The length of the list.
public:
//! Constructs an empty doubly linked list.
List() : m_count(0) { }
//! Constructs a doubly linked list that is a copy of \a L.
List(const List &L) : ListPure(L), m_count(L.m_count) { }
// destruction
~List() { }
typedef E value_type;
typedef ListElement element_type;
typedef ListConstIterator const_iterator;
typedef ListIterator iterator;
//! Returns true iff the list is empty.
bool empty() const { return ListPure::empty(); }
// returns length of list
int size() const { return m_count; }
// returns first element of list (0 if empty)
const ListConstIterator begin() const { return ListPure::begin(); }
// returns first element of list (0 if empty)
ListIterator begin() { return ListPure::begin(); }
// returns iterator to one-past-last element of list
ListConstIterator end() const { return ListConstIterator(); }
// returns iterator to one-past-last element of list
ListIterator end() { return ListIterator(); }
// returns last element of list (0 if empty)
const ListConstIterator rbegin() const { return ListPure::rbegin(); }
// returns last element of list (0 if empty)
ListIterator rbegin() { return ListPure::rbegin(); }
// returns iterator to one-before-first element of list
ListConstIterator rend() const { return ListConstIterator(); }
// returns iterator to one-before-first element of list
ListIterator rend() { return ListIterator(); }
// returns reference to first element
const E &front() const { return ListPure::front(); }
// returns reference to first element
E &front() { return ListPure::front(); }
// returns reference to last element
const E &back() const { return ListPure::back(); }
// returns reference to last element
E &back() { return ListPure::back(); }
// returns cyclic successor
ListConstIterator cyclicSucc(ListConstIterator it) const {
return ListPure::cyclicSucc(it);
}
// returns cyclic successor
ListIterator cyclicSucc(ListIterator it) {
return ListPure::cyclicSucc(it);
}
// returns cyclic predecessor
ListConstIterator cyclicPred(ListConstIterator it) const {
return ListPure::cyclicPred(it);
}
// returns cyclic predecessor
ListIterator cyclicPred(ListIterator it) {
return ListPure::cyclicPred(it);
}
// returns the iterator at position pos. Note that this takes time linear in pos.
ListConstIterator get(int pos) const {
OGDF_ASSERT(0 <= pos && pos < m_count)
return ListPure::get(pos);
}
// returns the iterator at position pos. Note that this takes time linear in pos.
ListIterator get(int pos) {
OGDF_ASSERT(0 <= pos && pos < m_count)
return ListPure::get(pos);
}
//! Returns the position (starting with 0) of iterator \a it in the list.
/**
* \pre \a it is a valid iterator pointing to an element in this list!
*/
int pos(ListConstIterator it) const {
OGDF_ASSERT(it.valid())
return ListPure::pos(it);
}
//! Returns an iterator to a random element in the list (or an invalid iterator if the list is empty)
/**
* This method takes linear time.
*/
ListConstIterator chooseIterator() const {
return (m_count > 0) ? get(randomNumber(0,m_count-1)) : ListConstIterator();
}
//! Returns an iterator to a random element in the list (or an invalid iterator if the list is empty)
/**
* This method takes linear time.
*/
ListIterator chooseIterator() {
return (m_count > 0) ? get(randomNumber(0,m_count-1)) : ListIterator();
}
//! Returns a random element from the list.
/**
* \pre The list is not empty!
*
* This method takes linear time.
*/
const E chooseElement() const {
OGDF_ASSERT(!empty());
return *chooseIterator();
}
//! Returns a random element from the list.
/**
* \pre The list is not empty!
*
* This method takes linear time.
*/
E chooseElement() {
OGDF_ASSERT(!empty());
return *chooseIterator();
}
// assignment
List