1// Copyright 2017 Google Inc. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14package pq 15 16import "testing" 17 18func TestQueue(t *testing.T) { 19 pq := NewQueue(func(x, y interface{}) bool { 20 return x.(string) < y.(string) 21 }, nil) 22 if n := pq.Len(); n != 0 { 23 t.Fatalf("pq.Len() = %d want 0", n) 24 } 25 pq.Push("Go") 26 pq.Push("C++") 27 pq.Push("Java") 28 for i, want := range []string{"C++", "Go", "Java"} { 29 wantLen := 3 - i 30 if n := pq.Len(); n != wantLen { 31 t.Fatalf("pq.Len() = %d want %d", n, wantLen) 32 } 33 if s := pq.Min().(string); s != want { 34 t.Fatalf("pq.Min() = %q want %q", s, want) 35 } 36 if n := pq.Len(); n != wantLen { 37 t.Fatalf("pq.Len() = %d want %d", n, wantLen) 38 } 39 if s := pq.Pop().(string); s != want { 40 t.Fatalf("pq.Pop() = %q want %q", s, want) 41 } 42 if n := pq.Len(); n != wantLen-1 { 43 t.Fatalf("pq.Len() = %d want %d", n, wantLen-1) 44 } 45 } 46 if n := pq.Len(); n != 0 { 47 t.Fatalf("pq.Len() = %d want 0", n) 48 } 49} 50 51// Test that reprioritizing an item works. 52func TestFix(t *testing.T) { 53 type item struct { 54 value int 55 index int 56 } 57 pq := NewQueue(func(x, y interface{}) bool { 58 return x.(*item).value < y.(*item).value 59 }, func(x interface{}, index int) { 60 x.(*item).index = index 61 }) 62 if n := pq.Len(); n != 0 { 63 t.Fatalf("pq.Len() = %d want 0", n) 64 } 65 i1 := &item{value: 1} 66 i2 := &item{value: 2} 67 i3 := &item{value: 3} 68 pq.Push(i3) 69 pq.Push(i1) 70 pq.Push(i2) 71 if n := pq.Len(); n != 3 { 72 t.Fatalf("pq.Len() = %d want 3", n) 73 } 74 for i, it := range []*item{i1, i2, i3} { 75 if i == 0 && it.index != 0 { 76 t.Errorf("item %+v want index 0", it) 77 } 78 if it.value != i+1 { 79 t.Errorf("item %+v want value %d", it, i+1) 80 } 81 } 82 i1.value = 4 83 pq.Fix(i1.index) 84 if n := pq.Len(); n != 3 { 85 t.Fatalf("pq.Len() = %d want 3", n) 86 } 87 for i, it := range []*item{i2, i3, i1} { 88 if i == 0 && it.index != 0 { 89 t.Errorf("item %+v want index 0", it) 90 } 91 if it.value != i+2 { 92 t.Errorf("item %+v want value %d", it, i+2) 93 } 94 } 95 for i, want := range []int{2, 3, 4} { 96 wantLen := 3 - i 97 if n := pq.Len(); n != wantLen { 98 t.Fatalf("pq.Len() = %d want %d", n, wantLen) 99 } 100 if it := pq.Min().(*item); it.value != want { 101 t.Fatalf("pq.Min() = %+v want value %d", it, want) 102 } 103 if n := pq.Len(); n != wantLen { 104 t.Fatalf("pq.Len() = %d want %d", n, wantLen) 105 } 106 if it := pq.Pop().(*item); it.value != want { 107 t.Fatalf("pq.Pop() = %+v want value %d", it, want) 108 } 109 if n := pq.Len(); n != wantLen-1 { 110 t.Fatalf("pq.Len() = %d want %d", n, wantLen-1) 111 } 112 } 113 if n := pq.Len(); n != 0 { 114 t.Fatalf("pq.Len() = %d want 0", n) 115 } 116} 117 118func TestRemove(t *testing.T) { 119 type item struct { 120 value int 121 index int 122 } 123 pq := NewQueue(func(x, y interface{}) bool { 124 return x.(*item).value < y.(*item).value 125 }, func(x interface{}, index int) { 126 x.(*item).index = index 127 }) 128 if n := pq.Len(); n != 0 { 129 t.Fatalf("pq.Len() = %d want 0", n) 130 } 131 i1 := &item{value: 1} 132 i2 := &item{value: 2} 133 i3 := &item{value: 3} 134 pq.Push(i3) 135 pq.Push(i1) 136 pq.Push(i2) 137 if n := pq.Len(); n != 3 { 138 t.Fatalf("pq.Len() = %d want 3", n) 139 } 140 for i, it := range []*item{i1, i2, i3} { 141 if i == 0 && it.index != 0 { 142 t.Errorf("item %+v want index 0", it) 143 } 144 if it.value != i+1 { 145 t.Errorf("item %+v want value %d", it, i+1) 146 } 147 } 148 pq.Remove(i3.index) 149 if n := pq.Len(); n != 2 { 150 t.Fatalf("pq.Len() = %d want 2", n) 151 } 152 for i, it := range []*item{i1, i2} { 153 if i == 0 && it.index != 0 { 154 t.Errorf("item %+v want index 0", it) 155 } 156 if it.value != i+1 { 157 t.Errorf("item %+v want value %d", it, i+2) 158 } 159 } 160 for i, want := range []int{1, 2} { 161 wantLen := 2 - i 162 if n := pq.Len(); n != wantLen { 163 t.Fatalf("pq.Len() = %d want %d", n, wantLen) 164 } 165 if it := pq.Min().(*item); it.value != want { 166 t.Fatalf("pq.Min() = %+v want value %d", it, want) 167 } 168 if n := pq.Len(); n != wantLen { 169 t.Fatalf("pq.Len() = %d want %d", n, wantLen) 170 } 171 if it := pq.Pop().(*item); it.value != want { 172 t.Fatalf("pq.Pop() = %+v want value %d", it, want) 173 } 174 if n := pq.Len(); n != wantLen-1 { 175 t.Fatalf("pq.Len() = %d want %d", n, wantLen-1) 176 } 177 } 178 if n := pq.Len(); n != 0 { 179 t.Fatalf("pq.Len() = %d want 0", n) 180 } 181} 182