Mercurial > repos > tabletprog

annotate 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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
202
cea671c4056c Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents: 192
diff changeset
1 {
271
bb4723fec05e Support for encoding objects, dictionaries, lists and arrays to JSON in json module
Michael Pavone <pavone@retrodev.com>
parents: 253
diff changeset
2 _jsonEncode <- :dict {
bb4723fec05e Support for encoding objects, dictionaries, lists and arrays to JSON in json module
Michael Pavone <pavone@retrodev.com>
parents: 253
diff changeset
3 parts <- #[]
bb4723fec05e Support for encoding objects, dictionaries, lists and arrays to JSON in json module
Michael Pavone <pavone@retrodev.com>
parents: 253
diff changeset
4 foreach: dict :key val {
bb4723fec05e Support for encoding objects, dictionaries, lists and arrays to JSON in json module
Michael Pavone <pavone@retrodev.com>
parents: 253
diff changeset
5 //TODO: escape field names
329
eef8a5cea812 Use a smarter algorithm for calculating module init order and break some circular module dependencies in the standard library
Michael Pavone <pavone@retrodev.com>
parents: 271
diff changeset
6 parts append: (key jsonEncode) . ":" . (jsonEncoder encode: val)
271
bb4723fec05e Support for encoding objects, dictionaries, lists and arrays to JSON in json module
Michael Pavone <pavone@retrodev.com>
parents: 253
diff changeset
7 }
bb4723fec05e Support for encoding objects, dictionaries, lists and arrays to JSON in json module
Michael Pavone <pavone@retrodev.com>
parents: 253
diff changeset
8 "{" . (parts join: ",") . "}"
bb4723fec05e Support for encoding objects, dictionaries, lists and arrays to JSON in json module
Michael Pavone <pavone@retrodev.com>
parents: 253
diff changeset
9 }
202
cea671c4056c Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents: 192
diff changeset
10 linearWithEls <- :els {
74
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
11 key:val <- :k v {
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
12 #{
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
13 key <- k
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
14 val <- v
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
15 }
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
16 }
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
17 find <- :tofind {
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
18 idx <- 0
164
75be44ed9df5 Dict improvements
Mike Pavone <pavone@retrodev.com>
parents: 94
diff changeset
19 while: {
75be44ed9df5 Dict improvements
Mike Pavone <pavone@retrodev.com>
parents: 94
diff changeset
20 if: idx < (els length) {
74
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
21 ((els get: idx) key: ) != tofind
164
75be44ed9df5 Dict improvements
Mike Pavone <pavone@retrodev.com>
parents: 94
diff changeset
22 } else: {false}
74
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
23 } do: {
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
24 idx <- idx + 1
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
25 }
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
26 if: idx < (els length) {idx} else: {-1}
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 #{
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
29 set <- :k v {
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
30 idx <- find: k
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
31 if: idx < 0 {
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
32 els append: (key: k val: v)
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
33 } else: {
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
34 (els get: idx) val!: v
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
35 }
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
36 self
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
37 }
164
75be44ed9df5 Dict improvements
Mike Pavone <pavone@retrodev.com>
parents: 94
diff changeset
38
74
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
39 get <- :k {
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
40 get: k withDefault: false
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
41 }
164
75be44ed9df5 Dict improvements
Mike Pavone <pavone@retrodev.com>
parents: 94
diff changeset
42
74
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
43 get:withDefault <- :k default {
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
44 idx <- find: k
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
45 if: idx < 0 {
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
46 default
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
47 } else: {
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
48 (els get: idx) val
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
49 }
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
50 }
164
75be44ed9df5 Dict improvements
Mike Pavone <pavone@retrodev.com>
parents: 94
diff changeset
51
75be44ed9df5 Dict improvements
Mike Pavone <pavone@retrodev.com>
parents: 94
diff changeset
52 get:elseSet <- :k :else {
248
96fdc5b37ceb Added get:else method to linear dict
Michael Pavone <pavone@retrodev.com>
parents: 202
diff changeset
53 get: k else: {
164
75be44ed9df5 Dict improvements
Mike Pavone <pavone@retrodev.com>
parents: 94
diff changeset
54 v <- else:
75be44ed9df5 Dict improvements
Mike Pavone <pavone@retrodev.com>
parents: 94
diff changeset
55 els append: (key: k val: v)
75be44ed9df5 Dict improvements
Mike Pavone <pavone@retrodev.com>
parents: 94
diff changeset
56 v
248
96fdc5b37ceb Added get:else method to linear dict
Michael Pavone <pavone@retrodev.com>
parents: 202
diff changeset
57 }
96fdc5b37ceb Added get:else method to linear dict
Michael Pavone <pavone@retrodev.com>
parents: 202
diff changeset
58 }
96fdc5b37ceb Added get:else method to linear dict
Michael Pavone <pavone@retrodev.com>
parents: 202
diff changeset
59
96fdc5b37ceb Added get:else method to linear dict
Michael Pavone <pavone@retrodev.com>
parents: 202
diff changeset
60 get:else <- :k :else {
96fdc5b37ceb Added get:else method to linear dict
Michael Pavone <pavone@retrodev.com>
parents: 202
diff changeset
61 idx <- find: k
96fdc5b37ceb Added get:else method to linear dict
Michael Pavone <pavone@retrodev.com>
parents: 202
diff changeset
62 if: idx < 0 {
96fdc5b37ceb Added get:else method to linear dict
Michael Pavone <pavone@retrodev.com>
parents: 202
diff changeset
63 else:
164
75be44ed9df5 Dict improvements
Mike Pavone <pavone@retrodev.com>
parents: 94
diff changeset
64 } else: {
75be44ed9df5 Dict improvements
Mike Pavone <pavone@retrodev.com>
parents: 94
diff changeset
65 (els get: idx) val
75be44ed9df5 Dict improvements
Mike Pavone <pavone@retrodev.com>
parents: 94
diff changeset
66 }
75be44ed9df5 Dict improvements
Mike Pavone <pavone@retrodev.com>
parents: 94
diff changeset
67 }
75be44ed9df5 Dict improvements
Mike Pavone <pavone@retrodev.com>
parents: 94
diff changeset
68
192
a868a2aec930 Add contains? method to linear dictionary
Mike Pavone <pavone@retrodev.com>
parents: 164
diff changeset
69 contains? <- :k {
a868a2aec930 Add contains? method to linear dictionary
Mike Pavone <pavone@retrodev.com>
parents: 164
diff changeset
70 (find: k) >= 0
a868a2aec930 Add contains? method to linear dictionary
Mike Pavone <pavone@retrodev.com>
parents: 164
diff changeset
71 }
a868a2aec930 Add contains? method to linear dictionary
Mike Pavone <pavone@retrodev.com>
parents: 164
diff changeset
72
91
3bf57ace3e0b added foreach on dict
William Morgan <bill@mrgn.org>
parents: 75
diff changeset
73 foreach <- :l {
3bf57ace3e0b added foreach on dict
William Morgan <bill@mrgn.org>
parents: 75
diff changeset
74 foreach: els :idx el {
94
6735db9b44ba Fixed my foreach on dict. Added test for it.
William Morgan <bill@mrgn.org>
parents: 91
diff changeset
75 l: (el key) (el val)
91
3bf57ace3e0b added foreach on dict
William Morgan <bill@mrgn.org>
parents: 75
diff changeset
76 }
3bf57ace3e0b added foreach on dict
William Morgan <bill@mrgn.org>
parents: 75
diff changeset
77 }
94
6735db9b44ba Fixed my foreach on dict. Added test for it.
William Morgan <bill@mrgn.org>
parents: 91
diff changeset
78
202
cea671c4056c Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents: 192
diff changeset
79 map <- :fun {
cea671c4056c Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents: 192
diff changeset
80 newels <- #[]
cea671c4056c Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents: 192
diff changeset
81 foreach: els :idx el {
cea671c4056c Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents: 192
diff changeset
82 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
83 }
cea671c4056c Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents: 192
diff changeset
84 linearWithEls: newels
cea671c4056c Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents: 192
diff changeset
85 }
cea671c4056c Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents: 192
diff changeset
86
164
75be44ed9df5 Dict improvements
Mike Pavone <pavone@retrodev.com>
parents: 94
diff changeset
87 length <- { els length }
271
bb4723fec05e Support for encoding objects, dictionaries, lists and arrays to JSON in json module
Michael Pavone <pavone@retrodev.com>
parents: 253
diff changeset
88
bb4723fec05e Support for encoding objects, dictionaries, lists and arrays to JSON in json module
Michael Pavone <pavone@retrodev.com>
parents: 253
diff changeset
89 jsonEncode <- {
bb4723fec05e Support for encoding objects, dictionaries, lists and arrays to JSON in json module
Michael Pavone <pavone@retrodev.com>
parents: 253
diff changeset
90 _jsonEncode: self
bb4723fec05e Support for encoding objects, dictionaries, lists and arrays to JSON in json module
Michael Pavone <pavone@retrodev.com>
parents: 253
diff changeset
91 }
74
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
92 }
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
93 }
250
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
94 _empty <- #{
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
95 empty? <- { true }
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
96 }
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
97 _makeBucket <- :key val {
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 empty? <- { false }
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
100 k <- key
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
101 v <- val
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
102 = <- :other { k = other }
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
103 }
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
104 }
349
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
105 _hashWithBuckets:size:hashdiffs <- :_buckets :_size :_hashdiffs {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
106 #{
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
107 size <- { size }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
108 ifget:else <- :key ifpres :ifnot {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
109 basehash <- key hash
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
110 notdone <- true
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
111 i <- 0
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
112 ret <- _empty
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
113
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
114 while: { if: notdone { i < (_hashdiffs length)}} do: {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
115 hv <- basehash + (_hashdiffs get: i)
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
116 trunc <- hv % (_buckets length)
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
117 if: trunc < 0 { trunc <- 0 - trunc }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
118 bucket <- _buckets get: trunc
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
119 if: (bucket empty?) {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
120 notdone <- false
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
121 } else: {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
122 if: bucket = key {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
123 ret <- bucket
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
124 notdone <- false
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
125 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
126 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
127 i <- i + 1
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
128 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
129 if: (ret empty?) ifnot else: {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
130 ifpres: (ret v)
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
131 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
132 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
133
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
134 get:else <- :key :else {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
135 ifget: key :val {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
136 val
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
137 } else: else
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
138 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
139
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
140 contains? <- :key {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
141 ifget: key :_ {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
142 true
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
143 } else: {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
144 false
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
145 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
146 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
147
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
148 set <- :key val {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
149 notdone <- true
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
150 basehash <- key hash
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
151 i <- 0
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
152 while: { if: notdone { i < (_hashdiffs length) } } do: {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
153 hv <- basehash + (_hashdiffs get: i)
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
154 trunc <- hv % (_buckets length)
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
155 if: trunc < 0 { trunc <- 0 - trunc }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
156 bucket <- (_buckets get: trunc)
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
157 if: (bucket empty?) {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
158 _size <- _size + 1
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
159 _buckets set: trunc (_makeBucket: key val)
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
160 notdone <- false
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
161 } else: {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
162 if: bucket = key {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
163 bucket v!: val
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
164 notdone <- false
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
165 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
166 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
167 i <- i + 1
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
168 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
169 if: notdone {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
170 newsize <- (_buckets length) * 3 + 1
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
171 lastdiff <- _hashdiffs get: ((_hashdiffs length) - 1)
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
172 if: lastdiff <= 0 {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
173 _hashdiffs append: 0 - lastdiff + 1
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
174 } else: {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
175 _hashdiffs append: 0 - lastdiff
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
176 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
177 newbucks <- #[]
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
178 newbucks resize: newsize
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
179 while: { (newbucks length) < newsize } do: {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
180 newbucks append: _empty
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
181 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
182 oldbucks <- _buckets
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
183 _buckets <- newbucks
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
184 _size <- 0
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
185 foreach: oldbucks :idx el {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
186 if: (not: (el empty?)) {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
187 set: (el k) (el v)
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
188 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
189 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
190 set: key val
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
191 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
192 self
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
193 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
194
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
195 foreach <- :fun {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
196 foreach: _buckets :idx el {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
197 if: (not: (el empty?)) {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
198 fun: (el k) (el v)
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
199 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
200 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
201 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
202
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
203 map <- :fun {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
204 newbucks <- _buckets map: :bucket {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
205 if: (bucket empty?) {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
206 bucket
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
207 } else: {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
208 _makeBucket: (bucket k) (fun: (bucket v))
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
209 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
210 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
211 _hashWithBuckets: newbucks size: _size hashdiffs: (_hashdiffs map: :e { e })
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
212 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
213
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
214 jsonEncode <- {
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
215 _jsonEncode: self
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
216 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
217 }
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
218 }
202
cea671c4056c Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents: 192
diff changeset
219 #{
cea671c4056c Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents: 192
diff changeset
220 //requires only that keys support equality
cea671c4056c Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents: 192
diff changeset
221 linear <- {
cea671c4056c Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents: 192
diff changeset
222 linearWithEls: #[]
cea671c4056c Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents: 192
diff changeset
223 }
250
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
224
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
225 //requires that keys support equality and hash
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
226 hash <- {
349
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
227 _hashWithBuckets: #[
250
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
228 _empty
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
229 _empty
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
230 _empty
349
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
231 _empty
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
232 ] size: 0 hashdiffs: #[0]
60292f131de9 Make map actually work right on hashmaps
Michael Pavone <pavone@retrodev.com>
parents: 344
diff changeset
233
250
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
234 }
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
235
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
236 main <- {
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
237 d <- hash
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
238 d set: "foo" "bar"
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
239 d set: "baz" "qux"
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
240 i <- 0
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
241 while: { i < 32 } do: {
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
242 d set: (string: i) "blah " . (string: i)
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
243 i <- i + 1
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
244 }
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
245 foreach: d :k v {
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
246 print: "k: " . k . ", v: " . v . "\n"
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
247 }
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
248 0
c58e17f5c0f6 Added hash dictionary to dict module
Michael Pavone <pavone@retrodev.com>
parents: 248
diff changeset
249 }
202
cea671c4056c Add map method to linear dict
Mike Pavone <pavone@retrodev.com>
parents: 192
diff changeset
250 }
74
434988bb1fb4 Add lame linear search dictionary
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
251 }