123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131 |
- // CookieJar - A contestant's algorithm toolbox
- // Copyright (c) 2013 Peter Szilagyi. All rights reserved.
- //
- // CookieJar is dual licensed: use of this source code is governed by a BSD
- // license that can be found in the LICENSE file. Alternatively, the CookieJar
- // toolbox may be used in accordance with the terms and conditions contained
- // in a signed written agreement between you and the author(s).
- package prque
- import (
- "math/rand"
- "testing"
- )
- func TestPrque(t *testing.T) {
- // Generate a batch of random data and a specific priority order
- size := 16 * blockSize
- prio := rand.Perm(size)
- data := make([]int, size)
- for i := 0; i < size; i++ {
- data[i] = rand.Int()
- }
- queue := New()
- for rep := 0; rep < 2; rep++ {
- // Fill a priority queue with the above data
- for i := 0; i < size; i++ {
- queue.Push(data[i], float32(prio[i]))
- if queue.Size() != i+1 {
- t.Errorf("queue size mismatch: have %v, want %v.", queue.Size(), i+1)
- }
- }
- // Create a map the values to the priorities for easier verification
- dict := make(map[float32]int)
- for i := 0; i < size; i++ {
- dict[float32(prio[i])] = data[i]
- }
- // Pop out the elements in priority order and verify them
- prevPrio := float32(size + 1)
- for !queue.Empty() {
- val, prio := queue.Pop()
- if prio > prevPrio {
- t.Errorf("invalid priority order: %v after %v.", prio, prevPrio)
- }
- prevPrio = prio
- if val != dict[prio] {
- t.Errorf("push/pop mismatch: have %v, want %v.", val, dict[prio])
- }
- delete(dict, prio)
- }
- }
- }
- func TestReset(t *testing.T) {
- // Generate a batch of random data and a specific priority order
- size := 16 * blockSize
- prio := rand.Perm(size)
- data := make([]int, size)
- for i := 0; i < size; i++ {
- data[i] = rand.Int()
- }
- queue := New()
- for rep := 0; rep < 2; rep++ {
- // Fill a priority queue with the above data
- for i := 0; i < size; i++ {
- queue.Push(data[i], float32(prio[i]))
- if queue.Size() != i+1 {
- t.Errorf("queue size mismatch: have %v, want %v.", queue.Size(), i+1)
- }
- }
- // Create a map the values to the priorities for easier verification
- dict := make(map[float32]int)
- for i := 0; i < size; i++ {
- dict[float32(prio[i])] = data[i]
- }
- // Pop out half the elements in priority order and verify them
- prevPrio := float32(size + 1)
- for i := 0; i < size/2; i++ {
- val, prio := queue.Pop()
- if prio > prevPrio {
- t.Errorf("invalid priority order: %v after %v.", prio, prevPrio)
- }
- prevPrio = prio
- if val != dict[prio] {
- t.Errorf("push/pop mismatch: have %v, want %v.", val, dict[prio])
- }
- delete(dict, prio)
- }
- // Reset and ensure it's empty
- queue.Reset()
- if !queue.Empty() {
- t.Errorf("priority queue not empty after reset: %v", queue)
- }
- }
- }
- func BenchmarkPush(b *testing.B) {
- // Create some initial data
- data := make([]int, b.N)
- prio := make([]float32, b.N)
- for i := 0; i < len(data); i++ {
- data[i] = rand.Int()
- prio[i] = rand.Float32()
- }
- // Execute the benchmark
- b.ResetTimer()
- queue := New()
- for i := 0; i < len(data); i++ {
- queue.Push(data[i], prio[i])
- }
- }
- func BenchmarkPop(b *testing.B) {
- // Create some initial data
- data := make([]int, b.N)
- prio := make([]float32, b.N)
- for i := 0; i < len(data); i++ {
- data[i] = rand.Int()
- prio[i] = rand.Float32()
- }
- queue := New()
- for i := 0; i < len(data); i++ {
- queue.Push(data[i], prio[i])
- }
- // Execute the benchmark
- b.ResetTimer()
- for !queue.Empty() {
- queue.Pop()
- }
- }
|