File: HASHED_DICTIONARY.html

package info (click to toggle)
lisaac 1%3A0.13.1-2
  • links: PTS
  • area: main
  • in suites: lenny
  • size: 15,232 kB
  • ctags: 6,386
  • sloc: ansic: 242,479; xml: 635; lisp: 333; makefile: 119; sh: 73; asm: 38
file content (186 lines) | stat: -rwxr-xr-x 15,722 bytes parent folder | download | duplicates (2) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
 
<!DOCTYPE HTML SYSTEM>
<!-- Generated by Lisaac shorter / html style -->
<html>
<head>
<title>
Lisaac prototype interface
</title>
</head>
<body BGCOLOR="#FFFFFF">

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
<br><br><strong><font color="#A020F0">Section</font></strong> <strong><font color="#A020F0">Header</font></strong>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp +</font></strong> <strong><font color="#0000FF">name</font></strong>    := <a href="HASHED_DICTIONARY.html"><font color="#008000">HASHED_DICTIONARY</font></a>[<font color="#008000">V</font>,<font color="#008000">K</font>];
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">comment</font></strong> :=<font color="#BC8F8F">" Associative memory.\
  \Values of type `V' are stored using Keys of type `K'."</font>;
  
  <br><font FACE="Sans-serif" color="#000000"><B> Efficient implementation of DICTIONARY using `hash_code' on keys.   </B></font>
	      
<br><br><strong><font color="#A020F0">Section</font></strong> <strong><font color="#A020F0">Inherit</font></strong>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">parent_simple_dictionary</font></strong>:<strong><font color="#A020F0">Expanded</font></strong> <a href="SIMPLE_DICTIONARY.html"><font color="#008000">SIMPLE_DICTIONARY</font></a>[<font color="#008000">V</font>,<font color="#008000">K</font>];
  
<br><br><strong><font color="#A020F0">Section</font></strong> <strong><font color="#A020F0">Public</font></strong>
<br><font FACE="Sans-serif" color="#000000"><B> HASHED_DICTIONARY</B></font>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp +</font></strong> <strong><font color="#0000FF">buckets</font></strong>:<a href="NATIVE_ARRAY.html"><font color="#008000">NATIVE_ARRAY</font></a>[<a href="HASHED_DICTIONARY_NODE.html"><font color="#008000">HASHED_DICTIONARY_NODE</font></a>[<font color="#008000">V</font>,<font color="#008000">K</font>]];
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  The `buckets' storage area is the primary hash table of `capacity'</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  elements. To search some key, the first access is done in `buckets'</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  using the remainder of the division of the key `hash_code' by</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  `capacity'. In order to try to avoid clashes, `capacity' is always a</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  prime number (selected using HASH_TABLE_SIZE).</font></strong></em>
  
<br><br><strong><font color="#A020F0">Section</font></strong> <strong><font color="#A020F0">Public</font></strong>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">default_size</font></strong>:<a href="INTEGER.html"><font color="#008000">INTEGER</font></a> := 
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Default size for the storage area in number of items.</font></strong></em>
  
  <br><font FACE="Sans-serif" color="#000000"><B> Counting:</B></font>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp +</font></strong> <strong><font color="#0000FF">capacity</font></strong>:<a href="INTEGER.html"><font color="#008000">INTEGER</font></a>;
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Of the `buckets' storage area.</font></strong></em>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp +</font></strong> <strong><font color="#0000FF">count</font></strong>:<a href="INTEGER.html"><font color="#008000">INTEGER</font></a>;
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Actual `count' of stored elements.</font></strong></em>
  
  <br><font FACE="Sans-serif" color="#000000"><B>  </B></font>
  <br><font FACE="Sans-serif" color="#000000"><B> Basic access:</B></font>
  <br><font FACE="Sans-serif" color="#000000"><B></B></font>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">has</font></strong> k:<font color="#008000">K</font> :<a href="BOOLEAN.html"><font color="#008000">BOOLEAN</font></a> <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Is there a value currently associated with key `k'?</font></strong></em>
    
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">at</font></strong> k:<font color="#008000">K</font> :<font color="#008000">V</font> <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Return the value associated to key `k'.</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  (See also `reference_at' if V is a reference type.)</font></strong></em>
    
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">reference_at</font></strong> k:<font color="#008000">K</font> :<font color="#008000">V</font> <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Return NULL or the value associated with key `k'. Actually, this </font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  feature is useful when the type of values (the type V) is a </font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  reference type, to avoid using `has' just followed by `at' to get </font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  the corresponding value.</font></strong></em>
    
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">fast_has</font></strong> k:<font color="#008000">K</font> :<a href="BOOLEAN.html"><font color="#008000">BOOLEAN</font></a> <-
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">fast_at</font></strong> k:<font color="#008000">K</font> :<font color="#008000">V</font> <-
    
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">fast_reference_at</font></strong> k:<font color="#008000">K</font> :<font color="#008000">V</font> <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Return NULL or the value associated with key `k'. Actually, this </font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  feature is useful when the type of values (the type V) is a </font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  reference type, to avoid using `has' just followed by `at' to get </font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  the corresponding value.</font></strong></em>
    
