Mercurial > repos > tabletprog

comparison modules/dict.tp @ 250:c58e17f5c0f6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
249:fd9005253861 250:c58e17f5c0f6
77 } 77 }
78 78
79 length <- { els length } 79 length <- { els length }
80 } 80 }
81 } 81 }
82 _empty <- #{
83 empty? <- { true }
84 }
85 _makeBucket <- :key val {
86 #{
87 empty? <- { false }
88 k <- key
89 v <- val
90 = <- :other { k = other }
91 }
92 }
82 #{ 93 #{
83 //requires only that keys support equality 94 //requires only that keys support equality
84 linear <- { 95 linear <- {
85 linearWithEls: #[] 96 linearWithEls: #[]
86 } 97 }
98
99 //requires that keys support equality and hash
100 hash <- {
101
102 _buckets <- #[
103 _empty
104 _empty
105 _empty
106 _empty]
107 _size <- 0
108 _hashdiffs <- #[0]
109 #{
110 size <- { size }
111 ifget:else <- :key ifpres :ifnot {
112 basehash <- key hash
113 notdone <- true
114 i <- 0
115 ret <- _empty
116
117 while: { if: notdone { i < (_hashdiffs length)}} do: {
118 hv <- basehash + (_hashdiffs get: i)
119 trunc <- hv % (_buckets length)
120 if: trunc < 0 { trunc <- 0 - trunc }
121 bucket <- _buckets get: trunc
122 if: (bucket empty?) {
123 notdone <- false
124 } else: {
125 if: bucket = key {
126 ret <- bucket
127 notdone <- false
128 }
129 }
130 }
131 if: (ret empty?) ifnot else: {
132 ifpres: (ret v)
133 }
134 }
135
136 get:else <- :key :else {
137 ifget: key :val {
138 val
139 } else: else
140 }
141
142 contains? <- :key {
143 ifget: key :_ {
144 true
145 } else: {
146 false
147 }
148 }
149
150 set <- :key val {
151 notdone <- true
152 basehash <- key hash
153 i <- 0
154 while: { if: notdone { i < (_hashdiffs length) } } do: {
155 hv <- basehash + (_hashdiffs get: i)
156 trunc <- hv % (_buckets length)
157 if: trunc < 0 { trunc <- 0 - trunc }
158 bucket <- (_buckets get: trunc)
159 if: (bucket empty?) {
160 _size <- _size + 1
161 _buckets set: trunc (_makeBucket: key val)
162 notdone <- false
163 } else: {
164 if: bucket = key {
165 bucket v!: val
166 notdone <- false
167 }
168 }
169 i <- i + 1
170 }
171 if: notdone {
172 newsize <- (_buckets length) * 3 + 1
173 lastdiff <- _hashdiffs get: ((_hashdiffs length) - 1)
174 if: lastdiff <= 0 {
175 _hashdiffs append: 0 - lastdiff + 1
176 } else: {
177 _hashdiffs append: 0 - lastdiff
178 }
179 newbucks <- #[]
180 newbucks resize: newsize
181 while: { (newbucks length) < newsize } do: {
182 newbucks append: _empty
183 }
184 oldbucks <- _buckets
185 _buckets <- newbucks
186 _size <- 0
187 foreach: oldbucks :idx el {
188 if: (not: (el empty?)) {
189 set: (el k) (el v)
190 }
191 }
192 set: key val
193 }
194 self
195 }
196
197 foreach <- :fun {
198 foreach: _buckets :idx el {
199 if: (not: (el empty?)) {
200 fun: (el k) (el v)
201 }
202 }
203 }
204 }
205 }
206
207 main <- {
208 d <- hash
209 d set: "foo" "bar"
210 d set: "baz" "qux"
211 i <- 0
212 while: { i < 32 } do: {
213 d set: (string: i) "blah " . (string: i)
214 i <- i + 1
215 }
216 foreach: d :k v {
217 print: "k: " . k . ", v: " . v . "\n"
218 }
219 0
220 }
87 } 221 }
88 } 222 }