vendor/gopkg.in/karalabe/cookiejar.v2/collections/prque/sstack.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
  10
  11 // The size of a block of data
  12 const blockSize = 4096
  13
  14 // A prioritized item in the sorted stack.
  15 type item struct {
  16         value    interface{}
  17         priority float32
  18 }
  19
  20 // Internal sortable stack data structure. Implements the Push and Pop ops for
  21 // the stack (heap) functionality and the Len, Less and Swap methods for the
  22 // sortability requirements of the heaps.
  23 type sstack struct {
  24         size     int
  25         capacity int
  26         offset   int
  27
  28         blocks [][]*item
  29         active []*item
  30 }
  31
  32 // Creates a new, empty stack.
  33 func newSstack() *sstack {
  34         result := new(sstack)
  35         result.active = make([]*item, blockSize)
  36         result.blocks = [][]*item{result.active}
  37         result.capacity = blockSize
  38         return result
  39 }
  40
  41 // Pushes a value onto the stack, expanding it if necessary. Required by
  42 // heap.Interface.
  43 func (s *sstack) Push(data interface{}) {
  44         if s.size == s.capacity {
  45                 s.active = make([]*item, blockSize)
  46                 s.blocks = append(s.blocks, s.active)
  47                 s.capacity += blockSize
  48                 s.offset = 0
  49         } else if s.offset == blockSize {
  50                 s.active = s.blocks[s.size/blockSize]
  51                 s.offset = 0
  52         }
  53         s.active[s.offset] = data.(*item)
  54         s.offset++
  55         s.size++
  56 }
  57
  58 // Pops a value off the stack and returns it. Currently no shrinking is done.
  59 // Required by heap.Interface.
  60 func (s *sstack) Pop() (res interface{}) {
  61         s.size--
  62         s.offset--
  63         if s.offset < 0 {
  64                 s.offset = blockSize - 1
  65                 s.active = s.blocks[s.size/blockSize]
  66         }
  67         res, s.active[s.offset] = s.active[s.offset], nil
  68         return
  69 }
  70
  71 // Returns the length of the stack. Required by sort.Interface.
  72 func (s *sstack) Len() int {
  73         return s.size
  74 }
  75
  76 // Compares the priority of two elements of the stack (higher is first).
  77 // Required by sort.Interface.
  78 func (s *sstack) Less(i, j int) bool {
  79         return s.blocks[i/blockSize][i%blockSize].priority > s.blocks[j/blockSize][j%blockSize].priority
  80 }
  81
  82 // Swaps two elements in the stack. Required by sort.Interface.
  83 func (s *sstack) Swap(i, j int) {
  84         ib, io, jb, jo := i/blockSize, i%blockSize, j/blockSize, j%blockSize
  85         s.blocks[ib][io], s.blocks[jb][jo] = s.blocks[jb][jo], s.blocks[ib][io]
  86 }
  87
  88 // Resets the stack, effectively clearing its contents.
  89 func (s *sstack) Reset() {
  90         *s = *newSstack()
  91 }