/*******************************************************************************
+
+  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 350003
#include <LEDA/REDEFINE_NAMES.h>
#endif

#include <LEDA/d_array.h>

//------------------------------------------------------------------------------
//
// Dictionary arrays with implementation parameter:
//
//   _d_array<I,E,impl> 
//
//------------------------------------------------------------------------------

/*{\Manpage {_d_array} {I,E,impl} {Dictionary Arrays with Implementation Parameter} }*/

/*{\Mdefinition
An instance of type |\Mname| is a dictionary array implemented by data type 
$impl$. $impl$ must be one of the dictionary implementations listed in
section \ref{Implementations Dictionaries} or a user defined data structure
fulfilling the specification given in section \ref{User Implementations
Dictionaries}. Note that depending on the actual implementation $impl$
the index type $I$ must either be linearly ordered or hashed.
}*/
  
/*{\Mtext
{\bf Example}\\
Using a dictionary array implemented by hashing with chaining  ($ch\_hash$)
to count the number of occurences of the elements in a sequence of strings.
\begingroup
\ttbig
{\obeyspaces\gdef {\ }}
\ttverbatim

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

//we first have to define a hash function for strings

int Hash(const string& x) { return (x.length() > 0) ? x[0] : 0; }

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

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

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

}
\endgroup

}*/


template <class I, class E, class impl> 

#if defined(__NO_TEMPLATE_ARG_BASE__)
class _d_array : public d_array<I,E> 
{ impl* dummy; 
  public: 
 _d_array() {}
 _d_array(E) {}
};
#else

class _d_array : private virtual impl, public d_array<I,E>
{

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); }
void print_key(GenPtr x)     const { LEDA_PRINT(I,x,cout); }
void print_inf(GenPtr x)     const { LEDA_PRINT(E,x,cout); }

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

public:


const E&  operator[](const I& i)  const
{ d_array_item it=(d_array_item)impl::lookup(leda_cast(i));
  return (it==nil) ? xdef : LEDA_CONST_ACCESS(E,impl::inf(impl::item(it))); 
}

E& operator[](const I& y)
{ d_array_item i=(d_array_item)impl::lookup(leda_cast(y));
  if (i==nil) i=(d_array_item)impl::insert(leda_cast(y),leda_cast(xdef));
  return LEDA_ACCESS(E,impl::inf(impl::item(i)));
}

bool defined(const I& y) const
{ return (impl::lookup(leda_cast(y))!=nil); }

void undefine(const I& y) { impl::del(leda_cast(y)); }


// iteration

 
GenPtr first_item() const { return impl::first_item(); }                    
 
void loop_to_succ(GenPtr& x) const { x = impl::next_item(impl::item(x)); }

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

// for backward compatibility (forall_defined)

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


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

 _d_array() {}
 _d_array(E i) { xdef=i; }
 _d_array(const _d_array<I,E,impl>& A) : impl(A) { xdef=A.xdef; }
~_d_array() { impl::clear(); } 


};

#endif


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

#endif
