Nested set v Doctrine 2

Nested set v Doctrine 2

Doctrine 2 a její Gedmo\Tree extenze v2.3 obsahuje hned několik možností pro manipulaci s hierarchickými (stromovými) strukturami dat. Pojďme se podívat na efektivní vytváření tzv. „nested set“ struktury a operace užitečné pro manipulaci se stromem a jeho větvemi.

Teorie nested set je zajímavá, ale budeme věnovat praktickému použití. Máte-li po ruce vhodné vývojové prostředí, můžete si příklady vyzkoušet prakticky.

Prvním krokem pro použití Gedmo\Tree extenze je namapování struktury stromu k dané entitě. Mapování je možné realizovat ve formátu YAML, XML, ale i PHPDoc anotacemi v entitě. My pro následující příklady použijeme právě anotací, které jsou v PHP kódu pak velmi dobře čitelné.

Pro zařazení entity do stromové struktury rozšíříme entitu o následující vlastnosti:

  • root: id rootovské entity
  • lvl: hloubka zanoření
  • lft: levý index
  • rgt: pravý index
  • parent: rodičovská entita
  • children: kolekce potomků daného uzlu

A přidáme si i jednu obecnou vlastnost entity:

  • title: název

Na pomoc s příklady si vezmeme zvířata, protože Foo a Barů je všude dostatek. Představme si tedy, že chceme realizovat klasifikační strom zvířat. Entita „Taxon“ by mohla vypadat například takto:


namespace Entity;

use Doctrine\ORM\Mapping as ORM;
use Gedmo\Mapping\Annotation as Gedmo;

/**
*
* @Gedmo\Tree(type="nested")
* @ORM\Table(name="taxon")
* @ORM\Entity(repositoryClass="Gedmo\Tree\Entity\Repository\NestedTreeRepository")
*
*
*/
class Taxon
{

    /**
    * @var string
    * @ORM\Column(name="title", type="text")
    */
    private $title;

    /**
    * @Gedmo\TreeLeft
    * @ORM\Column(name="lft", type="integer")
    */
    private $lft;

    /**
    * @Gedmo\TreeRight
    * @ORM\Column(name="rgt", type="integer")
    */
    private $rgt;

    /**
    * @Gedmo\TreeLevel
    * @ORM\Column(name="lvl", type="integer")
    * @GRID\Column(field="lvl")
    */
    private $lvl;

    /**
    * @Gedmo\TreeRoot
    * @ORM\Column(name="root", type="integer", nullable=true)
    */
    private $root;

    /**
    * @Gedmo\TreeParent
    * @ORM\ManyToOne(targetEntity="\Edge\MakaluBundle\Entity\Taxon", inversedBy="children")
    * @ORM\JoinColumn(name="parent_id", referencedColumnName="id", onDelete="SET NULL")
    */
    private $parent;

    /**
    * @ORM\OneToMany(targetEntity="\Edge\MakaluBundle\Entity\Taxon", mappedBy="parent")
    */
    private $children;

    public function setTitle($title)
    {
        $this->parent = $title;

        return $this;
    }

    public function getTitle()
    {
        return $this->title;
    }

    public function setParent(Taxon $parent = null)
    {
        $this->parent = $parent;

        return $this;
    }

    public function getParent()
    {
        return $this->parent;
    }

    public function getChildren()
    {
        return $this->children;
    }

    public function getRoot()
    {
        return $this->root;
    }

    public function getLvl()
    {
        return $this->lvl;
    }

}

Vlastní funkcionalitu pro práci se stromem poskytuje NestedTreeRepository. Co nabízí?

Sestavení stromu

Vytvořme si novou rootovskou entitu …

$taxon = new Taxon();
$taxon->setTitle('Taxon');
$this->em->persist($taxon);

… a také prvního potomka.

$bird = new Taxon();
$bird->setTitle('Bird');
$this->em->persistAsFirstChildOf($bird, $taxon);
$this->em->flush();

Máme hotový tento strom:

  • Taxon
    • Bird

A nyní si postavme i zbytek stromu:

$mammal = new Taxon();
$mammal->setTitle('Mammal');
$this->em->persistAsLastChildOf($mammal, $taxon);

$beast = new Taxon();
$beast->setTitle('Beast');
$this->em->persistAsLastChildOf($beast, $mammal);

$primate = new Taxon();
$primate->setTitle('Primate');
$this->em->persistAsLastChildOf($primate, $mammal);

$flower = new Taxon();
$flower->setTitle('Flower');
$this->em->persistAsLastChildOf($flower, $taxon);

$fish = new Taxon();
$fish->setTitle('Fish');
$this->em->persistAsLastChildOf($fish, $taxon);

