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

Passed

Push — master ( a3dc87...7d902f )

by Bingo

created 2019-11-16 17:52 UTC

FibonacciHeap::getOther() A

↳ Parent: FibonacciHeap

Complexity

Conditions	1
Paths	1

Size

Total Lines	3
Code Lines	1

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	1
eloc	1
nc	1
nop	0
dl	0
loc	3
rs	10
c	0
b	0
f	0

<?php

namespace heap;

use Exception;
use InvalidArgumentException;

/**
 * Class FibonacciHeap
 *
 * @package heap
 */
class FibonacciHeap
{
    /**
     * 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 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;
        $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 FibonacciHeap
     */
    public function getOther(): FibonacciHeap
    {
        return $this->other;
    }

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

bingo-soft / heap

Push — master ( a3dc87...7d902f )

FibonacciHeap::getOther() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like