annotate modules/sets.tp @ 347:ff7ea11b4b60

Add length method to executable bytearrays
author Michael Pavone <pavone@retrodev.com>
date Fri, 10 Apr 2015 00:48:12 -0700
parents a2d2d8e09291
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
80
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
1 #{
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
2 hash <- {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
3 empty <- #{
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
4 empty? <- { true }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
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
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
8 #{
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
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
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
11 contains? <- :object {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
12 hv <- object hash
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
13
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
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
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
17 i <- 0
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
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
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
21 trunc <- hv % (buckets length)
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
22 if: trunc < 0 { trunc <- 0 - trunc }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
23 bucketval <- (buckets get: trunc)
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
24 if: (bucketval empty?) {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
25 notdone <- false
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
26 } else: {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
27 if: (bucketval eq: hv) {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
28 ret <- true
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
29 notdone <- false
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
30 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
31 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
32 i <- i + 1
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
33 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
34 ret
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
35 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
36 add <- :object {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
37 addHash: (object hash)
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
38 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
39 addHash <- :hv {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
40 makeBucket <- :hv {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
41 #{
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
42 empty? <- { false }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
43 v <- hv
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
44 eq <- :other { v = other }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
45 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
46 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
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
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
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
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
52 trunc <- hv % (buckets length)
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
53 if: trunc < 0 { trunc <- 0 - trunc }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
54 bucketval <- (buckets get: trunc)
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
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
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
57 buckets set: trunc (makeBucket: hv)
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
58 notdone <- false
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
59 } else: {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
60 if: (bucketval eq: hv) {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
61 notdone <- false
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
62 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
63 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
64 i <- i + 1
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
65 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
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
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
74 newbucks <- #[]
125
6f8d868e8da0 Add size to set implementation
Mike Pavone <pavone@retrodev.com>
parents: 80
diff changeset
75 newbucks resize: newsize
80
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
76 while: { (newbucks length) < newsize } do: {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
77 newbucks append: empty
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
78 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
79 oldbucks <- buckets
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
80 buckets <- newbucks
125
6f8d868e8da0 Add size to set implementation
Mike Pavone <pavone@retrodev.com>
parents: 80
diff changeset
81 size <- 0
80
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
82 foreach: oldbucks :idx el {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
83 if: (not: (el empty?)) {
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
84 addHash: (el v)
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
85 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
86 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
87 addHash: hv
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
88 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
89 self
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
90 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
91 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
92 }
cbc92ee13f35 Add hash set
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
93 }