$repltile = new Taxon();
$repltile->setTitle('Reptile');
$this->em->persistAsLastChildOf($repltile, $taxon);

$this->em->flush();

Vytvořili jsme tuto reprezentaci stromu:

  • + Taxon
    • Bird
    • Mammal
      • Beast
      • Primate
    • Flower
    • Reptile
    • Fish

Odstranění entity

Mezi faunu se nám vloudila i flora a ta tam samozřejmě nepatří. Metodou removeFromTree($entity) jednoduše odstraníme entitu. Doctrine za nás přitom ohlídá konzistenci struktury stromu (aktualizuje indexy). Za zmínku stojí clearování EntityManageru. To slouží k pročištění vyrovnávací paměti. Entita totiž mohla být odstraněna z databáze, ale z paměti nikoliv. Flushování EntityManageru se v tomto případě volat nemusí.

$repo->removeFromTree($flower);
$this->em->clear();

A květiny jsou pryč – máme tedy strom:

  • + Taxon
    • Bird
    • Mammal
      • Beast
      • Primate
    • Reptile
    • Fish

Přesouváme entity v hierarchii

Pro manipulaci s větvemi stromu (uzly), slouží metody moveUp a moveDown. Obě metody mají stejné parametry. Prvním je entita, druhý (integer/boolean) určuje počet pozic, o které bude uzel posunut (integer), nebo značí, zda má být uzel přesunut na počátek či na konec (boolean). Za zmínku stojí dodat fakt, že entitu přesouváme vždy se všemi jejími potomky.

Volání,

$repo->moveUp($fish, 1);

posune ryby o jeden stupeň výše:

  • + Taxon
    • Bird
    • Mammal

      • Beast
      • Primate
    • Fish
    • Reptile

Pokud zadáme místo pozice boolean hodnotu true, přesuneme entitu a její potomky na první pozici v daném uzlu (hloubce).

$repo->moveUp($mammal, true);
  • + Taxon
    • Mammal
      • Beast
      • Primate
    • Bird
    • Fish
    • Reptile

Obdobně samozřejmě funguje metoda moveDown, směr je však opačný:

$repo->moveDown($mammal, 1);
  • + Taxon
    • Birds
    • Mammals
      • Beast
      • Primate
    • Fish
    • Reptile

S hodnotou pozice true pak logicky přesuneme entitu na poslední pozici v uzlu.

$repo->moveDown($bird, true);
  • + Taxon
    • Mammal
      • Beast
      • Primate
    • Fish
    • Reptile
    • Bird

Co když potřebujeme přesouvat i mezi jednotlivými uzly? Například entitu $beast chceme umístit pod $birds (jako prvního potomka). Nepřišla jsem na přímočaré řešení, ale výsledku lze dosáhnout následovně:

$beast->setParent($bird);
$this->em->flush();
$repo->persistAsNextSiblingOf($bird, $beast);
$this->em->flush();
  • + Taxon
    • Mammal
      • Primate
    • Fish
    • Reptile
    • Bird
      • Beast

Upss, ale tam přeci šelmy nepatří! Zpět s nimi  …

$repo->persistAsFirstChildOf($mammal, $beast);
$this->em->flush();
  • + Taxon
    • Mammal
      • Beast
      • Primate
    • Fish
    • Reptile
    • Bird

Chytré filtrování

Metoda getRootNodes($sortByField = null, $direction = ‚asc’) vrátí pole rootovských entit. To nám umožní univerzální přístup ke stromům, aniž bychom znali jejich konkrétní strukturu. Nalezení kořenových uzlů je typicky prvním krokem pro práci se stromem. Nested set přitom umožňuje i struktury s více kořeny. V našem případě máme root jediný a to entitu s názvem Taxon.

$repo->getRootNodes();
  • Taxon

Chceme-li získat entity, které nemají potomky, bude se nám hodit metoda getLeafs($root = null, $sortByField = null, $direction = ‚ASC’).

$repo->getLeafs($taxon);

V našem stromu dostaneme:

  • Beast
  • Primate
  • Fishe
  • Reptile
  • Bird

„Sourozenecké“ entity na stejné úrovni umístěné před vstupním uzlem $node získáme metodou getPrevSiblings($node, $includeSelf = false)

$repo->getPrevSiblings($fish);
  • Fish
  • Mammal
  • Reptile

Entity na stejné úrovni umístěné za vstupním uzlem $node získáme stejnou metodou getNextSiblings($node, $includeSelf = false)

$repo->getNextSiblings($reptile, true);
  • Reptile
  • Bird

Často potřebnou cestu k entitě vrací metoda getPath($node) a to ve tvaru pole entit. Pro strom:

  • + Taxon
    • Mammal
      • Beast
      • Primate
    • Fish
    • Reptile
    • Bird

