PairingHeap::link() - Code Metrics - Inspection of "refactor: refactor namespacing" - bingo-soft/heap - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( f37b88...0dd5a5 )

by Bingo

created 2019-11-24 08:08 UTC

PairingHeap::link() A

↳ Parent: PairingHeap

Complexity

Conditions	5
Paths	5

Size

Total Lines	16
Code Lines	12

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	13
CRAP Score	5

Importance

Changes

Metric	Value
cc	5
eloc	12
nc	5
nop	2
dl	0
loc	16
ccs	13
cts	13
cp	1
crap	5
rs	9.5555
c	0
b	0
f	0

<?php

namespace BingoSoft\Heap\Tree;

use Exception;
use InvalidArgumentException;
use BingoSoft\Heap\exception\NoSuchElementException;
use BingoSoft\Heap\MergeableAddressableHeapInterface;
use BingoSoft\Heap\AddressableHeapHandleInterface;

/**
 * Class PairingHeap
 *
 * @package BingoSoft\Heap\Tree
 */
class PairingHeap implements MergeableAddressableHeapInterface
{
    /**
     * The heap unique hash
     *
     * @var string
     */
    private $hash;

    /**
     * The heap root node
     *
     * @var PairingHeapNode
     */
    private $root = null;

    /**
     * Size of the heap
     *
     * @var int
     */
    private $size = 0;

    /**
     * Reference to current or some other heap in case of melding
     *
     * @var PairingHeap
     */
    private $other;

    /**
     * Construct a new Pairing heap
     */
    public function __construct()
    {
        $this->root = null;
        $this->size = 0;
        $this->other = $this;
        $this->hash = uniqid('', true);
    }

    /**
     * Insert a new node to the heap
     *
     * @param int $key - node key
     * @param null|mixed $value - node value
     *
     * @return AddressableHeapHandleInterface
     *
     * @throws Exception
     */
    public function insert(int $key, $value = null): AddressableHeapHandleInterface
    {
        if ($this->other != $this) {
            throw new Exception("A heap cannot be used after a meld");
        }

        $node = new PairingHeapNode($this, $key, $value);
        $this->root = $this->link($this->root, $node);
        $this->size += 1;
        return $node;
    }

    /**
     * Find heap node with the minimal key
     *
     * @return AddressableHeapHandleInterface
     *
     * @throws NoSuchElementException
     */
    public function findMin(): AddressableHeapHandleInterface
    {
        if ($this->size == 0) {
            throw new NoSuchElementException("No such element!");
        }
        return $this->root;
    }

    /*
     * Delete a node
     *
     * @param PairingHeapNode $node - the node to delete
     */
    public function delete(PairingHeapNode $node): void
    {
        if ($this->root == $node) {
            $this->deleteMin();
            $node->o_c = null;
            $node->y_s = null;
            $node->o_s = null;
            return;
        }

        if (is_null($node->o_s)) {
            throw new InvalidArgumentException("Invalid handle!");
        }

        // unlink from parent
        if (!is_null($node->y_s)) {
            $node->y_s->o_s = $node->o_s;
        }
        if ($node->o_s->o_c == $node) {
            $node->o_s->o_c = $node->y_s;
        } else {
            $node->o_s->y_s = $node->y_s;
        }
        $node->y_s = null;
        $node->o_s = null;

        // perform delete-min at tree rooted at this
        $t = $this->combine($this->cutChildren($node));

        // and merge with other cut tree
        $this->root = $this->link($this->root, $t);

        $this->size -= 1;
    }

    /**
     * Delete an element with the minimal key.
     *
     * @return AddressableHeapHandleInterface
     *
     * @throws NoSuchElementException
     */
    public function deleteMin(): AddressableHeapHandleInterface
    {
        if ($this->size == 0) {
            throw new NoSuchElementException("No such element!");
        }
        $oldRoot = $this->root;

        $this->root = $this->combine($this->cutChildren($this->root));

        $this->size -= 1;

        return $oldRoot;
    }

