fritzthecat-blog: JS Treetable

Hierarchical thinking is deeply rooted in our brains. It is a simple and effective concept. Only in our fast-changing modern times relational thinking has become more important.

Hierarchical thinking is the old Roman "Divide et impera". Split a big problem into smaller ones and then try to solve the smaller problems. Parts of a hierarchy are exchangeable and reusable, especially when the association from parent to child has no back-link.

Relational thinking is more navigational. It views the problem from different aspects, then surveys and filters it until solutions become visible. More like surrounding the enemy and making it give up :-) Separating parts of a relational system always leaves open references.

To have the best of both worlds available on our computers, the Treetable component exists. It is a table with multiple columns, and in one of these columns, most likely the first, a tree is rendered. You could also regard a tree to be a treetable with just one column.

This article is about how to integrate a treetable into an HTML web page using JavaScript, without using jQuery or any JS Widget library. It is just about building the treetable, not about loading folders dynamically, or editing it via drag & drop.

The Beauty

Click on the black triangles below to collapse or expand the tree. Mind that columns do not resize when the tree is expanded or collapsed.

Item	Chapter	PI
Item 1	1	3.14159 26535
Item 2	1.1	3.14159 26535
Item 3	1.1.1	3.14159 26535
Item 4	1.1.2	3.14159 26535
Item 5	1.1.2.1	3.14159 26535
Item 6	1.1.2.2	3.14159 26535
Item 7	2	3.14159 26535
Item 8	2.1	3.14159 26535

Also test following behaviour:

collapse "Item 4"
collapse "Item 1"
expand "Item 1" again and check that "Item 4" is still collapsed
now expand "Item 4"
collapse "Item 1"
expand "Item 1" again and check that "Item 4" is still expanded

Here is the HTML source code for this treetable:

<table data-tree-expanded="true" data-tree-column="0">
      <thead>
        <tr>
            <th>Item</th>
            <th>Chapter</th>
            <th>PI</th>
        </tr>
      </thead>
      <tbody>
        <tr data-tree-level="0">
            <td>Item 1</td>
            <td>1</td>
            <td>3.14159 26535</td>
        </tr>
        <tr data-tree-level="1">
            <td>Item 2</td>
            <td>1.1</td>
            <td>3.14159 26535</td>
        </tr>
        <tr data-tree-level="2">
            <td>Item 3</td>
            <td>1.1.1</td>
            <td>3.14159 26535</td>
        </tr>
        <tr data-tree-level="2">
            <td>Item 4</td>
            <td>1.1.2</td>
            <td>3.14159 26535</td>
        </tr>
        <tr data-tree-level="3">
            <td>Item 5</td>
            <td>1.1.2.1</td>
            <td>3.14159 26535</td>
        </tr>
        <tr data-tree-level="3">
            <td>Item 6</td>
            <td>1.1.2.2</td>
            <td>3.14159 26535</td>
        </tr>
        <tr data-tree-level="0">
            <td>Item 7</td>
            <td>2</td>
            <td>3.14159 26535</td>
        </tr>
        <tr data-tree-level="1">
            <td>Item 8</td>
            <td>2.1</td>
            <td>3.14159 26535</td>
        </tr>
      </tbody>
</table>

<script type="text/javascript">
  var table = document.getElementsByTagName("table")[0];
  treetableModule.initializeTable(table);
</script>

What kinds of treetable informations are in this table?

Initialization,
- whether the tree should be initially expanded: data-tree-expanded="...",
- and which column is to be the tree column: data-tree-column="..."
the 0-n tree level for each row: data-tree-level="..."

No ids are needed, no parent-child associations. But there is another necessity:

rows must be in a depth-first traversal order

Depth-first traversal order is the shape of the tree when it is fully expanded, so this is a quite natural thing.

How this HTML table is turned into an expanding treetable is subject of the JavaScript to be introduced now. The script has about 200 lines of code. It does not use any external JS library. I will introduce each part of it piece by piece, and you can find the full source code on bottom of this page.

Because it is so beautiful :-), here is the collapsed variant of above treetable, with the tree being in second column:

Item	Chapter	PI
Item 1	1	3.14159 26535
Item 2	1.1	3.14159 26535
Item 3	1.1.1	3.14159 26535
Item 4	1.1.2	3.14159 26535
Item 5	1.1.2.1	3.14159 26535
Item 6	1.1.2.2	3.14159 26535
Item 7	2	3.14159 26535
Item 8	2.1	3.14159 26535

The Beast

When we want to write a JavaScript that turns a table into a treetable, we face following problems:

