diff options
Diffstat (limited to 'vendor/github.com/emirpasic')
17 files changed, 1332 insertions, 0 deletions
diff --git a/vendor/github.com/emirpasic/gods/LICENSE b/vendor/github.com/emirpasic/gods/LICENSE new file mode 100644 index 0000000000..e5e449b6ec --- /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 0000000000..c35ab36d2c --- /dev/null +++ b/vendor/github.com/emirpasic/gods/containers/containers.go @@ -0,0 +1,35 @@ +// 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{} +} + +// GetSortedValues returns sorted container's elements with respect to the passed comparator. +// Does not effect 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 0000000000..ac48b54531 --- /dev/null +++ b/vendor/github.com/emirpasic/gods/containers/enumerable.go @@ -0,0 +1,61 @@ +// 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. + // TODO would appreciate help on how to enforce this in containers (don't want to type assert when chaining) + // 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. + // TODO need help on how to enforce this in containers (don't want to type assert when chaining) + // 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. + // TODO need help on how to enforce this in containers (don't want to type assert when chaining) + // 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. + // TODO need help on how to enforce this in containers (don't want to type assert when chaining) + // 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 0000000000..f1a52a365a --- /dev/null +++ b/vendor/github.com/emirpasic/gods/containers/iterator.go @@ -0,0 +1,109 @@ +// 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 +} + +// 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 +} + +// 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 + + 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 + + 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 0000000000..d7c90c83a0 --- /dev/null +++ b/vendor/github.com/emirpasic/gods/containers/serialization.go @@ -0,0 +1,17 @@ +// 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) +} + +// JSONDeserializer provides JSON deserialization +type JSONDeserializer interface { + // FromJSON populates containers's elements from the input JSON representation. + FromJSON([]byte) error +} diff --git a/vendor/github.com/emirpasic/gods/lists/arraylist/arraylist.go b/vendor/github.com/emirpasic/gods/lists/arraylist/arraylist.go new file mode 100644 index 0000000000..bfedac9eef --- /dev/null +++ b/vendor/github.com/emirpasic/gods/lists/arraylist/arraylist.go @@ -0,0 +1,228 @@ +// 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 arraylist implements the array list. +// +// Structure is not thread safe. +// +// Reference: https://en.wikipedia.org/wiki/List_%28abstract_data_type%29 +package arraylist + +import ( + "fmt" + "strings" + + "github.com/emirpasic/gods/lists" + "github.com/emirpasic/gods/utils" +) + +func assertListImplementation() { + var _ lists.List = (*List)(nil) +} + +// List holds the elements in a slice +type List struct { + elements []interface{} + size int +} + +const ( + growthFactor = float32(2.0) // growth by 100% + shrinkFactor = float32(0.25) // shrink when size is 25% of capacity (0 means never shrink) +) + +// New instantiates a new list and adds the passed values, if any, to the list +func New(values ...interface{}) *List { + list := &List{} + if len(values) > 0 { + list.Add(values...) + } + return list +} + +// Add appends a value at the end of the list +func (list *List) Add(values ...interface{}) { + list.growBy(len(values)) + for _, value := range values { + list.elements[list.size] = value + list.size++ + } +} + +// Get returns the element at index. +// Second return parameter is true if index is within bounds of the array and array is not empty, otherwise false. +func (list *List) Get(index int) (interface{}, bool) { + + if !list.withinRange(index) { + return nil, false + } + + return list.elements[index], true +} + +// Remove removes the element at the given index from the list. +func (list *List) Remove(index int) { + + if !list.withinRange(index) { + return + } + + list.elements[index] = nil // cleanup reference + copy(list.elements[index:], list.elements[index+1:list.size]) // shift to the left by one (slow operation, need ways to optimize this) + list.size-- + + list.shrink() +} + +// Contains checks if elements (one or more) are present in the set. +// All elements have to be present in the set for the method to return true. +// Performance time complexity of n^2. +// Returns true if no arguments are passed at all, i.e. set is always super-set of empty set. +func (list *List) Contains(values ...interface{}) bool { + + for _, searchValue := range values { + found := false + for _, element := range list.elements { + if element == searchValue { + found = true + break + } + } + if !found { + return false + } + } + return true +} + +// Values returns all elements in the list. +func (list *List) Values() []interface{} { + newElements := make([]interface{}, list.size, list.size) + copy(newElements, list.elements[:list.size]) + return newElements +} + +//IndexOf returns index of provided element +func (list *List) IndexOf(value interface{}) int { + if list.size == 0 { + return -1 + } + for index, element := range list.elements { + if element == value { + return index + } + } + return -1 +} + +// Empty returns true if list does not contain any elements. +func (list *List) Empty() bool { + return list.size == 0 +} + +// Size returns number of elements within the list. +func (list *List) Size() int { + return list.size +} + +// Clear removes all elements from the list. +func (list *List) Clear() { + list.size = 0 + list.elements = []interface{}{} +} + +// Sort sorts values (in-place) using. +func (list *List) Sort(comparator utils.Comparator) { + if len(list.elements) < 2 { + return + } + utils.Sort(list.elements[:list.size], comparator) +} + +// Swap swaps the two values at the specified positions. +func (list *List) Swap(i, j int) { + if list.withinRange(i) && list.withinRange(j) { + list.elements[i], list.elements[j] = list.elements[j], list.elements[i] + } +} + +// Insert inserts values at specified index position shifting the value at that position (if any) and any subsequent elements to the right. +// Does not do anything if position is negative or bigger than list's size +// Note: position equal to list's size is valid, i.e. append. +func (list *List) Insert(index int, values ...interface{}) { + + if !list.withinRange(index) { + // Append + if index == list.size { + list.Add(values...) + } + return + } + + l := len(values) + list.growBy(l) + list.size += l + copy(list.elements[index+l:], list.elements[index:list.size-l]) + copy(list.elements[index:], values) +} + +// Set the value at specified index +// Does not do anything if position is negative or bigger than list's size +// Note: position equal to list's size is valid, i.e. append. +func (list *List) Set(index int, value interface{}) { + + if !list.withinRange(index) { + // Append + if index == list.size { + list.Add(value) + } + return + } + + list.elements[index] = value +} + +// String returns a string representation of container +func (list *List) String() string { + str := "ArrayList\n" + values := []string{} + for _, value := range list.elements[:list.size] { + values = append(values, fmt.Sprintf("%v", value)) + } + str += strings.Join(values, ", ") + return str +} + +// Check that the index is within bounds of the list +func (list *List) withinRange(index int) bool { + return index >= 0 && index < list.size +} + +func (list *List) resize(cap int) { + newElements := make([]interface{}, cap, cap) + copy(newElements, list.elements) + list.elements = newElements +} + +// Expand the array if necessary, i.e. capacity will be reached if we add n elements +func (list *List) growBy(n int) { + // When capacity is reached, grow by a factor of growthFactor and add number of elements + currentCapacity := cap(list.elements) + if list.size+n >= currentCapacity { + newCapacity := int(growthFactor * float32(currentCapacity+n)) + list.resize(newCapacity) + } +} + +// Shrink the array if necessary, i.e. when size is shrinkFactor percent of current capacity +func (list *List) shrink() { + if shrinkFactor == 0.0 { + return + } + // Shrink when size is at shrinkFactor * capacity + currentCapacity := cap(list.elements) + if list.size <= int(float32(currentCapacity)*shrinkFactor) { + list.resize(list.size) + } +} diff --git a/vendor/github.com/emirpasic/gods/lists/arraylist/enumerable.go b/vendor/github.com/emirpasic/gods/lists/arraylist/enumerable.go new file mode 100644 index 0000000000..b3a8738825 --- /dev/null +++ b/vendor/github.com/emirpasic/gods/lists/arraylist/enumerable.go @@ -0,0 +1,79 @@ +// 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 arraylist + +import "github.com/emirpasic/gods/containers" + +func assertEnumerableImplementation() { + var _ containers.EnumerableWithIndex = (*List)(nil) +} + +// Each calls the given function once for each element, passing that element's index and value. +func (list *List) Each(f func(index int, value interface{})) { + iterator := list.Iterator() + for iterator.Next() { + f(iterator.Index(), iterator.Value()) + } +} + +// Map invokes the given function once for each element and returns a +// container containing the values returned by the given function. +func (list *List) Map(f func(index int, value interface{}) interface{}) *List { + newList := &List{} + iterator := list.Iterator() + for iterator.Next() { + newList.Add(f(iterator.Index(), iterator.Value())) + } + return newList +} + +// Select returns a new container containing all elements for which the given function returns a true value. +func (list *List) Select(f func(index int, value interface{}) bool) *List { + newList := &List{} + iterator := list.Iterator() + for iterator.Next() { + if f(iterator.Index(), iterator.Value()) { + newList.Add(iterator.Value()) + } + } + return newList +} + +// Any passes each element of the collection to the given function and +// returns true if the function ever returns true for any element. +func (list *List) Any(f func(index int, value interface{}) bool) bool { + iterator := list.Iterator() + for iterator.Next() { + if f(iterator.Index(), iterator.Value()) { + return true + } + } + return false +} + +// All passes each element of the collection to the given function and +// returns true if the function returns true for all elements. +func (list *List) All(f func(index int, value interface{}) bool) bool { + iterator := list.Iterator() + for iterator.Next() { + if !f(iterator.Index(), iterator.Value()) { + return false + } + } + return true +} + +// 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. +func (list *List) Find(f func(index int, value interface{}) bool) (int, interface{}) { + iterator := list.Iterator() + for iterator.Next() { + if f(iterator.Index(), iterator.Value()) { + return iterator.Index(), iterator.Value() + } + } + return -1, nil +} diff --git a/vendor/github.com/emirpasic/gods/lists/arraylist/iterator.go b/vendor/github.com/emirpasic/gods/lists/arraylist/iterator.go new file mode 100644 index 0000000000..38a93f3a8f --- /dev/null +++ b/vendor/github.com/emirpasic/gods/lists/arraylist/iterator.go @@ -0,0 +1,83 @@ +// 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 arraylist + +import "github.com/emirpasic/gods/containers" + +func assertIteratorImplementation() { + var _ containers.ReverseIteratorWithIndex = (*Iterator)(nil) +} + +// Iterator holding the iterator's state +type Iterator struct { + list *List + index int +} + +// Iterator returns a stateful iterator whose values can be fetched by an index. +func (list *List) Iterator() Iterator { + return Iterator{list: list, index: -1} +} + +// 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. +func (iterator *Iterator) Next() bool { + if iterator.index < iterator.list.size { + iterator.index++ + } + return iterator.list.withinRange(iterator.index) +} + +// 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. +func (iterator *Iterator) Prev() bool { + if iterator.index >= 0 { + iterator.index-- + } + return iterator.list.withinRange(iterator.index) +} + +// Value returns the current element's value. +// Does not modify the state of the iterator. +func (iterator *Iterator) Value() interface{} { + return iterator.list.elements[iterator.index] +} + +// Index returns the current element's index. +// Does not modify the state of the iterator. +func (iterator *Iterator) Index() int { + return iterator.index +} + +// 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.index = -1 +} + +// 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.index = iterator.list.size +} + +// 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. +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 index and value can be retrieved by Index() and Value(). +// Modifies the state of the iterator. +func (iterator *Iterator) Last() bool { + iterator.End() + return iterator.Prev() +} diff --git a/vendor/github.com/emirpasic/gods/lists/arraylist/serialization.go b/vendor/github.com/emirpasic/gods/lists/arraylist/serialization.go new file mode 100644 index 0000000000..2f283fb97d --- /dev/null +++ b/vendor/github.com/emirpasic/gods/lists/arraylist/serialization.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 arraylist + +import ( + "encoding/json" + "github.com/emirpasic/gods/containers" +) + +func assertSerializationImplementation() { + var _ containers.JSONSerializer = (*List)(nil) + var _ containers.JSONDeserializer = (*List)(nil) +} + +// ToJSON outputs the JSON representation of list's elements. +func (list *List) ToJSON() ([]byte, error) { + return json.Marshal(list.elements[:list.size]) +} + +// FromJSON populates list's elements from the input JSON representation. +func (list *List) FromJSON(data []byte) error { + err := json.Unmarshal(data, &list.elements) + if err == nil { + list.size = len(list.elements) + } + return err +} diff --git a/vendor/github.com/emirpasic/gods/lists/lists.go b/vendor/github.com/emirpasic/gods/lists/lists.go new file mode 100644 index 0000000000..1f6bb08e94 --- /dev/null +++ b/vendor/github.com/emirpasic/gods/lists/lists.go @@ -0,0 +1,33 @@ +// 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 lists provides an abstract List interface. +// +// In computer science, a list or sequence is an abstract data type that represents an ordered sequence of values, where the same value may occur more than once. An instance of a list is a computer representation of the mathematical concept of a finite sequence; the (potentially) infinite analog of a list is a stream. Lists are a basic example of containers, as they contain other values. If the same value occurs multiple times, each occurrence is considered a distinct item. +// +// Reference: https://en.wikipedia.org/wiki/List_%28abstract_data_type%29 +package lists + +import ( + "github.com/emirpasic/gods/containers" + "github.com/emirpasic/gods/utils" +) + +// List interface that all lists implement +type List interface { + Get(index int) (interface{}, bool) + Remove(index int) + Add(values ...interface{}) + Contains(values ...interface{}) bool + Sort(comparator utils.Comparator) + Swap(index1, index2 int) + Insert(index int, values ...interface{}) + Set(index int, value interface{}) + + containers.Container + // Empty() bool + // Size() int + // Clear() + // Values() []interface{} +} diff --git a/vendor/github.com/emirpasic/gods/trees/binaryheap/binaryheap.go b/vendor/github.com/emirpasic/gods/trees/binaryheap/binaryheap.go new file mode 100644 index 0000000000..70b28cf52d --- /dev/null +++ b/vendor/github.com/emirpasic/gods/trees/binaryheap/binaryheap.go @@ -0,0 +1,163 @@ +// 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 binaryheap implements a binary heap backed by array list. +// +// Comparator defines this heap as either min or max heap. +// +// Structure is not thread safe. +// +// References: http://en.wikipedia.org/wiki/Binary_heap +package binaryheap + +import ( + "fmt" + "github.com/emirpasic/gods/lists/arraylist" + "github.com/emirpasic/gods/trees" + "github.com/emirpasic/gods/utils" + "strings" +) + +func assertTreeImplementation() { + var _ trees.Tree = (*Heap)(nil) +} + +// Heap holds elements in an array-list +type Heap struct { + list *arraylist.List + Comparator utils.Comparator +} + +// NewWith instantiates a new empty heap tree with the custom comparator. +func NewWith(comparator utils.Comparator) *Heap { + return &Heap{list: arraylist.New(), Comparator: comparator} +} + +// NewWithIntComparator instantiates a new empty heap with the IntComparator, i.e. elements are of type int. +func NewWithIntComparator() *Heap { + return &Heap{list: arraylist.New(), Comparator: utils.IntComparator} +} + +// NewWithStringComparator instantiates a new empty heap with the StringComparator, i.e. elements are of type string. +func NewWithStringComparator() *Heap { + return &Heap{list: arraylist.New(), Comparator: utils.StringComparator} +} + +// Push adds a value onto the heap and bubbles it up accordingly. +func (heap *Heap) Push(values ...interface{}) { + if len(values) == 1 { + heap.list.Add(values[0]) + heap.bubbleUp() + } else { + // Reference: https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap + for _, value := range values { + heap.list.Add(value) + } + size := heap.list.Size()/2 + 1 + for i := size; i >= 0; i-- { + heap.bubbleDownIndex(i) + } + } +} + +// Pop removes top element on heap and returns it, or nil if heap is empty. +// Second return parameter is true, unless the heap was empty and there was nothing to pop. +func (heap *Heap) Pop() (value interface{}, ok bool) { + value, ok = heap.list.Get(0) + if !ok { + return + } + lastIndex := heap.list.Size() - 1 + heap.list.Swap(0, lastIndex) + heap.list.Remove(lastIndex) + heap.bubbleDown() + return +} + +// Peek returns top element on the heap without removing it, or nil if heap is empty. +// Second return parameter is true, unless the heap was empty and there was nothing to peek. +func (heap *Heap) Peek() (value interface{}, ok bool) { + return heap.list.Get(0) +} + +// Empty returns true if heap does not contain any elements. +func (heap *Heap) Empty() bool { + return heap.list.Empty() +} + +// Size returns number of elements within the heap. +func (heap *Heap) Size() int { + return heap.list.Size() +} + +// Clear removes all elements from the heap. +func (heap *Heap) Clear() { + heap.list.Clear() +} + +// Values returns all elements in the heap. +func (heap *Heap) Values() []interface{} { + return heap.list.Values() +} + +// String returns a string representation of container +func (heap *Heap) String() string { + str := "BinaryHeap\n" + values := []string{} + for _, value := range heap.list.Values() { + values = append(values, fmt.Sprintf("%v", value)) + } + str += strings.Join(values, ", ") + return str +} + +// Performs the "bubble down" operation. This is to place the element that is at the root +// of the heap in its correct place so that the heap maintains the min/max-heap order property. +func (heap *Heap) bubbleDown() { + heap.bubbleDownIndex(0) +} + +// Performs the "bubble down" operation. This is to place the element that is at the index +// of the heap in its correct place so that the heap maintains the min/max-heap order property. +func (heap *Heap) bubbleDownIndex(index int) { + size := heap.list.Size() + for leftIndex := index<<1 + 1; leftIndex < size; leftIndex = index<<1 + 1 { + rightIndex := index<<1 + 2 + smallerIndex := leftIndex + leftValue, _ := heap.list.Get(leftIndex) + rightValue, _ := heap.list.Get(rightIndex) + if rightIndex < size && heap.Comparator(leftValue, rightValue) > 0 { + smallerIndex = rightIndex + } + indexValue, _ := heap.list.Get(index) + smallerValue, _ := heap.list.Get(smallerIndex) + if heap.Comparator(indexValue, smallerValue) > 0 { + heap.list.Swap(index, smallerIndex) + } else { + break + } + index = smallerIndex + } +} + +// Performs the "bubble up" operation. This is to place a newly inserted +// element (i.e. last element in the list) in its correct place so that +// the heap maintains the min/max-heap order property. +func (heap *Heap) bubbleUp() { + index := heap.list.Size() - 1 + for parentIndex := (index - 1) >> 1; index > 0; parentIndex = (index - 1) >> 1 { + indexValue, _ := heap.list.Get(index) + parentValue, _ := heap.list.Get(parentIndex) + if heap.Comparator(parentValue, indexValue) <= 0 { + break + } + heap.list.Swap(index, parentIndex) + index = parentIndex + } +} + +// Check that the index is within bounds of the list +func (heap *Heap) withinRange(index int) bool { + return index >= 0 && index < heap.list.Size() +} diff --git a/vendor/github.com/emirpasic/gods/trees/binaryheap/iterator.go b/vendor/github.com/emirpasic/gods/trees/binaryheap/iterator.go new file mode 100644 index 0000000000..beeb8d7013 --- /dev/null +++ b/vendor/github.com/emirpasic/gods/trees/binaryheap/iterator.go @@ -0,0 +1,84 @@ +// 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 binaryheap + +import "github.com/emirpasic/gods/containers" + +func assertIteratorImplementation() { + var _ containers.ReverseIteratorWithIndex = (*Iterator)(nil) +} + +// Iterator returns a stateful iterator whose values can be fetched by an index. +type Iterator struct { + heap *Heap + index int +} + +// Iterator returns a stateful iterator whose values can be fetched by an index. +func (heap *Heap) Iterator() Iterator { + return Iterator{heap: heap, index: -1} +} + +// 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. +func (iterator *Iterator) Next() bool { + if iterator.index < iterator.heap.Size() { + iterator.index++ + } + return iterator.heap.withinRange(iterator.index) +} + +// 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. +func (iterator *Iterator) Prev() bool { + if iterator.index >= 0 { + iterator.index-- + } + return iterator.heap.withinRange(iterator.index) +} + +// Value returns the current element's value. +// Does not modify the state of the iterator. +func (iterator *Iterator) Value() interface{} { + value, _ := iterator.heap.list.Get(iterator.index) + return value +} + +// Index returns the current element's index. +// Does not modify the state of the iterator. +func (iterator *Iterator) Index() int { + return iterator.index +} + +// 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.index = -1 +} + +// 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.index = iterator.heap.Size() +} + +// 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. +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 index and value can be retrieved by Index() and Value(). +// Modifies the state of the iterator. +func (iterator *Iterator) Last() bool { + iterator.End() + return iterator.Prev() +} diff --git a/vendor/github.com/emirpasic/gods/trees/binaryheap/serialization.go b/vendor/github.com/emirpasic/gods/trees/binaryheap/serialization.go new file mode 100644 index 0000000000..00d0c7719c --- /dev/null +++ b/vendor/github.com/emirpasic/gods/trees/binaryheap/serialization.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 binaryheap + +import "github.com/emirpasic/gods/containers" + +func assertSerializationImplementation() { + var _ containers.JSONSerializer = (*Heap)(nil) + var _ containers.JSONDeserializer = (*Heap)(nil) +} + +// ToJSON outputs the JSON representation of the heap. +func (heap *Heap) ToJSON() ([]byte, error) { + return heap.list.ToJSON() +} + +// FromJSON populates the heap from the input JSON representation. +func (heap *Heap) FromJSON(data []byte) error { + return heap.list.FromJSON(data) +} 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 0000000000..a5a7427d34 --- /dev/null +++ b/vendor/github.com/emirpasic/gods/trees/trees.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 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{} +} 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 0000000000..6a9afbf346 --- /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 0000000000..79ced1f5d2 --- /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 0000000000..1ad49cbc07 --- /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.(type) { + case string: + return value.(string) + case int8: + return strconv.FormatInt(int64(value.(int8)), 10) + case int16: + return strconv.FormatInt(int64(value.(int16)), 10) + case int32: + return strconv.FormatInt(int64(value.(int32)), 10) + case int64: + return strconv.FormatInt(int64(value.(int64)), 10) + case uint8: + return strconv.FormatUint(uint64(value.(uint8)), 10) + case uint16: + return strconv.FormatUint(uint64(value.(uint16)), 10) + case uint32: + return strconv.FormatUint(uint64(value.(uint32)), 10) + case uint64: + return strconv.FormatUint(uint64(value.(uint64)), 10) + case float32: + return strconv.FormatFloat(float64(value.(float32)), 'g', -1, 64) + case float64: + return strconv.FormatFloat(float64(value.(float64)), 'g', -1, 64) + case bool: + return strconv.FormatBool(value.(bool)) + default: + return fmt.Sprintf("%+v", value) + } +} |