/*******************************************************************************
+
+  LEDA 3.5
+
+  d_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_D_ARRAY_H
#define LEDA_D_ARRAY_H

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


//------------------------------------------------------------------------------
// d_array 
//------------------------------------------------------------------------------


/*{\Manpage {d_array} {I,E} {Dictionary Arrays}}*/

#include <LEDA/impl/skiplist.h> 

#define DA_DEF_IMPL skiplist

typedef skiplist_item d_array_item;


template<class I, class E> 

class d_array : public virtual DA_DEF_IMPL 
{

/*{\Mdefinition
An instance $A$ of the parameterized data type |\Mname| (dictionary
array) is an injective mapping from the linearly ordered data type $I$, called
the index type of $A$, to the set of variables of data type $E$, called the
element type of $A$. We use $A(i)$ to denote the variable with index $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 dictionary 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 |h_arrays|, |maps|, and |dictionaries|. }*/


protected: 

E xdef;

int  cmp(GenPtr x, GenPtr y) const { return LEDA_COMPARE(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 }*/

d_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$.}*/

d_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$.}*/


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

d_array(const d_array<I,E>& A) : DA_DEF_IMPL(A) {xdef=A.xdef;}

virtual ~d_array() { clear(); }

/*{\Moperations 2 4 }*/

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

virtual E&  operator[](const I& i) 
{ d_array_item it = DA_DEF_IMPL::lookup(leda_cast(i));
  if (it==nil) 
  { GenPtr p = leda_cast(xdef);
    it=DA_DEF_IMPL::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 (DA_DEF_IMPL::lookup(leda_cast(i))!=nil); }
/*{\Mop      returns true if $i \in \mathit{dom}(A)$ and false otherwise.}*/


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


// iteration

virtual void loop_to_succ(GenPtr& x) const 
   { x = DA_DEF_IMPL::next_item(d_array_item(x)); }


virtual GenPtr forall_defined_test(GenPtr it, I& x) const
{ if (it) x = LEDA_ACCESS(I,key(d_array_item(it)));
  return it;
}

virtual GenPtr forall_loop_test(GenPtr it, E& x) const
{ if (it) x = LEDA_ACCESS(E,inf(d_array_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
Dictionary arrays are implemented by randomized search trees \cite{AS89}. 
Access operations $A[i]$ take time $O(\log \mathit{dom}(A))$.
The space requirement is $O(\mathit{dom}(A))$.}*/
  
/*{\Mexample

{\bf Program 1}:
We use a dictionary array to count the number of occurrences of the elements in a 
sequence of strings.


\begingroup
\ttbig
{\obeyspaces\gdef {\ }}
\ttverbatim

#include <LEDA/d_array.h>

main()
{ 
  d_array<string,int> N(0);
  string s;

  while (cin >> s) N[s]++;

  forall_defined(s,N) cout << s << "  " << N[s] << endl;

}
\endgroup


\bigskip
{\bf Program 2}:
We use a $d\_array\<string,string\>$ to realize an english/german dictionary.
\begingroup
\ttbig
{\obeyspaces\gdef {\ }}
\ttverbatim

#include <LEDA/d_array.h>

main()
{ 
  d_array<string,string> dic;

  dic["hello"] = "hallo";
  dic["world"] = "Welt";
  dic["book"]  = "Buch";
  dic["key"]   = "Schluessel";
  
  string s;
  forall_defined(s,dic) cout << s << "  " << dic[s] << endl;

}
\endgroup


}*/


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

#endif
