| 1 | Heap = require '..'
|
| 2 | {random} = Math
|
| 3 |
|
| 4 | describe 'Heap#push, Heap#pop', ->
|
| 5 | it 'should sort an array using push and pop', ->
|
| 6 | heap = new Heap
|
| 7 | heap.push(random()) for i in [1..10]
|
| 8 | sorted = (heap.pop() until heap.empty())
|
| 9 | sorted.slice().sort().should.eql(sorted)
|
| 10 |
|
| 11 | it 'should work with custom comparison function', ->
|
| 12 | cmp = (a, b) ->
|
| 13 | return -1 if a > b
|
| 14 | return 1 if a < b
|
| 15 | 0
|
| 16 | heap = new Heap(cmp)
|
| 17 | heap.push(random()) for i in [1..10]
|
| 18 | sorted = (heap.pop() until heap.empty())
|
| 19 | sorted.slice().sort().reverse().should.eql(sorted)
|
| 20 |
|
| 21 | describe 'Heap#replace', ->
|
| 22 | it 'should behave like pop() followed by push()', ->
|
| 23 | heap = new Heap
|
| 24 | heap.push(v) for v in [1..5]
|
| 25 | heap.replace(3).should.eql(1)
|
| 26 | heap.toArray().sort().should.eql([2,3,3,4,5])
|
| 27 |
|
| 28 | describe 'Heap#pushpop', ->
|
| 29 | it 'should behave like push() followed by pop()', ->
|
| 30 | heap = new Heap
|
| 31 | heap.push(v) for v in [1..5]
|
| 32 | heap.pushpop(6).should.eql(1)
|
| 33 | heap.toArray().sort().should.eql([2..6])
|
| 34 |
|
| 35 | describe 'Heap#contains', ->
|
| 36 | it 'should return whether it contains the value', ->
|
| 37 | heap = new Heap
|
| 38 | heap.push(v) for v in [1..5]
|
| 39 | heap.contains(v).should.be.true for v in [1..5]
|
| 40 | heap.contains(0).should.be.false
|
| 41 | heap.contains(6).should.be.false
|
| 42 |
|
| 43 | describe 'Heap#peek', ->
|
| 44 | it 'should return the top value', ->
|
| 45 | heap = new Heap
|
| 46 | heap.push(1)
|
| 47 | heap.peek().should.eql(1)
|
| 48 | heap.push(2)
|
| 49 | heap.peek().should.eql(1)
|
| 50 | heap.pop()
|
| 51 | heap.peek().should.eql(2)
|
| 52 |
|
| 53 | describe 'Heap#clone', ->
|
| 54 | it 'should return a cloned heap', ->
|
| 55 | a = new Heap
|
| 56 | a.push(v) for v in [1..5]
|
| 57 | b = a.clone()
|
| 58 | a.toArray().should.eql(b.toArray())
|
| 59 |
|
| 60 | describe 'Heap.nsmallest', ->
|
| 61 | it 'should return exactly n elements when size() >= n', ->
|
| 62 | Heap.nsmallest([1..10], 3).should.eql([1..3])
|
| 63 |
|
| 64 | array = [1,3,2,1,3,4,4,2,3,4,5,1,2,3,4,5,2,1,3,4,5,6,7,2]
|
| 65 | Heap.nsmallest(array, 2).should.eql([1, 1])
|
| 66 |
|
| 67 | it 'should return size() elements when size() <= n', ->
|
| 68 | Heap.nsmallest([3..1], 10).should.eql([1..3])
|
| 69 |
|
| 70 | describe 'Heap.nlargest', ->
|
| 71 | it 'should return exactly n elements when size() >= n', ->
|
| 72 | Heap.nlargest([1..10], 3).should.eql([10..8])
|
| 73 |
|
| 74 | it 'should return size() elements when size() <= n', ->
|
| 75 | Heap.nlargest([3..1], 10).should.eql([3..1])
|
| 76 |
|
| 77 | describe 'Heap#updateItem', ->
|
| 78 | it 'should return correct order', ->
|
| 79 | a = x: 1
|
| 80 | b = x: 2
|
| 81 | c = x: 3
|
| 82 | h = new Heap (m, n) -> m.x - n.x
|
| 83 | h.push(a)
|
| 84 | h.push(b)
|
| 85 | h.push(c)
|
| 86 | c.x = 0
|
| 87 | h.updateItem(c)
|
| 88 | h.pop().should.eql(c)
|