FibonacciHeap::meld() - Code Metrics - Inspection of "fix: fix cicd configuration" - bingo-soft/heap - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 75f154...f90f6b )

by Bingo

created 2019-11-24 10:41 UTC

FibonacciHeap::meld() B

↳ Parent: FibonacciHeap

Complexity

Conditions	6
Paths	6

Size

Total Lines	39
Code Lines	23

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	22
CRAP Score	6.0208

Importance

Changes

Metric	Value
cc	6
eloc	23
nc	6
nop	1
dl	0
loc	39
ccs	22
cts	24
cp	0.9167
crap	6.0208
rs	8.9297
c	0
b	0
f	0

<?php

namespace Heap\Tree;

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

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

    /**
     * Heap node with the minimal key
     *
     * @var FibonacciHeapNode
     */
    private $minRoot = null;
    
    /**
     * Number of roots in the heap
     *
     * @var int
     */
    private $roots = 0;

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

    /**
     * Auxiliary array for consolidation
     */
    private $aux = [];

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

    /**
     * Construct a new Fibonacci heap
     */
    public function __construct()
    {
        $this->minRoot = null;
        $this->roots = 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 FibonacciHeapNode($this, $key, $value);
        $this->addToRootList($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->minRoot;
    }

    /**
     * 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!");
        }
        $z = $this->minRoot;

        // move z children into root list
        $x = $z->child;
        $i = 0;
        while (!is_null($x)) {
            $nextX = ($x->next == $x) ? null : $x->next;

            // clear parent
            $x->parent = null;

            // remove from child list
            $x->prev->next = $x->next;
            $x->next->prev = $x->prev;

            // add to root list
            $x->next = $this->minRoot->next;
            // probably need to reset
            $x->prev = $this->minRoot;
            $this->minRoot->next = $x;
            $x->next->prev = $x;
            $this->roots += 1;

            // advance
            $x = $nextX;
            $i += 1;
        }
        $z->degree = 0;
        $z->child = null;

        // remove z from root list
        $z->prev->next = $z->next;
        $z->next->prev = $z->prev;
        $this->roots -= 1;

        // decrease size
        $this->size -= 1;

        // update minimum root
        
        if ($z == $z->next) {
            $this->minRoot = null;
        } else {
            $this->minRoot = $z->next;
            $this->consolidate();
        }

        // clear other fields
        $z->next = null;
        $z->prev = null;

        return $z;
    }

    /**
     * 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 FibonacciHeap)) {
            throw new InvalidArgumentException("The heap must be of type Fibonacci.");
        }
        $this->other = $other;
    }

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

    /**
     * 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 FibonacciHeap)) {
            throw new InvalidArgumentException("The heap to be melded must be of type Fibonacci.");
        }

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

        if ($this->size == 0) {
            // copy the other
            $this->minRoot = $other->minRoot;
        } elseif ($other->size != 0) {
            // concatenate root lists
            $h11 = $this->minRoot;
            $h12 = $h11->next;
            $h21 = $other->minRoot;
            $h22 = $h21->next;
            $h11->next = $h22;
            $h22->prev = $h11;
            $h21->next = $h12;
            $h12->prev = $h21;

            // find new minimum
            if ($other->minRoot->key < $this->minRoot->key) {
                $this->minRoot = $other->minRoot;
            }
        }
        $this->roots += $other->roots;
        $this->size += $other->size;

        // clear other
        $other->size = 0;
        $other->minRoot = null;
        $other->roots = 0;

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

    /**
     * Decrease the node key
     *
     * @param FibonacciHeapNode $node - the node
     * @param int $newKey - the node new key
     *
     * @throws Exception
     */
    public function decreaseKey(FibonacciHeapNode $node, int $newKey): void
    {
        if ($newKey > $node->key) {
            throw new InvalidArgumentException("Keys can only be decreased!");
        } elseif ($node->key != $newKey) {
            if (is_null($node->next)) {
                throw new InvalidArgumentException("Invalid handle!");
            }

            $node->key = $newKey;

            // if not root and heap order violation
            $parent = $node->parent;
            if (!is_null($parent) && $node->key < $parent->key) {
                $this->cut($node, $parent);
                $this->cascadingCut($parent);
            }

            // update minimum root
            if ($node->key < $this->minRoot->key) {
                $this->minRoot = $node;
            }
        }
    }

    /*
     * Decrease the key of a node to the minimum
     *
     * @param FibonacciHeapNode $node - the node
     */
    public function forceDecreaseKeyToMinimum(FibonacciHeapNode $node): void
    {
        // if not root
        $parent = $node->parent;
        if (!is_null($parent)) {
            $this->cut($node, $parent);
            $this->cascadingCut($parent);
        }
        $this->minRoot = $node;
    }

    /*
     * Consolidate: Make sure each root tree has a distinct degree.
     */
    private function consolidate(): void
    {
        $maxDegree = -1;

        // for each node in root list
        $numRoots = $this->roots;
        $x = $this->minRoot;
        while ($numRoots > 0) {
            $nextX = $x->next;
            $deg = $x->degree;

            while (true) {
                if (!isset($this->aux[$deg])) {
                    break;
                }
                $y = $this->aux[$deg];

                // make sure x's key is smaller
                if ($y->key < $x->key) {
                    $tmp = $x;
                    $x = $y;
                    $y = $tmp;
                }

                // make y a child of x
                $this->link($y, $x);

                $this->aux[$deg] = null;
                $deg += 1;
            }

            // store result
            $this->aux[$deg] = $x;

            // keep track of max degree
            if ($deg > $maxDegree) {
                $maxDegree = $deg;
            }

            // advance
            $x = $nextX;
            $numRoots -= 1;
        }

        // recreate root list and find minimum root
        $this->minRoot = null;
        $this->roots = 0;
        for ($i = 0; $i <= $maxDegree; $i += 1) {
            if (!is_null($this->aux[$i])) {
                $this->addToRootList($this->aux[$i]);
                $this->aux[$i] = null;
            }
        }
    }

    /*
     * Remove node "first" from the root list and make it a child of "second". Degree of "second"
     * increases by 1 and "first" is unmarked if marked.
     *
     * @param FibonacciHeapNode $first - first node
     * @param FibonacciHeapNode $second - second node
     */
    private function link(FibonacciHeapNode $first, FibonacciHeapNode $second): void
    {
        // remove from root list
        $first->prev->next = $first->next;
        $first->next->prev = $first->prev;

        // one less root
        $this->roots -= 1;

        // clear if marked
        $first->mark = false;

        // hang as second's child
        $second->degree += 1;
        $first->parent = $second;

        $child = $second->child;
        if (is_null($child)) {
            $second->child = $first;
            $first->next = $first;
            $first->prev = $first;
        } else {
            $first->prev = $child;
            $first->next = $child->next;
            $child->next = $first;
            $first->next->prev = $first;
        }
    }

    /*
     * Cut the link between node and its parent making node a root.
     *
     * @param FibonacciHeapNode $node - the node
     * @param FibonacciHeapNode $parent - the root node
     */
    private function cut(FibonacciHeapNode $node, FibonacciHeapNode $parent): void
    {
        // remove x from child list of y
        $node->prev->next = $node->next;
        $node->next->prev = $node->prev;
        $parent->degree -= 1;
        if ($parent->degree == 0) {
            $parent->child = null;
        } elseif ($parent->child == $node) {
            $parent->child = $node->next;
        }

        // add x to the root list
        $node->parent = null;
        $this->addToRootList($node);

        // clear if marked
        $node->mark = false;
    }

    /*
     * Cascading cut until a root or an unmarked node is found.
     *
     * @param FibonacciHeapNode $node - the starting node
     */
    private function cascadingCut(FibonacciHeapNode $node): void
    {
        while (!is_null(($parent = $node->parent))) {
            if (!$parent->mark) {
                $parent->mark = true;
                break;
            }
            $this->cut($node, $parent);
            $node = $parent;
        }
    }

    /**
     * Add the specified node to heap root list
     *
     * @param FibonacciHeapNode $node - the node to be added
     */
    private function addToRootList(FibonacciHeapNode $node): void
    {
        if (is_null($this->minRoot)) {
            $node->next = $node;
            $node->prev = $node;
            $this->minRoot = $node;
            $this->roots = 1;
        } else {
            $node->next = $this->minRoot->next;
            $node->prev = $this->minRoot;
            $this->minRoot->next->prev = $node;
            $this->minRoot->next = $node;

            if ($node->key < $this->minRoot->key) {
                $this->minRoot = $node;
            }
            $this->roots += 1;
        }
    }
}


