libgo/go/container/heap/heap_test.go

   1 // Copyright 2009 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package heap
   6
   7 import (
   8         "testing"
   9         "container/vector"
  10 )
  11
  12
  13 type myHeap struct {
  14         // A vector.Vector implements sort.Interface except for Less,
  15         // and it implements Push and Pop as required for heap.Interface.
  16         vector.Vector
  17 }
  18
  19
  20 func (h *myHeap) Less(i, j int) bool { return h.At(i).(int) < h.At(j).(int) }
  21
  22
  23 func (h *myHeap) verify(t *testing.T, i int) {
  24         n := h.Len()
  25         j1 := 2*i + 1
  26         j2 := 2*i + 2
  27         if j1 < n {
  28                 if h.Less(j1, i) {
  29                         t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h.At(i), j1, h.At(j1))
  30                         return
  31                 }
  32                 h.verify(t, j1)
  33         }
  34         if j2 < n {
  35                 if h.Less(j2, i) {
  36                         t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h.At(i), j1, h.At(j2))
  37                         return
  38                 }
  39                 h.verify(t, j2)
  40         }
  41 }
  42
  43
  44 func TestInit0(t *testing.T) {
  45         h := new(myHeap)
  46         for i := 20; i > 0; i-- {
  47                 h.Push(0) // all elements are the same
  48         }
  49         Init(h)
  50         h.verify(t, 0)
  51
  52         for i := 1; h.Len() > 0; i++ {
  53                 x := Pop(h).(int)
  54                 h.verify(t, 0)
  55                 if x != 0 {
  56                         t.Errorf("%d.th pop got %d; want %d", i, x, 0)
  57                 }
  58         }
  59 }
  60
  61
  62 func TestInit1(t *testing.T) {
  63         h := new(myHeap)
  64         for i := 20; i > 0; i-- {
  65                 h.Push(i) // all elements are different
  66         }
  67         Init(h)
  68         h.verify(t, 0)
  69
  70         for i := 1; h.Len() > 0; i++ {
  71                 x := Pop(h).(int)
  72                 h.verify(t, 0)
  73                 if x != i {
  74                         t.Errorf("%d.th pop got %d; want %d", i, x, i)
  75                 }
  76         }
  77 }
  78
  79
  80 func Test(t *testing.T) {
  81         h := new(myHeap)
  82         h.verify(t, 0)
  83
  84         for i := 20; i > 10; i-- {
  85                 h.Push(i)
  86         }
  87         Init(h)
  88         h.verify(t, 0)
  89
  90         for i := 10; i > 0; i-- {
  91                 Push(h, i)
  92                 h.verify(t, 0)
  93         }
  94
  95         for i := 1; h.Len() > 0; i++ {
  96                 x := Pop(h).(int)
  97                 if i < 20 {
  98                         Push(h, 20+i)
  99                 }
 100                 h.verify(t, 0)
 101                 if x != i {
 102                         t.Errorf("%d.th pop got %d; want %d", i, x, i)
 103                 }
 104         }
 105 }
 106
 107
 108 func TestRemove0(t *testing.T) {
 109         h := new(myHeap)
 110         for i := 0; i < 10; i++ {
 111                 h.Push(i)
 112         }
 113         h.verify(t, 0)
 114
 115         for h.Len() > 0 {
 116                 i := h.Len() - 1
 117                 x := Remove(h, i).(int)
 118                 if x != i {
 119                         t.Errorf("Remove(%d) got %d; want %d", i, x, i)
 120                 }
 121                 h.verify(t, 0)
 122         }
 123 }
 124
 125
 126 func TestRemove1(t *testing.T) {
 127         h := new(myHeap)
 128         for i := 0; i < 10; i++ {
 129                 h.Push(i)
 130         }
 131         h.verify(t, 0)
 132
 133         for i := 0; h.Len() > 0; i++ {
 134                 x := Remove(h, 0).(int)
 135                 if x != i {
 136                         t.Errorf("Remove(0) got %d; want %d", x, i)
 137                 }
 138                 h.verify(t, 0)
 139         }
 140 }
 141
 142
 143 func TestRemove2(t *testing.T) {
 144         N := 10
 145
 146         h := new(myHeap)
 147         for i := 0; i < N; i++ {
 148                 h.Push(i)
 149         }
 150         h.verify(t, 0)
 151
 152         m := make(map[int]bool)
 153         for h.Len() > 0 {
 154                 m[Remove(h, (h.Len()-1)/2).(int)] = true
 155                 h.verify(t, 0)
 156         }
 157
 158         if len(m) != N {
 159                 t.Errorf("len(m) = %d; want %d", len(m), N)
 160         }
 161         for i := 0; i < len(m); i++ {
 162                 if !m[i] {
 163                         t.Errorf("m[%d] doesn't exist", i)
 164                 }
 165         }
 166 }