<?php

 namespace Test;

 use Iterator;

 use ArrayAccess;

 use Exception;

 // 叶子结点或者连接结点的基类

 class HuffmanBase

 {

     protected $weight;       // 权重

     protected $parent;

     public function setParent($parent)

     {

         $this->parent = $parent;

     }

     public function getWeight()

     {

         return $this->weight;

     }

     public function getParent()

     {

         return $this->parent;

     }

 }

 // 叶子结点

 class HuffmanLeafNode extends HuffmanBase

 {

     protected $code;   // 需要编码的字母

     public function __construct($weight,$code,$parent = null)

     {

         if(!is_int($weight) || $weight <= 0 || is_null($code))

         {

             throw new Exception('Param is error!' .__FILE__.__LINE__);

         }

         $this->weight = abs($weight);

         $this->code = $code;

         $this->parent = $parent;

     }

     public function getCode()

     {

         return $this->code;

     }

 }

 // 连接结点

 class HuffmanJoinNode extends HuffmanBase

 {

     protected $lChild;

     protected $rChild;

     public function __construct($weight = 0,$lChild = null,$rChild = null)

     {

         $this->weight = $weight;

         $this->rChild = $rChild;

         $this->lChild = $lChild;

     }

     public function setWeight($leftWeight,$rightWeight)

     {

         if(!is_int($this->rChild) || !is_int($this->lChild))

         {

             throw new \Exception("Please initialize the left child or the right child!\n");

         }

         $this->weight = $leftWeight + $rightWeight;

     }

     public function setChild($child,$leftOrRight)

     {

         if('left' == $leftOrRight)

         {

             $this->lChild = $child;

         }

         elseif('right' == $leftOrRight)

         {

             $this->rChild = $child;

         }

         else

         {

             throw new \Exception("Please input 'left' or 'right' to leftOrRight!\n");

         }

     }

     public function getChild($leftOrRight)

     {

         if('left' == $leftOrRight)

         {

             return $this->lChild;

         }

         elseif('right' == $leftOrRight)

         {

             return $this->rChild;

         }

         else

         {

             throw new \Exception("Please input 'left' or 'right' to leftOrRight!\n");

         }

     }

 }

 // 哈夫曼树

 class HuffmanTree implements \ArrayAccess,\Iterator

 {

     protected $nodes = array();

     public function &getAllNodes()

     {

         return $this->nodes;

     }

     public function offsetExists($offset)

     {

         // TODO: Implement offsetExists() method.

         return isset($this->nodes[$offset]);

     }

     public function offsetGet($offset)

     {

         // TODO: Implement offsetGet() method.

         if(isset($this->nodes[$offset]))

         {

             return $this->nodes[$offset];

         }

         else

         {

             return null;

         }

     }

     public function offsetSet($offset,$value)

     {

         // TODO: Implement offsetSet() method.

         if(!($value instanceof HuffmanBase))

         {

             throw new Exception('Param is error!' .__FILE__.__LINE__);

         }

         if(is_null($offset))

         {

             $this->nodes[] = $value;

         }

         else

         {

             $this->nodes[$offset] = $value;

         }

     }

     public function offsetUnset($offset)

     {

         // TODO: Implement offsetUnset() method.

         unset($this->nodes[$offset]);

     }

     public function current()

     {

         // TODO: Implement current() method.

         return current($this->nodes);

     }

     public function key()

     {

         // TODO: Implement key() method.

         return key($this->nodes);

     }

     public function next()

     {

         // TODO: Implement next() method.

         next($this->nodes);

     }

     public function rewind()

     {

         // TODO: Implement rewind() method.

         reset($this->nodes);

     }

     public function valid()

     {

         // TODO: Implement valid() method.

         return $this->offsetExists(key($this->nodes));

     }

     public function length()

     {

         return count($this->nodes);

     }

 }

 // 从[$left,$right]区间选择parent=0并且weight最小的两个结点，其序号分别为$minNode1,$minNode2;

 function selectTwoMinWeightNode(HuffmanTree &$huffmanTree,$left,$right,&$minNode1,&$minNode2)

 {

     $left = abs($left);

     $right = abs($right);

     if(!is_int($left) || !is_int($right) || $left == $right)

     {

         throw new Exception('Param is error!' .__FILE__.__LINE__);

     }

     if($left > $right)

     {

         $tmp = $left;

         $left = $right;

         $right = $tmp;

     }

     $nodes = $huffmanTree->getAllNodes();

     if(!isset($nodes[$right]))

     {

         throw new Exception('Over the array index!'.__FILE__.__LINE__);

     }

     $tmp = array();

     for($i = $left;$i <= $right; ++$i)

     {

         $huffmanNode = $huffmanTree[$i];

         if(!is_null($huffmanNode->getParent()))

         {

             continue;

         }

         $tmp[$i] = $huffmanNode->getWeight();

     }

     if(count($tmp) <= 1)

     {

         throw new Exception('Not enough number!'.__FILE__.__LINE__);

     }

     asort($tmp,SORT_NUMERIC);

     $t = array_keys($tmp);

     $minNode1 = $t[0];

     $minNode2 = $t[1];

 }

 // (编码 => 权重)

 $nodes = array('A' => 3, 'B' => 4, 'C' => 7, 'D' => 10);

 $huffmanTree = new HuffmanTree();

 // 初始化哈夫曼树的叶子结点

 foreach($nodes as $code => $weight)

 {

     $huffmanNode = new HuffmanLeafNode($weight,$code);

     $huffmanTree[] = $huffmanNode;

 }

 $leafCount = $huffmanTree->length();        // 叶子结点的数量（大于1的值）

 $nodeCount = 2 * $leafCount -1 ;           // 哈夫曼树结点的数量

 // 初始化哈夫曼树的非叶子结点(如果编译器未优化，--$i应该是比$i++效率高点的)

 for($i = $nodeCount - $leafCount;$i >= 1; --$i)

 {

     $huffmanNode = new HuffmanJoinNode();

     $huffmanTree[] = $huffmanNode;

 }

 // 建立哈夫曼树

 for($i = $leafCount;$i < $nodeCount; ++$i)

 {

     selectTwoMinWeightNode($huffmanTree,0,$i-1,$minNode1,$minNode2);

     $huffmanNode1 = $huffmanTree[$minNode1];

     $huffmanNode2 = $huffmanTree[$minNode2];

     $huffmanNode1->setParent($i);

     $huffmanNode2->setParent($i);

     $huffmanTree[$i]->setChild($minNode1,'left');

     $huffmanTree[$i]->setChild($minNode2,'right');

     $huffmanTree[$i]->setWeight($huffmanNode1->getWeight(),$huffmanNode2->getWeight());

 }

 // 从叶子到根的遍历，得到字母的编码

 $huffmanCode = array();

 for($i = 0;$i < $leafCount; ++$i)

 {

     $leafNode = $huffmanTree[$i];

     $code = $leafNode->getCode();

     $reverseCode = array();

     for($c = $i,$pi = $leafNode->getParent();!is_null($pi);$pi = $huffmanTree[$pi]->getParent())

     {

         $huffmanNode = $huffmanTree[$pi];

         if($huffmanNode->getChild('left') === $c)

         {

             $reverseCode[] = 0;

         }

         elseif($huffmanNode->getChild('right') === $c)

         {

             $reverseCode[] = 1;

         }

         else

         {

             throw new Exception('Something error happened!' .__FILE__.__LINE__);

         }

         $c = $pi;

     }

     $huffmanCode[$code] = array_reverse($reverseCode);

 }

 foreach($huffmanCode as $key => $value)

 {

     $s = implode(',',$value);

     echo $key. " : " .$s ."\n";

 }