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

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

数值算法/人工智能

开发平台：

MultiPlatform

olist.h：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  olist.h
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #ifndef LEDA_OLIST_H
  14. #define LEDA_OLIST_H
  16. #include <LEDA/basic.h>
  18. //------------------------------------------------------------------------------
  19. //
  20. //  obj_list  (doubly linked lists of obj_links)
  21. //
  22. //  each "obj_link" may be present in at most one list 
  23. //  
  24. //------------------------------------------------------------------------------
  26. class obj_list; 
  27. class obj_link;
  29. typedef int  (*CMP_ITEM)(obj_link*,obj_link*);
  30. typedef void (*APP_ITEM)(obj_link*);
  31. typedef int  (*ORD_ITEM)(obj_link*);
  33. //------------------------------------------------------------------------------
  34. // class obj_link (base class for all list items)
  35. //------------------------------------------------------------------------------
  37. class obj_link {
  39. protected:
  41.   obj_link* succ_link;
  42.   obj_link* pred_link;
  44. void del_item() 
  45. { pred_link->succ_link = succ_link; 
  46.   succ_link->pred_link = pred_link; 
  47.  }
  49. public:
  51. //  obj_link() { succ = nil; }
  53.   obj_link* succ_item() { return succ_link; }
  54.   obj_link* pred_item() { return pred_link; }
  56.   friend class obj_list;
  57.   friend class c_obj_list;
  58.   friend class sc_obj_list;
  59.   friend class graph;
  60.   friend class node_list;
  61.   friend class node_slist;
  63. };
  66. //------------------------------------------------------------------------------
  67. // obj_list: base class for all doubly linked lists
  68. //------------------------------------------------------------------------------
  70. class obj_list {
  72.    obj_link* h;           // head
  73.    obj_link* t;           // tail
  74.    int count;             // length of list
  76. void quick_sort(obj_link**,obj_link**,CMP_ITEM);
  78. void insertion_sort(obj_link**,obj_link**,obj_link**,CMP_ITEM);
  80. public:
  83. // access operations
  85.    int  length() const { return count; }
  86.    int  size()   const { return count; }
  87.    bool empty()  const { return (count==0) ? true : false;}
  89.    obj_link* first()               const { return h; }
  90.    obj_link* first_item()          const { return h; }
  91.    obj_link* last()                const { return t; }
  92.    obj_link* last_item()           const { return t; }
  93.    obj_link* next_item(obj_link* p)   const { return p->succ_link; }
  94.    obj_link* succ(obj_link* p)        const { return p->succ_link; }
  95.    obj_link* pred(obj_link* p)        const { return p->pred_link; }
  97.    obj_link* cyclic_succ(obj_link* p) const 
  98.    { return p->succ_link? p->succ_link : h; }
  100.    obj_link* cyclic_pred(obj_link* p) const 
  101.    { return p->pred_link? p->pred_link : t; }
  103.    obj_link* succ(obj_link* l, int i) const; 
  104.    obj_link* pred(obj_link* l, int i) const;
  105.    obj_link* get_item(int = 0)     const; 
  107.    obj_link* max(CMP_ITEM) const;
  108.    obj_link* min(CMP_ITEM) const;
  109.    obj_link* search(obj_link*) const;
  111.    int    rank(obj_link*) const;
  113. // update operations
  115.    obj_link* insert(obj_link* p, obj_link* l);
  116.    obj_link* insert(obj_link* p, obj_link* l, int dir);
  117.    obj_link* push(obj_link* p);
  118.    obj_link* append(obj_link* p);
  120.    void del(obj_link* loc);
  121.    obj_link* pop();
  122.    obj_link* Pop();
  124.    void   conc(obj_list&);
  125.    void   split(obj_link*,obj_list&,obj_list&);
  126.    void   apply(APP_ITEM);
  127.    void   sort(CMP_ITEM);
  128.    void   bucket_sort(int,int,ORD_ITEM);
  129.    void   permute();
  130.    void   clear();
  132.    obj_list& operator=(const obj_list&); 
  133.    obj_list  operator+(const obj_list&); 
  135. // constructors & destructors
  137.    obj_list();    
  139.  //obj_list(const obj_list&);
  141.   ~obj_list()  { clear(); }
  143. };
  147. inline obj_link* obj_list::push(obj_link* p)   
  148. { count++;
  149.   p->pred_link = 0;
  150.   p->succ_link = h;
  151.   if (h) 
  152.       h = h->pred_link = p;
  153.   else   
  154.       h = t =  p;
  155.   return p;
  156.  }
  159. inline obj_link* obj_list::append(obj_link* p)
  160. { count++;
  161.   p->pred_link = t;
  162.   p->succ_link = 0;
  163.   if (t) 
  164.       t = t->succ_link = p;
  165.   else  
  166.       t = h = p;
  167.   return p; 
  168.  } 
  171. inline obj_link* obj_list::pop()    
  172. { obj_link* p=h; 
  173.   if (p) 
  174.   { if (--count) 
  175.       { h = h->succ_link; 
  176.         h->pred_link = 0; 
  177.        }
  178.     else  
  179.       h = t = 0;
  180.    }
  181.   return p;
  182.  }
  185. inline obj_link* obj_list::Pop()    
  186. { obj_link* p=t; 
  187.   if (p)
  188.   { if (--count) 
  189.       { t = t->pred_link; 
  190.         t->succ_link = 0; 
  191.        }
  192.     else  
  193.       h = t = 0;
  194.    }
  195.   return p;
  196.  }
  199. inline obj_link* obj_list::insert(obj_link* n, obj_link* p) 
  200. { // insert n insert after p
  201.   obj_link* s=p->succ_link;
  202.   n->pred_link = p;
  203.   n->succ_link = s;
  204.   p->succ_link = n;
  205.   if (p==t) t=n; else s->pred_link = n;
  206.   count++;
  207.   return n;
  208. }
  213. //------------------------------------------------------------------------------
  214. //
  215. // c_obj_list (doubly linked circular object list)
  216. //
  217. // simple and efficient implementation (no counter, iterator, sorting, etc.)
  218. // removed items are assigned a nil succ pointer 
  219. // member(x) <==>  x->succ != nil
  220. //
  221. //------------------------------------------------------------------------------
  223. class c_obj_list : public obj_link {
  225. // the list head is an obj_link, namely the predecessor of the first 
  226. // and the successor of the last element
  228. public:
  230. bool empty()  const { return (succ_link==(obj_link*)this) ? true : false;}
  232. obj_link* first()      const { return (succ_link==(obj_link*)this) ? nil : succ_link; }
  233. obj_link* last()       const { return (pred_link==(obj_link*)this) ? nil : pred_link; }
  234. obj_link* first_item() const { return first(); }
  235. obj_link* last_item()  const { return last(); }
  237. obj_link* next_item(obj_link* p) const { return succ(p); }
  239. obj_link* succ(obj_link* p) const 
  240. { return (p->succ_link==(obj_link*)this)? nil : p->succ_link;}
  242. obj_link* pred(obj_link* p) const 
  243. { return (p->pred_link==(obj_link*)this)? nil : p->pred_link;}
  245. obj_link* cyclic_succ(obj_link* p) const 
  246. { return (p->succ_link==(obj_link*)this) ? pred_link : p->succ_link; }
  248. obj_link* cyclic_pred(obj_link* p) const 
  249. { return (p->pred_link==(obj_link*)this) ? succ_link : p->pred_link; }
  252.  void insert(obj_link* n, obj_link* p) 
  253.  { // insert n insert after p
  254.    obj_link* s=p->succ_link;
  255.    n->pred_link = p;
  256.    n->succ_link = s;
  257.    p->succ_link = n;
  258.    s->pred_link = n;
  259.   }
  261.  obj_link* del(obj_link* x)
  262.  { obj_link*  p = x->pred_link;
  263.    obj_link*  s = x->succ_link;
  264.    p->succ_link = s;
  265.    s->pred_link = p;
  266.    x->succ_link = nil;
  267.    return x;
  268.   }
  270.  bool member(obj_link* x) { return x->succ_link != nil; }
  272.  void push(obj_link* p)   { insert(p,this); }
  273.  void append(obj_link* p) { insert(p,pred_link); }
  275.  obj_link* pop() { return del(succ_link); }
  276.  obj_link* Pop() { return del(pred_link); }
  278.  void clear() 
  279.  { while(succ_link != this) 
  280.    { obj_link* p = succ_link;
  281.      succ_link = p->succ_link;
  282.      p->succ_link = nil;
  283.     }
  284.    pred_link = this; 
  285.   }
  287.  void init() { succ_link = pred_link = this; }
  289. // constructors & destructors
  291.  c_obj_list()  { succ_link = pred_link = this; }
  292. ~c_obj_list()  { clear(); }
  294. };
  297. #endif