1 files changed, 311 insertions, 0 deletions
diff --git a/vendor/github.com/lann/ps/map.go b/vendor/github.com/lann/ps/map.go
new file mode 100644
index 0000000..192daec
--- /dev/null
+++ b/vendor/github.com/lann/ps/map.go
@@ -0,0 +1,311 @@
+// Fully persistent data structures. A persistent data structure is a data
+// structure that always preserves the previous version of itself when
+// it is modified. Such data structures are effectively immutable,
+// as their operations do not update the structure in-place, but instead
+// always yield a new structure.
+//
+// Persistent
+// data structures typically share structure among themselves.  This allows
+// operations to avoid copying the entire data structure.
+package ps
+
+import (
+	"bytes"
+	"fmt"
+)
+
+// Any is a shorthand for Go's verbose interface{} type.
+type Any interface{}
+
+// A Map associates unique keys (type string) with values (type Any).
+type Map interface {
+	// IsNil returns true if the Map is empty
+	IsNil() bool
+
+	// Set returns a new map in which key and value are associated.
+	// If the key didn't exist before, it's created; otherwise, the
+	// associated value is changed.
+	// This operation is O(log N) in the number of keys.
+	Set(key string, value Any) Map
+
+	// Delete returns a new map with the association for key, if any, removed.
+	// This operation is O(log N) in the number of keys.
+	Delete(key string) Map
+
+	// Lookup returns the value associated with a key, if any.  If the key
+	// exists, the second return value is true; otherwise, false.
+	// This operation is O(log N) in the number of keys.
+	Lookup(key string) (Any, bool)
+
+	// Size returns the number of key value pairs in the map.
+	// This takes O(1) time.
+	Size() int
+
+	// ForEach executes a callback on each key value pair in the map.
+	ForEach(f func(key string, val Any))
+
+	// Keys returns a slice with all keys in this map.
+	// This operation is O(N) in the number of keys.
+	Keys() []string
+
+	String() string
+}
+
+// Immutable (i.e. persistent) associative array
+const childCount = 8
+const shiftSize = 3
+
+type tree struct {
+	count    int
+	hash     uint64 // hash of the key (used for tree balancing)
+	key      string
+	value    Any
+	children [childCount]*tree
+}
+
+var nilMap = &tree{}
+
+// Recursively set nilMap's subtrees to point at itself.
+// This eliminates all nil pointers in the map structure.
+// All map nodes are created by cloning this structure so
+// they avoid the problem too.
+func init() {
+	for i := range nilMap.children {
+		nilMap.children[i] = nilMap
+	}
+}
+
+// NewMap allocates a new, persistent map from strings to values of
+// any type.
+// This is currently implemented as a path-copying binary tree.
+func NewMap() Map {
+	return nilMap
+}
+
+func (self *tree) IsNil() bool {
+	return self == nilMap
+}
+
+// clone returns an exact duplicate of a tree node
+func (self *tree) clone() *tree {
+	var m tree
+	m = *self
+	return &m
+}
+
+// constants for FNV-1a hash algorithm
+const (
+	offset64 uint64 = 14695981039346656037
+	prime64  uint64 = 1099511628211
+)
+
+// hashKey returns a hash code for a given string
+func hashKey(key string) uint64 {
+	hash := offset64
+	for _, codepoint := range key {
+		hash ^= uint64(codepoint)
+		hash *= prime64
+	}
+	return hash
+}
+
+// Set returns a new map similar to this one but with key and value
+// associated.  If the key didn't exist, it's created; otherwise, the
+// associated value is changed.
+func (self *tree) Set(key string, value Any) Map {
+	hash := hashKey(key)
+	return setLowLevel(self, hash, hash, key, value)
+}
+
+func setLowLevel(self *tree, partialHash, hash uint64, key string, value Any) *tree {
+	if self.IsNil() { // an empty tree is easy
+		m := self.clone()
+		m.count = 1
+		m.hash = hash
+		m.key = key
+		m.value = value
+		return m
+	}
+
+	if hash != self.hash {
+		m := self.clone()
+		i := partialHash % childCount
+		m.children[i] = setLowLevel(self.children[i], partialHash>>shiftSize, hash, key, value)
+		recalculateCount(m)
+		return m
+	}
+
+	// replacing a key's previous value
+	m := self.clone()
+	m.value = value
+	return m
+}
+
+// modifies a map by recalculating its key count based on the counts
+// of its subtrees
+func recalculateCount(m *tree) {
+	count := 0
+	for _, t := range m.children {
+		count += t.Size()
+	}
+	m.count = count + 1 // add one to count ourself
+}
+
+func (m *tree) Delete(key string) Map {
+	hash := hashKey(key)
+	newMap, _ := deleteLowLevel(m, hash, hash)
+	return newMap
+}
+
+func deleteLowLevel(self *tree, partialHash, hash uint64) (*tree, bool) {
+	// empty trees are easy
+	if self.IsNil() {
+		return self, false
+	}
+
+	if hash != self.hash {
+		i := partialHash % childCount
+		child, found := deleteLowLevel(self.children[i], partialHash>>shiftSize, hash)
+		if !found {
+			return self, false
+		}
+		newMap := self.clone()
+		newMap.children[i] = child
+		recalculateCount(newMap)
+		return newMap, true // ? this wasn't in the original code
+	}
+
+	// we must delete our own node
+	if self.isLeaf() { // we have no children
+		return nilMap, true
+	}
+	/*
+	   if self.subtreeCount() == 1 { // only one subtree
+	       for _, t := range self.children {
+	           if t != nilMap {
+	               return t, true
+	           }
+	       }
+	       panic("Tree with 1 subtree actually had no subtrees")
+	   }
+	*/
+
+	// find a node to replace us
+	i := -1
+	size := -1
+	for j, t := range self.children {
+		if t.Size() > size {
+			i = j
+			size = t.Size()
+		}
+	}
+
+	// make chosen leaf smaller
+	replacement, child := self.children[i].deleteLeftmost()
+	newMap := replacement.clone()
+	for j := range self.children {
+		if j == i {
+			newMap.children[j] = child
+		} else {
+			newMap.children[j] = self.children[j]
+		}
+	}
+	recalculateCount(newMap)
+	return newMap, true
+}
+
+// delete the leftmost node in a tree returning the node that
+// was deleted and the tree left over after its deletion
+func (m *tree) deleteLeftmost() (*tree, *tree) {
+	if m.isLeaf() {
+		return m, nilMap
+	}
+
+	for i, t := range m.children {
+		if t != nilMap {
+			deleted, child := t.deleteLeftmost()
+			newMap := m.clone()
+			newMap.children[i] = child
+			recalculateCount(newMap)
+			return deleted, newMap
+		}
+	}
+	panic("Tree isn't a leaf but also had no children. How does that happen?")
+}
+
+// isLeaf returns true if this is a leaf node
+func (m *tree) isLeaf() bool {
+	return m.Size() == 1
+}
+
+// returns the number of child subtrees we have
+func (m *tree) subtreeCount() int {
+	count := 0
+	for _, t := range m.children {
+		if t != nilMap {
+			count++
+		}
+	}
+	return count
+}
+
+func (m *tree) Lookup(key string) (Any, bool) {
+	hash := hashKey(key)
+	return lookupLowLevel(m, hash, hash)
+}
+
+func lookupLowLevel(self *tree, partialHash, hash uint64) (Any, bool) {
+	if self.IsNil() { // an empty tree is easy
+		return nil, false
+	}
+
+	if hash != self.hash {
+		i := partialHash % childCount
+		return lookupLowLevel(self.children[i], partialHash>>shiftSize, hash)
+	}
+
+	// we found it
+	return self.value, true
+}
+
+func (m *tree) Size() int {
+	return m.count
+}
+
+func (m *tree) ForEach(f func(key string, val Any)) {
+	if m.IsNil() {
+		return
+	}
+
+	// ourself
+	f(m.key, m.value)
+
+	// children
+	for _, t := range m.children {
+		if t != nilMap {
+			t.ForEach(f)
+		}
+	}
+}
+
+func (m *tree) Keys() []string {
+	keys := make([]string, m.Size())
+	i := 0
+	m.ForEach(func(k string, v Any) {
+		keys[i] = k
+		i++
+	})
+	return keys
+}
+
+// make it easier to display maps for debugging
+func (m *tree) String() string {
+	keys := m.Keys()
+	buf := bytes.NewBufferString("{")
+	for _, key := range keys {
+		val, _ := m.Lookup(key)
+		fmt.Fprintf(buf, "%s: %s, ", key, val)
+	}
+	fmt.Fprintf(buf, "}\n")
+	return buf.String()
+}