Práce se stromovou strukturou - Jet\Data_Tree

Práce s daty uspořádaných ve stromové struktuře je v našem oboru dosti častá věc. Však co jsou takové kategorie e-shopu, sekce intranetu, sekce portálu a spousta dalších věci - vše jsou to data uspořádaná do stromu. Tedy mající nějaký kořen a pak uzly (větve), pod které spadají uzly potomků a tak dále. Tímto pomyslným stromem je nutné procházet, hledat rodiče, potomky, cesty k uzlu, nebo strom zobrazovat / vypisovat. Jsou to časté operace a proto má Jet k tomu potřebný nástroj, který je využíván nejen platformou samotnou, ale je dobře využitelný i v aplikačním prostoru - sám jej používám často.

Stromová data - obecně

Aby data (a je jedno zda asociované pole, nebo instance objektů - podporováno je obojí) mohla být uspořádána do stromové struktury, tak musí splňovat několik jednoduchých pravidel:

  • Každá položka (budoucí uzel) musí mít vlastní a jednoznačný identifikátor
    Je jedno zda se bude jednat o číslo, nebo řetězec. Důležitá je unikátnost. Nesmí existovat dva uzly (větve) se stejným identifikátorem.
  • Každá položka musí mít identifikátor rodičovské větve - nadřazeného uzlu
    Data by měla být konzistentní. To znamená, že pokud má uzel identifikátor rodičovského uzlu třeba 432, pak uzel s tímto identifikátorem musí existovat. V opačném případě je identifikována nekonzistence dat a je vyhozena výjimka.
    Taková situace se dá řešit přepnutím stromu do režimu adopce, nebo ignorace sirotků - viz dále. Ovšem neměl by to být standardní postup, je normální dbát na konzistenci dat.
  • Každá položka by měla mít textový název (čitelný pro člověka - uživatele)
    Tomu budeme říkat label uzlu a je možné s ním pracovat například na úrovni UI.
  • Data by měla být seřazena
    Určitě je nutné seřadit si dopředu data dle jejich priority (ta může být určena čímkoliv - například abecedním pořadím, či nějakým indexem) tak jak budou seřazeny v jednotlivých větvích. A pro rychlost je také dobré seřadit data podle identifikátoru rodiče (to není nutné, ale určitě vhodné). Ideální data budou tedy seřazena: 1. podle identifikátoru rodiče, 2. v rámci toho podle priority, kterou určíte vy.
  • Každý uzel může mít libovolná další data
    Ať už jde o objekty, či asociovaná pole, uzel sebou může (a má) nést další data a informace. V praxi se ale nedoporučuje mít u uzlů takových metadat mnoho. Dejme tomu, že máte e-shop s tisíci kategoriemi a každá ta kategorie má spoustu informací včetně dlouhých textových popisků. Taková data dávat do stromu nedoporučuji. Znamená to velkou spotřebu paměti, velké datové přesuny a tak dále. Ovšem nezbytné metainformace ve stromu lze mít - od toho strom je.

Vytvoření stromu z pole

Vytvoření stromu z pole je v praxi nejtypičtější operace. Jde často u zpracování surových dat načtených z databáze, z keše, či jiného úložiště. Pojďme si tedy ukázat jak na to. Z předchozí části víte co musí data splňovat.

Nyní si ukážeme jak to provést v praxi a použijeme příklad z "vnitřností" Jetu a to sestavení MVC stránek do stromové struktury. Informace o jedné stránce - o budoucím uzlu stromové struktury - má tyto klíče:

  • id
  • parent_id
  • name
Seznam takových asociovaných polí je načten (což v příkladu řešit nebudeme, ale data jsou pro ukázku deklarována) a můžeme vyrobit strom:

$tree_data[] = [
    'id' => 'page-1',
    'parent_id' => MVC::HOMEPAGE_ID,
    'name' => 'Page 1'
];

$tree_data[] = [
    'id' => 'page-1-1',
    'parent_id' => 'page-1',
    'name' => 'Page 1-1'
];

$tree_data[] = [
    'id' => 'page-1-2',
    'parent_id' => 'page-1',
    'name' => 'Page 1-2'
];
$tree_data[] = [
    'id' => 'page-2',
    'parent_id' => MVC::HOMEPAGE_ID,
    'name' => 'Page 2'
];

