How to build, traverse and map simple trees

Trees have funny definitions like this:

A tree is either nothing or something creating more trees.

Here is some terminology.

Node.A structure holding some data.
Edge.A connection from a parent node to a child node.
Parent of a node X.Any node that creates X.
Child of a node X.Any node that is created by X.
Degree of a node X.Number of children of X.
Sibling of a node X.Any node which is another child of a parent of X.
Ancestor of a node X.Any node that is a parent of X or an ancestor of a parent of X.
Descendant of a node X.Any node that is a child of X or a descendant of a child of X.
Root node.Any node without parents.
Leaf node.Any node without children.
Internal node.Any node which is not a root nor a leaf.
Level of a node X.1 + Number of edges from a root to X.
Height of a node X.Number of edges from X to a leaf.

We call simple trees those trees where there is only one root and all other nodes have only one parent. There are many things that would be better represented by trees with multiple roots and multiple parents. Unfortunately their complexity is not really different from directed acyclic graphs, so the former are seen as a special case of the latter and treated accordingly.

Building

In JavaScript, we can build simple trees like this:

{[ .creation | 1.hilite(=javascript=) ]}

whose console output is:

simple tree

Usually we create trees for storing data together with their hierarchical relationships to other data. For example, a thesaurus easily fits into a tree. In fact, we can even define a thesaurus as a tree-like structure:

A thesaurus is either nothing or something creating a narrower thesaurus, and relating to some other thesaurus.

Thus a thesaurus is just a tree together with an additional generic relationship between its nodes.

Traversing

A tree traversal is maybe the most common operation for a tree, regarded as a collection of nodes. Each node is visited once, and there are many possible ways to do it orderly. One of the most common ways is to traverse in depth first order, i.e. starting from the root, we visit a node and each of its children. For example, in our tree (1(2(5,6),3,4(7))), a depth first traversal would visit in order: 1,2,5,6,3,4,7. It’s easy to understand why it’s a very common traversal. It’s not a coincidence that the order is the same we would get by erasing the structure.

Here is a bit of JavaScript code for traversing a tree in depth first order.

{[ .traversal-each| 1.hilite(=javascript=) ]}

The console output is:

traversal-each

Mapping

There are many possible things we can do while traversing a tree. One of the most common is to map nodes’ contents to some transformation so that we get another tree with same structure but different data.

Here is an updated version of TreeTraversal with a new map method.

{[ .traversal-map| 1.hilite(=javascript=) ]}

The console output is exactly the same as the one we got when building tree.

Note that both .each() and .map() of TreeTraversal share the same signature and functionality with .each() and .map() of jQuery respectively.

Here is a jsFiddle if you want to play around.

How to know whether two values are equal or not

JavaScript’s abstract (==) and strict (===) equality operators work fine for scalars like 1, 2, and ‘2’:

1 == 2     || false
2 == '2'   && true
2 === '2'  || false

Objects are another story. Two distinct objects are never equal for either strictly or abstract comparisons. An expression comparing objects is only true if the operands reference the same object. In other words, JavaScript’s equality operators applied to objects only compare their references. That is not very useful.

So I wrote a jQuery plugin to fix that issue.

{[ .equals | 1.hilite(=javascript=) ]}

Here are some simple use cases

{[ .simple-use | 1.hilite(=javascript=) ]}

whose console output is

--
 Case 1: two undefined values
true
--
 Case 2: two null values
true
--
 Case 3: undefined and null values
 ($.equals) comparing( undefined ,  null )
 ($.equals)     found different types undefined != null
false
--
 Case 4: undefined and null values -- abstract comparison
true
--
 Case 5: two NaN values
false
--
 Case 6: two different true values
 ($.equals) comparing( 1 ,  true )
 ($.equals)     found different types number != boolean
false
--
 Case 7: two different false values -- abstract comparison
true
--
 Case 8: same integer 123, 123
true
--
 Case 9: same number 123, Number(123)
true
--
 Case 10: same numeric value 123, 123.0
true
--
 Case 11: same numeric value 123, "123"
 ($.equals) comparing( 123 ,  123 )
 ($.equals)     found different types number != string
false
--
 Case 12: same numeric value 123, "123" -- abstract comparison
true
--
 Case 13: two different strings
false
--
 Case 14: two variables referencing the same object
true
--
 Case 15: an object copy and pasted from another one
 ($.equals) comparing( Object {a: 1, b: 2} ,  Object {a: 1, b: 2} )
 ($.equals)     found different values
true
--
 Case 16: two objects with the same keys and values, but in a different order
 ($.equals) comparing( Object {a: 1, b: 2} ,  Object {b: 2, a: 1} )
 ($.equals)     found different values
true
--
 Case 17: two objects with the same keys and values, but one different value
 ($.equals) comparing( Object {a: 1, b: 2} ,  Object {b: 2, a: "1"} )
 ($.equals)     found different values at key "a" 1 != 1
 ($.equals)   comparing( 1 ,  1 )
 ($.equals)       found different types number != string
false
--
 Case 18: two objects with the same keys and values, but one different value -- abstract comparison
 ($.equals) comparing( Object {a: 1, b: 2} ,  Object {b: 2, a: "1"} )
 ($.equals)     found different values
true

Advanced usage

That’s all well and fun, but comparing non-plain objects is where $.equals shines.

