/*******************************************************************************++  LEDA 3.5+++  dlist.h+++  Copyright (c) 1995, 1996, 1997  by  LEDA Software GmbH+  Postfach 151101, 66041 Saarbruecken, Germany+  All rights reserved.+ *******************************************************************************/#ifndef LEDA_DLIST_H#define LEDA_DLIST_H//------------------------------------------------------------------------------//  doubly linked lists//------------------------------------------------------------------------------#include <LEDA/basic.h>class __exportC dlist; class __exportC dlink;typedef dlink* list_item;class __exportC dlink {  dlink* succ;  dlink* pred;  GenPtr e;  dlink(GenPtr a, dlink* pre, dlink* suc)  {     e = a;    succ = suc;    pred = pre;  }  LEDA_MEMORY(dlink)  friend class __exportC dlist;  friend dlink* succ_item(dlink* p) { return p->succ; }  friend dlink* pred_item(dlink* p) { return p->pred; }  //space: 3 words = 12 bytes};//------------------------------------------------------------------------------// dlist: base class for all doubly linked lists//------------------------------------------------------------------------------class __exportC  dlist {   dlink* h;                     //head   dlink* t;                     //tail   dlink* iterator;              //iterator   int count;                    //length of list//space: 4 words + virtual =  5 words = 20 bytesvirtual int  cmp(GenPtr, GenPtr) const { return 0; }virtual int  ord(GenPtr) const { return 0; }virtual void app(GenPtr&) const {}virtual void read_el(GenPtr&,istream&) const {}virtual void print_el(GenPtr&,ostream&) const {}virtual void clear_el(GenPtr&) const {}virtual void copy_el(GenPtr&)  const {}virtual int  el_type_id() const { return UNKNOWN_TYPE_ID; }bool is_smaller(const GenPtr& x, const GenPtr& y){ return cmp(x,y) < 0; }bool is_smaller(const int& x, const int& y)      { return x < y; }bool is_smaller(const float& x, const float& y)  { return x < y; }bool is_smaller(const double& x, const double& y){ return x < y; }void gen_quick_sort(dlink**,GenPtr*,int,int,int);void int_quick_sort(dlink**,int*,int,int,int);void float_quick_sort(dlink**,float*,int,int,int);void double_quick_sort(dlink**,double*,int,int,int);void gen_insertion_sort(dlink**,dlink**,dlink**);void int_insertion_sort(dlink**,dlink**,dlink**);void double_insertion_sort(dlink**,dlink**,dlink**);void recompute_length() const;public:// access operations   int  length() const { if (count < 0) recompute_length(); return count; }   int  size()   const { return length(); }   bool empty()  const { return h==nil; }   // iteration   dlink* first_item()          const { return h; }   dlink* last_item()           const { return t; }   dlink* next_item(dlink* p)   const { return p ? p->succ : 0; }   dlink* pred_item(dlink* p)   const { return p ? p->pred : 0; }   dlink* stl_next_item(dlink* p)   const { return p ? p->succ : h; }   dlink* stl_pred_item(dlink* p)   const { return p ? p->pred : t; }   dlink* first()               const { return h; }   dlink* last()                const { return t; }   dlink* succ(dlink* p)        const { return p->succ; }   dlink* pred(dlink* p)        const { return p->pred; }   dlink* cyclic_succ(dlink*)   const;   dlink* cyclic_pred(dlink*)   const;   dlink* succ(dlink* l, int i) const;    dlink* pred(dlink* l, int i) const;   dlink* get_item(int = 0)     const;    dlink* max() const;   dlink* min() const;   dlink* search(GenPtr) const;   void   remove(GenPtr);   int    rank(GenPtr) const;   GenPtr contents(dlink* l) const { return l->e; }   GenPtr head()             const { return h ? h->e : 0;}   GenPtr tail()             const { return t ? t->e : 0;}// update operationsprotected:   dlink* insert(GenPtr a, dlink* l, int dir=0);   dlink* push(GenPtr a)      { if (count >= 0) count++;     if (h) h = h->pred = new dlink(a,0,h);      else   h = t =  new dlink(a,0,0);     return h;    }      dlink* append(GenPtr a)   { if (count >= 0) count++;     if (t) t = t->succ = new dlink(a,t,0);     else   t = h = new dlink(a,0,0);     return t;     }       void   assign(dlink* l, GenPtr a) { clear_el(l->e); l->e = a; }   void   apply();   void   sort(int,int=0);   void   merge(dlist&,int=0);   void   unique(int=0);public:   GenPtr del(dlink*);   GenPtr pop();   GenPtr Pop();   void  move_to_front(dlink*);   void  move_to_back(dlink*);   void  swap(dlist&);   void  splice(dlink*s, dlist&, dlink*, dlink*);   void  splice(dlink*s, dlist&, dlink*);   void  splice(dlink*s, dlist&);   void  conc(dlist&, int=0);   void  split(list_item, dlist&, dlist&, int=0);   void  bucket_sort(int,int);   void  bucket_sort();   void  reverse_items();   void  reverse();   void  reverse_items(list_item,list_item);   void  reverse(list_item,list_item);   void  permute();   void  clear();// operators   GenPtr&   entry(dlink* l)      const { return l->e; }   GenPtr    inf(dlink* l)        const { return l->e; }   GenPtr&   operator[](dlink* l) const { return l->e; }   dlist& operator=(const dlist&);    dlist  operator+(const dlist&);    void print(ostream&,string, char)       const;       void print(ostream& out,char space=' ') const { print(out,"",space);  }   void print(string s, char space=' ')    const { print(cout,s,space);  }   void print(char space=' ')              const { print(cout,"",space); }      void read(istream&,string, int);     void read(istream& in,int delim) { read(in,"",delim); }   void read(istream& in)           { read(in,"",EOF); }   void read(string s, int delim)   { read(cin,s,delim); }      void read(string s)              { read(cin,s,'\n'); }      void read(char delim)  { read(cin,"",delim);}     void read()            { read(cin,"",'\n');}  // constructors & destructors   dlist();       dlist(GenPtr a);   dlist(const dlist&);   virtual ~dlist()  { clear(); }   int space()  const { return sizeof(dlist) + length() * sizeof(dlink); }};#endif