Web Majster - triki i rozwiązania: Rekurencja

niedziela, 16 września 2012

Generowanie struktury drzewiastej do testów

Jak wygenerować tablicę, która będzie reprezentować strukturę drzewiastą?

Pomocna będzie funkcja do generowania losowych wartości tekstowych:

function randomText(){
 $ch = range('a', 'z');
 $count = count($ch);
 $length = rand(5, 10);
 $text = '';
 
 for($i=0; $i < $length; $i++){
  $text .= $ch{rand(0, $count-1)};
 }
 
 return $text;
}

Utwórzmy klasę Tree, która będzie miała trzy prywatne właściwości określające wygenerowane drzewo, liczbę poziomów drzewa oraz liczbę gałęzi na każdym poziomie.
Do metody Tree::makeTree() przekazujemy wartości, które określą nam wielkość drzewa.
W końcu generujemy rekurencyjnie drzewo w prywatnej metodzie Tree::_makeTree(). Wartości przekazywane do tej metody to aktualny poziom, numer gałęzi na poziomie oraz numer węzła w drzewie, tzn. klucz w tablicy rodzica.

class Tree{
 private $tree; // wygenerowane drzewo
 private $levels; // liczba poziomów drzewa
 private $branches; // liczba gałęzi na każdym poziomie
 
 public function makeTree($levels, $branches){
  $this->tree = array();
  $this->levels = $levels;
  $this->branches = $branches;
  
  $this->_makeTree();
 }
 
 private function _makeTree($level = 0, $branch = 0, $id = null){
  if ($level > $this->levels) {
   return;
  }
  
  $this->tree[] = array('value' => randomText(), 'parent' => $id);
  
  end($this->tree);
  $id = key($this->tree);
  
  for($i=0; $i < $this->branches; $i++) {
   $this->_makeTree($level+1, $i, $id);
  }
 }
 
 public function getTree(){
  return $this->tree;
 } 
}

Aby wartości w drzewie miały za każdym razem takie same wartości, można ustawić generator liczb losowych.

srand(0);
$t = new Tree();
$t->makeTree(3,2);
var_dump($t->getTree());

Te ustawienia wygenerują tablicę o tej strukturze:

array
  0 => 
    array
      'value' => string 'eifefuq' (length=7)
      'parent' => null
  1 => 
    array
      'value' => string 'yknjklv' (length=7)
      'parent' => int 0
  2 => 
    array
      'value' => string 'fovima' (length=6)
      'parent' => int 1
  3 => 
    array
      'value' => string 'rtnuteg' (length=7)
      'parent' => int 2
  4 => 
    array
      'value' => string 'miagkiylls' (length=10)
      'parent' => int 2
  5 => 
    array
      'value' => string 'xbpvmgosn' (length=9)
      'parent' => int 1
  6 => 
    array
      'value' => string 'tqwrsjw' (length=7)
      'parent' => int 5
  7 => 
    array
      'value' => string 'ocjmxpr' (length=7)
      'parent' => int 5
  8 => 
    array
      'value' => string 'uarkvdrq' (length=8)
      'parent' => int 0
  9 => 
    array
      'value' => string 'coehs' (length=5)
      'parent' => int 8
  10 => 
    array
      'value' => string 'nkdupaci' (length=8)
      'parent' => int 9
  11 => 
    array
      'value' => string 'hvcjublmpy' (length=10)
      'parent' => int 9
  12 => 
    array
      'value' => string 'gihucb' (length=6)
      'parent' => int 8
  13 => 
    array
      'value' => string 'zzkpck' (length=6)
      'parent' => int 12
  14 => 
    array
      'value' => string 'nbjtsdg' (length=7)
      'parent' => int 12