Add timesHeap with tests

timesHeap uses timesHeapContainer for heap implementation.
It provides API to heap of requestTime for higher layers of requests
package.
It will be used for finding minimum time among ValidAfter, Deadline
and Timeout requests' times. Every time the minimum time will come
requests-workers matcher will be notified.

Change-Id: Ifb30ff0180c39fe9d8c4748253a0391e1cf8bc75
Signed-off-by: Lukasz Wojciechowski <l.wojciechow@partner.samsung.com>

2 files changed, 221 insertions, 0 deletions

diff --git a/requests/timesheap.go b/requests/timesheap.go
new file mode 100644
index 0000000..73c46c8
--- /dev/null
+++ b/requests/timesheap.go
@@ -0,0 +1,66 @@
+/*
+ *  Copyright (c) 2017-2018 Samsung Electronics Co., Ltd All Rights Reserved
+ *
+ *  Licensed under the Apache License, Version 2.0 (the "License");
+ *  you may not use this file except in compliance with the License.
+ *  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License
+ */
+
+// File requests/timesheap.go provides minimum heap implementation for requestTime.
+// timesHeap structure provides easy API for usage in higher layers of requests
+// package. It uses timesHeapContainer for heap implementation.
+
+package requests
+
+import (
+	"container/heap"
+)
+
+// timesHeap implements requestTime heap. Its methods build API easy to be used
+// by higher layers of requests package.
+type timesHeap struct {
+	con timesHeapContainer
+}
+
+// newTimesHeap creates new timesHeap object and initializes it as an empty heap.
+func newTimesHeap() *timesHeap {
+	h := new(timesHeap)
+	heap.Init(&h.con)
+	return h
+}
+
+// Len returns size of the heap.
+func (h *timesHeap) Len() int {
+	return h.con.Len()
+}
+
+// Min returns the minimum heap element (associated with the earliest time).
+// The returned element is not removed from the heap. Size of the heap doesn't
+// change. It panics if the heap is empty.
+func (h *timesHeap) Min() requestTime {
+	if h.con.Len() == 0 {
+		panic("cannot get Min of empty heap")
+	}
+	return h.con[0]
+}
+
+// Pop removes and returns the minimum heap element that is associated with
+// earliest time. Heap's size is decreased by one.
+// Method panics if the heap is empty.
+func (h *timesHeap) Pop() requestTime {
+	return heap.Pop(&h.con).(requestTime)
+}
+
+// Push adds the requestTime element to the heap, keeping its minimum value
+// property. Heap's size is increased by one.
+func (h *timesHeap) Push(t requestTime) {
+	heap.Push(&h.con, t)
+}
diff --git a/requests/timesheap_test.go b/requests/timesheap_test.go
new file mode 100644
index 0000000..8a114c0
--- /dev/null
+++ b/requests/timesheap_test.go
@@ -0,0 +1,155 @@
+/*
+ *  Copyright (c) 2017-2018 Samsung Electronics Co., Ltd All Rights Reserved
+ *
+ *  Licensed under the Apache License, Version 2.0 (the "License");
+ *  you may not use this file except in compliance with the License.
+ *  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License
+ */
+
+package requests
+
+import (
+	"time"
+
+	. "github.com/onsi/ginkgo"
+	. "github.com/onsi/gomega"
+)
+
+var _ = Describe("TimesHeap", func() {
+	var h *timesHeap
+	var t []time.Time
+	var r []requestTime
+	BeforeEach(func() {
+		now := time.Now()
+		t = make([]time.Time, 0)
+		for i := 0; i < 4; i++ {
+			t = append(t, now.AddDate(0, 0, i))
+
+		}
+
+		r = []requestTime{
+			{time: t[0], req: 1},
+			{time: t[1], req: 2},
+			{time: t[2], req: 3},
+			{time: t[3], req: 4},
+			{time: t[3], req: 5},
+			{time: t[1], req: 6},
+		}
+
+		h = newTimesHeap()
+	})
+
+	Describe("newTimesHeap", func() {
+		It("should create an empty heap", func() {
+			Expect(h).NotTo(BeNil())
+			Expect(h.Len()).To(BeZero())
+		})
+		It("should create a new heap every time called", func() {
+			h2 := newTimesHeap()
+
+			h.Push(r[1])
+			h2.Push(r[2])
+
+			Expect(h.Len()).To(Equal(1))
+			Expect(h2.Len()).To(Equal(1))
+			Expect(h.Min()).To(Equal(r[1]))
+			Expect(h2.Min()).To(Equal(r[2]))
+		})
+	})
+
+	Describe("Len", func() {
+		It("should return valid heap size", func() {
+			for i, e := range r {
+				h.Push(e)
+				Expect(h.Len()).To(Equal(i+1), "i=%v", i)
+			}
+
+			for i := len(r) - 1; i >= 0; i-- {
+				h.Pop()
+				Expect(h.Len()).To(Equal(i), "i=%v", i)
+			}
+		})
+	})
+
+	Describe("Min", func() {
+		It("should return minimum value of the heap", func() {
+			toPush := []int{3, 5, 1, 2}
+			pushMin := []int{3, 5, 1, 1}
+			for i, e := range toPush {
+				h.Push(r[e])
+				Expect(h.Min()).To(Equal(r[pushMin[i]]))
+			}
+
+			popMin := []int{5, 2, 3}
+			for _, e := range popMin {
+				h.Pop()
+				Expect(h.Min()).To(Equal(r[e]))
+			}
+		})
+		It("should panic in case of empty heap", func() {
+			Expect(func() {
+				h.Min()
+			}).Should(Panic())
+		})
+	})
+
+	Describe("Pop", func() {
+		It("should pop minimal element", func() {
+			toPush := []int{5, 3, 1, 0}
+			for _, e := range toPush {
+				h.Push(r[e])
+			}
+
+			pushMin := []int{0, 1, 5, 3}
+			for _, e := range pushMin {
+				Expect(h.Min()).To(Equal(r[e]))
+				Expect(h.Pop()).To(Equal(r[e]))
+			}
+		})
+		It("should decrease heap size by one", func() {
+			toPush := []int{0, 2, 1, 5}
+			for _, e := range toPush {
+				h.Push(r[e])
+			}
+
+			popMin := []int{0, 1, 5, 2}
+			for i, e := range popMin {
+				Expect(h.Len()).To(Equal(len(popMin) - i))
+				Expect(h.Pop()).To(Equal(r[e]))
+			}
+			Expect(h.Len()).To(BeZero())
+		})
+		It("should panic in case of empty heap", func() {
+			Expect(func() {
+				h.Pop()
+			}).Should(Panic())
+		})
+	})
+
+	Describe("Push", func() {
+		It("should add elements to the heap keeping minimum property", func() {
+			toPush := []int{4, 5, 1, 3}
+			pushMin := []int{4, 5, 1, 1}
+			for i, e := range toPush {
+				h.Push(r[e])
+				Expect(h.Min()).To(Equal(r[pushMin[i]]))
+			}
+		})
+		It("should increase heap size by one", func() {
+			Expect(h.Len()).To(BeZero())
+			toPush := []int{1, 0, 2, 4}
+			for i, e := range toPush {
+				h.Push(r[e])
+				Expect(h.Len()).To(Equal(i + 1))
+			}
+		})
+	})
+})