uasort( $tree_data, function( array $a, array $b ) {
    return strcmp( $a['name'], $b['name'] );
} );
    
$tree = new Data_Tree();
        
$root = $tree->getRootNode();
$root->setId( MVC::HOMEPAGE_ID );
$root->setLabel( 'Homepage' );
        
$tree->setData( $tree_data );

Všimněte si prosím, že jsou nastavovány parametry kořenového uzlu. Kořenový uzel existuje vždy automaticky. Jeho identifikátor je ve výchozím stavu prázdná hodnota. Tedy jakýkoliv uzel nemá identifikátor rodiče, tak spadá automaticky pod kořenový uzel. Ovšem v tomto případě je identifikátor kořenového uzlu nastaven. Rovněž je nastaven label kořenového uzlu.

Metoda setData uspořádá data do stromové struktury a je možné se stromem dále pracovat - což si ukážeme později. Pokud jsou data nekonzistentní, je vyhozena výjimka Jet\Data_Tree_Exception.

Jak již bylo řečeno, tak stromová data musí mít identifikátor (klíč pole 'id'), identifikátor rodiče (klíč pole 'parent_id') a label (klíč pole 'name'). Ovšem názvy klíčů pole nejsou pevně dány. Toto jsou pouze výchozí hodnoty. Parametry konstruktoru a příslušnými metodami (viz níže) můžete názvy těchto klíčů změnit dle vašich potřeb.

Vytvoření stromu ze seznamu objektů

Někdy může být vhodnější a potřebné vytvořit strom ze seznamu objektů. Seznamem se myslí buď prosté pole obsahující objekty, nebo nějaký iterátor objekty vracející při průchodu. Princip je v jádru totožný jako při práci s poli. Je však pochopitelně několik odlišností:

  • Místo metody setData je nutné použít metodu setDataSource, které je předán seznam objektů a třída Data_Tree se automaticky přepne do režimu používání objektů místo asociovaného pole.
  • Objekty musí mít příslušné metody - gettery pro předání potřebných informací:
    • getId - vrací identifikátor uzlu
    • getParentId - vrací identifikátor rodičovského uzlu
    • getName - vrací label uzlu
    Metody musí existovat, ale jejich název není povinný. Pomocí příslušných metod (viz níže) je možné názvy potřebných metod objektů změnit. Pochopitelně je nutné to udělat před použitím metody setDataSource.

Nekonzistentní strom

Jak již bylo uvedeno, tak data stromu by měla být konzistentní, jinak při jeho inicializaci dochází k vyhození výjimky. Ovšem svět není dokonalý ... Může se stát, že prostě potřebujeme pracovat s nekonzistetními daty (například když z prostředka strom "zmizel" uzel, ale jeho potomci stále existují). Situace je řešitelná.

Před inicializací stromu je nutné jej přepnout do režimu adopce:

$tree = new Data_Tree();
$tree->setAdoptOrphans( true );

Uzly bez rodiče jsou v takovém režimu zařazeny pod kořenový uzel. Ve stromy tedy budou figurovat alespoň provizorně.

Druhou možností je sirotky prostě ignorovat a do stromu je vůbec nezařadit:

$tree = new Data_Tree();
$tree->setIgnoreOrphans( true );

Co konkrétně použít je na posouzení konkrétní situace a na vašem rozhodnutí. Jet sám o sobě nemůže určit které řešení je správné, proto si vynucuje volbu od vás.

Použití stromu

Uzel stromu

Strom je tvořen jednotlivými uzly - jak jsme si již řekli. A právě s uzly se bude dále pracovat. Pojďme se tedy kouknout co přesně uzel je. Uzel stromu je instance třídy Jet\Data_Tree_Node. Nese všechny potřebné informace o uzlu a takový objekt je stromem i vracen při práci s ním - při procházení stromu, hledání a tak dále.

Bylo řečeno, že uzel je objekt třídy Jet\Data_Tree_Node. Ovšem to je pravda jen částečně. Pomocí příslušné metody třídy Data_Tree (viz níže) můžete vnutit použití své vlastní třídy pro uzel stromu (pochopitelně před jeho naplněním daty). Tedy můžete si udělat vlastní uzel. Jedinou podmínkou je, že od třídy Jet\Data_Tree_Node musí dědit.

Získání uzlu