<br><br><strong><font color="#A020F0">Section</font></strong> <strong><font color="#A020F0">Public</font></strong>  

  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">put</font></strong> v:<font color="#008000">V</font> <strong><font color="#0000FF">to</font></strong> k:<font color="#008000">K</font>  <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Change some existing entry or `add' the new one. If there is</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  as yet no key `k' in the dictionary, enter it with item `v'.</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Otherwise overwrite the item associated with key `k'.</font></strong></em>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">fast_put</font></strong> v:<font color="#008000">V</font> <strong><font color="#0000FF">to</font></strong> k:<font color="#008000">K</font>  <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Change some existing entry or `add' the new one. If there is</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  as yet no key `k' in the dictionary, enter it with item `v'.</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Otherwise overwrite the item associated with key `k'.</font></strong></em>
      
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">add</font></strong> v:<font color="#008000">V</font> <strong><font color="#0000FF">to</font></strong> k:<font color="#008000">K</font> <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  To add a new entry `k' with its associated value `v'. Actually, this</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  is equivalent to call `put', but may run a little bit faster.</font></strong></em>
    
  <br><font FACE="Sans-serif" color="#000000"><B></B></font>
  <br><font FACE="Sans-serif" color="#000000"><B> Removing:</B></font>
  <br><font FACE="Sans-serif" color="#000000"><B></B></font>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">remove</font></strong> k:<font color="#008000">K</font> <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Remove entry `k' (which may exist or not before this call).</font></strong></em>
    
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">fast_remove</font></strong> k:<font color="#008000">K</font> <-
    
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">clear</font></strong> <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Discard all items.</font></strong></em>
    
  <br><font FACE="Sans-serif" color="#000000"><B></B></font>
  <br><font FACE="Sans-serif" color="#000000"><B> To provide iterating facilities:</B></font>
  <br><font FACE="Sans-serif" color="#000000"><B></B></font>
    
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">item</font></strong> i:<a href="INTEGER.html"><font color="#008000">INTEGER</font></a> :<font color="#008000">V</font> <-
      
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">key</font></strong> index:<a href="INTEGER.html"><font color="#008000">INTEGER</font></a> :<font color="#008000">K</font> <-
      
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">key_map_in</font></strong> buffer:<a href="COLLECTION.html"><font color="#008000">COLLECTION</font></a>[<font color="#008000">K</font>] <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Append in `buffer', all available keys (this may be useful to</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  speed up the traversal).</font></strong></em>
      
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">item_map_in</font></strong> buffer:<a href="COLLECTION.html"><font color="#008000">COLLECTION</font></a>[<font color="#008000">V</font>]  <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Append in `buffer', all available items (this may be useful to</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  speed up the traversal).</font></strong></em>
      
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">copy</font></strong> other:<font color="#008000">SELF</font> <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Reinitialize by copying all associations of `other'.</font></strong></em>
    
  <br><font FACE="Sans-serif" color="#000000"><B></B></font>
  <br><font FACE="Sans-serif" color="#000000"><B> Other features:</B></font>
  <br><font FACE="Sans-serif" color="#000000"><B></B></font>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">internal_key</font></strong> k:<font color="#008000">K</font> :<font color="#008000">K</font> <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Retrieve the internal key object which correspond to the existing</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  entry `k' (the one memorized into the `self' dictionary).</font></strong></em>
    
<br><br><strong><font color="#A020F0">Section</font></strong> <strong><font color="#A020F0">Public</font></strong>
  
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">create</font></strong>:<font color="#008000">SELF</font> <-
    
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">make</font></strong> <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  Create an empty dictionary. Internal storage `capacity' of the</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  dictionary is initialized using the `Default_size' value. Then,</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  tuning of needed storage `capacity' is performed automatically</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  according to usage. if you are really sure that your dictionary</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  is always really bigger than `Default_size', you may consider to use</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  `with_capacity' to save some execution time.</font></strong></em>
      
  <br><br><strong><font color="#FF0000">&nbsp &nbsp -</font></strong> <strong><font color="#0000FF">with_capacity</font></strong> medium_size:<a href="INTEGER.html"><font color="#008000">INTEGER</font></a> <-
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  May be used to save some execution time if one is sure that</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  storage size will rapidly become really bigger than `Default_size'.</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  When first `remove' occurs, storage size may naturally become</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  smaller than `medium_size'. Afterall, tuning of storage size is</font></strong></em>
  <br><em><strong><font color="#707070">&nbsp &nbsp &nbsp &nbsp  done automatically according to usage.</font></strong></em>
  		
  <br><font FACE="Sans-serif" color="#000000"><B></B></font>
  <br><font FACE="Sans-serif" color="#000000"><B> Invariant</B></font>
  <br><font FACE="Sans-serif" color="#000000"><B></B></font>
  
<br><font FACE="Sans-serif" color="#000000"><B>  [</B></font>
<br><font FACE="Sans-serif" color="#000000"><B>    -? {capacity > 0};</B></font>
<br><font FACE="Sans-serif" color="#000000"><B>    -? {capacity >= count};</B></font>
<br><font FACE="Sans-serif" color="#000000"><B>    -? {cache_user.in_range (-1) to count};</B></font>
<br><font FACE="Sans-serif" color="#000000"><B>    -? {(cache_user > 0) ->> {cache_node != NULL}};</B></font>
<br><font FACE="Sans-serif" color="#000000"><B>    -? {(cache_user > 0) ->> {cache_buckets.in_range 0 to (capacity - 1)}}</B></font>
<br><font FACE="Sans-serif" color="#000000"><B>  ];</B></font>
  
  
 <br><font FACE="Sans-serif" color="#000000"><B>------------------- OLD -------------------- </B></font>
  
     
</body>
</html>