home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / ledar34.zip / leda-r-3_4_tar / LEDA-3.4 / src / dict / _ch_array.c < prev    next >
C/C++ Source or Header  |  1996-09-03  |  4KB  |  224 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA 3.4
  4. +
  5. +  _ch_array.c
  6. +
  7. +  This file is part of the LEDA research version (LEDA-R) that can be 
  8. +  used free of charge in academic research and teaching. Any commercial
  9. +  use of this software requires a license which is distributed by the
  10. +  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
  11. +  (fax +49 681 31104).
  12. +
  13. +  Copyright (c) 1991-1996  by  Max-Planck-Institut fuer Informatik
  14. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  15. +  All rights reserved.
  16. + 
  17. *******************************************************************************/
  18.  
  19. #include <LEDA/impl/ch_array.h>
  20.  
  21. //------------------------------------------------------------------------------
  22. //
  23. //  hashing array with chaining and table doubling
  24. //
  25. //  only integer/pointer keys
  26. //  no delete operation
  27. //
  28. //  S. Naeher (1994)
  29. //
  30. //------------------------------------------------------------------------------
  31.  
  32.  
  33. #define NIL GenPtr(this)
  34.  
  35.  
  36. /* #define HASH(x) (table + (int(x) & table_size_1)) */
  37.  
  38. #define HASH(x) (table + (hash_fct(x) & table_size_1))
  39.  
  40.  
  41. ch_array::ch_array(int n) 
  42. { int ts = 1;
  43.   while (ts < n) ts <<= 1;
  44.   init_table(ts); 
  45. }
  46.  
  47.  
  48. GenPtr ch_array::lookup(GenPtr x) const
  49. { 
  50.   ch_array_item p = HASH(x);
  51.   ((GenPtr&)STOP.k) = x;
  52.   while (p->k != x) p = p->succ;
  53.   return (p == &STOP) ? nil : p;
  54. }
  55.  
  56.  
  57. GenPtr ch_array::access(GenPtr x) const
  58. { ch_array_item p = HASH(x);
  59.   ((GenPtr&)STOP.k) = x;
  60.   while (p->k != x) p = p->succ;
  61.   if (p == &STOP) init_inf(x);
  62.   else x = p->i;
  63.   return x;
  64. }
  65.  
  66.  
  67. GenPtr& ch_array::access(GenPtr x)
  68. { 
  69.   //if (x == NIL) error_handler(1,"internal error in ch_array");
  70.  
  71.   ch_array_item p = HASH(x);
  72.  
  73.   if (p->k == x) return p->i;
  74.  
  75.   if (p->k == NIL)
  76.   { p->k = x;
  77.     init_inf(p->i);
  78.     return p->i;
  79.    }
  80.  
  81.   STOP.k = x;
  82.   ch_array_item q = p->succ; 
  83.   while (q->k != x) q = q->succ;
  84.   if (q != &STOP) return q->i;
  85.  
  86.  
  87.   // index x not present, insert it
  88.  
  89.   if (free == table_end)   // table full: rehash
  90.   { rehash();
  91.     p = HASH(x);
  92.    }
  93.  
  94.   q = free++;
  95.   q->k = x;
  96.   init_inf(q->i);
  97.   q->succ = p->succ;
  98.   p->succ = q;
  99.  
  100.   return q->i;
  101. }
  102.  
  103.  
  104.  
  105. void ch_array::destroy() 
  106. { for(ch_array_item p = table; p < table_end; p++)
  107.     if (p->k != NIL) clear_inf(p->i);
  108.   delete[] table; 
  109.  }
  110.  
  111.  
  112. void ch_array::init_table(int T)
  113. { 
  114.   table_size = T;
  115.   table_size_1 = T-1;
  116.  
  117.   table = new ch_array_elem[2*T];
  118.  
  119.   free      = table + T;
  120.   table_end = free  + T;
  121.  
  122.   ch_array_item p=table;
  123.  
  124.   while (p<free) 
  125.   { p->k = NIL;
  126.     p->succ = &STOP;
  127.     p++;
  128.    }
  129.  
  130.   while (p<table_end) 
  131.   { p->k = NIL;
  132.     p++;
  133.    }
  134.  
  135.  
  136. }
  137.  
  138.  
  139. #define INSERT(x,y)\
  140. { ch_array_item q = HASH(x);\
  141.   if (q->k == NIL)\
  142.     { q->k = x;\
  143.       q->i = y;\
  144.      }\
  145.   else\
  146.    { free->k = x;\
  147.      free->i = y;\
  148.      free->succ = q->succ;\
  149.      q->succ = free++;\
  150.    }\
  151. }
  152.  
  153.  
  154. void ch_array::rehash()
  155. { 
  156.   ch_array_item old_table = table;
  157.   ch_array_item old_table_end = table_end;
  158.   
  159.   init_table(2*table_size);
  160.  
  161.   for(ch_array_item p = old_table; p < old_table_end; p++)
  162.       if (p->k != NIL) INSERT(p->k,p->i);
  163.  
  164.   delete[] old_table;
  165. }
  166.  
  167.  
  168. ch_array_item ch_array::first_item() const
  169. { ch_array_item p = table;
  170.   while (p < table_end && p->k == NIL) p++;
  171.   return (p < table_end) ? p : 0;
  172.  }
  173.  
  174.  
  175. ch_array_item ch_array::next_item(ch_array_item p) const
  176. { p++;
  177.   while (p < table_end && p->k == NIL) p++;
  178.   return (p < table_end) ? p : 0;
  179.  }
  180.  
  181.  
  182. ch_array::ch_array(const ch_array& D)
  183. { 
  184.   init_table(D.table_size);
  185.  
  186.   for(ch_array_item p = D.table; p < D.table_end; p++) 
  187.   { if (p->k != GenPtr(&D)) 
  188.     { INSERT(p->k,p->i);
  189.       D.copy_inf(p->i);
  190.      }
  191.    }
  192. }
  193.  
  194.  
  195. ch_array& ch_array::operator=(const ch_array& D)
  196. { 
  197.   destroy();
  198.   init_table(D.table_size);
  199.  
  200.   for(ch_array_item p = D.table; p < D.table_end; p++) 
  201.   { if (p->k != GenPtr(&D)) 
  202.     { INSERT(p->k,p->i);
  203.       copy_inf(p->i);
  204.      }
  205.    }
  206.   return *this;
  207. }
  208.  
  209.  
  210. void ch_array::print()
  211. { for (int i=0; i<table_size; i++)
  212.   { ch_array_item p = table + i;
  213.     if (p->k != NIL)
  214.     { int l = 0;
  215.       while(p != &STOP)
  216.       { l++; 
  217.         p = p->succ;
  218.        }
  219.       cout << string("L(%d) = %d",i,l) << endl;
  220.      }
  221.    }
  222. }
  223.   
  224.