/*******************************************************************************
+
+  LEDA 3.5
+
+  h_array.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_H_ARRAY_H
#define LEDA_H_ARRAY_H

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

//----------------------------------------------------------------
// h_array  
//----------------------------------------------------------------

#include <LEDA/basic.h> 
#include <LEDA/impl/ch_hash.h> 


/*{\Manpage {h_array} {I,E} {Hashing Arrays} }*/

template<class I, class E>

class h_array : private ch_hash {

/*{\Mdefinition
An instance $A$ of the parameterized data type |\Mname| (hashing array)
is an injective mapping from a hashed data type $I$ (cf. section 
\ref{Hashed Types}), called the index type of $A$, to the set of variables 
of arbitrary type $E$, called the element type of $A$. We use $A(i)$ to 
denote the variable indexed by $i$ and  we use $\mathit{dom}(A)$ to denote 
the set of ``used indices''. This set is empty at the time of creation and 
is modified by array accesses. Each hashing array has an associated default 
value |xdef|. The variable $A(i)$ has value |xdef| for all $i \not\in dom(A)$.

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

protected: 

E xdef;

bool equal_key(GenPtr x, GenPtr y) const { return LEDA_EQUAL(I,x,y); }

int  hash_fct(GenPtr x)      const { return LEDA_HASH(I,x);    }
void clear_key(GenPtr& x)    const { LEDA_CLEAR(I,x); }
void clear_inf(GenPtr& x)    const { LEDA_CLEAR(E,x); }
void copy_key(GenPtr& x)     const { LEDA_COPY(I,x);  }
void copy_inf(GenPtr& x)     const { LEDA_COPY(E,x);  }

int  key_type_id() const { return LEDA_TYPE_ID(I); }

public:

/*{\Mcreation A }*/

h_array()        { }
/*{\Mcreate 
creates an injective function $a$ 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| stays undefined) and |dom(A)| to the empty set, and 
initializes $A$ with $a$.}*/

h_array(E x) : xdef(x) {}
/*{\Mcreate 
creates an injective function $a$ from $I$ to the set of unused variables of
type $E$, sets |xdef| to |x| and |dom(A)| to the empty set, and initializes $A$
with $a$.}*/


h_array<I,E>& operator=(const h_array<I,E>& A)
{ ch_hash::operator=(A); xdef=A.xdef; return *this; }

h_array(const h_array<I,E>& A) : ch_hash(A),xdef(A.xdef) {}


virtual ~h_array() { clear(); }   


/*{\Moperations 2 4 }*/

virtual const E&  operator[](const I& i)  const
{ ch_hash_item it = ch_hash::lookup(leda_cast(i));
  if (it) return LEDA_CONST_ACCESS(E,inf(it));
  else return xdef;
}

virtual E&  operator[](const I& i) 
{ ch_hash_item it = ch_hash::lookup(leda_cast(i));
  if (it == nil) 
  { GenPtr p = leda_cast(xdef);
    it = ch_hash::fast_insert(leda_cast(i),p);
   }
  return LEDA_ACCESS(E,inf(it)); 
}
/*{\Marrop    returns the variable $A(i)$.}*/

virtual bool defined(const I& i)  const 
{ return (ch_hash::lookup(leda_cast(i)) != nil); }
/*{\Mop      returns true if $i \in \mathit{dom}(A)$ and false otherwise.}*/



virtual void undefine(const I& i)
{ ch_hash::del(leda_cast(i)); }
/*{\Mop      removes $i$ from $\mathit{dom}(A)$ and sets |A(i)| to |xdef|. }*/


ch_hash_item first_item() const { return ch_hash::first_item(); }

void loop_to_succ(GenPtr& x) const 
{ x = ch_hash::next_item(*(ch_hash_item*)&x); }

GenPtr forall_loop_test(GenPtr it, E& x) const
{ if (it) x = LEDA_ACCESS(E,ch_hash::inf(ch_hash_item(it)));
  return it;
}

GenPtr forall_defined_test(GenPtr it, I& x) const
{ if (it) x = LEDA_ACCESS(I,ch_hash::key(ch_hash_item(it)));
  return it;
}

/*{\Mtext     
\bigskip
{\bf Iteration} }*/

/*{\Mtext
{\bf forall\_defined}($i,A$) 
$\{$ ``the elements from $\mathit{dom}(A)$ are successively assigned to $i$'' $\}$ 
}*/

/*{\Mtext
{\bf forall}($x,A$) 
$\{$ ``for all $i \in \mathit{dom}(A)$ the entries $A[i]$ are 
successively assigned to $x$'' $\}$ 
}*/


};

/*{\Mimplementation
Hashing arrays are implemented by hashing with chaining. Access operations 
take expected time $O(1)$. In many cases, hashing arrays are more efficient 
than dictionary arrays (cf. \ref{Dictionary Arrays}).}*/

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

#endif

