1  package queue
 2  
 3  import (
 4  	"math/rand"
 5  	"testing"
 6  	"time"
 7  )
 8  
 9  type testQueueItem struct {
10  	Value  int
11  	Expiry time.Time
12  }
13  
14  func (e testQueueItem) Less(other PriorityQueueItem) bool {
15  	return e.Expiry.Before(other.(*testQueueItem).Expiry)
16  }
17  
18  func TestExpiryQueue(t *testing.T) {
19  	// The number of elements we push to the queue.
20  	count := 100
21  	// Generate a random permutation of a range [0, count)
22  	array := rand.Perm(count)
23  	// t0 holds a reference time point.
24  	t0 := time.Date(1975, time.April, 5, 12, 0, 0, 0, time.UTC)
25  
26  	var testQueue PriorityQueue
27  
28  	if testQueue.Len() != 0 && !testQueue.Empty() {
29  		t.Fatal("Expected the queue to be empty")
30  	}
31  
32  	// Create elements with expiry of t0 + value * second.
33  	for _, value := range array {
34  		testQueue.Push(&testQueueItem{
35  			Value:  value,
36  			Expiry: t0.Add(time.Duration(value) * time.Second),
37  		})
38  	}
39  
40  	// Now expect that we can retrieve elements in order of their expiry.
41  	for i := 0; i < count; i++ {
42  		expectedQueueLen := count - i
43  		if testQueue.Len() != expectedQueueLen {
44  			t.Fatalf("Expected the queue len %v, got %v",
45  				expectedQueueLen, testQueue.Len())
46  		}
47  
48  		if testQueue.Empty() {
49  			t.Fatalf("Did not expect the queue to be empty")
50  		}
51  
52  		top := testQueue.Top().(*testQueueItem)
53  		if top.Value != i {
54  			t.Fatalf("Expected queue top %v, got %v", i, top.Value)
55  		}
56  
57  		popped := testQueue.Pop().(*testQueueItem)
58  		if popped != top {
59  			t.Fatalf("Expected queue top %v equal to popped: %v",
60  				top, popped)
61  		}
62  	}
63  
64  	if testQueue.Len() != 0 || !testQueue.Empty() {
65  		t.Fatalf("Expected the queue to be empty")
66  	}
67  }