set an expand control to every parent row into the column where the tree should reside
store the state whether a row is expanded or collapsed into that very row
calculate and realize the indentation that expresses the tree level of every row
determine the parent/child relations, i.e. find the child rows for each parent row
toggle the expand control to a collapse symbol on click, and reverse, and make rows visible or invisible on that event
avoid that expanding or collapsing rows resizes the tree column, i.e. keep that constant without hiding anything

Store collapsed/expanded state into rows

I chose CSS classes to store the state, because this also could be used for additional state-stylings. To find out whether a row is expanded I check its CSS classes to contain the class "expanded". To set it expanded, I add the CSS class "expanded", and at the same moment also change its expand control to the new state (that way the two always should be "in sync").

  var expandSymbol = "\u25B8"; // triangle right unicode
  var collapseSymbol = "\u25BE"; // triangle down unicode

  var EXPANDED_RE = /\bexpanded\b/;
  var COLLAPSED_RE = /\bcollapsed\b/;

  var isExpanded = function(element) {
    var expanded = EXPANDED_RE.test(element.className);
    var collapsed = COLLAPSED_RE.test(element.className);
    return expanded ? true : collapsed ? false : undefined;
  };

  var setExpanded = function(row, expand, treeCellColumn, expandSymbol, collapseSymbol) {
    var expandControl = row.children[treeCellColumn].children[0];
    if (expand === true) { // expand folder
      row.className = row.className.replace(COLLAPSED_RE, "");
      row.className += " expanded";
      expandControl.innerHTML = collapseSymbol;
    }
    else if (expand === false) { // collapse folder
      row.className = row.className.replace(EXPANDED_RE, "");
      row.className += " collapsed";
      expandControl.innerHTML = expandSymbol;
    }
    else { // leaf item
      row.className = row.className.replace(EXPANDED_RE, "");
      row.className = row.className.replace(COLLAPSED_RE, "");
      expandControl.innerHTML = "";
    }
  };

Both functions work with the JS property "className". The isExpanded() function could be shorter, but by testing for both states it works precise and returns undefined when there is no state at all.

The setExpanded() function removes the old state and then appends the new state. The regular expression EXPANDED_RE can be read as a word boundary, followed by "expanded", followed by another word boundary. Regular expression word boundaries \b are start of text, space, tab, newline, and end of text.
The setExpanded() function also sets a new expansion symbol into the expand-control of that row. We haven't yet created that expand-control.

Determine parent/child relations

This is the core part of the script. We need to dynamically determine the child rows of a parent row, and, in the same manner, which of the rows are parent rows. i.e. can be expanded or collapsed.

To do this we need the levels of the rows, which is given by the data-tree-level. So we just need to read that attribute and turn it into a number. Having (1) the level, and (2) the assumption that rows are in depth-first-traversal order, we can loop them and find out which of them are parent rows: those that have at least one follower row with a level higher than their own level.

We do this loop initially to set an expand-control into every row that is a parent, and a placeholder to all other rows (placeholder needed for tree-indentation). We do this also on every expand/collapse click to determine which rows must be set visible or invisible.

On collapse clicks we must set all children below the clicked row invisible, recursively.
On expand clicks we must set all direct children of the clicked row to visible, and also the children of all expanded children, recursively. We must not set the children of collapsed children visible. This is the reason why we need a stored expansion state in every row.

  var getLevel = function(row) {
    return parseInt(row.getAttribute("data-tree-level"), 10);
  };

  var isBelowExpandedParent = function(baseLevel, childLevel, parents, precedingItem) {
    var levelChange = childLevel - baseLevel - parents.length - 1;
    if (levelChange < 0)
      for (var i = 0; i > levelChange; i--)
        parents.pop();
    else if (levelChange === 1)
      parents.push(precedingItem);
    else if (levelChange > 1)
      throw "Treetable items are not in a depth-first order!";

    for (var i = 0; i < parents.length; i++)
      if ( ! isExpanded(parents[i]) )
        return false;

    return true;
  };

  var findSubTree = function(row, onCollapse) {
    var baseLevel = getLevel(row);
    var parent = row.parentElement;
    var collection = [];
    var inSubTree = false;
    var parents = [];
    var precedingItem;

    for (var i = 0; i < parent.children.length; i++) {
      var child = parent.children[i];
      if (child === row) { // before start of sub-tree
        inSubTree = true;
      }
      else if (inSubTree) {
        var childLevel = getLevel(child);
        if (childLevel > baseLevel) { // in sub-tree
          // on collapse all children are collected, recursively,
          // on expand only direct children or items below expanded parents,
          // not items below collapsed parents
          if (onCollapse ||
              childLevel === baseLevel + 1 ||
              isBelowExpandedParent(baseLevel, childLevel, parents, precedingItem))
            collection.push(child);

          precedingItem = child;
        }
        else { // end of sub-tree
          inSubTree = false;
        }
      }
    }
    return collection;
  };

