Blog Archive

Home
Filter by: Javascript Primer

treebeard-the-ent-e1269783419659Organizing data so that you sort, filter or manipulate items efficiently is critical for front end applications.  These days its not enough to have a pretty design – it’s gotta like do some stuff.  Just sayin’.  It would be silly if you had to constantly send requests back to a server just filter them, or sort them in a new order.

Sometimes you might be asked to support hierarchical or nested data.  A perfect example is a project plan: there are levels and nested levels; there is an implied relationship between the parent levels and their children; the order of the list items implies a precession, or a progression.  Consider also thate each list item not only has a task, but also has the duration for that task, and you have to total all the durations for an estimate.  Perhaps your crazy manager asks you to only fetch the tasks where a certain team member works, oh, and by the way, exclude all the tasks that are parent level tasks.  As you can see, there is a need for a structured approach that you can easily re-use.

Simple Nested Structures May Not Be Enough

In general, creating nested data structures is fairly straight forward.  Let’s continue with our scenario of a project plan:


var Task = function (options) {
    var _options = options || {};

    var _description = _options.description || "";
    var _assignedTo = _options.assignedTo || "";
    var _duration = _options.duration || 0.0;

    var _tasks = [];

    return {
        description: _description,
        assignedTo: _assignedTo,
        duration: _duration,
        tasks: _tasks
    };
};

We will represent each project item as a Task that has a description, the team assigned to the task and a duration. The array “_tasks” represents the sub tasks or children of a task. You can indeed represent a hierarchy by simply adding this array and achieving what ever nesting levels that you desire.  This jsFiddle illustrates what that would look like.

While this does the job, how are you going to provide filtering? We need a way to walk the hierarchy; furthermore, we don’t want a one time function for type of traversal. Also, how do we handle the times when we need to affect a change only to items that are two levels deep. Simple recursion will not be enough here.

TreeNodes Can Provide Help

What we need is a data structure that will tell us where we are in the hierarchy of data items; who the parent of an item is, and if there are any children for a particular item. Once we can obtain these, performing operations are much easier, and we can answer questions like “What are all the tasks that over 10 hours” or “what are all the tasks for ‘POC Development’”.  Being able to walk the hierarchy will also give us the capability to automatically calculate the overall hours for a project.

var TreeNode = function (options) {
        var _options = options || {};

        var _value = _options.value || {};
        var _children = _options.children || [];
        var _parent = _options.parent || null;

        //  Public methods
        var isRoot = function () {
            return (_parent == null);
        };

        var level = function () {
            return isRoot() ? 0 : _parent.level() + 1;
        };

        var addChild = function (value) {
            var childNode = new TreeNode({ value: value, parent: this });
            _children.push(childNode);

            return childNode;
        };

        return {
            value: _value,
            children: _children,
            parent: _parent,

            //  public methods
            isRoot: isRoot,
            isLeaf: isLeaf,
            level: level,
            addChild: addChild
        };
    };

Let’s dissect this a bit. A TreeNode will wrap an object; more specifically “_value” will be the container for our Task object. “_children” is an array of TreeNodes that each wrap another Task object. A TreeNode can have a “_parent”, so naturally any item the _children array will “point” back a single TreeNode. This establishes our relationships between tasks and sub-tasks. In some scenarios you have a TreeNode and need to a property for that TreeNode’s parent, and “_parent” offers that convenience.

The function “isRoot()” tells us that we are at the top of a hierarchy. “level()” tells us what level a TreeNode sits at. Looking at this code you’ll note that it relies on “isRoot()” to determine whether to return a 0 or simply increment the “_parent.level”. To create your hierarchy, simple call TreeNode.addChild(new Task);

If you look at the jsFiddle you’ll see that we have a hierarchy established, and the path of “Check Team Schedule” can represented as tasks[3].tasks[0].tasks[2].  If we were to set a variable to tasks[3].tasks[0].tasks[2] we are disconnected from our hierarchy, as the individual items sitting in each “tasks” array are unaware of their parents.  In order for us to start any filtering or querying, we will first have to pull the tasks apart and re-assemble them as TreeNodes.  Luckily we can create a function to build a tree from our Task objects:

var treeFuncs = function(){
    var buildTaskTree = function (sourceTasks) {
        var tree = new TreeNode({
            value: "ROOT"
        });

        var taskStack = [];
        var treeNodeTargetStack = [];

        taskStack.push(sourceTasks);
        treeNodeTargetStack.push(tree);

        while (taskStack.length > 0) {
            var currentTask = taskStack.pop();
            var targetNode = treeNodeTargetStack.pop();

            var length = currentTask.length;
            for (var i = 0; i < length; i++) {
                var task = currentTask[i];
                var childNode = targetNode.addChild(task);

                if (task.tasks.length > 0) {
                    taskStack.push(task.tasks);
                    treeNodeTargetStack.push(childNode);
                }
            }
        }

        return tree;
    };

    return {
        buildTaskTree: buildTaskTree
    };
};

