Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > View Code
d_array.h
Package: leda.tar.gz　[view]
Upload User: gzelex
Upload Date: 2007-01-07
Package Size: 707k
Code Size: 4k
Category:

Mathimatics-Numerical algorithms

Development Platform:

MultiPlatform

d_array.h：Code Content
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  d_array.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_D_ARRAY_H
  14. #define LEDA_D_ARRAY_H
  16. //------------------------------------------------------------------------------
  17. // d_array 
  18. //------------------------------------------------------------------------------
  20. #include <LEDA/impl/skiplist.h> 
  22. /*{Manpage {d_array} {I,E} {Dictionary Arrays}}*/
  25. #define DA_DEF_IMPL skiplist
  26. typedef skiplist_item d_array_item;
  28. template<class I, class E> 
  30. class d_array : public virtual DA_DEF_IMPL 
  31. {
  32. /*{Mdefinition
  33. An instance $A$ of the parameterized data type name (dictionary
  34. array) is an injective mapping from the linearly ordered data type $I$, called
  35. the index type of $A$, to the set of variables of data type $E$, called the
  36. element type of $A$. We use $A(i)$ to denote the variable with index $i$.}*/
  38. E init;
  40. int  cmp(GenPtr x, GenPtr y) const { return LEDA_COMPARE(I,x,y); }
  41. /*
  42. int  hash_fct(GenPtr x)      const { return LEDA_HASH(I,x); }
  43. */
  44. void clear_key(GenPtr& x)    const { LEDA_CLEAR(I,x); }
  45. void clear_inf(GenPtr& x)    const { LEDA_CLEAR(E,x); }
  46. void copy_key(GenPtr& x)     const { LEDA_COPY(I,x);  }
  47. void copy_inf(GenPtr& x)     const { LEDA_COPY(E,x);  }
  48. int  int_type()              const { return LEDA_INT_TYPE(I); }
  50. public:
  52. /*{Mcreation A }*/
  54. d_array()        { }
  56. d_array(E x) { init=x; }
  57. /*{Mcreate 
  58. creates an injective function $a$ from $I$ to the set of unused variables of
  59. type $E$, assigns $x$ to all variables in the range of $a$ and initializes $A$
  60. with $a$.}*/
  63. d_array<I,E>& operator=(const d_array<I,E>& A)
  64. { DA_DEF_IMPL::operator=(A); init=A.init; return *this; }
  66. d_array(const d_array<I,E>& A) : DA_DEF_IMPL(A) {init=A.init;}
  68. virtual ~d_array() { clear(); }
  70. /*{Moperations 2 4 }*/
  72. virtual E&  operator[](const I& i) 
  73. { d_array_item it=DA_DEF_IMPL::lookup(Convert(i));
  74.   if (it==nil) 
  75.   { GenPtr p = Convert(init);
  76.     it=DA_DEF_IMPL::insert(Convert(i),p);
  77.    }
  78.   return LEDA_ACCESS(E,info(it)); 
  79. }
  80. /*{Marrop    returns the variable $A(i)$.}*/
  83. virtual bool defined(I i)  const 
  84. { return (DA_DEF_IMPL::lookup(Convert(i))!=nil); }
  85. /*{Mop      returns true if $i in dom(A)$, false otherwise; here
  86.              $dom(A)$ is the set of all $iin I$ for which $A[i]$ has
  87.              already been executed.}*/
  90. virtual void undefine(I i)
  91. { DA_DEF_IMPL::del(Convert(i)); }
  92. /*{Mop      removes $i$ from $dom(A)$. } */
  95. // iteration
  97. virtual void loop_to_succ(GenPtr& x) const 
  98.    { x = DA_DEF_IMPL::next_item(d_array_item(x)); }
  101. virtual GenPtr forall_defined_test(GenPtr it, I& x) const
  102. { if (it) x = LEDA_ACCESS(I,key(d_array_item(it)));
  103.   return it;
  104. }
  106. virtual GenPtr forall_loop_test(GenPtr it, E& x) const
  107. { if (it) x = LEDA_ACCESS(E,inf(d_array_item(it)));
  108.   return it;
  109. }
  111. #if defined(__ELSE_SCOPE_BUG__)
  112. GenPtr forall_loop_item;
  113. GenPtr& Forall_Loop_Item() const { return (GenPtr&)forall_loop_item; }
  114. #endif
  116. };
  118. /*{Mtext     
  119. bigskip
  120. {bf Iteration} }*/
  123. /*{Mtext
  124. {bf forall_defined}($i,A$) 
  125. ${$ ``the elements from $dom(A)$ are successively assigned to $i$'' $}$ }*/
  127. /*{Mtext
  128. {bf forall}($x,A$) 
  129. ${$ ``for all $i in dom(A)$ the entries $A[i]$ are successively assigned to $x$'' $}$ }*/
  133. /*{Mimplementation
  134. Dictionary arrays are implemented by randomized search trees cite{AS89}. 
  135. Access operations $A[i]$ take time $O(log dom(A))$.
  136. The space requirement is $O(dom(A))$.}*/
  137.   
  138. /*{Mexample
  140. {bf Program 1}:
  141. We use a dictionary array to count the number of occurrences of the elements in a 
  142. sequence of strings.
  145. begingroup
  146. ttbig
  147. {obeyspacesgdef { }}
  148. ttverbatim
  150. #include <LEDA/d_array.h>
  152. main()
  153. { 
  154.   d_array<string,int> N(0);
  155.   string s;
  157.   while (cin >> s) N[s]++;
  159.   forall_defined(s,N) cout << s << "  " << N[s] << endl;
  161. }
  162. endgroup
  165. bigskip
  166. {bf Program 2}:
  167. We use a $d_array<string,string>$ to realize an english/german dictionary.
  168. begingroup
  169. ttbig
  170. {obeyspacesgdef { }}
  171. ttverbatim
  173. #include <LEDA/d_array.h>
  175. main()
  176. { 
  177.   d_array<string,string> dic;
  179.   dic["hello"] = "hallo";
  180.   dic["world"] = "Welt";
  181.   dic["book"]  = "Buch";
  182.   dic["key"]   = "Schluessel";
  183.   
  184.   string s;
  185.   forall_defined(s,dic) cout << s << "  " << dic[s] << endl;
  187. }
  188. endgroup
  191. }*/
  193. #endif