ok...i have seen plenty of examples about how to Rebuild_Tree or Add_Node in a nested set data hierarchy, but has anyone done Move_Node? I have been struggling with the mathy-math of moving a branch in a data tree when you're using MODIFIED PREORDER TREE TRAVERSAL. i.e., 'nested sets'.
(this means you are using LFT and RGT to define your tree structure rather than recursive parent_id to define parent-child relationships....it's supposed to be faster).
more info here:
http://www.sitepoint.com/article/1105
this is a THORNY problem. if anybody out there in the wide wide world of PHP/sql can help me simplify this beastly code (and i'm not even sure it works), i would be very grateful.
function move_node($uid_to_move, $where_to_move, $placement) {
// get info about the node we are moving
$uid_to_move = mysql_escape_string($uid_to_move);
$sql = "SELECT parent_id, lft, rgt FROM " . DB_HIERARCHY_TABLE . " WHERE uid=\"$uid_to_move\";";
$query_result = mysql_query($sql)
or die("Could not locate record of moving node. Query failed:" . mysql_error());
if (mysql_num_rows($query_result) < 1) {
die("Query for moving node didn't return anything.");
}
$row = mysql_fetch_assoc($query_result)
or die("Couldn't fetch row from moving record query results.");
$moving_branch_lft = $row['lft'];
$moving_branch_rgt = $row['rgt'];
$moving_branch_parent_id = $row['parent_id'];
$moving_branch_size = ($row['rgt'] - $row['lft']) + 1;
// get info about the node we are moving TO:
$where_to_move = mysql_escape_string($where_to_move);
$sql = "SELECT parent_id, lft, rgt FROM " . DB_HIERARCHY_TABLE . " WHERE uid=\"$where_to_move\";";
$query_result = mysql_query($sql)
or die("Could not locate record of destination node. Query failed:" . mysql_error());
if (mysql_num_rows($query_result) < 1) {
die("Query for destination node didn't return anything.");
}
$row = mysql_fetch_assoc($query_result)
or die("Couldn't fetch row from destination record query results.");
$destination_branch_lft = $row['lft'];
$destination_branch_rgt = $row['rgt'];
$destination_branch_parent_id = $row['parent_id'];
$destination_branch_size = ($row['rgt']-$row['lft']) + 1;
// DETERMINE OFFSET...
// this is tricky because it depends on how many children
// you are moving, which direction, before / after, etc.
if ($destination_branch_lft > $moving_branch_lft) {
// in this case, the destination node is MOVEing...
// because we are cutting the branch out in FRONT
// of the node, its value will be reduced by the
// size of the branch
// $destination_base refers to the desired LFT value
$destination_base = $destination_branch_lft - $moving_size;
} else {
$destination_base = $destination_branch_lft;
}
switch ($placement) {
case "before":
// if we are placing the moving branch before the
// destination branch, we want the moving branch
// to simply take over the destination branch's location
$offset = $destination_base - $moving_branch_lft;
$current_destination = $destination_branch_lft;
$new_parent_id = $destination_branch_parent_id;
break;
case "after":
// if the moving branch goes after
// we need to take the dest. branch size into account
$offset = $destination_base - $moving_branch_lft + $destination_branch_size;
$current_destination = $destination_branch_rgt + 1;
$new_parent_id = $destination_branch_parent_id;
break;
case "inside":
// if the moving branch goes inside, we want to adopt
// the first spot inside the branch
$offset = $destination_base - $moving_branch_lft + 1;
$current_destination = $destination_branch_lft + 1;
$new_parent_id = $where_to_move;
break;
default:
die("unexpected placement arg to move_node:" . $placement);
} // switch
// MOVE STEPS
// we should have enough info now to calculate the expected positions
// of the move nodes. let us update them now and set the EXCLUDE flag
// so that we can keep them separate from the update statements that
// deal with the nodes that aren't moving
$sql = "UPDATE " . DB_HIERARCHY_TABLE .
" SET exclude=1, lft=lft+$offset, rgt=rgt+$offset
WHERE lft>=$moving_branch_lft AND
rgt<=$moving_branch_rgt";
mysql_query($sql)
or die("Query to update moved branch failed:" . mysql_error());
// now that the moving nodes are isolated, we can update
// all the nodes that aren't moving but will be shifted by the
// absence or addition of the moved branch
// SOME LFTs SHIFT DOWN
$sql = "UPDATE " . DB_HIERARCHY_TABLE .
" SET lft=lft-$moving_branch_size
WHERE lft>$moving_branch_lft AND
lft<$current_destination AND exclude=0;";
mysql_query($sql)
or die("Query to downshift lfts failed:" . mysql_error());
// SOME RGTs SHIFT DOWN
$sql = "UPDATE " . DB_HIERARCHY_TABLE .
" SET rgt=rgt-$moving_branch_size WHERE
rgt>$moving_branch_lft AND
rgt<$current_destination AND exclude=0;";
mysql_query($sql)
or die("Query to downshift rgts failed:" . mysql_error());
// SOME LFTS SHIFT UP
$sql = "UPDATE " . DB_HIERARCHY_TABLE .
" SET lft=lft+$moving_branch_size WHERE
lft<$moving_branch_lft AND
lft>=$current_destination AND exclude=0;";
mysql_query($sql)
or die("Query to upshift lfts failed:" . mysql_error());
// SOME RGTS SHIFT UP
$sql = "UPDATE " . DB_HIERARCHY_TABLE .
" SET rgt=rgt+$moving_branch_size WHERE
rgt<$moving_branch_lft AND
rgt>=$current_destination AND exclude=0;";
mysql_query($sql)
or die("Query to upshift rgts failed:" . mysql_error());
// SET EXCLUDE FLAGS BACK TO 0
$sql = "UPDATE " . DB_HIERARCHY_TABLE .
" SET exclude=0;";
mysql_query($sql)
or die("Query to clear excludes failed:" . mysql_error());
// SET PARENT ID OF THE MOVED BRANCH'S ROOT
$sql = "UPDATE " . DB_HIERARCHY_TABLE .
" SET parent_id=\"$new_parent_id\" WHERE
uid=\"$uid_to_move\";";
mysql_query($sql)
or die("Query to set parentid of moved node failed:" . mysql_error());
} //move_node()
