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

AbstractMergeableAddressableHeapTest::testMeld2() A
last analyzed 2019-11-25 07:56 UTC

↳ Parent: AbstractMergeableAddressableHeapTest

Complexity

Conditions	1
Paths	1

Size

Total Lines	35
Code Lines	27

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	1

Metric	Value
cc	1
eloc	27
c	1
b	0
f	1
nc	1
nop	0
dl	0
loc	35
rs	9.488

<?php

namespace tests;

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

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

    abstract protected function createHeap(): MergeableAddressableHeapInterface;

    public function testMeld1(): void
    {
        $a = $this->createHeap();
        $a->insert(10);
        $a->insert(11);
        $a->insert(12);
        $a->insert(13);

        $b = $this->createHeap();
        $b->insert(14);
        $b->insert(15);
        $b->insert(16);
        $b4 = $b->insert(17);

        $a->meld($b);

        $this->assertEquals(8, $a->size());
        $this->assertTrue($b->isEmpty());
        $this->assertEquals(0, $b->size());

        $b4->decreaseKey(9);
        $this->assertEquals(9, $a->findMin()->getKey());
    }

    public function testMeld2(): void
    {
        $a = $this->createHeap();
        $a->insert(10);
        $a->insert(11);
        $a->insert(12);
        $a->insert(13);

        $b = $this->createHeap();
        $b->insert(14);
        $b->insert(15);
        $b->insert(16);
        $b4 = $b->insert(17);

        $c = $this->createHeap();
        $c->insert(18);
        $c->insert(19);
        $c->insert(20);
        $c4 = $c->insert(21);

        $a->meld($b);
        $a->meld($c);

        $this->assertEquals(12, $a->size());
        $this->assertTrue($b->isEmpty());
        $this->assertEquals(0, $b->size());

        $this->assertTrue($c->isEmpty());
        $this->assertEquals(0, $c->size());

        $this->assertEquals(10, $a->findMin()->getKey());
        $b4->decreaseKey(9);
        $this->assertEquals(9, $a->findMin()->getKey());
        $c4->decreaseKey(8);
        $this->assertEquals(8, $a->findMin()->getKey());
    }

    public function testMultipleMelds(): void
    {
        $a = $this->createHeap();
        $a->insert(10);
        $a->insert(11);
        $a->insert(12);
        $a->insert(13);

        $b = $this->createHeap();
        $b->insert(14);
        $b->insert(15);
        $b->insert(16);
        $b->insert(17);

        $c = $this->createHeap();
        $c->insert(18);
        $c->insert(19);
        $c->insert(20);
        $c->insert(21);

        $a->meld($b);
        // Invalid: A heap cannot be used after a meld.
        $this->expectException(Exception::class);
        $a->meld($b);
    }

    public function testInsertAfterAMeld(): void
    {
        $a = $this->createHeap();
        $a->insert(10);
        $a->insert(11);
        $a->insert(12);
        $a->insert(13);

        $b = $this->createHeap();
        $b->insert(14);
        $b->insert(15);
        $b->insert(16);
        $b->insert(17);

        $a->meld($b);
        // Invalid: A heap cannot be used after a meld.
        $this->expectException(Exception::class);
        $b->insert(30);
    }

    public function testMeldGeneric(): void
    {
        $h1 = $this->createHeap();

        for ($i = 0; $i < self::SIZE; $i += 1) {
            $h1->insert(2 * $i);
        }

        $h2 = $this->createHeap();
        for ($i = 0; $i < self::SIZE; $i += 1) {
            $h2->insert(2 * $i + 1);
        }

        $h1->meld($h2);

        $this->assertEquals($h1->size(), self::SIZE * 2);
        $this->assertEquals($h2->size(), 0);

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

    public function testMeldGeneric1(): void
    {
        $h1 = $this->createHeap();

        $h2 = $this->createHeap();
        for ($i = 0; $i < self::SIZE; $i += 1) {
            $h2->insert($i);
        }

        $h1->meld($h2);

        $this->assertEquals($h1->size(), self::SIZE);
        $this->assertEquals($h2->size(), 0);

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

    public function testMeldGeneric2(): void
    {
        $h1 = $this->createHeap();

        $h2 = $this->createHeap();
        for ($i = 0; $i < self::SIZE; $i += 1) {
            $h1->insert($i);
        }

        $h1->meld($h2);

        $this->assertEquals($h1->size(), self::SIZE);
        $this->assertEquals($h2->size(), 0);

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

    public function testMeld(): void
    {
        $h1 = $this->createHeap();
        $h2 = $this->createHeap();

        for ($i = 0; $i < self::SIZE; $i += 1) {
            if ($i % 2 == 0) {
                $h1->insert($i);
            } else {
                $h2->insert($i);
            }
        }

        $h1->meld($h2);

        $this->assertTrue($h2->isEmpty());
        $this->assertEquals(0, $h2->size());

        for ($i = 0; $i < self::SIZE; $i += 1) {
            $this->assertEquals($i, $h1->findMin()->getKey());
            $h1->deleteMin();
        }
        $this->assertTrue($h1->isEmpty());
    }
}


1			<?php
2
3			namespace tests;
4
5			use PHPUnit\Framework\TestCase;
6			use Exception;
7			use InvalidArgumentException;
8			use TypeError;
9			use Heap\MergeableAddressableHeapInterface;
10			use Heap\Exception\NoSuchElementException;
11
12			abstract class AbstractMergeableAddressableHeapTest extends TestCase
13			{
14			protected const SIZE = 100;
15
16			abstract protected function createHeap(): MergeableAddressableHeapInterface;
17
18			public function testMeld1(): void
19			{
20			$a = $this->createHeap();
21			$a->insert(10);
22			$a->insert(11);
23			$a->insert(12);
24			$a->insert(13);
25
26			$b = $this->createHeap();
27			$b->insert(14);
28			$b->insert(15);
29			$b->insert(16);
30			$b4 = $b->insert(17);
31
32			$a->meld($b);
33
34			$this->assertEquals(8, $a->size());
35			$this->assertTrue($b->isEmpty());
36			$this->assertEquals(0, $b->size());
37
38			$b4->decreaseKey(9);
39			$this->assertEquals(9, $a->findMin()->getKey());
40			}
41
42			public function testMeld2(): void
43			{
44			$a = $this->createHeap();
45			$a->insert(10);
46			$a->insert(11);
47			$a->insert(12);
48			$a->insert(13);
49
50			$b = $this->createHeap();
51			$b->insert(14);
52			$b->insert(15);
53			$b->insert(16);
54			$b4 = $b->insert(17);
55
56			$c = $this->createHeap();
57			$c->insert(18);
58			$c->insert(19);
59			$c->insert(20);
60			$c4 = $c->insert(21);
61
62			$a->meld($b);
63			$a->meld($c);
64
65			$this->assertEquals(12, $a->size());
66			$this->assertTrue($b->isEmpty());
67			$this->assertEquals(0, $b->size());
68
69			$this->assertTrue($c->isEmpty());
70			$this->assertEquals(0, $c->size());
71
72			$this->assertEquals(10, $a->findMin()->getKey());
73			$b4->decreaseKey(9);
74			$this->assertEquals(9, $a->findMin()->getKey());
75			$c4->decreaseKey(8);
76			$this->assertEquals(8, $a->findMin()->getKey());
77			}
78
79			public function testMultipleMelds(): void
80			{
81			$a = $this->createHeap();
82			$a->insert(10);
83			$a->insert(11);
84			$a->insert(12);
85			$a->insert(13);
86
87			$b = $this->createHeap();
88			$b->insert(14);
89			$b->insert(15);
90			$b->insert(16);
91			$b->insert(17);
92
93			$c = $this->createHeap();
94			$c->insert(18);
95			$c->insert(19);
96			$c->insert(20);
97			$c->insert(21);
98
99			$a->meld($b);
100			// Invalid: A heap cannot be used after a meld.
101			$this->expectException(Exception::class);
102			$a->meld($b);
103			}
104
105			public function testInsertAfterAMeld(): void
106			{
107			$a = $this->createHeap();
108			$a->insert(10);
109			$a->insert(11);
110			$a->insert(12);
111			$a->insert(13);
112
113			$b = $this->createHeap();
114			$b->insert(14);
115			$b->insert(15);
116			$b->insert(16);
117			$b->insert(17);
118
119			$a->meld($b);
120			// Invalid: A heap cannot be used after a meld.
121			$this->expectException(Exception::class);
122			$b->insert(30);
123			}
124
125			public function testMeldGeneric(): void
126			{
127			$h1 = $this->createHeap();
128
129			for ($i = 0; $i < self::SIZE; $i += 1) {
130			$h1->insert(2 * $i);
131			}
132
133			$h2 = $this->createHeap();
134			for ($i = 0; $i < self::SIZE; $i += 1) {
135			$h2->insert(2 * $i + 1);
136			}
137
138			$h1->meld($h2);
139
140			$this->assertEquals($h1->size(), self::SIZE * 2);
141			$this->assertEquals($h2->size(), 0);
142
143			$prev = null;
144			while (!$h1->isEmpty()) {
145			$cur = $h1->findMin()->getKey();
146			$h1->deleteMin();
147			if (!is_null($prev)) {
148			$this->assertTrue($prev <= $cur);
149			}
150			$prev = $cur;
151			}
152			}
153
154			public function testMeldGeneric1(): void
155			{
156			$h1 = $this->createHeap();
157
158			$h2 = $this->createHeap();
159			for ($i = 0; $i < self::SIZE; $i += 1) {
160			$h2->insert($i);
161			}
162
163			$h1->meld($h2);
164
165			$this->assertEquals($h1->size(), self::SIZE);
166			$this->assertEquals($h2->size(), 0);
167
168			$prev = null;
169			while (!$h1->isEmpty()) {
170			$cur = $h1->findMin()->getKey();
171			$h1->deleteMin();
172			if (!is_null($prev)) {
173			$this->assertTrue($prev <= $cur);
174			}
175			$prev = $cur;
176			}
177			}
178
179			public function testMeldGeneric2(): void
180			{
181			$h1 = $this->createHeap();
182
183			$h2 = $this->createHeap();
184			for ($i = 0; $i < self::SIZE; $i += 1) {
185			$h1->insert($i);
186			}
187
188			$h1->meld($h2);
189
190			$this->assertEquals($h1->size(), self::SIZE);
191			$this->assertEquals($h2->size(), 0);
192
193			$prev = null;
194			while (!$h1->isEmpty()) {
195			$cur = $h1->findMin()->getKey();
196			$h1->deleteMin();
197			if (!is_null($prev)) {
198			$this->assertTrue($prev <= $cur);
199			}
200			$prev = $cur;
201			}
202			}
203
204			public function testMeld(): void
205			{
206			$h1 = $this->createHeap();
207			$h2 = $this->createHeap();
208
209			for ($i = 0; $i < self::SIZE; $i += 1) {
210			if ($i % 2 == 0) {
211			$h1->insert($i);
212			} else {
213			$h2->insert($i);
214			}
215			}
216
217			$h1->meld($h2);
218
219			$this->assertTrue($h2->isEmpty());
220			$this->assertEquals(0, $h2->size());
221
222			for ($i = 0; $i < self::SIZE; $i += 1) {
223			$this->assertEquals($i, $h1->findMin()->getKey());
224			$h1->deleteMin();
225			}
226			$this->assertTrue($h1->isEmpty());
227			}
228			}
229

bingo-soft / heap

AbstractMergeableAddressableHeapTest::testMeld2() A last analyzed 2019-11-25 07:56 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

AbstractMergeableAddressableHeapTest::testMeld2() A
last analyzed 2019-11-25 07:56 UTC