home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / d2_dicti.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  4.9 KB  |  126 lines
  1. {\magonebf  6.2 Two-dimensional dictionaries (d2\_dictionary)}
  2.  
  3. An instance $D$ of the data type $d2\_dictionary$ is a collection of items 
  4. ($dic2\_item$). Every item in $D$ contains a key from a linearly ordered 
  5. data type $K1$, a key from a linearly ordered data type $K2$, and an 
  6. information from a data type $I$. $K1$ and $K2$ are called the key types 
  7. of $D$, and $I$ is called the information type of $D$. The number
  8. of items in $D$ is called the size of $D$. A two-dimensional dictionary of size
  9. zero is said to be  empty. We use $<k_1,k_2,i>$ to denote the item with first 
  10. key $k_1$, second key $k_2$, and information $i$. For each pair 
  11. $(k_1,k_2) \in K1 \times K2$ there is at most one item $<k_1,k_2,i> \in D$.
  12. Additionally to the normal dictionary operations, the data type $d2\_dictionary$
  13. supports rectangular range queries on $K1\times K2$.
  14.  
  15.  
  16. \bigskip
  17. {\bf 1. Declaration of a two-dimensional dictionary type}
  18.  
  19. \declthree d2\_dictionary K1 K2 I
  20.  
  21. introduces a new data type with name \name\ consisting of all 
  22. two-dimensional dictionaries with key types $K1$ and $K2$ and 
  23. information type $I$. \precond $K1$ and $K2$ are linearly ordered.
  24.  
  25.  
  26. \bigskip
  27. {\bf 2. Creation of a two-dimensional dictionary}
  28.  
  29.  
  30. \create D {}
  31.  
  32. creates an instance \var\ of type \name\ and initializes \var\ to the 
  33. empty dictionary. 
  34.  
  35.  
  36.  
  37. \bigskip
  38. {\bf 3. \operations}
  39.  
  40. \+\cleartabs & \hskip 3truecm & \hskip 5truecm &\cr
  41. \+\op K1               key1 {dic2\_item\ it}  
  42.                             {returns the first key of item $it$.}
  43. \+\nop                      {\precond $it$ is an item in \var.}
  44. \smallskip
  45. \+\op K2               key2 {dic2\_item\ it}  
  46.                             {returns the second key of item $it$.}
  47. \+\nop                      {\precond $it$ is an item in \var.}
  48. \smallskip
  49. \+\op I                inf {dic2\_item\ it}   
  50.                             {returns the information of item $it$.}
  51. \+\nop                      {\precond $it$ is an item in \var.}
  52. \smallskip
  53. \+\op dic2\_item       max\_key1 {}   
  54.                             {returns the item with maximal first key.}
  55. \smallskip
  56. \+\op dic2\_item       max\_key2 {}   
  57.                             {returns the item with maximal second key.}
  58. \smallskip
  59. \+\op dic2\_item       min\_key1 {}   
  60.                             {returns the item with minimal first key.}
  61. \smallskip
  62. \+\op dic2\_item       min\_key2 {}   
  63.                             {returns the item with minimal second key.}
  64.  
  65. \vfill\eject
  66.  
  67. \+\op dic2\_item       insert {K1\ k_1,\ K2\ k_2,\ I\ i}  {}
  68. \+\nop                      {associates the information $i$ with the keys}
  69. \+\nop                      {$k_1$ and $k_2$. If there is an item $<k_1,k_2,j>$}
  70. \+\nop                      {in \var\ then $j$ is replaced by i, else a new }
  71. \+\nop                      {item $<k_1,k_2,i>$ is added to $D$. In both }
  72. \+\nop                      {cases the item is returned.}
  73. \smallskip
  74. \+\op dic2\_item       lookup {K1\ k_1,\ K2\ k_2}  {}
  75. \+\nop                      {returns the item with keys $k_1$ and $k_2$}
  76. \+\nop                      {(nil if no such item exists in \var).}
  77. \smallskip
  78. \+\op list(dic2\_item) range\_search {K1\ a,\ K1\ b,\ K2\ c,\ K2\ d} {}
  79. \+\nop                      {returns the list of all items $<k_1,k_2,i> \in$ \var} 
  80. \+\nop                      {with $a \le k_1 \le b$ and $c \le k_2 \le d$.}
  81. \smallskip
  82. \+\op list(dic2\_item) all\_items {}
  83.                             {returns the list of all items of \var.}
  84. \smallskip
  85. \+\op void             del {K1\ k_1,\ K2\ k_2}         
  86.                             {deletes the item with keys $k_1$ and $k_2$}
  87. \+\nop                      {from \var.}
  88. \smallskip
  89. \+\op void             del\_item {dic2\_item\ it}   
  90.                             {removes item $it$ from \var.}
  91. \+\nop                      {\precond $it$ is an item in \var.}
  92. \smallskip
  93. \+\op void             change\_inf {dic2\_item\ it,\ I\ i} {}
  94. \+\nop                      {makes $i$ the information of item $it$.}
  95. \+\nop                      {\precond $it$ is an item in \var.}
  96. \smallskip
  97. \+\op void             clear {}           
  98.                             {makes \var\ the empty d2\_dictionary.}
  99. \smallskip 
  100. \+\op bool             empty {}           
  101.                             {returns true if \var\ is empty, false otherwise.}
  102. \smallskip 
  103. \+\op int  size {}          
  104.                             {returns the size of \var.}
  105.  
  106.  
  107.  
  108. \bigskip
  109. {\bf 4. Iteration}
  110.  
  111. {\bf forall\_dic2\_items}($i,D$) 
  112. $\{$ ``the items of $D$ are successively assigned to $i$ '' $\}$
  113.  
  114.  
  115.  
  116. \bigskip
  117. {\bf 5. Implementation}
  118.  
  119. Two-dimensional dictionaries are implemented by dynamic two-dimensional range
  120. trees based on BB[$\alpha$] trees. Operations insert, lookup, del\_item, del 
  121. take time $O(\log^2 n)$,  range\_search takes time $O(k + \log^2 n)$, where
  122. $k$ is the size of the returned list, key, inf, empty, size, change\_inf
  123. take time $O(1)$, and clear takes time $O(n\log n)$. Here $n$ is the current 
  124. size of the dictionary. The space requirement is $O(n\log n)$.
  125.  
  126.