Mercurial > repos > tabletprog
view 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 |
line wrap: on
line source
#{ hash <- { empty <- #{ empty? <- { true } } #{ buckets <- #[empty empty empty empty] contains? <- :object { hv <- object hash notdone <- true hashes <- #[hv (hv + 1) (hv - 1)] i <- 0 ret <- false while: { if: notdone { i < 3 } } do: { hv <- hashes get: i trunc <- hv % (buckets length) if: trunc < 0 { trunc <- 0 - trunc } bucketval <- (buckets get: trunc) if: (bucketval empty?) { notdone <- false } else: { if: (bucketval eq: hv) { ret <- true notdone <- false } } i <- i + 1 } ret } add <- :object { addHash: (object hash) } addHash <- :hv { makeBucket <- :hv { #{ empty? <- { false } v <- hv eq <- :other { v = other } } } notdone <- true hashes <- #[hv (hv + 1) (hv - 1)] i <- 0 while: { if: notdone { i < 3 } } do: { hv <- hashes get: i trunc <- hv % (buckets length) if: trunc < 0 { trunc <- 0 - trunc } bucketval <- (buckets get: trunc) if: (bucketval empty?) { buckets set: trunc (makeBucket: hv) notdone <- false } else: { if: (bucketval eq: hv) { notdone <- false } } i <- i + 1 } if: notdone { newsize <- (buckets length) * 3 newbucks <- #[] while: { (newbucks length) < newsize } do: { newbucks append: empty } oldbucks <- buckets buckets <- newbucks foreach: oldbucks :idx el { if: (not: (el empty?)) { addHash: (el v) } } addHash: hv } self } } } }