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

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

数值算法/人工智能

开发平台：

MultiPlatform

_dlist.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _dlist.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  14. #include <LEDA/impl/dlist.h>
  15. #include <ctype.h>
  18. #define SWAP(a,b) { register dlink* x = *a; *a = *b; *b = x; }
  20. #define MIN_D 16 
  22. //------------------------------------------------------------------------------
  23. // Members of class dlist: base class for all lists
  24. //------------------------------------------------------------------------------
  26. dlist::dlist()      
  27. { h=0; 
  28.   t=0;
  29.   count=0;
  30.   iterator=0; 
  31. }
  33. dlist::dlist(GenPtr a) 
  34. { h=t=new dlink(a,0,0);
  35.   count=1; 
  36.   iterator=0;  
  37. }
  39. dlist::dlist(const dlist& x)
  40. { register dlink* p;
  42.   iterator=h=t=0; 
  43.   count = 0; 
  44.                               
  45.   for (p = x.h; p; p = p->succ) append(p->e); 
  47.   if (!int_type())
  48.     for (p = h; p; p = p->succ) x.copy_el(p->e);
  49. }
  52. void dlist::recompute_length() const
  53. { int n = 0;
  54.   for(dlink* it = h; it; it = it->succ)  n++;
  55.   *(int*)&count = n;
  56. }
  59. //------------------------------------------------------------------------------
  60. // Iteration:
  61. //------------------------------------------------------------------------------
  63. dlink* dlist::move_iterator(int dir) const 
  64. { if (iterator) 
  65.      set_iterator(dir ? iterator->pred : iterator->succ);
  66.   else 
  67.      set_iterator(dir ? t : h);
  68.   return iterator;
  69.  } 
  71. bool dlist::current_element(GenPtr& x) const 
  72. { if (iterator) 
  73.   { x = iterator->e; 
  74.     return true; 
  75.    } 
  76.   return false; 
  77.  }
  79. bool dlist::next_element(GenPtr& x)    const 
  80. { if (iterator) 
  81.      set_iterator(iterator->succ);
  82.   else 
  83.      set_iterator(h);
  85.   if (iterator) 
  86.   { x = iterator->e;
  87.     return true; 
  88.    } 
  89.   return false; 
  90.  }
  92. bool dlist::prev_element(GenPtr& x)  const
  93. { if (iterator) 
  94.      set_iterator(iterator->pred);
  95.   else 
  96.      set_iterator(t);
  98.   if (iterator) 
  99.   { x = iterator->e;
  100.     return true; 
  101.    } 
  102.   return false; 
  103.  }
  105. //------------------------------------------------------------------------------
  107. dlink* dlist::get_item(int i) const
  108. { dlink* p = h;
  109.   while ( p && i--) p = p->succ; 
  110.   return p;
  111. }
  113. dlink* dlist::succ(dlink* p, int i)  const
  114. { while ( p && i--) p = p->succ; 
  115.   return p;
  116. }
  118. dlink* dlist::pred(dlink* p, int i) const
  119. { while ( p && i--) p = p->pred; 
  120.   return p;
  121. }
  123. dlink* dlist::search(GenPtr x) const  /* linear search */
  124. { dlink* p = h;
  125.   while ( p && cmp(p->e,x) != 0) p = p->succ; 
  126.   return p;
  127. } 
  129. int dlist::rank(GenPtr x)   const   /* rank by linear search */
  130. { dlink* p = h;
  131.   int r = 1;
  132.   while ( p && cmp(p->e,x) != 0)
  133.   { p = p->succ; 
  134.     r++;
  135.    }
  136.   return (p) ? r : 0;
  137. } 
  139. GenPtr dlist::pop()    
  140. { if (h==nil) return nil;
  141.   if (iterator!=0) error_handler(1,"pop: deletion while iterator is active");
  142.   dlink* x=h; 
  143.   h = h->succ;
  144.   if (h) h->pred = 0;
  145.   else t = nil;
  146.   GenPtr p = x->e;
  147.   delete x;
  148.   count--;
  149.   return p;
  150. }
  153. GenPtr dlist::Pop()    
  154. { if (h==nil) return 0;
  155.   if (iterator!=0) error_handler(1,"Pop: deletion while iterator is active");
  156.   dlink* x=t; 
  157.   t = t->pred;
  158.   if (t) t->succ = 0;
  159.   else h = nil;
  160.   GenPtr p = x->e;
  161.   delete x;
  162.   count--;
  163.   return p;
  164. }
  166. dlink* dlist::insert(GenPtr a, dlink* l, int dir) 
  167. { 
  168.   if (iterator!=0) error_handler(2,"insert: insertion while iterator is active");
  170.   if (l==0) return dir ? append(a) : push(a); 
  172.   dlink* s=l->succ;
  173.   dlink* p=l->pred;
  174.   dlink* n;
  175.   
  176.   if (dir==0) //insert after l
  177.   { n= new dlink(a,l,s);
  178.     l->succ = n;
  179.     if (l==t) t=n;
  180.     else s->pred = n;}
  182.   else //insert before l
  183.   { n= new dlink(a,p,l);
  184.     l->pred = n;
  185.     if (l==h) h=n;
  186.     else p->succ = n;}
  188.   if (count >= 0) count++;
  189.  
  190.   return n;
  191. }
  194. void dlist::conc(dlist& l, int dir)
  195. { 
  196.   if (iterator!=0) error_handler(2,"conc: iterator is active");
  198.   if (h==nil)
  199.    { h = l.h; 
  200.      t = l.t; 
  201.     }
  202.   else
  203.   { if (dir==0)  // append l 
  204.     { t->succ = l.h;
  205.       if (l.h) { l.h->pred = t; t = l.t; } 
  206.      }
  207.     else // prepend l
  208.     { h->pred = l.t;
  209.       if (l.t) { l.t->succ= h; h = l.h; } 
  210.      }
  211.    }
  213.  if (count < 0 || l.count < 0)
  214.     count = -1;
  215.  else
  216.     count += l.count;
  218.  l.h = l.t = 0;
  219.  l.count = 0;
  220. }
  223. void dlist::split(dlink* p, dlist& L1, dlist& L2, int dir)
  224. { 
  225.   // split L0 at item p into L1 and L2 and  L is made empty
  226.   // if p == nil copy L0 to L2 and make L1 empty (if not identical to L0)
  227.   // if p != nil we have to distinguish two cases
  228.   // dir == 0: p becomes first item of L2
  229.   // dir != 0: p becomes last item of L1
  231.   if (iterator) error_handler(1,"dlist::split: iterator is active.");
  232.   if (h == nil) error_handler(1,"dlist::split: list is empty.");
  233.   if (&L1 == &L2) error_handler(1,"dlist::split: identical arguments.");
  235.   if (this != &L1) L1.clear();
  236.   if (this != &L2) L2.clear();
  238.   if (p == nil) 
  239.   { p = h;
  240.     dir = 0;
  241.    }
  243.  /* The first item of L1 is either h or nil depending whether L1 is non-empty
  244.   * or not. L1 is empty if dir == 0 and p->pred does not exist. A similar 
  245.   * argument applies to L2. 
  246.   */
  248.   dlink* L1_last  = (dir != 0) ? p : p->pred;
  249.   dlink* L1_first = (L1_last)  ? h : nil;
  251.   dlink* L2_first = (dir == 0) ? p : p->succ;
  252.   dlink* L2_last =  (L2_first) ? t : nil;
  254.   h = t = 0;
  255.   count = 0;
  257.   L1.h = L1_first;
  258.   L1.t = L1_last;
  259.   L1.count = -1; // size unknown
  260.   if (L1_last) L1_last->succ = 0;
  262.   L2.h = L2_first;
  263.   L2.t = L2_last;
  264.   L2.count = -1; // size unknown
  265.   if (L2_first) L2_first->pred = 0;
  266. }
  270. GenPtr dlist::del(dlink* it)
  271. { if (iterator) error_handler(1,"dlist: deletion while iterator is active");
  272.   if (it==nil)  error_handler(999,"dlist: delete nil-item");
  273.   if (it==h)  return pop();
  274.   if (it==t)  return Pop();
  275.   dlink*  p = it->pred;
  276.   dlink*  s = it->succ;
  277.   GenPtr x = it->e;
  278.   p->succ = s;
  279.   s->pred = p;
  280.   count--;
  281.   delete it;
  282.   return x;
  283. }
  285. dlink* dlist::cyclic_succ(dlink* it) const
  286. { if (it==0) return 0;
  287.   return it->succ? it->succ : h;
  288. }
  290. dlink* dlist::cyclic_pred(dlink* it) const
  291. { if (it==0) return 0;
  292.   return it->pred? it->pred : t;
  293. }
  296. dlink* dlist::max() const
  297. { if (h==0) return 0;
  298.   dlink* m=h;
  299.   dlink* p=m->succ;
  301.   while (p)
  302.   { if (cmp(p->e,m->e) > 0) m=p;
  303.     p=p->succ;
  304.    }
  306.   return m;
  307. }
  309. dlink* dlist::min() const
  310. { if (h==0) return 0;
  311.   dlink* m=h;
  312.   dlink* p=m->succ;
  314.   while (p)
  315.   { if (cmp(p->e,m->e) < 0) m=p;
  316.     p=p->succ;
  317.    }
  319.   return m;
  320. }
  323. void dlist::apply()
  324. { register dlink* p = h;
  325.   while (p)
  326.   { app(p->e);
  327.     p = p->succ;
  328.    }
  329. }
  331. void dlist::permute()
  332. { 
  333.   if (iterator!=0) 
  334.           error_handler(3,"permute: modification while iterator is active");
  336.   length();
  338.   list_item* A = new list_item[count+2];
  339.   list_item x = h;
  340.   int j;
  342.   A[0] = A[count+1] = 0;
  343.  
  344.   for(j=1; j <= count; j++)
  345.   { A[j] = x;
  346.     x = x->succ;
  347.    }
  349.   for(j=1; j<count; j++)  
  350.   { int r = rand_int(j,count);
  351.     x = A[j];
  352.     A[j] = A[r];
  353.     A[r] = x;
  354.    }
  356.   for(j=1; j<=count; j++) 
  357.   { A[j]->succ = A[j+1];
  358.     A[j]->pred = A[j-1];
  359.    }
  361.   h = A[1];
  362.   t = A[count];
  363.   
  364.   delete A;
  365. }
  366.         
  368. void dlist::bucket_sort(int i, int j)
  369. { if (iterator!=0) 
  370.         error_handler(3,"bucket_sort: modification while iterator is active");
  372.   if (h==nil) return; // empty list
  374.   int n = j-i+1;
  376.   register list_item* bucket= new list_item[n+1];
  377.   register list_item* stop = bucket + n;
  378.   register list_item* p;
  380.   register list_item q;
  381.   register list_item x;
  383.   for(p=bucket;p<=stop;p++)  *p = 0;
  385.   while (h) 
  386.   { x = h; 
  387.     h = h->succ;
  388.     int k = ord(x->e);
  389.     if (k >= i && k <= j) 
  390.      { p = bucket+k-i;
  391.        x->pred = *p;
  392.        if (*p) (*p)->succ = x;
  393.        *p = x;
  394.       }
  395.     else 
  396.        error_handler(4,string("bucket_sort: value %d out of range",k)) ;
  397.    }
  399.  for(p=stop; *p==0; p--); 
  401.  // now p points to the end of the rightmost non-empty bucket
  402.  // make it the new head  of the list (remember: list is not empty)
  404.  t = *p;
  405.  t->succ = nil;
  407.  for(q = *p; q->pred; q = q->pred); // now q points to the start of this bucket
  409.  // link buckets together from right to left:
  410.  // q points to the start of the last bucket
  411.  // p points to end of the next bucket
  413.  while(--p >= bucket) 
  414.    if (*p)
  415.    { (*p)->succ = q;
  416.      q->pred = *p;
  417.      for(q = *p; q->pred; q = q->pred); 
  418.     }
  420.  h = q;   // head = start of leftmost non-empty bucket
  422.  delete bucket;
  423. }
  426. void dlist::quick_sort(dlink** l, dlink** r)
  427. { // use virtual cmp function
  429.   register dlink** i = l+(r-l)/2; //rand_int()%(r-l);
  430.   register dlink** k;
  431.  
  432.   if (cmp((*i)->e,(*r)->e)>0) SWAP(i,r);
  434.   SWAP(l,i);
  435.  
  436.   GenPtr s = (*l)->e;
  437.  
  438.   i = l;
  439.   k = r;
  441.   for(;;)
  442.   { while (cmp((*(++i))->e,s)<0);
  443.     while (cmp((*(--k))->e,s)>0);
  444.     if (i<k) SWAP(i,k) else break;
  445.    }
  447.   SWAP(l,k);
  449.   if (k > l+MIN_D) quick_sort(l,k-1);
  450.   if (r > k+MIN_D) quick_sort(k+1,r);
  451. }
  452.         
  453. void dlist::int_quick_sort(dlink** l, dlink** r)
  454. { // use built-in < and > operators for integers
  456.   register dlink** i = l+(r-l)/2; //rand_int()%(r-l);
  457.   register dlink** k;
  458.  
  459.   if ((*i)->e > (*r)->e) SWAP(i,r);
  461.   SWAP(l,i);
  462.  
  463.   int s = LEDA_ACCESS(int,(*l)->e);
  464.  
  465.   i = l;
  466.   k = r;
  468.   for(;;)
  469.   { while (LEDA_ACCESS(int,(*(++i))->e) < s);
  470.     while (LEDA_ACCESS(int,(*(--k))->e) > s);
  471.     if (i<k) SWAP(i,k) else break;
  472.    }
  474.   SWAP(l,k);
  476.   if (k > l+MIN_D) int_quick_sort(l,k-1);
  477.   if (r > k+MIN_D) int_quick_sort(k+1,r);
  478. }
  481. void dlist::insertion_sort(dlink** l, dlink** r, dlink** min_stop)
  482. {
  483.   register dlink** min=l;
  484.   register dlink** run;
  485.   register dlink** p;
  486.   register dlink** q;
  488.   for (run = l+1; run <= min_stop; run++)
  489.       if (cmp((*run)->e,(*min)->e) < 0) min = run;
  491.   SWAP(min,l);
  493.   if (r == l+1) return; 
  495.   for(run=l+2; run <= r; run++)
  496.   { for (min = run-1; cmp((*run)->e,(*min)->e) < 0; min--);
  497.     min++;
  498.     if (run != min) 
  499.     { dlink* save = *run;
  500.       for(p=run, q = run-1; p > min; p--,q--) *p = *q;
  501.       *min = save;
  502.      }
  503.    }
  504. }
  507. void dlist::int_insertion_sort(dlink** l, dlink** r, dlink** min_stop)
  508. {
  509.   register dlink** min=l;
  510.   register dlink** run;
  511.   register dlink** p;
  512.   register dlink** q;
  514.   for (run = l+1; run <= min_stop; run++)
  515.     if (LEDA_ACCESS(int,(*run)->e) < LEDA_ACCESS(int,(*min)->e)) min = run;
  517.   SWAP(min,l);
  519.   if (r == l+1) return; 
  521.   for(run=l+2; run <= r; run++)
  522.   { for (min=run-1;LEDA_ACCESS(int,(*run)->e)<LEDA_ACCESS(int,(*min)->e);min--);
  523.     min++;
  524.     if (run != min) 
  525.     { dlink* save = *run;
  526.       for(p=run, q = run-1; p > min; p--,q--) *p = *q;
  527.       *min = save;
  528.      }
  529.    }
  530. }
  535. void dlist::sort()
  536. { if (iterator!=0)
  537.       error_handler(1,"sort: modification while iterator is active");
  539.   if (length() <= 1) return;    // nothing to sort
  541.   dlink** A = new dlink*[count+2];
  543.   register dlink*  loc = h;
  544.   register dlink** p;
  545.   register dlink** stop = A+count+1;
  547.   dlink** left  = A+1;
  548.   dlink** right = A+count;
  549.   dlink** min_stop = left + MIN_D;
  551.   if (min_stop > right) min_stop = right;
  553. min_stop = right;
  555.   for(p=A+1; p<stop; p++)
  556.   { *p = loc;
  557.     loc = loc->succ;
  558.    }
  561.   if (int_type())
  562.      { int_quick_sort(left,right);
  563.        int_insertion_sort(left,right,min_stop);
  564.       }
  565.    else
  566.      { quick_sort(left,right);
  567.        insertion_sort(left,right,min_stop);
  568.       }
  570.   *A = *stop = 0;
  572.   for (p=A+1;p<stop;p++) 
  573.   { (*p)->succ = *(p+1);
  574.     (*p)->pred = *(p-1);
  575.    }
  577.   h = A[1];
  578.   t = A[count];
  580.   delete A;
  581. }
  584. dlist& dlist::operator=(const dlist& x)
  585. { register dlink* p;
  587.   clear();
  589.   for (p = x.h; p; p = p->succ) append(p->e); 
  591.   if (!int_type())
  592.     for (p = h; p; p = p->succ) copy_el(p->e);
  593.                                 
  594.   return *this;
  595. }
  598. dlist dlist::operator+(const dlist& x)  // concatenation
  599. { dlist y = x;
  600.   dlink* p = t;
  601.   while (p) { y.push(p->e);    
  602.               x.copy_el(p->e);
  603.               p = p->pred;}
  604.   return y;
  605. }
  608. void dlist::clear()
  609. { if (h==nil) return;
  611.   if (!int_type())
  612.     for(dlink* p = h; p; p = p->succ) clear_el(p->e);
  614.   deallocate_list(h,t,sizeof(dlink));
  615.   iterator=h=t=nil;
  616.   count=0;
  617. }
  619. void dlist::print(ostream& out, string s, char space) const
  620. { list_item l = h;
  621.   cout << s;
  622.   if (l)
  623.   { print_el(l->e,out); 
  624.     l = l->succ;
  625.     while (l)
  626.       { out << string(space);
  627.         print_el(l->e,out); 
  628.         l = l->succ;
  629.        }
  630.   }
  631.   out.flush();
  632. }
  635. void dlist::read(istream& in, string s, int delim)
  636. { char c;
  637.   GenPtr x;
  638.   cout << s;
  639.   clear();
  640.   if (delim == EOF)
  641.      for(;;)
  642.      { while (in.get(c) && isspace(c));
  643.        if (!in) break;
  644.        in.putback(c);
  645.        read_el(x,in); 
  646.        append(x);
  647.       }
  648.   else
  649.      for(;;)
  650.      { while (in.get(c) && isspace(c) && c!=delim);
  651.        if (!in || c==delim) break;
  652.        in.putback(c);
  653.        read_el(x,in); 
  654.        append(x);
  655.       }
  656. }