/*******************************************************************************
+
+  LEDA 3.5
+
+  _ch_map.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_map.h>

//------------------------------------------------------------------------------
//
//  hashing array with chaining and table doubling
//
//  only integer/pointer keys
//  no delete operation
//
//  S. Naeher (1994)
//  K. Mehlhorn/S. Naeher (1997)
//
//------------------------------------------------------------------------------


#ifdef NULLKEY
#undef NULLKEY
#endif

#define NULLKEY 0


ch_map::ch_map(int n) 
{ if (n < 0)
   { def_table_size = 512;
     init_table(512); 
    }
  else
   { int ts = 1;
     while (ts < n) ts <<= 1;
     def_table_size = ts;
     init_table(ts);
    }
  init_nullkey1();
}



ch_map_item ch_map::lookup(unsigned long x) const 
{ ch_map_item p = HASH(x);
  ((unsigned long&)STOP.k) = x;
  while (p->k != x) p = p->succ;
  return (p == &STOP) ? nil : p;
}


GenPtr& ch_map::access(ch_map_item p, unsigned long x)
{ STOP.k = x;
  ch_map_item q = p->succ; 
  while (q->k != x) q = q->succ;
  if (q != &STOP) return q->i;

  // index x not present, insert it

  if (free == table_end)   
  { // table full: rehash
    rehash();
    if (x == table_size) return table->i;
    p = HASH(x);
   }

  if (p->k == NULLKEY)
  { p->k = x;
    init_inf(p->i);
    return p->i;
   }

  q = free++;
  q->k = x;
  init_inf(q->i);
  q->succ = p->succ;
  p->succ = q;
  return q->i;
}



void ch_map::init_table(int T)
{ table_size = T;
  table_size_1 = T-1;
  table = new ch_map_elem[T + T/2];
  free = table + T;
  table_end = free + T/2;      

  for (ch_map_item p = table; p < free; p++) 
  { p->succ = &STOP; 
    p->k = NULLKEY;
   }
}


#ifdef INSERT
#undef INSERT
#endif

#define INSERT(x,y)                                                        \
{ ch_map_item q = HASH(x);                                                 \
  if (x != NULLKEY && q->k == NULLKEY)                                     \
    { q->k = x;                                                            \
      q->i = y; }                                                          \
  else                                                                     \
   { free->k = x;                                                          \
     free->i = y;                                                          \
     free->succ = q->succ;                                                 \
     q->succ = free++; }                                                   }
                                                                            

void ch_map::rehash()
{ 
  ch_map_item old_table = table;
  ch_map_item old_table_mid = table + table_size;
  ch_map_item old_table_end = table_end;

  init_table(2*table_size);

  ch_map_item p;

  for(p = old_table; p < old_table_mid; p++)
  { unsigned long x = p->k;
    if (x != NULLKEY)
    { ch_map_item q = HASH(x);  
      q->k = x;
      q->i = p->i;
     }
   }

  while (p < old_table_end)
  { unsigned long x = p->k;
    INSERT(x,p->i);
    p++;
   }

  if (table->k == NULLKEY) init_nullkey1();

  delete[] old_table;
}


void ch_map::clear_entries() 
{ for(ch_map_item p = table; p < free; p++)
    if (p->k != NULLKEY || p >= table + table_size) 
    clear_inf(p->i);
 }


void ch_map::clear() 
{ clear_entries();
  delete[] table;
  init_table(def_table_size); 
  init_nullkey1();
}


ch_map::ch_map(const ch_map& D)
{ 
  init_table(D.table_size);

  for(ch_map_item p = D.table; p < D.free; p++) 
  { if (p->k != NULLKEY || p >= D.table + D.table_size)
    { INSERT(p->k,p->i);
      D.copy_inf(p->i);
     }
   }

  if (table->k == NULLKEY)  // init_nullkey1
  { table[0].k = table_size;
    D.init_inf(table[0].i);
   }
}



ch_map& ch_map::operator=(const ch_map& D)
{ 
  clear_entries();
  delete[] table;
  init_table(D.table_size);

  for(ch_map_item p = D.table; p < D.free; p++) 
  { if (p->k != NULLKEY || p >= D.table + D.table_size)
    { INSERT(p->k,p->i);
      copy_inf(p->i);
     }
   }

  if (table->k == NULLKEY) init_nullkey1();

  return *this;
}


