home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / slist.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  4.8 KB  |  180 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  slist.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.  
  18. #ifndef SLISTH
  19. #define SLISTH
  20.  
  21. /*------------------------------------------------------------------------------ 
  22.     SLIST   (simply linked lists)
  23.  
  24.     Stefan Naeher
  25.     FB10 Informatik 
  26.     Universitaet des Saarlandes 
  27.     6600 Saarbruecken
  28.  
  29.     September 1988
  30.     
  31. ------------------------------------------------------------------------------*/
  32.  
  33.  
  34. #include <LEDA/basic.h>
  35.  
  36.  
  37. class SLIST; 
  38. class slink;
  39.  
  40. typedef slink* slist_item;
  41.  
  42. //------------------------------------------------------------------------------
  43. // class slink 
  44. //------------------------------------------------------------------------------
  45.  
  46. class slink {
  47.  
  48.   friend class SLIST;
  49.  
  50.   slink* succ;
  51.   ent e;
  52.  
  53.   slink(ent a, slink* suc)
  54.   { 
  55.     e = a;
  56.     succ = suc;
  57.   }
  58.  
  59.   OPERATOR_NEW(2)
  60.   OPERATOR_DEL(2)
  61.  
  62. };
  63.  
  64.  
  65. //------------------------------------------------------------------------------
  66. // SLIST: base class for all simply linked Lists
  67. //------------------------------------------------------------------------------
  68.  
  69. class SLIST {
  70.  
  71.    slink* h;                     //head
  72.    slink* t;                     //tail
  73.    slink* iterator;              //iterator;
  74.    int    count;                 //length of List
  75.  
  76. virtual void copy_el(ent& x)  const { x=x; }
  77. virtual void clear_el(ent& x) const { x=x; }
  78.  
  79. public:
  80.  
  81.    int space()  const { return sizeof(SLIST) + count * sizeof(slink); }
  82.    int length() const { return count; }
  83.    int empty()  const { return (count==0);}
  84.  
  85.    slink* push(ent a);
  86.    slink* push(SLIST& l);
  87.    slink* append(ent a);
  88.    slink* append(SLIST& l);
  89.    slink* insert(ent a, slink* l);
  90.    slink* first() const { return h; }
  91.    slink* last()  const { return t; }
  92.  
  93.    slink* get_iterator()  const { return iterator; }
  94.  
  95.    void   set_iterator(slink* loc) const 
  96.    { const slist_item *const p = &iterator;  
  97.      (*(slink**)p) = loc;
  98.     }
  99.  
  100.    void init_iterator()  const { set_iterator(0); }
  101.  
  102.    slink* move_iterator() const  
  103.    { set_iterator( iterator ? iterator->succ : h);
  104.      return iterator;
  105.    } 
  106.  
  107.    slink* cyclic_succ(slink*) const;
  108.    slink* succ(slink* l)      const { return l->succ; }
  109.  
  110.    void pop();
  111.  
  112.    ent  head()   const { return h ? h->e : 0;}
  113.    ent  tail()   const { return t ? t->e : 0;}
  114.  
  115.    bool current_element(ent& x)  const
  116.    { if (!iterator) return false;
  117.      else { x = iterator->e;
  118.             return true; }
  119.     }
  120.  
  121.    bool next_element(ent& x) const 
  122.   { move_iterator(); 
  123.     return current_element(x); 
  124.    }
  125.  
  126.    ent  contents(slink* l)  const { return l->e; }
  127.    ent& operator[](slink* l)      { return l->e; }
  128.  
  129.    void clear();
  130.  
  131.    SLIST();    
  132.    SLIST(ent a);
  133.    SLIST& operator=(const SLIST&); 
  134.    SLIST  operator+(SLIST); 
  135.    SLIST(const SLIST&);
  136.    ~SLIST()     { clear(); }
  137. };
  138.  
  139.  
  140. //------------------------------------------------------------------------------
  141. // slist: generic SLISTs
  142. //-----------------------------------------------------------------------------
  143.  
  144. #define slist(type) name2(type,slist)
  145.  
  146. #define slistdeclare(type)\
  147. \
  148. struct slist(type) : SLIST {\
  149. slink* push(type a)            { return SLIST::push( Ent(a) ); }\
  150. slink* push(slist(type)& l)    { return SLIST::push((SLIST&)l); }\
  151. slink* append(type a)          { return SLIST::append( Ent(a) ); }\
  152. slink* append(slist(type)& l)  { return SLIST::append((SLIST&)l); }\
  153. slink* insert(type a, slink* l){ return SLIST::insert(Ent(a),l); }\
  154. bool current_element(type& x) const { ent y; bool b = SLIST::current_element(y);\
  155.                                       if (b) x = type(y); return b; }\
  156. bool next_element(type& x)    const { ent y; bool b = SLIST::next_element(y);\
  157.                                       if (b) x = type(y); return b; }\
  158. type pop()                    { return type(SLIST::pop() ); }\
  159. type head()             const { return type(SLIST::head() ); }\
  160. type tail()             const { return type(SLIST::tail() ); }\
  161. type contents(slink* l) const { return type(SLIST::contents(l)); }\
  162. type inf(slink* l)      const { return type(SLIST::contents(l)); }\
  163. \
  164.    slist(type)() { }\
  165.    slist(type)(const slist(type)& a) : SLIST((SLIST&)a) { }\
  166.    slist(type)(type a) : SLIST(Ent(a)) { }\
  167.    ~slist(type)() {}\
  168. \
  169.    slist(type)& operator=(const slist(type)& a)\
  170.            { return (slist(type)&)SLIST::operator=((SLIST&)a); }\
  171.    slist(type) operator+(slist(type) a)\
  172.            { return (slist(type)&)(SLIST(*this) + SLIST(a)); }\
  173.    slink* operator+=(type x)  { return append(x); }\
  174.    slink* operator&=(type x)  { return push(x); }\
  175.    type& operator[](slink* l) { return *(type*)&SLIST::operator[](l); }\
  176. };
  177.  
  178.  
  179. #endif
  180.