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