Heap\Tree\FibonacciHeapNode

Complexity

Total Complexity

11

Size/Duplication

Total Lines	166
Duplicated Lines	0 %

Test Coverage

Coverage

91.67%

Importance

Changes

0

7 Methods

Rating	Name	Duplication	Size	Complexity
A	getOwner()	0	18	4
A	decreaseKey()	0	4	1
A	delete()	0	8	2
A	__construct()	0	6	1
A	getKey()	0	3	1
A	getValue()	0	3	1
A	setValue()	0	3	1

<?php

namespace Heap\Tree;

use InvalidArgumentException;
use Heap\AddressableHeapHandleInterface;

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

    /**
     * Node heap
     *
     * @var FibonacciHeap
     */
    public $heap;
    
    /**
     * Node value
     *
     * @var mixed
     */
    public $value;
    
    /**
     * Parent node
     *
     * @var FibonacciHeapNode
     */
    public $parent = null;
    
    /**
     * Child node
     *
     * @var FibonacciHeapNode
     */
    public $child = null;
    
    /**
     * Previous node
     *
     * @var FibonacciHeapNode
     */
    public $prev = null;
    
    /**
     * Next node
     *
     * @var FibonacciHeapNode
     */
    public $next = null;
    
    /**
     * True if the node lost child nodes
     *
     * @var bool
     */
    public $mark = false;
    
    /**
     * Node key
     *
     * @var int
     */
    public $key;
    
    /**
     * Node degree
     *
     * @var int
     */
    public $degree = 0;
    
    /**
     * Construct a new Fibonacci heap node
     *
     * @param FibonacciHeap $heap - heap to which the node belongs
     * @param int $key - the node key
     * @param mixed $value - value stored in the node
     */
    public function __construct(FibonacciHeap $heap, int $key, $value)
    {
        $this->heap = $heap;
        $this->key = $key;
        $this->value = $value;
        $this->hash = uniqid('', true);
    }

    /**
     * Get the node key
     *
     * @return int
     */
    public function getKey(): int
    {
        return $this->key;
    }
    
    /**
     * Get the node value
     *
     * @return mixed
     */
    public function getValue()
    {
        return $this->value;
    }
    
    /**
     * Set the node value
     *
     * @param mixed $value - node value
     */
    public function setValue($value): void
    {
        $this->value = $value;
    }

    /**
     * Decrease the node key
     *
     * @param int $newKey - new node key
     */
    public function decreaseKey(int $newKey): void
    {
        $heap = $this->getOwner();
        $heap->decreaseKey($this, $newKey);
    }

    /**
     * Delete the node
     *
     * @throws InvalidArgumentException
     */
    public function delete(): void
    {
        if (is_null($this->next)) {
            throw new InvalidArgumentException("Invalid handle!");
        }
        $heap = $this->getOwner();
        $heap->forceDecreaseKeyToMinimum($this);
        $heap->deleteMin();
    }

    /**
     * Get the owner heap of the node
     *
     * @return FibonacciHeap
     */
    public function getOwner(): FibonacciHeap
    {
        if ($this->heap->getOther() != $this->heap) {
            // find root
            $root = $this->heap;
            while ($root != $root->getOther()) {
                $root = $root->getOther();
            }
            // path-compression
            $cur = $this->heap;
            while ($cur->getOther() != $root) {
                $next = $cur->getOther();
                $cur->setOther($root);
                $cur = $next;
            }
            $this->heap = $root;
        }
        return $this->heap;
    }
}