[TECH] QUICKLY TRAVERSING AN INFORMATION TREE PART 2
2009 April 14Recently I linked to an entry on LGP's blog on searching a hierarchical data tree.
Last weekend I implemented it in blindRSS. I must say, it's really fun to work with, but hell to implement. Here's the SQL queries you need for it:
I'm using 'startID' and 'endID' as the fields for sorting (LGP just calls them 'min' and 'max'.
Adding something is quite easy:
$q = mysql_query("SELECT * FROM feeds WHERE ID = '".$parentID."'");
$parent = mysql_fetch_object($q);
mysql_query("UPDATE feeds SET endID=endID+2 WHERE endID >= ".$parent->endID);
mysql_query("UPDATE feeds SET startID=startID+2 WHERE startID >= ".$parent->endID); # $parent->endID is correct!
mysql_query("INSERT INTO feeds (startID, endID, name) VALUES ($parent->endID, $parent->endID + 1, 'xxx')");
?>
Deleting something is also still trivial:
$q = mysql_query("SELECT * FROM feeds WHERE ID='".$deleteID."'");
$delete = mysql_fetch_object($q);
mysql_query("DELETE FROM feeds WHERE ID = ".$delete->ID." LIMIT 1");
mysql_query("UPDATE feeds SET endID=endID-2 WHERE endID >= ".$delete->endID);
mysql_query("UPDATE feeds SET startID=startID-2 WHERE startID >= ".$delete->endID); # $r->endID is correct!
?>
The thing that cost me a few days figuring out was how to MOVE something within the structure. Just take my word for it, this works.
In the case of blindRSS an element can bei either a directory or a file so I had to use two cases for moving. If the target to move to is a directory, the entry to be moved would be added to the END of the directory:
# tag entries for moving
mysql_query("UPDATE feeds SET movedirection = 'moveme' WHERE startID >= ".$feedToChange->startID." AND endID <= ".$feedToChange->endID);
# get number of entries to move, times 2
$difference = ($feedToChange->endID - $feedToChange->startID) + 1;
# remove entries from structure
mysql_query("UPDATE feeds SET startID = startID - $difference WHERE startID > ".$feedToChange->endID);
mysql_query("UPDATE feeds SET endID = endID - $difference WHERE endID > ".$feedToChange->endID);
# update our start/end IDs
$q = mysql_query("SELECT * FROM feeds WHERE `ID` = '".mysql_real_escape_string($_GET['moveabove'])."'");
$feedToMoveTo = mysql_fetch_object($q);
$q = mysql_query("SELECT * FROM feeds WHERE `ID` = '".mysql_real_escape_string($_GET['feedid'])."'");
$feedToChange = mysql_fetch_object($q);
# make room for entries
mysql_query("UPDATE feeds SET startID = startID + $difference WHERE startID >= ".$feedToMoveTo->endID);
mysql_query("UPDATE feeds SET endID = endID + $difference WHERE endID >= ".$feedToMoveTo->endID);
# update our IDs again
$q = mysql_query("SELECT * FROM feeds WHERE `ID` = '".mysql_real_escape_string($_GET['moveabove'])."'");
$feedToMoveTo = mysql_fetch_object($q);
$q = mysql_query("SELECT * FROM feeds WHERE `ID` = '".mysql_real_escape_string($_GET['feedid'])."'");
$feedToChange = mysql_fetch_object($q);
# insert entries into structure
mysql_query("UPDATE feeds SET startID = startID - ".$feedToChange->startID." + ".$feedToMoveTo->endID." - $difference WHERE movedirection = 'moveme'");
mysql_query("UPDATE feeds SET endID = endID - ".$feedToChange->startID." + ".$feedToMoveTo->endID." - $difference WHERE movedirection = 'moveme'");
mysql_query("UPDATE feeds SET movedirection = 'none'");
?>
Finally, if the target to move to is a feed entry instead of a directory, the queries are like this:
# Tag the entry we want to move later
mysql_query("UPDATE feeds SET movedirection = 'moveme' WHERE startID >= ".$feedToChange->startID." AND endID <= ".$feedToChange->endID);
# Get the number of entries we want to move, times 2
$difference = ($feedToChange->endID - $feedToChange->startID) + 1;
# Remove the feed from the structure
mysql_query("UPDATE feeds SET startID = startID - $difference WHERE startID > ".$feedToChange->endID);
mysql_query("UPDATE feeds SET endID = endID - $difference WHERE endID > ".$feedToChange->endID);
# Update our start/end IDs
$q = mysql_query("SELECT * FROM feeds WHERE `ID` = '".mysql_real_escape_string($_GET['moveabove'])."'");
$feedToMoveTo = mysql_fetch_object($q);
$q = mysql_query("SELECT * FROM feeds WHERE `ID` = '".mysql_real_escape_string($_GET['feedid'])."'");
$feedToChange = mysql_fetch_object($q);
# Make room for the entry at the target location
# only change entries which are not marked for moving, otherwise we get problems when moving a
# directory with x entries by less than x downwards
mysql_query("UPDATE feeds SET startID = startID + $difference WHERE startID >= ".$feedToMoveTo->startID." AND movedirection = 'none'");
mysql_query("UPDATE feeds SET endID = endID + $difference WHERE endID > ".$feedToMoveTo->startID." AND movedirection = 'none'");
# Update again
$q = mysql_query("SELECT * FROM feeds WHERE `ID` = '".mysql_real_escape_string($_GET['moveabove'])."'");
$feedToMoveTo = mysql_fetch_object($q);
$q = mysql_query("SELECT * FROM feeds WHERE `ID` = '".mysql_real_escape_string($_GET['feedid'])."'");
$feedToChange = mysql_fetch_object($q);
# finally, move to the target location
mysql_query("UPDATE feeds SET startID = startID - ".$feedToChange->startID." + ".$feedToMoveTo->startID." - ".$difference." WHERE movedirection = 'moveme'");
mysql_query("UPDATE feeds SET endID = endID - ".$feedToChange->startID." + ".$feedToMoveTo->startID." - $difference WHERE movedirection = 'moveme'");
mysql_query("UPDATE feeds SET movedirection = 'none'");
?>
Does your head hurt now? Mine did :-)
EOF
Category: blog
Tags: Tech