    /**
     * Check if the heap is empty.
     *
     * @return bool
     */
    public function isEmpty(): bool
    {
        return $this->size == 0;
    }

    /**
     * Get the number of elements in the heap.
     *
     * @return int
     */
    public function size(): int
    {
        return $this->size;
    }

    /**
     * Get the other heap referenced in the current heap
     *
     * @return MergeableAddressableHeapInterface
     */
    public function getOther(): MergeableAddressableHeapInterface
    {
        return $this->other;
    }

    /**
     * Reference the other heap in the current heap
     *
     * @param MergeableAddressableHeapInterface $other - the other heap
     */
    public function setOther(MergeableAddressableHeapInterface $other): void
    {
        if (!($other instanceof PairingHeap)) {
            throw new InvalidArgumentException("The heap must be of type Pairing.");
        }
        $this->other = $other;
    }

    /**
     * Clear all the elements in the heap
     */
    public function clear(): void
    {
        $this->root = null;
        $this->size = 0;
        $this->other = $this;
    }

    /**
     * Meld other heap to the current heap
     *
     * @param MergeableAddressableHeapInterface $other - the heap to be melded
     *
     * @throws Exception
     */
    public function meld(MergeableAddressableHeapInterface $other): void
    {
        if (!($other instanceof PairingHeap)) {
            throw new InvalidArgumentException("The heap to be melded must be of type Pairing.");
        }

        if ($other->other != $other) {
            throw new Exception("A heap cannot be used after a meld.");
        }

        $this->size += $other->size;
        $this->root = $this->link($this->root, $other->root);

        // clear other
        $other->size = 0;
        $other->root = null;

        // take ownership
        $other->other = $this;
    }

    /**
     * Decrease the node key
     *
     * @param PairingHeapNode $node - the node
     * @param int $newKey - the node new key
     *
     * @throws Exception
     */
    public function decreaseKey(PairingHeapNode $node, int $newKey): void
    {
        if ($newKey > $node->key) {
            throw new InvalidArgumentException("Keys can only be decreased!");
        } elseif ($node->key != $newKey) {
            if (is_null($node->o_s)) {
                throw new InvalidArgumentException("Invalid handle!");
            }
            $node->key = $newKey;
            // unlink from parent
            if (!is_null($node->y_s)) {
                $node->y_s->o_s = $node->o_s;
            }
            if ($node->o_s->o_c == $node) {
                $node->o_s->o_c = $node->y_s;
            } else {
                $node->o_s->y_s = $node->y_s;
            }
            $node->y_s = null;
            $node->o_s = null;

            // merge with root
            $this->root = $this->link($this->root, $node);
        }
    }

    /*
     * Link two nodes
     *
     * @param PairingHeapNode $first - first node
     * @param PairingHeapNode $second - second node
     *
     * @return null|PairingHeapNode
     */
    private function link(?PairingHeapNode $first = null, ?PairingHeapNode $second = null): ?PairingHeapNode
    {
        if (is_null($second)) {
            return $first;
        } elseif (is_null($first)) {
            return $second;
        } elseif ($first->key < $second->key) {
            $second->y_s = $first->o_c;
            $second->o_s = $first;
            if ($first->o_c != null) {
                $first->o_c->o_s = $second;
            }
            $first->o_c = $second;
            return $first;
        }
        return $this->link($second, $first);
    }

    /**
     * Cut the children of a node and return the list.
     *
     * @param PairingHeapNode $node - the root node
     *
     * @return PairingHeapNode
     */
    private function cutChildren(PairingHeapNode $node): ?PairingHeapNode
    {
        $child = $node->o_c;
        $node->o_c = null;
        if (!is_null($child)) {
            $child->o_s = null;
        }
        return $child;
    }

