How To Move A Node In Nested Sets With SQL

    /**
     *  -- create new space for subtree
     *  UPDATE tags SET lpos = lpos + :width WHERE lpos >= :newpos
     *  UPDATE tags SET rpos = rpos + :width WHERE rpos >= :newpos
     * 
     *  -- move subtree into new space
     *  UPDATE tags SET lpos = lpos + :distance, rpos = rpos + :distance
     *           WHERE lpos >= :tmppos AND rpos < :tmppos + :width
     * 
     *  -- remove old space vacated by subtree
     *  UPDATE tags SET lpos = lpos - :width WHERE lpos > :oldrpos
     *  UPDATE tags SET rpos = rpos - :width WHERE rpos > :oldrpos
     */

    // calculate position adjustment variables
    int width = node.getRpos() - node.getLpos() + 1;
    int distance = newpos - node.getLpos();
    int tmppos = node.getLpos();
            
    // backwards movement must account for new space
    if (distance < 0) {
        distance -= width;
        tmppos += width;
    }

    public void move(Node node, int newpos) {
        try {
            refresh(node);
            
            // calculate position adjustment variables
            int width = node.getRpos() - node.getLpos() + 1;
            int distance = newpos - node.getLpos();
            int tmppos = node.getLpos();
            
            // backwards movement must account for new space
            if (distance < 0) {
                distance -= width;
                tmppos += width;
            }
            
            // create new space for subtree
            UpdateBuilder update1 = updateBuilder();
            update1.updateColumnExpression("lpos", "lpos + " + width);
            update1.where().ge("lpos", newpos);
            update(update1.prepare());
            
            UpdateBuilder update2 = updateBuilder();
            update2.updateColumnExpression("rpos", "rpos + " + width);
            update2.where().ge("rpos", newpos);
            update(update2.prepare());
            
            // move subtree into new space
            UpdateBuilder update3 = updateBuilder();
            update3.updateColumnExpression("lpos", "lpos + " + distance);
            update3.updateColumnExpression("rpos", "rpos + " + distance);
            update3.where().ge("lpos", tmppos)
                   .and().lt("rpos", tmppos + width);
            update(update3.prepare());
            
            // remove old space vacated by subtree
            UpdateBuilder update4 = updateBuilder();
            update4.updateColumnExpression("lpos", "lpos - " + width);
            update4.where().gt("lpos", node.getRpos());
            update(update4.prepare());
            
            UpdateBuilder update5 = updateBuilder();
            update5.updateColumnExpression("rpos", "rpos - " + width);
            update5.where().gt("rpos", node.getRpos());
            update(update5.prepare());
            
            // refresh local data
            refresh(node);
            getObjectCache().clearAll();
        } catch (SQLException e) {
            Log.e("Error moving node", e.getMessage());
        }
    }

You May Also Like

Paging Large Data Sets With A LazyList	CSS Menus	Vimliner: The Smallest, Fastest Outliner for VIM	Centering Multiple Line Content with CSS
Using <base href/> with Anchors	Representing Syntax	f:viewParam Validation Doesn't Fit With f:event	Ideas for JSF 2.0

Hi Roger Keays, Thanks for your solutions.

Thank you!

This is the best and the most understandable method to move trees!

Whoa, spezial thanks for that! Awesome, it works perfect!

Best regards from germany

Michael

Thanks for this! I've added it to a PHP nested set library I am putting together. https://github.com/previousnext/nested-set

I have a question. 

                         1 Root 8

              2 Child1 5        6 Child2 7

             3 Child1.1 4

I want to move Child1 under Child2. The shift happens, but there becomes a gap in the tree. The problem I'm having is that Child2.Left is still 6. Then Child1.Left is also 6.  Like so.

1 Root 8

6 Child2 7

6 Child1 9

7 Child1.1 8 

It's like Child2 should shift over to Child.Left = 2 to fill the gap.  

Like many others trying this for the first time is SQL, my brain is fried.

It's useful for me.Although it took me a whole day to figure it out .I even considered the matrix encoding way to store the tree-like structure.But I choose nested set.So。。

it works like a charm. THANKS FOR THE POST.

THANK YOU SO MUCH ! it works like a charm !

Answer to Ryan :

You need to compute newpos. As newpos is the left position where the subtree is targeted, you can do like this :

if target position is before a node, newpos = left position of this node

if target position is into a node (as a child), newpos = left position of this node + 1

if target position is after a node, newpos = right position of this node + 1

 

In your example, if you want groupA become a sub-group of groupB, new pos = 3 +1 = 4

I am really interesting in implementing this, however I'm a bit confused:

Given the following structure :

id, name, lft, rgt

------------------

1, root, 1, 6

2, GroupA, 2, 5

3, GroupB, 3, 4

===========================

If I wanted to take GroupA and make it a sub-group of GroupB, basically flipping the two groups, how would I accomplish this using GroupA as the target node? How do you determine what the newLeftPosition is?

 

 

 

THANK YOU so much for this!

;)

Even with this walk through it took me a couple days to wrap my head around this. But this does work perfectly! I had missed the bit about going backwards and that hung me up for a bit as well.

Also, I'm using this with jstree. So figuring out the new position required some javascript finagling but it works. I can't believe it. It works. And it's so sexy!

 

Ok, this Java code works:

 

// Create space for subtree
        String hql = "UPDATE CatStructure SET lft = lft + " + width
                + " where lft > " + newParent.getLft();
        Query query = session.createQuery(hql);
        int _return = query.executeUpdate();

        hql = "UPDATE CatStructure SET rgt = rgt + " + width + " where rgt >= "
                + newParent.getLft();
        query = session.createQuery(hql);
        _return = query.executeUpdate();

        // Move subtree into new space
        hql = "UPDATE CatStructure SET lft = lft + " + distance
                + ", rgt = rgt + " + distance + " where lft >= " + tmpPos
                + " and rgt < " + (tmpPos + width);
        query = session.createQuery(hql);
        _return = query.executeUpdate();

        // remove old space
        hql = "UPDATE CatStructure SET lft = lft - " + width + " where lft > "
                + actualElement.getRgt();
        query = session.createQuery(hql);
        _return = query.executeUpdate();

        hql = "UPDATE CatStructure SET rgt = rgt - " + width + " where rgt > "
                + actualElement.getRgt();
        query = session.createQuery(hql);
        _return = query.executeUpdate();

This does not work. The major issue is that the lpos and rpos values of subtree are changed after the "create space" step. The "move" and "remove" steps still use old values of the node.

This does not work. The major issue is that the lpos and rpos values of subtree are changed after the "create space" step. The "move" and "remove" steps still use old values of the node.

This does not work. The major issue is that the lpos and rpos values of subtree are changed after the "create space" step. The "move" and "remove" steps still use old values of the node.

brilliant, 

works like it should, very good explanation, thank you!

Moving nodes in nested sets is a complex operation. There were a few solutions on Stack Overflow for moving a node under a given parent, however this doesn't let you select the position of the node amongst it's siblings.

This solution lets you move a node to any position in the tree, with just a single input parameter - the new left position (newpos) of the node.

I follow in psuedo-sql but it still not work. I don't know why. Does it really work?

Saved my life! Superb!

:newpos is the new left position of the node being moved. You have to provide that variable.

 In your example what is :newpos?

Don't worry, it took me more than a while to figure out too. Glad it helped you though. Don't forget to post a link/share/like to your blog or favourite social network. That way I'm motivated to write more.