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

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

数值算法/人工智能

开发平台：

MultiPlatform

_array.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _array.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/gen_array.h>
  15. #define SWAP(a,b) { GenPtr help = *a; *a = *b; *b = help; }
  17. #define MIN_D 16 
  19. void gen_array::read(istream& in, string s)
  20. { cout << s;
  21.   for (int i = 0; in && i<sz; i++) read_el(v[i],in);
  22.  }
  24. void gen_array::print(ostream& out, string s, char space) const
  25. { out << s;
  26.   for (int i=0; i<sz; i++)
  27.   { out << string("%c",space);
  28.     print_el(v[i],out); 
  29.    }
  30.   out.flush();
  31. }
  33. void gen_array::clear() 
  34. { GenPtr* p = v + sz;
  35.   while (p > v) clear_entry(*--p);
  36. }
  38. void gen_array::init() 
  39. { GenPtr* p = v + sz;
  40.   while (p > v) init_entry(*--p);
  41. }
  43. gen_array::gen_array()
  44. { Low = 0;
  45.   High = -1;
  46.   sz = 0;
  47.   v = 0;
  48.   last = 0;
  49. }
  52. gen_array::gen_array(int a, int b)
  53. { if (a>b) error_handler(1,"bad array size");
  54.   Low = a;
  55.   High = b;
  56.   sz = b-a+1;
  57.   v = new GenPtr[sz];  
  58.   if (v==0) error_handler(99,"array: out of memory");
  59.   last = v+sz-1;
  60.  }
  62. gen_array::gen_array(int n)
  63. { Low = 0;
  64.   High = n-1;
  65.   sz = n;
  66.   v = new GenPtr[sz];
  67.   if (v==0) error_handler(99,"array: out of memory");
  68.   last = v+sz-1;
  69. }
  71. gen_array::gen_array(const gen_array& a)
  72. { sz = a.sz;
  73.   Low = a.Low;
  74.   High = a.High;
  75.   v = new GenPtr[sz];
  76.   if (v==0) error_handler(99,"array: out of memory");
  77.   last = v+sz-1;
  78.   GenPtr* vv = v + sz;
  79.   GenPtr* av = a.v + sz;
  80.   while (vv > v) 
  81.   { *--vv = *--av;
  82.     a.copy_entry(*vv);
  83.    }
  84. }
  86. gen_array& gen_array::operator=(const gen_array& a)
  87. { if (this == &a) return *this;
  89.   if (sz != a.sz)
  90.   { clear();
  91.     sz = a.sz;       
  92.     delete v;
  93.     v = new GenPtr[sz];
  94.     if (v==0) error_handler(99,"array: out of memory");
  95.     last = v+sz-1;
  96.    }
  98.   Low = a.Low;
  99.   High = a.High;
  100.   GenPtr* vv = v + sz;
  101.   GenPtr* av = a.v + sz;
  102.   while (vv > v) 
  103.   { *--vv = *--av;
  104.     copy_entry(*vv);
  105.    }
  107.   return *this;
  108. }
  110. void gen_array::permute(int l, int r)
  111. {
  112.   if (l<Low || l>High || r<l || r>High) 
  113.          error_handler(2,"array::permute illegal range");
  114.  
  115.   l -= Low;
  116.   r -= Low;
  118.   GenPtr* x;
  119.   GenPtr* y;
  120.   GenPtr* stop = v+r+1;
  122.   for(x=v+l;x!=stop;x++) 
  123.   { y = v + rand_int(l,r);  
  124.     SWAP(x,y);  
  125.    }
  126. }
  129. void gen_array::sort(int l, int h) 
  130. {
  131.   GenPtr* left  = v+l-Low;
  132.   GenPtr* right = v+h-Low;
  133.   GenPtr* min_stop = left + MIN_D;
  135.   if (min_stop > right) min_stop = right;
  137.   if (int_type())
  138.     { int_quick_sort(left,right);
  139.       int_insertion_sort(left,right,min_stop);
  140.      }
  141.   else
  142.      { quick_sort(left,right);
  143.        insertion_sort(left,right,min_stop);
  144.       }
  145.  }
  148. void gen_array::quick_sort(GenPtr* l, GenPtr* r)
  149. { 
  150.   GenPtr* i = l+(r-l)/2; //rand_int(l,r);
  151.   GenPtr* k;
  153.   if (cmp(*i,*r) > 0) SWAP(i,r);
  154.   SWAP(l,i);
  156.   GenPtr  s = *l;
  158.   i = l;
  159.   k = r;
  161.   for(;;)
  162.   { while (cmp(*(++i),s)<0);
  163.     while (cmp(*(--k),s)>0);
  164.     if (i<k) SWAP(i,k) else break;
  165.    }
  167.   SWAP(l,k);
  169.   if (k > l+MIN_D) quick_sort(l,k-1);
  170.   if (r > k+MIN_D) quick_sort(k+1,r);
  171. }
  175. void gen_array::int_quick_sort(GenPtr* l, GenPtr* r)
  176. { 
  177.   GenPtr* i = l+(r-l)/2; //rand_int(l,r)
  178.   GenPtr* k;
  180.   if (LEDA_ACCESS(int,*i) > LEDA_ACCESS(int,*r)) SWAP(i,r);
  181.   SWAP(l,i);
  183.   int  s = LEDA_ACCESS(int,*l);
  185.   i = l;
  186.   k = r;
  188.   for(;;)
  189.   { while (LEDA_ACCESS(int,*(++i)) < s);
  190.     while (LEDA_ACCESS(int,*(--k)) > s);
  191.     if (i<k) SWAP(i,k) else break;
  192.    }
  194.   SWAP(l,k);
  196.   if (k > l+MIN_D) int_quick_sort(l,k-1);
  197.   if (r > k+MIN_D) int_quick_sort(k+1,r);
  198. }
  201. void gen_array::insertion_sort(GenPtr* l, GenPtr* r, GenPtr* min_stop)
  202. {
  203.   GenPtr* min=l;
  204.   GenPtr* run;
  205.   GenPtr* p;
  206.   GenPtr* q;
  208.   for (run = l+1; run <= min_stop; run++)
  209.       if (cmp(*run,*min) < 0) min = run;
  211.   SWAP(min,l);
  213.   if (r == l+1) return;
  215.   for(run=l+2; run <= r; run++)
  216.   { for (min = run-1; cmp(*run,*min) < 0; min--);
  217.     min++;
  218.     if (run != min) 
  219.     { GenPtr save = *run;
  220.       for(p=run, q = run-1; p > min; p--,q--) *p = *q;
  221.       *min = save;
  222.      }
  223.    }
  224. }
  228. void gen_array::int_insertion_sort(GenPtr* l, GenPtr* r, GenPtr* min_stop)
  229. {
  230.   GenPtr* min=l;
  231.   GenPtr* run;
  232.   GenPtr* p;
  233.   GenPtr* q;
  235.   for (run = l+1; run <= min_stop; run++)
  236.       if (LEDA_ACCESS(int,*run) <  LEDA_ACCESS(int,*min)) min = run;
  238.   SWAP(min,l);
  240.   if (r == l+1) return;
  242.   for(run=l+2; run <= r; run++)
  243.   { for (min = run-1; LEDA_ACCESS(int,*run) < LEDA_ACCESS(int,*min); min--);
  244.     min++;
  245.     if (run != min) 
  246.     { GenPtr save = *run;
  247.       for(p=run, q = run-1; p > min; p--,q--) *p = *q;
  248.       *min = save;
  249.      }
  250.    }
  251. }
  256. int gen_array::binary_search(GenPtr x)
  257. { int l = 0;
  258.   int r = sz-1;
  260.   if (int_type())
  261.     { int x_i = LEDA_ACCESS(int,x);
  262.       while (l<r)
  263.       { int m = (l+r)/2;
  264.         int m_i = LEDA_ACCESS(int,elem(m));
  265.         if (x_i == m_i) { l = m; break; }
  266.         l = (x_i > m_i) ? m+1 : m-1;
  267.        }
  268.      }
  269.   else
  270.      while (l<r)
  271.      { int m = (l+r)/2;
  272.        int c = cmp(x,elem(m));
  273.        if (c == 0) { l = m; break; }
  274.        l = (c > 0) ? m+1 : m-1;
  275.       }
  277.   return  (cmp(elem(l),x)==0) ? (l+Low) : (Low-1);
  278. }
  282. void gen_array2::init(int a, int b, int c, int d)
  283. { int i,j;
  284.   for (i=a;i<=b;i++) 
  285.       for (j=c; j<=d; j++) init_entry(row(i)->entry(j));
  286. }
  288. gen_array2::gen_array2(int a, int b, int c, int d) : A(a,b) 
  289. { Low1  = a;
  290.   High1 = b;
  291.   Low2  = c;
  292.   High2 = d;
  293.   while (b>=a) A.entry(b--) = (GenPtr) new gen_array(c,d); 
  294. }
  296. gen_array2::gen_array2(int a, int b) : A(a) 
  297. { Low1  = 0;
  298.   High1 = a-1;
  299.   Low2  = 0;
  300.   High2 = b-1;
  301.   while (a>0) A.entry(--a) = (GenPtr) new gen_array(b); 
  302. }
  304. void gen_array2::clear()
  305. { int i,j;
  306.   for (i=Low1;i<=High1;i++) 
  307.   for (j=Low2;j<=High2;j++) 
  308.   clear_entry(row(i)->entry(j));
  309. }
  311. gen_array2::~gen_array2()
  312. { for (int i=Low1;i<=High1;i++) delete (gen_array*)A.entry(i); }
  316. void gen_array2::copy_row(gen_array* from, gen_array* to) const
  317. { GenPtr* p = to->v + to->sz;
  318.   GenPtr* q = from->v + from->sz;
  319.   while (q > from->v) 
  320.   { *--p = *--q;
  321.     copy_entry(*p);
  322.    }
  323. }
  326. gen_array2::gen_array2(const gen_array2& a) : A(a.Low1,a.High1)
  327. { 
  328.   Low1 = a.Low1;
  329.   High1 = a.High1;
  330.   Low2 = a.Low2;
  331.   High2 = a.High2;
  333.   for(int i=Low1; i<=High1; i++)
  334.   { gen_array* p =  new gen_array(Low2,High2); 
  335.     if (p==0) error_handler(99,"array2: out of memory");
  336.     a.copy_row((gen_array*)a.A.inf(i),p);
  337.     A.entry(i) = p;
  338.    }
  339. }
  341. gen_array2& gen_array2::operator=(const gen_array2& a)
  342. { 
  343.   clear();
  345.   Low1 = a.Low1;
  346.   High1 = a.High1;
  347.   Low2 = a.Low2;
  348.   High2 = a.High2;
  350.   for(int i=Low1; i<=High1; i++)
  351.   { gen_array* p =  new gen_array(Low2,High2); 
  352.     if (p==0) error_handler(99,"array2: out of memory");
  353.     a.copy_row((gen_array*)a.A.inf(i),p);
  354.     A.entry(i) = p;
  355.    }
  357.   return *this;
  358. }