Strukturovaná diskuse pod články – praxe

18. srpna 2005

•

V předchozím článku jsem teoreticky vysvětlil algoritmy pro tvorbu diskusí po články. V tomto článku již naleznete hotové řešení, které si můžete stáhnout a využít na vlastním webu.

Výstavba pole následníků

Pokud si vzpomínáte na mé vysvětlení z předchozího článku, jedná se v podstatě o přepis matice do jednorozměrného pole. Musíme si tedy pomyslně to jednorozměrné pole rozdělit na úseky, přičemž každý úsek bude odpovídat jednomu řádku původní matice. K tomu ale potřebujeme zjistit délky těchto řádků, respektive úseků (je samozřejmé, že nebudeme přepisovat prázdná políčka).

Za tímto účelem si vytvoříme pomocné pole, kde hodnota n-tého prvku zastupuje počet následníků n-tého příspěvku. Toto pole naplníme jednoduše během jediného průchodu polem, ve kterém máme uloženy předchůdce jednotlivých příspěvků. Například má-li prvek číslo „5“ předchůdce číslo „1“ – počet následníků příspěvku „1“ navýšíme o jedna.

Vyřešili jsme tedy délky úseků, ale sami vidíte, že tím jsme jen v půlce cesty. U každého úseku totiž kromě jeho délky potřebujeme znát i místo, kam patří. Vezměme v úvahu situaci, kdy máme nějaký úsek délky „n“ a počáteční bod v poli je „k“. Otázka zní – kde začíná další úsek? Představíte-li si tu situaci, vidíte, že tento úsek skončí po n prvcích a protože začal na k-tém prvku, bude mít poslední prvek tohoto úseku číslo n+k-1. Z toho jasně plyne, že první prvek následujícího úseku má číslo n+k. A takto získáme do druhého pomocného pole počátky těchto úseků. Pokud třeba první úsek začne na místě „0“ a bude mít délku „3“, začne druhý úsek na místě „3“. Bude-li druhý úsek délky „2“, začne třetí úsek na místě „5“. Tento popis si projděte velmi pečlivě, je stěžejní pro pochopení způsobu ukládání do pole.

Tím jsme opracovali poslední stavební kámen nutný k vybudování pole následníků. Uchopme si nyní nějaký příspěvek. Známe jeho předchůdce, takže víme, do kterého úseku budeme ukládat. Abychom si to zjednodušili, uložíme ho na první volné místo v tomto úseku. Jak ale zjistit, kde takové místo je? Na počátku víme, kde úsek začíná (tuto hodnotu máme uloženou v pomocném poli), je tedy snadné toto místo najít. Pak ale není problém navýšit tento index o jedna a toto zopakovat vždy po přidání dalšího následníka do pole.

Příklad: Úsek následníků příspěvku „3“ začíná na políčku „10“. Přidám-li následníka tohoto příspěvku, změním toto číslo na „11“, po přidání dalšího na „12“ a tak dále. Kde bereme jistotu, že se takto nedostaneme do dalšího úseku? Protože počty následníků se od minulého průchodu nezměnily a my jsme velikosti úseků volili s ohledem na počty následníků, můžeme si být nyní jisti, že je tento postup korektní.

Asi si ale pamatujete, že potřebujeme, aby zároveň byly jednotlivé příspěvky v úsecích setříděny podle toho, kdy přišly do diskuse. Tady musí zapracovat nějaké požadavky na vstupní data. Pokud příspěvek A přišel dříve než příspěvek B, pak platí, že index(A)<index(B), jinými slovy, čím vyšší číslo příspěvku, tím později byl příspěvek vytvořen.

Nyní stačí pouze šikovně (tedy ve správném pořadí) postupovat při naplňování pole následníků. Rozmyslete si, co se stane, když půjdeme od příspěvku s nejmenším indexem až po největší. Pokud si vezmeme nějaký úsek, bude do něj nutně uložen nejprve článek s nejmenším indexem (díky pořadí vyhodnocení prostě přijde první na řadu). A díky naší podmínce odpovídá tento výsledek požadavku, aby nejprve byly uloženy příspěvky, které přišly dříve.

Nakonec ještě zopakujeme zjištění počátků úseků (toto pole jsme si rozházeli při tvorbě pole následníků), protože je budeme potřebovat k nalezení následníků daného prvku. Vždy se podíváme, kde daný úsek začíná, a potom projdeme právě tolik prvků, kolik má daný prvek následníků, například pomocí cyklu for.

Možná si teď říkáte, co se stane s prvky, které nemají žádné následníky. V poli následníků jim přece byl přiřazen počátek úseku a navíc na tom místě bude mít následníka někdo jiný! To je samozřejmě pravda a nikde není ani zmínka o řešení. V našem případě totiž není co řešit. Když projdeme následníky daného prvku (kterých je v tomto případě „0“), tak vlastně neprojdeme nic, protože uděláme nula kroků, a není tedy třeba žádné dodatečné podmínky.

Třída `clsDiscussion_sort`

Můžeme se pustit do tvorby třídy, která ztělesňuje výše popsaný algoritmus. Nejprve si vezmeme z tabulky, kde jsou uloženy příspěvky, všechna data, která potřebujeme. Jedná se o index příspěvku a jeho rodiče, pro zajímavost navíc ještě samotný text příspěvku a jeho autora (pozor, proměnná $_GET[id] je v tomto případě číslo článku, ke kterému se příspěvky vztahují):

