diff 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 diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/modules/sets.tp	Mon Jul 16 01:22:48 2012 -0700
@@ -0,0 +1,80 @@
+#{
+	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
+			}
+		}
+	}
+}