Mercurial > repos > tabletprog
annotate modules/sets.tp @ 105:35006a6e1c47
Fixed more editor coderot and improved syntax/selection coloring a bit.
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Thu, 11 Apr 2013 09:16:35 -0700 |
parents | a905e13db753 |
children | a2d2d8e09291 |
rev | line source |
---|---|
80 | 1 #{ |
2 hash <- { | |
3 empty <- #{ | |
4 empty? <- { true } | |
5 } | |
81
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
6 size <- 0 |
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
7 hashdiffs <- #[0] |
80 | 8 #{ |
9 buckets <- #[empty empty empty empty] | |
10 contains? <- :object { | |
11 hv <- object hash | |
12 | |
13 notdone <- true | |
81
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
14 |
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
15 basehash <- hv |
80 | 16 i <- 0 |
17 ret <- false | |
81
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
18 while: { if: notdone { i < (hashdiffs length) } } do: { |
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
19 hv <- basehash + (hashdiffs get: i) |
80 | 20 trunc <- hv % (buckets length) |
21 if: trunc < 0 { trunc <- 0 - trunc } | |
22 bucketval <- (buckets get: trunc) | |
23 if: (bucketval empty?) { | |
24 notdone <- false | |
25 } else: { | |
26 if: (bucketval eq: hv) { | |
27 ret <- true | |
28 notdone <- false | |
29 } | |
30 } | |
31 i <- i + 1 | |
32 } | |
33 ret | |
34 } | |
35 add <- :object { | |
36 addHash: (object hash) | |
37 } | |
38 addHash <- :hv { | |
39 makeBucket <- :hv { | |
40 #{ | |
41 empty? <- { false } | |
42 v <- hv | |
43 eq <- :other { v = other } | |
44 } | |
45 } | |
46 notdone <- true | |
81
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
47 basehash <- hv |
80 | 48 i <- 0 |
81
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
49 while: { if: notdone { i < (hashdiffs length) } } do: { |
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
50 hv <- basehash + (hashdiffs get: i) |
80 | 51 trunc <- hv % (buckets length) |
52 if: trunc < 0 { trunc <- 0 - trunc } | |
53 bucketval <- (buckets get: trunc) | |
54 if: (bucketval empty?) { | |
81
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
55 size <- size + 1 |
80 | 56 buckets set: trunc (makeBucket: hv) |
57 notdone <- false | |
58 } else: { | |
59 if: (bucketval eq: hv) { | |
60 notdone <- false | |
61 } | |
62 } | |
63 i <- i + 1 | |
64 } | |
65 if: notdone { | |
81
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
66 newsize <- (buckets length) * 3 + 1 |
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
67 lastdiff <- hashdiffs get: ((hashdiffs length) - 1) |
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
68 if: lastdiff <= 0 { |
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
69 hashdiffs append: ((0 - lastdiff) + 1) |
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
70 } else: { |
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
71 hashdiffs append: (0 - lastdiff) |
a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
72 } |
80 | 73 newbucks <- #[] |
74 while: { (newbucks length) < newsize } do: { | |
75 newbucks append: empty | |
76 } | |
77 oldbucks <- buckets | |
78 buckets <- newbucks | |
79 foreach: oldbucks :idx el { | |
80 if: (not: (el empty?)) { | |
81 addHash: (el v) | |
82 } | |
83 } | |
84 addHash: hv | |
85 } | |
86 self | |
87 } | |
88 } | |
89 } | |
90 } |