How to Render All Records from a Nested Set into a Real HTML Tree

How to render all records from a nested set into a real html tree

It would be nice if nested sets had better features out of the box wouldn't it.

The trick as you have discovered is to build the tree from a flat set:

start with a set of all node sorted by lft
the first node is a root add it as the root of the tree move to next node
if it is a child of the previous node (lft between prev.lft and prev.rht) add a child to the tree and move forward one node
otherwise move up the tree one level and repeat test

see below:

def tree_from_set(set) #set must be in order
  buf = START_TAG(set[0])
  stack = []
  stack.push set[0]
  set[1..-1].each do |node|
    if stack.last.lft < node.lft < stack.last.rgt
      if node.leaf? #(node.rgt - node.lft == 1)
        buf << NODE_TAG(node)
      else
        buf << START_TAG(node)
        stack.push(node)
      end
    else#
      buf << END_TAG
      stack.pop
      retry
    end
  end
  buf <end

def START_TAG(node) #for example
  "#{node.name}
"
end

def NODE_TAG(node)
  "#{node.name}
"
end

def END_TAG
  "
"
end

How to render a tree from an awesome_nested_set and hit the database only once?

If you really want to do it without any extra db queries, you may need to get them all and convert it into an array with .to_a and then re-create the tree structure in memory by iterating and constructing a hash.

However, there is something called a "closure tree" that is a really powerful way to do tree structures really fast in SQL, that some guys much smarter than me figured out. There is a ruby/rails gem that does it for you, and one of its features is to get an entire tree in a single SELECT statement, and puts it into a nested hash structure which would be perfect for your recursive iteration you're talking about. You may want to look into it: https://github.com/mceachen/closure_tree

But really, if your tree isn't that big, you may want to avoid the "premature optimization" and just do it the easy way, hit the database a few to a few dozen times (if you're always going to stop at level 2, the maximum number of queries is the number of children of the root).

Getting a modified preorder tree traversal model (nested set) into a ul

Ok, let's do some bounty hunting ;)

Step 0 - Sanitize example:

As already mentioned, your example data is broken, as it does not define a valid nested set. If you took this data from an app, you should check the insert/delete logic.

So for testing, I used a sanitized version like so:

(MySQL here, as it was the first at hand)

