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

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

数值算法/人工智能

开发平台：

MultiPlatform

_olist.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _olist.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #include <LEDA/impl/olist.h>
  14. #include <ctype.h>
  16. #define SWAP(a,b) { register obj_link* x = *a; *a = *b; *b = x; }
  18. #define MIN_D 16 
  20. //------------------------------------------------------------------------------
  21. // Members of class obj_list
  22. //------------------------------------------------------------------------------
  24. obj_list::obj_list()      
  25. { h = nil; 
  26.   t = nil;
  27.   count = 0;
  28. }
  30. void obj_list::clear()
  31. { h = nil;
  32.   t = nil;
  33.   count = 0;
  34.  }
  37. obj_link* obj_list::get_item(int i) const
  38. { obj_link* p = h;
  39.   while ( p && i--) p = p->succ_link; 
  40.   return p;
  41. }
  43. obj_link* obj_list::succ(obj_link* p, int i)  const
  44. { while ( p && i--) p = p->succ_link; 
  45.   return p;
  46. }
  48. obj_link* obj_list::pred(obj_link* p, int i) const
  49. { while ( p && i--) p = p->pred_link; 
  50.   return p;
  51. }
  54. int obj_list::rank(obj_link* x)   const   /* rank by linear search */
  55. { obj_link* p = h;
  56.   int r = 1;
  57.   while ( p && p != x) 
  58.   { p = p->succ_link; 
  59.     r++;
  60.    }
  61.   return (p) ? r : 0;
  62. } 
  65. obj_link* obj_list::insert(obj_link* n, obj_link* l, int dir) 
  66. { 
  67.   if (dir==0) //insert after l
  68.     return insert(n,l);
  69.   else //insert before l
  70.     { obj_link* p=l->pred_link;
  71.       n->pred_link = p;
  72.       n->succ_link = l;
  73.       l->pred_link = n;
  74.       if (l==h) h=n;
  75.       else p->succ_link = n;
  76.       count++;
  77.       return n;
  78.     }
  79. }
  82. void obj_list::conc(obj_list& l)
  83. { if (t) { t->succ_link = l.h;
  84.           if (l.h) { l.h->pred_link = t; t = l.t; } }
  85.    else { h = l.h; t = l.t; }
  86.  count = count+l.count;
  87.  l.h = l.t = 0;
  88.  l.count = 0;
  89. }
  92. void obj_list::split(obj_link* p, obj_list& l1, obj_list& l2)
  93. { 
  94.   l1.clear();
  95.   l2.clear();
  97.   if (p==nil)    // l1 = empty,  l2 = l, l = empty;
  98.   { l2.h = h;
  99.     l2.t = t;
  100.     l2.count = count;
  101.     h = t = 0;
  102.     count = 0;
  103.     return;
  104.    }
  106.   if (h == 0) return;   /* empty list */
  109.   if (p->pred_link)
  110.   { l1.h = h;
  111.     l1.t = p->pred_link;
  112.     p->pred_link->succ_link = 0;
  113.    }
  115.   p->pred_link = 0;
  116.   l2.h = p;
  117.   l2.t = t;
  120.   // have to set counters
  121.   // "count the smaller half" gives amortized n log n  bound
  123.   obj_link* l = l1.h;
  124.   obj_link* r = l2.h;
  125.   int    c = 0;
  127.   while (l && r)
  128.   { l = l->succ_link;
  129.     r = r->succ_link;
  130.     c++;
  131.    }
  133.   if (l==0)   // left end reached first
  134.   { l1.count = c;
  135.     l2.count = count - l1.count;
  136.    }
  138.   else
  139.   { l2.count = c;
  140.     l1.count = count - l2.count;
  141.    }
  143.   /* make original list empty */
  144.   
  145.   h = t = 0;
  146.   count = 0;
  148. }
  151. void obj_list::del(obj_link* x)
  152. { 
  153.   if (x==h)  
  154.     pop();
  155.   else
  156.     if (x==t)  
  157.        Pop();
  158.     else
  159.        { obj_link*  p = x->pred_link;
  160.          obj_link*  s = x->succ_link;
  161.          p->succ_link = s;
  162.          s->pred_link = p;
  163.          count--;
  164.         }
  165. }
  168. obj_link* obj_list::max(CMP_ITEM f) const
  169. { if (h==0) return 0;
  170.   obj_link* m=h;
  171.   obj_link* p=m->succ_link;
  173.      while (p)
  174.      { if (f(p,m) > 0) m=p;
  175.        p=p->succ_link;
  176.       }
  178.   return m;
  179. }
  181. obj_link* obj_list::min(CMP_ITEM f) const
  182. { if (h==0) return 0;
  183.   obj_link* m=h;
  184.   obj_link* p=m->succ_link;
  186.      while (p)
  187.      { if (f(p,m) < 0) m=p;
  188.        p=p->succ_link;
  189.      }
  191.   return m;
  192. }
  195. void obj_list::apply(APP_ITEM apply)
  196. { register obj_link* p = h;
  197.   while (p)
  198.   { apply(p);
  199.     p = p->succ_link;
  200.    }
  201. }
  203. void obj_list::permute()
  204. { 
  205.   obj_link** A = new obj_link*[count+2];
  206.   obj_link* x = h;
  207.   int j;
  209.   A[0] = A[count+1] = 0;
  210.  
  211.   for(j=1; j <= count; j++)
  212.   { A[j] = x;
  213.     x = x->succ_link;
  214.    }
  216.   for(j=1; j<count; j++)  
  217.   { int r = rand_int(j,count);
  218.     x = A[j];
  219.     A[j] = A[r];
  220.     A[r] = x;
  221.    }
  223.   for(j=1; j<=count; j++) 
  224.   { A[j]->succ_link = A[j+1];
  225.     A[j]->pred_link = A[j-1];
  226.    }
  228.   h = A[1];
  229.   t = A[count];
  230.   
  231.   delete A;
  232. }
  233.         
  235. void obj_list::bucket_sort(int i, int j, ORD_ITEM ord)
  236. { 
  237.   int n = j-i+1;
  239.   register obj_link** bucket= new obj_link*[n+1];
  240.   register obj_link** stop = bucket + n;
  241.   register obj_link** p;
  243.   register obj_link* q;
  244.   register obj_link* x;
  246.   for(p=bucket;p<=stop;p++)  *p = 0;
  248.   while (h) 
  249.   { x = h; 
  250.     h = h->succ_link;
  251.     int k = ord(x);
  252.     if (k >= i && k <= j) 
  253.      { p = bucket+k-i;
  254.        x->succ_link = *p;
  255.        if (*p) (*p)->pred_link = x;
  256.        *p = x;
  257.       }
  258.     else 
  259.        error_handler(4,"bucket_sort: value out of range") ;
  260.    }
  262.  for(p=bucket; *p==0 && p<stop; p++);
  263.   
  264.  h = *p;
  266.  if (h) 
  267.  { for(q=h;q->succ_link; q = q->succ_link);
  268.    h->pred_link = 0;
  269.    p++;
  270.   }
  272.  while(p<stop) 
  273.  { if (*p)
  274.    { q->succ_link = *p;
  275.      (*p)->pred_link = q;
  276.      while(q->succ_link) q = q->succ_link;
  277.     }
  278.    p++;
  279.   }
  281.  t = q;
  283.  delete bucket;
  284. }
  286.         
  287. void obj_list::quick_sort(obj_link** l, obj_link** r, CMP_ITEM usr_cmp)
  288. { // use parameter usr_cmp
  290.   register obj_link** i = l+(r-l)/2; //rand_int()%(r-l);
  291.   register obj_link** k;
  292.  
  293.   if (usr_cmp((*i),(*r))>0) SWAP(i,r);
  295.   SWAP(l,i);
  296.  
  297.   obj_link* s = (*l);
  298.  
  299.   i = l;
  300.   k = r;
  302.   for(;;)
  303.   { while (usr_cmp((*(++i)),s)<0);
  304.     while (usr_cmp((*(--k)),s)>0);
  305.     if (i<k) SWAP(i,k) else break;
  306.    }
  308.   SWAP(l,k);
  310.   if (k > l+MIN_D) quick_sort(l,k-1,usr_cmp);
  311.   if (r > k+MIN_D) quick_sort(k+1,r,usr_cmp);
  312. }
  313.         
  316. void obj_list::insertion_sort(obj_link** l, obj_link** r, obj_link** min_stop, 
  317.                                CMP_ITEM usr_cmp)
  318. {
  319.   register obj_link** min=l;
  320.   register obj_link** run;
  321.   register obj_link** p;
  322.   register obj_link** q;
  324.   for (run = l+1; run <= min_stop; run++)
  325.       if (usr_cmp((*run),(*min)) < 0) min = run;
  327.   SWAP(min,l);
  329.   if (r == l+1) return; 
  331.   for(run=l+2; run <= r; run++)
  332.   { for (min = run-1; usr_cmp((*run),(*min)) < 0; min--);
  333.     min++;
  334.     if (run != min) 
  335.     { obj_link* save = *run;
  336.       for(p=run, q = run-1; p > min; p--,q--) *p = *q;
  337.       *min = save;
  338.      }
  339.    }
  340. }
  344. void obj_list::sort(CMP_ITEM f)
  345. { 
  346.   if (count<=1) return;    // nothing to sort
  348.   obj_link** A = new obj_link*[count+2];
  350.   register obj_link*  loc = h;
  351.   register obj_link** p;
  352.   register obj_link** stop = A+count+1;
  354.   obj_link** left  = A+1;
  355.   obj_link** right = A+count;
  356.   obj_link** min_stop = left + MIN_D;
  358.   if (min_stop > right) min_stop = right;
  360. min_stop = right;
  362.   for(p=A+1; p<stop; p++)
  363.   { *p = loc;
  364.     loc = loc->succ_link;
  365.    }
  368.    quick_sort(left,right,f);
  369.    insertion_sort(left,right,min_stop,f);
  371.   *A = *stop = 0;
  373.   for (p=A+1;p<stop;p++) 
  374.   { (*p)->succ_link = *(p+1);
  375.     (*p)->pred_link = *(p-1);
  376.    }
  378.   h = A[1];
  379.   t = A[count];
  381.   delete A;
  382. }