Both isBelowExpandedParent() and findSubTree() functions are quite complicated. findSubTree() receives a row it must find a sub-tree for. A sub-tree includes all children recursively, not only direct children. It loops over all rows and sets a mark when it has found the given row. After that mark it collects children until the level is decreasing below the start-level.

To collect children for both expanding and collapsing case it considers the onCollapse flag. Is this true, it collects the entire sub-tree. Is this false, it collects only direct children, and such that are below a parent that is expanded. It leaves out the rows that are below a parent which is collapsed.

To keep track of the current parent in that loop, a sub-function has been coded. It receives all necessary state information from its caller function: the current level, the base level, a stack of parents and the previous row. It maintains the stack of parents by inserting or removing when level increases or decreases. Besides this function also checks the level progression and throws an error when the level increases by more than one (you can not see grand-children without passing the parent before).

With these functions we have the tree logic implemented.

Add listeners and implement expand/collapse callbacks

The "click" callback function must do two things: (1) set visible or invisible rows that have been found by findSubTree(), and (2) toggle the expand-control to visualize the new state.

  var toggleExpansion = function(row, isExpanded, treeCellColumn, expandSymbol, collapseSymbol) {
    if ( ! expandSymbol || ! collapseSymbol )
      throw "Lost symbols!";

    var subTree = findSubTree(row, isExpanded);
    for (var i = 0; i < subTree.length; i++)
      subTree[i].style.display = isExpanded ? "none" : "";

    if (subTree.length > 0)
      setExpanded(row, ! isExpanded, treeCellColumn, expandSymbol, collapseSymbol);
  };

  var addListener = function(expandControl, row, treeCellColumn, expandSymbol, collapseSymbol) {
    expandControl.addEventListener("click", function() {
      toggleExpansion(row, isExpanded(row), treeCellColumn, expandSymbol, collapseSymbol);
    });
  };

The addListener() function installs the callback into the browser and makes all given parameters available to that very callback. This is what is called "lambda" or "continuation": some variable values that will still be there, unchanged, whenever an event occurs. JavaScript provides that by default, in Java you would need to make all parameters final to achieve that.

The toggleExpansion() function then actually performs the state change. It finds the sub-tree of its given row, toggles its visibility state, and then exchanges the expand symbol and the current expansion state by calling the setExpanded() function defined above.

So now we solved most problem listed above. What remains to do is initialization, putting all together and bringing it to life.

Initialization

What is missing is inserting the expand-controls, and managing the tree column width. To do the first we loop all rows and simply prepend a newly created span element before the content of the td tree cell in that row. We then call toggleExpansion() on that row, which will set the state and the according symbol to the created expand control. Finally we add our callback listener to the "click" event of the expand-control.

Mind that the table is initially built like it was fully expanded, even when data-tree-expanded mandates that it should be collapsed. This is to measure the maximum column width of the tree column. To not provoke strange effects on the browser UI, the table is kept invisible while this is in progress. In a second initialization the collapsed state then gets established when needed.

  var invisiblyInitializeAndConfigureTable = function(
      treetable,
      treeCellColumn,
      initiallyExpanded)
  {
    var rows = treetable.getElementsByTagName("TR");
    var foundTreeCell = false;
    
    for (var i = 0; i < rows.length; i++) {
      var row = rows[i];
      var treeCell = row.children[treeCellColumn];

      if (treeCell) { // could contain no cells at all
        foundTreeCell = true;
        var level = getLevel(row);
        var expandControl = document.createElement("span");
        expandControl.style.cssText =
            "display: inline-block; "+ // force browser to respect width
            "width: 1em; "+
            "margin-left: "+level+"em; "+ // tree level indentation in "m"
            "margin-right: 0.2em; "+
            "cursor: pointer;";
        treeCell.insertBefore(expandControl, treeCell.childNodes[0]);

        toggleExpansion(row, initiallyExpanded, treeCellColumn, expandSymbol, collapseSymbol);

        addListener(expandControl, row, treeCellColumn, expandSymbol, collapseSymbol);
      }
    }
    return foundTreeCell ? rows : undefined;
  };

  var initializeAndConfigureTable = function(treetable, initiallyExpanded, treeCellColumn) {
    treeCellColumn = (treeCellColumn && treeCellColumn >= 0) ? treeCellColumn : 0;
    initiallyExpanded = (initiallyExpanded !== undefined) ? initiallyExpanded : false;

    treetable.style.visibility = "hidden"; // hide table until it is ready

    var rows = invisiblyInitializeAndConfigureTable(
        treetable,
        treeCellColumn,
        false); // to find out column widths, expand all initially

    if ( ! rows )
      throw "Found not a single tree cell at column index (0-n): "+treeCellColumn;

    var treeColumnWidth = rows[0].children[treeCellColumn].clientWidth;

    if ( ! initiallyExpanded ) // set the initial collapsed state
      for (var i = 0; i < rows.length; i++)
        toggleExpansion(rows[i], ! initiallyExpanded, treeCellColumn, expandSymbol, collapseSymbol);

    for (var i = 0; i < rows.length; i++)
      rows[i].children[treeCellColumn].style.width = treeColumnWidth+"px";

    treetable.style.visibility = "visible"; // show table
  };

