Updating tree

Kudose

'ello all.

I've been reading http://www.sitepoint.com/article/hierarchical-data-database/3/ and have a functioning tree that I can add to or delete from. I am having trouble figuring out the algorithm to update the tree when a node is moved.

Here is the method I am using ... I am sure it is something obvious.

Any assistance would be great ... my mind is fried and it's only noon. :bemused:

public function updateRole(array $data, $where, array $old){
      $this->db->beginTransaction();
      try {
        // if left or right values altered
        if($data['lft'] != $old['lft']){
          // parent updated
          $parent = $this->getParentByLFT($data['lft']);
          if(!is_array($parent)){
            $parent['lft'] = $parent['rght'] = 0;
          }
          // update lft
          $this->db->query("UPDATE `".$this->_name."` SET `lft` = `lft` + 1 WHERE `lft` > ".$parent['lft']);
          // update rght
          $this->db->query("UPDATE `".$this->_name."` SET `rght` = `rght` + 1 WHERE `rght` < ".$parent['rght']);
          // update rght
          $this->db->query("UPDATE `".$this->_name."` SET `rght` = `rght` + 2 WHERE `rght` >= ".$parent['rght']);
        }
        // replace $data['lft'] with parent lft + 1
        $data['lft'] = $parent['lft'] + 1;
        // replace $data['rght'] with parent rght - 1
        $data['rght'] = $parent['rght'] - 1;
        // update record
        $this->db->update($this->_name, $data, $where);
        $this->db->commit();
        return true;
      } catch(Exception $e){
        $this->db->rollBack();
        throw new Exception($e->getMessage());
      }
    }

I saw the function used in the link above, but I don't want to traverse the tree to update it (unless that's the only way).

TIA!

edit

Before this method is run, the tree is intact. Afterwards the tree is borked on both lft and rght.

roleid lft rght role_name
1 1 10 Administrator
2 3 10 Member
3 5 6 Guest
10 2 7 Test

sneakyimp

I had asked the same question before here but didn't get a whole lot of feedback.

I don't remember much about it but I do seem to recall that you have to determine a few things about the node, where it is located, and where it is going before you know what to update.

Weedpacket

I haven't worked through all the logic of moving a subtree, but I can see one problem with your algorithm

 $this->db->query("UPDATE `".$this->_name."` SET `rght` = `rght` + 1 WHERE `rght` < ".$parent['rght']);
$this->db->query("UPDATE `".$this->_name."` SET `rght` = `rght` + 2 WHERE `rght` >= ".$parent['rght']);

This will always increase the rght field of the root element - but that should only increase (by exactly two) if a new node is added (the lft field of the root is 1, the rght field of the root is 2*(number of nodes in tree)). Also, the rght and lft fields should change parity only if their depth in the tree changes (the root's lft field is odd, the root's children are even, the root's grandchildren are odd....)

Perhaps what you could do is work out the consequences would be of deleting the nodes of the subtree and then reinserting them; then you'll know what the net effect of the move should be.