pak volání:

$repo->getPath($primate);

vrátí:

array(0 => $taxon, 1 => $beast, 2 => $mammal, 3 => $primate)

Neméně často potřebujeme vrátit všechny potomky. S metodou children($node = null, $direct = false, $sortByField = null, $direction = ‚ASC’, $includeNode = false) je to hračka.

Popišme si jednotlivé parametry, není jich málo:

  • $node – entita, jejíž potomky požadujeme
  • $direct (boolean) – omezí výstup pouze na přímé potomky (true) či vrátí všechny (false)
  • $sortByField: – lze řadit dle nějaké vlastnosti entity
  • $direction: – směr řazení (DESC, ASC)
  • $includeNode: – výstup bude zahrnovat i entitu $node

Volání metody:

$repo->children($taxon, true);

Nám v našem aktuálním stromu vrátí jen přímé potomky:

  • Mammal
  • Fish
  • Reptile
  • Bird

Volání:

$repo->children($taxon, false);

Pak vrátí celý strom tj. úplně všechny potomky:

  • Mammal
    • Beast
    • Primate
  • Fish
  • Reptile
  • Bird

Též se vám nechce generovat html seznam? Metoda getChildrenHierarchy($node = null, $direct = false, array $options = array(), $includeNode = false) to hravě zvládne.

Až na $options, jsme se s většinou parametů v této metodě už dříve setkali.

Podívejme se $options na zoubek:

  • decorate = false|true – vrátí vícerozměrné pole | rep. html
  • rootOpen = '<ul>' – počátek uzlu
  • rootClose = '</ul>' – ukončení uzlu
  • childStart = '<li>' – počátek potomka
  • childClose = '</li>' – ukončení potomka
  • nodeDecorator = null; – Closure

Volání v s následujícím nastavením:

$options = array(
'decorate' => true,
'nodeDecorator' => function($node) { return ’<b>’.$node['title'].’</b>’; }
);

$repo->getChildrenHierarchy($ammal, false, $options, true);

Vrátí celý html seznam ve stringu:

"<ul><li><b>Taxon</b><ul><li><b>Mammal</b><ul><li><b>Beast</b>
</li><li><b>Primate</b></li></ul></li><li><b>Fish</b></li><li>
<b>Reptile</b></li><li><b>Bird</b></li></ul></li></ul>"

Pár slov na závěr

S hierarchickými daty programátoři běžně manipulují a bez kvalitní implementace se mohou stát trnem v patě. Vytvořit kvalitní implementaci nested set modelu není jednoduchý úkol. S použitím Doctrine extenze Gedmo\Tree je práce opravdu snadná. I bez předchozích zkušeností jsem se při aplikaci na reálném projektu nesetkala s většími komplikacemi.

Zaujal vás tento článek? Máte jiné zkušenosti? Jak často řešíte problematiku stromového uložení dat a jak ji řešíte? Napište do diskuse, ráda se dozvím i váš pohled na věc.

