home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / basic / _array.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  4.3 KB  |  222 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _array.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/array.h>
  17.  
  18.  
  19. void ent_array::read(istream& in, string s)
  20. { cout << s;
  21.   int i = 0; 
  22.   while (in && i<sz)
  23.   { clear_entry(v[i]);
  24.     read_el(v[i],in);
  25.     i++;
  26.    }
  27.  }
  28.  
  29. void ent_array::print(ostream& out, string s, char space) const
  30. { cout << s;
  31.   int i = 0; 
  32.   while (i < sz)
  33.     { out << chr(space);
  34.       print_el(v[i],out); 
  35.       i++;
  36.      }
  37.   out.flush();
  38. }
  39.  
  40. void ent_array::clear() 
  41. { register int i = sz;
  42.   register ent* vv = &v[i];
  43.   while (i--) clear_entry(*--vv);
  44. }
  45.  
  46. void ent_array::init() 
  47. { register int i = sz;
  48.   register ent* vv = &v[i];
  49.   while (i--) init_entry(*--vv);
  50. }
  51.  
  52.  
  53. ent_array::ent_array(int a, int b)
  54. { if (a>b) error_handler(1,"bad array size");
  55.   Low = a;
  56.   High = b;
  57.   sz = b-a+1;
  58.   v = new ent[sz];
  59.   if (v==0) error_handler(99,"array: out of memory");
  60.  }
  61.  
  62. ent_array::ent_array(int n)
  63. { Low = 0;
  64.   High = n-1;
  65.   sz = n;
  66.   v = new ent[sz];
  67.   if (v==0) error_handler(99,"array: out of memory");
  68.  
  69.   register int i = sz;
  70.   register ent* vv = &v[i];
  71.   while (i--) init_entry(*--vv);
  72. }
  73.  
  74. ent_array::ent_array(ent_array& a)
  75. {       register i = a.sz;
  76.     sz = i;    
  77.         Low = a.Low;
  78.         High = a.High;
  79.     v = new ent[i];
  80.     register ent* vv = &v[i];
  81.     register ent* av = &a.v[i];
  82.     while (i--) { copy_entry(*--av);
  83.                       *--vv = *av;
  84.                      }
  85. }
  86.  
  87. ent_array& ent_array::operator=(ent_array& a)
  88. {
  89.     register i = a.sz;
  90.     if ((sz != i) || (Low != a.Low) || (High != a.High))
  91.         error_handler(3,"different array types in assignment");
  92.     register ent* vv = &v[i];
  93.     register ent* av = &a.v[i];
  94.     while (i--) 
  95.         { clear_entry(*--vv);
  96.       copy_entry(*--av);
  97.           *vv = *av;
  98.         }
  99.     return *this;
  100. }
  101.  
  102. void ent_array::permute(int l, int r)
  103. {
  104.   if (l<Low || l>High || r<l || r>High) 
  105.          error_handler(2,"array::permute illegal range");
  106.  
  107.   l -= Low;
  108.   r -= Low;
  109.  
  110.   register ent* x;
  111.   register ent* stop = v+r+1;
  112.   register int j;
  113.  
  114.   init_random();
  115.   for(x=v+l;x!=stop;x++) 
  116.   { j = random(l,r);  
  117.     if (x!=v+j) SWAP(*x,v[j]);  
  118.    }
  119. }
  120.  
  121.  
  122. void ent_array::quick_sort(register int l, register int r)
  123. { 
  124.   register int i = l;
  125.   register int k = r+1;
  126.   ent s = v[l];
  127.  
  128.   while (i<k)
  129.   { while (i<r && cmp(v[++i],s)<0);
  130.     while (k>l && cmp(v[--k],s)>0);
  131.     if (k>i) SWAP(v[i],v[k]);
  132.    }
  133.  
  134.   SWAP(v[l],v[k]);
  135.  
  136.   if (l < k-1) quick_sort(l,k-1);
  137.   if (r > k+1) quick_sort(k+1,r);
  138. }
  139.  
  140. void ent_array::quick_sort(register int l, register int r, CMP_ENT CMP)
  141. { 
  142.   register int i = l;
  143.   register int k = r+1;
  144.   ent s = v[l];
  145.  
  146.   while (i<k)
  147.   { while (i<r && CMP(v[++i],s)<0);
  148.     while (k>l && CMP(v[--k],s)>0);
  149.     if (k>i) SWAP(v[i],v[k]);
  150.    }
  151.  
  152.   SWAP(v[l],v[k]);
  153.  
  154.   if (l < k-1) quick_sort(l,k-1,CMP);
  155.   if (r > k+1) quick_sort(k+1,r,CMP);
  156. }
  157.  
  158.  
  159. int ent_array::binary_search(ent x)
  160. { int l = 0;
  161.   int r = sz-1;
  162.   int m;
  163.   while (l<r)
  164.   { m = (l+r)/2;
  165.     if (cmp(x,elem(m))==0) { l = m; break; }
  166.     if (cmp(x,elem(m)) > 0) l = m+1;
  167.     else
  168.     if (cmp(x,elem(m)) < 0) r = m-1;
  169.    }
  170.  
  171.   return  (cmp(elem(l),x)==0) ? (l+Low) : (Low-1);
  172. }
  173.  
  174. int ent_array::binary_search(ent x, CMP_ENT CMP)
  175. { int l = 0;
  176.   int r = sz-1;
  177.   int m;
  178.   while (l<r)
  179.   { m = (l+r)/2;
  180.     if (CMP(x,elem(m))==0) { l = m; break; }
  181.     if (CMP(x,elem(m)) > 0) l = m+1;
  182.     else
  183.     if (CMP(x,elem(m)) < 0) r = m-1;
  184.    }
  185.  
  186.   return  (CMP(elem(l),x)==0) ? (l+Low) : (Low-1);
  187. }
  188.  
  189.  
  190. void ent_array2::init(int a, int b, int c, int d)
  191. { register int i,j;
  192.   for (i=a;i<=b;i++) 
  193.       for (j=c; j<=d; j++) init_entry(row(i)->entry(j));
  194. }
  195.  
  196. ent_array2::ent_array2(int a, int b, int c, int d) : A(a,b) 
  197. { Low1  = a;
  198.   High1 = b;
  199.   Low2  = c;
  200.   High2 = d;
  201.   while (b>=a) A.entry(b--) = (ent) new ent_array(c,d); }
  202.  
  203. ent_array2::ent_array2(int a, int b) : A(a) 
  204. { Low1  = 0;
  205.   High1 = a-1;
  206.   Low2  = 0;
  207.   High2 = b-1;
  208.   while (a>0) A.entry(--a) = (ent) new ent_array(b); }
  209.  
  210. void ent_array2::clear()
  211. { register int i,j;
  212.   for (i=Low1;i<=High1;i++) 
  213.   for (j=Low2;j<=High2;j++) 
  214.   clear_entry(row(i)->entry(j));
  215.  }
  216.  
  217. ent_array2::~ent_array2()
  218. { register int i;
  219.   for (i=Low1;i<=High1;i++) delete (ent_array*)A.entry(i);
  220.  }
  221.  
  222.