Mercurial > repos > tabletprog

comparison modules/dict.tp @ 349:60292f131de9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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"