0

I need to check certain conditions (of size n) on an object and perform one of several options available (size m) based on the result. Seems to me it fits a tree.

Now. The tree is quite large and I wonder if there's a way to reduce it.

Here's a sample of it

The conditions are marked as c1,...,cn and the functions to perform are marked as f1,...,fm (the crossed zeros are dont-care values)

enter image description here

  • 2
    have a look at Karnaugh maps – devnull May 7 '15 at 7:13
  • 1
    possible duplicate of How to turn truth table into smallest possible if / else block – gnat May 7 '15 at 7:15
  • @devnull but Karnaugh maps produce a binary output no? in my case the outcome isn't binary – Yoni Levy May 7 '15 at 7:19
  • @gnat: I consider this question to be more specific than the possible duplicate. It might be that the actual case (unlike the one shown in the table) has a non-uniform tree, where some nodes are only two levels deep, while others are eight levels deep. In the possible duplicate, the answers will force to have the same depth, which can lead to severe and very problematic duplication if the number of branches is big. – Arseni Mourzenko May 7 '15 at 7:54
  • 1
    @YoniLevy there is nothing preventing you from replacing the 1 and 0 with different values. The implication of grouping the values together is the key concept of the Karnaugh map and applicable here. – user40980 May 7 '15 at 14:25
4

Indeed, a tree is a good data structure for that. You can then create a BST which will allow to find by lookup a specific action based on the c1 to cn conditions.

Obviously, this has a huge benefit of avoiding ugly code such as:

if (c1) {
    if (c2) {
        if (c3) {
            ...
        }
        ...
    }
    ...
}

Whether the BST can be simplified even more depends on the exact association between the conditions and the actions. Look for a pattern. Imagine what would happen if you put c1 after c2.

How do I search for the action?

If you express your conditions as an array of n elements [c1, c1, ⋯ cn], you can then search for the action either recursively or iteratively. For instance, a recursive approach would look like this:

var findAction = function (conditions, node) {
    // `shift` also removes the element from the array.
    var currentCondition = conditions.shift();

    if (typeof node !== 'boolean') {
        return node;
    }

    return findAction(conditions, node[currentCondition]);
}

which can be called like this:

var conditions = [false, false, true, false];
var tree = {
    true: {
        true: f1,
        false: {
            true: f2,
            false: f1
        }
    },
    false: {
        true: {
            true: f5,
            false: f3
        },
        false: {
            true: {
                true: f2,
                false: f6
            },
            false: f4
        }
    }
};


findAction(conditions, tree)(); // Will execute `f6`.

The Karnaugh map seems much easier...

It is, but it also has a limitation: all your leafs should be at the same depth. This is actually the case in the table you've shown, but may not necessarily be the case in the real problem you are attempting to solve.

If, for instance, some nodes are two levels deep while others are eight levels deep, with Karnaugh map, you have to align them to be eight levels deep, which will probably result in severe duplication (but not necessarily in reduced maintainability; it may actually be that maintainability will only increase). With a BST, you don't have to do that.

A simplistic example of the following BST:

var tree = {
    true: {
        true: f1,
        false: {
            true: {
                true: f2,
                false: f3
            },
            false: f4
        }
    },
    false: f5
};

will be expressed like this Karnaugh map:

var tree = {
    true: {
        true: {
            true: {
                true: f1,
                false: f1
            },
            false: {
                true: f1,
                false: f1
            }
        },
        false: {
            true: {
                true: f2,
                false: f3
            },
            false: {
                true: f4,
                false: f4
            }
        }
    },
    false: {
        true: {
            true: {
                true: f5,
                false: f5
            },
            false: {
                true: f5,
                false: f5
            }
        },
        false: {
            true: {
                true: f5,
                false: f5
            },
            false: {
                true: f5,
                false: f5
            }
        }
    }
};
  • The BST solution seems better – Yoni Levy May 7 '15 at 8:19
  • And Kudos for the very complete answer. – Yoni Levy May 7 '15 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.