queue.go 2.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899
  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. // Package queue implements a FIFO (first in first out) data structure supporting
  9. // arbitrary types (even a mixture).
  10. //
  11. // Internally it uses a dynamically growing circular slice of blocks, resulting
  12. // in faster resizes than a simple dynamic array/slice would allow.
  13. package queue
  14. // The size of a block of data
  15. const blockSize = 4096
  16. // First in, first out data structure.
  17. type Queue struct {
  18. tailIdx int
  19. headIdx int
  20. tailOff int
  21. headOff int
  22. blocks [][]interface{}
  23. head []interface{}
  24. tail []interface{}
  25. }
  26. // Creates a new, empty queue.
  27. func New() *Queue {
  28. result := new(Queue)
  29. result.blocks = [][]interface{}{make([]interface{}, blockSize)}
  30. result.head = result.blocks[0]
  31. result.tail = result.blocks[0]
  32. return result
  33. }
  34. // Pushes a new element into the queue, expanding it if necessary.
  35. func (q *Queue) Push(data interface{}) {
  36. q.tail[q.tailOff] = data
  37. q.tailOff++
  38. if q.tailOff == blockSize {
  39. q.tailOff = 0
  40. q.tailIdx = (q.tailIdx + 1) % len(q.blocks)
  41. // If we wrapped over to the end, insert a new block and update indices
  42. if q.tailIdx == q.headIdx {
  43. buffer := make([][]interface{}, len(q.blocks)+1)
  44. copy(buffer[:q.tailIdx], q.blocks[:q.tailIdx])
  45. buffer[q.tailIdx] = make([]interface{}, blockSize)
  46. copy(buffer[q.tailIdx+1:], q.blocks[q.tailIdx:])
  47. q.blocks = buffer
  48. q.headIdx++
  49. q.head = q.blocks[q.headIdx]
  50. }
  51. q.tail = q.blocks[q.tailIdx]
  52. }
  53. }
  54. // Pops out an element from the queue. Note, no bounds checking are done.
  55. func (q *Queue) Pop() (res interface{}) {
  56. res, q.head[q.headOff] = q.head[q.headOff], nil
  57. q.headOff++
  58. if q.headOff == blockSize {
  59. q.headOff = 0
  60. q.headIdx = (q.headIdx + 1) % len(q.blocks)
  61. q.head = q.blocks[q.headIdx]
  62. }
  63. return
  64. }
  65. // Returns the first element in the queue. Note, no bounds checking are done.
  66. func (q *Queue) Front() interface{} {
  67. return q.head[q.headOff]
  68. }
  69. // Checks whether the queue is empty.
  70. func (q *Queue) Empty() bool {
  71. return q.headIdx == q.tailIdx && q.headOff == q.tailOff
  72. }
  73. // Returns the number of elements in the queue.
  74. func (q *Queue) Size() int {
  75. if q.tailIdx > q.headIdx {
  76. return (q.tailIdx-q.headIdx)*blockSize - q.headOff + q.tailOff
  77. } else if q.tailIdx < q.headIdx {
  78. return (len(q.blocks)-q.headIdx+q.tailIdx)*blockSize - q.headOff + q.tailOff
  79. } else {
  80. return q.tailOff - q.headOff
  81. }
  82. }
  83. // Clears out the contents of the queue.
  84. func (q *Queue) Reset() {
  85. *q = *New()
  86. }