Any iterative process will imply a limit to tree width. Similarly, any recursive process will imply a limit to tree depth. Most algos will involve a little bit of both. If such logic is included in the contract then it will be hard to estimate how large the tree can be before trouble starts. But, we'll be sure that transaction cost increases with scale. At the block gas limit and/or stack limit, important processes won't work at all.
It's also worth noting that there really isn't any way to delete information from the blockchain, so I wouldn't dwell on the actual destruction of leaves and branches that are pruned away. It's sufficient (and about the same) to logically remove them.
In the code below, the nodes include some simple structures:
- Each node has one parent.
- Each node has an unordered list of the children.
We can add new nodes wherever they belong. A client can obtain the length of the children list and iterate over the children. That makes exploring the tree possible.
Delete is a little tricky.
The basic principle is a pruned branch has no parent. We ignore what's below the pruned branch, since a top-down exploration won't lead to pruned nodes.
To facilitate deletion, the children get an additional pointer; their position in the list of children in the parent. We note that as we add nodes.
To delete a node,
- Move the parents last child to the row to delete in the children list.
- Update the parent position pointer in the child that moved.
- Shorten the children list by one.
So, if the parent has children:
and we want to delete D.
- Move F to the 4th position, where D is.
We make it easy to locate D's position with another pointer:
In D:
- parent is X
- parentIndex is 3 (position in the parent's list)
Having done so, parent's list reads:
Make the list one row shorter with --.
- Don't forget to update F's parentIndex pointer. Was 5. Now 3, because
it moved.
- Zero out the deleted nodes' parent pointers.
Any node can be seen to be attached to the root by following it's ancestry all the way to the tree root. It should be an unbroken chain of parents. If a 0 parent is encountered before the treeRoot, then the node lives in a pruned branch. Logically deleted.
I've included a recursive process to show the simplicity of the logic, but it's better to do that process client-side because it's recursive.
A dishonest client may be able to muck about in pruned branches when the recursive check is absent. If the values set are of any consequence, then it's better to sweep up "pending" changes with a trusted client using a restricted "onlyOwner" process. A client can crawl wide and deep, up and down without ever running out of gas because it will be calling tiny functions as it goes. The contract functions that change state should always zero out pending so state integrity is maintained at each atomic step.
An honest front-end will be able to provide dependable tree navigation at any scale.
Quickly sketched out with minimal testing. Hope it helps:
pragma solidity ^0.4.6;
contract ObjectTree {
bytes32 public treeRoot;
struct NodeStruct {
bytes32 parent; // the id of the parent node
uint parentIndex; // the position of this node in the Parent's children list
bytes32[] children; // unordered list of children below this node
// add useful node properties here
}
mapping(bytes32 => NodeStruct) nodeStructs;
event LogNewNode(bytes32 nodeId, bytes32 parentId);
event LogDelNode(bytes32 nodeId);
function ObjectTree() {
treeRoot = newNode(0);
}
function newNode(bytes32 parent)
public
returns(bytes32 newNodeId)
{
// very tempting to call isActiveNode(parent) here
// to prevent insertion in pruned branches. Not scalable.
newNodeId = sha3(parent, msg.sender, block.number);
NodeStruct memory node;
node.parent = parent;
if(parent>0) {
node.parentIndex = registerChild(parent,newNodeId);
}
nodeStructs[newNodeId] = node;
LogNewNode(newNodeId, parent);
return newNodeId;
}
function registerChild(bytes32 parentId, bytes32 childId)
private
returns(uint index)
{
return nodeStructs[parentId].children.push(childId) - 1;
}
// to remove a node,
// we'll zero the parent and parent index.
// we'll remove the node from the parent's children list
// To do that, we'll
// 1. move the list child into the row to delete
// 2. update the index of the node that moved
// 3. shorten the parent's children list by one
function pruneBranch(bytes32 nodeId)
public
returns(bool success)
{
bytes32 parent = nodeStructs[nodeId].parent;
uint rowToDelete = nodeStructs[nodeId].parentIndex;
uint rowToMove = nodeStructs[parent].children.length-1; // last child in the list
// move the last child into the row to delete
nodeStructs[parent].children[rowToDelete] = nodeStructs[parent].children[rowToMove];
// maintain pointer integrity ... pointer in the child that moved
nodeStructs[nodeStructs[parent].children[rowToMove]].parentIndex = rowToMove;
// parent has one less children now
nodeStructs[parent].children.length--;
// zero out the node that was pruned
nodeStructs[nodeId].parent=0;
nodeStructs[nodeId].parentIndex=0;
LogDelNode(nodeId);
return true;
}
// This following recursive process puts an upper bound on the tree depth the contract can handle.
// Therefore, better to implement similar logic on the client side and recursively call nodeStructs
// until a node can be confirmed attached to the treeRoot in an unbroken chain.
// Shown here for illustration only since it won't scale infinately.
function isActiveNode(bytes32 nodeId)
public
constant
returns(bool isIndeed)
{
if(nodeId==treeRoot) return true;
if(nodeStructs[nodeId].parent==0) return false;
return isActiveNode(nodeStructs[nodeId].parent);
}
function getNodeChildCount(bytes32 nodeId)
public
constant
returns(uint childCount)
{
return(nodeStructs[nodeId].children.length);
}
function getNodeChildAtIndex(bytes32 nodeId, uint index)
public
constant
returns(bytes32 childId)
{
return nodeStructs[nodeId].children[index];
}
}
