/*******************************************************************************
+
+  LEDA 3.5
+
+  _dictionary.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_DICTIONARY_H
#define __LEDA_DICTIONARY_H

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

#include <LEDA/dictionary.h>

//------------------------------------------------------------------------------
//
// Dictionaries with implementation parameter:
//
//   _dictionary<keytype,inftype,dic_impl> 
//
//------------------------------------------------------------------------------

/*{\Manpage {_dictionary} {K,I,impl} {Dictionaries with Implementation Parameter} }*/

/*{\Mdefinition
An instance of type |\Mname| is a dictionary 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 key type $K$ must either be linearly ordered or hashed.
}*/

/*{\Mtext
{\bf Example}\\
Using a dictionary implemented by skiplists to count the number of 
occurrences of the elements in a sequence of strings.
\begingroup
\ttbig
{\obeyspaces\gdef {\ }}
\ttverbatim

#include <LEDA/_dictionary.h>
#include <LEDA/impl/skiplist.h>

main()
{
  _dictionary<string,int,skiplist> D;
  string s;
  dic_item it;

  while (cin >> s)
  { it = D.lookup(s);
    if (it==nil) D.insert(s,1);
    else D.change_inf(it,D.inf(it)+1);
  }

  forall_items(it,D) cout << D.key(it) << " : " <<  D.inf(it) << endl;

}
\endgroup
}*/


template <class K, class I, class impl> 

#if defined(__NO_TEMPLATE_ARG_BASE__)
class _dictionary : public dictionary<K,I> { impl* dummy; };
#else

class _dictionary : private virtual impl, public dictionary<K,I>
{


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

int  cmp(GenPtr x, GenPtr y) const { return LEDA_COMPARE(K,x,y); }
int  hash_fct(GenPtr x)      const { return LEDA_HASH(K,x); }
void clear_key(GenPtr& x)    const { LEDA_CLEAR(K,x); }
void clear_inf(GenPtr& x)    const { LEDA_CLEAR(I,x); }
void copy_key(GenPtr& x)     const { LEDA_COPY(K,x); }
void copy_inf(GenPtr& x)     const { LEDA_COPY(I,x); }
void print_key(GenPtr x)     const { LEDA_PRINT(K,x,cout); }
void print_inf(GenPtr x)     const { LEDA_PRINT(I,x,cout); }

public:

dic_item lookup(const K& x) const 
{ return dic_item(impl::lookup(leda_cast(x))); }

int defined(const K& x) const { return (lookup(x)==nil) ? false : true; }

void change_inf(dic_item it, const I& i)
{ impl::change_inf(impl::item(it),leda_cast(i));}

dic_item insert(const K& x, const I& y)
{ return dic_item(impl::insert(leda_cast(x),leda_cast(y))); }

void del(const K& x) { impl::del(leda_cast(x)); }
void del_item(dic_item it) { impl::del_item(impl::item(it)); }

K key(dic_item it) const 
{ return LEDA_ACCESS(K,impl::key(impl::item(it))); }

I inf(dic_item it) const 
{ return LEDA_ACCESS(I,impl::inf(impl::item(it)));}

const I& operator[](dic_item it)  const
{ return LEDA_CONST_ACCESS(I,impl::inf(impl::item(it)));}

I& operator[](dic_item it)
{ return LEDA_ACCESS(I,impl::inf(impl::item(it)));}

int  size() const { return impl::size(); }
bool empty() const { return (size()==0) ? true : false; }
void clear() { impl::clear(); }

dic_item first_item() const { return dic_item(impl::first_item()); }
dic_item next_item(dic_item it) const 
{ return dic_item(impl::next_item(impl::item(it))); }

_dictionary<K,I,impl>& operator=(const _dictionary<K,I,impl>& D)
{ impl::operator=(D); return *this; }

 _dictionary() {}
 _dictionary(const _dictionary<K,I,impl>& D) : impl(D) {}
~_dictionary() { impl::clear(); }


};

#endif


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

