1// Copyright (c) 2015, Emir Pasic. All rights reserved.
  2// Use of this source code is governed by a BSD-style
  3// license that can be found in the LICENSE file.
  4
  5package binaryheap
  6
  7import (
  8	"github.com/emirpasic/gods/containers"
  9)
 10
 11// Assert Iterator implementation
 12var _ containers.ReverseIteratorWithIndex = (*Iterator)(nil)
 13
 14// Iterator returns a stateful iterator whose values can be fetched by an index.
 15type Iterator struct {
 16	heap  *Heap
 17	index int
 18}
 19
 20// Iterator returns a stateful iterator whose values can be fetched by an index.
 21func (heap *Heap) Iterator() Iterator {
 22	return Iterator{heap: heap, index: -1}
 23}
 24
 25// Next moves the iterator to the next element and returns true if there was a next element in the container.
 26// If Next() returns true, then next element's index and value can be retrieved by Index() and Value().
 27// If Next() was called for the first time, then it will point the iterator to the first element if it exists.
 28// Modifies the state of the iterator.
 29func (iterator *Iterator) Next() bool {
 30	if iterator.index < iterator.heap.Size() {
 31		iterator.index++
 32	}
 33	return iterator.heap.withinRange(iterator.index)
 34}
 35
 36// Prev moves the iterator to the previous element and returns true if there was a previous element in the container.
 37// If Prev() returns true, then previous element's index and value can be retrieved by Index() and Value().
 38// Modifies the state of the iterator.
 39func (iterator *Iterator) Prev() bool {
 40	if iterator.index >= 0 {
 41		iterator.index--
 42	}
 43	return iterator.heap.withinRange(iterator.index)
 44}
 45
 46// Value returns the current element's value.
 47// Does not modify the state of the iterator.
 48func (iterator *Iterator) Value() interface{} {
 49	start, end := evaluateRange(iterator.index)
 50	if end > iterator.heap.Size() {
 51		end = iterator.heap.Size()
 52	}
 53	tmpHeap := NewWith(iterator.heap.Comparator)
 54	for n := start; n < end; n++ {
 55		value, _ := iterator.heap.list.Get(n)
 56		tmpHeap.Push(value)
 57	}
 58	for n := 0; n < iterator.index-start; n++ {
 59		tmpHeap.Pop()
 60	}
 61	value, _ := tmpHeap.Pop()
 62	return value
 63}
 64
 65// Index returns the current element's index.
 66// Does not modify the state of the iterator.
 67func (iterator *Iterator) Index() int {
 68	return iterator.index
 69}
 70
 71// Begin resets the iterator to its initial state (one-before-first)
 72// Call Next() to fetch the first element if any.
 73func (iterator *Iterator) Begin() {
 74	iterator.index = -1
 75}
 76
 77// End moves the iterator past the last element (one-past-the-end).
 78// Call Prev() to fetch the last element if any.
 79func (iterator *Iterator) End() {
 80	iterator.index = iterator.heap.Size()
 81}
 82
 83// First moves the iterator to the first element and returns true if there was a first element in the container.
 84// If First() returns true, then first element's index and value can be retrieved by Index() and Value().
 85// Modifies the state of the iterator.
 86func (iterator *Iterator) First() bool {
 87	iterator.Begin()
 88	return iterator.Next()
 89}
 90
 91// Last moves the iterator to the last element and returns true if there was a last element in the container.
 92// If Last() returns true, then last element's index and value can be retrieved by Index() and Value().
 93// Modifies the state of the iterator.
 94func (iterator *Iterator) Last() bool {
 95	iterator.End()
 96	return iterator.Prev()
 97}
 98
 99// NextTo moves the iterator to the next element from current position that satisfies the condition given by the
100// passed function, and returns true if there was a next element in the container.
101// If NextTo() returns true, then next element's index and value can be retrieved by Index() and Value().
102// Modifies the state of the iterator.
103func (iterator *Iterator) NextTo(f func(index int, value interface{}) bool) bool {
104	for iterator.Next() {
105		index, value := iterator.Index(), iterator.Value()
106		if f(index, value) {
107			return true
108		}
109	}
110	return false
111}
112
113// PrevTo moves the iterator to the previous element from current position that satisfies the condition given by the
114// passed function, and returns true if there was a next element in the container.
115// If PrevTo() returns true, then next element's index and value can be retrieved by Index() and Value().
116// Modifies the state of the iterator.
117func (iterator *Iterator) PrevTo(f func(index int, value interface{}) bool) bool {
118	for iterator.Prev() {
119		index, value := iterator.Index(), iterator.Value()
120		if f(index, value) {
121			return true
122		}
123	}
124	return false
125}
126
127// numOfBits counts the number of bits of an int
128func numOfBits(n int) uint {
129	var count uint
130	for n != 0 {
131		count++
132		n >>= 1
133	}
134	return count
135}
136
137// evaluateRange evaluates the index range [start,end) of same level nodes in the heap as the index
138func evaluateRange(index int) (start int, end int) {
139	bits := numOfBits(index+1) - 1
140	start = 1<<bits - 1
141	end = start + 1<<bits
142	return
143}