To je naprosto základní operace. Na základě jedinečného identifikátoru lze snadno získat instantici uzlu ať se nalézá kdekoliv ve struktuře stromu: $node = $tree->getNode( 'page-1-2' ); Pozor! Může se stát, že uzel neexistuje. V takovém případě je vrácena hodnota null a je tedy nutné s touto eventualitou počítat.

Rodiče, potomci a cesty

Když už máme k dispozici uzel, tak s ním můžeme dále pracovat. Například získat jeho rodicě, nebo naopak potomky:

$parent = $node->getParent();
foreach($node->getChildren() as $child) {
    //... ... ..
}

Nebo je možné získat cesty. Například víte, že existuje určitý uzel, ale potřebujete vědět jaká je k němu cesta. Tedy potřebujete seznam identifikátorů všech jeho rodičovských uzlů: $parent_ids = $tree->getPath( 'page-1-2' );

Prosté procházení stromem

Strom můžete velice snadno projít jako by se jednalo o jednoduchý seznam. Tedy projít postupně všechny uzly od kořenu po poslední uzel s tím, že procházení bude plně reflektovat uspořádání stromu. Není nutné pro to používat žádné rekurzivní funkce, ale stačí pouhý cyklus:

foreach( $tree as $node ) {
    echo 'Node ID: '.$node->getId().PHP_EOL;
    echo 'Parent node ID: '.$node->getParentId().PHP_EOL;
    echo 'Label: '.$node->getLabel().PHP_EOL;
    echo 'Depth: '.$node->getDepth().PHP_EOL;
}

... a tak dále

Nyní již znáte princip jak se s Jet\Data_Tree pracuje. Dále prosím koukněte na seznam metod třídy Jet\Data_Tree a také na seznam metod třídy Jet\Data_Tree_Node. Tam získáte další informace a kompletní přehled o možnostech Data_Tree.

Seznam metod

Metoda Význam
public __construct(
string $id_key='id',
string $parent_id_key='parent_id'
)		 Konstruktor umožňuje rovnou nastavit nejzákladnější parametry a to název klíč pole reprezentující identifikátor a název klíče pole reprezentující identifikátor rodiče.
public getNodesClassName(
) : string		 Vrací název třídy, která bude představovat uzel stromu.
public setNodesClassName(
string $nodes_class_name
) : void		 Nastavuje název třídy, která bude reprezentovat uzel stromu.

Je nutné nastavit ještě před naplnění stromu daty.

Třída musí dědit od Jet\Data_Tree_Node.
public getAdoptOrphans(
) : bool		 Indikuje zda je zapnutý režim adopce sirotků.

Je nutné nastavit ještě před naplnění stromu daty.

Výchozí stav je: vypnuto
public setAdoptOrphans(
bool $adopt_orphans
) : void		 Zapíná / vypíná režim adopce sirotků.
public getIgnoreOrphans(
) : bool		 Indikuje zda je zapnutý režim ignorování sirotků.

Je nutné nastavit ještě před naplnění stromu daty.

Výchozí stav je: vypnuto
public setIgnoreOrphans(
bool $ignore_orphans
) : void		 Zapíná / vypíná režim ignorování sirotků.

Je nutné nastavit ještě před naplnění stromu daty.
public getIdKey(
) : string		 Vrací název klíče pole reprezentujícího identifikátor uzlu.

Výchozí hodnota je: 'id'
public setIdKey(
string $id_key
) : void		 Nastavuje název klíče pole reprezentujícího identifikátor uzlu.

Je nutné nastavit ještě před naplnění stromu daty.
public getParentIdKey(
) : string		 Vrací název klíče pole reprezentujícího identifikátor rodičovského uzlu.

Výchozí hodnota je: 'parent_id'
public setParentIdKey(
string $parent_id_key
) : void		 Nastavuje název klíče pole reprezentujícího identifikátor rodičovského uzlu.

Je nutné nastavit ještě před naplnění stromu daty.
public getLabelKey(
) : string		 Vrací název klíče pole reprezentujícího label uzlu.

Výchozí hodnota je: 'name'
public setLabelKey(
string $label_key
) : void		 Nastavuje název klíče pole reprezentujícího label uzlu.

Je nutné nastavit ještě před naplnění stromu daty.
public getIdGetterMethodName(
) : string		 Vrací název metody vracející identifikátor uzlu v režimu práce s objekty.

Výchozí hodnota: 'getId'
public setIdGetterMethodName(
string $id_getter_method_name
) : void		 Nastavuje název metody vracející identifikátor uzlu v režimu práce s objekty.

