Mercurial > repos > tabletprog

comparison modules/sets.tp @ 80:cbc92ee13f35

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 }