# HG changeset patch
# User Michael Pavone <pavone@retrodev.com>
# Date 1397109310 25200
# Node ID c58e17f5c0f66e222f3b27fa24d614c3ea5605c3
# Parent  fd9005253861c9b72a5d8791ba97f89e650ae791
Added hash dictionary to dict module

diff -r fd9005253861 -r c58e17f5c0f6 modules/dict.tp
--- a/modules/dict.tp	Wed Apr 09 22:54:52 2014 -0700
+++ b/modules/dict.tp	Wed Apr 09 22:55:10 2014 -0700
@@ -79,10 +79,144 @@
 			length <- { els length }
 		}
 	}
+	_empty <- #{
+		empty? <- { true }
+	}
+	_makeBucket <- :key val {
+		#{
+			empty? <- { false }
+			k <- key
+			v <- val
+			= <- :other { k = other }
+		}
+	}
 	#{
 		//requires only that keys support equality
 		linear <- {
 			linearWithEls: #[]
 		}
+
+		//requires that keys support equality and hash
+		hash <- {
+
+			_buckets <- #[
+				_empty
+				_empty
+				_empty
+				_empty]
+			_size <- 0
+			_hashdiffs <- #[0]
+			#{
+				size <- { size }
+				ifget:else <- :key ifpres :ifnot {
+					basehash <- key hash
+					notdone <- true
+					i <- 0
+					ret <- _empty
+
+					while: { if: notdone { i < (_hashdiffs length)}} do: {
+						hv <- basehash + (_hashdiffs get: i)
+						trunc <- hv % (_buckets length)
+						if: trunc < 0 { trunc <- 0 - trunc }
+						bucket <- _buckets get: trunc
+						if: (bucket empty?) {
+							notdone <- false
+						} else: {
+							if: bucket = key {
+								ret <- bucket
+								notdone <- false
+							}
+						}
+					}
+					if: (ret empty?) ifnot else: {
+						ifpres: (ret v)
+					}
+				}
+
+				get:else <- :key :else {
+					ifget: key :val {
+						val
+					} else: else
+				}
+
+				contains? <- :key {
+					ifget: key :_ {
+						true
+					} else: {
+						false
+					}
+				}
+
+				set <- :key val {
+					notdone <- true
+					basehash <- key hash
+					i <- 0
+					while: { if: notdone { i < (_hashdiffs length) } } do: {
+						hv <- basehash + (_hashdiffs get: i)
+						trunc <- hv % (_buckets length)
+						if: trunc < 0 { trunc <- 0 - trunc }
+						bucket <- (_buckets get: trunc)
+						if: (bucket empty?) {
+							_size <- _size + 1
+							_buckets set: trunc (_makeBucket: key val)
+							notdone <- false
+						} else: {
+							if: bucket = key {
+								bucket v!: val
+								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?)) {
+								set: (el k) (el v)
+							}
+						}
+						set: key val
+					}
+					self
+				}
+
+				foreach <- :fun {
+					foreach: _buckets :idx el {
+						if: (not: (el empty?)) {
+							fun: (el k) (el v)
+						}
+					}
+				}
+			}
+		}
+
+		main <- {
+			d <- hash
+			d set: "foo" "bar"
+			d set: "baz" "qux"
+			i <- 0
+			while: { i < 32 } do: {
+				d set: (string: i) "blah " . (string: i)
+				i <- i + 1
+			}
+			foreach: d :k v {
+				print: "k: " . k . ", v: " . v . "\n"
+			}
+			0
+		}
 	}
 }