Mercurial > repos > tabletprog
annotate modules/sets.tp @ 242:0e7982adc76b
Make the successful return value from a match expression be truthy and the failure value false. This avoids an extra method call when checking the result and avoids allocating a new object when a match fails.
| author | Mike Pavone <pavone@retrodev.com> |
|---|---|
| date | Sun, 05 Jan 2014 20:56:25 -0800 |
| 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 } |