Mercurial > repos > tabletprog
comparison modules/dict.tp @ 349:60292f131de9
Make map actually work right on hashmaps
author | Michael Pavone <pavone@retrodev.com> |
---|---|
date | Fri, 10 Apr 2015 01:19:10 -0700 |
parents | 7de6ac24eb64 |
children | 04ba2118c5fe |
comparison
equal
deleted
inserted
replaced
348:a840e9a068a2 | 349:60292f131de9 |
---|---|
100 k <- key | 100 k <- key |
101 v <- val | 101 v <- val |
102 = <- :other { k = other } | 102 = <- :other { k = other } |
103 } | 103 } |
104 } | 104 } |
105 _hashWithBuckets:size:hashdiffs <- :_buckets :_size :_hashdiffs { | |
106 #{ | |
107 size <- { size } | |
108 ifget:else <- :key ifpres :ifnot { | |
109 basehash <- key hash | |
110 notdone <- true | |
111 i <- 0 | |
112 ret <- _empty | |
113 | |
114 while: { if: notdone { i < (_hashdiffs length)}} do: { | |
115 hv <- basehash + (_hashdiffs get: i) | |
116 trunc <- hv % (_buckets length) | |
117 if: trunc < 0 { trunc <- 0 - trunc } | |
118 bucket <- _buckets get: trunc | |
119 if: (bucket empty?) { | |
120 notdone <- false | |
121 } else: { | |
122 if: bucket = key { | |
123 ret <- bucket | |
124 notdone <- false | |
125 } | |
126 } | |
127 i <- i + 1 | |
128 } | |
129 if: (ret empty?) ifnot else: { | |
130 ifpres: (ret v) | |
131 } | |
132 } | |
133 | |
134 get:else <- :key :else { | |
135 ifget: key :val { | |
136 val | |
137 } else: else | |
138 } | |
139 | |
140 contains? <- :key { | |
141 ifget: key :_ { | |
142 true | |
143 } else: { | |
144 false | |
145 } | |
146 } | |
147 | |
148 set <- :key val { | |
149 notdone <- true | |
150 basehash <- key hash | |
151 i <- 0 | |
152 while: { if: notdone { i < (_hashdiffs length) } } do: { | |
153 hv <- basehash + (_hashdiffs get: i) | |
154 trunc <- hv % (_buckets length) | |
155 if: trunc < 0 { trunc <- 0 - trunc } | |
156 bucket <- (_buckets get: trunc) | |
157 if: (bucket empty?) { | |
158 _size <- _size + 1 | |
159 _buckets set: trunc (_makeBucket: key val) | |
160 notdone <- false | |
161 } else: { | |
162 if: bucket = key { | |
163 bucket v!: val | |
164 notdone <- false | |
165 } | |
166 } | |
167 i <- i + 1 | |
168 } | |
169 if: notdone { | |
170 newsize <- (_buckets length) * 3 + 1 | |
171 lastdiff <- _hashdiffs get: ((_hashdiffs length) - 1) | |
172 if: lastdiff <= 0 { | |
173 _hashdiffs append: 0 - lastdiff + 1 | |
174 } else: { | |
175 _hashdiffs append: 0 - lastdiff | |
176 } | |
177 newbucks <- #[] | |
178 newbucks resize: newsize | |
179 while: { (newbucks length) < newsize } do: { | |
180 newbucks append: _empty | |
181 } | |
182 oldbucks <- _buckets | |
183 _buckets <- newbucks | |
184 _size <- 0 | |
185 foreach: oldbucks :idx el { | |
186 if: (not: (el empty?)) { | |
187 set: (el k) (el v) | |
188 } | |
189 } | |
190 set: key val | |
191 } | |
192 self | |
193 } | |
194 | |
195 foreach <- :fun { | |
196 foreach: _buckets :idx el { | |
197 if: (not: (el empty?)) { | |
198 fun: (el k) (el v) | |
199 } | |
200 } | |
201 } | |
202 | |
203 map <- :fun { | |
204 newbucks <- _buckets map: :bucket { | |
205 if: (bucket empty?) { | |
206 bucket | |
207 } else: { | |
208 _makeBucket: (bucket k) (fun: (bucket v)) | |
209 } | |
210 } | |
211 _hashWithBuckets: newbucks size: _size hashdiffs: (_hashdiffs map: :e { e }) | |
212 } | |
213 | |
214 jsonEncode <- { | |
215 _jsonEncode: self | |
216 } | |
217 } | |
218 } | |
105 #{ | 219 #{ |
106 //requires only that keys support equality | 220 //requires only that keys support equality |
107 linear <- { | 221 linear <- { |
108 linearWithEls: #[] | 222 linearWithEls: #[] |
109 } | 223 } |
110 | 224 |
111 //requires that keys support equality and hash | 225 //requires that keys support equality and hash |
112 hash <- { | 226 hash <- { |
113 | 227 _hashWithBuckets: #[ |
114 _buckets <- #[ | 228 _empty |
115 _empty | 229 _empty |
116 _empty | 230 _empty |
117 _empty | 231 _empty |
118 _empty] | 232 ] size: 0 hashdiffs: #[0] |
119 _size <- 0 | 233 |
120 _hashdiffs <- #[0] | |
121 #{ | |
122 size <- { size } | |
123 ifget:else <- :key ifpres :ifnot { | |
124 basehash <- key hash | |
125 notdone <- true | |
126 i <- 0 | |
127 ret <- _empty | |
128 | |
129 while: { if: notdone { i < (_hashdiffs length)}} do: { | |
130 hv <- basehash + (_hashdiffs get: i) | |
131 trunc <- hv % (_buckets length) | |
132 if: trunc < 0 { trunc <- 0 - trunc } | |
133 bucket <- _buckets get: trunc | |
134 if: (bucket empty?) { | |
135 notdone <- false | |
136 } else: { | |
137 if: bucket = key { | |
138 ret <- bucket | |
139 notdone <- false | |
140 } | |
141 } | |
142 i <- i + 1 | |
143 } | |
144 if: (ret empty?) ifnot else: { | |
145 ifpres: (ret v) | |
146 } | |
147 } | |
148 | |
149 get:else <- :key :else { | |
150 ifget: key :val { | |
151 val | |
152 } else: else | |
153 } | |
154 | |
155 contains? <- :key { | |
156 ifget: key :_ { | |
157 true | |
158 } else: { | |
159 false | |
160 } | |
161 } | |
162 | |
163 set <- :key val { | |
164 notdone <- true | |
165 basehash <- key hash | |
166 i <- 0 | |
167 while: { if: notdone { i < (_hashdiffs length) } } do: { | |
168 hv <- basehash + (_hashdiffs get: i) | |
169 trunc <- hv % (_buckets length) | |
170 if: trunc < 0 { trunc <- 0 - trunc } | |
171 bucket <- (_buckets get: trunc) | |
172 if: (bucket empty?) { | |
173 _size <- _size + 1 | |
174 _buckets set: trunc (_makeBucket: key val) | |
175 notdone <- false | |
176 } else: { | |
177 if: bucket = key { | |
178 bucket v!: val | |
179 notdone <- false | |
180 } | |
181 } | |
182 i <- i + 1 | |
183 } | |
184 if: notdone { | |
185 newsize <- (_buckets length) * 3 + 1 | |
186 lastdiff <- _hashdiffs get: ((_hashdiffs length) - 1) | |
187 if: lastdiff <= 0 { | |
188 _hashdiffs append: 0 - lastdiff + 1 | |
189 } else: { | |
190 _hashdiffs append: 0 - lastdiff | |
191 } | |
192 newbucks <- #[] | |
193 newbucks resize: newsize | |
194 while: { (newbucks length) < newsize } do: { | |
195 newbucks append: _empty | |
196 } | |
197 oldbucks <- _buckets | |
198 _buckets <- newbucks | |
199 _size <- 0 | |
200 foreach: oldbucks :idx el { | |
201 if: (not: (el empty?)) { | |
202 set: (el k) (el v) | |
203 } | |
204 } | |
205 set: key val | |
206 } | |
207 self | |
208 } | |
209 | |
210 foreach <- :fun { | |
211 foreach: _buckets :idx el { | |
212 if: (not: (el empty?)) { | |
213 fun: (el k) (el v) | |
214 } | |
215 } | |
216 } | |
217 | |
218 map <- :fun { | |
219 foreach: _buckets :idx el { | |
220 if: (not: (el empty?)) { | |
221 el v!: (fun: (el v)) | |
222 } | |
223 } | |
224 } | |
225 | |
226 jsonEncode <- { | |
227 _jsonEncode: self | |
228 } | |
229 } | |
230 } | 234 } |
231 | 235 |
232 main <- { | 236 main <- { |
233 d <- hash | 237 d <- hash |
234 d set: "foo" "bar" | 238 d set: "foo" "bar" |