The invisiblyInitializeAndConfigureTable() function inserts expand controls, called by initializeAndConfigureTable that sets the initial expansion state and the maximum column width.

Expand controls are styled to display: inline-block; to make the browser respect their width. This is essential for the tree indentation, set by "margin-left: "+level+"em;".

The width of the tree column is taken from first row's clientWidth and transferred as pixels to each td that is a tree cell.

With these two initialization functions we are ready to build any treetable, found by class or by id, whatever. For completeness here is the function that reads the initialization attributes from the heading table element.

  var initializeTable = function(treetable) {
    var treeCellColumnString = treetable.getAttribute("data-tree-column");
    var treeCellColumn = treeCellColumnString ? parseInt(treeCellColumnString, 10) : 0;
    var initiallyExpanded = treetable.getAttribute("data-tree-expanded") === "true";
    initializeAndConfigureTable(treetable, initiallyExpanded, treeCellColumn);
  };

Mind how the default for data-tree-expanded is set to false by comparing it to the string "true". Any other value than "true" would generate a value of false. Normally you don't want to have a tree fully expanded.

Full Source

Here is the full source for quickly trying this out.

"use strict";

var treetableModule = (function()
{
  var that = {};

  var expandSymbol = "\u25B8"; // triangle right unicode
  var collapseSymbol = "\u25BE"; // triangle down unicode

  var EXPANDED_RE = /\bexpanded\b/;
  var COLLAPSED_RE = /\bcollapsed\b/;

  var isExpanded = function(element) {
    var expanded = EXPANDED_RE.test(element.className);
    var collapsed = COLLAPSED_RE.test(element.className);
    return expanded ? true : collapsed ? false : undefined;
  };

  var setExpanded = function(row, expand, treeCellColumn, expandSymbol, collapseSymbol) {
    var expandControl = row.children[treeCellColumn].children[0];
    if (expand === true) { // expand folder
      row.className = row.className.replace(COLLAPSED_RE, "");
      row.className += " expanded";
      expandControl.innerHTML = collapseSymbol;
    }
    else if (expand === false) { // collapse folder
      row.className = row.className.replace(EXPANDED_RE, "");
      row.className += " collapsed";
      expandControl.innerHTML = expandSymbol;
    }
    else { // leaf item
      row.className = row.className.replace(EXPANDED_RE, "");
      row.className = row.className.replace(COLLAPSED_RE, "");
      expandControl.innerHTML = "";
    }
  };

  var getLevel = function(row) {
    return parseInt(row.getAttribute("data-tree-level"), 10);
  };

  var isBelowExpandedParent = function(baseLevel, childLevel, parents, precedingItem) {
    var levelChange = childLevel - baseLevel - parents.length - 1;
    if (levelChange < 0)
      for (var i = 0; i > levelChange; i--)
        parents.pop();
    else if (levelChange === 1)
      parents.push(precedingItem);
    else if (levelChange > 1)
      throw "Treetable items are not in a depth-first order!";

    for (var i = 0; i < parents.length; i++)
      if ( ! isExpanded(parents[i]) )
        return false;

    return true;
  };

  var findSubTree = function(row, onCollapse) {
    var baseLevel = getLevel(row);
    var parent = row.parentElement;
    var collection = [];
    var inSubTree = false;
    var parents = [];
    var precedingItem;

    for (var i = 0; i < parent.children.length; i++) {
      var child = parent.children[i];
      if (child === row) { // before start of sub-tree
        inSubTree = true;
      }
      else if (inSubTree) {
        var childLevel = getLevel(child);
        if (childLevel > baseLevel) { // in sub-tree
          // on collapse all children are collected, recursively,
          // on expand only direct children or items below expanded parents,
          // not items below collapsed parents
          if (onCollapse ||
              childLevel === baseLevel + 1 ||
              isBelowExpandedParent(baseLevel, childLevel, parents, precedingItem))
            collection.push(child);

          precedingItem = child;
        }
        else { // end of sub-tree
          inSubTree = false;
        }
      }
    }
    return collection;
  };

  var toggleExpansion = function(row, isExpanded, treeCellColumn, expandSymbol, collapseSymbol) {
    if ( ! expandSymbol || ! collapseSymbol )
      throw "Lost symbols!";

    var subTree = findSubTree(row, isExpanded);
    for (var i = 0; i < subTree.length; i++)
      subTree[i].style.display = isExpanded ? "none" : "";

    if (subTree.length > 0)
      setExpanded(row, ! isExpanded, treeCellColumn, expandSymbol, collapseSymbol);
  };

  var addListener = function(expandControl, row, treeCellColumn, expandSymbol, collapseSymbol) {
    expandControl.addEventListener("click", function() {
      toggleExpansion(row, isExpanded(row), treeCellColumn, expandSymbol, collapseSymbol);
    });
  };

  var invisiblyInitializeAndConfigureTable = function(
      treetable,
      treeCellColumn,
      initiallyExpanded)
  {
    var rows = treetable.getElementsByTagName("TR");
    var foundTreeCell = false;
    
    for (var i = 0; i < rows.length; i++) {
      var row = rows[i];
      var treeCell = row.children[treeCellColumn];

      if (treeCell) { // could contain no cells at all
        foundTreeCell = true;
        var level = getLevel(row);
        var expandControl = document.createElement("span");
        expandControl.style.cssText =
            "display: inline-block; "+ // force browser to respect width
            "width: 1em; "+
            "margin-left: "+level+"em; "+ // tree level indentation in "m"
            "margin-right: 0.2em; "+
            "cursor: pointer;";
        treeCell.insertBefore(expandControl, treeCell.childNodes[0]);

        toggleExpansion(row, initiallyExpanded, treeCellColumn, expandSymbol, collapseSymbol);

        addListener(expandControl, row, treeCellColumn, expandSymbol, collapseSymbol);
      }
    }
    return foundTreeCell ? rows : undefined;
  };

  var initializeAndConfigureTable = function(treetable, initiallyExpanded, treeCellColumn) {
    treeCellColumn = (treeCellColumn && treeCellColumn >= 0) ? treeCellColumn : 0;
    initiallyExpanded = (initiallyExpanded !== undefined) ? initiallyExpanded : false;

    treetable.style.visibility = "hidden"; // hide table until it is ready

    var rows = invisiblyInitializeAndConfigureTable(
        treetable,
        treeCellColumn,
        false); // to find out column widths, expand all initially

    if ( ! rows )
      throw "Found not a single tree cell at column index (0-n): "+treeCellColumn;

    var treeColumnWidth = rows[0].children[treeCellColumn].clientWidth;

    if ( ! initiallyExpanded ) // set the initial collapsed state
      for (var i = 0; i < rows.length; i++)
        toggleExpansion(rows[i], ! initiallyExpanded, treeCellColumn, expandSymbol, collapseSymbol);

    for (var i = 0; i < rows.length; i++)
      rows[i].children[treeCellColumn].style.width = treeColumnWidth+"px";

    treetable.style.visibility = "visible"; // show table
  };

  var initializeTable = function(treetable) {
    var treeCellColumnString = treetable.getAttribute("data-tree-column");
    var treeCellColumn = treeCellColumnString ? parseInt(treeCellColumnString, 10) : 0;
    var initiallyExpanded = treetable.getAttribute("data-tree-expanded") === "true";
    initializeAndConfigureTable(treetable, initiallyExpanded, treeCellColumn);
  };

  var initializeTables = function(treetables) {
    for (var i = 0; i < treetables.length; i++)
      initializeTable(treetables[i]);
  };

  var getClassTreetables = function() {
    return document.getElementsByClassName("treetable");
  };

  var initializeClassTreetables = function() {
    initializeTables(getClassTreetables());
  };

  var setExpandSymbols = function(expandSym, collapseSym) {
    if (expandSym)
      expandSymbol = expandSym; 
    if (collapseSym)
      collapseSymbol = collapseSym; 
  };

  that.initializeClassTreetables = initializeClassTreetables;
  that.initializeTables = initializeTables;
  that.initializeTable = initializeTable;
  that.initializeAndConfigureTable = initializeAndConfigureTable;
  that.getClassTreetables = getClassTreetables;
  that.setExpandSymbols = setExpandSymbols;

  return that;

}());

You can always visit my homepage for the current state of this utility.

fritzthecat-blog

Blog-Archiv

Dienstag, 31. März 2015

JS Treetable