The function buildTaskTree accepts an array of Task objects. Next, we will create a root for our TreeNodes, and all other child TreeNodes will be added to this variable. Instead of using recursion, we will create two stacks “taskStack”, where we will store all the Task objects, and “treeNodeTargetStack” will hold the current TreeNode that will receive new children. Note that we are “seeding” the “taskStack” with the incoming array of Task objects. “targetTreeStack” will have the “tree” variable that is the root of the tree that we are building.

The while loop will always pull from the taskStack; more specifically, the first pass will have the top level tasks “Discuss Product Concept”, “Create Mockups”, “Setup POC environment”, “POC Development” from our project plan. We look at each item and add it to the current position of the tree. If the current Task has children we will want to do two things:

  1. Push the child tasks array onto the “taskStack”. When we execute the loop again, it will pick up this new entry and continue our processing.
  2. Push the newly created child TreeNode onto the treeNodeTargetStack so that we maintain the hierarchy between the tasks. The next time we execute the while loop, we are the current TreeNode and add to its children. This maintains our hierarchy relationships.

That’s it. Each subsequent pass of the while loop drives deeper into Tasks hierarchy as each child is added to “taskStack”. When we’re done, we return “tree” as our TreeNode structure.

How To Put TreeNodes To Good Use

Great. We have TreeNodes. Now what? Well, our goal was to create structure that we could traverse and always know who our parent was, and who our children were, as well as creating the ability to determine what level in the hierarchy we are located.  To find answers to questions that require us to filter, sort, etc we will visit each node on the TreeNode structure, and at each stop we will perform a function that will act as our query and record the result for that node.  When the trip is done we’ll have a subset of our tree.

First the function that walks the TreeNode:


var traverseAndApply = function (treeNode, func, functionArgs) {
        var treeNodeStack = [];
        var rootArray = [];
        rootArray.push(treeNode);

        treeNodeStack.push(rootArray);

        while (treeNodeStack.length > 0) {
            var currentNodeList = treeNodeStack.pop();
            var length = currentNodeList.length;

            for (var i = 0; i < length; i++) {
                var currentNode = currentNodeList[i];
                if (currentNode.parent != null) {
                    func(currentNode.value, currentNode, functionArgs);
                }

                if (currentNode.children.length > 0) {
                    treeNodeStack.push(currentNode.children);
                }
            }
        }
    };

The function traverseAndApply accepts three arguments. The argument “func” is a function, and this is the function that will executed at each node in the TreeNode. “functionArgs” are the items that will be pass into the “func”. The remainder of his function may look familiar – the approach is the same as in buildTaskTree. Again, we are avoiding recursion and are using the stack approach. We push the TreeNode to an array, then push the array onto a stack. As we loop, we pull each TreeNode, fire off “func”, then progress to the next.

So let’s put this to use. Our first example will be to find all tasks that are the top level tasks, in the parlance of our TreeNode, where the TreeNode.level() is equal to 1.


var treeNode = _treeFuncs.buildTaskTree(_tasks);

        var matchTopLevelArgs = {};
        matchTopLevelArgs.results = []

        var matchTopLevelFunc = function(value, node, funcArgs){
            if(node.level() == 1){
                funcArgs.results.push(value);
            }
        };

        _treeFuncs.traverseAndApply(treeNode, matchTopLevelFunc, matchTopLevelArgs);

And now let’s find all of Frodo’s tasks that are not top level tasks:

var treeNode = _treeFuncs.buildTaskTree(_tasks);

        var frodoTasksArgs = {};
        frodoTasksArgs.results = [];

        var frodoTasksFunc = function(value, node, funcArgs){
            if((value.assignedTo.indexOf("Frodo") > -1) & (node.level() != 1)){
                funcArgs.results.push(value);
            }
        };

In our jsFiddle you’ll find working versions of the above filter examples. Experiment around and see what you can come up with.

Future Considerations

Now that we have the basics down you can see that we have a very powerful tool. No doubt you have noticed that the hours for our project don’t make sense, as normally the duration of a task is comprised of the duration of any sub-tasks. Since we can visit each node, we may be able to devise a way to create a function that can calculate the duration for each level appropriately.

Another idea could also be the ability to change a task to sub-task or maybe make a sub-task into a new parent.  Our ability to manipulate the TreeNode and it’s underlying data can go a long for us.  So that’s what we will explore next time.  Until then, play the video below and enjoy some tree music.

This post is in our Javascript Primer series, a collections of articles aimed at .Net and back-end developers who are transition to client-side UX development.  In a previous installment, the topic of publish-subscribe design pattern was featured, and this pattern fostered loosely coupled ViewModels.  It is recommended that you read that post as well, as this edition of our primer builds on those concepts.

A basic tenant to good programming is to break down activities to small components.  Smaller functions are easier to maintain.  In many instances the information that the users are working with is best presented in logical groups, dissected so that an improper decision can never be made.  A rich user interface may force you to break a larger object into several ViewModels.  But guess what?  If you need to break information down, will also need to re-assemble this information to transmit back to mother ship to be stored in your database.

