/*******************************************************************************
+
+  LEDA 3.5
+
+  map.h
+
+  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.
+ 
*******************************************************************************/
#ifndef LEDA_MAP_H
#define LEDA_MAP_H

#if !defined(LEDA_ROOT_INCL_ID)
#define LEDA_ROOT_INCL_ID 350071
#include <LEDA/REDEFINE_NAMES.h>
#endif

//------------------------------------------------------------------------------
// map  
//------------------------------------------------------------------------------ 
#include <LEDA/impl/ch_map.h> 

#if defined(__MICROSOFTC__)
#pragma warning(disable:4172)
#endif


/*{\Manpage {map} {I,E} {Maps}}*/

template<class I, class E>

class map : private ch_map {
 
/*{\Mdefinition
An instance $M$ of the parameterized data type |\Mname| is an injective 
mapping from the data type $I$, called the index type of $M$,
to the set of variables of data type $E$, called the element type of $M$.
$I$ must be a pointer, item, or handle type or the type int. We use
$M(i)$ to denote the variable indexed by $i$. All variables are initialized to |xdef|
(which is specified in the constructor).

Related data types are |d_arrays|, |h_arrays|, and |dictionaries|. }*/



 E xdef;

 void copy_inf(GenPtr& x)   const { LEDA_COPY(E,x);  }
 void clear_inf(GenPtr& x)  const { LEDA_CLEAR(E,x); }
 void init_inf(GenPtr& x)   const { x = leda_copy((E&)xdef); }

 public:

/*{\Mcreation M }*/

map()  { init_nullkey1(); }
/*{\Mcreate 
creates an injective function $m$ from $I$ to the set of unused variables of
type $E$, sets |xdef| to the default value of type |E| (if |E| has no default 
value then |xdef| is an unspecifed element of |E|), and 
initializes $M$ with $m$.}*/

map(E x,int table_sz) : ch_map(table_sz), xdef (x) { init_nullkey1(); }

map(E x) : xdef(x) { init_nullkey1(); }
/*{\Mcreate 
creates an injective function $m$ from $I$ to the set of unused variables of
type $E$, sets |xdef| to |x|, and initializes $M$
with $m$.}*/

 map<I,E>& operator=(const map<I,E>& M) 
 { ch_map::operator=((ch_map&)M);
   return *this;
  }
 map(const map<I,E>& M): ch_map((ch_map&)M), xdef(M.xdef) {}
~map() { clear_entries(); }

 
/*{\Moperations 2 4.5 }*/


const E& operator[](const I& i) const 
{ ch_map_item p = lookup(ID_Number(i)); 
  if (p) return LEDA_ACCESS(E,inf(p));
  else return xdef;
 }

 
E& operator[](const I& i) { return LEDA_ACCESS(E,access(ID_Number(i))); }
/*{\Marrop        returns the variable $M(i)$.}*/
 
 
bool defined(const I& i) const { return lookup(ID_Number(i)) != nil; }
/*{\Mop      returns true if $A[i] \not= |xdef|$.}*/
 
};


/*{\Mimplementation
Maps are implemented by hashing with chaining and table doubling. 
Access operations |M[i]| take expected time $O(1)$. }*/
 


#if LEDA_ROOT_INCL_ID == 350071
#undef LEDA_ROOT_INCL_ID
#include <LEDA/UNDEFINE_NAMES.h>
#endif


#endif