CREATE TABLE t_categories`(
  `id` INTEGER UNSIGNED NOT NULL AUTO_INCREMENT,
  `title` VARCHAR(45) NOT NULL,
  `lft` INTEGER UNSIGNED NOT NULL,
  `rght` INTEGER UNSIGNED NOT NULL,
  PRIMARY KEY (`id`)
);

INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 1',1,16);
INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 2',2,3);
INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 3',4,7);
INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 4',5,6);
INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 5',8,13);
INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 6',9,12);
INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 7',10,11);
INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 8',14,15);

Step 1 - Let the database do the ordering

Nested sets where primarily invented as a convenient way of storing trees in databases, as they make it pretty easy to query for subtrees, parent relations and, especially interesting in this case, for order and depth:

SELECT node.title, (COUNT(parent.title) - 1) AS depth
 FROM t_categories AS node
 CROSS JOIN t_categories AS parent
 WHERE node.lft BETWEEN parent.lft AND parent.rght
 GROUP BY node.title
 ORDER BY node.lft

This will return your set neatly ordered, starting with the root node and continuing to the end in preorder. Most importantly, it will add the depth of each node as a positive integer, indicating how many levels the node is below root (level 0). For the above example data, the result will be:

title, depth
'Cat 1', 0
'Cat 2', 1
'Cat 3', 1
'Cat 4', 2
'Cat 5', 1
'Cat 6', 2
'Cat 7', 3
'Cat 8', 1

In code:

// Grab ordered data
$query = '';
$query .= 'SELECT node.title, (COUNT(parent.title) - 1) AS depth';
$query .= ' FROM t_categories AS node';
$query .= ' CROSS JOIN t_categories AS parent';
$query .= ' WHERE node.lft BETWEEN parent.lft AND parent.rght';
$query .= ' GROUP BY node.title';
$query .= ' ORDER BY node.lft';

$result = mysql_query($query);

// Build array
$tree = array();
while ($row = mysql_fetch_assoc($result)) {
  $tree[] = $row;
}

The resulting array will look like this:

Array
(
    [0] => Array
        (
            [title] => Cat 1
            [depth] => 0
        )

    [1] => Array
        (
            [title] => Cat 2
            [depth] => 1
        )
    ...
)

Step 2 - Output as HTML list fragment:

Using while loop:

// bootstrap loop
$result = '';
$currDepth = -1;  // -1 to get the outer while (!empty($tree)) {
  $currNode = array_shift($tree);
  // Level down?
  if ($currNode['depth'] > $currDepth) {
    // Yes, open     $result .= '';
  }
  // Level up?
  if ($currNode['depth'] < $currDepth) {
    // Yes, close n open     $result .= str_repeat('
', $currDepth - $currNode['depth']);
  }
  // Always add node
  $result .= '' . $currNode['title'] . '
';
  // Adjust current depth
  $currDepth = $currNode['depth'];
  // Are we finished?
  if (empty($tree)) {
    // Yes, close n open     $result .= str_repeat('
', $currDepth + 1);
  }
}

print $result;

Same logic as recursive function:

function renderTree($tree, $currDepth = -1) {
  $currNode = array_shift($tree);
  $result = '';
  // Going down?
  if ($currNode['depth'] > $currDepth) {
    // Yes, prepend     $result .= '';
  }
  // Going up?
  if ($currNode['depth'] < $currDepth) {
    // Yes, close n open     $result .= str_repeat('
', $currDepth - $currNode['depth']);
  }
  // Always add the node
  $result .= '' . $currNode['title'] . '
';
  // Anything left?
  if (!empty($tree)) {
    // Yes, recurse
    $result .=  renderTree($tree, $currNode['depth']);
  }
  else {
    // No, close remaining     $result .= str_repeat('
', $currNode['depth'] + 1);
  }
  return $result;
}

print renderTree($tree);

Both will output the following structure:

Nitpickers corner: Questioner explicitly asked for

ordered

;-)

Getting nested set model into a ul but hiding closed subtrees

As you already managed to sort the sequence, why not just output as needed?

As some leafs need to appear closed, so the iterator should be able to skip children of non-selected nodes.

Doing so lead me to an idea to solve the problem of terminating the output tree (output = parsing). What to do if the last valid node in the sequence is at a higher depth than 0? I appended a NULL terminator for that. So still open levels can be closed before the loop finishes.

Additionally the iterator overloads nodes to offer common methods on them, like comparing against the currently selected element.

The MyRenderTree function (Demo/Full code)

Edit: The Demo Codepad has problems, here is the source-code: Gist

Getting nested set model into a but hiding “closed” subtrees

function MyRenderTree($tree = array(array('name'=>'','depth'=>'', 'lft'=>'','rgt'=>'')) , $current=false)
{
    $sequence = new SequenceTreeIterator($tree);

    echo '';
    $hasChildren = FALSE;
    foreach($sequence as $node)
    {
        if ($close = $sequence->getCloseLevels())
        {
            echo str_repeat('
', $close);
            $hasChildren = FALSE;
        }
        if (!$node && $hasChildren)
        {
            echo '', "\n";
        }
        if (!$node) break; # terminator

        $hasChildren = $node->hasChildren();
        $isSelected = $node->isSupersetOf($current);

        $classes = array();
        $isSelected && ($classes[] = 'selected') && $hasChildren && $classes[] = 'open';
        $node->isSame($current) && $classes[] = 'current';

        printf('%s', implode(' ', $classes), $node['name']);

        if ($hasChildren)
            if ($isSelected)
                echo '';
            else
                $sequence->skipChildren()
            ;
        else
            echo ''
        ;
    }
    echo '
';
}

This can be solved as well in a single foreach and some variables, however I think for re-useablilty, the implementation based on the SPL Iterators is better.

How to generate nested lists with awesome_nested_set

Use a partial to render the children and kick it off with children methods:

in: _tree.html.erb

<% content_tag :li, :id => dom_id(menu) do %>
  <%= menu.title %>    
  <% content_tag :ul do %>
   <% for child in menu.children do %>
    <%= render :partial => "tree", :locals => {:menu => child }%>
   <% end %>
  <% end unless menu.leaf? %>
 <% end %>

in: show.html.erb

<%= render :partial => "tree", :locals => {:menu => @menu} %>

Replace @menu with your object.

How can I render a tree structure (recursive) using a django template?

I think the canonical answer is: "Don't".

What you should probably do instead is unravel the thing in your view code, so it's just a matter of iterating over (in|de)dents in the template. I think I'd do it by appending indents and dedents to a list while recursing through the tree and then sending that "travelogue" list to the template. (the template would then insert

I'm also pretty sure recursively including template files is really a wrong way to do it...

How to handle recursive rendering of data using AngularJS

rather than nest your controllers, nest the data and just have the one controller.

the view is handled by a template that references itself recursively.

as chadermani has linked to, there are some answers out there.

here is a fiddle with a great example (not my code)

http://jsfiddle.net/brendanowen/uXbn6/8/

and the code from the fiddle

<script type="text/ng-template"  id="tree_item_renderer.html">
    {{data.name}}
    <button ng-click="add(data)">Add node</button>
    <button ng-click="delete(data)" ng-show="data.nodes.length  0">Delete nodes</button>
    <ul> <li ng-repeat="data in data.nodes" ng-include="'tree_item_renderer.html'"></li>    </ul></script>

<ul ng-app="Application" ng-controller="TreeController">
    <li ng-repeat="data in tree" ng-include="'tree_item_renderer.html'"></li></ul>angular.module("myApp", []).
controller("TreeController", ['$scope', function($scope) {
    $scope.delete = function(data) {
        data.nodes = [];
    };
    $scope.add = function(data) {
        var post = data.nodes.length + 1;
        var newName = data.name + '-' + post;
        data.nodes.push({name: newName,nodes: []});
    };
    $scope.tree = [{name: "Node", nodes: []}];
}]);

How to Render All Records from a Nested Set into a Real HTML Tree