diff options
Diffstat (limited to 'vendor/gopkg.in/karalabe/cookiejar.v2/collections/prque')
-rwxr-xr-x | vendor/gopkg.in/karalabe/cookiejar.v2/collections/prque/prque.go | 66 | ||||
-rwxr-xr-x | vendor/gopkg.in/karalabe/cookiejar.v2/collections/prque/sstack.go | 91 |
2 files changed, 0 insertions, 157 deletions
diff --git a/vendor/gopkg.in/karalabe/cookiejar.v2/collections/prque/prque.go b/vendor/gopkg.in/karalabe/cookiejar.v2/collections/prque/prque.go deleted file mode 100755 index 5c1967c65..000000000 --- a/vendor/gopkg.in/karalabe/cookiejar.v2/collections/prque/prque.go +++ /dev/null @@ -1,66 +0,0 @@ -// CookieJar - A contestant's algorithm toolbox -// Copyright (c) 2013 Peter Szilagyi. All rights reserved. -// -// CookieJar is dual licensed: use of this source code is governed by a BSD -// license that can be found in the LICENSE file. Alternatively, the CookieJar -// toolbox may be used in accordance with the terms and conditions contained -// in a signed written agreement between you and the author(s). - -// Package prque implements a priority queue data structure supporting arbitrary -// value types and float priorities. -// -// The reasoning behind using floats for the priorities vs. ints or interfaces -// was larger flexibility without sacrificing too much performance or code -// complexity. -// -// If you would like to use a min-priority queue, simply negate the priorities. -// -// Internally the queue is based on the standard heap package working on a -// sortable version of the block based stack. -package prque - -import ( - "container/heap" -) - -// Priority queue data structure. -type Prque struct { - cont *sstack -} - -// Creates a new priority queue. -func New() *Prque { - return &Prque{newSstack()} -} - -// Pushes a value with a given priority into the queue, expanding if necessary. -func (p *Prque) Push(data interface{}, priority float32) { - heap.Push(p.cont, &item{data, priority}) -} - -// Pops the value with the greates priority off the stack and returns it. -// Currently no shrinking is done. -func (p *Prque) Pop() (interface{}, float32) { - item := heap.Pop(p.cont).(*item) - return item.value, item.priority -} - -// Pops only the item from the queue, dropping the associated priority value. -func (p *Prque) PopItem() interface{} { - return heap.Pop(p.cont).(*item).value -} - -// Checks whether the priority queue is empty. -func (p *Prque) Empty() bool { - return p.cont.Len() == 0 -} - -// Returns the number of element in the priority queue. -func (p *Prque) Size() int { - return p.cont.Len() -} - -// Clears the contents of the priority queue. -func (p *Prque) Reset() { - *p = *New() -} diff --git a/vendor/gopkg.in/karalabe/cookiejar.v2/collections/prque/sstack.go b/vendor/gopkg.in/karalabe/cookiejar.v2/collections/prque/sstack.go deleted file mode 100755 index 9f393196e..000000000 --- a/vendor/gopkg.in/karalabe/cookiejar.v2/collections/prque/sstack.go +++ /dev/null @@ -1,91 +0,0 @@ -// CookieJar - A contestant's algorithm toolbox -// Copyright (c) 2013 Peter Szilagyi. All rights reserved. -// -// CookieJar is dual licensed: use of this source code is governed by a BSD -// license that can be found in the LICENSE file. Alternatively, the CookieJar -// toolbox may be used in accordance with the terms and conditions contained -// in a signed written agreement between you and the author(s). - -package prque - -// The size of a block of data -const blockSize = 4096 - -// A prioritized item in the sorted stack. -type item struct { - value interface{} - priority float32 -} - -// 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 { - size int - capacity int - offset int - - blocks [][]*item - active []*item -} - -// Creates a new, empty stack. -func newSstack() *sstack { - result := new(sstack) - 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 - } - 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 - 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 -} - -// 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 - s.blocks[ib][io], s.blocks[jb][jo] = s.blocks[jb][jo], s.blocks[ib][io] -} - -// Resets the stack, effectively clearing its contents. -func (s *sstack) Reset() { - *s = *newSstack() -} |