Printing a tree structure in a list like manner, storing the indent strings (which consist of┣, ┃, ┗ )

Question

I want to store the "node indentation string" for each object, something like this:

foo
┣bar
┃┗baz
┃ ┗qux
┃  ┣quux
┃  ┗corge
┣fizz
┗buzz

Given data for each object:

objects = [
{'id':1,'parent_id':null, 'name':'foo'}
{'id':2,'parent_id':1, 'name':'bar'}
];

Note that I don't want to print anything, I just want to work out the indent as an array of characters for each object:

{'id':6,'parent_id':4, 'name':'corge', 'indent':['┃',' ',' ','┗']}

So far I can only indent them with spaces but no 'pipes' and I am stumped at coming up with a solution. Any help?

I am using JS with Angular if it helps.

EDIT: As requested the code I have so far. I didn't post this at first because I felt that it's a wrong foundation/approach to build on. How it works is pretty trivial: for each object, count it's ancestors and add " "'s accordingly.

// go through all our objects and set their indent strings
setIndents = function()
{
    for (var x in objects) {
        var o = objects[x];
        o.nodes = [];

        // push space character for amount of ancestors
        numParents = countParents(o, 0);
        for (var i = 0; i < numParents; i++)
            o.nodes.push(" ");
    }
};
// recursively counts how many ancestors until we hit the root
countParents = function(current, count)
{
    if (current.parent_id !== null) {
        for (var x in objects) {
            if (objects[x].id == current.parent_id) {
                current = objects[x]; //set as new current
                count++;
                break;
            }
        }
        return countParents(current, count);
    } else {
        return count;
    }

};

Answer 1

As @JBCP pointed out (see comments) there is a serious flaw in my original code that would break the whole thing if the initial order was anything but perfect.

So here's an updated version, the order of elements can now be random (it still plays a role in such that it indirectly defines the children order, but the tree-structure will be correct).

I also split the functions so that they can be better configured. For example treeIndent now expects a node branch produced by treeify. (Note: the shuffle function is just there to test the order independence)

'use strict';

/**
 * @see https://bost.ocks.org/mike/shuffle/
 *
 * @param array
 * @returns {*}
 */
function shuffle(array) {
    var m = array.length, t, i;

    // While there remain elements to shuffle…
    while (m) {
        // Pick a remaining element…
        i = Math.floor(Math.random() * m--);

        // And swap it with the current element.
        t = array[m];
        array[m] = array[i];
        array[i] = t;
    }

    return array;
}

function treeify(flat) {
    var map = { __root__: { children: [] }};

    flat.forEach(function (node) {
        var
            parentId = node.parent_id || '__root__',
            id = node.id;

        // init parent
        if (!map.hasOwnProperty(parentId)) {
            map[parentId] = { element: null, children: [] };
        }

        // init self
        if (!map.hasOwnProperty(id)) {
            map[id] = { element: null, children: [] };
        }

        map[id].element = node;
        map[parentId].children.push(map[id]);
    });

    return map.__root__.children;
}

function treeIndent(branch, cfg, decorator, indent)
{
    indent = indent || [];

    branch.forEach(function (node, i) {
        decorator(node.element, indent.concat(
            i === branch.length - 1 ? cfg.isLastChild : cfg.hasNextSibling
        ));

        treeIndent(node.children, cfg, decorator, indent.concat(
            i === branch.length - 1 ? cfg.ancestorIsLastChild : cfg.ancestorHasNextSibling
        ));
    });
}

var input = [
    { id: 1, parent_id: null,              name: 'root'  },
        { id: 2, parent_id: 1,             name: 'bar'   },
            { id: 5, parent_id: 2,         name: 'baz'   },
                { id: 6, parent_id: 5,     name: 'qux'   },
                    { id: 7, parent_id: 6, name: 'quux'  },
                    { id: 8, parent_id: 6, name: 'corge' },
            { id: 9, parent_id: 2,         name: 'but'   },
        { id: 3, parent_id: 1,             name: 'fizz'  },
        { id: 4, parent_id: 1,             name: 'buzz'  }
];

var log = document.getElementById('log');

treeIndent(treeify(shuffle(input)), {
    hasNextSibling:         '├',
    isLastChild:            '└',
    ancestorHasNextSibling: '│',
    ancestorIsLastChild:    ' '
}, function (element, indent) {
    log.innerHTML += indent.join(' ') + ' ' + element.name + "\n";
});

<pre id="log"></pre>

---

Old answer (broken!):

try the following:

function makeTree(flat) {
  var map = { __root__: { children: [] }};

  flat.forEach(function (node) {
    var
      parentId = node.parent_id || '__root__',
      id = node.id;

    // init parent
    if (!map.hasOwnProperty(parentId)) {
      map[parentId] = { children: [] };
    }

    // init self
    if (!map.hasOwnProperty(id)) {
      map[id] = { children: [] };
    }

    map[id].element = node;
    map[parentId].children.push(map[id]);
  });

  return map.__root__.children;
}

function injectTreeIndent(input) {
  var
    levelMap = [],
    indicators = {
      hasNextSibling:         '┣',
      isLastChild:            '┗',
      ancestorHasNextSibling: '┃',
      ancestorIsLastChild:    ' '
    }
  ;

  // apply `indent`
  (function traverse(branch, depth) {
    branch.forEach(function (node, idx) {
      node.element.indent = levelMap.map(function (ancestor) {
        return ancestor === indicators.hasNextSibling ? indicators.ancestorHasNextSibling : indicators.ancestorIsLastChild;
      });

      // if (depth > 0) { // uncomment this, if root elements should have no indentation
      node.element.indent.push(
        levelMap[depth] = branch.length - 1 > idx ? indicators.hasNextSibling : indicators.isLastChild
      );
      // }

      traverse(node.children, depth + 1);

      levelMap.pop();
    });
  }(makeTree(input), 0));
}

var input = [
  { id: 1, parent_id: null, name: 'foo'   },
  { id: 2, parent_id: 1,    name: 'bar'   },
  { id: 5, parent_id: 2,    name: 'baz'   },
  { id: 6, parent_id: 5,    name: 'qux'   },
  { id: 7, parent_id: 6,    name: 'quux'  },
  { id: 8, parent_id: 6,    name: 'corge' },
  { id: 3, parent_id: 1,    name: 'fizz'  },
  { id: 4, parent_id: 1,    name: 'buzz'  }
];

injectTreeIndent(input);

• makeTree is used to optain a nested structure derived from the given flat data.
• injectTreeIndent then traverses that nested structure to inject the required indent informatoin.

demo: http://jsfiddle.net/6R7wf/1/

demo with root elements having no indenation: http://jsfiddle.net/zMY7v/