view modules/sets.tp @ 126:a2d2d8e09291

Merge
author Mike Pavone <pavone@retrodev.com>
date Mon, 05 Aug 2013 23:37:17 -0700
parents 6f8d868e8da0 a905e13db753
children
line wrap: on
line source
#{
	hash <- {
		empty <- #{
			empty? <- { true }
		}
		size <- 0
		hashdiffs <- #[0]
		#{
			buckets <- #[empty empty empty empty]
			size <- 0
			contains? <- :object {
				hv <- object hash
				
				notdone <- true
				
				basehash <- hv
				i <- 0
				ret <- false
				while: { if: notdone { i < (hashdiffs length) } } do: {
					hv <- basehash + (hashdiffs 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
				basehash <- hv
				i <- 0
				while: { if: notdone { i < (hashdiffs length) } } do: {
					hv <- basehash + (hashdiffs 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 + 1
					lastdiff <- hashdiffs get: ((hashdiffs length) - 1)
					if: lastdiff <= 0 {
						hashdiffs append: ((0 - lastdiff) + 1)
					} else: {
						hashdiffs append: (0 - lastdiff)
					}
					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
			}
		}
	}
}