9 komentářů

  1. Tomáš Kuba
    Srp 14, 2013 @ 21:23:40

    Niki díky za článek. Každý kdo si nezkusil naimplementovat traverzování kolem stromu zřejmě nedocení jakou kopu práce autoři Gedmo\Tree ušetřili celému světu :) Troufnu si tvrdit, že téměř každá aplikace na webu bude obsahovat nějaká data ukládaná ve stromu a manipulace s těmito daty se bez dobře postavené DB abstrakční vrstvy může stát ošklivou noční můrou.

    Přeji „happy coding“ všem ;)

    Reply

  2. Jan Tichý
    Srp 15, 2013 @ 12:06:26

    Knihovnu samotnou jsem zatím nijak podrobně nezkoumal, ale zaujalo mě hned několik věcíL

    * Kde se v entity manageru objevily metody $this->em->persistAsFirstChildOf() a $this->em->persistAsLastChildOf()? To se EM někde dědí nebo přetěžuje? Nebo je to překlep a ty metody patří do $repo?

    * Pokud ano, tak opravdu je to navržené tak, že funkce persistAsFirstChildOf(), persistAsLastChildOf(), persistAsNextSiblingOf(), moveUp(), moveDown() jsou součástí REPOZITÁŘE? Tedy opravdu repozitář zajišťuje i persistenci a manupulaci s daty?

    * Když si budu chtít napsat svůj vlastní repozitář, budu si ho moct napsat od začátku sám, nebo si ho budu muset podědit od tohohle jejich?

    * Bude to fungovat i pokud v definici entity vynechám parametr anotace repositoryClass=“Gedmo\Tree\Entity\Repository\NestedTreeRepository“? Bylo by fajn, kdyby ano, protože tohle vázání repository na entitu přímo v definici entity je bad practice z pohledu IOC/DI.

    Reply

  3. Václav Novotný
    Srp 16, 2013 @ 10:03:49

    Ahoj Honzo, díky za komentář. Nikol tu dneska není, tak zkusím odpovědět já.

    EntityManager nemá metody persistAsFirstChildOf() atd., je to překlep, tyto metody má, jak jsi správně poznamenal, repository ($repo).

    Konkrétně je to tam řešené přes magický call:

        /**
         * Allows the following 'virtual' methods:
         * - persistAsFirstChild($node)
         * - persistAsFirstChildOf($node, $parent)
         * - persistAsLastChild($node)
         * - persistAsLastChildOf($node, $parent)
         * - persistAsNextSibling($node)
         * - persistAsNextSiblingOf($node, $sibling)
         * - persistAsPrevSibling($node)
         * - persistAsPrevSiblingOf($node, $sibling)
         * Inherited virtual methods:
         * - find*
         *
         * @see \Doctrine\ORM\EntityRepository
         * @throws InvalidArgumentException - If arguments are invalid
         * @throws BadMethodCallException - If the method called is an invalid find* or persistAs* method
         *      or no find* either persistAs* method at all and therefore an invalid method call.
         * @return mixed - TreeNestedRepository if persistAs* is called
         */
        public function __call($method, $args)
    

    Ano, je to tak, že se repository plete i do persistence dat a není to košér.
    Ohledně napsání vlastního repository si nejsem teď úplně jistý, nemám to ozkoušené, takže budu vařit z vody. Existuje interface \Gedmo\Tree\RepositoryInterface. Existuje také \Gedmo\Tree\Entity\Repository\AbstractTreeRepository, ze kterého se dá vyjít. Osobně to chápu tak, že samotný interface, který musí tvé nové repository splňovat je relativně malé (a správně definuje získávací metody), ale abys mohl se stromem pracovat, musíš si pak dopsat i něco, co ti bude data do stromu ukládat. Jestli to bude jiná třída, je to na tobě. Pokud to ale nechceš implementovat, můžeš použít výchozí \Gedmo\Tree\Entity\Repository\NestedTreeRepository, které nesprávně motá získávání a ukládání dat do jedné třídy. Klasické zjednodušení práce na úkor správnosti objektové architektury, jak ho známe :)

    Podle mých testů parametr anotace repositoryClass=“Gedmo\Tree\Entity\Repository\NestedTreeRepository“ vynechat nezle. Nato je tato extenze s Doctrine ORM málo integrovaná. Respektive zdá se, že Doctrine neumožňuje zaregistrovat jiná repository pro entity „určitého typu“ (závěr o Doctrine ORM je opět spíše postavený na očekáváních než na tom, že bych to hledal v kódu).

    Reply

    • Candy
      Úno 09, 2017 @ 05:32:10

      A wonderful job. Super helpful inooamrtifn.

      Reply

  4. Frantisek Ferko
    Pro 25, 2015 @ 21:09:01

    Ahoj trosku ma zarazilo hned to s $this->em ale to bolo vysvetlene vyssie…
    v nasledujucom kode mi nejde do hlavy anotacia @GRID ma byt niekde pouzita a co to vlastne robi alebo ako to mame chapat? :)
    /**
    * @Gedmo\TreeLevel
    * @ORM\Column(name=“lvl“, type=“integer“)
    * @GRID\Column(field=“lvl“) <—– toto myslim
    */
    private $lvl;

    inak pekny bundle dik :)

    Reply

  5. Martin Kejzlar
    Led 21, 2016 @ 23:07:42

    Díky za pěkný článek. Osobně jsem si nedávno zkoušel udělat podobnou knihovnu ručně a je to opravdu oříšek. Sice se mi povedlo dá do kupy pro moje potřeby funkční model, ale ke konci, jak třída bobtnala, jsem se už uchyloval k nepěknostem v kódu a čítil jsem, že se v tom zamotávám. Tuhle knihovnu zkouším asi 3 hodiny a zatím max. spokojenost. Svůj kód zahodím a nasadím tohle.

    Reply

    • Nikol Ježková
      Úno 08, 2016 @ 09:31:48

      Mám radost, že článek pomohl :-)

      Reply

  6. Jiří Hrozný
    Čec 01, 2017 @ 15:43:51

    Zdravím, článek je fajn, ale chybí mi informace, kde se získá repozitář $repo a co vše je potřeba k nastavení gedma krom instalace přes composer. Díky

    Reply

Napsat komentář k Tomáš Kuba Zrušit