ch_map.h

This software was done in part for a textbook on AI I ve written called _The Basis of AI_ (tentative

/*******************************************************************************
+
+  LEDA 3.5
+
+
+  ch_map.h
+
+
+  Copyright (c) 1995, 1996, 1997  by  LEDA Software GmbH
+  Postfach 151101, 66041 Saarbruecken, Germany
+  All rights reserved.
+ 
*******************************************************************************/


#ifndef LEDA_CH_MAP_H
#define LEDA_CH_MAP_H

#include <LEDA/basic.h>
 

//------------------------------------------------------------------------------
// class ch_map_elem  
//------------------------------------------------------------------------------

class __exportC ch_map_elem 
{
  friend class __exportC ch_map;

  unsigned long    k;
  GenPtr           i;
  ch_map_elem*  succ;
};

typedef ch_map_elem*  ch_map_item;


//--------------------------------------------------------------------
// class ch_map
//--------------------------------------------------------------------

class __exportC ch_map 
{

   ch_map_elem STOP;

   ch_map_elem* table;
   ch_map_elem* table_end;
   ch_map_elem* free;

   int table_size;           
   int table_size_1;           
   int def_table_size;           

   virtual void clear_inf(GenPtr&)  const { }
   virtual void copy_inf(GenPtr&)   const { }
   virtual void init_inf(GenPtr&)   const { }

   ch_map_elem*  HASH(unsigned long x)  const
   { return table + (x & table_size_1);  }

   void init_table(int);
   void rehash();

   GenPtr& access(ch_map_item, unsigned long);

   protected:

   GenPtr&  inf(ch_map_item p) const { return p->i; }

   void init_nullkey1()
   { table->k = table_size;
     init_inf(table->i);
   }

   void clear_entries();


   GenPtr& access(unsigned long);
   ch_map_item lookup(unsigned long) const;

   void clear();

   ch_map(int=-1); 
   ch_map(const ch_map&);
   ch_map& operator=(const ch_map&);
   virtual ~ch_map() { delete[] table; }

   // not defined
   ch_map_item first_item() const { return 0; }
   ch_map_item next_item(ch_map_item) const { return 0; }

};


inline GenPtr& ch_map::access(unsigned long x)
{ ch_map_item p = HASH(x);

  if ( p->k == x ) return p->i;
  else
  { if ( p->k == 0) // NULLKEY
    { p->k = x;
      init_inf(p->i);
      return p->i;
    }
    else 
      return access(p,x);
  }
}


#endif