DunLog

Když jsem vyvíjel NORS 3, musel jsem řešit, jak napsat co nejlépe algoritmus, který vytvoří vazby mezi komentáři.

Pokud nevíte, co tím myslím, trochu to přiblížím: když někdo chce reagovat na nějaký komentář, klikne na odkaz Odpovědět, který vloží do pole Text např. [1]. Nebo to může udělat ručně.

A já jsem potřeboval napsat algoritmus, který zjistí tyto vazby mezi komentáři a přidá k nim texty: "reakce na ..." a "tento komentář inspiroval...". Samozřejmě jsem také potřeboval, aby měl tento algoritmus co možná nejmenší složitost, tedy ne nějakou O(2^N).

Chvíli popřemýšlejte, jak byste to řešili a pak schválně porovnejte s mým řešením. O(2N).

//$q3 je objekt ktery obsahuje odkaz na MySQL resource
//$q3->fetch() vraci pole jako fce mysql_fetch_array

while($kom = $q3->fetch()){
    $komentar[$i] = clear_comment($kom); //odstrani vsechny nebezpecnosti
    
    if(eregi("[([[:digit:]]+)]",$komentar[$i]['text'])){  //obsahuje komentar [x]?
      $j = eregi_replace(".*[([[:digit:]]+)].*","1",$komentar[$i]['text']); //ziskani cisla
      if($i>$j){ //pouze pokud reaguje na starsi komentare
        $reakce[$i][]=$j;
        $inspirace[$j][]=$i;
      }
    }
    $i++;
  }   
if(is_array($komentar)){
    $i = 1;
    foreach($komentar as $key=>$value){
      $kom = $value;
      $kom['text'] = eregi_replace("[([[:digit:]]+)]","",$kom['text']); //odstraneni [x]
      echo '<div class="komentar" id="post'.$kom['id_komentar'].'">';
      echo '<div class="autor">';
      echo '[<a href="'.GenUrl(array('show'=>'clanek','id'=>$line['link'])).'#post'.$komentar[$i]['id_komentar'].'" title="permanent link">'.$i.'</a>]';
      
      if($kom['web']) echo ' <a href="'.$kom['web'].'"> '.stripslashes($kom['user']).'</a>';
      elseif($kom['mail']) echo ' <a href="mailto:'.crypt_mail($kom['mail']).'"> '.stripslashes($kom['user']).'</a>'; 
      else echo ' '.stripslashes($kom['user']);
      
      echo ' - '.$kom['date'].'</div>';
      echo '<div><img class="right" src="http://www.gravatar.com/avatar.php?gravatar_id='.md5(trim($value['mail'])).'&rating=PG&size=30&default='.$SETTINGS['URL'].'images/gravatar.gif" />';
      
      if($reakce[$i]){
        foreach($reakce[$i] as $reakce1)
        echo '<div class="reakce">Reakce na <a href="'.GenUrl(array('show'=>'clanek','id'=>$line['link'])).'#post'.$komentar[$reakce1]['id_komentar'].'">['.$reakce1.'] '.$komentar[$reakce1]['user'].'</a></div>';
      }
      
      echo paragraph(stripslashes($kom['text']),1); //formatovani a vypis textu
      
      echo '<div class="odpoved"><a href="javascript:addtag('['.$i.']');document.getElementById('f').text.focus();">Odpovědět</a>';
      
      if($inspirace[$i]){
        foreach($inspirace[$i] as $inspirace1)
        echo '<div class="inspirace">Na tento komentář odpověděl <a href="'.GenUrl(array('show'=>'clanek','id'=>$line['link'])).'#post'.$komentar[$inspirace1]['id_komentar'].'">['.$inspirace1.'] '.$komentar[$inspirace1]['user'].'</a></div>';
      }
      
      echo '</div></div></div>';
      $i++;
    }
  }