开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
dictionary.h
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：5k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

dictionary.h：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  dictionary.h
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #ifndef LEDA_DICTIONARY_H
  14. #define LEDA_DICTIONARY_H
  16. #include <LEDA/basic.h>    
  19. #define DIC_DEF_IMPL skiplist
  20. #include <LEDA/impl/skiplist.h> 
  21. typedef skiplist_item dic_item;
  23. /*{Manpage {dictionary} {K,I} {Dictionaries}}*/
  25. template <class K, class I> 
  27. class dictionary : public virtual DIC_DEF_IMPL 
  28. {
  29. /*{Mdefinition
  30. An instance $D$ of the parameterized data type name is a collection
  31. of items ($dic_item$). Every item in $D$ contains a key from the linearly
  32. ordered data type $K$, called the key type of $D$, and an information from the
  33. data type $I$, called the information type  of $D$. The number of items in $D$
  34. is called the size of $D$. A dictionary of size zero is called the empty
  35. dictionary. We use $<k,i>$ to denote an item with key $k$ and information
  36. $i$ ($i$ is said to be the information associated with key $k$).  For each
  37. $k in K$ there is at most one $i in I$ with $<k,i> in D$.}*/
  40. int  int_type()              const { return LEDA_INT_TYPE(K); }
  41. int  cmp(GenPtr x, GenPtr y) const { return LEDA_COMPARE(K,x,y); }
  42. int  hash_fct(GenPtr x)      const { return LEDA_HASH(K,x); }
  43. void clear_key(GenPtr& x)    const { LEDA_CLEAR(K,x); }
  44. void clear_inf(GenPtr& x)    const { LEDA_CLEAR(I,x); }
  45. void copy_key(GenPtr& x)     const { LEDA_COPY(K,x); }
  46. void copy_inf(GenPtr& x)     const { LEDA_COPY(I,x); }
  48. public:
  50. /*{Mcreation D }*/
  52. dictionary() {}
  53. /*{Mcreate creates an instance var of type name and initializes it with 
  54.             the empty dictionary.}*/
  57. dictionary(const dictionary<K,I>& D) : DIC_DEF_IMPL(D) {}
  59. dictionary<K,I>& operator=(const dictionary<K,I>& D)
  60. { DIC_DEF_IMPL::operator=(D); return *this; }
  61.          
  62. virtual ~dictionary()   { DIC_DEF_IMPL::clear(); }
  65. /*{Moperations 2 4.2 }*/
  67. virtual K key(dic_item it) const { return LEDA_ACCESS(K,DIC_DEF_IMPL::key(it));}
  69. /*{Mop   returns the key of item $it$.\
  70.   precond $it$ is an item in var.}*/
  72. virtual I inf(dic_item it) const { return LEDA_ACCESS(I,DIC_DEF_IMPL::inf(it));}
  73. /*{Mop     returns the information of item $it$.\
  74.     precond $it$ is an item in var.}*/
  76. virtual int  defined(K k) const 
  77. { return (lookup(k) == nil) ? false : true; }
  79. virtual dic_item insert(K k, I i)
  80. { return DIC_DEF_IMPL::insert(Convert(k),Convert(i)); } 
  81. /*{Mop      associates the information $i$ with the key $k$.
  82.              If there is an item $<k,j>$ in var then $j$ is
  83.              replaced by $i$, else a new item $<k,i>$ is added
  84.              to var. In both cases the item is returned.}*/
  86. virtual dic_item lookup(K k) const
  87. { return DIC_DEF_IMPL::lookup(Convert(k));}
  88. /*{Mop        returns the item with key $k$ (nil if no such
  89.        item exists in var).}*/
  91. virtual I access(K k)  const { return inf(lookup(k));}
  92. /*{Mop       returns the information associated with key $k$.
  93.               precond there is an item with key $k$ in var.}*/
  95. virtual void  del(K k)          { DIC_DEF_IMPL::del(Convert(k)); } 
  96. /*{Mop       deletes the item with key $k$ from var
  97.               (null operation, if no such item exists).}*/
  99. virtual void  del_item(dic_item it) { DIC_DEF_IMPL::del_item(it); } 
  100. /*{Mop       removes item $it$ from var.\
  101.               precond $it$ is an item in var.}*/
  103. virtual void change_inf(dic_item it, I i)
  104. { DIC_DEF_IMPL::change_inf(it,Convert(i)); }
  105. /*{Mopl      makes $i$ the information of item $it$.\
  106.               precond $it$ is an item in var.}*/
  108. virtual void     clear() { DIC_DEF_IMPL::clear(); }
  109. /*{Mop       makes var the empty dictionary.}*/ 
  111. virtual int      size()  const { return DIC_DEF_IMPL::size(); }
  112. /*{Mop       returns the size of var.}*/
  114. virtual bool     empty() const { return (size()==0) ? true : false; }
  115. /*{Mop       returns true if var is empty, false otherwise.}*/
  117. virtual dic_item first_item() const { return DIC_DEF_IMPL::first_item(); }
  118. virtual dic_item next_item(dic_item it) const { return DIC_DEF_IMPL::next_item(it);}
  120. };
  122. /*{Mimplementation
  123. Dictionaries are implemented by randomized search trees cite{AS89}. Operations 
  124. insert, lookup, del_item, del take time $O(log n)$, key, inf, empty, size,
  125. change_inf take time $O(1)$, and clear takes time $O(n)$. Here $n$ is the 
  126. current size of the dictionary. The space requirement is $O(n)$.}*/ 
  129. /*{Mexample
  130. We count the number of occurrences of each string in a sequence of strings.
  132. begingroup
  133. ttbig
  134. {obeyspacesgdef { }}
  135. ttverbatim
  137. #include <LEDA/dictionary.h>
  139. main()
  140. { dictionary<string,int> D;
  141.   string s;
  142.   dic_item it;
  144.   while (cin >> s)
  145.   { it = D.lookup(s);
  146.     if (it==nil) D.insert(s,1);
  147.     else D.change_inf(it,D.inf(it)+1);
  148.   }
  150.   forall_items(it,D) cout << D.key(it) << " : " <<  D.inf(it) << endl;
  152. }
  153. endgroup
  155. }*/
  158. #endif