Mfonte\Base62x\Compression\Huffman\HuffmanNode

Complexity

Total Complexity

19

Size/Duplication

Total Lines	127
Duplicated Lines	0 %

Importance

Changes	2
Bugs	1	Features	0

12 Methods

Rating	Name	Duplication	Size	Complexity
A	__construct()	0	4	1
A	getCodeHash()	0	7	2
A	getWeight()	0	3	1
A	loadFromString()	0	3	1
A	getSymbol()	0	3	1
A	readEncodedNode()	0	29	5
A	getLeftChild()	0	3	1
A	join()	0	7	1
A	getRightChild()	0	3	1
A	getParent()	0	3	1
A	__toString()	0	10	3
A	isLeaf()	0	3	1

<?php

namespace Mfonte\Base62x\Compression\Huffman;

use Mfonte\Base62x\Exception\CompressionException;

/**
 * 	Node in a huffman tree implementing a huffman coding.
 */
class HuffmanNode
{
    private $weight = null;
    private $symbol = null;
    private $leftChild = null;
    private $rightChild = null;
    private $parent = null;

    /**
     *	create a new leaf node.
     */
    public function __construct($symbol, $weight = null)
    {
        $this->symbol = $symbol;
        $this->weight = $weight;
    }

    /**
     * 	create a new node whose children are the supplied nodes.
     */
    public static function join(self $left, self $right)
    {
        $newParent = new self(null, $left->getWeight() + $right->getWeight());
        $newParent->leftChild = $left;
        $newParent->rightChild = $right;

        return $newParent;
    }

    /**
     * 	perform a depth-first search to construct a.
     */
    public function getCodeHash(&$hashTable, $prefix = '')
    {
        if ($this->isLeaf()) {
            $hashTable[$this->symbol] = $prefix;
        } else {
            $this->leftChild->getCodeHash($hashTable, "{$prefix}0");
            $this->rightChild->getCodeHash($hashTable, "{$prefix}1");
        }
    }

    public function isLeaf()
    {
        return $this->symbol !== null;
    }

    public function getWeight()
    {
        return $this->weight;
    }

    public function getSymbol()
    {
        return $this->symbol;
    }

    public function getRightChild()
    {
        return $this->rightChild;
    }

    public function getLeftChild()
    {
        return $this->leftChild;
    }

    public function getParent()
    {
        return $this->parent;
    }

    /**
     * 	read a node encoded using __toString.
     */
    private static function readEncodedNode(&$str)
    {
        $retval = null;
        $switch = $str[0];
        $str = mb_substr($str, 1);
        switch ($switch) {
            case '0':
                $left = self::readEncodedNode($str);
                $right = self::readEncodedNode($str);
                $parent = new self(null);
                $parent->leftChild = $left;
                $parent->rightChild = $right;

                $retval = $parent;
                break;
            case '1':
            case '2':
                $symbol = ($switch == 1)
                    ? $str[0] :
                    HuffmanCoding::SYMBOL_EOF;
                $str = mb_substr($str, 1);

                $retval = new self($symbol);
                break;
            default:
                throw new CompressionException('huffman', 'Encoding is out of sync.');
        }

        return $retval;
    }

    /**
     * 	opposite of __toString.
     **/
    public static function loadFromString(&$str)
    {
        return self::readEncodedNode($str);
    }

    /**
     * 	create a string for compactly encoding this node (and its children).
     */
    public function __toString()
    {
        if ($this->isLeaf()) {
            if ($this->symbol === HuffmanCoding::SYMBOL_EOF) {
                return '2~';	//	~ stands in BC HuffmanCoding::SYMBOL_EOF may be more than one byte
            } else {
                return '1'.$this->symbol;
            }
        } else {
            return '0'.(string) $this->leftChild.(string) $this->rightChild;
        }
    }
}