Geek asks and answers

Printing a tree structure in a list, for example, saving indent lines (which consist of ┃, ┃, ┗)

I want to save the line "node indentation" for each object, something like this:

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

Data for each object:

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

Note that I do not want to print anything, I just want to work out indentas an array of characters for each object:

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

So far, I can only step back from them with spaces, but not with pipes, and I come up with a dead end for a solution. Any help?

I am using JS with Angular if this helps.

EDIT: as requested by the code that I still have. At first, I did not publish this because I felt that this was the wrong foundation / approach to building. How this works is pretty trivial: for each object, consider it ancestors and add " "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;
    }

};
+3
2

@JBCP (. ), , , - .

, , ( , , ).

, . , treeIndent node, treeify. (: shuffle )

'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:         '&boxvr;',
    isLastChild:            '&boxur;',
    ancestorHasNextSibling: '&boxv;',
    ancestorIsLastChild:    ' '
}, function (element, indent) {
    log.innerHTML += indent.join(' ') + ' ' + element.name + "\n";
});
<pre id="log"></pre>
Hide result

(!):

:

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 , .
  • injectTreeIndent , .

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

: http://jsfiddle.net/zMY7v/

+5

for (var i = 0; i < numParents; i++) o.nodes.push(" ");

if (o.nodes.length === 1)
    o.nodes[0] = "┣";
else if (o.nodes.length > 1) {
    o.nodes[0] = "┃";
    o.nodes[o.nodes.length - 1] = "┗";
}
+1

More articles:


All Articles