prque_test.go 3.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131
  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 prque
  9. import (
  10. "math/rand"
  11. "testing"
  12. )
  13. func TestPrque(t *testing.T) {
  14. // Generate a batch of random data and a specific priority order
  15. size := 16 * blockSize
  16. prio := rand.Perm(size)
  17. data := make([]int, size)
  18. for i := 0; i < size; i++ {
  19. data[i] = rand.Int()
  20. }
  21. queue := New()
  22. for rep := 0; rep < 2; rep++ {
  23. // Fill a priority queue with the above data
  24. for i := 0; i < size; i++ {
  25. queue.Push(data[i], float32(prio[i]))
  26. if queue.Size() != i+1 {
  27. t.Errorf("queue size mismatch: have %v, want %v.", queue.Size(), i+1)
  28. }
  29. }
  30. // Create a map the values to the priorities for easier verification
  31. dict := make(map[float32]int)
  32. for i := 0; i < size; i++ {
  33. dict[float32(prio[i])] = data[i]
  34. }
  35. // Pop out the elements in priority order and verify them
  36. prevPrio := float32(size + 1)
  37. for !queue.Empty() {
  38. val, prio := queue.Pop()
  39. if prio > prevPrio {
  40. t.Errorf("invalid priority order: %v after %v.", prio, prevPrio)
  41. }
  42. prevPrio = prio
  43. if val != dict[prio] {
  44. t.Errorf("push/pop mismatch: have %v, want %v.", val, dict[prio])
  45. }
  46. delete(dict, prio)
  47. }
  48. }
  49. }
  50. func TestReset(t *testing.T) {
  51. // Generate a batch of random data and a specific priority order
  52. size := 16 * blockSize
  53. prio := rand.Perm(size)
  54. data := make([]int, size)
  55. for i := 0; i < size; i++ {
  56. data[i] = rand.Int()
  57. }
  58. queue := New()
  59. for rep := 0; rep < 2; rep++ {
  60. // Fill a priority queue with the above data
  61. for i := 0; i < size; i++ {
  62. queue.Push(data[i], float32(prio[i]))
  63. if queue.Size() != i+1 {
  64. t.Errorf("queue size mismatch: have %v, want %v.", queue.Size(), i+1)
  65. }
  66. }
  67. // Create a map the values to the priorities for easier verification
  68. dict := make(map[float32]int)
  69. for i := 0; i < size; i++ {
  70. dict[float32(prio[i])] = data[i]
  71. }
  72. // Pop out half the elements in priority order and verify them
  73. prevPrio := float32(size + 1)
  74. for i := 0; i < size/2; i++ {
  75. val, prio := queue.Pop()
  76. if prio > prevPrio {
  77. t.Errorf("invalid priority order: %v after %v.", prio, prevPrio)
  78. }
  79. prevPrio = prio
  80. if val != dict[prio] {
  81. t.Errorf("push/pop mismatch: have %v, want %v.", val, dict[prio])
  82. }
  83. delete(dict, prio)
  84. }
  85. // Reset and ensure it's empty
  86. queue.Reset()
  87. if !queue.Empty() {
  88. t.Errorf("priority queue not empty after reset: %v", queue)
  89. }
  90. }
  91. }
  92. func BenchmarkPush(b *testing.B) {
  93. // Create some initial data
  94. data := make([]int, b.N)
  95. prio := make([]float32, b.N)
  96. for i := 0; i < len(data); i++ {
  97. data[i] = rand.Int()
  98. prio[i] = rand.Float32()
  99. }
  100. // Execute the benchmark
  101. b.ResetTimer()
  102. queue := New()
  103. for i := 0; i < len(data); i++ {
  104. queue.Push(data[i], prio[i])
  105. }
  106. }
  107. func BenchmarkPop(b *testing.B) {
  108. // Create some initial data
  109. data := make([]int, b.N)
  110. prio := make([]float32, b.N)
  111. for i := 0; i < len(data); i++ {
  112. data[i] = rand.Int()
  113. prio[i] = rand.Float32()
  114. }
  115. queue := New()
  116. for i := 0; i < len(data); i++ {
  117. queue.Push(data[i], prio[i])
  118. }
  119. // Execute the benchmark
  120. b.ResetTimer()
  121. for !queue.Empty() {
  122. queue.Pop()
  123. }
  124. }