feat: connect to spicedb

12 files changed, 1423 insertions, 0 deletions

diff --git a/vendor/github.com/emirpasic/gods/LICENSE b/vendor/github.com/emirpasic/gods/LICENSE
new file mode 100644
index 0000000..e5e449b
--- /dev/null
+++ b/vendor/github.com/emirpasic/gods/LICENSE
@@ -0,0 +1,41 @@
+Copyright (c) 2015, Emir Pasic
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+* Redistributions of source code must retain the above copyright notice, this
+  list of conditions and the following disclaimer.
+
+* Redistributions in binary form must reproduce the above copyright notice,
+  this list of conditions and the following disclaimer in the documentation
+  and/or other materials provided with the distribution.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+-------------------------------------------------------------------------------
+
+AVL Tree:
+
+Copyright (c) 2017 Benjamin Scher Purcell <benjapurcell@gmail.com>
+
+Permission to use, copy, modify, and distribute this software for any
+purpose with or without fee is hereby granted, provided that the above
+copyright notice and this permission notice appear in all copies.
+
+THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
diff --git a/vendor/github.com/emirpasic/gods/containers/containers.go b/vendor/github.com/emirpasic/gods/containers/containers.go
new file mode 100644
index 0000000..a512a3c
--- /dev/null
+++ b/vendor/github.com/emirpasic/gods/containers/containers.go
@@ -0,0 +1,36 @@
+// Copyright (c) 2015, Emir Pasic. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package containers provides core interfaces and functions for data structures.
+//
+// Container is the base interface for all data structures to implement.
+//
+// Iterators provide stateful iterators.
+//
+// Enumerable provides Ruby inspired (each, select, map, find, any?, etc.) container functions.
+//
+// Serialization provides serializers (marshalers) and deserializers (unmarshalers).
+package containers
+
+import "github.com/emirpasic/gods/utils"
+
+// Container is base interface that all data structures implement.
+type Container interface {
+	Empty() bool
+	Size() int
+	Clear()
+	Values() []interface{}
+	String() string
+}
+
+// GetSortedValues returns sorted container's elements with respect to the passed comparator.
+// Does not affect the ordering of elements within the container.
+func GetSortedValues(container Container, comparator utils.Comparator) []interface{} {
+	values := container.Values()
+	if len(values) < 2 {
+		return values
+	}
+	utils.Sort(values, comparator)
+	return values
+}
diff --git a/vendor/github.com/emirpasic/gods/containers/enumerable.go b/vendor/github.com/emirpasic/gods/containers/enumerable.go
new file mode 100644
index 0000000..7066005
--- /dev/null
+++ b/vendor/github.com/emirpasic/gods/containers/enumerable.go
@@ -0,0 +1,57 @@
+// Copyright (c) 2015, Emir Pasic. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package containers
+
+// EnumerableWithIndex provides functions for ordered containers whose values can be fetched by an index.
+type EnumerableWithIndex interface {
+	// Each calls the given function once for each element, passing that element's index and value.
+	Each(func(index int, value interface{}))
+
+	// Map invokes the given function once for each element and returns a
+	// container containing the values returned by the given function.
+	// Map(func(index int, value interface{}) interface{}) Container
+
+	// Select returns a new container containing all elements for which the given function returns a true value.
+	// Select(func(index int, value interface{}) bool) Container
+
+	// Any passes each element of the container to the given function and
+	// returns true if the function ever returns true for any element.
+	Any(func(index int, value interface{}) bool) bool
+
+	// All passes each element of the container to the given function and
+	// returns true if the function returns true for all elements.
+	All(func(index int, value interface{}) bool) bool
+
+	// Find passes each element of the container to the given function and returns
+	// the first (index,value) for which the function is true or -1,nil otherwise
+	// if no element matches the criteria.
+	Find(func(index int, value interface{}) bool) (int, interface{})
+}
+
+// EnumerableWithKey provides functions for ordered containers whose values whose elements are key/value pairs.
+type EnumerableWithKey interface {
+	// Each calls the given function once for each element, passing that element's key and value.
+	Each(func(key interface{}, value interface{}))
+
+	// Map invokes the given function once for each element and returns a container
+	// containing the values returned by the given function as key/value pairs.
+	// Map(func(key interface{}, value interface{}) (interface{}, interface{})) Container
+
+	// Select returns a new container containing all elements for which the given function returns a true value.
+	// Select(func(key interface{}, value interface{}) bool) Container
+
+	// Any passes each element of the container to the given function and
+	// returns true if the function ever returns true for any element.
+	Any(func(key interface{}, value interface{}) bool) bool
+
+	// All passes each element of the container to the given function and
+	// returns true if the function returns true for all elements.
+	All(func(key interface{}, value interface{}) bool) bool
+
+	// Find passes each element of the container to the given function and returns
+	// the first (key,value) for which the function is true or nil,nil otherwise if no element
+	// matches the criteria.
+	Find(func(key interface{}, value interface{}) bool) (interface{}, interface{})
+}
diff --git a/vendor/github.com/emirpasic/gods/containers/iterator.go b/vendor/github.com/emirpasic/gods/containers/iterator.go
new file mode 100644
index 0000000..73994ec
--- /dev/null
+++ b/vendor/github.com/emirpasic/gods/containers/iterator.go
@@ -0,0 +1,133 @@
+// Copyright (c) 2015, Emir Pasic. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package containers
+
+// IteratorWithIndex is stateful iterator for ordered containers whose values can be fetched by an index.
+type IteratorWithIndex interface {
+	// Next moves the iterator to the next element and returns true if there was a next element in the container.
+	// If Next() returns true, then next element's index and value can be retrieved by Index() and Value().
+	// If Next() was called for the first time, then it will point the iterator to the first element if it exists.
+	// Modifies the state of the iterator.
+	Next() bool
+
+	// Value returns the current element's value.
+	// Does not modify the state of the iterator.
+	Value() interface{}
+
+	// Index returns the current element's index.
+	// Does not modify the state of the iterator.
+	Index() int
+
+	// Begin resets the iterator to its initial state (one-before-first)
+	// Call Next() to fetch the first element if any.
+	Begin()
+
+	// First moves the iterator to the first element and returns true if there was a first element in the container.
+	// If First() returns true, then first element's index and value can be retrieved by Index() and Value().
+	// Modifies the state of the iterator.
+	First() bool
+
+	// NextTo moves the iterator to the next element from current position that satisfies the condition given by the
+	// passed function, and returns true if there was a next element in the container.
+	// If NextTo() returns true, then next element's index and value can be retrieved by Index() and Value().
+	// Modifies the state of the iterator.
+	NextTo(func(index int, value interface{}) bool) bool
+}
+
+// IteratorWithKey is a stateful iterator for ordered containers whose elements are key value pairs.
+type IteratorWithKey interface {
+	// Next moves the iterator to the next element and returns true if there was a next element in the container.
+	// If Next() returns true, then next element's key and value can be retrieved by Key() and Value().
+	// If Next() was called for the first time, then it will point the iterator to the first element if it exists.
+	// Modifies the state of the iterator.
+	Next() bool
+
+	// Value returns the current element's value.
+	// Does not modify the state of the iterator.
+	Value() interface{}
+
+	// Key returns the current element's key.
+	// Does not modify the state of the iterator.
+	Key() interface{}
+
+	// Begin resets the iterator to its initial state (one-before-first)
+	// Call Next() to fetch the first element if any.
+	Begin()
+
+	// First moves the iterator to the first element and returns true if there was a first element in the container.
+	// If First() returns true, then first element's key and value can be retrieved by Key() and Value().
+	// Modifies the state of the iterator.
+	First() bool
+
+	// NextTo moves the iterator to the next element from current position that satisfies the condition given by the
+	// passed function, and returns true if there was a next element in the container.
+	// If NextTo() returns true, then next element's key and value can be retrieved by Key() and Value().
+	// Modifies the state of the iterator.
+	NextTo(func(key interface{}, value interface{}) bool) bool
+}
+
+// ReverseIteratorWithIndex is stateful iterator for ordered containers whose values can be fetched by an index.
+//
+// Essentially it is the same as IteratorWithIndex, but provides additional:
+//
+// Prev() function to enable traversal in reverse
+//
+// Last() function to move the iterator to the last element.
+//
+// End() function to move the iterator past the last element (one-past-the-end).
+type ReverseIteratorWithIndex interface {
+	// Prev moves the iterator to the previous element and returns true if there was a previous element in the container.
+	// If Prev() returns true, then previous element's index and value can be retrieved by Index() and Value().
+	// Modifies the state of the iterator.
+	Prev() bool
+
+	// End moves the iterator past the last element (one-past-the-end).
+	// Call Prev() to fetch the last element if any.
+	End()
+
+	// Last moves the iterator to the last element and returns true if there was a last element in the container.
+	// If Last() returns true, then last element's index and value can be retrieved by Index() and Value().
+	// Modifies the state of the iterator.
+	Last() bool
+
+	// PrevTo moves the iterator to the previous element from current position that satisfies the condition given by the
+	// passed function, and returns true if there was a next element in the container.
+	// If PrevTo() returns true, then next element's index and value can be retrieved by Index() and Value().
+	// Modifies the state of the iterator.
+	PrevTo(func(index int, value interface{}) bool) bool
+
+	IteratorWithIndex
+}
+
+// ReverseIteratorWithKey is a stateful iterator for ordered containers whose elements are key value pairs.
+//
+// Essentially it is the same as IteratorWithKey, but provides additional:
+//
+// Prev() function to enable traversal in reverse
+//
+// Last() function to move the iterator to the last element.
+type ReverseIteratorWithKey interface {
+	// Prev moves the iterator to the previous element and returns true if there was a previous element in the container.
+	// If Prev() returns true, then previous element's key and value can be retrieved by Key() and Value().
+	// Modifies the state of the iterator.
+	Prev() bool
+
+	// End moves the iterator past the last element (one-past-the-end).
+	// Call Prev() to fetch the last element if any.
+	End()
+
+	// Last moves the iterator to the last element and returns true if there was a last element in the container.
+	// If Last() returns true, then last element's key and value can be retrieved by Key() and Value().
+	// Modifies the state of the iterator.
+	Last() bool
+
+	// PrevTo moves the iterator to the previous element from current position that satisfies the condition given by the
+	// passed function, and returns true if there was a next element in the container.
+	// If PrevTo() returns true, then next element's key and value can be retrieved by Key() and Value().
+	// Modifies the state of the iterator.
+	PrevTo(func(key interface{}, value interface{}) bool) bool
+
+	IteratorWithKey
+}
diff --git a/vendor/github.com/emirpasic/gods/containers/serialization.go b/vendor/github.com/emirpasic/gods/containers/serialization.go
new file mode 100644
index 0000000..fd9cbe2
--- /dev/null
+++ b/vendor/github.com/emirpasic/gods/containers/serialization.go
@@ -0,0 +1,21 @@
+// Copyright (c) 2015, Emir Pasic. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package containers
+
+// JSONSerializer provides JSON serialization
+type JSONSerializer interface {
+	// ToJSON outputs the JSON representation of containers's elements.
+	ToJSON() ([]byte, error)
+	// MarshalJSON @implements json.Marshaler
+	MarshalJSON() ([]byte, error)
+}
+
+// JSONDeserializer provides JSON deserialization
+type JSONDeserializer interface {
+	// FromJSON populates containers's elements from the input JSON representation.
+	FromJSON([]byte) error
+	// UnmarshalJSON @implements json.Unmarshaler
+	UnmarshalJSON([]byte) error
+}
diff --git a/vendor/github.com/emirpasic/gods/trees/redblacktree/iterator.go b/vendor/github.com/emirpasic/gods/trees/redblacktree/iterator.go
new file mode 100644
index 0000000..e39da7d
--- /dev/null
+++ b/vendor/github.com/emirpasic/gods/trees/redblacktree/iterator.go
@@ -0,0 +1,190 @@
+// Copyright (c) 2015, Emir Pasic. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package redblacktree
+
+import "github.com/emirpasic/gods/containers"
+
+// Assert Iterator implementation
+var _ containers.ReverseIteratorWithKey = (*Iterator)(nil)
+
+// Iterator holding the iterator's state
+type Iterator struct {
+	tree     *Tree
+	node     *Node
+	position position
+}
+
+type position byte
+
+const (
+	begin, between, end position = 0, 1, 2
+)
+
+// Iterator returns a stateful iterator whose elements are key/value pairs.
+func (tree *Tree) Iterator() Iterator {
+	return Iterator{tree: tree, node: nil, position: begin}
+}
+
+// IteratorAt returns a stateful iterator whose elements are key/value pairs that is initialised at a particular node.
+func (tree *Tree) IteratorAt(node *Node) Iterator {
+	return Iterator{tree: tree, node: node, position: between}
+}
+
+// Next moves the iterator to the next element and returns true if there was a next element in the container.
+// If Next() returns true, then next element's key and value can be retrieved by Key() and Value().
+// If Next() was called for the first time, then it will point the iterator to the first element if it exists.
+// Modifies the state of the iterator.
+func (iterator *Iterator) Next() bool {
+	if iterator.position == end {
+		goto end
+	}
+	if iterator.position == begin {
+		left := iterator.tree.Left()
+		if left == nil {
+			goto end
+		}
+		iterator.node = left
+		goto between
+	}
+	if iterator.node.Right != nil {
+		iterator.node = iterator.node.Right
+		for iterator.node.Left != nil {
+			iterator.node = iterator.node.Left
+		}
+		goto between
+	}
+	for iterator.node.Parent != nil {
+		node := iterator.node
+		iterator.node = iterator.node.Parent
+		if node == iterator.node.Left {
+			goto between
+		}
+	}
+
+end:
+	iterator.node = nil
+	iterator.position = end
+	return false
+
+between:
+	iterator.position = between
+	return true
+}
+
+// Prev moves the iterator to the previous element and returns true if there was a previous element in the container.
+// If Prev() returns true, then previous element's key and value can be retrieved by Key() and Value().
+// Modifies the state of the iterator.
+func (iterator *Iterator) Prev() bool {
+	if iterator.position == begin {
+		goto begin
+	}
+	if iterator.position == end {
+		right := iterator.tree.Right()
+		if right == nil {
+			goto begin
+		}
+		iterator.node = right
+		goto between
+	}
+	if iterator.node.Left != nil {
+		iterator.node = iterator.node.Left
+		for iterator.node.Right != nil {
+			iterator.node = iterator.node.Right
+		}
+		goto between
+	}
+	for iterator.node.Parent != nil {
+		node := iterator.node
+		iterator.node = iterator.node.Parent
+		if node == iterator.node.Right {
+			goto between
+		}
+	}
+
+begin:
+	iterator.node = nil
+	iterator.position = begin
+	return false
+
+between:
+	iterator.position = between
+	return true
+}
+
+// Value returns the current element's value.
+// Does not modify the state of the iterator.
+func (iterator *Iterator) Value() interface{} {
+	return iterator.node.Value
+}
+
+// Key returns the current element's key.
+// Does not modify the state of the iterator.
+func (iterator *Iterator) Key() interface{} {
+	return iterator.node.Key
+}
+
+// Node returns the current element's node.
+// Does not modify the state of the iterator.
+func (iterator *Iterator) Node() *Node {
+	return iterator.node
+}
+
+// Begin resets the iterator to its initial state (one-before-first)
+// Call Next() to fetch the first element if any.
+func (iterator *Iterator) Begin() {
+	iterator.node = nil
+	iterator.position = begin
+}
+
+// End moves the iterator past the last element (one-past-the-end).
+// Call Prev() to fetch the last element if any.
+func (iterator *Iterator) End() {
+	iterator.node = nil
+	iterator.position = end
+}
+
+// First moves the iterator to the first element and returns true if there was a first element in the container.
+// If First() returns true, then first element's key and value can be retrieved by Key() and Value().
+// Modifies the state of the iterator
+func (iterator *Iterator) First() bool {
+	iterator.Begin()
+	return iterator.Next()
+}
+
+// Last moves the iterator to the last element and returns true if there was a last element in the container.
+// If Last() returns true, then last element's key and value can be retrieved by Key() and Value().
+// Modifies the state of the iterator.
+func (iterator *Iterator) Last() bool {
+	iterator.End()
+	return iterator.Prev()
+}
+
+// NextTo moves the iterator to the next element from current position that satisfies the condition given by the
+// passed function, and returns true if there was a next element in the container.
+// If NextTo() returns true, then next element's key and value can be retrieved by Key() and Value().
+// Modifies the state of the iterator.
+func (iterator *Iterator) NextTo(f func(key interface{}, value interface{}) bool) bool {
+	for iterator.Next() {
+		key, value := iterator.Key(), iterator.Value()
+		if f(key, value) {
+			return true
+		}
+	}
+	return false
+}
+
+// PrevTo moves the iterator to the previous element from current position that satisfies the condition given by the
+// passed function, and returns true if there was a next element in the container.
+// If PrevTo() returns true, then next element's key and value can be retrieved by Key() and Value().
+// Modifies the state of the iterator.
+func (iterator *Iterator) PrevTo(f func(key interface{}, value interface{}) bool) bool {
+	for iterator.Prev() {
+		key, value := iterator.Key(), iterator.Value()
+		if f(key, value) {
+			return true
+		}
+	}
+	return false
+}
diff --git a/vendor/github.com/emirpasic/gods/trees/redblacktree/redblacktree.go b/vendor/github.com/emirpasic/gods/trees/redblacktree/redblacktree.go
new file mode 100644
index 0000000..b335e3d
--- /dev/null
+++ b/vendor/github.com/emirpasic/gods/trees/redblacktree/redblacktree.go
@@ -0,0 +1,548 @@
+// Copyright (c) 2015, Emir Pasic. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package redblacktree implements a red-black tree.
+//
+// Used by TreeSet and TreeMap.
+//
+// Structure is not thread safe.
+//
+// References: http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
+package redblacktree
+
+import (
+	"fmt"
+	"github.com/emirpasic/gods/trees"
+	"github.com/emirpasic/gods/utils"
+)
+
+// Assert Tree implementation
+var _ trees.Tree = (*Tree)(nil)
+
+type color bool
+
+const (
+	black, red color = true, false
+)
+
+// Tree holds elements of the red-black tree
+type Tree struct {
+	Root       *Node
+	size       int
+	Comparator utils.Comparator
+}
+
+// Node is a single element within the tree
+type Node struct {
+	Key    interface{}
+	Value  interface{}
+	color  color
+	Left   *Node
+	Right  *Node
+	Parent *Node
+}
+
+// NewWith instantiates a red-black tree with the custom comparator.
+func NewWith(comparator utils.Comparator) *Tree {
+	return &Tree{Comparator: comparator}
+}
+
+// NewWithIntComparator instantiates a red-black tree with the IntComparator, i.e. keys are of type int.
+func NewWithIntComparator() *Tree {
+	return &Tree{Comparator: utils.IntComparator}
+}
+
+// NewWithStringComparator instantiates a red-black tree with the StringComparator, i.e. keys are of type string.
+func NewWithStringComparator() *Tree {
+	return &Tree{Comparator: utils.StringComparator}
+}
+
+// Put inserts node into the tree.
+// Key should adhere to the comparator's type assertion, otherwise method panics.
+func (tree *Tree) Put(key interface{}, value interface{}) {
+	var insertedNode *Node
+	if tree.Root == nil {
+		// Assert key is of comparator's type for initial tree
+		tree.Comparator(key, key)
+		tree.Root = &Node{Key: key, Value: value, color: red}
+		insertedNode = tree.Root
+	} else {
+		node := tree.Root
+		loop := true
+		for loop {
+			compare := tree.Comparator(key, node.Key)
+			switch {
+			case compare == 0:
+				node.Key = key
+				node.Value = value
+				return
+			case compare < 0:
+				if node.Left == nil {
+					node.Left = &Node{Key: key, Value: value, color: red}
+					insertedNode = node.Left
+					loop = false
+				} else {
+					node = node.Left
+				}
+			case compare > 0:
+				if node.Right == nil {
+					node.Right = &Node{Key: key, Value: value, color: red}
+					insertedNode = node.Right
+					loop = false
+				} else {
+					node = node.Right
+				}
+			}
+		}
+		insertedNode.Parent = node
+	}
+	tree.insertCase1(insertedNode)
+	tree.size++
+}
+
+// Get searches the node in the tree by key and returns its value or nil if key is not found in tree.
+// Second return parameter is true if key was found, otherwise false.
+// Key should adhere to the comparator's type assertion, otherwise method panics.
+func (tree *Tree) Get(key interface{}) (value interface{}, found bool) {
+	node := tree.lookup(key)
+	if node != nil {
+		return node.Value, true
+	}
+	return nil, false
+}
+
+// GetNode searches the node in the tree by key and returns its node or nil if key is not found in tree.
+// Key should adhere to the comparator's type assertion, otherwise method panics.
+func (tree *Tree) GetNode(key interface{}) *Node {
+	return tree.lookup(key)
+}
+
+// Remove remove the node from the tree by key.
+// Key should adhere to the comparator's type assertion, otherwise method panics.
+func (tree *Tree) Remove(key interface{}) {
+	var child *Node
+	node := tree.lookup(key)
+	if node == nil {
+		return
+	}
+	if node.Left != nil && node.Right != nil {
+		pred := node.Left.maximumNode()
+		node.Key = pred.Key
+		node.Value = pred.Value
+		node = pred
+	}
+	if node.Left == nil || node.Right == nil {
+		if node.Right == nil {
+			child = node.Left
+		} else {
+			child = node.Right
+		}
+		if node.color == black {
+			node.color = nodeColor(child)
+			tree.deleteCase1(node)
+		}
+		tree.replaceNode(node, child)
+		if node.Parent == nil && child != nil {
+			child.color = black
+		}
+	}
+	tree.size--
+}
+
+// Empty returns true if tree does not contain any nodes
+func (tree *Tree) Empty() bool {
+	return tree.size == 0
+}
+
+// Size returns number of nodes in the tree.
+func (tree *Tree) Size() int {
+	return tree.size
+}
+
+// Size returns the number of elements stored in the subtree.
+// Computed dynamically on each call, i.e. the subtree is traversed to count the number of the nodes.
+func (node *Node) Size() int {
+	if node == nil {
+		return 0
+	}
+	size := 1
+	if node.Left != nil {
+		size += node.Left.Size()
+	}
+	if node.Right != nil {
+		size += node.Right.Size()
+	}
+	return size
+}
+
+// Keys returns all keys in-order
+func (tree *Tree) Keys() []interface{} {
+	keys := make([]interface{}, tree.size)
+	it := tree.Iterator()
+	for i := 0; it.Next(); i++ {
+		keys[i] = it.Key()
+	}
+	return keys
+}
+
+// Values returns all values in-order based on the key.
+func (tree *Tree) Values() []interface{} {
+	values := make([]interface{}, tree.size)
+	it := tree.Iterator()
+	for i := 0; it.Next(); i++ {
+		values[i] = it.Value()
+	}
+	return values
+}
+
+// Left returns the left-most (min) node or nil if tree is empty.
+func (tree *Tree) Left() *Node {
+	var parent *Node
+	current := tree.Root
+	for current != nil {
+		parent = current
+		current = current.Left
+	}
+	return parent
+}
+
+// Right returns the right-most (max) node or nil if tree is empty.
+func (tree *Tree) Right() *Node {
+	var parent *Node
+	current := tree.Root
+	for current != nil {
+		parent = current
+		current = current.Right
+	}
+	return parent
+}
+
+// Floor Finds floor node of the input key, return the floor node or nil if no floor is found.
+// Second return parameter is true if floor was found, otherwise false.
+//
+// Floor node is defined as the largest node that is smaller than or equal to the given node.
+// A floor node may not be found, either because the tree is empty, or because
+// all nodes in the tree are larger than the given node.
+//
+// Key should adhere to the comparator's type assertion, otherwise method panics.
+func (tree *Tree) Floor(key interface{}) (floor *Node, found bool) {
+	found = false
+	node := tree.Root
+	for node != nil {
+		compare := tree.Comparator(key, node.Key)
+		switch {
+		case compare == 0:
+			return node, true
+		case compare < 0:
+			node = node.Left
+		case compare > 0:
+			floor, found = node, true
+			node = node.Right
+		}
+	}
+	if found {
+		return floor, true
+	}
+	return nil, false
+}
+
+// Ceiling finds ceiling node of the input key, return the ceiling node or nil if no ceiling is found.
+// Second return parameter is true if ceiling was found, otherwise false.
+//
+// Ceiling node is defined as the smallest node that is larger than or equal to the given node.
+// A ceiling node may not be found, either because the tree is empty, or because
+// all nodes in the tree are smaller than the given node.
+//
+// Key should adhere to the comparator's type assertion, otherwise method panics.
+func (tree *Tree) Ceiling(key interface{}) (ceiling *Node, found bool) {
+	found = false
+	node := tree.Root
+	for node != nil {
+		compare := tree.Comparator(key, node.Key)
+		switch {
+		case compare == 0:
+			return node, true
+		case compare < 0:
+			ceiling, found = node, true
+			node = node.Left
+		case compare > 0:
+			node = node.Right
+		}
+	}
+	if found {
+		return ceiling, true
+	}
+	return nil, false
+}
+
+// Clear removes all nodes from the tree.
+func (tree *Tree) Clear() {
+	tree.Root = nil
+	tree.size = 0
+}
+
+// String returns a string representation of container
+func (tree *Tree) String() string {
+	str := "RedBlackTree\n"
+	if !tree.Empty() {
+		output(tree.Root, "", true, &str)
+	}
+	return str
+}
+
+func (node *Node) String() string {
+	return fmt.Sprintf("%v", node.Key)
+}
+
+func output(node *Node, prefix string, isTail bool, str *string) {
+	if node.Right != nil {
+		newPrefix := prefix
+		if isTail {
+			newPrefix += "│   "
+		} else {
+			newPrefix += "    "
+		}
+		output(node.Right, newPrefix, false, str)
+	}
+	*str += prefix
+	if isTail {
+		*str += "└── "
+	} else {
+		*str += "┌── "
+	}
+	*str += node.String() + "\n"
+	if node.Left != nil {
+		newPrefix := prefix
+		if isTail {
+			newPrefix += "    "
+		} else {
+			newPrefix += "│   "
+		}
+		output(node.Left, newPrefix, true, str)
+	}
+}
+
+func (tree *Tree) lookup(key interface{}) *Node {
+	node := tree.Root
+	for node != nil {
+		compare := tree.Comparator(key, node.Key)
+		switch {
+		case compare == 0:
+			return node
+		case compare < 0:
+			node = node.Left
+		case compare > 0:
+			node = node.Right
+		}
+	}
+	return nil
+}
+
+func (node *Node) grandparent() *Node {
+	if node != nil && node.Parent != nil {
+		return node.Parent.Parent
+	}
+	return nil
+}
+
+func (node *Node) uncle() *Node {
+	if node == nil || node.Parent == nil || node.Parent.Parent == nil {
+		return nil
+	}
+	return node.Parent.sibling()
+}
+
+func (node *Node) sibling() *Node {
+	if node == nil || node.Parent == nil {
+		return nil
+	}
+	if node == node.Parent.Left {
+		return node.Parent.Right
+	}
+	return node.Parent.Left
+}
+
+func (tree *Tree) rotateLeft(node *Node) {
+	right := node.Right
+	tree.replaceNode(node, right)
+	node.Right = right.Left
+	if right.Left != nil {
+		right.Left.Parent = node
+	}
+	right.Left = node
+	node.Parent = right
+}
+
+func (tree *Tree) rotateRight(node *Node) {
+	left := node.Left
+	tree.replaceNode(node, left)
+	node.Left = left.Right
+	if left.Right != nil {
+		left.Right.Parent = node
+	}
+	left.Right = node
+	node.Parent = left
+}
+
+func (tree *Tree) replaceNode(old *Node, new *Node) {
+	if old.Parent == nil {
+		tree.Root = new
+	} else {
+		if old == old.Parent.Left {
+			old.Parent.Left = new
+		} else {
+			old.Parent.Right = new
+		}
+	}
+	if new != nil {
+		new.Parent = old.Parent
+	}
+}
+
+func (tree *Tree) insertCase1(node *Node) {
+	if node.Parent == nil {
+		node.color = black
+	} else {
+		tree.insertCase2(node)
+	}
+}
+
+func (tree *Tree) insertCase2(node *Node) {
+	if nodeColor(node.Parent) == black {
+		return
+	}
+	tree.insertCase3(node)
+}
+
+func (tree *Tree) insertCase3(node *Node) {
+	uncle := node.uncle()
+	if nodeColor(uncle) == red {
+		node.Parent.color = black
+		uncle.color = black
+		node.grandparent().color = red
+		tree.insertCase1(node.grandparent())
+	} else {
+		tree.insertCase4(node)
+	}
+}
+
+func (tree *Tree) insertCase4(node *Node) {
+	grandparent := node.grandparent()
+	if node == node.Parent.Right && node.Parent == grandparent.Left {
+		tree.rotateLeft(node.Parent)
+		node = node.Left
+	} else if node == node.Parent.Left && node.Parent == grandparent.Right {
+		tree.rotateRight(node.Parent)
+		node = node.Right
+	}
+	tree.insertCase5(node)
+}
+
+func (tree *Tree) insertCase5(node *Node) {
+	node.Parent.color = black
+	grandparent := node.grandparent()
+	grandparent.color = red
+	if node == node.Parent.Left && node.Parent == grandparent.Left {
+		tree.rotateRight(grandparent)
+	} else if node == node.Parent.Right && node.Parent == grandparent.Right {
+		tree.rotateLeft(grandparent)
+	}
+}
+
+func (node *Node) maximumNode() *Node {
+	if node == nil {
+		return nil
+	}
+	for node.Right != nil {
+		node = node.Right
+	}
+	return node
+}
+
+func (tree *Tree) deleteCase1(node *Node) {
+	if node.Parent == nil {
+		return
+	}
+	tree.deleteCase2(node)
+}
+
+func (tree *Tree) deleteCase2(node *Node) {
+	sibling := node.sibling()
+	if nodeColor(sibling) == red {
+		node.Parent.color = red
+		sibling.color = black
+		if node == node.Parent.Left {
+			tree.rotateLeft(node.Parent)
+		} else {
+			tree.rotateRight(node.Parent)
+		}
+	}
+	tree.deleteCase3(node)
+}
+
+func (tree *Tree) deleteCase3(node *Node) {
+	sibling := node.sibling()
+	if nodeColor(node.Parent) == black &&
+		nodeColor(sibling) == black &&
+		nodeColor(sibling.Left) == black &&
+		nodeColor(sibling.Right) == black {
+		sibling.color = red
+		tree.deleteCase1(node.Parent)
+	} else {
+		tree.deleteCase4(node)
+	}
+}
+
+func (tree *Tree) deleteCase4(node *Node) {
+	sibling := node.sibling()
+	if nodeColor(node.Parent) == red &&
+		nodeColor(sibling) == black &&
+		nodeColor(sibling.Left) == black &&
+		nodeColor(sibling.Right) == black {
+		sibling.color = red
+		node.Parent.color = black
+	} else {
+		tree.deleteCase5(node)
+	}
+}
+
+func (tree *Tree) deleteCase5(node *Node) {
+	sibling := node.sibling()
+	if node == node.Parent.Left &&
+		nodeColor(sibling) == black &&
+		nodeColor(sibling.Left) == red &&
+		nodeColor(sibling.Right) == black {
+		sibling.color = red
+		sibling.Left.color = black
+		tree.rotateRight(sibling)
+	} else if node == node.Parent.Right &&
+		nodeColor(sibling) == black &&
+		nodeColor(sibling.Right) == red &&
+		nodeColor(sibling.Left) == black {
+		sibling.color = red
+		sibling.Right.color = black
+		tree.rotateLeft(sibling)
+	}
+	tree.deleteCase6(node)
+}
+
+func (tree *Tree) deleteCase6(node *Node) {
+	sibling := node.sibling()
+	sibling.color = nodeColor(node.Parent)
+	node.Parent.color = black
+	if node == node.Parent.Left && nodeColor(sibling.Right) == red {
+		sibling.Right.color = black
+		tree.rotateLeft(node.Parent)
+	} else if nodeColor(sibling.Left) == red {
+		sibling.Left.color = black
+		tree.rotateRight(node.Parent)
+	}
+}
+
+func nodeColor(node *Node) color {
+	if node == nil {
+		return black
+	}
+	return node.color
+}
diff --git a/vendor/github.com/emirpasic/gods/trees/redblacktree/serialization.go b/vendor/github.com/emirpasic/gods/trees/redblacktree/serialization.go
new file mode 100644
index 0000000..9f2a23c
--- /dev/null
+++ b/vendor/github.com/emirpasic/gods/trees/redblacktree/serialization.go
@@ -0,0 +1,48 @@
+// Copyright (c) 2015, Emir Pasic. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package redblacktree
+
+import (
+	"encoding/json"
+	"github.com/emirpasic/gods/containers"
+	"github.com/emirpasic/gods/utils"
+)
+
+// Assert Serialization implementation
+var _ containers.JSONSerializer = (*Tree)(nil)
+var _ containers.JSONDeserializer = (*Tree)(nil)
+
+// ToJSON outputs the JSON representation of the tree.
+func (tree *Tree) ToJSON() ([]byte, error) {
+	elements := make(map[string]interface{})
+	it := tree.Iterator()
+	for it.Next() {
+		elements[utils.ToString(it.Key())] = it.Value()
+	}
+	return json.Marshal(&elements)
+}
+
+// FromJSON populates the tree from the input JSON representation.
+func (tree *Tree) FromJSON(data []byte) error {
+	elements := make(map[string]interface{})
+	err := json.Unmarshal(data, &elements)
+	if err == nil {
+		tree.Clear()
+		for key, value := range elements {
+			tree.Put(key, value)
+		}
+	}
+	return err
+}
+
+// UnmarshalJSON @implements json.Unmarshaler
+func (tree *Tree) UnmarshalJSON(bytes []byte) error {
+	return tree.FromJSON(bytes)
+}
+
+// MarshalJSON @implements json.Marshaler
+func (tree *Tree) MarshalJSON() ([]byte, error) {
+	return tree.ToJSON()
+}
diff --git a/vendor/github.com/emirpasic/gods/trees/trees.go b/vendor/github.com/emirpasic/gods/trees/trees.go
new file mode 100644
index 0000000..8d1b868
--- /dev/null
+++ b/vendor/github.com/emirpasic/gods/trees/trees.go
@@ -0,0 +1,22 @@
+// Copyright (c) 2015, Emir Pasic. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package trees provides an abstract Tree interface.
+//
+// In computer science, a tree is a widely used abstract data type (ADT) or data structure implementing this ADT that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.
+//
+// Reference: https://en.wikipedia.org/wiki/Tree_%28data_structure%29
+package trees
+
+import "github.com/emirpasic/gods/containers"
+
+// Tree interface that all trees implement
+type Tree interface {
+	containers.Container
+	// Empty() bool
+	// Size() int
+	// Clear()
+	// Values() []interface{}
+	// String() string
+}
diff --git a/vendor/github.com/emirpasic/gods/utils/comparator.go b/vendor/github.com/emirpasic/gods/utils/comparator.go
new file mode 100644
index 0000000..6a9afbf
--- /dev/null
+++ b/vendor/github.com/emirpasic/gods/utils/comparator.go
@@ -0,0 +1,251 @@
+// Copyright (c) 2015, Emir Pasic. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package utils
+
+import "time"
+
+// Comparator will make type assertion (see IntComparator for example),
+// which will panic if a or b are not of the asserted type.
+//
+// Should return a number:
+//    negative , if a < b
+//    zero     , if a == b
+//    positive , if a > b
+type Comparator func(a, b interface{}) int
+
+// StringComparator provides a fast comparison on strings
+func StringComparator(a, b interface{}) int {
+	s1 := a.(string)
+	s2 := b.(string)
+	min := len(s2)
+	if len(s1) < len(s2) {
+		min = len(s1)
+	}
+	diff := 0
+	for i := 0; i < min && diff == 0; i++ {
+		diff = int(s1[i]) - int(s2[i])
+	}
+	if diff == 0 {
+		diff = len(s1) - len(s2)
+	}
+	if diff < 0 {
+		return -1
+	}
+	if diff > 0 {
+		return 1
+	}
+	return 0
+}
+
+// IntComparator provides a basic comparison on int
+func IntComparator(a, b interface{}) int {
+	aAsserted := a.(int)
+	bAsserted := b.(int)
+	switch {
+	case aAsserted > bAsserted:
+		return 1
+	case aAsserted < bAsserted:
+		return -1
+	default:
+		return 0
+	}
+}
+
+// Int8Comparator provides a basic comparison on int8
+func Int8Comparator(a, b interface{}) int {
+	aAsserted := a.(int8)
+	bAsserted := b.(int8)
+	switch {
+	case aAsserted > bAsserted:
+		return 1
+	case aAsserted < bAsserted:
+		return -1
+	default:
+		return 0
+	}
+}
+
+// Int16Comparator provides a basic comparison on int16
+func Int16Comparator(a, b interface{}) int {
+	aAsserted := a.(int16)
+	bAsserted := b.(int16)
+	switch {
+	case aAsserted > bAsserted:
+		return 1
+	case aAsserted < bAsserted:
+		return -1
+	default:
+		return 0
+	}
+}
+
+// Int32Comparator provides a basic comparison on int32
+func Int32Comparator(a, b interface{}) int {
+	aAsserted := a.(int32)
+	bAsserted := b.(int32)
+	switch {
+	case aAsserted > bAsserted:
+		return 1
+	case aAsserted < bAsserted:
+		return -1
+	default:
+		return 0
+	}
+}
+
+// Int64Comparator provides a basic comparison on int64
+func Int64Comparator(a, b interface{}) int {
+	aAsserted := a.(int64)
+	bAsserted := b.(int64)
+	switch {
+	case aAsserted > bAsserted:
+		return 1
+	case aAsserted < bAsserted:
+		return -1
+	default:
+		return 0
+	}
+}
+
+// UIntComparator provides a basic comparison on uint
+func UIntComparator(a, b interface{}) int {
+	aAsserted := a.(uint)
+	bAsserted := b.(uint)
+	switch {
+	case aAsserted > bAsserted:
+		return 1
+	case aAsserted < bAsserted:
+		return -1
+	default:
+		return 0
+	}
+}
+
+// UInt8Comparator provides a basic comparison on uint8
+func UInt8Comparator(a, b interface{}) int {
+	aAsserted := a.(uint8)
+	bAsserted := b.(uint8)
+	switch {
+	case aAsserted > bAsserted:
+		return 1
+	case aAsserted < bAsserted:
+		return -1
+	default:
+		return 0
+	}
+}
+
+// UInt16Comparator provides a basic comparison on uint16
+func UInt16Comparator(a, b interface{}) int {
+	aAsserted := a.(uint16)
+	bAsserted := b.(uint16)
+	switch {
+	case aAsserted > bAsserted:
+		return 1
+	case aAsserted < bAsserted:
+		return -1
+	default:
+		return 0
+	}
+}
+
+// UInt32Comparator provides a basic comparison on uint32
+func UInt32Comparator(a, b interface{}) int {
+	aAsserted := a.(uint32)
+	bAsserted := b.(uint32)
+	switch {
+	case aAsserted > bAsserted:
+		return 1
+	case aAsserted < bAsserted:
+		return -1
+	default:
+		return 0
+	}
+}
+
+// UInt64Comparator provides a basic comparison on uint64
+func UInt64Comparator(a, b interface{}) int {
+	aAsserted := a.(uint64)
+	bAsserted := b.(uint64)
+	switch {
+	case aAsserted > bAsserted:
+		return 1
+	case aAsserted < bAsserted:
+		return -1
+	default:
+		return 0
+	}
+}
+
+// Float32Comparator provides a basic comparison on float32
+func Float32Comparator(a, b interface{}) int {
+	aAsserted := a.(float32)
+	bAsserted := b.(float32)
+	switch {
+	case aAsserted > bAsserted:
+		return 1
+	case aAsserted < bAsserted:
+		return -1
+	default:
+		return 0
+	}
+}
+
+// Float64Comparator provides a basic comparison on float64
+func Float64Comparator(a, b interface{}) int {
+	aAsserted := a.(float64)
+	bAsserted := b.(float64)
+	switch {
+	case aAsserted > bAsserted:
+		return 1
+	case aAsserted < bAsserted:
+		return -1
+	default:
+		return 0
+	}
+}
+
+// ByteComparator provides a basic comparison on byte
+func ByteComparator(a, b interface{}) int {
+	aAsserted := a.(byte)
+	bAsserted := b.(byte)
+	switch {
+	case aAsserted > bAsserted:
+		return 1
+	case aAsserted < bAsserted:
+		return -1
+	default:
+		return 0
+	}
+}
+
+// RuneComparator provides a basic comparison on rune
+func RuneComparator(a, b interface{}) int {
+	aAsserted := a.(rune)
+	bAsserted := b.(rune)
+	switch {
+	case aAsserted > bAsserted:
+		return 1
+	case aAsserted < bAsserted:
+		return -1
+	default:
+		return 0
+	}
+}
+
+// TimeComparator provides a basic comparison on time.Time
+func TimeComparator(a, b interface{}) int {
+	aAsserted := a.(time.Time)
+	bAsserted := b.(time.Time)
+
+	switch {
+	case aAsserted.After(bAsserted):
+		return 1
+	case aAsserted.Before(bAsserted):
+		return -1
+	default:
+		return 0
+	}
+}
diff --git a/vendor/github.com/emirpasic/gods/utils/sort.go b/vendor/github.com/emirpasic/gods/utils/sort.go
new file mode 100644
index 0000000..79ced1f
--- /dev/null
+++ b/vendor/github.com/emirpasic/gods/utils/sort.go
@@ -0,0 +1,29 @@
+// Copyright (c) 2015, Emir Pasic. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package utils
+
+import "sort"
+
+// Sort sorts values (in-place) with respect to the given comparator.
+//
+// Uses Go's sort (hybrid of quicksort for large and then insertion sort for smaller slices).
+func Sort(values []interface{}, comparator Comparator) {
+	sort.Sort(sortable{values, comparator})
+}
+
+type sortable struct {
+	values     []interface{}
+	comparator Comparator
+}
+
+func (s sortable) Len() int {
+	return len(s.values)
+}
+func (s sortable) Swap(i, j int) {
+	s.values[i], s.values[j] = s.values[j], s.values[i]
+}
+func (s sortable) Less(i, j int) bool {
+	return s.comparator(s.values[i], s.values[j]) < 0
+}
diff --git a/vendor/github.com/emirpasic/gods/utils/utils.go b/vendor/github.com/emirpasic/gods/utils/utils.go
new file mode 100644
index 0000000..262c625
--- /dev/null
+++ b/vendor/github.com/emirpasic/gods/utils/utils.go
@@ -0,0 +1,47 @@
+// Copyright (c) 2015, Emir Pasic. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package utils provides common utility functions.
+//
+// Provided functionalities:
+// - sorting
+// - comparators
+package utils
+
+import (
+	"fmt"
+	"strconv"
+)
+
+// ToString converts a value to string.
+func ToString(value interface{}) string {
+	switch value := value.(type) {
+	case string:
+		return value
+	case int8:
+		return strconv.FormatInt(int64(value), 10)
+	case int16:
+		return strconv.FormatInt(int64(value), 10)
+	case int32:
+		return strconv.FormatInt(int64(value), 10)
+	case int64:
+		return strconv.FormatInt(value, 10)
+	case uint8:
+		return strconv.FormatUint(uint64(value), 10)
+	case uint16:
+		return strconv.FormatUint(uint64(value), 10)
+	case uint32:
+		return strconv.FormatUint(uint64(value), 10)
+	case uint64:
+		return strconv.FormatUint(value, 10)
+	case float32:
+		return strconv.FormatFloat(float64(value), 'g', -1, 64)
+	case float64:
+		return strconv.FormatFloat(value, 'g', -1, 64)
+	case bool:
+		return strconv.FormatBool(value)
+	default:
+		return fmt.Sprintf("%+v", value)
+	}
+}