Mercurial > repos > tabletprog
annotate modules/sets.tp @ 125:6f8d868e8da0
Add size to set implementation
| author | Mike Pavone <pavone@retrodev.com> |
|---|---|
| date | Mon, 05 Aug 2013 23:36:18 -0700 |
| parents | cbc92ee13f35 |
| children | a2d2d8e09291 |
| rev | line source |
|---|---|
| 80 | 1 #{ |
| 2 hash <- { | |
| 3 empty <- #{ | |
| 4 empty? <- { true } | |
| 5 } | |
| 6 #{ | |
| 7 buckets <- #[empty empty empty empty] | |
|
125
6f8d868e8da0
Add size to set implementation
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
8 size <- 0 |
| 80 | 9 contains? <- :object { |
| 10 hv <- object hash | |
| 11 | |
| 12 notdone <- true | |
| 13 hashes <- #[hv (hv + 1) (hv - 1)] | |
| 14 i <- 0 | |
| 15 ret <- false | |
| 16 while: { if: notdone { i < 3 } } do: { | |
| 17 hv <- hashes get: i | |
| 18 trunc <- hv % (buckets length) | |
| 19 if: trunc < 0 { trunc <- 0 - trunc } | |
| 20 bucketval <- (buckets get: trunc) | |
| 21 if: (bucketval empty?) { | |
| 22 notdone <- false | |
| 23 } else: { | |
| 24 if: (bucketval eq: hv) { | |
| 25 ret <- true | |
| 26 notdone <- false | |
| 27 } | |
| 28 } | |
| 29 i <- i + 1 | |
| 30 } | |
| 31 ret | |
| 32 } | |
| 33 add <- :object { | |
| 34 addHash: (object hash) | |
| 35 } | |
| 36 addHash <- :hv { | |
| 37 makeBucket <- :hv { | |
| 38 #{ | |
| 39 empty? <- { false } | |
| 40 v <- hv | |
| 41 eq <- :other { v = other } | |
| 42 } | |
| 43 } | |
| 44 notdone <- true | |
| 45 hashes <- #[hv (hv + 1) (hv - 1)] | |
| 46 i <- 0 | |
| 47 while: { if: notdone { i < 3 } } do: { | |
| 48 hv <- hashes get: i | |
| 49 trunc <- hv % (buckets length) | |
| 50 if: trunc < 0 { trunc <- 0 - trunc } | |
| 51 bucketval <- (buckets get: trunc) | |
| 52 if: (bucketval empty?) { | |
|
125
6f8d868e8da0
Add size to set implementation
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
53 size <- size + 1 |
| 80 | 54 buckets set: trunc (makeBucket: hv) |
| 55 notdone <- false | |
| 56 } else: { | |
| 57 if: (bucketval eq: hv) { | |
| 58 notdone <- false | |
| 59 } | |
| 60 } | |
| 61 i <- i + 1 | |
| 62 } | |
| 63 if: notdone { | |
| 64 newsize <- (buckets length) * 3 | |
| 65 newbucks <- #[] | |
|
125
6f8d868e8da0
Add size to set implementation
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
66 newbucks resize: newsize |
| 80 | 67 while: { (newbucks length) < newsize } do: { |
| 68 newbucks append: empty | |
| 69 } | |
| 70 oldbucks <- buckets | |
| 71 buckets <- newbucks | |
|
125
6f8d868e8da0
Add size to set implementation
Mike Pavone <pavone@retrodev.com>
parents:
80
diff
changeset
|
72 size <- 0 |
| 80 | 73 foreach: oldbucks :idx el { |
| 74 if: (not: (el empty?)) { | |
| 75 addHash: (el v) | |
| 76 } | |
| 77 } | |
| 78 addHash: hv | |
| 79 } | |
| 80 self | |
| 81 } | |
| 82 } | |
| 83 } | |
| 84 } |