view 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
line wrap: on
line source

#{
	hash <- {
		empty <- #{
			empty? <- { true }
		}
		#{
			buckets <- #[empty empty empty empty]
			size <- 0
			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?) {
						size <- size + 1
						buckets set: trunc (makeBucket: hv)
						notdone <- false
					} else: {
						if: (bucketval eq: hv) {
							notdone <- false
						}
					}
					i <- i + 1
				}
				if: notdone {
					newsize <- (buckets length) * 3
					newbucks <- #[]
					newbucks resize: newsize
					while: { (newbucks length) < newsize } do: {
						newbucks append: empty
					}
					oldbucks <- buckets
					buckets <- newbucks
					size <- 0
					foreach: oldbucks :idx el {
						if: (not: (el empty?)) {
							addHash: (el v)
						}
					}
					addHash: hv
				}
				self
			}
		}
	}
}