From b6329c9c286b09d2f974fd134cbe3029b1e4e11f Mon Sep 17 00:00:00 2001
From: Paul Buetow <pbuetow@mimecast.com>
Date: Mon, 24 Aug 2020 17:22:58 +0100
Subject: fix elementary pq

---
 queue/elementarypq.go | 18 +++++++++---------
 queue/pq_test.go      | 15 +++++++++------
 2 files changed, 18 insertions(+), 15 deletions(-)

diff --git a/queue/elementarypq.go b/queue/elementarypq.go
index 1155cb4..b66d531 100644
--- a/queue/elementarypq.go
+++ b/queue/elementarypq.go
@@ -9,21 +9,21 @@ type ElementaryPQ struct {
 	capacity int
 }
 
-func NewElementaryPQ(capacity int) ElementaryPQ {
-	return ElementaryPQ{make(ds.ArrayList, 0, capacity), 0, capacity}
+func NewElementaryPQ(capacity int) *ElementaryPQ {
+	return &ElementaryPQ{make(ds.ArrayList, 0, capacity), 0, capacity}
 }
 
-func (q ElementaryPQ) Insert(a int) {
+func (q *ElementaryPQ) Insert(a int) {
 	q.a = append(q.a, a)
 	q.size++
 }
 
-func (q ElementaryPQ) Max() (max int) {
+func (q *ElementaryPQ) Max() (max int) {
 	_, max = q.max()
 	return
 }
 
-func (q ElementaryPQ) DeleteMax() int {
+func (q *ElementaryPQ) DeleteMax() int {
 	if q.Empty() {
 		return 0
 	}
@@ -37,20 +37,20 @@ func (q ElementaryPQ) DeleteMax() int {
 	return max
 }
 
-func (q ElementaryPQ) Empty() bool {
+func (q *ElementaryPQ) Empty() bool {
 	return q.Size() == 0
 }
 
-func (q ElementaryPQ) Size() int {
+func (q *ElementaryPQ) Size() int {
 	return q.size
 }
 
-func (q ElementaryPQ) Clear() {
+func (q *ElementaryPQ) Clear() {
 	q.size = 0
 	q.a = make(ds.ArrayList, 0, q.capacity)
 }
 
-func (q ElementaryPQ) max() (ind, max int) {
+func (q *ElementaryPQ) max() (ind, max int) {
 	for i, a := range q.a {
 		if a > max {
 			ind, max = i, a
diff --git a/queue/pq_test.go b/queue/pq_test.go
index 0b13144..76ad187 100644
--- a/queue/pq_test.go
+++ b/queue/pq_test.go
@@ -10,6 +10,9 @@ const minLength int = 1
 const maxLength int = 10000
 const factor int = 100
 
+// Store results here to avoid compiler optimizations
+var benchResult ds.ArrayList
+
 func TestElementaryPQ(t *testing.T) {
 	q := NewElementaryPQ(1)
 	for i := minLength; i <= maxLength; i *= factor {
@@ -24,10 +27,11 @@ func test(q PQ, l int, t *testing.T) {
 			q.Insert(a)
 		}
 		prev, started := 0, false
+		t.Log("Size", q.Size(), q.Empty())
 		for !q.Empty() {
 			next := q.DeleteMax()
 			if started {
-				if next < prev {
+				if next > prev {
 					t.Errorf("Expected element '%v' to be lower than previous '%v': %v",
 						next, prev, q)
 				}
@@ -49,13 +53,12 @@ func BenchmarkElementaryPQ(b *testing.B) {
 }
 
 func benchmark(q PQ, l int, b *testing.B) {
-	r := ds.NewRandomArrayList(l, -1)
-	aux := ds.NewArrayList(l)
+	benchResult = ds.NewRandomArrayList(l, -1)
 
 	b.Run(fmt.Sprintf("randomInsert(%d)", l), func(b *testing.B) {
 		for i := 0; i < b.N; i++ {
 			q.Clear()
-			for _, a := range r {
+			for _, a := range benchResult {
 				q.Insert(a)
 			}
 		}
@@ -64,11 +67,11 @@ func benchmark(q PQ, l int, b *testing.B) {
 	b.Run(fmt.Sprintf("randomInsertAndDeleteMax(%d)", l), func(b *testing.B) {
 		for i := 0; i < b.N; i++ {
 			q.Clear()
-			for _, a := range r {
+			for _, a := range benchResult {
 				q.Insert(a)
 			}
 			for i := 0; !q.Empty(); i++ {
-				aux[i] = q.DeleteMax()
+				benchResult[i] = q.DeleteMax()
 			}
 		}
 	})
-- 
cgit v1.2.3