Instantly share code, notes, and snippets.

@smrchy /README.md
Last active Apr 16, 2018

Embed
What would you like to do?
Sort a SQL query with id and parentid so that the rows have the correct order of the tree.

_queryTreeSort

Note: Please check this blog post for more details on these functions.

Sort a SQL query with id and parentid so that the rows have the correct order of the tree.

Parameters:

  • q (Array): A query result (see example below)
  • id (String): The name of the id column (Default: "id")
  • parentid (String): The name of the ParentItemID column (Default: "parentid")

Example:

SQL: SELECT * FROM Animals ORDER BY name

_queryTreeSort({q: [
	{"id": 456, "parentid": 123, "name": "Dogs"},
	{"id": 214, "parentid": 456, "name": "Labradors"},
	{"id": 123, "parentid": 0, "name": "Mammals"},
	{"id": 810, "parentid": 456, "name": "Pugs"},
	{"id": 919, "parentid": 456, "name": "Terriers"}
]});

Result:

[
	{"id": 123, "parentid": 0, "name": "Mammals"},
	{"id": 456, "parentid": 123, "name": "Dogs"},
	{"id": 214, "parentid": 456, "name": "Labradors"},
	{"id": 810, "parentid": 456, "name": "Pugs"},
	{"id": 919, "parentid": 456, "name": "Terriers"}
]

What now?

Use the result to loop over the query or create a tree with _makeTree()

_makeTree

Transform a correctly sorted SQL query with id and parentid into a tree object. Use _queryTreeSort() to sort you SQL query.

Parameters:

  • q (Array): A query result (see example below)
  • id (String): The name of the id column (Default: "id")
  • parentid (String): The name of the ParentItemID column (Default: "parentid")
  • children (String): The name of the "children" array to be created in rows that have children (Default: "children")

Example:

_makeTree({ q:
	[
		{"id": 123, "parentid": 0, "name": "Mammals"},
		{"id": 456, "parentid": 123, "name": "Dogs"},
		{"id": 214, "parentid": 456, "name": "Labradors"},
		{"id": 810, "parentid": 456, "name": "Pugs"},
		{"id": 919, "parentid": 456, "name": "Terriers"}
	]
});

Result:

[
	{
		"id": 123,
		"parentid": 0,
		"name": "Mammals",
		"children": [
			{
				"id": 456,
				"parentid": 123,
				"name": "Dogs",
				"children": [
					{
						"id": 214,
						"parentid": 456,
						"name": "Labradors"
					},
					{
						"id": 810,
						"parentid": 456,
						"name": "Pugs"
					},
					{
						"id": 919,
						"parentid": 456,
						"name": "Terriers"
					}
				]
			}
		]
	}
]

What now?

Use the result to display your tree with a recursive function like _renderTree()

_makeTree = (options) ->
id = options.id or "id"
pid = options.parentid or "parentid"
children = options.children or "children"
temp = {}
o = []
# Create the tree
for e in options.q
e[children] = []
# Add the row to the index
temp[e[id]] = e
# This parent should be in the index
if temp[e[pid]]?
# This row is a child
# Add the child to the parent
temp[e[pid]][children].push(e)
else
# Add a root item
o.push(e)
return o
var _makeTree = function(options) {
var children, e, id, o, pid, temp, _i, _len, _ref;
id = options.id || "id";
pid = options.parentid || "parentid";
children = options.children || "children";
temp = {};
o = [];
_ref = options.q;
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
e = _ref[_i];
e[children] = [];
temp[e[id]] = e;
if (temp[e[pid]] != null) {
temp[e[pid]][children].push(e);
} else {
o.push(e);
}
}
return o;
};
_queryTreeSort = (options) ->
id = options.id or "id"
pid = options.parentid or "parentid"
ri = [] # Root items
rfi = {} # Rows from id
cfi = {} # Children from id
o = []
# Setup Indexing
for e, i in options.q
rfi[e[id]] = i
if not cfi[e[pid]]?
cfi[e[pid]] = []
cfi[e[pid]].push(options.q[i][id])
# Find parents without rows
for e in options.q when not rfi[e[pid]]?
ri.push(e[id])
# Create the correct order
while ri.length
thisid = ri.splice(0,1)
o.push(options.q[rfi[thisid]])
if cfi[thisid]?
ri = cfi[thisid].concat(ri)
return o
var _queryTreeSort = function(options) {
var cfi, e, i, id, o, pid, rfi, ri, thisid, _i, _j, _len, _len1, _ref, _ref1;
id = options.id || "id";
pid = options.parentid || "parentid";
ri = [];
rfi = {};
cfi = {};
o = [];
_ref = options.q;
for (i = _i = 0, _len = _ref.length; _i < _len; i = ++_i) {
e = _ref[i];
rfi[e[id]] = i;
if (cfi[e[pid]] == null) {
cfi[e[pid]] = [];
}
cfi[e[pid]].push(options.q[i][id]);
}
_ref1 = options.q;
for (_j = 0, _len1 = _ref1.length; _j < _len1; _j++) {
e = _ref1[_j];
if (rfi[e[pid]] == null) {
ri.push(e[id]);
}
}
while (ri.length) {
thisid = ri.splice(0, 1);
o.push(options.q[rfi[thisid]]);
if (cfi[thisid] != null) {
ri = cfi[thisid].concat(ri);
}
}
return o;
};
_renderTree = (tree) ->
html = "<ul>"
for e in tree
html += "<li>#{e.name}"
if e.children?
html += _renderTree(e.children)
html += "</li>"
html += "</ul>"
return html
var _renderTree = function(tree) {
var e, html, _i, _len;
html = "<ul>";
for (_i = 0, _len = tree.length; _i < _len; _i++) {
e = tree[_i];
html += "<li>" + e.name;
if (e.children != null) {
html += _renderTree(e.children);
}
html += "</li>";
}
html += "</ul>";
return html;
};
@mpneuried

This comment has been minimized.

mpneuried commented Dec 18, 2013

To Speed up the raw Make Tree it's also possible to do the makeTree without the presorting.
Just use this version of _makeTree:

_makeTree = (options) ->
    id = options.id or "id"
    pid = options.parentid or "parentid"
    children = options.children or "children"

    # create the index
    temp = {}
    for e in options.q
        # predefine the childs array
        e[children] = []
        # write the id index to find by parentid in second loop
        temp[e[id]] = e

    # Create the tree
    o = []
    for e in options.q
        # This parent should be in the index
        if temp[e[pid]]?
            # This row is a child
            # Add the child to the parent
            temp[e[pid]][children].push(e)
        else
            # Add a root item
            o.push(e)
    return o
@RedskyThirty

This comment has been minimized.

RedskyThirty commented Mar 25, 2016

If someone needs... Tree to Array:

var _flatTree = function(options) {
    var id, pid, children, parentNodeId, tree, output, entry, entryChildren;
    id = options.id || "id";
    pid = options.parentid || "parentid";
    children = options.children || "children";
    parentNodeId = options.parentnodeid || null;
    tree = options.tree;
    output = [];

    for (var i = 0; i < tree.length; i++)
    {
        entry = tree[i];
        entryChildren = entry[children];

        delete entry[children];

        if(entry[pid] == undefined) entry[pid] = parentNodeId;

        output.push(entry);

        if((entryChildren != null) && (entryChildren.length > 0))
        {
            var flat = _flatTree({tree:entryChildren, parentid:pid, parentnodeid:entry[id], children:children});
            for (var j = 0; j < flat.length; j++) output.push(flat[j]);
        }
    }

    return output;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment