home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / basic / _list.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  10.9 KB  |  575 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _list.c
  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. #include <LEDA/list.h>
  17.  
  18. /*  Definition  der Member-Funktionen der Klasse "dlist"
  19.     (doppelt verkettete Listen)
  20.  
  21.     Stefan Naeher
  22.     FB10 Informatik 
  23.     Universitaet des Saarlandes 
  24.     6600 Saarbruecken
  25.  
  26.     September 1988
  27.     
  28. */
  29.  
  30. //------------------------------------------------------------------------------
  31. // Members of class dlist: base class for all lists
  32. //------------------------------------------------------------------------------
  33.  
  34. dlist::dlist()      
  35. { h=0; 
  36.   t=0;
  37.   count=0;
  38.   iterator=0; 
  39. }
  40.  
  41. dlist::dlist(ent a) 
  42. { h=t=new dlink(a,0,0);
  43.   count=1; 
  44.   iterator=0;  
  45. }
  46.  
  47. dlist::dlist(const dlist& x)
  48. { h=0; 
  49.   t=0; 
  50.   count=0; 
  51.   iterator=0;
  52.  
  53.   dlink* p = x.h;
  54.                               
  55.   while (p) { x.copy_el(p->e); /* copy list using virtual copy_el of x !! */
  56.               append(p->e);    // does not make a copy  !!
  57.               p = p->succ; 
  58.              }
  59. }
  60.  
  61. //------------------------------------------------------------------------------
  62. // Iteration:
  63. //------------------------------------------------------------------------------
  64.  
  65. dlink* dlist::move_iterator(int dir) const 
  66. { if (iterator) 
  67.      set_iterator(dir ? iterator->pred : iterator->succ);
  68.   else 
  69.      set_iterator(dir ? t : h);
  70.   return iterator;
  71.  } 
  72.  
  73. bool dlist::current_element(ent& x) const 
  74. { if (iterator) 
  75.   { x = iterator->e; 
  76.     return true; 
  77.    } 
  78.   return false; 
  79.  }
  80.  
  81. bool dlist::next_element(ent& x)    const 
  82. { if (iterator) 
  83.      set_iterator(iterator->succ);
  84.   else 
  85.      set_iterator(h);
  86.  
  87.   if (iterator) 
  88.   { x = iterator->e;
  89.     return true; 
  90.    } 
  91.   return false; 
  92.  }
  93.  
  94. bool dlist::prev_element(ent& x)  const
  95. { if (iterator) 
  96.      set_iterator(iterator->pred);
  97.   else 
  98.      set_iterator(t);
  99.  
  100.   if (iterator) 
  101.   { x = iterator->e;
  102.     return true; 
  103.    } 
  104.   return false; 
  105.  }
  106.  
  107. //------------------------------------------------------------------------------
  108.  
  109. dlink* dlist::get_item(int i) const
  110. { dlink* p = h;
  111.   while ( p && i--) p = p->succ; 
  112.   return p;
  113. }
  114.  
  115. dlink* dlist::succ(dlink* p, int i)  const
  116. { while ( p && i--) p = p->succ; 
  117.   return p;
  118. }
  119.  
  120. dlink* dlist::pred(dlink* p, int i) const
  121. { while ( p && i--) p = p->pred; 
  122.   return p;
  123. }
  124.  
  125. dlink* dlist::search(ent x) const  /* linear search */
  126. { dlink* p = h;
  127.   while ( p && (p->e != x)) p = p->succ; 
  128.   return p;
  129. } 
  130.  
  131. int dlist::rank(ent x)   const   /* rank by linear search */
  132. { dlink* p = h;
  133.   int r = 1;
  134.   while ( p && (p->e != x)) 
  135.   { p = p->succ; 
  136.     r++;
  137.    }
  138.   return (p) ? r : 0;
  139. } 
  140.  
  141. void dlist::pop()    
  142. { if (iterator!=0) error_handler(1,"pop: deletion while iterator is active");
  143.   dlink* x=h; 
  144.   if (count==0) return;
  145.   if (--count) { h = h->succ; h->pred = 0; }
  146.   else  h = t = 0;
  147.   clear_el(x->e);
  148.   delete x;
  149. }
  150.  
  151. void dlist::Pop()    
  152. { if (iterator!=0) error_handler(1,"Pop: deletion while iterator is active");
  153.   dlink* x=t; 
  154.   if (count==0) return;
  155.   if (--count) { t = t->pred; t->succ = 0; }
  156.   else  h = t = 0;
  157.   clear_el(x->e);
  158.   delete x;
  159. }
  160.  
  161. dlink* dlist::insert(ent a, dlink* l, int dir) 
  162. { 
  163.   if (iterator!=0) error_handler(2,"insert: insertion while iterator is active");
  164.  
  165.   if (l==0) return dir ? append(a) : push(a); 
  166.  
  167.   dlink* s=l->succ;
  168.   dlink* p=l->pred;
  169.   dlink* n;
  170.   
  171.   if (dir==0) //insert after l
  172.   { n= new dlink(a,l,s);
  173.     l->succ = n;
  174.     if (l==t) t=n;
  175.     else s->pred = n;}
  176.  
  177.   else //insert before l
  178.   { n= new dlink(a,p,l);
  179.     l->pred = n;
  180.     if (l==h) h=n;
  181.     else p->succ = n;}
  182.  
  183.   count++;
  184.  
  185.   return n;
  186. }
  187.  
  188. dlink* dlist::push(ent a)   
  189. { if (iterator!=0) error_handler(2,"push: insertion while iterator is active");
  190.   count++;
  191.   if (h) h = h->pred = new dlink(a,0,h); 
  192.   else   h = t =  new dlink(a,0,0);
  193.   return h;
  194. }
  195.  
  196. dlink* dlist::append(ent a)
  197. { if(iterator!=0) error_handler(2,"append: insertion while iterator is active");
  198.   count++;
  199.   if (t) t = t->succ = new dlink(a,t,0);
  200.   else   t = h = new dlink(a,0,0);
  201.   return t; 
  202. } 
  203.  
  204. void dlist::conc(dlist& l)
  205. { if (iterator!=0) error_handler(2,"conc: iterator is active");
  206.  if (t) { t->succ = l.h;
  207.           if (l.h) { l.h->pred = t; t = l.t; } }
  208.    else { h = l.h; t = l.t; }
  209.  count = count+l.count;
  210.  l.h = l.t = 0;
  211.  l.count = 0;
  212. }
  213.  
  214.  
  215. void dlist::split(dlink* p, dlist& l1, dlist& l2)
  216. { if (iterator!=0) 
  217.    error_handler(1,"list: split while iterator is active");
  218.  
  219.   //if (p==nil) error_handler(888,"split at nil item");
  220.  
  221.   l1.clear();
  222.   l2.clear();
  223.  
  224.   if (p==nil)    // l1 = empty,  l2 = l, l = empty;
  225.   { l2.h = h;
  226.     l2.t = t;
  227.     l2.count = count;
  228.     h = t = 0;
  229.     count = 0;
  230.     return;
  231.    }
  232.  
  233.   if (h == 0) return;   /* empty list */
  234.  
  235.  
  236.   if (p->pred)
  237.   { l1.h = h;
  238.     l1.t = p->pred;
  239.     p->pred->succ = 0;
  240.    }
  241.  
  242.   p->pred = 0;
  243.   l2.h = p;
  244.   l2.t = t;
  245.  
  246.  
  247.   // have to set counters
  248.   // "count the smaller half" gives amortized n log n  bound
  249.  
  250.   dlink* l = l1.h;
  251.   dlink* r = l2.h;
  252.   int    c = 0;
  253.  
  254.   while (l && r)
  255.   { l = l->succ;
  256.     r = r->succ;
  257.     c++;
  258.    }
  259.  
  260.   if (l==0)   // left end reached first
  261.   { l1.count = c;
  262.     l2.count = count - l1.count;
  263.    }
  264.  
  265.   else
  266.   { l2.count = c;
  267.     l1.count = count - l2.count;
  268.    }
  269.  
  270.   /* make original list empty */
  271.   
  272.   h = t = 0;
  273.   count = 0;
  274.  
  275. }
  276.  
  277.  
  278. void dlist::del(dlink* loc)
  279. { if (iterator!=0) 
  280.    error_handler(1,"dlist::del: deletion while iterator is active");
  281.  
  282.   if (loc==0)   
  283.    error_handler(999,"dlist::del: item = nil");
  284.  
  285.   if (loc==h)  { pop(); return; }
  286.  
  287.   if (loc==t)  { Pop(); return; }
  288.   
  289.  
  290.   dlink* p = loc->pred;
  291.   dlink* s = loc->succ;
  292.   p->succ = s;
  293.   s->pred = p;
  294.   count--;
  295.  
  296.   clear_el(loc->e);
  297.   delete loc;
  298. }
  299.  
  300. dlink* dlist::cyclic_succ(dlink* loc) const
  301. { if (loc==0) return 0;
  302.   return loc->succ? loc->succ : h;
  303. }
  304.  
  305. dlink* dlist::cyclic_pred(dlink* loc) const
  306. { if (loc==0) return 0;
  307.   return loc->pred? loc->pred : t;
  308. }
  309.  
  310. dlink* dlist::max(CMP_ENT f) const
  311. { if (h==0) return 0;
  312.   dlink* m=h;
  313.   dlink* p=m->succ;
  314.  
  315.   if (f) // use cmp function f
  316.      while (p)
  317.      { if (f(p->e,m->e)) m=p;
  318.        p=p->succ;
  319.       }
  320.   else  /* // use virtual cmp function  
  321.            while (p)
  322.            { if (cmp(p->e,m->e)) m=p;
  323.              p=p->succ;
  324.             }
  325.          */
  326.         error_handler(1,"list: max needs cmp function parameter");
  327.  
  328.   return m;
  329. }
  330.  
  331. dlink* dlist::min(CMP_ENT f) const
  332. { if (h==0) return 0;
  333.   dlink* m=h;
  334.   dlink* p=m->succ;
  335.  
  336.   if (f) // use cmp function f
  337.      while (p)
  338.      { if (f(m->e,p->e)) m=p;
  339.        p=p->succ;
  340.      }
  341.   else  /* // use virtual cmp function  
  342.            while (p)
  343.            { if (cmp(m->e,p->e)) m=p;
  344.              p=p->succ;
  345.             }
  346.          */
  347.         error_handler(1,"list: min needs cmp function parameter");
  348.  
  349.   return m;
  350. }
  351.  
  352. void dlist::apply(ENT_TO_VOID f)
  353. { dlink* p = h;
  354.  
  355.   while (p)
  356.   { f(p->e);
  357.     p = p->succ;
  358.   }
  359. }
  360.  
  361. void dlist::permute()
  362. { 
  363.   if (iterator!=0) error_handler(3,"permute: modification while iterator is active");
  364.  
  365.   list_item* A = new list_item[count+2];
  366.   list_item x = h;
  367.   int j;
  368.  
  369.   A[0] = A[count+1] = 0;
  370.  
  371.   for(j=1; j <= count; j++)
  372.   { A[j] = x;
  373.     x = x->succ;
  374.    }
  375.  
  376.   init_random();
  377.  
  378.   for(j=1; j<count; j++)  
  379.   { int r = random(j,count);
  380.     if (j!=r) SWAP(A[j],A[r]);
  381.    }
  382.  
  383.   for(j=1; j<=count; j++) 
  384.   { A[j]->succ = A[j+1];
  385.     A[j]->pred = A[j-1];
  386.    }
  387.  
  388.   h = A[1];
  389.   t = A[count];
  390.   
  391.   delete A;
  392. }
  393.         
  394.  
  395. void dlist::bucket_sort(int i, int j, ENT_TO_INT f)
  396. { if (iterator!=0) error_handler(3,"bucket_sort: modification while iterator is active");
  397.   int k;
  398.   dlist* bucket= new dlist[j-i+1];
  399.   ent e;
  400.  
  401.   while (count) { e = head(); 
  402.                   copy_el(e);
  403.                   pop();      // destroys one copy
  404.                   k = f(e);
  405.                   if ((k>=i)&&(k<=j)) bucket[k-i].append(e);
  406.                   else error_handler(4,"bucket_sort: value out of range") ;
  407.                  }
  408.  for (k=i;k<=j;k++) 
  409.      while (bucket[k-i].count) 
  410.        { e = bucket[k-i].head();
  411.          append(e);
  412.          bucket[k-i].pop();    // no destroy  in dlist::pop
  413.         }
  414.  
  415.  delete (char*)bucket;
  416. }
  417.  
  418. /*
  419. void dlist::quick_sort(dlink** A,int l, int r)
  420. { // use virtual cmp routine (member of dlist)
  421.  
  422.   register int i = l;
  423.   register int k = r+1;
  424.   ent s = A[l]->e;
  425.   //dlink* t;
  426.  
  427.   while (i<k)
  428.   { while (i < r && cmp(A[++i]->e,s) < 0);
  429.     while (k > l && cmp(A[--k]->e,s) > 0);
  430.     if (k>i) SWAP(A[i],A[k]);
  431.    }
  432.  
  433.   SWAP(A[l],A[k]);
  434.  
  435.   if (l < k-1) quick_sort(A,l,k-1);
  436.   if (r > k+1) quick_sort(A,k+1,r);
  437. }
  438. */
  439.  
  440.         
  441. void dlist::quick_sort(dlink** A,int l, int r, CMP_ENT cmp_fct)
  442. { // use ordering defined by cmp_fct(ent& x,ent& y)
  443.  
  444.   register int i = l;
  445.   register int k = r+1;
  446.   ent s = A[l]->e;
  447.   //dlink* t;
  448.  
  449.   while (i<k)
  450.   { while (i<r && cmp_fct(A[++i]->e,s)<0);
  451.     while (k>l && cmp_fct(A[--k]->e,s)>0);
  452.     if (k>i) SWAP(A[i],A[k]);
  453.    }
  454.  
  455.   SWAP(A[l],A[k]);
  456.  
  457.   //t = A[l];
  458.   //A[l] = A[k];
  459.   //A[k] = t;
  460.  
  461.   if (l < k-1) quick_sort(A,l,k-1,cmp_fct);
  462.   if (r > k+1) quick_sort(A,k+1,r,cmp_fct);
  463. }
  464.  
  465. void dlist::sort(CMP_ENT cmp_fct)
  466. { if (iterator!=0)
  467.       error_handler(1,"sort: modification while iterator is active");
  468.  
  469.   if (count==0) return;    // nothing to sort
  470.  
  471.   register int i;
  472.   register dlink* loc = h;
  473.   dlink** A = new dlink*[count+2];
  474.  
  475.   A[0] = A[count+1] = 0;
  476.  
  477.   for(i=1;i<=count;i++)
  478.   { A[i] = loc;
  479.     loc = loc->succ;
  480.    }
  481.  
  482.   init_random();
  483.  
  484.   for(i=1;i<=count;i++) 
  485.     { int j = random(1,count);    // random permutation
  486.        if (i!=j) SWAP(A[i],A[j]);  
  487.      }
  488.  
  489.   if (cmp_fct)
  490.        quick_sort(A,1,count,cmp_fct);
  491.   else // quick_sort(A,1,count);
  492.        error_handler(1,"list: sort needs cmp function parameter");
  493.  
  494.   for (i=1;i<=count;i++) 
  495.   { A[i]->succ = A[i+1];
  496.     A[i]->pred = A[i-1];
  497.    }
  498.  
  499.   h = A[1];
  500.   t = A[count];
  501.  
  502.   delete A;
  503.  }
  504.         
  505.  
  506. dlist& dlist::operator=(const dlist& x)
  507. { iterator=0;
  508.   clear();
  509.  
  510.   dlink* p = x.h;         
  511.                                 
  512.   while (p) { copy_el(p->e);
  513.               append(p->e);  // does not make a copy !!!
  514.               p = p->succ;
  515.              }
  516.   return *this;
  517. }
  518.  
  519. dlist dlist::operator+(const dlist& x)  // concatenation
  520. {
  521.  dlist y = x;
  522.   dlink* p = t;
  523.   while (p) { x.copy_el(p->e);
  524.               y.push(p->e);    
  525.               p = p->pred;}
  526.   return y;
  527. }
  528.  
  529. void dlist::clear()
  530. { if (h==nil) return;
  531.   register dlink* p = h;
  532.   while (p) 
  533.   { clear_el(p->e);
  534.     p = p->succ;
  535.     //delete h;
  536.     //h = p;
  537.    }
  538.   deallocate_list(h,t,3);
  539.   h=0;
  540.   t=0;
  541.   iterator=0;
  542.   count=0;
  543. }
  544.  
  545. void dlist::print(ostream& out, string s, char space) const
  546. { list_item l = h;
  547.   cout << s;
  548.   if (l)
  549.   { print_el(l->e,out); 
  550.     l = l->succ;
  551.     while (l)
  552.       { out << chr(space);
  553.         print_el(l->e,out); 
  554.         l = l->succ;
  555.        }
  556.   }
  557.   out.flush();
  558. }
  559.  
  560. void dlist::read(istream& in, string s, char delim)
  561. { char c;
  562.   ent x;
  563.   cout << s;
  564.  
  565.   clear();
  566.   while (in)
  567.   { in.get(c);
  568.     if (c==delim) break;
  569.     in.putback(c);
  570.     read_el(x,in); // creates an object 
  571.     append(x);     // makes no copy   (dlist)
  572.    }
  573.  
  574. }
  575.