diff options
Diffstat (limited to 'vendor/github.com/emirpasic/gods/trees/binaryheap')
3 files changed, 269 insertions, 0 deletions
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) +} |