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

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

数值算法/人工智能

开发平台：

MultiPlatform

h_array.h：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  h_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_H_ARRAY_H
  14. #define LEDA_H_ARRAY_H
  16. //------------------------------------------------------------------------------
  17. // h_array  
  18. //------------------------------------------------------------------------------ 
  19. #include <LEDA/basic.h> 
  20. #include <LEDA/impl/ch_array.h> 
  23. /*{Manpage {h_array} {I,E} {Hashing Arrays} }*/
  25. template<class I, class E>
  27. class h_array : private ch_array {
  29. /*{Mdefinition
  30. An instance $A$ of the parameterized data type name (hashing array)
  31. is an injective mapping from a hashed data type $I$ (cf. section 
  32. ref{Hashed Types}), called the index type of $A$, to the set of variables 
  33. of arbitrary type $E$, called the element type of $A$. We use $A(i)$ to 
  34. denote the variable indexed by $i$.}*/
  36.  E X;
  38.  int  int_type()           const { return LEDA_INT_TYPE(I); }
  39.  int  hash_fct(GenPtr x)   const { return LEDA_HASH(I,x); }
  40.  void copy_inf(GenPtr& x)  const { LEDA_COPY(E,x);  }
  41.  void clear_inf(GenPtr& x) const { LEDA_CLEAR(E,x); }
  42.  void init_inf(GenPtr& x)  const { x = Copy(X); }
  45.  public:
  47. /*{Mcreation A }*/
  50. h_array(E x, int sz) : ch_array(sz) { X = x; }
  52. h_array(E x) : ch_array(1) { X = x; }
  54. /*{Mcreate 
  55. creates an injective function $a$ from $I$ to the set of unused variables of
  56. type $E$, assigns $x$ to all variables in the range of $a$ and initializes $A$
  57. with $a$. }*/
  58.  
  59.  h_array() { }
  60.  h_array(const h_array<I,E>& A): ch_array((ch_array&)A) { X = A.X; }
  61. ~h_array() { }
  65. /*{Moperations 2 4.5 }*/
  67. E& operator[](I i) { return LEDA_ACCESS(E,access(Convert(i))); }
  68. /*{Marrop        returns the variable $A(i)$}*/
  70. E operator[](I i) const { return LEDA_ACCESS(E,access(Convert(i))); }
  72. bool defined(I i) const { return (lookup(Convert(i)) != nil); }
  73. /*{Mop      returns true if $i in dom(A)$, false otherwise; here
  74.      $dom(A)$ is the set of all $iin I$ for which $A[i]$ has
  75.      already been executed.}*/
  77. // iteration
  79. ch_array_item first_item() const { return ch_array::first_item(); }
  81. void loop_to_succ(GenPtr& x) const 
  82. { x = ch_array::next_item(*(ch_array_item*)&x); }
  84. GenPtr forall_loop_test(GenPtr it, E& x) const
  85. { if (it) x = LEDA_ACCESS(E,ch_array::inf(ch_array_item(it)));
  86.   return it;
  87. }
  89. GenPtr forall_defined_test(GenPtr it, I& x) const
  90. { if (it) x = LEDA_ACCESS(I,ch_array::key(ch_array_item(it)));
  91.   return it;
  92. }
  94. };
  97. /*{Mtext
  98. bigskip
  99. {bf forall_defined}($i,A$) 
  100. ${$ ``the elements from $dom(A)$ are successively assigned to $i$'' $}$ }*/
  103. /*{Mimplementation
  104. Hashing arrays are implemented by hashing with chaining. Access operations 
  105. take expected time $O(1)$. In many cases, hashing arrays are more efficient 
  106. than dictionary arrays (cf. ref{Dictionary Arrays}).}*/
  108. #endif