Fantom-foundation/go-lachesis

// This is a duplicated and slightly modified version of "gopkg.in/karalabe/cookiejar.v2/collections/prque".

package prque

// The size of a block of data
const blockSize = 4096

// A prioritized item in the sorted stack.
//
// Note: priorities can "wrap around" the int64 range, a comes before b if (a.priority - b.priority) > 0.
// The difference between the lowest and highest priorities in the queue at any point should be less than 2^63.
type item struct {
    value    interface{}
    priority int64
}

// setIndexCallback is called when the element is moved to a new index.
// Providing setIndexCallback is optional, it is needed only if the application needs
// to delete elements other than the top one.
type setIndexCallback func(a interface{}, i int)

// Internal sortable stack data structure. Implements the Push and Pop ops for
// the stack (heap) functionality and the Len, Less and Swap methods for the
// sortability requirements of the heaps.
type sstack struct {
    setIndex setIndexCallback
    size     int
    capacity int
    offset   int

    blocks [][]*item
    active []*item
}

// Creates a new, empty stack.
func newSstack(setIndex setIndexCallback) *sstack {
    result := new(sstack)
    result.setIndex = setIndex
    result.active = make([]*item, blockSize)
    result.blocks = [][]*item{result.active}
    result.capacity = blockSize
    return result
}

// Pushes a value onto the stack, expanding it if necessary. Required by
// heap.Interface.
func (s *sstack) Push(data interface{}) {
    if s.size == s.capacity {
        s.active = make([]*item, blockSize)
        s.blocks = append(s.blocks, s.active)
        s.capacity += blockSize
        s.offset = 0
    } else if s.offset == blockSize {
        s.active = s.blocks[s.size/blockSize]
        s.offset = 0
    }
    if s.setIndex != nil {
        s.setIndex(data.(*item).value, s.size)
    }
    s.active[s.offset] = data.(*item)
    s.offset++
    s.size++
}

// Pops a value off the stack and returns it. Currently no shrinking is done.
// Required by heap.Interface.
func (s *sstack) Pop() (res interface{}) {
    s.size--
    s.offset--
    if s.offset < 0 {
        s.offset = blockSize - 1
        s.active = s.blocks[s.size/blockSize]
    }
    res, s.active[s.offset] = s.active[s.offset], nil
    if s.setIndex != nil {
        s.setIndex(res.(*item).value, -1)
    }
    return
}

// Returns the length of the stack. Required by sort.Interface.
func (s *sstack) Len() int {
    return s.size
}

// Compares the priority of two elements of the stack (higher is first).
// Required by sort.Interface.
func (s *sstack) Less(i, j int) bool {
    return (s.blocks[i/blockSize][i%blockSize].priority - s.blocks[j/blockSize][j%blockSize].priority) > 0
}

// Swaps two elements in the stack. Required by sort.Interface.
func (s *sstack) Swap(i, j int) {
    ib, io, jb, jo := i/blockSize, i%blockSize, j/blockSize, j%blockSize
    a, b := s.blocks[jb][jo], s.blocks[ib][io]
    if s.setIndex != nil {
        s.setIndex(a.value, i)
        s.setIndex(b.value, j)
    }
    s.blocks[ib][io], s.blocks[jb][jo] = a, b
}

// Resets the stack, effectively clearing its contents.
func (s *sstack) Reset() {
    *s = *newSstack(s.setIndex)
}