FibonacciHeapTest::testDeleteNodes() - Code Metrics - Inspection of "test: add fibonacci heap tests" - bingo-soft/heap - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Branch — master (7d902f)

by Bingo

created 2019-11-16 17:52 UTC

FibonacciHeapTest::testDeleteNodes() A

↳ Parent: FibonacciHeapTest

Complexity

Conditions	2
Paths	2

Size

Total Lines	39
Code Lines	34

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	1

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

<?php

namespace tests;

use PHPUnit\Framework\TestCase;
use heap\FibonacciHeap;
use heap\FibonacciHeapNode;

class FibonacciHeapTest extends TestCase
{
    private const SIZE = 100;

    public function testInsert(): void
    {
        $heap = new FibonacciHeap();
       
        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 = new FibonacciHeap();
        $heap->insert(1, "value1")->setValue("value2");
        $this->assertEquals("value2", $heap->findMin()->getValue());
    }

    public function testEmptyAfterDeleteAll(): void
    {
        $heap = new FibonacciHeap();
        $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 = new FibonacciHeap();

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

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

    public function testFindDeleteSame(): void
    {
        $heap = new FibonacciHeap();

        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 = new FibonacciHeap();

        $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 = new FibonacciHeap();

        $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 = new FibonacciHeap();

        $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());
    }
}


