/*******************************************************************************
+
+  LEDA 3.5
+
+  _ch_map2.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_map2.h>

//------------------------------------------------------------------------------
//
//  Two-dimensional hashing array with chaining and table doubling
//
//  S. Naeher (1997)
//
//------------------------------------------------------------------------------

#ifdef NULLKEY
#undef NULLKEY
#endif

#define NULLKEY 0xFFFFFFFF


ch_map2::ch_map2(int sz, int n) 
{ 
  shift = 0;
  while (sz >>= 1) shift++;

  if (n < 512)
     init_table(512); 
  else
   { int ts = 1;
     while (ts < n) ts <<= 1;
     init_table(ts);
    }
}


ch_map2_item ch_map2::lookup(ch_map2_item p, unsigned long x, 
                                             unsigned long y) const 
{ ((unsigned long&)STOP.k1) = x;
  ((unsigned long&)STOP.k2) = y;
  while (p->k1 != x || p->k2 != y) p = p->succ;
  return (p == &STOP) ? nil : p;
}


GenPtr& ch_map2::access(ch_map2_item p, unsigned long x, unsigned long y)
{ 
  STOP.k1 = x;
  STOP.k2 = y;
  ch_map2_item q = p->succ; 
  while (q->k1 != x || q->k2 != y) q = q->succ;
  if (q != &STOP) return q->i;


  // index x not present, insert it

  if (free == table_end)   // table full: rehash
  { rehash();
    p = HASH(x,y);
   }

  if (p->k1 == NULLKEY && p->k2 == NULLKEY)
  { p->k1 = x;
    p->k2 = y;
    init_inf(p->i);
    return p->i;
   }

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




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

  for (ch_map2_item p=table; p < free; p++) 
  { p->k1 = NULLKEY;
    p->k2 = NULLKEY;
    p->succ = &STOP;
   }
}


#ifdef INSERT
#undef INSERT
#endif

#define INSERT(x,y,z)                                                     \
{ ch_map2_item q = HASH(x,y);                                             \
  if (q->k1 == NULLKEY && q->k2 == NULLKEY)                               \
    { q->k1 = x;                                                          \
      q->k2 = y;                                                          \
      q->i  = z; }                                                        \
  else                                                                    \
   { free->k1 = x;                                                        \
     free->k2 = y;                                                        \
     free->i  = z;                                                        \
     free->succ = q->succ;                                                \
     q->succ = free++; }                                                  }


void ch_map2::rehash()
{ 
  ch_map2_item old_table = table;
  ch_map2_item old_table_mid = table+table_size;
  ch_map2_item old_table_end = table_end;
  
  //init_table(4*table_size);
  init_table(2*table_size);

  ch_map2_item p;
  for(p = old_table; p < old_table_mid; p++)
  { unsigned long x = p->k1;
    unsigned long y = p->k2;
    if (x != NULLKEY || y != NULLKEY)
    { ch_map2_item q = HASH(x,y);
      q->k1 = x;
      q->k2 = y;
      q->i = p->i;
     }
   }

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

  delete[] old_table;
}


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

  for(ch_map2_item p = D.table; p < D.table_end; p++) 
  { if (p->k1 != NULLKEY || p->k2 != NULLKEY)
    { INSERT(p->k1,p->k2,p->i);
      D.copy_inf(p->i);
     }
   }
}


void ch_map2::clear_entries() 
{ for(ch_map2_item p = table; p < free; p++)
    if (p->k1 != NULLKEY || p->k2 != NULLKEY) clear_inf(p->i);
 }


void ch_map2::clear() 
{ clear_entries();
  delete[] table;
  init_table(512); 
 }


ch_map2& ch_map2::operator=(const ch_map2& D)
{ 
  clear_entries();
  delete[] table;

  init_table(D.table_size);

  for(ch_map2_item p = D.table; p < D.table_end; p++) 
  { if (p->k1 != NULLKEY || p->k2 != NULLKEY)
    { INSERT(p->k1,p->k2,p->i);
      copy_inf(p->i);
     }
   }
  return *this;
}

