5 : Hervorragend 4 : Gut 3 : Durchschnittlich 2 : Schlecht 1 : Schrecklich

[Nested Set] move subtree

Veröffentlicht: 25-02-2010 um 14:09 von AmicaNoctis
Aktualisiert: 25-02-2010 um 15:22 von AmicaNoctis

Stichworte move, nested set, node, relocate, subtree, tree

---

Hi there,

there are several multi-statement solutions out there to move a subtree to a new location (possibly inside another parent node), but I couln't find a solution on the Web to achieve this with a single update statement.

Well, here it is:

Code:

-- moves a subtree before the specified position
-- if the position is the rgt of a node, the subtree will be its last child
-- if the position is the lft of a node, the subtree will be inserted before
-- @param l the lft of the subtree to move
-- @param r the rgt of the subtree to move
-- @param p the position to move the subtree before
update tree
set
	lft = lft + if (:p > :r,
		if (:r < lft and lft < :p,
			:l - :r - 1,
			if (:l <= lft and lft < :r,
				:p - :r - 1,
				0
			)
		),
		if (:p <= lft and lft < :l,
			:r - :l + 1,
			if (:l <= lft and lft < :r,
				:p - :l,
				0
			)
		)
	),
	rgt = rgt + if (:p > :r,
		if (:r < rgt and rgt < :p,
			:l - :r - 1,
			if (:l < rgt and rgt <= :r,
				:p - :r - 1,
				0
			)
		),
		if (:p <= rgt and rgt < :l,
			:r - :l + 1,
			if (:l < rgt and rgt <= :r,
				:p - :l,
				0
			)
		)
	)
where :r < :p or :p < :l;

Here's another one which swaps two subtrees:

Code:

-- swaps two subtrees, where A is the subtree having the lower lgt/rgt values
-- and B is the subtree having the higher ones
-- @param al the lft of subtree A
-- @param ar the rgt of subtree A, must be lower than bl
-- @param bl the lft of subtree B, must be higher than ar
-- @param br the rgt of subtree B
update tree
set
	lft = lft + @offset := if (lft > :ar and rgt < :bl,
		:br - :bl - :ar + :al,
		if (lft < :bl, :br - :ar, :al - :bl)
	),
	rgt = rgt + @offset
where lft >= :al and lft <= :br and :ar < :bl;

The drawback of these statements is that lft and rgt values are temporarily ambiguous, so this method can only be applied when there is no unique index on the lft and rgt column.

Please leave a comment if you happen to discover a situation, where this does not work (except when attempting to move a subtree into itself, which would be just stupid and will be ignored intentionally). In spite of numerous tests, I take no responsibility, if this might mess up your Nested Set, so better test with a copy of your table.

Regards,

Amica

Kategorie: Sonstiges

Hits 2519 Kommentare 2

Kommentare

1. 	Die Grundlagen dazu gibt es hier: php-resource.de Das 'Nested Sets' Modell - Bäume mit SQL PHP Tutorials nicht nur für Anfänger Leider nur auf deutsch.
   	Veröffentlicht: 25-02-2010 um 15:20 von onemorenerd

2. 	Sehr nützlich! Dadurch spart man sich einige SQL-Updates und Nerven.
   	Veröffentlicht: 25-02-2010 um 15:56 von Berni

Trackbacks

AmicaNoctis

• Registriert seit Jul 2009
• Ort Dresden
• Beiträge 5.463
• Blog-Einträge 9

• Blog-Einträge von AmicaNoctis suchen

  Blogs durchsuchen nach: Nur Titel durchsuchen

  Erweiterte Suche
• Kategorien

  Globale Kategorien

  • Geschichten von Entwickler für Entwickler
  • Coding Stuff

  Lokale Kategorien

  • PHP-bezogen
  • Sonstiges
  • Kategorielos
• Neue Kommentare

  • Christlich-Diskriminierende Union? von goth
  • Mit PHP auf UNC-Pfade zugreifen von fireweasel
  • [Nested Set] move subtree von Berni
  • Windows 7 von fireweasel
  • Fluent Interface in der GUI-Entwicklung von PHP-Desaster
• Neue Blog-Einträge

  • Vererbung mit eingebauten Klassen
  • Gruppenwechsel in PHP
  • [Nested Set] move subtree
  • Mit PHP auf UNC-Pfade zugreifen
  • Windows 7
• Besucher

  • Besth
  • chorn
  • ezkimo
  • ghostgambler
  • Malachite
  • mo78
  • streuner
  • TobiaZ
  • webteddy
  • woozel

• Archiv
  <      Februar 2012
  Mo	Di	Mi	Do	Fr	Sa	So
  23	24	25	26	27	28	29
  30	31	1	2	3	4	5
  6	7	8	9	10	11	12
  13	14	15	16	17	18	19
  20	21	22	23	24	25	26
  27	28	29	1	2	3	4