vendor/gopkg.in/karalabe/cookiejar.v2/collections/prque/prque.go

   1 // CookieJar - A contestant's algorithm toolbox
   2 // Copyright (c) 2013 Peter Szilagyi. All rights reserved.
   3 //
   4 // CookieJar is dual licensed: use of this source code is governed by a BSD
   5 // license that can be found in the LICENSE file. Alternatively, the CookieJar
   6 // toolbox may be used in accordance with the terms and conditions contained
   7 // in a signed written agreement between you and the author(s).
   8
   9 // Package prque implements a priority queue data structure supporting arbitrary
  10 // value types and float priorities.
  11 //
  12 // The reasoning behind using floats for the priorities vs. ints or interfaces
  13 // was larger flexibility without sacrificing too much performance or code
  14 // complexity.
  15 //
  16 // If you would like to use a min-priority queue, simply negate the priorities.
  17 //
  18 // Internally the queue is based on the standard heap package working on a
  19 // sortable version of the block based stack.
  20 package prque
  21
  22 import (
  23         "container/heap"
  24 )
  25
  26 // Priority queue data structure.
  27 type Prque struct {
  28         cont *sstack
  29 }
  30
  31 // Creates a new priority queue.
  32 func New() *Prque {
  33         return &Prque{newSstack()}
  34 }
  35
  36 // Pushes a value with a given priority into the queue, expanding if necessary.
  37 func (p *Prque) Push(data interface{}, priority float32) {
  38         heap.Push(p.cont, &item{data, priority})
  39 }
  40
  41 // Pops the value with the greates priority off the stack and returns it.
  42 // Currently no shrinking is done.
  43 func (p *Prque) Pop() (interface{}, float32) {
  44         item := heap.Pop(p.cont).(*item)
  45         return item.value, item.priority
  46 }
  47
  48 // Pops only the item from the queue, dropping the associated priority value.
  49 func (p *Prque) PopItem() interface{} {
  50         return heap.Pop(p.cont).(*item).value
  51 }
  52
  53 // Checks whether the priority queue is empty.
  54 func (p *Prque) Empty() bool {
  55         return p.cont.Len() == 0
  56 }
  57
  58 // Returns the number of element in the priority queue.
  59 func (p *Prque) Size() int {
  60         return p.cont.Len()
  61 }
  62
  63 // Clears the contents of the priority queue.
  64 func (p *Prque) Reset() {
  65         *p = *New()
  66 }