1			<?php
2
3			namespace tests;
4
5			use PHPUnit\Framework\TestCase;
6			use heap\FibonacciHeap;
7			use heap\FibonacciHeapNode;
8
9			class FibonacciHeapTest extends TestCase
10			{
11			private const SIZE = 100;
12
13			public function testInsert(): void
14			{
15			$heap = new FibonacciHeap();
16
17			for ($i = 0; $i < self::SIZE; $i += 1) {
18			$heap->insert($i);
19			$this->assertEquals(0, $heap->findMin()->getKey());
20			$this->assertFalse($heap->isEmpty());
21			$this->assertEquals($heap->size(), $i + 1);
22			}
23
24			for ($i = self::SIZE - 1; $i >= 0; $i -= 1) {
25			$this->assertEquals($heap->findMin()->getKey(), self::SIZE - $i - 1);
26			$heap->deleteMin();
27			}
28			}
29
30			public function testSetValue(): void
31			{
32			$heap = new FibonacciHeap();
33			$heap->insert(1, "value1")->setValue("value2");
34			$this->assertEquals("value2", $heap->findMin()->getValue());
35			}
36
37			public function testEmptyAfterDeleteAll(): void
38			{
39			$heap = new FibonacciHeap();
40			$heap->insert(780);
41			$this->assertEquals($heap->size(), 1);
42			$this->assertEquals(780, $heap->findMin()->getKey());
43
44			$heap->insert(-389);
45			$this->assertEquals($heap->size(), 2);
46			$this->assertEquals(-389, $heap->findMin()->getKey());
47
48			$heap->insert(306);
49			$this->assertEquals($heap->size(), 3);
50			$this->assertEquals(-389, $heap->findMin()->getKey());
51
52			$heap->insert(579);
53			$this->assertEquals($heap->size(), 4);
54			$this->assertEquals(-389, $heap->findMin()->getKey());
55
56			$heap->deleteMin();
57			$this->assertEquals($heap->size(), 3);
58			$this->assertEquals(306, $heap->findMin()->getKey());
59
60			$heap->deleteMin();
61			$this->assertEquals($heap->size(), 2);
62			$this->assertEquals(579, $heap->findMin()->getKey());
63
64			$heap->deleteMin();
65			$this->assertEquals($heap->size(), 1);
66			$this->assertEquals(780, $heap->findMin()->getKey());
67
68			$heap->deleteMin();
69			$this->assertEquals($heap->size(), 0);
70
71			$this->assertTrue($heap->isEmpty());
72			}
73
74			public function testRandomDelete(): void
75			{
76			$heap = new FibonacciHeap();
77
78			for ($i = 0; $i < self::SIZE; $i += 1) {
79			$heap->insert(random_int(0, 100000));
80			}
81
82			$prev = null;
83			while (!$heap->isEmpty()) {
84			$cur = $heap->findMin()->getKey();
85			$heap->deleteMin();
86			if (!is_null($prev)) {
87			$this->assertTrue($prev <= $cur);
88			}
89			$prev = $cur;
90			}
91			}
92
93			public function testFindDeleteSame(): void
94			{
95			$heap = new FibonacciHeap();
96
97			for ($i = 0; $i < self::SIZE; $i += 1) {
98			$heap->insert(random_int(0, 100000));
99			}
100
101			while (!$heap->isEmpty()) {
102			$this->assertEquals($heap->findMin(), $heap->deleteMin());
103			}
104			}
105
106			public function testDeleteNodes(): void
107			{
108			$heap = new FibonacciHeap();
109
110			$nodes = [];
111			for ($i = 0; $i < 15; $i += 1) {
112			$nodes[$i] = $heap->insert($i);
113			}
114
115			$nodes[5]->delete();
116			$this->assertEquals(0, $heap->findMin()->getKey());
117			$nodes[7]->delete();
118			$this->assertEquals(0, $heap->findMin()->getKey());
119			$nodes[0]->delete();
120			$this->assertEquals(1, $heap->findMin()->getKey());
121			$nodes[2]->delete();
122			$this->assertEquals(1, $heap->findMin()->getKey());
123			$nodes[1]->delete();
124			$this->assertEquals(3, $heap->findMin()->getKey());
125			$nodes[3]->delete();
126			$this->assertEquals(4, $heap->findMin()->getKey());
127			$nodes[9]->delete();
128			$this->assertEquals(4, $heap->findMin()->getKey());
129			$nodes[4]->delete();
130			$this->assertEquals(6, $heap->findMin()->getKey());
131			$nodes[8]->delete();
132			$this->assertEquals(6, $heap->findMin()->getKey());
133			$nodes[11]->delete();
134			$this->assertEquals(6, $heap->findMin()->getKey());
135			$nodes[6]->delete();
136			$this->assertEquals(10, $heap->findMin()->getKey());
137			$nodes[12]->delete();
138			$this->assertEquals(10, $heap->findMin()->getKey());
139			$nodes[10]->delete();
140			$this->assertEquals(13, $heap->findMin()->getKey());
141			$nodes[13]->delete();
142			$this->assertEquals(14, $heap->findMin()->getKey());
143			$nodes[14]->delete();
144			$this->assertTrue($heap->isEmpty());
145			}
146
147			public function testNodesRandomDelete(): void
148			{
149			$heap = new FibonacciHeap();
150
151			$nodes = [];
152			for ($i = 0; $i < 8; $i += 1) {
153			$nodes[$i] = $heap->insert($i);
154			}
155
156			$nodes[5]->delete();
157			$this->assertEquals(0, $heap->findMin()->getKey());
158			$nodes[7]->delete();
159			$this->assertEquals(0, $heap->findMin()->getKey());
160			$nodes[0]->delete();
161			$this->assertEquals(1, $heap->findMin()->getKey());
162			$nodes[2]->delete();
163			$this->assertEquals(1, $heap->findMin()->getKey());
164			$nodes[1]->delete();
165			$this->assertEquals(3, $heap->findMin()->getKey());
166			}
167
168			public function testAddDelete(): void
169			{
170			$heap = new FibonacciHeap();
171
172			$nodes = [];
173			for ($i = 0; $i < self::SIZE; $i += 1) {
174			$nodes[$i] = $heap->insert($i);
175			}
176
177			for ($i = self::SIZE - 1; $i >= 0; $i -= 1) {
178			$nodes[$i]->delete();
179			if ($i > 0) {
180			$this->assertEquals(0, $heap->findMin()->getKey());
181			}
182			}
183			$this->assertTrue($heap->isEmpty());
184			}
185			}
186

bingo-soft / heap

Branch — master (7d902f)

FibonacciHeapTest::testDeleteNodes() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like