$query=MySQL_Query(„SELECT id, parent_id, text, jmeno FROM prispevky WHERE article_id=’$_GET[id]‘ ORDER BY date“);

Možná jste si všimli jednoho problému, který jsme zatím neřešili. Většinou máme v jedné tabulce příspěvky všech článků dohromady. To tedy znamená, že jeden článek nemá příspěvky s indexy „1“ až „10“, ale může mít třeba 2,5,6,8. Náš algoritmus ale předpokládá pouze čísla „1“ až „n“, která jdou za sebou. Řešením je převodní tabulka, která převede řadu 1,3,5,8 na požadovanou 1,2,3,4.

//zjistíme si počet příspěvků
$dis_count=MySQL_Num_Rows($query);
$id2n[0]=0;
While ($data = MySQL_Fetch_Array($query)){
  $p++;
  $id2n[$data[id]]=$p;
  $unsort_data[$p]=$data;
}
for ($q=1;$q<=$dis_count;$q++) {
  //pole rodičů
  $data=$unsort_data[$q];
  $parent_list[$q]=$id2n[$data[parent_id]];
}

Nyní nám již nic nebrání aplikovat naši třídu na takto vytvořené pole příspěvků.

$Discussion_sort= new clsDiscussion_sort($parent_list);

A je na čase vysvětlit si, co nám třída vrátí a jak s ní zacházet. Naším cílem bylo vytvořit takové pole, ze kterého bude možné určit pořadí příspěvků. Zároveň nám šlo o to, abychom u každého příspěvku mohli určit i jeho odsazení. Pořadí příspěvků nalezneme v poli $Discussion_sort->Order[$i], kde $i je rovno „1“ až „n“. Hodnoty jsou vždy indexy příspěvků. Odsazení jednotlivých příspěvků jsou uložena v poli $Discussion_sort-gt;Indentation[$index], kde $index je index prvku a hodnotou je odsazení. Základní použití včetně převodní tabulky by tedy bylo takové:

for ($i=1;$i<=$Discussion_sort->Count;$i++) {
  $data=$unsort_data[$Discussion_sort->Order[$i]];
  $odsazeni=100; //odsazení příspěvků mezi sebou v pixelech;
  $indentation=$Discussion_sort->Indentation[$Discussion_sort->Order[$i]]*$odsazeni-$odsazeni;
  $diskuse.=“<div class=’spot‘ style=’margin-left:“.$indentation.“px‘>“;
  $diskuse.=“ <div class=’jmeno‘>$data[jmeno]</div>“;
  $diskuse.=“ <div class=’text‘>$data</div>“;
  $diskuse.=“</div>“;
}

Základem třídy jsou dvě funkce – Zanor() a Main. Vysvětlení celého algoritmu jsme si již provedli, proto jsou v kódu jen krátké komentáře:

class clsDiscussion_sort {
  //kontruktor třídy, parametrem je pole příspěvků
  function clsDiscussion_sort($dis_array) {
    global $vysl,$pocty,$N,$pred;
    $pred=$dis_array;
    $N=count($pred);
    $this->Main();
    $this->Count=$N;
    $this->Order =$vysl; //pořadí
    $this->Indentation =$pocty; //odsazení
  }
  function zanor($akt){
    global $pred,$poc,$por,$pocty,$vysl,$index,$N;
    //prochazeni do hloubky
    $vysl[$index++]=$akt;
    for($i=0;$i<$pocty[$akt];$i++){
      $this->zanor($por[$poc[$akt]+$i]);
    };
  }
  function Main() {
    global $pred,$poc,$por,$pocty,$vysl,$index,$N;
    //pripravi pomocna pole pro rekurzi
    for($i=0;$i<=$N;$i++)
      $pocty[$i]=$por[$i]=0;
    //zjisteni poctu nasledniku
    for($i=1;$i<=$N;$i++)
      $pocty[$pred[$i]]++;
    $poc[0]=0;
    for($i=1;$i<=$N;$i++)
      $poc[$i]=$poc[$i-1]+$pocty[$i-1]; //pocatky v poli
    //ulozeni nasledniku do pole
    for($i=1;$i<=$N;$i++)
      $por[$poc[$pred[$i]]++]=$i;
    $poc[0]=0;
    for($i=1;$i<=$N;$i++)
      $poc[$i]=$poc[$i-1]+$pocty[$i-1]; //pocatky v poli
    $index=0;
    $this->zanor(0);
    //v tuhle chvili jsou ve $vysl ulozena cisla prispevku tak jak je budeme vypisovat
    //Zjisteni odsazeni;
    $pocty[0]=0; //0-ty prvek je vsude jen jakysi pomyslny,pomocny
    pocatek stromu
    for ($i=1;$i<=$N;$i++)
      $pocty[$i]=$pocty[$pred[$i]]+1;
  }
}

Věřím, že se vám podobný algoritmus bude hodit. Třídu můžete využít nejen pro diskuse pod články, uplatnění najde například i v různých diskusních fórech.

Samozřejmě si můžete stáhnout zdrojový kód a použít ho pro vlastní potřebu.