Create a gist now

Instantly share code, notes, and snippets.

@smrchy /README.md
Last active May 19, 2017

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;
};

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

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