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

Completed

Branch — master (a3dc87)

by Bingo

created 2019-11-15 19:30 UTC

FibonacciHeap::link() A

↳ Parent: FibonacciHeap

Complexity

Conditions	2
Paths	2

Size

Total Lines	26
Code Lines	16

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	2
eloc	16
nc	2
nop	2
dl	0
loc	26
rs	9.7333
c	0
b	0
f	0

<?php

namespace heap;

use Exception;
use InvalidArgumentException;

/**
 * Class FibonacciHeap
 *
 * @package heap
 */
class FibonacciHeap
{
    /**
     * 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;
    }

    /**
     * Insert a new node to the heap
     *
     * @param int $key - node key
     * @param null|mixed $value - node value
     *
     * @return FibonacciHeapNode
     *
     * @throws Exception
     */
    public function insert(int $key, $value = null): FibonacciHeapNode
    {
        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 FibonacciHeapNode
     *
     * @throws Exception
     */
    public function findMin(): FibonacciHeapNode
    {
        if ($this->size == 0) {
            throw new Exception("No such element!");
        }
        return $this->minRoot;
    }

    /**
     * Get an element with the minimum key.
     *
     * @return FibonacciHeapNode
     */
    public function deleteMin(): FibonacciHeapNode
    {
        if ($this->size == 0) {
            throw new Exception("No such element!");
        }
        $z = $this->minRoot;

        // move z children into root list
        $x = $z->child;
        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;
        }
        $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;
    }

    /**
     * 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 FibonacciHeap $other - the heap to be melded
     */
    public function meld(FibonacciHeap $other): void
    {
        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
     */
    private function decreaseKey(FibonacciHeapNode $node, int $newKey): void

    {
        if ($newKey > $node->key) {
            throw new Exception("Keys can only be decreased!");
        } elseif ($node->key != $newKey) {
            $node->key = $newKey;
            
            if (is_null($node->next)) {
                throw new Exception("Invalid handle!");
            }

            // 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) {
                $y = $this->aux[$deg];
                if (is_null($y)) {
                    break;
                }

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

bingo-soft / heap

Branch — master (a3dc87)

FibonacciHeap::link() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like