开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
dlist.h
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：6k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

dlist.h：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  dlist.h
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  14. #ifndef LEDA_DLIST_H
  15. #define LEDA_DLIST_H
  17. //------------------------------------------------------------------------------
  18. //  doubly linked lists
  19. //------------------------------------------------------------------------------
  21. #include <LEDA/basic.h>
  23. //------------------------------------------------------------------------------
  24. // some declarations
  25. //------------------------------------------------------------------------------
  27. class dlist; 
  28. class dlink;
  30. typedef dlink* list_item;
  32. //------------------------------------------------------------------------------
  33. // class dlink (list items)
  34. //------------------------------------------------------------------------------
  36. class dlink {
  38.   dlink* succ;
  39.   dlink* pred;
  40.   GenPtr e;
  42.   dlink(GenPtr a, dlink* pre, dlink* suc)
  43.   { 
  44.     e = a;
  45.     succ = suc;
  46.     pred = pre;
  47.   }
  49.   LEDA_MEMORY(dlink)
  52.   friend class dlist;
  53.   friend dlink* succ_item(dlink* p) { return p->succ; }
  54.   friend dlink* pred_item(dlink* p) { return p->pred; }
  56.   //space: 3 words = 12 bytes
  57. };
  62. //------------------------------------------------------------------------------
  63. // dlist: base class for all doubly linked lists
  64. //------------------------------------------------------------------------------
  66. class dlist {
  68.    dlink* h;                     //head
  69.    dlink* t;                     //tail
  70.    dlink* iterator;              //iterator
  71.    int count;                    //length of list
  73. //space: 4 words + virtual =  5 words = 20 bytes
  75. virtual int  cmp(GenPtr, GenPtr) const { return 0; }
  76. virtual int  ord(GenPtr) const { return 0; }
  77. virtual void app(GenPtr&) const {}
  78. virtual void read_el(GenPtr&,istream&) const {}
  79. virtual void print_el(GenPtr&,ostream&) const {}
  80. virtual void clear_el(GenPtr&) const {}
  81. virtual void copy_el(GenPtr&)  const {}
  82. virtual int  int_type() const { return 0; }
  84. void quick_sort(list_item*,list_item*);
  85. void int_quick_sort(list_item*,list_item*);
  87. void insertion_sort(dlink**,dlink**,dlink**);
  88. void int_insertion_sort(dlink**,dlink**,dlink**);
  90. void recompute_length() const;
  92. public:
  94. // access operations
  96.    int  length() const { if (count < 0) recompute_length(); return count; }
  97.    int  size()   const { return length(); }
  98.    bool empty()  const { return h==nil; }
  100.    dlink* first()               const { return h; }
  101.    dlink* first_item()          const { return h; }
  102.    dlink* last()                const { return t; }
  103.    dlink* last_item()           const { return t; }
  104.    dlink* next_item(dlink* p)   const { return p->succ; }
  105.    dlink* succ(dlink* l)        const { return l->succ; }
  106.    dlink* pred(dlink* l)        const { return l->pred; }
  107.    dlink* cyclic_succ(dlink*)   const;
  108.    dlink* cyclic_pred(dlink*)   const;
  109.    dlink* succ(dlink* l, int i) const; 
  110.    dlink* pred(dlink* l, int i) const;
  111.    dlink* get_item(int = 0)     const; 
  113.    dlink* max() const;
  114.    dlink* min() const;
  115.    dlink* search(GenPtr) const;
  117.    int    rank(GenPtr) const;
  119.    GenPtr contents(dlink* l) const { return l->e; }
  120.    GenPtr head()             const { return h ? h->e : 0;}
  121.    GenPtr tail()             const { return t ? t->e : 0;}
  124. // update operations
  126. protected:
  128.    dlink* insert(GenPtr a, dlink* l, int dir=0);
  130.    dlink* push(GenPtr a)   
  131.    { if (count >= 0) count++;
  132.      if (h) h = h->pred = new dlink(a,0,h); 
  133.      else   h = t =  new dlink(a,0,0);
  134.      return h;
  135.     }
  136.    
  137.    dlink* append(GenPtr a)
  138.    { if (count >= 0) count++;
  139.      if (t) t = t->succ = new dlink(a,t,0);
  140.      else   t = h = new dlink(a,0,0);
  141.      return t; 
  142.     } 
  143.    
  144.    void   assign(dlink* l, GenPtr a) { clear_el(l->e); l->e = a; }
  146.    void   apply();
  147.    void   sort();
  149. public:
  151.    GenPtr del(dlink* loc);
  152.    GenPtr pop();
  153.    GenPtr Pop();
  155.    void   conc(dlist&,int dir=0);
  156.    void   split(list_item,dlist&,dlist&,int dir=0);
  157.    void   bucket_sort(int,int);
  158.    void   permute();
  159.    void   clear();
  161. // iteration
  163.    GenPtr loop_to_succ(GenPtr& x) const { return x = list_item(x)->succ; }
  164.    GenPtr loop_to_pred(GenPtr& x) const { return x = list_item(x)->pred; }
  166. #if defined(__ELSE_SCOPE_BUG__)
  167.    GenPtr forall_loop_item;
  168.    GenPtr& Forall_Loop_Item() const { return (GenPtr&)forall_loop_item; }
  169. #endif
  173. //  old iteration stuff
  175.    void set_iterator(dlink* p) const { *(dlink**)&iterator = p; }
  176.    void init_iterator()        const { set_iterator(nil); }
  177.    void reset()                const { set_iterator(nil); }
  178.  
  179.    dlink* get_iterator()       const { return iterator; }
  180.    dlink* move_iterator(int=0) const;
  182.    bool   current_element(GenPtr&) const;
  183.    bool   next_element(GenPtr&)    const;
  184.    bool   prev_element(GenPtr&)    const;
  187. // operators
  189.    GenPtr&   entry(dlink* l)            { return l->e; }
  190.    GenPtr    inf(dlink* l)        const { return l->e; }
  191.    GenPtr&   operator[](dlink* l)       { return l->e; }
  192.    GenPtr    operator[](dlink* l) const { return l->e; }
  194.    dlist& operator=(const dlist&); 
  195.    dlist  operator+(const dlist&); 
  198.    void print(ostream&,string, char)       const;    
  199.    void print(ostream& out,char space=' ') const { print(out,"",space);  }
  200.    void print(string s, char space=' ')    const { print(cout,s,space);  }
  201.    void print(char space=' ')              const { print(cout,"",space); }   
  204.    void read(istream&,string, int);  
  206.    void read(istream& in,int delim) { read(in,"",delim); }
  207.    void read(istream& in)           { read(in,"",EOF); }
  209.    void read(string s, int delim)   { read(cin,s,delim); }   
  210.    void read(string s)              { read(cin,s,'n'); }   
  212.    void read(char delim)  { read(cin,"",delim);}  
  213.    void read()            { read(cin,"",'n');}  
  216. // constructors & destructors
  218.    dlist();    
  219.    dlist(GenPtr a);
  220.    dlist(const dlist&);
  222.    virtual ~dlist()  { clear(); }
  224.    int space()  const { return sizeof(dlist) + length() * sizeof(dlink); }
  225. };
  229. #if !defined(__TEMPLATE_FUNCTIONS__)
  230. // default I/O and cmp functions
  232. inline void Print(const dlist& L,ostream& out) { L.print(out); out << endl; }
  233. inline void Read(dlist& L, istream& in)        { L.read(in,'n'); }
  234. inline int  compare(const dlist&,const dlist&) { return 0; }
  235. #endif
  237. #endif