Challenges for the ViewModels

There are several challenges ahead for you if need your ViewModels to communicate, and you want to retain the agility provided to you with loose coupling.  If you recall the architecture we established with the publish and subscribe design pattern, all our “pieces” are highly independent from one another.  But we now have a complication.  Independence also means blissful ignorance.  Each ViewModel only knows how to contribute their small portions of information for glorious “mother object”.  The best it can is yield up what it has and somehow, someway, something will piece things together.

Let’s consider a code example:

We have simple project tracker that has a name, a roster of workers and a calendar that displays each workers start date.  Each tab is serviced by a ViewModel.  The “Project Info” tab shares the project name information with “Team”.  The tab “Team” shares the project team data with both the “Project Info” and the “Timeline” tabs.  This is accomplished using the publish and subscribe pattern that was detailed in this post.  You should review that post is your are unfamiliar with postaljs or with the publish and subscribe design pattern.

The challenge here is that we want a “Save” button that will easily gather the data from each tab and save it our project object.   We also want this controlling activity to be flexible and allow each ViewModel to supply the data needed without too much orchestration: in other words, we just ask the ViewModel “What do you have for a project object”, and each ViewModel fulfills its responsibility.

Pipe and Filter Pattern For Chaining Events or Commands

Many of you with a background in server side application development may recognize the pipe and filter pattern.  Simply said, it is a way to chain a set of operations that are to be performed in succession.  This diagram is a depiction of the pipe and filter:

PipesAndFilters

The “Filter” is a function that performs one thing.  Our pipe is the “orchestrator” or directory in that it will forward to each filter as ordered.

For our purposes we will continue to use postaljs as our communication mechanism.  We’ll need a pipeline that will keep track of which filter to execute and forward data to each subsequent filter of the process chain.

var pipeline = {
  index: 0,
  filters: ["edit.getViewOneData","edit.getViewTwoData","edit.finalDestination"]
 };

The property “filters” contains the names of the postaljs topics that will kick off a function.  In this case we will need 3 subscriptions that listen for items listed in the “filters” array.  Each process step, or filter, will be executed in the order that listed in the “filters” array: in this case, “edit.getViewOneData” will be executed first.  The property “index” tracks which filter is being processed.  As each filter is executed, it will increment index, then use index to access the next topic in the chain of events.  Starting off the process is accomplished in this fashion:

// Now start up the pipeline, fire off the first step that will execute the first filter
 postal.publish({
  channel: "pipenfilter",
  topic: pipeline.filters[pipeline.index],
  data: pipeline
 });

//  A sample subscription.  This will be executed first since it is listed first in the pipeline.filters array
postal.subscribe({
  channel: "pipenfilter",
  topic: "edit.getViewOneData",
  callback: function (pipeline, env) {
    fetchViewOneData(pipeline);
}
 });

//  After filter performs, it needs to call the next filter in the chain<
var fetchViewOneData = function(pipeline){
  // ... perform activities with some data

  //  To forward to next step, increment the index
  pipeline.index++;

  //  Now forward to the next filter
  postal.publish({
    channel: "pipenfilter",
    topic: pipeline.filters[pipeline.index],
    data: pipeline
  });
};

For our particular scenario with the project UX above we will have to do a few simple things:

  1. The ViewModels “ProjectInfo”, “Budget” and “Team” will need subscriptions to a “pipenfilter” channel
  2. Each ViewModel will need a corresponding filter function, so the “Team” ViewModel will get a “fetchTeamFilter”
  3. Add an endpoint in our $(document).ready section to act as a controller for the pipeline process.  Since we don’t have a controller this logic can sit here.  Naturally for cleaner production code you’ll want to be a bit cleaner and place this in a controller object.

All of the addition changes are noted with a “New pipe and filter” comment, so you can search through the Javascript to see where the changes have been made.  Most of the updates are just a few lines, and the nice thing is that the code to forward to the next filter is the same each time.  Not much exciting stuff to be seen other than incrementing the index and passing the data to the next topic.

Where No One Has Gone Before (just sayin’)

Now that you can synchronize your data, assemble it back into a proper object, you can begin your next journey.  There’s many long term benefits here that you will begin to realize.  What if you need to add an additional ViewModel, or what if you need to change which ViewModel display the groupings of data?  Without our pipe and filter solution, you would need to change a lot of things.  With what we have described here, the most that have to do is to add an additional filter name to the pipeline list and make sure that your additional ViewModel functioned properly.  The other ViewModels are left untouched.

Another benefit is also be that you can control what functions are fired while allowing the ViewModels to do their thing.  What if you had a ViewModel that published changes to other ViewModels after it finished performing calculations.  By ordering the filters in the pipeline accordingly, you can allow the ViewModels to do that hard work and be assured that all aspects of your data is up to date.  Doing more with less code means you can test and maintain this code with confidence.


ActiveEngine Software by ActiveEngine, LLC.