    /*
     * Two pass pair and compute root.
     *
     * @param PairingHeapNode $node - the node
     *
     * @return null|PairingHeapNode
     */
    private function combine(?PairingHeapNode $node = null): ?PairingHeapNode
    {
        if (is_null($node)) {
            return null;
        }
        if (!is_null($node->o_s)) {
            throw new InvalidArgumentException("Invalid handle!");
        }
        
        // left-right pass
        $pairs = null;
        $it = $node;
        while (!is_null($it)) {
            $p_it = $it;
            $it = $it->y_s;

            if (is_null($it)) {
                // append last node to pair list
                $p_it->y_s = $pairs;
                $p_it->o_s = null;
                $pairs = $p_it;
            } else {
                $n_it = $it->y_s;

                // disconnect both
                $p_it->y_s = null;
                $p_it->o_s = null;
                $it->y_s = null;
                $it->o_s = null;

                // link trees
                $p_it = $this->link($p_it, $it);

                // append to pair list
                $p_it->y_s = $pairs;
                $pairs = $p_it;

                // advance
                $it = $n_it;
            }
        }

        // second pass (reverse order - due to add first)
        $it = $pairs;
        $f = null;
        while (!is_null($it)) {
            $nextIt = $it->y_s;
            $it->y_s = null;
            $f = $this->link($f, $it);
            $it = $nextIt;
        }

        return $f;
    }
}


