// Programm: list.h
// Doppelt verkettete Listen
#include
#include
#include
namespace ifm {
//
// ListElement: Die Elemente der Liste
//
class ListElement {
public:
ListElement(int x, ListElement* p, ListElement* n);
int data;
friend class List;
friend class ListIterator;
friend class ListConstIterator;
friend std::ostream& operator<<(std::ostream& o, const List& l);
private:
ListElement* prev_;
ListElement* next_;
};
ListElement::ListElement(int x, ListElement* p, ListElement* n)
: data(x), prev_(p), next_(n)
{}
//
// Iterator Klassen
//
class ListIterator {
public:
typedef int value_type;
typedef int* pointer;
typedef int& reference;
typedef std::ptrdiff_t difference_type;
typedef std::bidirectional_iterator_tag iterator_category;
typedef ListIterator This;
ListIterator(ListElement* p) : ptr_(p) {}
friend bool operator==(const This& x, const This& y);
int& operator*() const { return ptr_->data; }
This& operator++() { ptr_ = ptr_->next_; return *this; }
This operator++(int) { This t = *this; ++*this; return t; }
This& operator--() { ptr_ = ptr_->prev_; return *this; }
This operator--(int) { This t = *this; --*this; return t; }
friend class List;
private:
ListElement* ptr_;
};
bool operator==(const ListIterator& x, const ListIterator& y)
{ return x.ptr_ == y.ptr_; }
bool operator!=(const ListIterator& x, const ListIterator& y)
{ return !(x == y); }
class ListConstIterator {
public:
typedef int value_type;
typedef int* pointer;
typedef int& reference;
typedef std::ptrdiff_t difference_type;
typedef std::bidirectional_iterator_tag iterator_category;
typedef ListConstIterator This;
ListConstIterator(const ListElement* p) : ptr_(p) {}
friend bool operator==(const This& x, const This& y);
const int& operator*() const { return ptr_->data; }
This& operator++() { ptr_ = ptr_->next_; return *this; }
This operator++(int) { This t = *this; ++*this; return t; }
This& operator--() { ptr_ = ptr_->prev_; return *this; }
This operator--(int) { This t = *this; --*this; return t; }
friend class List;
private:
const ListElement* ptr_;
};
bool operator==(const ListConstIterator& x, const ListConstIterator& y)
{ return x.ptr_ == y.ptr_; }
bool operator!=(const ListConstIterator& x, const ListConstIterator& y)
{ return !(x == y); }
//
// Die Liste
//
class List {
public:
typedef ListIterator iterator;
typedef ListConstIterator const_iterator;
List(); // POST: Initialisiert zu leerer Liste.
~List(); // POST: Alle Listenelemente geloescht.
List(const List& l); // POST: Initialisiert zu l.
List& operator=(const List&); // POST: Ersetzt durch l.
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
void insert(int x, iterator i);
// PRE: i ist aus [begin(),end())
// POST: fuege x vor i ein.
void erase(iterator i);
// PRE: i ist aus [begin(), end())
// POST: i aus Liste entfernt
private:
void append(const_iterator b, const_iterator e);
// POST: die Elemente aus [b,e) wurden am Ende der Liste
// eingefuegt, d.h. *[b,e) ist Suffix der Liste.
void destroy(iterator b, iterator e);
// POST: die Elemente aus [b,e) wurden geloescht, der belegte
// Speicher wurde freigegeben.
ListElement sentinel;
};
//
// Memberfunktionen von List
//
List::List() : sentinel(0, 0, 0)
{
sentinel.next_ = &sentinel;
sentinel.prev_ = &sentinel;
}
List::~List() { destroy(begin(), end()); }
List::List(const List& l) : sentinel(0, 0, 0)
{
sentinel.next_ = &sentinel;
sentinel.prev_ = &sentinel;
append(l.begin(), l.end());
}
List& List::operator=(const List& l)
{
if (&l != this) {
destroy(begin(), end());
append(l.begin(), l.end());
}
return *this;
}
void List::append(const_iterator b, const_iterator e)
{ for (; b != e; ++b) insert(*b, end()); }
void List::destroy(iterator b, iterator e)
{
while (b != e) {
iterator d = b++;
delete d.ptr_;
}
}
List::const_iterator List::begin() const { return sentinel.next_; }
List::const_iterator List::end() const { return &sentinel; }
List::iterator List::begin() { return sentinel.next_; }
List::iterator List::end() { return &sentinel; }
void List::insert(int x, iterator i)
// PRE: i ist aus [begin(),end())
// POST: fuege x vor i ein.
{
ListElement* ip = i.ptr_;
ListElement* n = new ListElement(x, ip->prev_, ip);
n->prev_->next_ = n;
n->next_->prev_ = n;
}
void List::erase(iterator i)
// PRE: i ist aus [begin(), end())
// POST: i aus Liste entfernt
{
ListElement* ip = i.ptr_;
ip->prev_->next_ = ip->next_;
ip->next_->prev_ = ip->prev_;
delete ip;
}
std::ostream& operator<<(std::ostream& o, const List& l)
{
o << "(";
for (List::const_iterator i = l.begin(); i != l.end(); ++i)
o << *i << ",";
return o << ")";
}
} // namespace ifm
