AbstractAddressableHeapTest::testDeleteNodes() - Code Metrics - bingo-soft/heap - Measure and Improve Code Quality continuously with Scrutinizer

AbstractAddressableHeapTest::testDeleteNodes() A
last analyzed 2019-11-25 07:56 UTC

↳ Parent: AbstractAddressableHeapTest

Complexity

Conditions	2
Paths	2

Size

Total Lines	39
Code Lines	34

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	2
eloc	34
c	0
b	0
f	0
nc	2
nop	0
dl	0
loc	39
rs	9.376

<?php

namespace tests;

use PHPUnit\Framework\TestCase;
use Exception;
use InvalidArgumentException;
use TypeError;
use Heap\AddressableHeapInterface;
use Heap\Exception\NoSuchElementException;

abstract class AbstractAddressableHeapTest extends TestCase
{
    protected const SIZE = 100;

    abstract protected function createHeap(): AddressableHeapInterface;

    public function testInsert(): void
    {
        $heap = $this->createHeap();
       
        for ($i = 0; $i < self::SIZE; $i += 1) {
            $heap->insert($i);
            $this->assertEquals(0, $heap->findMin()->getKey());
            $this->assertFalse($heap->isEmpty());
            $this->assertEquals($heap->size(), $i + 1);
        }

        for ($i = self::SIZE - 1; $i >= 0; $i -= 1) {
            $this->assertEquals($heap->findMin()->getKey(), self::SIZE - $i - 1);
            $heap->deleteMin();
        }
    }

    public function testSetValue(): void
    {
        $heap = $this->createHeap();
        $heap->insert(1, "value1")->setValue("value2");
        $this->assertEquals("value2", $heap->findMin()->getValue());
    }

    public function testEmptyAfterDeleteAll(): void
    {
        $heap = $this->createHeap();
        $heap->insert(780);
        $this->assertEquals($heap->size(), 1);
        $this->assertEquals(780, $heap->findMin()->getKey());

        $heap->insert(-389);
        $this->assertEquals($heap->size(), 2);
        $this->assertEquals(-389, $heap->findMin()->getKey());

        $heap->insert(306);
        $this->assertEquals($heap->size(), 3);
        $this->assertEquals(-389, $heap->findMin()->getKey());

        $heap->insert(579);
        $this->assertEquals($heap->size(), 4);
        $this->assertEquals(-389, $heap->findMin()->getKey());

        $heap->deleteMin();
        $this->assertEquals($heap->size(), 3);
        $this->assertEquals(306, $heap->findMin()->getKey());

        $heap->deleteMin();
        $this->assertEquals($heap->size(), 2);
        $this->assertEquals(579, $heap->findMin()->getKey());

        $heap->deleteMin();
        $this->assertEquals($heap->size(), 1);
        $this->assertEquals(780, $heap->findMin()->getKey());

        $heap->deleteMin();
        $this->assertEquals($heap->size(), 0);

        $this->assertTrue($heap->isEmpty());
    }

    public function testRandomDelete(): void
    {
        $heap = $this->createHeap();

        for ($i = 0; $i < self::SIZE; $i += 1) {
            $heap->insert(random_int(0, 100000));
        }

        $prev = null;
        $i = 0;
        while (!$heap->isEmpty()) {
            $cur = $heap->findMin()->getKey();
            $heap->deleteMin();
            if (!is_null($prev)) {
                $this->assertTrue($prev <= $cur);
            }
            $prev = $cur;
            $i += 1;
        }
    }

    public function testFindDeleteSame(): void
    {
        $heap = $this->createHeap();

        for ($i = 0; $i < self::SIZE; $i += 1) {
            $heap->insert(random_int(0, 100000));
        }

        while (!$heap->isEmpty()) {
            $this->assertEquals($heap->findMin(), $heap->deleteMin());
        }
    }

