Mercurial > repos > tabletprog
annotate modules/sets.tp @ 331:61f5b794d939
Breaking change: method call syntax now always uses the syntactic receiver as the actual receiver. This makes its behavior different from function call syntax, but solves some problems with methods being shadowed by local variables and the like.
| author | Michael Pavone <pavone@retrodev.com> |
|---|---|
| date | Sat, 28 Mar 2015 14:21:04 -0700 |
| parents | a2d2d8e09291 |
| children |
| 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] | |
|
125
6f8d868e8da0
Add size to set implementation
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
10 size <- 0 |
| 80 | 11 contains? <- :object { |
| 12 hv <- object hash | |
| 13 | |
| 14 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
|
15 |
|
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
|
16 basehash <- hv |
| 80 | 17 i <- 0 |
| 18 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
|
19 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
|
20 hv <- basehash + (hashdiffs get: i) |
| 80 | 21 trunc <- hv % (buckets length) |
| 22 if: trunc < 0 { trunc <- 0 - trunc } | |
| 23 bucketval <- (buckets get: trunc) | |
| 24 if: (bucketval empty?) { | |
| 25 notdone <- false | |
| 26 } else: { | |
| 27 if: (bucketval eq: hv) { | |
| 28 ret <- true | |
| 29 notdone <- false | |
| 30 } | |
| 31 } | |
| 32 i <- i + 1 | |
| 33 } | |
| 34 ret | |
| 35 } | |
| 36 add <- :object { | |
| 37 addHash: (object hash) | |
| 38 } | |
| 39 addHash <- :hv { | |
| 40 makeBucket <- :hv { | |
| 41 #{ | |
| 42 empty? <- { false } | |
| 43 v <- hv | |
| 44 eq <- :other { v = other } | |
| 45 } | |
| 46 } | |
| 47 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
|
48 basehash <- hv |
| 80 | 49 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
|
50 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
|
51 hv <- basehash + (hashdiffs get: i) |
| 80 | 52 trunc <- hv % (buckets length) |
| 53 if: trunc < 0 { trunc <- 0 - trunc } | |
| 54 bucketval <- (buckets get: trunc) | |
| 55 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
|
56 size <- size + 1 |
| 80 | 57 buckets set: trunc (makeBucket: hv) |
| 58 notdone <- false | |
| 59 } else: { | |
| 60 if: (bucketval eq: hv) { | |
| 61 notdone <- false | |
| 62 } | |
| 63 } | |
| 64 i <- i + 1 | |
| 65 } | |
| 66 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
|
67 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
|
68 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
|
69 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
|
70 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
|
71 } 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
|
72 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
|
73 } |
| 80 | 74 newbucks <- #[] |
|
125
6f8d868e8da0
Add size to set implementation
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
75 newbucks resize: newsize |
| 80 | 76 while: { (newbucks length) < newsize } do: { |
| 77 newbucks append: empty | |
| 78 } | |
| 79 oldbucks <- buckets | |
| 80 buckets <- newbucks | |
|
125
6f8d868e8da0
Add size to set implementation
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
81 size <- 0 |
| 80 | 82 foreach: oldbucks :idx el { |
| 83 if: (not: (el empty?)) { | |
| 84 addHash: (el v) | |
| 85 } | |
| 86 } | |
| 87 addHash: hv | |
| 88 } | |
| 89 self | |
| 90 } | |
| 91 } | |
| 92 } | |
| 93 } |