| 1 |
package minheap |
| 2 |
|
| 3 |
import ( |
| 4 |
. "launchpad.net/gocheck" |
| 5 |
"testing" |
| 6 |
) |
| 7 |
|
| 8 |
func Test(t *testing.T) { TestingT(t) } |
| 9 |
|
| 10 |
type MinHeapSuite struct{} |
| 11 |
|
| 12 |
var _ = Suite(&MinHeapSuite{}) |
| 13 |
|
| 14 |
func toEl(i int) interface{} { |
| 15 |
return &i |
| 16 |
} |
| 17 |
|
| 18 |
func fromEl(i interface{}) int { |
| 19 |
return *(i.(*int)) |
| 20 |
} |
| 21 |
|
| 22 |
func (s *MinHeapSuite) TestPeek(c *C) { |
| 23 |
mh := NewMinHeap() |
| 24 |
|
| 25 |
el := &Element{ |
| 26 |
Value: toEl(1), |
| 27 |
Priority: 5, |
| 28 |
} |
| 29 |
|
| 30 |
mh.PushEl(el) |
| 31 |
c.Assert(fromEl(mh.PeekEl().Value), Equals, 1) |
| 32 |
c.Assert(mh.Len(), Equals, 1) |
| 33 |
|
| 34 |
el = &Element{ |
| 35 |
Value: toEl(2), |
| 36 |
Priority: 1, |
| 37 |
} |
| 38 |
mh.PushEl(el) |
| 39 |
c.Assert(mh.Len(), Equals, 2) |
| 40 |
c.Assert(fromEl(mh.PeekEl().Value), Equals, 2) |
| 41 |
c.Assert(fromEl(mh.PeekEl().Value), Equals, 2) |
| 42 |
c.Assert(mh.Len(), Equals, 2) |
| 43 |
|
| 44 |
el = mh.PopEl() |
| 45 |
|
| 46 |
c.Assert(fromEl(el.Value), Equals, 2) |
| 47 |
c.Assert(mh.Len(), Equals, 1) |
| 48 |
c.Assert(fromEl(mh.PeekEl().Value), Equals, 1) |
| 49 |
|
| 50 |
mh.PopEl() |
| 51 |
c.Assert(mh.Len(), Equals, 0) |
| 52 |
} |
| 53 |
|
| 54 |
func (s *MinHeapSuite) TestUpdate(c *C) { |
| 55 |
mh := NewMinHeap() |
| 56 |
x := &Element{ |
| 57 |
Value: toEl(1), |
| 58 |
Priority: 4, |
| 59 |
} |
| 60 |
y := &Element{ |
| 61 |
Value: toEl(2), |
| 62 |
Priority: 3, |
| 63 |
} |
| 64 |
z := &Element{ |
| 65 |
Value: toEl(3), |
| 66 |
Priority: 8, |
| 67 |
} |
| 68 |
mh.PushEl(x) |
| 69 |
mh.PushEl(y) |
| 70 |
mh.PushEl(z) |
| 71 |
c.Assert(fromEl(mh.PeekEl().Value), Equals, 2) |
| 72 |
|
| 73 |
mh.UpdateEl(z, 1) |
| 74 |
c.Assert(fromEl(mh.PeekEl().Value), Equals, 3) |
| 75 |
|
| 76 |
mh.UpdateEl(x, 0) |
| 77 |
c.Assert(fromEl(mh.PeekEl().Value), Equals, 1) |
| 78 |
} |