dlist.h

This software was done in part for a textbook on AI I ve written called _The Basis of AI_ (tentative

/*******************************************************************************
+
+  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 bytes

virtual 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 operations

protected:

   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