With that in mind, I wrote two symmetrical operations for jQuery: scatter and gather. In Maths multiplication distributes over addition, allowing you to scatter a x (b + c) to a x b + a x c, and gather back a x b + a x c to a x (b + c). Likewise with these two operations, you can scatter jQuery over its elements: $:[ e1, e2 ] to [ $:e1, $:e2 ] and gather back [ $:e1, $:e2 ] to $:[ e1, e2 ].

{[ .scatter-gather | 1.hilite(=javascript=) ]}

Here are some advanced use cases

{[ .advanced-use | 1.hilite(=javascript=) ]}

whose console output is

--
 Case 19: object_$, $(object_$.toArray())
 ($.equals) comparing( 
[html, head, meta, title, script, link, style, script, body, p, div, span, prevObject: jQuery.fn.init[1], context: document, selector: "*", jquery: "1.11.2-pre ... ]
 ,  
[html, head, meta, title, script, link, style, script, body, p, div, span, jquery: "1.11.2-pre ... ]
 )
 ($.equals)     found different lengths 163 != 161
false
--
 Case 20: object_$, $(object_$.toArray()) -- DOM Elements only
 ($.equals) comparing( 
[html, head, meta, title, script, link, style, script, body, p, div, span, prevObject: jQuery.fn.init[1], context: document, selector: "*", jquery: "1.11.2-pre ... ]
 ,  
[html, head, meta, title, script, link, style, script, body, p, div, span, jquery: "1.11.2-pre ... ]
 )
 ($.equals)     found different values
true
--
 Case 21: object_$, $.gather(object_$.scatter())
 ($.equals) comparing( 
[html, head, meta, title, script, link, style, script, body, p, div, span, prevObject: jQuery.fn.init[1], context: document, selector: "*", jquery: "1.11.2-pre ... ]
 ,  
[html, head, meta, title, script, link, style, script, body, p, div, span, jquery: "1.11.2-pre ... ]
 )
 ($.equals)     found different lengths 163 != 161
false
--
 Case 22: object_$, $.gather(object_$.scatter()) -- DOM Elements only
 ($.equals) comparing( 
[html, head, meta, title, script, link, style, script, body, p, div, span, prevObject: jQuery.fn.init[1], context: document, selector: "*", jquery: "1.11.2-pre ... ]
 ,  
[html, head, meta, title, script, link, style, script, body, p, div, span, jquery: "1.11.2-pre ... ]
 )
 ($.equals)     found different values
true
--
 Case 23: $(object_$.toArray()), $.gather(object_$.scatter())
 ($.equals) comparing( 
[html, head, meta, title, script, link, style, script, body, p, div, span, jquery: "1.11.2-pre ... ]
 ,  
[html, head, meta, title, script, link, style, script, body, p, div, span, jquery: "1.11.2-pre ... ]
 )
 ($.equals)     found different values
true
--
 Case 24: $("body"), $("head") -- DOM Elements only
 ($.equals) comparing( 
[body, prevObject: jQuery.fn.init[1], context: document, selector: "body", jquery: "1.11.2-pre ... ]
 ,  
[head, prevObject: jQuery.fn.init[1], context: document, selector: "head", jquery: "1.11.2-pre ... ]
 )
 ($.equals)     found different values at key "0" <body>​…​</body>​ != <head>​…​</head>​
 ($.equals)   comparing( <body>​…​</body>​ ,  <head>​…​</head>​ )
 ($.equals)       found different values at key "lastElementChild" <div>​…​</div>​ != <script type=​"text/​javascript">​…​</script>​
 ($.equals)   comparing( <div>​…​</div>​ ,  <script type=​"text/​javascript">​…​</script>​ )
 ($.equals)       found different lengths 6 != 3
false

As you see, even if by looking at the console you can easily spot outstanding differences thanks to the great object inspection offered by the browser, my plugin is dumber by design, and in general it finds different differences. The important thing is that you get a false or a true when you really expect a false or a true, respectively.

In particular,

  • case 19 and 20 tell us that object_$ and $(object_$.toArray()) are not identical but they contain the same DOM elements
  • case 21 and 22 tell us that object_$ and $.gather(object_$.scatter()) are not identical but they contain the same DOM elements
  • case 23 tells us that $(object_$.toArray()) and $.gather(object_$.scatter()) are identical (but still different objects)
  • case 24 tells us that $(“body”) and $(“head”) are different… as expected 🙂
    • please notice that they are both jQuery objects containing only one DOM element, but given the way the filter is written, $.equals tries to compare also lastElementChild. We could have taken the key into consideration like filter: function(value, key) { … }

Here is a jsFiddle if you want to play around.

 

How to fiddle on any web page

Once you have a nice jQuery plugin for accessing any URL, it’s only natural that you start fiddling around with some web page here and there.

Lately I wanted to dominate the http://disco-tools.eu/disco2_portal/terms.php beast.. ehm.. page, which is home to the official European thesaurus of skills and competences. It’s a good starting point for projects related with education in Europe, but also worldwide. Even if it is far from perfect, it’s translated to many European languages (English, German, French, Czech, Hungarian, Italian, Lithuanian, Polish, Slovak, Spanish, Swedish) and it organizes around 9000 terms in each language.

Screen Shot 2014-06-05 at 11.13.33

My target is to be able to browse the thesaurus from the Result frame of jsFiddle.

First Attempt

I already showed that YQL is not the best choice for getting this URL, due to its inability to let stuff come through without correcting it before. So, I will still use my own proxy.

My first attempt (open in jsFiddle):

{[ .disco-attempt1 | 1.hilite(=javascript=) ]}

produced this result:

Screen Shot 2014-06-05 at 10.19.50