1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
var Heap = require('../lib/internal/Heap').default;
var {expect} = require('chai');
describe('Heap', () => {
it('push', () => {
var heap = new Heap();
expect(heap.length).to.eql(0);
heap.push({priority: 1, data: 'foo1'});
heap.push({priority: 2, data: 'foo2'});
heap.push({priority: 9, data: 'foo3'});
heap.push({priority: 2, data: 'foo4'});
heap.push({priority: 2, data: 'foo5'});
heap.push({priority: 5, data: 'foo6'});
heap.push({priority: -5, data: 'foo7'});
heap.push({priority: 1, data: 'foo8'});
expect(heap.length).to.eql(8);
expect(heap.shift().data).to.eql('foo7');
expect(heap.shift().data).to.eql('foo1');
heap.push({priority: -10, data: 'foo9'});
heap.push({priority: 12, data: 'foo10'});
expect(heap.shift().data).to.eql('foo9');
expect(heap.shift().data).to.eql('foo8');
expect(heap.shift().data).to.eql('foo2');
expect(heap.shift().data).to.eql('foo4');
expect(heap.shift().data).to.eql('foo5');
heap.push({priority: -1, data: 'foo11'});
heap.push({priority: 7, data: 'foo12'});
expect(heap.shift().data).to.eql('foo11');
expect(heap.shift().data).to.eql('foo6');
expect(heap.shift().data).to.eql('foo12');
expect(heap.shift().data).to.eql('foo3');
expect(heap.shift().data).to.eql('foo10');
expect(heap.length).to.eql(0);
});
it('toArray', () => {
var heap = new Heap();
expect(heap.toArray()).to.eql([]);
for (var i = 0; i < 5; i++) {
heap.push({data: i});
}
expect(heap.toArray()).to.eql([0, 1, 2, 3, 4]);
});
it('remove', () => {
var heap = new Heap();
for (var i = 0; i < 5; i++) {
heap.push({data: i});
}
heap.remove((node) => {
return node.data === 3;
})
expect(heap.toArray()).to.eql([0, 1, 2, 4]);
});
it('remove (head)', () => {
var heap = new Heap();
for (var i = 0; i < 5; i++) {
heap.push({data: i});
}
heap.remove((node) => {
return node.data === 0;
})
expect(heap.toArray()).to.eql([1, 2, 3, 4]);
});
it('remove (tail)', () => {
var heap = new Heap();
for (var i = 0; i < 5; i++) {
heap.push({data: i});
}
heap.remove((node) => {
return node.data === 4;
})
expect(heap.toArray()).to.eql([0, 1, 2, 3]);
});
it('remove (all)', () => {
var heap = new Heap();
for (var i = 0; i < 5; i++) {
heap.push({data: i});
}
heap.remove((node) => {
return node.data < 5;
})
expect(heap.toArray()).to.eql([]);
});
it('empty', () => {
var heap = new Heap();
for (var i = 0; i < 5; i++) {
heap.push({data: i});
}
var empty = heap.empty();
expect(heap).to.equal(empty);
expect(heap.toArray()).to.eql([]);
});
});
|
