summaryrefslogtreecommitdiffstats
path: root/vendor/github.com/emirpasic/gods/trees/binaryheap
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/github.com/emirpasic/gods/trees/binaryheap')
-rw-r--r--vendor/github.com/emirpasic/gods/trees/binaryheap/binaryheap.go163
-rw-r--r--vendor/github.com/emirpasic/gods/trees/binaryheap/iterator.go84
-rw-r--r--vendor/github.com/emirpasic/gods/trees/binaryheap/serialization.go22
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)
+}