/*******************************************************************************
+
+  LEDA 3.5
+
+  _ch_hash.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
#include <LEDA/impl/ch_hash.h>

void ch_hash::init(int T)
{ 
  ch_hash_item p;
  ch_hash_item stop;

  table_size = T;
  table_size_1 = T-1;

  low_table  = (T > 1024) ? T/2 : -1;
  high_table = 2*T;

  table = new ch_hash_elem[table_size];

  stop = table + table_size;
  for(p = table; p < stop; p++) p->succ = nil;

  count = 0;
}


void ch_hash::rehash(int T)
{ 
  ch_hash_item old_table = table;
  int old_table_size = table_size;
  int old_count = count;

  init(T); 
  count = old_count;   // since init overwrites count

  ch_hash_item stop = old_table + old_table_size;
  for (ch_hash_item it = old_table; it < stop; it++) 
  { 
    ch_hash_item old_r = it->succ;
    if (old_r == nil) continue;
    ch_hash_item old_p = it;
    do
    { ch_hash_item p = table_entry_for(old_p->k);
      //  table + (hash_fct(old_p->k) & table_size_1);
      if (p->succ == nil)
        { p->k = old_p->k;
          p->i = old_p->i;
          p->succ = &STOP;
        }
      else
        { p->succ = new ch_hash_elem(old_p->k,old_p->i,p->succ); }
      if (old_p != it)
        { delete old_p; }
      old_p = old_r;
      old_r = old_p->succ;
    } while (old_p != &STOP);
   }

  delete[] old_table;
}


void ch_hash::destroy()
{ 
  for(int i = 0; i < table_size; i++) 
  { ch_hash_item p = table + i;
    if ( p->succ == nil ) continue;
    do
    { clear_key(p->k);
      clear_inf(p->i);
      ch_hash_item q = p;
      p = p->succ;
      if ( q != table + i ) delete q;
    } while ( p != &STOP);
  }

  delete[] table;
}


ch_hash::ch_hash(const ch_hash& D)
{ ch_hash_item p;
  init(D.table_size);
  for (int i = 0; i < table_size; i++)
  { p = &D.table[i];
    if (p->succ == nil) continue;
    while(p != &(D.STOP))
    { fast_insert(p->k,p->i);
      D.copy_key(p->k);
      D.copy_inf(p->i);  
      p = p->succ;
    }
  }
}

ch_hash& ch_hash::operator=(const ch_hash& D)
{ ch_hash_item p;
  clear();
  init(D.table_size);
  for (int i=0; i<D.table_size; i++)
  { p = &D.table[i];
    if (p->succ == nil) continue;
    while(p != &(D.STOP))
    { fast_insert(p->k,p->i);
      p = p->succ;
     }
   }
  return *this;
}



ch_hash_item ch_hash::lookup(GenPtr x) const
{ 
  ch_hash_item q = table_entry_for(x);
 
  if ( q->succ == nil ) return nil;

  ((GenPtr&)STOP.k) = x;

  if ( key_type_id() == INT_TYPE_ID )
     { while ( q->k != x ) q = q->succ;}
  else
     { while (!equal_key(q->k,x)) q = q->succ;}

  return (q == &STOP) ? nil : q;
}


ch_hash_item ch_hash::insert(GenPtr x, GenPtr y)
{ 
  ch_hash_item p = table_entry_for(x);
  ch_hash_item q = p;

  if (p->succ != nil)
  { STOP.k = x;

    if (key_type_id() == INT_TYPE_ID)
       while (p->k != x) p = p->succ;
    else
       while (!equal_key(p->k,x)) p = p->succ;

    if (p != &STOP)
    { clear_inf(p->i);
      p->i = y;
      copy_inf(p->i);
      return p;
    }
  }

  // rehash before inserting the new key

  if (++count == high_table) 
  { rehash(high_table);
    q = table_entry_for(x);
  }

  copy_key(x);
  copy_inf(y);

  if (q->succ == nil) 
    { q->k = x;
      q->i = y;
      q->succ = &STOP;
     }
  else
    { q->succ = new ch_hash_elem(x,y,q->succ);
      q = q->succ;
     }

  return q;
}


ch_hash_item ch_hash::fast_insert(GenPtr x, GenPtr y)
{ 
  ch_hash_item p = table_entry_for(x);
  ch_hash_item q = p;

  if (++count == high_table) 
  { rehash(high_table);
    q = table_entry_for(x);
  }

  copy_key(x);
  copy_inf(y);

  if (q->succ == nil) 
    { q->k = x;
      q->i = y;
      q->succ = &STOP;
     }
  else
    { q->succ = new ch_hash_elem(x,y,q->succ);
      q = q->succ;
     }

  return q;
}


void ch_hash::del(GenPtr x)
{ 
  ch_hash_item p = lookup(x);
  if ( p != nil) del_item(p);
}

  

void ch_hash::del_item(ch_hash_item q)
{ ch_hash_item p = table_entry_for(q->k);

  clear_key(q->k);
  clear_inf(q->i);

  if (p == q) // q is first item in its list
    { if ( q->succ == &STOP ) q->succ = nil;
      else 
      { p       = q->succ;
        q->k    = p->k;
        q->i    = p->i;
        q->succ = p->succ;
        delete p;
      }
    }
  else // q is not the first item
    { while( p->succ != q ) p = p->succ;
      p->succ = q->succ;
      delete q;
     }
  count--;
  if (count == low_table) rehash(low_table);
 }
  

void ch_hash::change_inf(ch_hash_item p, GenPtr x)
{ clear_inf(p->i);
  p->i = x;
  copy_inf(p->i);
 }  


ch_hash_item ch_hash::first_item() const 
{ *(ch_hash_item*)&iterator = table;
  ch_hash_item q = table;
  if (q->succ == nil) q = next_item(q); 
  return q;
 }


ch_hash_item ch_hash::next_item(ch_hash_item q) const 
{ if ( q->succ != nil && q->succ != &STOP) return q->succ;
  ch_hash_item stop = table + table_size;
  while (iterator < stop)
  { (*(ch_hash_item*)&iterator)++;
    if (iterator == stop) return nil;
    if (iterator->succ == nil) continue; 
    return iterator;
   }
  return 0;
}



