Mercurial > repos > tabletprog
annotate modules/dict.tp @ 250:c58e17f5c0f6
Added hash dictionary to dict module
author | Michael Pavone <pavone@retrodev.com> |
---|---|
date | Wed, 09 Apr 2014 22:55:10 -0700 |
parents | 96fdc5b37ceb |
children | 697c2c562af2 |
rev | line source |
---|---|
202
cea671c4056c
Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents:
192
diff
changeset
|
1 { |
cea671c4056c
Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents:
192
diff
changeset
|
2 linearWithEls <- :els { |
74
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
3 key:val <- :k v { |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
4 #{ |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
5 key <- k |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
6 val <- v |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
7 } |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
8 } |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
9 find <- :tofind { |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
10 idx <- 0 |
164 | 11 while: { |
12 if: idx < (els length) { | |
74
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
13 ((els get: idx) key: ) != tofind |
164 | 14 } else: {false} |
74
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
15 } do: { |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
16 idx <- idx + 1 |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
17 } |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
18 if: idx < (els length) {idx} else: {-1} |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
19 } |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
20 #{ |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
21 set <- :k v { |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
22 idx <- find: k |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
23 if: idx < 0 { |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
24 els append: (key: k val: v) |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
25 } else: { |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
26 (els get: idx) val!: v |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
27 } |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
28 self |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
29 } |
164 | 30 |
74
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
31 get <- :k { |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
32 get: k withDefault: false |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
33 } |
164 | 34 |
74
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
35 get:withDefault <- :k default { |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
36 idx <- find: k |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
37 if: idx < 0 { |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
38 default |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
39 } else: { |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
40 (els get: idx) val |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
41 } |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
42 } |
164 | 43 |
44 get:elseSet <- :k :else { | |
248
96fdc5b37ceb
Added get:else method to linear dict
Michael Pavone <pavone@retrodev.com>
parents:
202
diff
changeset
|
45 get: k else: { |
164 | 46 v <- else: |
47 els append: (key: k val: v) | |
48 v | |
248
96fdc5b37ceb
Added get:else method to linear dict
Michael Pavone <pavone@retrodev.com>
parents:
202
diff
changeset
|
49 } |
96fdc5b37ceb
Added get:else method to linear dict
Michael Pavone <pavone@retrodev.com>
parents:
202
diff
changeset
|
50 } |
96fdc5b37ceb
Added get:else method to linear dict
Michael Pavone <pavone@retrodev.com>
parents:
202
diff
changeset
|
51 |
96fdc5b37ceb
Added get:else method to linear dict
Michael Pavone <pavone@retrodev.com>
parents:
202
diff
changeset
|
52 get:else <- :k :else { |
96fdc5b37ceb
Added get:else method to linear dict
Michael Pavone <pavone@retrodev.com>
parents:
202
diff
changeset
|
53 idx <- find: k |
96fdc5b37ceb
Added get:else method to linear dict
Michael Pavone <pavone@retrodev.com>
parents:
202
diff
changeset
|
54 if: idx < 0 { |
96fdc5b37ceb
Added get:else method to linear dict
Michael Pavone <pavone@retrodev.com>
parents:
202
diff
changeset
|
55 else: |
164 | 56 } else: { |
57 (els get: idx) val | |
58 } | |
59 } | |
60 | |
192
a868a2aec930
Add contains? method to linear dictionary
Mike Pavone <pavone@retrodev.com>
parents:
164
diff
changeset
|
61 contains? <- :k { |
a868a2aec930
Add contains? method to linear dictionary
Mike Pavone <pavone@retrodev.com>
parents:
164
diff
changeset
|
62 (find: k) >= 0 |
a868a2aec930
Add contains? method to linear dictionary
Mike Pavone <pavone@retrodev.com>
parents:
164
diff
changeset
|
63 } |
a868a2aec930
Add contains? method to linear dictionary
Mike Pavone <pavone@retrodev.com>
parents:
164
diff
changeset
|
64 |
91 | 65 foreach <- :l { |
66 foreach: els :idx el { | |
94
6735db9b44ba
Fixed my foreach on dict. Added test for it.
William Morgan <bill@mrgn.org>
parents:
91
diff
changeset
|
67 l: (el key) (el val) |
91 | 68 } |
69 } | |
94
6735db9b44ba
Fixed my foreach on dict. Added test for it.
William Morgan <bill@mrgn.org>
parents:
91
diff
changeset
|
70 |
202
cea671c4056c
Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents:
192
diff
changeset
|
71 map <- :fun { |
cea671c4056c
Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents:
192
diff
changeset
|
72 newels <- #[] |
cea671c4056c
Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents:
192
diff
changeset
|
73 foreach: els :idx el { |
cea671c4056c
Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents:
192
diff
changeset
|
74 newels append: (key: (el key) val: (fun: (el val))) |
cea671c4056c
Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents:
192
diff
changeset
|
75 } |
cea671c4056c
Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents:
192
diff
changeset
|
76 linearWithEls: newels |
cea671c4056c
Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents:
192
diff
changeset
|
77 } |
cea671c4056c
Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents:
192
diff
changeset
|
78 |
164 | 79 length <- { els length } |
74
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
80 } |
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
81 } |
250
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
82 _empty <- #{ |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
83 empty? <- { true } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
84 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
85 _makeBucket <- :key val { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
86 #{ |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
87 empty? <- { false } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
88 k <- key |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
89 v <- val |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
90 = <- :other { k = other } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
91 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
92 } |
202
cea671c4056c
Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents:
192
diff
changeset
|
93 #{ |
cea671c4056c
Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents:
192
diff
changeset
|
94 //requires only that keys support equality |
cea671c4056c
Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents:
192
diff
changeset
|
95 linear <- { |
cea671c4056c
Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents:
192
diff
changeset
|
96 linearWithEls: #[] |
cea671c4056c
Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents:
192
diff
changeset
|
97 } |
250
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
98 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
99 //requires that keys support equality and hash |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
100 hash <- { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
101 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
102 _buckets <- #[ |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
103 _empty |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
104 _empty |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
105 _empty |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
106 _empty] |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
107 _size <- 0 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
108 _hashdiffs <- #[0] |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
109 #{ |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
110 size <- { size } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
111 ifget:else <- :key ifpres :ifnot { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
112 basehash <- key hash |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
113 notdone <- true |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
114 i <- 0 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
115 ret <- _empty |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
116 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
117 while: { if: notdone { i < (_hashdiffs length)}} do: { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
118 hv <- basehash + (_hashdiffs get: i) |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
119 trunc <- hv % (_buckets length) |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
120 if: trunc < 0 { trunc <- 0 - trunc } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
121 bucket <- _buckets get: trunc |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
122 if: (bucket empty?) { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
123 notdone <- false |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
124 } else: { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
125 if: bucket = key { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
126 ret <- bucket |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
127 notdone <- false |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
128 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
129 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
130 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
131 if: (ret empty?) ifnot else: { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
132 ifpres: (ret v) |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
133 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
134 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
135 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
136 get:else <- :key :else { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
137 ifget: key :val { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
138 val |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
139 } else: else |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
140 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
141 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
142 contains? <- :key { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
143 ifget: key :_ { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
144 true |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
145 } else: { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
146 false |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
147 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
148 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
149 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
150 set <- :key val { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
151 notdone <- true |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
152 basehash <- key hash |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
153 i <- 0 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
154 while: { if: notdone { i < (_hashdiffs length) } } do: { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
155 hv <- basehash + (_hashdiffs get: i) |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
156 trunc <- hv % (_buckets length) |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
157 if: trunc < 0 { trunc <- 0 - trunc } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
158 bucket <- (_buckets get: trunc) |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
159 if: (bucket empty?) { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
160 _size <- _size + 1 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
161 _buckets set: trunc (_makeBucket: key val) |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
162 notdone <- false |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
163 } else: { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
164 if: bucket = key { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
165 bucket v!: val |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
166 notdone <- false |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
167 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
168 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
169 i <- i + 1 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
170 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
171 if: notdone { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
172 newsize <- (_buckets length) * 3 + 1 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
173 lastdiff <- _hashdiffs get: ((_hashdiffs length) - 1) |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
174 if: lastdiff <= 0 { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
175 _hashdiffs append: 0 - lastdiff + 1 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
176 } else: { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
177 _hashdiffs append: 0 - lastdiff |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
178 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
179 newbucks <- #[] |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
180 newbucks resize: newsize |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
181 while: { (newbucks length) < newsize } do: { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
182 newbucks append: _empty |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
183 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
184 oldbucks <- _buckets |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
185 _buckets <- newbucks |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
186 _size <- 0 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
187 foreach: oldbucks :idx el { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
188 if: (not: (el empty?)) { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
189 set: (el k) (el v) |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
190 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
191 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
192 set: key val |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
193 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
194 self |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
195 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
196 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
197 foreach <- :fun { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
198 foreach: _buckets :idx el { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
199 if: (not: (el empty?)) { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
200 fun: (el k) (el v) |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
201 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
202 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
203 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
204 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
205 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
206 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
207 main <- { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
208 d <- hash |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
209 d set: "foo" "bar" |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
210 d set: "baz" "qux" |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
211 i <- 0 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
212 while: { i < 32 } do: { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
213 d set: (string: i) "blah " . (string: i) |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
214 i <- i + 1 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
215 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
216 foreach: d :k v { |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
217 print: "k: " . k . ", v: " . v . "\n" |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
218 } |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
219 0 |
c58e17f5c0f6
Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents:
248
diff
changeset
|
220 } |
202
cea671c4056c
Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents:
192
diff
changeset
|
221 } |
74
434988bb1fb4
Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
222 } |