// $Id: doublelist.h,v 1.1.1.1 2000/11/02 08:47:16 fritzi Exp $

// This file is part of the DEAL Library
// DEAL is Copyright(1995) by
// Roland Becker, Guido Kanschat, Franz-Theo Suttmeier


#ifndef __doublelist_h
#define __doublelist_h

// #pragma interface

/*
CLASS
   DoubleNode

   Implementation class for DoubleList
KEYWORDS
   Container
OVERVIEW
   This class implements a double linked list node for intrusive lists.
   A class that is to be contained in a DoubleList must inherit from
   DoubleNode.
   */
class DoubleNode
{
public:
  friend class DListBase;
  ///////////////
  //
  // Pointer to predecessor
  //
  DoubleNode* pred;
  ///////////////
  //
  // Pointer to successor
  //
  DoubleNode* succ;
  ///////////////
  //
  // Standard constructor creating a non-linked node
  //
  DoubleNode() { pred = succ = 0; }
  ///////////////
  //
  // The function knot inserts the item p before this object into the list.
  //
  void knot(DoubleNode* p);	// Einf"ugen eines Knotens vor *this
  ///////////////
  //
  // Remove this object from the list and update the links of adjacent items.
  void dissolve();
};

//////////
typedef DoubleNode* DoubleNodePtr;
//////////
typedef const DoubleNode* cDoubleNodePtr;

/*
CLASS
   DListBase
   Base class for DoubleList
OVERVIEW
   Internal use only!
   */
class DListBase
{
protected:
  //////////
  DoubleNode listhead;
  
  //////////
  DListBase();
  
  //////////
  void append(DoubleNodePtr);
  //////////
  void insert(DoubleNodePtr);
  
  //////////
  DoubleNodePtr first() const;
  //////////
  DoubleNodePtr last() const;
  //////////
  DoubleNodePtr next(cDoubleNodePtr) const;
  //////////
  DoubleNodePtr prev(cDoubleNodePtr) const;
};

/*
CLASS
   DoubleList
   Double linked intrusive list
KEYWORDS
   Container
OVERVIEW
   This class implements a double linked list. The item class N has
   to be derived from DoubleNode to be linked.
   */
template<class N>
class DoubleList : private DListBase
{
public:
  // GROUP: Insertion

  //////////
  //
  // Append an item to the end of the list.
  //
  void append(N* n) { DListBase::append((DoubleNodePtr) n); }
  //////////
  //
  // Insert an item at the beginning of the list.
  //
  void insert(N* n) { DListBase::insert((DoubleNodePtr) n); }

  // GROUP: Access

  //////////
  //
  // Return address of first item or zero for empty list.
  //
  N* first() const { return (N*) DListBase::first(); }
  //////////
  //
  // Return address of last item or zero for empty list.
  //
  N* last() const { return (N*) DListBase::last(); }
  //////////
  //
  // Skip to next item or return zero at the end of the list.
  //
  N* next(const N* n) const { return (N*) DListBase::next(n); }
  //////////
  //
  // Skip to previous item or return zero at the beginning of the list.
  //
  N* prev(const N* n) const { return (N*) DListBase::prev(n); }
  //////////
  //
  // Remove all items from the list and delete them.
  //
  void cleanup()
  {
    N* s,* su;
    if (!last()) return;
    for(s=first();s;s=su)
    {
      su=next(s);
      delete s;
    }
    listhead.succ = listhead.pred = &listhead;
  }
  //////////
  //
  // Destructor deleting all items.
  //
  ~DoubleList() {  cleanup();  }  
};

inline DListBase::DListBase()
{
  listhead.pred = listhead.succ = &listhead;
}

#endif