Generating a tree from nested set

Question

I am looking to display a html tree from nested set data.

As the displayed tree does not always display all branches the leaf nodes cannot be identified by subtracting the lft & rgt values.

              1 Drinks 27
           /       |       \
 2 Coffee 3     4 Tea 20     21 Milk 26
               /        \
         5 Black 8     9 Green 19
                       /       \
             10 China 14      15 Africa 18

I was looking to adapt the following code: How to render all records from a nested set into a real html tree

Solution:

Happy to receive code improvement suggestions :)

def tree_from_set(set, start_level)
  buf = "<ul>"
  parent = []
  prev = set[start_level]
  set[start_level+1..-1].each do |node|

    if node.lft.between?(prev.lft, prev.rgt)
      # Previous was the parent
      buf << open_parent_tag(prev)
      parent.push(prev)
    else
      if node.lft.between?(parent.last.lft, parent.last.rgt)
        #Previous was a child
        buf << leaf_tag(prev)
      else
        buf << leaf_tag(prev)
        begin
          buf << "</ul></li>"
          parent.pop
        end until parent.empty? or node.lft.between?(parent.last.lft, parent.last.rgt)
      end
    end  

    prev = node
  end

  buf << leaf_tag(prev)
  begin
    buf << "</ul></li>"
    parent.pop
  end until parent.empty?

  buf << "</ul>"
  buf.html_safe
end


def open_parent_tag(node)
  %{ <li>
       #{link_to(node.name, node)}
       <ul>
  }
end


def leaf_tag(node)
  content_tag(:li, link_to(node.name, node))
end

Answer 1

I used this function, but on php, not on ruby:

<?php
//nested sets data ordered by left
$data = array(
 array("left" => 1, "right" => 10, "name" => "P0"),
 array("left" => 2, "right" => 7, "name" => "P1"),
 array("left" => 3, "right" => 4, "name" => "P11"),
 array("left" => 5, "right" => 6, "name" => "P12"),
 array("left" => 8, "right" => 9, "name" => "P2")
);

//Converter function gets nested sets array and returns nested php array
function nest($arrData){
 $stack = array();
 $arraySet = array();
 foreach( $arrData as $intKey=>$arrValues) {
  $stackSize = count($stack);
  while($stackSize > 0 && $stack[$stackSize-1]['right'] < $arrValues['left']) {
   array_pop($stack);
   $stackSize--;
  }

  $link =& $arraySet;
  for($i=0;$i<$stackSize;$i++) {
   $link =& $link[$stack[$i]['id']]["children"]; //navigate to the proper children array
  }

  $tmp = array_push($link,  array ('item'=>$arrValues,'children'=>array()));
  array_push($stack, array('id' => $tmp-1, 'right' => $arrValues['right']));
 }

 return $arraySet;
}


//Print result
printArray(nest($data));

function printArray($array){
 echo "<ul>";
 foreach ($array as $row){
  $children = $row['children'];
  echo "<li>";
  echo $row['item']['name'];
  if (!empty($children)) printArray($children);
  echo "</li>";
 }
 echo "</ul>";
}
?>

Answer 2

Managed to convert it to C++ for those who was looking for it like I was.

readDataBaseData(QVector<NodeData> &data, DBNode *node)
{
    if(data.size() < 1){
        return;
    }

    QVector<QPair<NodeData, int>> stack;
    DBNode* arrayRes = node;

    foreach (NodeData curArrDataItem, data) {
        int stackSize = stack.size();

        while(stackSize > 0 &&
              stack.at(stackSize - 1).first.right < curArrDataItem.left){

            stack.pop_back();
            stackSize--;
        }

        DBNode* link = arrayRes;
        for(int i = 0; i < stackSize; i++){
            link = link->childAt(stack.at(i).second);
        }

        link = new DBNode(curArrDataItem, link);
        stack.push_back(QPair<NodeData, int>(curArrDataItem, link->getParent()->childCount() - 1));
    }
}