Je nutné nastavit ještě před naplnění stromu daty.
public getParentIdGetterMethodName(
) : string		 Vrací název metody vracející identifikátor rodičovského uzlu v režimu práce s objekty.

Výchozí hodnota: 'getParentId'
public setParentIdGetterMethodName(
string $parent_id_getter_method_name
) : void		 Nastavuje název metody vracející identifikátor rodičovského uzlu v režimu práce s objekty.

Je nutné nastavit ještě před naplnění stromu daty.
public getLabelGetterMethodName(
) : string		 Vrací název metody vracející label uzlu v režimu práce s objekty.

Výchozí hodnota: 'getName'
public setLabelGetterMethodName(
string $label_getter_method_name
) : void		 Nastavuje název metody vracející label uzlu v režimu práce s objekty.

Je nutné nastavit ještě před naplnění stromu daty.
public setData(
array $data
) : void		 Naplní a inicializuje strom s tím, že data jsou tvořena asociovanými poly.
public setDataSource(
Iterator|array $data
) : void		 Naplní a inicializuje strom s tím, že data jsou tvořena objekty a automaticky tak zapíná režim práce s objekty.
public getRootNode(
) : Data_Tree_Node|null		 Vrací kořenový uzel, který je možné dále nastavit.
public setRootNode(
Data_Tree_Node $node
) : void		 Vnucuje kořenový uzel z venčí.

Je nutné nastavit ještě před naplnění stromu daty.
public appendNode(
array|object $item_data
) : Data_Tree_Node|null		 Přidává uzel. Přidávaný uzel má podobu surových dat. To znamená asociovaného pole, nebo objektu (v režimu práce s objekty).

Vrací instanci vytvořeného uzlu.

Používá se po naplnění stromu daty.
public getNode(
string $node_id
) : Data_Tree_Node|null		 Vrací instanci uzlu reprezentovaného daným identifikátorem bez ohledu na umístění uzlu ve stormové struktuře. Vrací null pokud uzel neexistuje.
public getNodes(
) : Data_Tree_Node[]		 Vrací instance všech uzlů ve stromu.
public getNodesIds(
) : array		 Vrací identifikátory všech uzlů ve stromu.
public getNodeExists(
string $node_id
) : bool		 Indikuje zda uzel s daným identifikátorem ve stromu existuje.
public getPath(
string $target_node_id
) : array|bool		 Hledá cestu k danému uzlu a vrací jí v podobě pole všech identifikátorů rodičovských uzlů včetně uzlů hledaného seřazených chronologicky od kořene po hledaný uzel.
public toJSON(
) : string		 Exportuje strom do formátu JSON.
public jsonSerialize(
) : array		 Umožňuje předat instanci stromu funkci json_encode.
public toArray(
) : array		 Exportuje storm do pole ovšem s tím, že je respektováno zanoření a uspořádání stromu. Tedy nejde o pouhý zpětný export uzlů do pole, ale výsledné pole představuje stromovou strukturou.
public getChildrenKey(
) : string		 Pro účel exportů (toJSON, toJSON a toArray)

Vrací jaký klíč reprezentuje potomky uzlu v exportovaných datech.

Výchozí hodnota: 'children'
public setChildrenKey(
string $children_key
) : void		 Pro účel exportů (toJSON, toJSON a toArray)

Nastavuje jaký klíč reprezentuje potomky uzlu v exportovaných datech.
public getDepthKey(
) : string		 Pro účel exportů (toJSON, toJSON a toArray)

Vrací jaký klíč reprezentuje hloubku uzlu v exportovaných datech.

Výchozí hodnota: 'depth'
public setDepthKey(
string $depth_key
) : void		 Pro účel exportů (toJSON, toJSON a toArray)

Nastavuje jaký klíč reprezentuje hloubku uzlu v exportovaných datech.
public rewind(
) : void		 Viz PHP Iterator
public current(
) : Data_Tree_Node		 Viz PHP Iterator
public key(
) : string		 Viz PHP Iterator
public next(
) : void		 Viz PHP Iterator
public valid(
) : bool		 Viz PHP Iterator
public count(
) : int		 Viz PHP Countable
Předchozí kapitola
Práce s textem - Jet\Data_Text
Další kapitola
Jet\Data_Tree_Node
GitHub