1		<?php
2
3		namespace Heap\Tree;
4
5		use Exception;
6		use InvalidArgumentException;
7		use Heap\exception\NoSuchElementException;
8		use Heap\MergeableAddressableHeapInterface;
9		use Heap\AddressableHeapHandleInterface;
10
11		/**
12		* Class FibonacciHeap
13		*
14		* @package Heap\Tree
15		*/
16		class FibonacciHeap implements MergeableAddressableHeapInterface
17		{
18		/**
19		* The heap unique hash
20		*
21		* @var string
22		*/
23		private $hash;
24
25		/**
26		* Heap node with the minimal key
27		*
28		* @var FibonacciHeapNode
29		*/
30		private $minRoot = null;
31
32		/**
33		* Number of roots in the heap
34		*
35		* @var int
36		*/
37		private $roots = 0;
38
39		/**
40		* Size of the heap
41		*
42		* @var int
43		*/
44		private $size = 0;
45
46		/**
47		* Auxiliary array for consolidation
48		*/
49		private $aux = [];
50
51		/**
52		* Reference to current or some other heap in case of melding
53		*
54		* @var FibonacciHeap
55		*/
56		private $other;
57
58		/**
59		* Construct a new Fibonacci heap
60		*/
61	26	public function __construct()
62		{
63	26	$this->minRoot = null;
64	26	$this->roots = 0;
65	26	$this->other = $this;
66	26	$this->hash = uniqid('', true);
67	26	}
68
69		/**
70		* Insert a new node to the heap
71		*
72		* @param int $key - node key
73		* @param null\|mixed $value - node value
74		*
75		* @return AddressableHeapHandleInterface
76		*
77		* @throws Exception
78		*/
79	23	public function insert(int $key, $value = null): AddressableHeapHandleInterface
80		{
81	23	if ($this->other != $this) {
82	1	throw new Exception("A heap cannot be used after a meld");
83		}
84
85	23	$node = new FibonacciHeapNode($this, $key, $value);
86	23	$this->addToRootList($node);
87	23	$this->size += 1;
88	23	return $node;
89		}
90
91		/**
92		* Find heap node with the minimal key
93		*
94		* @return AddressableHeapHandleInterface
95		*
96		* @throws NoSuchElementException
97		*/
98	18	public function findMin(): AddressableHeapHandleInterface
99		{
100	18	if ($this->size == 0) {
101	1	throw new NoSuchElementException("No such element!");
102		}
103	17	return $this->minRoot;
104		}
105
106		/**
107		* Delete an element with the minimal key.
108		*
109		* @return AddressableHeapHandleInterface
110		*
111		* @throws NoSuchElementException
112		*/
113	18	public function deleteMin(): AddressableHeapHandleInterface
114		{
115	18	if ($this->size == 0) {
116	1	throw new NoSuchElementException("No such element!");
117		}
118	17	$z = $this->minRoot;
119
120		// move z children into root list
121	17	$x = $z->child;
122	17	$i = 0;
123	17	while (!is_null($x)) {
124	12	$nextX = ($x->next == $x) ? null : $x->next;
125
126		// clear parent
127	12	$x->parent = null;
128
129		// remove from child list
130	12	$x->prev->next = $x->next;
131	12	$x->next->prev = $x->prev;
132
133		// add to root list
134	12	$x->next = $this->minRoot->next;
135		// probably need to reset
136	12	$x->prev = $this->minRoot;
137	12	$this->minRoot->next = $x;
138	12	$x->next->prev = $x;
139	12	$this->roots += 1;
140
141		// advance
142	12	$x = $nextX;
143	12	$i += 1;
144		}
145	17	$z->degree = 0;
146	17	$z->child = null;
147
148		// remove z from root list
149	17	$z->prev->next = $z->next;
150	17	$z->next->prev = $z->prev;
151	17	$this->roots -= 1;
152
153		// decrease size
154	17	$this->size -= 1;
155
156		// update minimum root
157
158	17	if ($z == $z->next) {
159	11	$this->minRoot = null;
160		} else {
161	17	$this->minRoot = $z->next;
162	17	$this->consolidate();
163		}
164
165		// clear other fields
166	17	$z->next = null;
167	17	$z->prev = null;
168
169	17	return $z;
170		}
171
172		/**
173		* Check if the heap is empty.
174		*
175		* @return bool
176		*/
177	12	public function isEmpty(): bool
178		{
179	12	return $this->size == 0;
180		}
181
182		/**
183		* Get the number of elements in the heap.
184		*
185		* @return int
186		*/
187	8	public function size(): int
188		{
189	8	return $this->size;
190		}
191
192		/**
193		* Get the other heap referenced in the current heap
194		*
195		* @return MergeableAddressableHeapInterface
196		*/
197	10	public function getOther(): MergeableAddressableHeapInterface
198		{
199	10	return $this->other;
200		}
201
202		/**
203		* Reference the other heap in the current heap
204		*
205		* @param MergeableAddressableHeapInterface $other - the other heap
206		*/
207		public function setOther(MergeableAddressableHeapInterface $other): void
208		{
209		if (!($other instanceof FibonacciHeap)) {
210		throw new InvalidArgumentException("The heap must be of type Fibonacci.");
211		}
212		$this->other = $other;
213		}
214
215		/**
216		* Clear all the elements in the heap
217		*/
218		public function clear(): void
219		{
220		$this->minRoot = null;
221		$this->roots = 0;
222		$this->other = $this;
223		$this->size = 0;
224		}
225
226		/**
227		* Meld other heap to the current heap
228		*
229		* @param MergeableAddressableHeapInterface $other - the heap to be melded
230		*
231		* @throws Exception
232		*/
233	8	public function meld(MergeableAddressableHeapInterface $other): void
234		{
235	8	if (!($other instanceof FibonacciHeap)) {
236		throw new InvalidArgumentException("The heap to be melded must be of type Fibonacci.");
237		}
238
239	8	if ($other->other != $other) {
240	1	throw new Exception("A heap cannot be used after a meld.");
241		}
242
243	8	if ($this->size == 0) {
244		// copy the other
245	1	$this->minRoot = $other->minRoot;
246	7	} elseif ($other->size != 0) {
247		// concatenate root lists
248	6	$h11 = $this->minRoot;
249	6	$h12 = $h11->next;
250	6	$h21 = $other->minRoot;
251	6	$h22 = $h21->next;
252	6	$h11->next = $h22;
253	6	$h22->prev = $h11;
254	6	$h21->next = $h12;
255	6	$h12->prev = $h21;
256
257		// find new minimum
258	6	if ($other->minRoot->key < $this->minRoot->key) {
259		$this->minRoot = $other->minRoot;
260		}
261		}
262	8	$this->roots += $other->roots;
263	8	$this->size += $other->size;
264
265		// clear other
266	8	$other->size = 0;
267	8	$other->minRoot = null;
268	8	$other->roots = 0;
269
270		// take ownership
271	8	$other->other = $this;
272	8	}
273
274		/**
275		* Decrease the node key
276		*
277		* @param FibonacciHeapNode $node - the node
278		* @param int $newKey - the node new key
279		*
280		* @throws Exception
281		*/
282	6	public function decreaseKey(FibonacciHeapNode $node, int $newKey): void
283		{
284	6	if ($newKey > $node->key) {
285	1	throw new InvalidArgumentException("Keys can only be decreased!");
286	6	} elseif ($node->key != $newKey) {
287	6	if (is_null($node->next)) {
288	1	throw new InvalidArgumentException("Invalid handle!");
289		}
290
291	5	$node->key = $newKey;
292
293		// if not root and heap order violation
294	5	$parent = $node->parent;
295	5	if (!is_null($parent) && $node->key < $parent->key) {
296	1	$this->cut($node, $parent);
297	1	$this->cascadingCut($parent);
298		}
299
300		// update minimum root
301	5	if ($node->key < $this->minRoot->key) {
302	5	$this->minRoot = $node;
303		}
304		}
305	5	}
306
307		/*
308		* Decrease the key of a node to the minimum
309		*
310		* @param FibonacciHeapNode $node - the node
311		*/
312	5	public function forceDecreaseKeyToMinimum(FibonacciHeapNode $node): void
313		{
314		// if not root
315	5	$parent = $node->parent;
316	5	if (!is_null($parent)) {
317	4	$this->cut($node, $parent);
318	4	$this->cascadingCut($parent);
319		}
320	5	$this->minRoot = $node;
321	5	}
322
323		/*
324		* Consolidate: Make sure each root tree has a distinct degree.
325		*/
326	17	private function consolidate(): void
327		{
328	17	$maxDegree = -1;
329
330		// for each node in root list
331	17	$numRoots = $this->roots;
332	17	$x = $this->minRoot;
333	17	while ($numRoots > 0) {
334	17	$nextX = $x->next;
335	17	$deg = $x->degree;
336
337	17	while (true) {
338	17	if (!isset($this->aux[$deg])) {
339	17	break;
340		}
341	16	$y = $this->aux[$deg];
342
343		// make sure x's key is smaller
344	16	if ($y->key < $x->key) {
345	10	$tmp = $x;
346	10	$x = $y;
347	10	$y = $tmp;
348		}
349
350		// make y a child of x
351	16	$this->link($y, $x);
352
353	16	$this->aux[$deg] = null;
354	16	$deg += 1;
355		}
356
357		// store result
358	17	$this->aux[$deg] = $x;
359
360		// keep track of max degree
361	17	if ($deg > $maxDegree) {
362	17	$maxDegree = $deg;
363		}
364
365		// advance
366	17	$x = $nextX;
367	17	$numRoots -= 1;
368		}
369
370		// recreate root list and find minimum root
371	17	$this->minRoot = null;
372	17	$this->roots = 0;
373	17	for ($i = 0; $i <= $maxDegree; $i += 1) {
374	17	if (!is_null($this->aux[$i])) {
375	17	$this->addToRootList($this->aux[$i]);
376	17	$this->aux[$i] = null;
377		}
378		}
379	17	}
380
381		/*
382		* Remove node "first" from the root list and make it a child of "second". Degree of "second"
383		* increases by 1 and "first" is unmarked if marked.
384		*
385		* @param FibonacciHeapNode $first - first node
386		* @param FibonacciHeapNode $second - second node
387		*/
388	16	private function link(FibonacciHeapNode $first, FibonacciHeapNode $second): void
389		{
390		// remove from root list
391	16	$first->prev->next = $first->next;
392	16	$first->next->prev = $first->prev;
393
394		// one less root
395	16	$this->roots -= 1;
396
397		// clear if marked
398	16	$first->mark = false;
399
400		// hang as second's child
401	16	$second->degree += 1;
402	16	$first->parent = $second;
403
404	16	$child = $second->child;
405	16	if (is_null($child)) {
406	16	$second->child = $first;
407	16	$first->next = $first;
408	16	$first->prev = $first;
409		} else {
410	15	$first->prev = $child;
411	15	$first->next = $child->next;
412	15	$child->next = $first;
413	15	$first->next->prev = $first;
414		}
415	16	}
416
417		/*
418		* Cut the link between node and its parent making node a root.
419		*
420		* @param FibonacciHeapNode $node - the node
421		* @param FibonacciHeapNode $parent - the root node
422		*/
423	5	private function cut(FibonacciHeapNode $node, FibonacciHeapNode $parent): void
424		{
425		// remove x from child list of y
426	5	$node->prev->next = $node->next;
427	5	$node->next->prev = $node->prev;
428	5	$parent->degree -= 1;
429	5	if ($parent->degree == 0) {
430	4	$parent->child = null;
431	5	} elseif ($parent->child == $node) {
432	4	$parent->child = $node->next;
433		}
434
435		// add x to the root list
436	5	$node->parent = null;
437	5	$this->addToRootList($node);
438
439		// clear if marked
440	5	$node->mark = false;
441	5	}
442
443		/*
444		* Cascading cut until a root or an unmarked node is found.
445		*
446		* @param FibonacciHeapNode $node - the starting node
447		*/
448	5	private function cascadingCut(FibonacciHeapNode $node): void
449		{
450	5	while (!is_null(($parent = $node->parent))) {
451	3	if (!$parent->mark) {
452	3	$parent->mark = true;
453	3	break;
454		}
455	1	$this->cut($node, $parent);
456	1	$node = $parent;
457		}
458	5	}
459
460		/**
461		* Add the specified node to heap root list
462		*
463		* @param FibonacciHeapNode $node - the node to be added
464		*/
465	23	private function addToRootList(FibonacciHeapNode $node): void
466		{
467	23	if (is_null($this->minRoot)) {
468	23	$node->next = $node;
469	23	$node->prev = $node;
470	23	$this->minRoot = $node;
471	23	$this->roots = 1;
472		} else {
473	22	$node->next = $this->minRoot->next;
474	22	$node->prev = $this->minRoot;
475	22	$this->minRoot->next->prev = $node;
476	22	$this->minRoot->next = $node;
477
478	22	if ($node->key < $this->minRoot->key) {
479	10	$this->minRoot = $node;
480		}
481	22	$this->roots += 1;
482		}
483	23	}
484		}
485

bingo-soft / heap

Push — master ( 75f154...f90f6b )

FibonacciHeap::meld() B

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like