    public function testDeleteNodes(): void
    {
        $heap = $this->createHeap();

        $nodes = [];
        for ($i = 0; $i < 15; $i += 1) {
            $nodes[$i] = $heap->insert($i);
        }

        $nodes[5]->delete();
        $this->assertEquals(0, $heap->findMin()->getKey());
        $nodes[7]->delete();
        $this->assertEquals(0, $heap->findMin()->getKey());
        $nodes[0]->delete();
        $this->assertEquals(1, $heap->findMin()->getKey());
        $nodes[2]->delete();
        $this->assertEquals(1, $heap->findMin()->getKey());
        $nodes[1]->delete();
        $this->assertEquals(3, $heap->findMin()->getKey());
        $nodes[3]->delete();
        $this->assertEquals(4, $heap->findMin()->getKey());
        $nodes[9]->delete();
        $this->assertEquals(4, $heap->findMin()->getKey());
        $nodes[4]->delete();
        $this->assertEquals(6, $heap->findMin()->getKey());
        $nodes[8]->delete();
        $this->assertEquals(6, $heap->findMin()->getKey());
        $nodes[11]->delete();
        $this->assertEquals(6, $heap->findMin()->getKey());
        $nodes[6]->delete();
        $this->assertEquals(10, $heap->findMin()->getKey());
        $nodes[12]->delete();
        $this->assertEquals(10, $heap->findMin()->getKey());
        $nodes[10]->delete();
        $this->assertEquals(13, $heap->findMin()->getKey());
        $nodes[13]->delete();
        $this->assertEquals(14, $heap->findMin()->getKey());
        $nodes[14]->delete();
        $this->assertTrue($heap->isEmpty());
    }

    public function testNodesRandomDelete(): void
    {
        $heap = $this->createHeap();

        $nodes = [];
        for ($i = 0; $i < 8; $i += 1) {
            $nodes[$i] = $heap->insert($i);
        }

        $nodes[5]->delete();
        $this->assertEquals(0, $heap->findMin()->getKey());
        $nodes[7]->delete();
        $this->assertEquals(0, $heap->findMin()->getKey());
        $nodes[0]->delete();
        $this->assertEquals(1, $heap->findMin()->getKey());
        $nodes[2]->delete();
        $this->assertEquals(1, $heap->findMin()->getKey());
        $nodes[1]->delete();
        $this->assertEquals(3, $heap->findMin()->getKey());
    }

    public function testAddDelete(): void
    {
        $heap = $this->createHeap();

        $nodes = [];
        for ($i = 0; $i < self::SIZE; $i += 1) {
            $nodes[$i] = $heap->insert($i);
        }

        for ($i = self::SIZE - 1; $i >= 0; $i -= 1) {
            $nodes[$i]->delete();
            if ($i > 0) {
                $this->assertEquals(0, $heap->findMin()->getKey());
            }
        }
        $this->assertTrue($heap->isEmpty());
    }

    public function testDeleteTwice(): void
    {
        $heap = $this->createHeap();

        $nodes = [];
        for ($i = 0; $i < 15; $i += 1) {
            $nodes[$i] = $heap->insert($i);
        }

        $nodes[5]->delete();
        $this->assertEquals(0, $heap->findMin()->getKey());
        $nodes[7]->delete();
        $this->assertEquals(0, $heap->findMin()->getKey());
        $nodes[0]->delete();
        $this->assertEquals(1, $heap->findMin()->getKey());
        $nodes[2]->delete();
        $this->assertEquals(1, $heap->findMin()->getKey());
        $nodes[1]->delete();
        $this->assertEquals(3, $heap->findMin()->getKey());
        $nodes[3]->delete();
        $this->assertEquals(4, $heap->findMin()->getKey());
        $nodes[9]->delete();
        $this->assertEquals(4, $heap->findMin()->getKey());
        $nodes[4]->delete();
        $this->assertEquals(6, $heap->findMin()->getKey());

        // again
        $this->expectException(InvalidArgumentException::class);
        $nodes[2]->delete();
    }

    public function testDeleteMindeleteTwice(): void
    {
        $heap = $this->createHeap();
        $e1 = $heap->insert(50);
        $heap->insert(100);
        $heap->deleteMin();
        $this->expectException(InvalidArgumentException::class);
        $e1->delete();
    }

    public function testDeleteMinDeleteTwiceChained(): void
    {
        $heap = $this->createHeap();
        for ($i = 0; $i < 15; $i += 1) {
            $heap->insert($i);
        }
        $this->expectException(InvalidArgumentException::class);
        $heap->deleteMin()->delete();
    }

    public function testDeleteMinDecreaseKey(): void
    {
        $heap = $this->createHeap();
        for ($i = 100; $i < 200; $i += 1) {
            $heap->insert($i);
        }
        $this->expectException(InvalidArgumentException::class);
        $heap->deleteMin()->decreaseKey(0);
    }

    public function testNoElementFindMin(): void
    {
        $heap = $this->createHeap();
        $this->expectException(NoSuchElementException::class);
        $heap->findMin();
    }

    public function testDeleteMinFindMin(): void
    {
        $heap = $this->createHeap();
        $this->expectException(NoSuchElementException::class);
        $heap->deleteMin();
    }

    /*public function testNullPointerException(): void
    {
        $heap = $this->createHeap();
        $this->expectException(TypeError::class);
        $heap->insert(null, null);
    }*/

