home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / list.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  9.3 KB  |  298 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  list.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #ifndef LISTH
  18. #define LISTH
  19.  
  20. /*------------------------------------------------------------------------------ 
  21.     list (doubled linked lists)
  22.  
  23.     Stefan Naeher
  24.     FB10 Informatik 
  25.     Universitaet des Saarlandes 
  26.     6600 Saarbruecken
  27.  
  28.     September 1988
  29.     
  30. ------------------------------------------------------------------------------*/
  31.  
  32. #include <LEDA/basic.h>
  33.  
  34. //------------------------------------------------------------------------------
  35. // some declarations
  36. //------------------------------------------------------------------------------
  37.  
  38. class dlist; 
  39. class dlink;
  40.  
  41. typedef dlink* list_item;
  42.  
  43.  
  44. //------------------------------------------------------------------------------
  45. // class dlink (list items)
  46. //------------------------------------------------------------------------------
  47.  
  48. class dlink {
  49.  
  50.   friend class dlist;
  51.  
  52.   dlink* succ;
  53.   dlink* pred;
  54.   ent e;
  55.  
  56.   dlink(ent a, dlink* pre, dlink* suc)
  57.   { 
  58.     e = a;
  59.     succ = suc;
  60.     pred = pre;
  61.   }
  62.  
  63.   OPERATOR_NEW(3)
  64.   OPERATOR_DEL(3)
  65.  
  66. //space: 3 words = 12 bytes
  67. };
  68.  
  69.  
  70. //------------------------------------------------------------------------------
  71. // dlist: base class for all doubly linked lists
  72. //------------------------------------------------------------------------------
  73.  
  74. class dlist {
  75.  
  76.    dlink* h;                     //head
  77.    dlink* t;                     //tail
  78.    dlink* iterator;              //iterator
  79.    int count;                    //length of list
  80.  
  81. //space: 4 words + virtual =  5 words = 20 bytes
  82.  
  83. // virtual int cmp(ent& x, ent& y) { return x-y; }
  84.  
  85. virtual void print_el(ent& x,ostream& out) const { out << int(x); }
  86. virtual void read_el(ent& x,istream& in)   const { in >> *(int*)&x; }
  87. virtual void clear_el(ent& x) const { x=0; }
  88. virtual void copy_el(ent& x)  const { x=x; }
  89. virtual void init_el(ent& x)  const { x=0; }
  90.  
  91. // void quick_sort(list_item* A,int l, int r);
  92.  
  93. void quick_sort(list_item* A,int l, int r, CMP_ENT cmp_fct);
  94.  
  95.  
  96. public:
  97.  
  98. // access operations
  99.  
  100.    int  length() const { return count; }
  101.    int  size()   const { return count; }
  102.    bool empty()  const { return (count==0) ? true : false;}
  103.  
  104.    dlink* first()               const { return h; }
  105.    dlink* first_item()          const { return h; }
  106.    dlink* last()                const { return t; }
  107.    dlink* last_item()           const { return t; }
  108.    dlink* next_item(dlink* p)   const { return p->succ; }
  109.    dlink* succ(dlink* l)        const { return l->succ; }
  110.    dlink* pred(dlink* l)        const { return l->pred; }
  111.    dlink* cyclic_succ(dlink*)   const;
  112.    dlink* cyclic_pred(dlink*)   const;
  113.    dlink* succ(dlink* l, int i) const; 
  114.    dlink* pred(dlink* l, int i) const;
  115.    dlink* get_item(int = 0)     const; 
  116.  
  117.    dlink* max(CMP_ENT) const;
  118.    dlink* min(CMP_ENT) const;
  119.    dlink* search(ent)  const;
  120.  
  121.    int    rank(ent) const;
  122.  
  123.    ent    contents(dlink* l) const { return l->e; }
  124.    ent    head()             const { return h ? h->e : 0;}
  125.    ent    tail()             const { return t ? t->e : 0;}
  126.  
  127.  
  128. // update operations
  129.  
  130.    dlink* insert(ent a, dlink* l, int dir=0);
  131.    dlink* push(ent a);
  132.    dlink* append(ent a);
  133.  
  134.    void   assign(dlink* l, ent a) { copy_el(a); l->e = a; }
  135.    void   conc(dlist&);
  136.    void   split(list_item,dlist&,dlist&);
  137.  
  138.    void   del(dlink* loc);
  139.    void   pop();
  140.    void   Pop();
  141.  
  142.    void   apply(ENT_TO_VOID);
  143.    void   sort(CMP_ENT);
  144.    void   bucket_sort(int i, int j, ENT_TO_INT f);
  145.    void   permute();
  146.    void   clear();
  147.  
  148. // iteration
  149.  
  150.    void   set_iterator(dlink* loc) const     
  151.    { const list_item *const p = &iterator;    // hack to stay const
  152.      (*(dlink**)p) = loc;
  153.     }
  154.  
  155.    void  init_iterator()        const { set_iterator(nil); }
  156.    void  reset()                const { set_iterator(nil); }
  157.    dlink* get_iterator()        const { return iterator; }
  158.  
  159.    dlink* move_iterator(int=0)  const;
  160.    bool   current_element(ent&) const;
  161.    bool   next_element(ent&)    const;
  162.    bool   prev_element(ent&)    const;
  163.  
  164.  
  165. // operators
  166.  
  167.    ent&   entry(dlink* l)            { return l->e; }
  168.    ent    inf(dlink* l)        const { return l->e; }
  169.    ent&   operator[](dlink* l)       { return l->e; }
  170.    ent    operator[](dlink* l) const { return l->e; }
  171.  
  172.    dlist& operator=(const dlist&); 
  173.    dlist  operator+(const dlist&); 
  174.  
  175.  
  176.    void print(ostream&,string, char)       const;    
  177.    void print(ostream& out,char space=' ') const { print(out,"",space);  }
  178.    void print(string s, char space=' ')    const { print(cout,s,space);  }
  179.    void print(char space=' ')              const { print(cout,"",space); }   
  180.  
  181.  
  182.    void read(istream&,string, char);  
  183.    void read(istream& in,char delim=EOF) { read(in,"",delim); }
  184.    void read(string s, char delim='\n')  { read(cin,s,delim); }   
  185.    void read(char delim='\n')            { read(cin,"",delim);}  
  186.  
  187.  
  188. // constructors & destructors
  189.  
  190.    dlist();    
  191.    dlist(ent a);
  192.    dlist(const dlist&);
  193.  
  194.   ~dlist()  { clear(); }
  195.  
  196.    int space()  const { return sizeof(dlist) + count * sizeof(dlink); }
  197. };
  198.  
  199.  
  200. //------------------------------------------------------------------------------
  201. // list: generic dlists
  202. //-----------------------------------------------------------------------------
  203.  
  204. #define list(type) name2(type,list)
  205.  
  206. #define listdeclare(type)\
  207. \
  208. typedef int  (*COMPARE(type,list)) (type&, type&);\
  209. typedef void (*APPLY(type,list))   (type&);\
  210. typedef int  (*ORD(type,list))     (type&);\
  211. \
  212. struct list(type) : public dlist {\
  213. \
  214. void print_el(ent& x,ostream& out) const { Print(*(type*)&x,out);  }\
  215. void read_el(ent& x,istream& in)   const { type y=0; Read(y,in); x = Copy(y); }\
  216. void clear_el(ent& x) const { Clear(*(type*)&x); }\
  217. void copy_el(ent& x)  const { Copy(*(type*)&x);  }\
  218. void init_el(ent& x)  const { type y=0; x = Copy(y);  }\
  219. \
  220. void   conc(list(type)& l)    { dlist::conc((dlist&)l); }\
  221. void   split(list_item p, list(type)& l1, list(type)& l2)\
  222.                               { dlist::split(p,(dlist&)l1,(dlist&)l2);}\
  223. list_item search(type a) const{ return dlist::search(Ent(a)); }\
  224. int       rank(type a)   const{ return dlist::rank(Ent(a)); }\
  225. \
  226. list_item push(type a)        { return dlist::push(Copy(a)); }\
  227. list_item append(type a)      { return dlist::append(Copy(a)); }\
  228. list_item insert(type a, list_item l, int dir=0)\
  229.                               { return dlist::insert(Copy(a),l,dir); }\
  230. \
  231. type  contents(list_item l) const { ent x = dlist::contents(l); return *(type*)&x; }\
  232. type  inf(list_item l)   const{ return contents(l); }\
  233. \
  234. type  head()             const{ ent x = dlist::head(); return *(type*)&x;    }\
  235. type  tail()             const{ ent x = dlist::tail(); return *(type*)&x;    }\
  236. \
  237. type  pop()                   { type x=head(); dlist::pop(); return x;       }\
  238. type  Pop()                   { type x=tail(); dlist::Pop(); return x;       }\
  239. \
  240. type  del(list_item a)        { type x=contents(a); dlist::del(a); return x; }\
  241. type  del_item(list_item a)   { type x=contents(a); dlist::del(a); return x; }\
  242. \
  243. void   assign(list_item p,type a) { dlist::assign(p,Ent(a)); }\
  244. \
  245. list_item max(COMPARE(type,list) f=0) const { return dlist::max(CMP_ENT(f)); }\
  246. list_item min(COMPARE(type,list) f=0) const { return dlist::max(CMP_ENT(f)); }\
  247. void      sort(COMPARE(type,list) f=0) { dlist::sort(CMP_ENT(f)); }\
  248. void      apply(APPLY(type,list) f)    { dlist::apply(ENT_TO_VOID(f)); }\
  249. void      bucket_sort(int i, int j, ORD(type,list) f)\
  250.                                   { dlist::bucket_sort(i,j,ENT_TO_INT(f)); }\
  251. \
  252. bool current_element(type& x) const { ent y; bool b = dlist::current_element(y);\
  253.                                       if (b) x = *(type*)&y; return b; }\
  254. bool next_element(type& x)    const { ent y; bool b = dlist::next_element(y);\
  255.                                       if (b) x = *(type*)&y; return b; }\
  256. bool prev_element(type& x)    const { ent y; bool b = dlist::prev_element(y);\
  257.                                       if (b) x = *(type*)&y; return b; }\
  258. \
  259. list(type)() {}\
  260. list(type)(const list(type)& a) : dlist((dlist&)a) {}\
  261. list(type)(type a)              : dlist(Ent(a))    {}\
  262. \
  263. ~list(type)() { clear(); }\
  264. \
  265. list(type)& operator=(const list(type)& a)\
  266.                             { return *(list(type)*)&dlist::operator=(a);}\
  267. \
  268. list(type) operator+(const list(type)& a)\
  269.                             { dlist L = *(dlist*)this + *(dlist*)&a;\
  270.                            /* dlist L = dlist::operator+(a); */     \
  271.                               return *(list(type)*)&L; }\
  272. list_item operator+=(type x)\
  273.                             { return append(x); }\
  274. \
  275. list_item operator[](int i) { return get_item(i); }\
  276. \
  277. type&  operator[](list_item p)\
  278.                             { return *(type*)&dlist::entry(p); }\
  279. type   operator[](list_item p) const\
  280.                             { return type(dlist::inf(p)); }\
  281. }; 
  282.  
  283.  
  284.  
  285. //------------------------------------------------------------------------------
  286. // Iteration Macros
  287. //------------------------------------------------------------------------------
  288.  
  289. #define forall_list_items(a,b) for( a=(b).first(); a ; a=(b).succ(a) )
  290. #define Forall_list_items(a,b) for( a=(b).last();  a ; a=(b).pred(a) )
  291.  
  292. /* forall(a,b)  defined in basic.h */
  293.  
  294. #define Forall(a,b) for( (b).init_iterator(); (b).prev_element(a); )
  295.  
  296.  
  297. #endif
  298.