How to implement a decision tree in javascript. Looking for a better solution than my ugly ones

Question

I'm looking for a better way to implement a decision tree in javascript. Being very new to programming I have a very limited number of tools in my toolbox. The only ways I know to do this are: .with a huge ugly hard to maintain and follow if else if statement .I could use a switch/case statement and do a state machine type thing.

Suggestions and theories are appreciated. Also, small code examples would be very helpful. Thanks for taking a look.

Dale

Solution 1

If it is a really big tree, and especially if it is generated from data, you could treat the decision functions like data, using a functional approach. For example:

var decisionTree = 
    new Case( true, Array(
                  new Case ( function(n){ return n < 0; }, Math.sin ),
                  new Case ( function(n){ return n < 2; }, "0<= n < 2" ),
                  new Case ( true, "Greater than two " )));

decisionTree.evaluate(1); // evaluates to string "0<= n < 2"
decisionTree.evaluate(-Math.PI/2); // evaluates to -1
decisionTree.evaluate(5); // evaluates to string "Greater than two"

Using this implementation, you can arbitrarily nest your tree:

// Represents a predicate and corresponding action to take if predicate is a
// match.
//
// predicate : true or Function( object ) returning a boolean.
//
// action : One of Function, Case, Array of Cases or other value (see
//          Case.evaluate as to how each is applied)
//
//
Case = function (predicate, action) {  
    this.predicate = predicate;
    this.action = action;
};


Case.prototype = {
    nomatch : { match : false },
    match : function (v) { return { match : true, result :v }; },


    // Recursively test Cases and applies corresponding action on
    // `object`.
    //
    // The action applied depends on the datatype of `action`:
    //
    // - Function : evaluates to `action( object )`
    // 
    // - Case : A subsequent test is performed.  Evaluates to whatever
    //          the Cases action evaluates to.
    //          
    // - Array of Cases : Subsequent tests are performed.  Evaluates to whatever
    //          the action of the first matching Case evaluates to.
    //
    // - Any other Value : Evaluates to itself
    // 
    // returns object containing fields:
    //
    //     match:  boolean, indicates if Case was a match
    //
    //     result:  result of action applied
    // 
    evaluate : function( object ) {
        var match = this.predicate;

        if ( match instanceof Function )
            match = match( object );

        if ( match ) {

            if (this.action instanceof Function )
                return this.match( this.action(object) );

            if ( this.action instanceof Case )
                return this.action.evaluate( object );

            if ( this.action instanceof Array ) {
                var decision;
                var result;
                for (var c = 0; c < this.action.length; c++ ) {
                    decision = this.action[c];
                    if ( decision instanceof Case )  {
                        result = decision.evaluate( object );
                        if (result.match)
                            return result;
                    } else throw("Array of Case expected");
                }

                return this.nomatch;
            }

            return this.match(this.action);
        } 
        return this.nomatch;
    }
};

Solution 2

The best practice for this sort of thing is to nest if-then statements in a meaningful way, and then put them in their own function bodies. A function should never have more than 2 nested if's; after that, it is acceptable to put further nested if's in functions which are named and implemented well, thus abstracting the complexity of the program while retaining its meaning for the programmer who will read your code after you're gone. :)

Comments

[Dale]

I like that answer. My problem isn't nested if-then statements. I don't have any nested ifs. I have one if(else if) statement for each leaf of the tree that does something. So I've put all of my complexity into computing the conditional. Is it more desirable to nest them and abstract the nesting inside functions as you suggested? Thanks.

[djhaskin987]

It is most often desirable to abstract nesting or long if-then chains when it is unclear what it does or if it's hard to read. This gives much more readability to your program (in any language) when small functions are used to abstract hard-to-understand things such as long if-then chains. As a rule of thumb, if you have to write a comment about what a particular if-then statement does or why it's there, it's better just to put it in it's own well-named function rather than comment it. Your co-workers will thank you.