elementary priority queue

4 files changed, 105 insertions, 0 deletions

diff --git a/ds/arraylist.go b/ds/arraylist.go
index e0e4536..feee14e 100644
--- a/ds/arraylist.go
+++ b/ds/arraylist.go
@@ -6,6 +6,7 @@ import (
 	"strings"
 )
 
+// Idea: Once Go got generics use generics here instead of hard coded int type
 type ArrayList []int
 
 func NewArrayList(l int) ArrayList {
diff --git a/queue/elementarypq.go b/queue/elementarypq.go
new file mode 100644
index 0000000..31cab9f
--- /dev/null
+++ b/queue/elementarypq.go
@@ -0,0 +1,53 @@
+package queue
+
+import "algorithms/ds"
+
+type ElementaryPQ struct {
+	a    ds.ArrayList
+	size int
+}
+
+func NewElementaryPQ(capacity int) ElementaryPQ {
+	return ElementaryPQ{make(ds.ArrayList, 0, capacity), 0}
+}
+
+func (q ElementaryPQ) Insert(a int) {
+	q.a = append(q.a, a)
+	q.size++
+}
+
+func (q ElementaryPQ) Max() (max int) {
+	_, max = q.max()
+	return
+}
+
+func (q ElementaryPQ) DeleteMax() int {
+	if q.Empty() {
+		return 0
+	}
+
+	ind, max := q.max()
+	for i := ind + 1; i < q.Size(); i++ {
+		q.a[i-1] = q.a[i]
+	}
+	q.size--
+
+	return max
+}
+
+func (q ElementaryPQ) Empty() bool {
+	return q.Size() == 0
+}
+
+func (q ElementaryPQ) Size() int {
+	return q.size
+}
+
+func (q ElementaryPQ) max() (ind, max int) {
+	for i, a := range q.a {
+		if a > max {
+			ind, max = i, a
+		}
+	}
+	return ind, max
+}
diff --git a/queue/pq.go b/queue/pq.go
new file mode 100644
index 0000000..ecf54c8
--- /dev/null
+++ b/queue/pq.go
@@ -0,0 +1,9 @@
+package queue
+
+type PQ interface {
+	Insert(a int)
+	Max() (max int)
+	DeleteMax() int
+	Empty() bool
+	Size() int
+}
diff --git a/queue/pq_test.go b/queue/pq_test.go
new file mode 100644
index 0000000..35e12fd
--- /dev/null
+++ b/queue/pq_test.go
@@ -0,0 +1,42 @@
+package queue
+
+import (
+	"algorithms/ds"
+	"fmt"
+	"testing"
+)
+
+const minLength int = 1
+const maxLength int = 1000
+const factor int = 10
+
+func TestElementaryPQ(t *testing.T) {
+	q := NewElementaryPQ(1)
+	for i := minLength; i <= maxLength; i *= factor {
+		test(q, i, t)
+	}
+}
+
+func test(q PQ, l int, t *testing.T) {
+	cb := func(t *testing.T) {
+		t.Parallel()
+		for _, a := range ds.NewRandomArrayList(l, -1) {
+			q.Insert(a)
+		}
+		prev, started := 0, false
+		for !q.Empty() {
+			next := q.DeleteMax()
+			if started {
+				if next < prev {
+					t.Errorf("Expected element '%v' to be lower than previous '%v': %v",
+						next, prev, q)
+				}
+				prev = next
+				continue
+			}
+			started = true
+			prev = next
+		}
+	}
+	t.Run(fmt.Sprintf("%d", l), cb)
+}