3v4l.org

run code in 300+ PHP versions simultaneously
<?php abstract class Drzewo { public $waga; public $znaki; // tworzymy nowe Drzewo - zeby to zrozumiec przydaje sie zajrzec do konstruktora Rozgalezionego drzewa function nowe_Drzewo($prawe) { $nowawaga = $this->waga + $prawe->waga; $noweznaki = $this->znaki + $prawe->znaki; return new Rozgalezione($this,$prawe,$noweznaki,$nowawaga); } // to nalezy przeczytac po zobaczeniu jak tworzone sa drzewa function dekoduj_znak($bity) { if ($this instanceof Lisc) return array($this->znak,$bity); else if ($bity[0] == 0) $nowedrzewo = $this->lewe; else $nowedrzewo = $this->prawe; return $nowedrzewo->dekoduj_znak(array_slice($bity,1)); } function dekoduj($bity){ if ($bity == array()) array(); else { $odkodowany_znak = dekoduj_znak($bity); $znak = $odkodowany_znak[0]; $nowebity = $odkodowany_znak[1]; $dekodowanareszta = $this->dekoduj($nowebity); return array_merge(array($a),$dekodowanareszta); } } } //Drzewo jest Lisciem class Lisc extends Drzewo { public $znak; function __construct($z,$w){ $this->znak = $z; $this->waga = $w; $this->znaki = array($z); } } // ... albo ma poddrzewa class Rozgalezione extends Drzewo { public $lewe; public $prawe; function __construct($podDrzewo_lewe, $podDrzewo_prawe, $z , $w){ $this->lewe = $podDrzewo_lewe; $this->prawe = $podDrzewo_prawe; $this->znaki = $z; $this->waga = $w; } } /* function nowe_Drzewo($lewe,$prawe) { $nowawaga = $lewe->waga + $prawe->waga; $noweznaki = array_merge($lewe->znaki, $prawe->znaki); return new Rozgalezione($lewe,$prawe, $noweznaki, $nowawaga); } function zamien_na_tablice($str){ //oprocz zmiany w tablice usuwamy spacje $str = str_replace(' ','',$str); return str_split($str); } /*nazwa sama sie wyjasnia wystapienia_w_tekscie : array[Char] -> array[(Char,Int)] */ function wystapienia_w_tekscie($tekst) { $wystapienia = array(); $dl = count($tekst); // ZAL TEKST JEST LISTA CHAR'OW for ($i = 0; $i < $dl ; $i++){ $litera = $tekst[$i]; $wystapienia[$litera] +=1; } return $wystapienia; } /* stworz_liste_Lisci_dla_znakow : array[(Char,Int)] -> array[drzewa] */ function stworz_liste_Lisci_dla_znakow( $wystapienia ) { usort($wystapienia); $a = array(); foreach ($wystapienia as $znak => $ile) { $Lisc_w_Liscie = new Lisc($znak,$ile); $a = array_merge($a,array($Lisc_w_Liscie)); } return $a; } /*to jest to samo co insert z insertion sort umiesc_w_odpowiednim_miejscu : drzewa x array[drzewa] -> array[drzewa] */ function umiesc_w_odpowiednim_miejscu($d , $a){ if ($a == array()) return array($d); else { $glowa = $a[0]; $ogon = array_slice($a,1); if ($glowa->waga <= $d->waga) return array_merge( array($glowa) , umiesc_w_odpowiednim_miejscu($d,$ogon)); else return array_merge( array($d), $a); } } /* konstruuj_z_drzew : array[drzewa] -> drzewa MOMENT - NAJWAZNIEJSZY POMYSL HUFFMANNA jesli mamy poszeregowane wzgl. czestosci znaki, to tworzymy Drzewo kodujace w nast sposob : - umieszczamy 'na dole' Drzewo scalone z Lisci o 2 najrzadziej wystepujace symbolach - rekurencyjnie stosujemy funkcje do reszty - doklejamy wyzej opisane Liscie */ function konstruuj_z_drzew($drzewa) { /* zakladamy ze drzewa sa wysortowane - funkcja stworz_liste_Lisci_dla_znakow sortuje wejscie, a ta funkcje bedziemy stosować do jej wyjscia */ if (length($drzewa) <= 1) return $drzewa; else { // TO WARTO SOBIE NARYSOWAC $d1 = $drzewa[0]; $d2 = $drzewa[1]; $dolne = $d1->nowe_Drzewo($d2) ; $reszta = array_slice($drzewa,2); umiesc_w_odpowiednim_miejscu($dolne,konstruuj_Drzewo_huffmana($reszta)); } } ?>
Output for 5.3.0 - 5.3.29, 5.4.0 - 5.4.45, 5.5.0 - 5.5.38, 5.6.0 - 5.6.28, 7.0.0 - 7.0.20, 7.1.0 - 7.1.10, 7.2.0 - 7.2.33, 7.3.12 - 7.3.33, 7.4.0 - 7.4.33, 8.0.0 - 8.0.30, 8.1.0 - 8.1.27, 8.2.0 - 8.2.17, 8.3.0 - 8.3.4

preferences:
219.44 ms | 404 KiB | 297 Q