1		<?php
2
3		namespace BingoSoft\Heap\Tree;
4
5		use Exception;
6		use InvalidArgumentException;
7		use BingoSoft\Heap\exception\NoSuchElementException;
8		use BingoSoft\Heap\MergeableAddressableHeapInterface;
9		use BingoSoft\Heap\AddressableHeapHandleInterface;
10
11		/**
12		* Class PairingHeap
13		*
14		* @package BingoSoft\Heap\Tree
15		*/
16		class PairingHeap implements MergeableAddressableHeapInterface
17		{
18		/**
19		* The heap unique hash
20		*
21		* @var string
22		*/
23		private $hash;
24
25		/**
26		* The heap root node
27		*
28		* @var PairingHeapNode
29		*/
30		private $root = null;
31
32		/**
33		* Size of the heap
34		*
35		* @var int
36		*/
37		private $size = 0;
38
39		/**
40		* Reference to current or some other heap in case of melding
41		*
42		* @var PairingHeap
43		*/
44		private $other;
45
46		/**
47		* Construct a new Pairing heap
48		*/
49	26	public function __construct()
50		{
51	26	$this->root = null;
52	26	$this->size = 0;
53	26	$this->other = $this;
54	26	$this->hash = uniqid('', true);
55	26	}
56
57		/**
58		* Insert a new node to the heap
59		*
60		* @param int $key - node key
61		* @param null\|mixed $value - node value
62		*
63		* @return AddressableHeapHandleInterface
64		*
65		* @throws Exception
66		*/
67	23	public function insert(int $key, $value = null): AddressableHeapHandleInterface
68		{
69	23	if ($this->other != $this) {
70	1	throw new Exception("A heap cannot be used after a meld");
71		}
72
73	23	$node = new PairingHeapNode($this, $key, $value);
74	23	$this->root = $this->link($this->root, $node);
75	23	$this->size += 1;
76	23	return $node;
77		}
78
79		/**
80		* Find heap node with the minimal key
81		*
82		* @return AddressableHeapHandleInterface
83		*
84		* @throws NoSuchElementException
85		*/
86	18	public function findMin(): AddressableHeapHandleInterface
87		{
88	18	if ($this->size == 0) {
89	1	throw new NoSuchElementException("No such element!");
90		}
91	17	return $this->root;
92		}
93
94		/*
95		* Delete a node
96		*
97		* @param PairingHeapNode $node - the node to delete
98		*/
99	7	public function delete(PairingHeapNode $node): void
100		{
101	7	if ($this->root == $node) {
102	5	$this->deleteMin();
103	5	$node->o_c = null;
104	5	$node->y_s = null;
105	5	$node->o_s = null;
106	5	return;
107		}
108
109	6	if (is_null($node->o_s)) {
110	3	throw new InvalidArgumentException("Invalid handle!");
111		}
112
113		// unlink from parent
114	4	if (!is_null($node->y_s)) {
115	4	$node->y_s->o_s = $node->o_s;
116		}
117	4	if ($node->o_s->o_c == $node) {
118	3	$node->o_s->o_c = $node->y_s;
119		} else {
120	3	$node->o_s->y_s = $node->y_s;
121		}
122	4	$node->y_s = null;
123	4	$node->o_s = null;
124
125		// perform delete-min at tree rooted at this
126	4	$t = $this->combine($this->cutChildren($node));
127
128		// and merge with other cut tree
129	4	$this->root = $this->link($this->root, $t);
130
131	4	$this->size -= 1;
132	4	}
133
134		/**
135		* Delete an element with the minimal key.
136		*
137		* @return AddressableHeapHandleInterface
138		*
139		* @throws NoSuchElementException
140		*/
141	18	public function deleteMin(): AddressableHeapHandleInterface
142		{
143	18	if ($this->size == 0) {
144	1	throw new NoSuchElementException("No such element!");
145		}
146	17	$oldRoot = $this->root;
147
148	17	$this->root = $this->combine($this->cutChildren($this->root));
149
150	17	$this->size -= 1;
151
152	17	return $oldRoot;
153		}
154
155		/**
156		* Check if the heap is empty.
157		*
158		* @return bool
159		*/
160	12	public function isEmpty(): bool
161		{
162	12	return $this->size == 0;
163		}
164
165		/**
166		* Get the number of elements in the heap.
167		*
168		* @return int
169		*/
170	8	public function size(): int
171		{
172	8	return $this->size;
173		}
174
175		/**
176		* Get the other heap referenced in the current heap
177		*
178		* @return MergeableAddressableHeapInterface
179		*/
180	12	public function getOther(): MergeableAddressableHeapInterface
181		{
182	12	return $this->other;
183		}
184
185		/**
186		* Reference the other heap in the current heap
187		*
188		* @param MergeableAddressableHeapInterface $other - the other heap
189		*/
190		public function setOther(MergeableAddressableHeapInterface $other): void
191		{
192		if (!($other instanceof PairingHeap)) {
193		throw new InvalidArgumentException("The heap must be of type Pairing.");
194		}
195		$this->other = $other;
196		}
197
198		/**
199		* Clear all the elements in the heap
200		*/
201		public function clear(): void
202		{
203		$this->root = null;
204		$this->size = 0;
205		$this->other = $this;
206		}
207
208		/**
209		* Meld other heap to the current heap
210		*
211		* @param MergeableAddressableHeapInterface $other - the heap to be melded
212		*
213		* @throws Exception
214		*/
215	8	public function meld(MergeableAddressableHeapInterface $other): void
216		{
217	8	if (!($other instanceof PairingHeap)) {
218		throw new InvalidArgumentException("The heap to be melded must be of type Pairing.");
219		}
220
221	8	if ($other->other != $other) {
222	1	throw new Exception("A heap cannot be used after a meld.");
223		}
224
225	8	$this->size += $other->size;
226	8	$this->root = $this->link($this->root, $other->root);
227
228		// clear other
229	8	$other->size = 0;
230	8	$other->root = null;
231
232		// take ownership
233	8	$other->other = $this;
234	8	}
235
236		/**
237		* Decrease the node key
238		*
239		* @param PairingHeapNode $node - the node
240		* @param int $newKey - the node new key
241		*
242		* @throws Exception
243		*/
244	6	public function decreaseKey(PairingHeapNode $node, int $newKey): void
245		{
246	6	if ($newKey > $node->key) {
247	1	throw new InvalidArgumentException("Keys can only be decreased!");
248	6	} elseif ($node->key != $newKey) {
249	6	if (is_null($node->o_s)) {
250	1	throw new InvalidArgumentException("Invalid handle!");
251		}
252	5	$node->key = $newKey;
253		// unlink from parent
254	5	if (!is_null($node->y_s)) {
255	5	$node->y_s->o_s = $node->o_s;
256		}
257	5	if ($node->o_s->o_c == $node) {
258	4	$node->o_s->o_c = $node->y_s;
259		} else {
260	2	$node->o_s->y_s = $node->y_s;
261		}
262	5	$node->y_s = null;
263	5	$node->o_s = null;
264
265		// merge with root
266	5	$this->root = $this->link($this->root, $node);
267		}
268	5	}
269
270		/*
271		* Link two nodes
272		*
273		* @param PairingHeapNode $first - first node
274		* @param PairingHeapNode $second - second node
275		*
276		* @return null\|PairingHeapNode
277		*/
278	23	private function link(?PairingHeapNode $first = null, ?PairingHeapNode $second = null): ?PairingHeapNode
279		{
280	23	if (is_null($second)) {
281	5	return $first;
282	23	} elseif (is_null($first)) {
283	23	return $second;
284	22	} elseif ($first->key < $second->key) {
285	22	$second->y_s = $first->o_c;
286	22	$second->o_s = $first;
287	22	if ($first->o_c != null) {
288	21	$first->o_c->o_s = $second;
289		}
290	22	$first->o_c = $second;
291	22	return $first;
292		}
293	18	return $this->link($second, $first);
294		}
295
296		/**
297		* Cut the children of a node and return the list.
298		*
299		* @param PairingHeapNode $node - the root node
300		*
301		* @return PairingHeapNode
302		*/
303	17	private function cutChildren(PairingHeapNode $node): ?PairingHeapNode
304		{
305	17	$child = $node->o_c;
306	17	$node->o_c = null;
307	17	if (!is_null($child)) {
308	16	$child->o_s = null;
309		}
310	17	return $child;
311		}
312
313		/*
314		* Two pass pair and compute root.
315		*
316		* @param PairingHeapNode $node - the node
317		*
318		* @return null\|PairingHeapNode
319		*/
320	17	private function combine(?PairingHeapNode $node = null): ?PairingHeapNode
321		{
322	17	if (is_null($node)) {
323	13	return null;
324		}
325	16	if (!is_null($node->o_s)) {
326		throw new InvalidArgumentException("Invalid handle!");
327		}
328
329		// left-right pass
330	16	$pairs = null;
331	16	$it = $node;
332	16	while (!is_null($it)) {
333	16	$p_it = $it;
334	16	$it = $it->y_s;
335
336	16	if (is_null($it)) {
337		// append last node to pair list
338	14	$p_it->y_s = $pairs;
339	14	$p_it->o_s = null;
340	14	$pairs = $p_it;
341		} else {
342	14	$n_it = $it->y_s;
343
344		// disconnect both
345	14	$p_it->y_s = null;
346	14	$p_it->o_s = null;
347	14	$it->y_s = null;
348	14	$it->o_s = null;
349
350		// link trees
351	14	$p_it = $this->link($p_it, $it);
352
353		// append to pair list
354	14	$p_it->y_s = $pairs;
355	14	$pairs = $p_it;
356
357		// advance
358	14	$it = $n_it;
359		}
360		}
361
362		// second pass (reverse order - due to add first)
363	16	$it = $pairs;
364	16	$f = null;
365	16	while (!is_null($it)) {
366	16	$nextIt = $it->y_s;
367	16	$it->y_s = null;
368	16	$f = $this->link($f, $it);
369	16	$it = $nextIt;
370		}
371
372	16	return $f;
373		}
374		}
375

bingo-soft / heap

Push — master ( f37b88...0dd5a5 )

PairingHeap::link() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like