    public function testDecreaseKey(): void
    {
        $heap = $this->createHeap();
        $nodes = [];
        for ($i = 0; $i < 15; $i += 1) {
            $nodes[$i] = $heap->insert($i + 100);
        }
        $this->assertEquals(100, $heap->findMin()->getKey());
        $nodes[5]->decreaseKey(5);
        $this->assertEquals(5, $heap->findMin()->getKey());
        $nodes[1]->decreaseKey(50);
        $this->assertEquals(5, $heap->findMin()->getKey());
        $nodes[1]->decreaseKey(20);
        $this->assertEquals(5, $heap->findMin()->getKey());
        $nodes[5]->delete();
        $this->assertEquals(20, $heap->findMin()->getKey());
        $nodes[10]->decreaseKey(3);
        $this->assertEquals(3, $heap->findMin()->getKey());
        $nodes[0]->decreaseKey(0);
        $this->assertEquals(0, $heap->findMin()->getKey());
    }

    public function testDecreaseKeyAndDelete(): void
    {
        $heap = $this->createHeap();
        $nodes = [];
        for ($i = 0; $i < 1000; $i += 1) {
            $nodes[$i] = $heap->insert($i + 2000);
        }
        for ($i = 999; $i >= 0; $i -= 1) {
            $nodes[$i]->decreaseKey($nodes[$i]->getKey() - 2000);
        }
        for ($i = 0; $i < 1000; $i += 1) {
            $this->assertEquals($i, $heap->deleteMin()->getKey());
        }
    }

    public function testIncreaseKeyException(): void
    {
        $heap = $this->createHeap();
        $nodes = [];
        for ($i = 0; $i < 15; $i += 1) {
            $nodes[$i] = $heap->insert($i + 100);
        }
        $this->assertEquals(100, $heap->findMin()->getKey());
        $nodes[5]->decreaseKey(5);
        $this->assertEquals(5, $heap->findMin()->getKey());
        $this->expectException(InvalidArgumentException::class);
        $nodes[1]->decreaseKey(102);
    }
}


