<?php

/* 
 * Przykładowy kod do książki: Algorytmy i struktury danych w języku PHP 7
 * 
 * Autor: Mizanur Rahman <mizanur.rahman@gmail.com>
 * 
 */

function huffmanEncode(array $symbols): array {
   $heap = new SplPriorityQueue;
   $heap->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
   foreach ($symbols as $symbol => $weight) {
      $heap->insert(array($symbol => ''), -$weight);
   }
   
   while ($heap->count() > 1) {
      $low = $heap->extract();
      $high = $heap->extract();
      foreach ($low['data'] as &$x)
         $x = '0' . $x;
      foreach ($high['data'] as &$x)
         $x = '1' . $x;
      $heap->insert($low['data'] + $high['data'], $low['priority'] + $high['priority']);
   }
   $result = $heap->extract();
   return $result['data'];
}

$txt = 'Algorytmy i struktury danych w języku PHP 7 ';
$symbols = array_count_values(str_split($txt));
$codes = huffmanEncode($symbols);

echo "Symbol\t\tWaga\t\tKod Huffmana\n";
foreach ($codes as $sym => $code) {
   echo "$sym\t\t$symbols[$sym]\t\t$code\n";
}
