home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / incl / array.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  5.7 KB  |  193 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  array.h
  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.  
  17.  
  18.  
  19. #ifndef ARRAYH
  20. #define ARRAYH
  21.  
  22. #include <LEDA/basic.h>
  23.  
  24. //------------------------------------------------------------------------------
  25. // array
  26. // 
  27. // Stefan Naeher  (1989)
  28. //------------------------------------------------------------------------------
  29.  
  30.  
  31.  
  32. class ent_array {
  33.     ent* v;
  34.     int sz;    
  35.         int Low;
  36.         int High;
  37.         int t;
  38.         int dir;
  39.         void quick_sort(int l, int r);
  40.         void quick_sort(int l, int r, CMP_ENT f);
  41.  
  42. virtual int cmp(ent& x, ent& y)  { return int(x)-int(y); };
  43. virtual void print_el(ent& x,ostream& out) const { out << int(x); }
  44. virtual void read_el(ent& x,istream& in)   const { in >> *(int*)&x; }
  45. virtual void clear_entry(ent& x) { x = 0; }
  46. virtual void copy_entry(ent& x)  { x = 0; }
  47. virtual void init_entry(ent& x)  { x = 0; }
  48.  
  49. protected:
  50.         void clear();
  51.  
  52. public:
  53.    void init();
  54.     ~ent_array() { delete v; }
  55.  
  56.     ent_array(int, int);
  57.     ent_array(int);
  58.     ent_array(ent_array&);
  59.     ent_array& operator=(ent_array&);
  60.         int size() { return sz; }
  61.         int low()  { return Low; }
  62.         int high() { return High; }
  63.     ent& elem(int i)       { return v[i]; }
  64.     ent  elem(int i) const { return v[i]; }
  65.     ent& entry(int i)
  66.     { if (i<Low || i>High)
  67.           error_handler(2,"array::entry index out of range");
  68.           return v[i-Low];
  69.          }
  70.     ent  inf(int i) const
  71.     { if (i<Low || i>High)
  72.           error_handler(2,"array::inf index out of range");
  73.           return v[i-Low];
  74.          }
  75.  
  76.         void permute(int,int);
  77.  
  78.         void permute()  { permute(Low,High); }
  79.  
  80.         void sort(CMP_ENT f, int l, int h, bool randomize) 
  81.         { if (randomize) permute();
  82.           quick_sort(l-Low,h-Low,f);
  83.          }
  84.  
  85.         void sort(CMP_ENT f, bool randomize) 
  86.         { if (randomize) permute();
  87.           quick_sort(0,sz-1,f); 
  88.          }
  89.  
  90.         int binary_search(ent);
  91.         int binary_search(ent,CMP_ENT);
  92.  
  93.    void print(ostream&,string, char space)   const;    
  94.    void print(ostream& out,char space=' ') const { print(out,"",space);  }
  95.    void print(string s, char space=' ')    const { print(cout,s,space);  }
  96.    void print(char space=' ')              const { print(cout,"",space); }   
  97.  
  98.  
  99.    void read(istream&,string);  
  100.    void read(istream& in)      { read(in,"");  }
  101.    void read(string s )        { read(cin,s);  }   
  102.    void read()                 { read(cin,""); }   
  103.  
  104.  
  105. };
  106.  
  107.  
  108. #define array(type) name2(type,array)
  109.  
  110. #define arraydeclare(type)\
  111. \
  112. typedef int (*name2(type,_array_cmp))(type&,type&);\
  113. \
  114. class array(type) : public ent_array {\
  115. \
  116. /*int     cmp(ent& x, ent& y) { return compare(type(x),type(y)); }*/\
  117. \
  118. void print_el(ent& x,ostream& out) const { Print(*(type*)&x,out);}\
  119. void read_el(ent& x,istream& in)   const { type y=0; Read(y,in); x = Copy(y); }\
  120. void clear_entry(ent& x)  { Clear(*(type*)&x); }\
  121. void copy_entry(ent& x)   { Copy(*(type*)&x);  }\
  122. void init_entry(ent& x)   { type y=0; x = Copy(y); }\
  123. \
  124. public:\
  125. array(type)(int a, int b)   : ent_array(a,b)             { init(); }\
  126. array(type)(int n)          : ent_array(n)               { init(); }\
  127. array(type)(array(type)& A) : ent_array((ent_array&) A)  {}\
  128. ~array(type)()                                           { clear(); }\
  129. \
  130. array(type)& operator=(array(type)& A)\
  131.               { return (array(type)&)ent_array::operator=((ent_array&) A); }\
  132. type& operator[](int i)             { return *(type*)&ent_array::entry(i);}\
  133. type  operator[](int i)   const     { return type(ent_array::inf(i));}\
  134. void sort(name2(type,_array_cmp) f, bool rand=true)\
  135.                                     { CMP_ENT g = CMP_ENT(f);\
  136.                                       ent_array::sort(g,rand); }\
  137. void sort(name2(type,_array_cmp) f,int l, int h, bool rand=true)\
  138.                                     { CMP_ENT g = CMP_ENT(f);\
  139.                                       ent_array::sort(g,l,h,rand); }\
  140. int binary_search(type x)           { return ent_array::binary_search(Ent(x));}\
  141. int binary_search(type x,name2(type,_array_cmp) f)\
  142.                          { return ent_array::binary_search(Ent(x),CMP_ENT(f));}\
  143. };
  144.  
  145. /*------------------------------------------------------------------------*/
  146. /* 2 dimensional arrays                                                   */
  147. /*------------------------------------------------------------------------*/
  148.  
  149.  
  150.  
  151. class ent_array2 {
  152. ent_array A;
  153. int Low1, Low2, High1, High2;
  154. virtual void clear_entry(ent& x)  { x = 0; }
  155. virtual void copy_entry(ent& x)   { x = 0; }
  156. virtual void init_entry(ent& x)   { x = 0; }
  157.  
  158. protected:
  159. void clear();
  160. ent_array* row(int i) const { return (ent_array*)A.inf(i); }
  161.  
  162. public:
  163. void init(int,int,int,int);
  164. int low1()  { return Low1; }
  165. int low2()  { return Low2; }
  166. int high1() { return High1; }
  167. int high2() { return High2; }
  168. ent_array2(int,int,int,int);
  169. ent_array2(int,int);
  170. ~ent_array2();
  171. };
  172.  
  173.  
  174. #define array2(type) name2(type,array2)
  175.  
  176. #define array2declare(type)\
  177. \
  178. struct array2(type) : public ent_array2 {\
  179. \
  180. void clear_entry(ent& x)  { Clear(*(type*)&x); }\
  181. void copy_entry(ent& x)   { x = Copy(*(type*)&x);  }\
  182. void init_entry(ent& x)   { type y=0; x = Copy(y); }\
  183. \
  184. type& operator()(int i, int j)       { return *(type*)&(row(i)->entry(j)); }\
  185. type  operator()(int i, int j) const { return type(row(i)->entry(j)); }\
  186. \
  187.  array2(type)(int a,int b,int c,int d) :ent_array2(a,b,c,d){ init(a,b,c,d);}\
  188.  array2(type)(int n,int m)             :ent_array2(n,m)    { init(0,n-1,0,m-1);}\
  189. ~array2(type)()                                            { clear();         }\
  190. };
  191.  
  192. #endif
  193.