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 } |