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


#include <LEDA/basic.h>    

#include <LEDA/impl/skiplist.h> 
#define DIC_DEF_IMPL skiplist
typedef skiplist_item dic_item;

/*{\Manpage {dictionary} {K,I} {Dictionaries}}*/

template <class K, class I> 

class dictionary : public virtual DIC_DEF_IMPL 
{


/*{\Mdefinition
An instance $D$ of the parameterized data type |\Mname| is a collection
of items ($dic\_item$). Every item in $D$ contains a key from the linearly
ordered data type $K$, called the key type of $D$, and an information from the
data type $I$, called the information type  of $D$. The number of items in $D$
is called the size of $D$. A dictionary of size zero is called the empty
dictionary. We use $\<k,i\>$ to denote an item with key $k$ and information
$i$ ($i$ is said to be the information associated with key $k$).  For each
$k \in K$ there is at most one $i \in I$ with $\<k,i\> \in D$.}*/


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

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

typedef dic_item item;
typedef K key_type;
typedef I inf_type;

/*{\Mcreation D }*/

dictionary() {}
/*{\Mcreate creates an instance |\Mvar| of type |\Mname| and initializes it with 
            the empty dictionary.}*/


dictionary(const dictionary<K,I>& D) : DIC_DEF_IMPL(D) {}

dictionary<K,I>& operator=(const dictionary<K,I>& D)
{ DIC_DEF_IMPL::operator=(D); return *this; }
         
virtual ~dictionary()   { DIC_DEF_IMPL::clear(); }


/*{\Moperations 2 4.2 }*/

virtual K key(dic_item it) const 
{ return LEDA_ACCESS(K,DIC_DEF_IMPL::key(it));}

/*{\Mop   returns the key of item $it$.\\
	  \precond $it$ is an item in |\Mvar|.}*/

virtual I  inf(dic_item it) const
{ return LEDA_ACCESS(I,DIC_DEF_IMPL::inf(it));}
/*{\Mop     returns the information of item $it$.\\
            \precond $it$ is an item in |\Mvar|.}*/
 

/*{\Moptions nextwarning=no}*/
virtual const I& operator[](dic_item it)  const
{ return LEDA_CONST_ACCESS(I,DIC_DEF_IMPL::inf(it));}

virtual I& operator[](dic_item it) 
{ return LEDA_ACCESS(I,DIC_DEF_IMPL::inf(it));}
/*{\Marrop  returns a reference to the information of item $it$.\\
            \precond $it$ is an item in |\Mvar|.}*/
 

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

virtual dic_item insert(const K& k, const I& i)
{ return DIC_DEF_IMPL::insert(leda_cast(k),leda_cast(i)); } 
/*{\Mop      associates the information $i$ with the key $k$.
             If there is an item $\<k,j\>$ in |\Mvar| then $j$ is
             replaced by $i$, else a new item $\<k,i\>$ is added
       	     to |\Mvar|. In both cases the item is returned.}*/

virtual dic_item lookup(const K& k) const
{ return DIC_DEF_IMPL::lookup(leda_cast(k));}
/*{\Mop        returns the item with key $k$ (nil if no such
	       item exists in \Mvar).}*/

virtual I access(const K& k)  const { return inf(lookup(k));}
/*{\Mop       returns the information associated with key $k$.
              \precond there is an item with key $k$ in |\Mvar|.}*/

virtual void  del(const K& k)          { DIC_DEF_IMPL::del(leda_cast(k)); } 
/*{\Mop       deletes the item with key $k$ from |\Mvar|
              (null operation, if no such item exists).}*/

virtual void  del_item(dic_item it) { DIC_DEF_IMPL::del_item(it); } 
/*{\Mop       removes item $it$ from |\Mvar|.\\
              \precond $it$ is an item in |\Mvar|.}*/

virtual void change_inf(dic_item it, const I& i)
{ DIC_DEF_IMPL::change_inf(it,leda_cast(i)); }
/*{\Mopl      makes $i$ the information of item $it$.\\
              \precond $it$ is an item in |\Mvar|.}*/

virtual void     clear() { DIC_DEF_IMPL::clear(); }
/*{\Mop       makes |\Mvar| the empty dictionary.}*/ 

virtual int      size()  const { return DIC_DEF_IMPL::size(); }
/*{\Mop       returns the size of |\Mvar|.}*/

virtual bool     empty() const { return (size()==0) ? true : false; }
/*{\Mop       returns true if |\Mvar| is empty, false otherwise.}*/

virtual dic_item first_item() const { return DIC_DEF_IMPL::first_item(); }
virtual dic_item next_item(dic_item it) const { return DIC_DEF_IMPL::next_item(it);}

/*
typedef dictionary<K,I> this_type;

STL_ITERATORS(this_type,dic_item,I)
*/

};

/*{\Mimplementation
Dictionaries are implemented by randomized search trees \cite{AS89}. Operations 
insert, lookup, del\_item, del take time $O(\log n)$, key, inf, empty, size,
change\_inf take time $O(1)$, and clear takes time $O(n)$. Here $n$ is the 
current size of the dictionary. The space requirement is $O(n)$.}*/ 


/*{\Mexample
We count the number of occurrences of each string in a sequence of strings.

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

#include <LEDA/dictionary.h>

main()
{ dictionary<string,int> 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

}*/



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

#endif
