Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: korabro 23. 07. 2020, 11:31:59
-
Uz par dnu se snazim zmenit poradi prvku v nested set modelu, ale bez uspechu.
Interval <7;16> se snazim preradit v <6;23> na prvni misto
id name lft rgt
1 ROOT 1 24
2 1 6 23
4 2 4 5
5 3 2 3
7 1.2 21 22
8 1.3 19 20
9 1.4 17 18
11 100 7 16
12 100.1 14 15
14 100.2 12 13
15 100.3 10 11
16 100.4 8 9
- pro presouvane prvky plati 0-x
- nasledovne vsechno prvky v intervalu <6;23> snizit o velikost mnoziny <7;16>
id name lft rgt
1 ROOT 1 24
2 1 6 23
4 2 4 5
5 3 2 3
7 1.2 11 12
8 1.3 9 10
9 1.4 7 8
11 100 -7 -16
12 100.1 -14 -15
14 100.2 -12 -13
15 100.3 -10 -11
16 100.4 -8 -9
V poslednim kromu se nevim rady jak prvky dostat do nasledujiciho umisteni
id name lft rgt
1 ROOT 1 24
2 1 6 23
4 2 4 5
5 3 2 3
7 1.2 11 12
8 1.3 9 10
9 1.4 7 8
11 100 13 22
12 100.1 14 15
14 100.2 16 17
15 100.3 18 19
16 100.4 20 21
-
Začněte tím, že napíšete, o jaké prostředí se jedná – nějaký programovací jazyk, knihovna, databáze? Jinak obecně set (množina) označuje skupinu prvků, které nemají definované pořadí. Jste si jist, že vaše prostředí používá set v jiném významu a pořadí je tam definované?
-
Mnozina je ulozena v MYSQL. Pomoci PHP pak provadim zmeny. Prostredi ve kterem se vysledny list pouziva nyni potrebuje resit i razeni prvku. Pridani a odebirani prvku je snadne. Razeni uz tolik ne. Jako posledni moznost me napadlo pridat sloupec urcujici poradi prvku v ramci rozsahu rodice.
Vysledek by mohl vypadat takto:
id name lft rgt prio
1 ROOT 1 24 1
2 1 6 23 1
4 2 4 5 2
5 3 2 3 3
7 1.2 21 22 2
8 1.3 19 20 3
9 1.4 17 18 4
11 100 7 16 5
12 100.1 14 15 1
14 100.2 12 13 2
15 100.3 10 11 3
16 100.4 8 9 4
ale snad se to da resit i bez toho
-
Vaším cílem je tedy reprezentovat stromovou (nebo jen dvouúrovňovou?) strukturu, kde si uživatel bude moci ručně seřadit prvky pod konkrétním uzlem? Pokud chcete použít nested set model, nezbývá vám při aktualizaci nic jiného, než prvky přečíslovat. Pokud budou aktualizace relativně častá operace, zvolil bych spíš jinou reprezentaci stromu. Přidat sloupec určující pořadí prvků v rámci rozsahu rodiče nedává smysl – tahle informace už je zakódovaná v left a right.
-
Jde o stromovou strukturu, ktera reprezentuje navigaci na webu. Vnoreni prvku muze byt neomezene. Zmena poradi polozek se deje jen v pripade, kdy to vyzaduje spravce. S tim postupem precislovani si prave nevim rady.
-
Musíte vždy projít kompletně určitý podstrom a ten přečíslovat. Pokud budete pořadí měnit vždy jen prohozením dvou prvků, přečíslujete jen ta dva prvky (a jejich podstromy). Pokud uživateli umožníte třeba 4. prvek přetáhnout rovnou na 1. místo, nebo přerovnat celou jednu úroveň a pak nové pořadí jako prvek uložit, musíte přečíslovat celý podstrom společného rodičovského prvku. Přečíslování děláte, jako byste to čísloval poprvé – procházíte prvky v uživatelem určeném pořadí a postupně je číslujete.
-
Pokud mam nasledujici znazorneni:
|-------[2-15]----[16-21]-----[22-25]-------|
1 A B C 26
poradi prvku je zobrazeno nasledovne: (vyssi rozsah ma prednost)
1.C
2.B
3.A
pozadovany je:
1.A
2.B
3.C
Ale ten postup pro prepocet urcit nedovedu
-
Třeba jsem jen blbý a neznalý, ale mě to připadá už od začátku nějak divně navržené.
Pokud do tabulky ukládám stromovou strukturu dal bych tam položky:
id - číselné, unikátní, neměnné, začínající od 1
parentId - root položky mají 0, ostatní jejich nadřazenou položku
localOrder - lokální pořadí v rámci jedné podskupiny
jakékoliv další položky, pro řazení nevýznamné
Pro zobrazení celého stromu najednou buď použiju rekurzi, nebo bych si musel dodefinovat složený globalOrder (složený ze všech localOrder položek od dotyčného prvku až do rootu) a ten při změně pořadí vždy aktualizovat všem prvkům podstromu posunutého prvku.
Pokud budu chtít cokoliv přetřídit v rámci některé podskupiny, použiju jako filtr parentId (identifákátor podskupiny) a tam jednoduchým algoritmem přeházím localOrder hodnoty.
-
Uz par dnu se snazim zmenit poradi prvku v nested set modelu, ale bez uspechu.
Interval <7;16> se snazim preradit v <6;23> na prvni misto
Když jsem tuto úlohu onehdá řešil, tak jsem si to srovnal na tyto čtyři scénáře:
1/ přidání prvku
2/ odebrání prvku
3/ přesun prvku dolů
4/ přesun prvku nahoru
Ve tvém případě to bude tedy přesun nahoru, jestli jsem to dobře pochopil (když tak mě oprav).
To znamená
- vytvořit místo, kam se přesunou prvku
- přesunout prvky
To znamená zjistit jak široký je uzel který přesouváš, to znamená rgt - lft, to znamená jeden SELECT = size.
To znamená zjistit offset přesouvaného uzlu, to znamená jeden SELECT = offset.
Následně UPDATE, které přečísluje všechny uzly, kterou jsou větší jak začátek umístění o size (včetně uzlu, který budeš přesouvat).
Následně UPDATE, které přečísluje přesouvaný uzel: původní lft = lft - offset. (Offset si můžeš vypočítat na začátku, nebo po přesunu - jde oboje.)
Plus samozřejmě by se to dalo různě optimalizovat.
-
Třeba jsem jen blbý a neznalý, ale mě to připadá už od začátku nějak divně navržené.
To co tam má navržené je takzvané Traverzování kolem stromu. Celkem úspěšná technika jak do ploché databáze uložit strom. Má spousta i výkonnostních výhod pro čtení. Horší je zápis, ale je to spíše náročné na hlavu. Po odlazení už to funguje moc pěkně.
PS: Nejsem si jist, zda v tomto případě je či není nutný znát rodiče, tedy parent_id.
-
Uz par dnu se snazim zmenit poradi prvku v nested set modelu, ale bez uspechu.
Interval <7;16> se snazim preradit v <6;23> na prvni misto
Když jsem tuto úlohu onehdá řešil, tak jsem si to srovnal na tyto čtyři scénáře:
1/ přidání prvku
2/ odebrání prvku
3/ přesun prvku dolů
4/ přesun prvku nahoru
Ve tvém případě to bude tedy přesun nahoru, jestli jsem to dobře pochopil (když tak mě oprav).
To znamená
- vytvořit místo, kam se přesunou prvku
- přesunout prvky
To znamená zjistit jak široký je uzel který přesouváš, to znamená rgt - lft, to znamená jeden SELECT = size.
To znamená zjistit offset přesouvaného uzlu, to znamená jeden SELECT = offset.
Následně UPDATE, které přečísluje všechny uzly, kterou jsou větší jak začátek umístění o size (včetně uzlu, který budeš přesouvat).
Následně UPDATE, které přečísluje přesouvaný uzel: původní lft = lft - offset. (Offset si můžeš vypočítat na začátku, nebo po přesunu - jde oboje.)
Plus samozřejmě by se to dalo různě optimalizovat.
Misto v cilovem rodici mam ale nevim jak tam ty prvky presunout. Prvky oznacene pro presun maji minusovou hodnotu (na zacatku prispevku je to videt) Prakticky provedu odebrani mnoziny a pak znovu pridani. Zadny delete ani insert, protoze id radku je primarni klic a ten se nesmi zmenit kvuli relacim.
-
Uz par dnu se snazim zmenit poradi prvku v nested set modelu, ale bez uspechu.
Interval <7;16> se snazim preradit v <6;23> na prvni misto
Když jsem tuto úlohu onehdá řešil, tak jsem si to srovnal na tyto čtyři scénáře:
1/ přidání prvku
2/ odebrání prvku
3/ přesun prvku dolů
4/ přesun prvku nahoru
Ve tvém případě to bude tedy přesun nahoru, jestli jsem to dobře pochopil (když tak mě oprav).
To znamená
- vytvořit místo, kam se přesunou prvku
- přesunout prvky
To znamená zjistit jak široký je uzel který přesouváš, to znamená rgt - lft, to znamená jeden SELECT = size.
To znamená zjistit offset přesouvaného uzlu, to znamená jeden SELECT = offset.
Následně UPDATE, které přečísluje všechny uzly, kterou jsou větší jak začátek umístění o size (včetně uzlu, který budeš přesouvat).
Následně UPDATE, které přečísluje přesouvaný uzel: původní lft = lft - offset. (Offset si můžeš vypočítat na začátku, nebo po přesunu - jde oboje.)
Plus samozřejmě by se to dalo různě optimalizovat.
Misto v cilovem rodici mam ale nevim jak tam ty prvky presunout. Prvky oznacene pro presun maji minusovou hodnotu (na zacatku prispevku je to videt) Prakticky provedu odebrani mnoziny a pak znovu pridani. Zadny delete ani insert, protoze id radku je primarni klic a ten se nesmi zmenit kvuli relacim.
Aha. Tak ten problém bude s těmi minusovými hodnotami.
Nene, já neříkám, že máš něco mazat. Budeš používat jen UPDATE. Také žádné odebrání z množiny a její přidání. Jen upravuješ hodnotu lft a rgt.
Takže: nejdřív všechno, včetně těch prvků určených pro přesun přečísluješ nahoru. Ke každému lft a rgt přičteš šířku toho uzlu. Nebudeš tomu dávat záporné hodnoty ani nic podobného.
Pak vezmeš ten uzel a opět přečísluješ lft a rgt směrem dolu tak aby zapadl do připravené díry.
A pak (na to jsem v původním příspěvku zapomněl) zacelíš díru která vznikla po přesunu toho prvku a to tím, že opět přečísluješ lft a rgt dolu o velikost šířku posouvaného uzlu.
Pracuješ s UPDATE a nejvíc řešíš správné WHERE, aby si přečísloval tu správnou množinu uzlů. V prvním případě počínaje prvním uzlem, který chceš stěhovat až do konce. V druhém případě jen uzly, které chceš stěhovat. A ve třetím případě jen uzly od původně posledního rgt stěhované prvku plus jedna až do konce.
-
Takže: nejdřív všechno, včetně těch prvků určených pro přesun přečísluješ nahoru. Ke každému lft a rgt přičteš šířku toho uzlu. Nebudeš tomu dávat záporné hodnoty ani nic podobného.
Pak vezmeš ten uzel a opět přečísluješ lft a rgt směrem dolu tak aby zapadl do připravené díry.
A pak (na to jsem v původním příspěvku zapomněl) zacelíš díru která vznikla po přesunu toho prvku a to tím, že opět přečísluješ lft a rgt dolu o velikost šířku posouvaného uzlu.
Pokud si to predstavuju spravne tak pri presnym postupu je vysledek nula. Nic se nemeni
-
Takže: nejdřív všechno, včetně těch prvků určených pro přesun přečísluješ nahoru. Ke každému lft a rgt přičteš šířku toho uzlu. Nebudeš tomu dávat záporné hodnoty ani nic podobného.
Pak vezmeš ten uzel a opět přečísluješ lft a rgt směrem dolu tak aby zapadl do připravené díry.
A pak (na to jsem v původním příspěvku zapomněl) zacelíš díru která vznikla po přesunu toho prvku a to tím, že opět přečísluješ lft a rgt dolu o velikost šířku posouvaného uzlu.
Pokud si to predstavuju spravne tak pri presnym postupu je vysledek nula. Nic se nemeni
To určitě ne. Proč si to myslíš?
-
name lft rgt
1 1 8
1.3 2 3
1.2 4 5
1.1 6 7
Prvek 1.3 budu chtit zobrazovat jako prvni. Je nutno ho dat za prvek 1.1. Prvky s vetsim intervalem maji vyssi hodnotu pri zobrazovani.
Sirka uzlu je 3-2+1=2
Takže: nejdřív všechno, včetně těch prvků určených pro přesun přečísluješ nahoru. Ke každému lft a rgt přičteš šířku toho uzlu.
name lft rgt
1 3 10
1.3 4 5
1.2 6 7
1.1 8 9
Pak vezmeš ten uzel a opět přečísluješ lft a rgt směrem dolu tak aby zapadl do připravené díry.
name lft rgt
1 3 10
1.3 2 3
1.2 6 7
1.1 8 9
A pak (na to jsem v původním příspěvku zapomněl) zacelíš díru která vznikla po přesunu toho prvku a to tím, že opět přečísluješ lft a rgt dolu o velikost šířku posouvaného uzlu.
name lft rgt
1 1 8
1.3 2 3
1.2 4 5
1.1 6 7
-
name lft rgt
1 1 8
1.3 2 3
1.2 4 5
1.1 6 7
Prvek 1.3 budu chtit zobrazovat jako prvni. Je nutno ho dat za prvek 1.1. Prvky s vetsim intervalem maji vyssi hodnotu pri zobrazovani.
Prvek 1.3 chceš zobrazovat jako první, nebo za prvek 1.1? Nemůžeš chtít oboje. A nebo ti nerozumím. Jak by měl vypadat cílový stav?
-
name lft rgt
1 1 8
1.3 2 3
1.2 4 5
1.1 6 7
se ve vysledku zobrazuje
1.
1.1
1.2
1.3
1.3 potrebuji zobrazovat jako prvni
name lft rgt
1 1 8
1.3 6 7
1.2 2 3
1.1 4 5
-
name lft rgt
1 1 8
1.3 2 3
1.2 4 5
1.1 6 7
se ve vysledku zobrazuje
1.
1.1
1.2
1.3
1.3 potrebuji zobrazovat jako prvni
name lft rgt
1 1 8
1.3 6 7
1.2 2 3
1.1 4 5
Jo ták. Tak to je proto, protože to máš blbě seřazené. Výpis bude vždycky ... ORDER BY lft. To znamená, že potřebuješ přeskládat ty lft a rgt.
Tedy:
name lft rgt
1 1 8
1.3 2 3
1.2 4 5
1.1 6 7
je správně, a máš to definovaný jak to chceš aby se to zobrazovalo. Pokud nezobrazuje, tak máš špatně řazení. To bude ten problém.
-
omlouvam se spatne jsem to napsal 1.3 potrebuji zobrazovat jako prvni v seznamu pod 1 tzn.
1.
1.3
1.1
1.2
proto potrebuju lft a rgt preskladat nasledovne
name lft rgt
1 1 8
1.3 6 7
1.2 2 3
1.1 4 5
order je prave "BY RGT"
ale vubec nevim jakym postupem to spravne preskladat
-
omlouvam se spatne jsem to napsal 1.3 potrebuji zobrazovat jako prvni v seznamu pod 1 tzn.
1.
1.3
1.1
1.2
proto potrebuju lft a rgt preskladat nasledovne
name lft rgt
1 1 8
1.3 6 7
1.2 2 3
1.1 4 5
order je prave "BY RGT"
ale vubec nevim jakym postupem to spravne preskladat
OK, v tom případě tedy:
Máš:
name lft rgt
1 1 8
1.3 2 3
1.1 4 5
1.2 6 7
A chceš to mít takto:
name lft rgt
1 1 8
1.3 2 3
1.2 4 5
1.1 6 7
To znamená posunout 1.2 nahoru. To znamená podle mého návodu:
1.krok - vytvoření díry
name lft rgt
1 1 8
1.3 2 3
1.1 6 8
1.2 9 10
2.krok - přesun uzlu
name lft rgt
1 1 8
1.3 2 3
1.2 4 5
1.1 6 8
A protože 1.2 byla poslední, není co uklízet.
order je prave "BY RGT"
Seřazení má být BY lft ASC, ale BY rgt ASC by asi mělo jít taky, i když je to takové řazení "zezadu".
-
Pomuze tohle?
https://php.vrana.cz/traverzovani-kolem-stromu-prakticky.php
https://php.vrana.cz/traverzovani-kolem-stromu-presuny-uzlu.php
-
Takhle to je komplikované protože při postupných úpravach se ti nové/už upravené left-right páry kříží s těmi ještě neupravenými a prase aby se v tom pak vyznalo.
Zjednoduš si to - rozděl si prvky v parentu přesouvaného objektu na disjunktní podmnožiny, označkuj si je a pak na nich proveď potřebné operace podle značek. V případě přesunu nahoru:
Prvky před cilovým umístěním - nechat být
Prvky mezi cílovým místem a zdrojovým místem - přečíslovat left i right - zvětšit o velikost přesouvaného objektu (neboli děláme díru)
Prvky objektu - přečíslovat left i right - zmenšit o vzdálenost původního a nového umístění (přesouváme do díry)
Prvy za zdrojovým ojbektem - nechat být
A nezapomeň na zámky jinak se ti to v multiuser prostředí rozese... rozpadne.
-
Prvy za zdrojovým ojbektem - nechat být
Tak to je pak další optimalizace: Můžeš si vytáhnout idečka přesouvaného uzlu, a při přepočítávání lft a rgt k nim přihlížet. Pak by se by oko vystačilo se dvěma UPDATY, a navíc se nebudou ničit indexy u řádek, které nás nezajímají. Drobná nevýhoda je, že nemůžu postavit unikátní index nad lft a rgt.
A nebo je přesouvat na konec a až pak teprve do díry... no, prostor pro optimalizaci tu je.
-
Dalo by se to tedy resit nejak takto (nemel jsem to cas jeste otestovat a mozna nevidim chybu):
Existujici list:
1 | 1 12
1.3 | 2 7
1.3.2 | 3 4
1.3.1 | 5 6
1.2 | 8 9
1.1 | 10 11
Se bude zobrazovat jako pri "order right"
///////////
1
1.1
1.2
1.3
1.3.1
1.3.2
//////////
Pozadavek: celou mnozinu 1.3 chci zobrazovat na zacatku seznamu v rodici 1. Presun nesmi negativne ovlivnit jine, nez mnoziny rodicovskeho intervalu.
1) Presouvane prvky oznacit pro tranzit odectenim od nuly
1 | 1 12
1.3 | -2 -7
1.3.2 | -3 -4
1.3.1 | -5 -6
1.2 | 8 9
1.1 | 10 11
2) V rodici odecist misto = poctu odebranych prvku +1
lft > 7 and lft < 12 lft= lft - 6
rgt > 7 and rgt < 12 rgt= rgt - 6
1 | 1 12
1.3 | -2 -7
1.3.2 | -3 -4
1.3.1 | -5 -6
1.2 | 2 3
1.1 | 4 5
3) A na zaver vratit prvky z tranzitu odectenim od nuly a pricist rgt posledniho prvku v rodici tj. 5
x<0 lft=0 - (lft)+5-1
x<0 rgt=0 -(rgt)+5-1
1 | 1 12
1.3 | 6 11
1.3.2 | 7 8
1.3.1 | 9 10
1.2 | 2 3
1.1 | 4 5
Se bude zobrazovat jako pri "order right"
///////////
1
1.3
1.3.1
1.3.2
1.1
1.2
//////////
- Kontroly:
;na konci zmeny je treba potvrdit ze prvek s lft=1 a rgt=12 stale existuje
;zadne prvky nemaji lft<0 and rgt<0
;zadne cislo lft ani rgt se nevyskytuje > 1
-
1) Presouvane prvky oznacit pro tranzit odectenim od nuly
Ono používání záporného čísla nemusí být tak dobrý nápad, jak by se mohlo na první pohled zdát. Nemůžeš pak použít UNSIGNED, a díky tomu vlastně máš poloviční rozsah těch čísel (-2147483648..2147483647 na místo 0..4294967295). Třeba ti to nevadí, neříkám nic. Ale je dobré o tom vědět.
-
1) Presouvane prvky oznacit pro tranzit odectenim od nuly
Ono používání záporného čísla nemusí být tak dobrý nápad, jak by se mohlo na první pohled zdát. Nemůžeš pak použít UNSIGNED, a díky tomu vlastně máš poloviční rozsah těch čísel (-2147483648..2147483647 na místo 0..4294967295). Třeba ti to nevadí, neříkám nic. Ale je dobré o tom vědět.
+1