/home/Śpiechu->Blog

Siedzę sobie w domu na urlo­pie i usku­tecz­niam to, co lubię najbar­dziej czyli progra­muję. Niektó­rzy lubią wyle­gi­wać się na plaży czeka­jąc aż czer­niak łaska­wie zawita na ich skórę, inni chodzą po zagra­nicz­nych targo­wi­skach i pilnują port­fela, a ja lubię siedzieć sobie wygod­nie przed kompu­te­rem cały dzień i dłubać.

Dzisiaj przed­mio­tem mojego dłuba­nia jest imple­men­ta­cja kole­jek prio­ry­te­to­wych w PHP, czyli SplHeap. Cała zabawa polega na tym że doda­jąc nowe elementy do kolejki zawsze mamy je posor­to­wane. Po prostu wrzu­camy i tyle — samo się robi :-) Mało tego, podczas wycią­ga­nia jakie­goś elementu możemy sobie doda­wać nowe i one też zajmują swoje miej­sca w hierar­chii ważności.

Posta­wi­łem sobie za cel zrobić mecha­nizm, który będzie mi sorto­wał ciągi znaków. Ponadto ma dać się nim stero­wać, czy np. liczby mają mieć pierw­szeń­stwo przed lite­rami oraz czy wiel­kie litery mają mieć pierw­szeń­stwo przed małymi. Powstało coś o ładnej nazwie SpiechuPriorityQueue i SpiechuStringComparator (skrom­ność przede wszystkim).

Najpierw kod klasy kolejki:

class SpiechuPriorityQueue extends SplHeap {
 
   private $stringComparator;
 
   public function __construct($ignoreCase = false, $numbersAtFront = true) {
      $this->stringComparator = new SpiechuStringComparator('PL',$ignoreCase,$numbersAtFront);
}
 
   public function insert($value,$priority = 0) {
      echo 'Dodaję: ' . $value . '<br/>';
      parent::insert($value);
}
 
   protected function compare($str1,$str2) {
      return $this->stringComparator->compare($str1, $str2);
}
 
   public function extract() {
      $extracted = parent::extract();
      echo 'Wyciągam: ' . $extracted . '<br/>';
      return $extracted;
   }
}

Mamy tutaj kilka tajem­ni­czych zagrań:

1. na etapie tworze­nia obiektu kolejki możemy usta­lić para­me­try sortowania,
2. całą robotę odwala za nas SpiechuStringComparator,
3. nie da się usta­lać ręcz­nie prio­ry­te­tów w meto­dzie insert (ręczne mody­fi­ka­cje popsu­łyby nasz mecha­nizm sortujący),
4. wyma­gane jest prze­sło­nię­cie metody compare, którą SplHeap sam sobie wywo­łuje tworząc hierar­chię elemen­tów w środku

Zapewne pojawi się pyta­nie jak tego używać. Dosyć prosto:

$queue = new SpiechuPriorityQueue();
 
$queue->insert('ABC');
$queue->insert('CBA');
$queue->extract();
$queue->insert('ABW');
$queue->insert('NKOTB');
$queue->extract();
$queue->insert('1Pierwszy');
$queue->extract();
$queue->insert('2Drugi');
$queue->insert('3Ostatni');
$queue->extract();
$queue->insert('abc');
$queue->insert('abCadabra');
 
echo '---pozostałe---<br>';
 
while($queue->valid()) {
   $queue->extract();
}
?>

Widać powy­żej, że prze­pla­tamy doda­wa­nie i wycią­ga­nie elemen­tów. Na koniec spraw­dzamy czy coś jest w kolejce i wyciągamy.

Co zwróci nam powyż­sze wywo­ła­nie kodu? Domyśl­nie kolejka nie igno­ruje małych i dużych liter oraz stawia liczby jako ważniej­sze od liter. Otrzy­mamy:
Dodaję: ABC
Dodaję: CBA
Wyciągam: ABC
Dodaję: ABW
Dodaję: NKOTB
Wyciągam: ABW
Dodaję: 1Pierwszy
Wyciągam: 1Pierwszy
Dodaję: 2Drugi
Dodaję: 3Ostatni
Wyciągam: 2Drugi
Dodaję: abc
Dodaję: abCadabra
---pozostałe---
Wyciągam: 3Ostatni
Wyciągam: abCadabra
Wyciągam: abc
Wyciągam: CBA
Wyciągam: NKOTB
Jeżeli zigno­ru­jemy wiel­kość liter, a liczby usta­wimy jako mniej ważne od liter to otrzy­mamy:
Dodaję: ABC
Dodaję: CBA
Wyciągam: ABC
Dodaję: ABW
Dodaję: NKOTB
Wyciągam: ABW
Dodaję: 1Pierwszy
Wyciągam: CBA
Dodaję: 2Drugi
Dodaję: 3Ostatni
Wyciągam: NKOTB
Dodaję: abc
Dodaję: abCadabra
---pozostałe---
Wyciągam: abc
Wyciągam: abCadabra
Wyciągam: 1Pierwszy
Wyciągam: 2Drugi
Wyciągam: 3Ostatni
Fajne, co?

Mecha­nizm sorto­wa­nia zrobi­łem od zera sam. Dostępny jest tutaj. Może­cie sobie robić z nim co chce­cie (pod warun­kiem napi­sa­nia pozy­tyw­nego komen­ta­rza pod wpisem i ewen­tu­al­nym klik­nię­ciem na „Lubię to” :-) ). Komen­to­wa­łem po angiel­sku (trochę zwięk­szę tym audy­to­rium, a Wam zapewne nie zrobi różnicy).

Podobne wpisy:

1. Weź mi zrób proce­sor tekstu cz. 1 / 2
2. MySQL, PDO i proce­dury składowane
3. 3 wzorce projek­towe w ok. 100 liniach kodu PHP
4. Bezstratna opty­ma­li­za­cja plików JPG