sstack_test.go 2.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
  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. "sort"
  12. "testing"
  13. )
  14. func TestSstack(t *testing.T) {
  15. // Create some initial data
  16. size := 16 * blockSize
  17. data := make([]*item, size)
  18. for i := 0; i < size; i++ {
  19. data[i] = &item{rand.Int(), rand.Float32()}
  20. }
  21. stack := newSstack()
  22. for rep := 0; rep < 2; rep++ {
  23. // Push all the data into the stack, pop out every second
  24. secs := []*item{}
  25. for i := 0; i < size; i++ {
  26. stack.Push(data[i])
  27. if i%2 == 0 {
  28. secs = append(secs, stack.Pop().(*item))
  29. }
  30. }
  31. rest := []*item{}
  32. for stack.Len() > 0 {
  33. rest = append(rest, stack.Pop().(*item))
  34. }
  35. // Make sure the contents of the resulting slices are ok
  36. for i := 0; i < size; i++ {
  37. if i%2 == 0 && data[i] != secs[i/2] {
  38. t.Errorf("push/pop mismatch: have %v, want %v.", secs[i/2], data[i])
  39. }
  40. if i%2 == 1 && data[i] != rest[len(rest)-i/2-1] {
  41. t.Errorf("push/pop mismatch: have %v, want %v.", rest[len(rest)-i/2-1], data[i])
  42. }
  43. }
  44. }
  45. }
  46. func TestSstackSort(t *testing.T) {
  47. // Create some initial data
  48. size := 16 * blockSize
  49. data := make([]*item, size)
  50. for i := 0; i < size; i++ {
  51. data[i] = &item{rand.Int(), float32(i)}
  52. }
  53. // Push all the data into the stack
  54. stack := newSstack()
  55. for _, val := range data {
  56. stack.Push(val)
  57. }
  58. // Sort and pop the stack contents (should reverse the order)
  59. sort.Sort(stack)
  60. for _, val := range data {
  61. out := stack.Pop()
  62. if out != val {
  63. t.Errorf("push/pop mismatch after sort: have %v, want %v.", out, val)
  64. }
  65. }
  66. }
  67. func TestSstackReset(t *testing.T) {
  68. // Create some initial data
  69. size := 16 * blockSize
  70. data := make([]*item, size)
  71. for i := 0; i < size; i++ {
  72. data[i] = &item{rand.Int(), rand.Float32()}
  73. }
  74. stack := newSstack()
  75. for rep := 0; rep < 2; rep++ {
  76. // Push all the data into the stack, pop out every second
  77. secs := []*item{}
  78. for i := 0; i < size; i++ {
  79. stack.Push(data[i])
  80. if i%2 == 0 {
  81. secs = append(secs, stack.Pop().(*item))
  82. }
  83. }
  84. // Reset and verify both pulled and stack contents
  85. stack.Reset()
  86. if stack.Len() != 0 {
  87. t.Errorf("stack not empty after reset: %v", stack)
  88. }
  89. for i := 0; i < size; i++ {
  90. if i%2 == 0 && data[i] != secs[i/2] {
  91. t.Errorf("push/pop mismatch: have %v, want %v.", secs[i/2], data[i])
  92. }
  93. }
  94. }
  95. }