From c8f7879655125bcbf18f41897cf3f7e7385693aa Mon Sep 17 00:00:00 2001 From: Paul Buetow Date: Mon, 24 Aug 2020 17:25:35 +0100 Subject: refactor --- queue/elementarypq.go | 60 ---------------------------------- queue/elementarypriority.go | 60 ++++++++++++++++++++++++++++++++++ queue/pq.go | 10 ------ queue/pq_test.go | 78 --------------------------------------------- queue/priority.go | 10 ++++++ queue/queue_test.go | 78 +++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 148 insertions(+), 148 deletions(-) delete mode 100644 queue/elementarypq.go create mode 100644 queue/elementarypriority.go delete mode 100644 queue/pq.go delete mode 100644 queue/pq_test.go create mode 100644 queue/priority.go create mode 100644 queue/queue_test.go (limited to 'queue') diff --git a/queue/elementarypq.go b/queue/elementarypq.go deleted file mode 100644 index b66d531..0000000 --- a/queue/elementarypq.go +++ /dev/null @@ -1,60 +0,0 @@ -package queue - -import "algorithms/ds" - -type ElementaryPQ struct { - a ds.ArrayList - size int - // Initial capacity - capacity int -} - -func NewElementaryPQ(capacity int) *ElementaryPQ { - return &ElementaryPQ{make(ds.ArrayList, 0, capacity), 0, capacity} -} - -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) Clear() { - q.size = 0 - q.a = make(ds.ArrayList, 0, q.capacity) -} - -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/elementarypriority.go b/queue/elementarypriority.go new file mode 100644 index 0000000..508cbcb --- /dev/null +++ b/queue/elementarypriority.go @@ -0,0 +1,60 @@ +package queue + +import "algorithms/ds" + +type ElementaryPriority struct { + a ds.ArrayList + size int + // Initial capacity + capacity int +} + +func NewElementaryPriority(capacity int) *ElementaryPriority { + return &ElementaryPriority{make(ds.ArrayList, 0, capacity), 0, capacity} +} + +func (q *ElementaryPriority) Insert(a int) { + q.a = append(q.a, a) + q.size++ +} + +func (q *ElementaryPriority) Max() (max int) { + _, max = q.max() + return +} + +func (q *ElementaryPriority) 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 *ElementaryPriority) Empty() bool { + return q.Size() == 0 +} + +func (q *ElementaryPriority) Size() int { + return q.size +} + +func (q *ElementaryPriority) Clear() { + q.size = 0 + q.a = make(ds.ArrayList, 0, q.capacity) +} + +func (q *ElementaryPriority) 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 deleted file mode 100644 index 5f2079a..0000000 --- a/queue/pq.go +++ /dev/null @@ -1,10 +0,0 @@ -package queue - -type PQ interface { - Insert(a int) - Max() (max int) - DeleteMax() int - Empty() bool - Size() int - Clear() -} diff --git a/queue/pq_test.go b/queue/pq_test.go deleted file mode 100644 index 76ad187..0000000 --- a/queue/pq_test.go +++ /dev/null @@ -1,78 +0,0 @@ -package queue - -import ( - "algorithms/ds" - "fmt" - "testing" -) - -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 { - 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 - t.Log("Size", q.Size(), q.Empty()) - 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) -} - -func BenchmarkElementaryPQ(b *testing.B) { - q := NewElementaryPQ(1) - for i := minLength; i <= maxLength; i *= factor { - benchmark(q, i, b) - } -} - -func benchmark(q PQ, l int, b *testing.B) { - 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 benchResult { - q.Insert(a) - } - } - }) - - b.Run(fmt.Sprintf("randomInsertAndDeleteMax(%d)", l), func(b *testing.B) { - for i := 0; i < b.N; i++ { - q.Clear() - for _, a := range benchResult { - q.Insert(a) - } - for i := 0; !q.Empty(); i++ { - benchResult[i] = q.DeleteMax() - } - } - }) -} diff --git a/queue/priority.go b/queue/priority.go new file mode 100644 index 0000000..86dad68 --- /dev/null +++ b/queue/priority.go @@ -0,0 +1,10 @@ +package queue + +type PriorityQueue interface { + Insert(a int) + Max() (max int) + DeleteMax() int + Empty() bool + Size() int + Clear() +} diff --git a/queue/queue_test.go b/queue/queue_test.go new file mode 100644 index 0000000..6be87be --- /dev/null +++ b/queue/queue_test.go @@ -0,0 +1,78 @@ +package queue + +import ( + "algorithms/ds" + "fmt" + "testing" +) + +const minLength int = 1 +const maxLength int = 10000 +const factor int = 100 + +// Store results here to avoid compiler optimizations +var benchResult ds.ArrayList + +func TestElementaryPriority(t *testing.T) { + q := NewElementaryPriority(1) + for i := minLength; i <= maxLength; i *= factor { + test(q, i, t) + } +} + +func test(q PriorityQueue, 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 + t.Log("Size", q.Size(), q.Empty()) + 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) +} + +func BenchmarkElementaryPriority(b *testing.B) { + q := NewElementaryPriority(1) + for i := minLength; i <= maxLength; i *= factor { + benchmark(q, i, b) + } +} + +func benchmark(q PriorityQueue, l int, b *testing.B) { + 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 benchResult { + q.Insert(a) + } + } + }) + + b.Run(fmt.Sprintf("randomInsertAndDeleteMax(%d)", l), func(b *testing.B) { + for i := 0; i < b.N; i++ { + q.Clear() + for _, a := range benchResult { + q.Insert(a) + } + for i := 0; !q.Empty(); i++ { + benchResult[i] = q.DeleteMax() + } + } + }) +} -- cgit v1.2.3