1			<?php
2
3			namespace tests;
4
5			use PHPUnit\Framework\TestCase;
6			use Exception;
7			use InvalidArgumentException;
8			use TypeError;
9			use Heap\AddressableHeapInterface;
10			use Heap\Exception\NoSuchElementException;
11
12			abstract class AbstractAddressableHeapTest extends TestCase
13			{
14			protected const SIZE = 100;
15
16			abstract protected function createHeap(): AddressableHeapInterface;
17
18			public function testInsert(): void
19			{
20			$heap = $this->createHeap();
21
22			for ($i = 0; $i < self::SIZE; $i += 1) {
23			$heap->insert($i);
24			$this->assertEquals(0, $heap->findMin()->getKey());
25			$this->assertFalse($heap->isEmpty());
26			$this->assertEquals($heap->size(), $i + 1);
27			}
28
29			for ($i = self::SIZE - 1; $i >= 0; $i -= 1) {
30			$this->assertEquals($heap->findMin()->getKey(), self::SIZE - $i - 1);
31			$heap->deleteMin();
32			}
33			}
34
35			public function testSetValue(): void
36			{
37			$heap = $this->createHeap();
38			$heap->insert(1, "value1")->setValue("value2");
39			$this->assertEquals("value2", $heap->findMin()->getValue());
40			}
41
42			public function testEmptyAfterDeleteAll(): void
43			{
44			$heap = $this->createHeap();
45			$heap->insert(780);
46			$this->assertEquals($heap->size(), 1);
47			$this->assertEquals(780, $heap->findMin()->getKey());
48
49			$heap->insert(-389);
50			$this->assertEquals($heap->size(), 2);
51			$this->assertEquals(-389, $heap->findMin()->getKey());
52
53			$heap->insert(306);
54			$this->assertEquals($heap->size(), 3);
55			$this->assertEquals(-389, $heap->findMin()->getKey());
56
57			$heap->insert(579);
58			$this->assertEquals($heap->size(), 4);
59			$this->assertEquals(-389, $heap->findMin()->getKey());
60
61			$heap->deleteMin();
62			$this->assertEquals($heap->size(), 3);
63			$this->assertEquals(306, $heap->findMin()->getKey());
64
65			$heap->deleteMin();
66			$this->assertEquals($heap->size(), 2);
67			$this->assertEquals(579, $heap->findMin()->getKey());
68
69			$heap->deleteMin();
70			$this->assertEquals($heap->size(), 1);
71			$this->assertEquals(780, $heap->findMin()->getKey());
72
73			$heap->deleteMin();
74			$this->assertEquals($heap->size(), 0);
75
76			$this->assertTrue($heap->isEmpty());
77			}
78
79			public function testRandomDelete(): void
80			{
81			$heap = $this->createHeap();
82
83			for ($i = 0; $i < self::SIZE; $i += 1) {
84			$heap->insert(random_int(0, 100000));
85			}
86
87			$prev = null;
88			$i = 0;
89			while (!$heap->isEmpty()) {
90			$cur = $heap->findMin()->getKey();
91			$heap->deleteMin();
92			if (!is_null($prev)) {
93			$this->assertTrue($prev <= $cur);
94			}
95			$prev = $cur;
96			$i += 1;
97			}
98			}
99
100			public function testFindDeleteSame(): void
101			{
102			$heap = $this->createHeap();
103
104			for ($i = 0; $i < self::SIZE; $i += 1) {
105			$heap->insert(random_int(0, 100000));
106			}
107
108			while (!$heap->isEmpty()) {
109			$this->assertEquals($heap->findMin(), $heap->deleteMin());
110			}
111			}
112
113			public function testDeleteNodes(): void
114			{
115			$heap = $this->createHeap();
116
117			$nodes = [];
118			for ($i = 0; $i < 15; $i += 1) {
119			$nodes[$i] = $heap->insert($i);
120			}
121
122			$nodes[5]->delete();
123			$this->assertEquals(0, $heap->findMin()->getKey());
124			$nodes[7]->delete();
125			$this->assertEquals(0, $heap->findMin()->getKey());
126			$nodes[0]->delete();
127			$this->assertEquals(1, $heap->findMin()->getKey());
128			$nodes[2]->delete();
129			$this->assertEquals(1, $heap->findMin()->getKey());
130			$nodes[1]->delete();
131			$this->assertEquals(3, $heap->findMin()->getKey());
132			$nodes[3]->delete();
133			$this->assertEquals(4, $heap->findMin()->getKey());
134			$nodes[9]->delete();
135			$this->assertEquals(4, $heap->findMin()->getKey());
136			$nodes[4]->delete();
137			$this->assertEquals(6, $heap->findMin()->getKey());
138			$nodes[8]->delete();
139			$this->assertEquals(6, $heap->findMin()->getKey());
140			$nodes[11]->delete();
141			$this->assertEquals(6, $heap->findMin()->getKey());
142			$nodes[6]->delete();
143			$this->assertEquals(10, $heap->findMin()->getKey());
144			$nodes[12]->delete();
145			$this->assertEquals(10, $heap->findMin()->getKey());
146			$nodes[10]->delete();
147			$this->assertEquals(13, $heap->findMin()->getKey());
148			$nodes[13]->delete();
149			$this->assertEquals(14, $heap->findMin()->getKey());
150			$nodes[14]->delete();
151			$this->assertTrue($heap->isEmpty());
152			}
153
154			public function testNodesRandomDelete(): void
155			{
156			$heap = $this->createHeap();
157
158			$nodes = [];
159			for ($i = 0; $i < 8; $i += 1) {
160			$nodes[$i] = $heap->insert($i);
161			}
162
163			$nodes[5]->delete();
164			$this->assertEquals(0, $heap->findMin()->getKey());
165			$nodes[7]->delete();
166			$this->assertEquals(0, $heap->findMin()->getKey());
167			$nodes[0]->delete();
168			$this->assertEquals(1, $heap->findMin()->getKey());
169			$nodes[2]->delete();
170			$this->assertEquals(1, $heap->findMin()->getKey());
171			$nodes[1]->delete();
172			$this->assertEquals(3, $heap->findMin()->getKey());
173			}
174
175			public function testAddDelete(): void
176			{
177			$heap = $this->createHeap();
178
179			$nodes = [];
180			for ($i = 0; $i < self::SIZE; $i += 1) {
181			$nodes[$i] = $heap->insert($i);
182			}
183
184			for ($i = self::SIZE - 1; $i >= 0; $i -= 1) {
185			$nodes[$i]->delete();
186			if ($i > 0) {
187			$this->assertEquals(0, $heap->findMin()->getKey());
188			}
189			}
190			$this->assertTrue($heap->isEmpty());
191			}
192
193			public function testDeleteTwice(): void
194			{
195			$heap = $this->createHeap();
196
197			$nodes = [];
198			for ($i = 0; $i < 15; $i += 1) {
199			$nodes[$i] = $heap->insert($i);
200			}
201
202			$nodes[5]->delete();
203			$this->assertEquals(0, $heap->findMin()->getKey());
204			$nodes[7]->delete();
205			$this->assertEquals(0, $heap->findMin()->getKey());
206			$nodes[0]->delete();
207			$this->assertEquals(1, $heap->findMin()->getKey());
208			$nodes[2]->delete();
209			$this->assertEquals(1, $heap->findMin()->getKey());
210			$nodes[1]->delete();
211			$this->assertEquals(3, $heap->findMin()->getKey());
212			$nodes[3]->delete();
213			$this->assertEquals(4, $heap->findMin()->getKey());
214			$nodes[9]->delete();
215			$this->assertEquals(4, $heap->findMin()->getKey());
216			$nodes[4]->delete();
217			$this->assertEquals(6, $heap->findMin()->getKey());
218
219			// again
220			$this->expectException(InvalidArgumentException::class);
221			$nodes[2]->delete();
222			}
223
224			public function testDeleteMindeleteTwice(): void
225			{
226			$heap = $this->createHeap();
227			$e1 = $heap->insert(50);
228			$heap->insert(100);
229			$heap->deleteMin();
230			$this->expectException(InvalidArgumentException::class);
231			$e1->delete();
232			}
233
234			public function testDeleteMinDeleteTwiceChained(): void
235			{
236			$heap = $this->createHeap();
237			for ($i = 0; $i < 15; $i += 1) {
238			$heap->insert($i);
239			}
240			$this->expectException(InvalidArgumentException::class);
241			$heap->deleteMin()->delete();
242			}
243
244			public function testDeleteMinDecreaseKey(): void
245			{
246			$heap = $this->createHeap();
247			for ($i = 100; $i < 200; $i += 1) {
248			$heap->insert($i);
249			}
250			$this->expectException(InvalidArgumentException::class);
251			$heap->deleteMin()->decreaseKey(0);
252			}
253
254			public function testNoElementFindMin(): void
255			{
256			$heap = $this->createHeap();
257			$this->expectException(NoSuchElementException::class);
258			$heap->findMin();
259			}
260
261			public function testDeleteMinFindMin(): void
262			{
263			$heap = $this->createHeap();
264			$this->expectException(NoSuchElementException::class);
265			$heap->deleteMin();
266			}
267
268			/*public function testNullPointerException(): void
269			{
270			$heap = $this->createHeap();
271			$this->expectException(TypeError::class);
272			$heap->insert(null, null);
273			}*/
274
275			public function testDecreaseKey(): void
276			{
277			$heap = $this->createHeap();
278			$nodes = [];
279			for ($i = 0; $i < 15; $i += 1) {
280			$nodes[$i] = $heap->insert($i + 100);
281			}
282			$this->assertEquals(100, $heap->findMin()->getKey());
283			$nodes[5]->decreaseKey(5);
284			$this->assertEquals(5, $heap->findMin()->getKey());
285			$nodes[1]->decreaseKey(50);
286			$this->assertEquals(5, $heap->findMin()->getKey());
287			$nodes[1]->decreaseKey(20);
288			$this->assertEquals(5, $heap->findMin()->getKey());
289			$nodes[5]->delete();
290			$this->assertEquals(20, $heap->findMin()->getKey());
291			$nodes[10]->decreaseKey(3);
292			$this->assertEquals(3, $heap->findMin()->getKey());
293			$nodes[0]->decreaseKey(0);
294			$this->assertEquals(0, $heap->findMin()->getKey());
295			}
296
297			public function testDecreaseKeyAndDelete(): void
298			{
299			$heap = $this->createHeap();
300			$nodes = [];
301			for ($i = 0; $i < 1000; $i += 1) {
302			$nodes[$i] = $heap->insert($i + 2000);
303			}
304			for ($i = 999; $i >= 0; $i -= 1) {
305			$nodes[$i]->decreaseKey($nodes[$i]->getKey() - 2000);
306			}
307			for ($i = 0; $i < 1000; $i += 1) {
308			$this->assertEquals($i, $heap->deleteMin()->getKey());
309			}
310			}
311
312			public function testIncreaseKeyException(): void
313			{
314			$heap = $this->createHeap();
315			$nodes = [];
316			for ($i = 0; $i < 15; $i += 1) {
317			$nodes[$i] = $heap->insert($i + 100);
318			}
319			$this->assertEquals(100, $heap->findMin()->getKey());
320			$nodes[5]->decreaseKey(5);
321			$this->assertEquals(5, $heap->findMin()->getKey());
322			$this->expectException(InvalidArgumentException::class);
323			$nodes[1]->decreaseKey(102);
324			}
325			}
326

bingo-soft / heap

AbstractAddressableHeapTest::testDeleteNodes() A last analyzed 2019-11-25 07:56 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

AbstractAddressableHeapTest::testDeleteNodes() A
last analyzed 2019-11-25 07:56 UTC