The If-Then-Else Framework:
Coding branching logic without nested if’s
Part III: Enhancements To Support Scaling
Paul Corazza ()
Summary
In the first two parts of the article, Paul described in detail how to use the If-Then-Else framework to code complex branching logic. In this final part, he analyzes the performance of the framework and shows how to optimize algorithms and implementation choices, and how to minimize the risks involved in using the framework in larger-scale projects. The final product is a sleek, industry-ready upgrade of the prototype presented in previous articles, complete with new user options, a performance test harness, and automated safety features capable of handling thousands of conditions and rules.The If-Then-Else Framework is a tool for coding complex branching logic in a maintainable way. In the first two parts of this series, I described in some detail how to use the framework in a simple but typical case. I used this example as a means to illustrate most of the framework's features; in actual practice, however, the effort required to use the framework is more aptly rewarded when used in a more challenging context.
The purpose of this final installment is to study and solve the problems that arise when you do venture into more challenging territory with this framework. The refinements that I will discuss address the consequences of increasing the number of conditions, rules and actions. Using the framework without these refinements, you will find that, as the number of conditions, rules, and actions grows, performance can degrade rapidly, the order of evaluation becomes nearly impossible to keep straight, and the likelihood of introducing a pair of inconsistent rules increases quickly. In this article, I will identify the performance bottlenecks--involving in some cases algorithm selection and in others, Java implementation issues--and rewrite these critical sections; I will introduce a sequencing mechanism that will automate the bookkeeping involved in adhering to the order of evaluation; and I will introduce an automated consistency checker that will throw an exception if inconsistent rules have been loaded. And after all of it, the fundamental steps for using the framework, already described in Parts 1 and 2, will remain unchanged.
The discussion here will provide the reader with a number of concrete advantages. First of all, the final product of these refinements will be an industry-ready package that you can use reliably in any project that requires implementation of complex branching logic. Also, having worked through the modifications, you will have an advanced level of familiarity with the framework that will enable you to use its features to the fullest. Better still, you will see useful Java solutions to design and implementation problems -- these specific solutions, and the general problem-solving approaches that spawn them, can be reused in a variety of programming contexts. In that sense, this last part of the series offers a smorgasbord of advanced Java engineering techniques.
The focal point of the discussion will be a set of questions that I raised at the end of Part 2 and that I mentioned briefly above. Before formally stating these, I'll review some of the highlights of previous installments.
In order to get started with the framework, you perform a simple analysis of the logic that you need to code; in the analysis, you determine the conditions (the "if/else if" parts) and the resulting actions (the "then" parts), and you encapsulate these in instances of the classes Condition and Action, respectively. Actions are always performed on other objects; in the framework, in order for an object to be a recipient of an action, it must implement the Updateable interface, which involves implementing the doUpdate() method. Finally, in order to access the "rules engine" (the guts of the framework that will evaluate conditions and fire off actions), you need to load up rules that tell you which sequence of booleans will fire off which action -- these are loaded typically as part of initialization. And you need to load up the conditions that need to be evaluated -- these are typically determined sometime after initialization has completed. Both of these operations are performed in a user-defined subclass of the framework class Invoker by implementing the abstract methods loadRules() and loadConditions(), respectively.
Once you have taken these steps, you set the machinery in motion by creating an instance of the Invoker subclass (which calls the loadRules() method) and by calling the execute() method on this instance (which calls loadConditions() and passes the conditions and rules to the IfThenElse class, which in turn orchestrates the evaluation of conditions, the lookup of the appropriate action, and the execution of that action). Listing 1 displays the re-write of the URLProcessor_bad class, introduced in Part 1 as the central example of nested-if code; this rewritten version, called URLProcessor_good, employs the basic principles of implementing the If-Then-Else Framework:
Listing 1: The class URLProcessor_good with user-defined inner classes
class URLProcessor_good extends URLProcessor implements logic.Updateable {
static final String URL_STR = "urlString";
URLProcessor_good(){
super();
}
void decideUrl() {
try {
Invoker inv = new ConcreteInvoker((Updateable)this);
inv.execute();
}
catch(NestingTooDeepException ntde) {}
catch(IllegalExpressionException iee) {}
catch(RuleNotFoundException rnfe) {}
catch(DataNotFoundException dnfe) {}
}
/** Updateable interface implementation */
public void doUpdate(Hashtable ht) {
if(ht == null) return;
Object ob = ht.get(Action.MAIN_KEY);
if(ob != null & ob instanceof String) {
setUrl((String)ob);
}
}
static class OtherCondition extends Condition {
public static final String KEY = "key";
public OtherCondition(Hashtable ht) {
super(ht);
}
public Boolean evaluate() throws DataNotFoundException {
Object ob = null;
if(getData() == null || (ob = getData().get(KEY)) == null) {
throw new DataNotFoundException();
}
if(!(ob instanceof DataBank.Region)) {
return Boolean.FALSE;
}
DataBank.Region region = (DataBank.Region)ob;
boolean result = !region.equals(DataBank.WEST_REGION) &
!region.equals(DataBank.EAST_REGION);
return new Boolean(result);
}
}
static class MemberCondition extends Condition {
public static final String KEY = "id";
public static final String TABLE = "table";
public MemberCondition(Hashtable ht) {
super(ht);
}
public Boolean evaluate() throws DataNotFoundException {
Object id = null, table = null;
if(getData() == null || ((id = getData().get(KEY)) == null) ||
((table = getData().get(TABLE))==null) ||
!(table instanceof Hashtable)) {
throw new DataNotFoundException();
}
Hashtable members = (Hashtable)table;
return new Boolean(members.containsKey(id));
}
}
public class ConcreteInvoker extends Invoker {
public ConcreteInvoker(Updateable ud) throws NestingTooDeepException {
super(ud);
}
public void loadRules() throws NestingTooDeepException {
rules = new Rules();
try {
// Conditions: Actions:
// East|West|Other|Lim|Member
rules.addRule("TFFT*", new Action(ud,EAST_PRIVILEGED));
rules.addRule("TFFF*", new Action(ud,EAST_NOT_PRIVILEGED));
rules.addRule("FTFTT", new Action(ud,WEST_MEMBER_PRIVILEGED));
rules.addRule("FTFTF", new Action(ud,WEST_NONMEMBER_PRIVILEGED));
rules.addRule("FTFFT", new Action(ud,WEST_MEMBER_NOT_PRIVILEGED));
rules.addRule("FTFFF", new Action(ud,WEST_NONMEMBER_NOT_PRIVILEGED));
rules.addRule("FFT**", new Action(ud,OTHER_REGION));
}
catch(NestingTooDeepException e) {
throw e;
}
}
public void loadConditions() throws IllegalExpressionException {
try {
conditions = new Vector(5);
conditions.addElement(new Condition(db.getRegion(),DataBank.EAST_REGION));
conditions.addElement(new Condition(db.getRegion(),DataBank.WEST_REGION));
Hashtable other = new Hashtable();
other.put(OtherCondition.KEY,db.getRegion());
conditions.addElement(new OtherCondition(other));
conditions.addElement(new Condition(db.LIMIT_THRESHOLD, Condition.LESS,db.getLimit() ));
Hashtable mem = new Hashtable();
mem.put(MemberCondition.TABLE, db.getWestMembers());
mem.put(MemberCondition.KEY, db.getUserId());
conditions.addElement(new MemberCondition(mem));
}
catch(IllegalExpressionException e) {
throw e;
}
}
}
}
Listing 1 will provide a point of reference as I attempt to refine the framework's functionality. The following questions will provide a structure for the discussion:
Main Questions
- Order of evaluation. As you can see in Listing 1, the comments in the loadRules() method spell out the intended order of evaluation: I always consider conditions in the following order, whether I am loading conditions or creating a sequence of booleans:
East, West, Other, Limit, Member
But what happens when the number of conditions grows to 15 or 20? You can no longer expect to rely on a difficult-to-read set of notes in a documentation area as a means to guarantee strict adherence to a particular order of evaluation. Clearly, this part of the framework begs for an automated solution that can eliminate the human error that unavoidably creeps in with scaling.
- Performance. In Listing 1, you will notice that one of the exceptions that is handled in the decideURL() method (which is the point of control for handling exceptions) is the NestingTooDeepException. The framework will throw this exception whenever the number of Condition instances exceeds 30. Though in practice, you probably would never need that many conditions, you may wonder what dark secrets I am protecting by imposing this limit. As you will see, although there are fundamental technical reasons for this restriction, the more significant issue is performance: When the number of conditions gets too close to 30, performance becomes unacceptably slow. You can actually force the framework to falter badly with as few as 12 or 13 conditions (I will show how this works shortly). A review of the framework code will reveal one main reason for performance degradation--namely, more than one exponential-time algorithm. Some additional profiling will reveal another performance hit that has to do with the use of Java Hashtables. These considerations will lead us to implement some new algorithms, and to make a different choice of Java container classes.
- Consistency checking. In Part 2 of this series, I pointed out how a careless use of wildcards in the creation of boolean sequences can easily result in a pair of inconsistent rules. For clarity, I will define what I mean by these terms. First, recall that a rule is a match-up between a sequence of booleans (represented as a String of Ts and Fs, denoting true's and false's) and an Action instance that should be fired off whenever a sequence of Conditions evaluates to this particular sequence of booleans. (You create a rule every time you invoke the addRule() method in Rules.) I will say that two rules are inconsistent whenever they match the same boolean sequence to two different Action instances. For instance, the following lines of code would indicate that inconsistent rules have been loaded:
//assume that Action a and Action b are not equal
Action a = new Action(..);
Action b = new Action(..);
rules.addRule("TFTT", a);
.
.
.
rules.addRule("TFTT", b);
It is relatively easy to avoid explicit errors like this one; however, the following pair of inconsistent rules could easily be overlooked:
rules.addRule("*FTT", a);
.
.
.
rules.addRule("T*TT",b);
As I explained in Part 2, each of the boolean Strings *FTT and T*TT is actually treated by the framework as a pair of boolean Strings with no wildcards. The framework translates the two rules created above into the following four rules:
TFTT --> a
FFTT --> a
TTTT --> b
TFTT --> b
As you can see, after translation, the two original rules give rise to the pair of inconsistent rules
TFTT --> a and TFTT --> b.
It is not hard to imagine that if you had to manually key in a hundred or more rules, many with wildcards, you would eventually make one of these subtle mistakes--you would key in a pair that is, at least under framework translation, inconsistent. What makes this unacceptable, however, is that the framework provides no run-time consistency checking that would allow you to catch and correct such errors. As it operates now, the framework will handle the creation of these rules as follows: It will silently overwrite the first rule involving TFTT with the second rule involving this String, and will therefore always execute Action b when it encounters TFTT.
Below, I will suggest a consistency-checking mechanism. I will also discuss the performance hit that such a mechanism must inevitably cause.
Order of Evaluation
In order to reduce the risk of error in adhering to a chosen order of evaluation, I need to automate the procedure that guarantees that the same order is used in loading conditions as is used in building up boolean Strings during the phase of loading rules. To do this, I need to move the specification of the order out of the comments section and into the code, and then use this piece of code to properly arrange the conditions and the boolean Strings as they are loaded.
One simple observation that suggests how to begin is that I can always specify a unique ordering of any set of objects by mapping them in a one-to-one way into the integers. So, I can accomplish my objective of specifying an order of evaluation within the code by using integer constants having names that correspond to the conditions that I happen to be using. I can then use these constants to ensure a proper order of loading in both the loadRules() and loadConditions() implementations.
A handy way in Java to specify a set of constants for a class is to define them in an interface and require the class that uses the constants to implement this interface. Below, I have created an interface OrderOfEvaluation which specifies constants for the sample code I have been considering (see Listing 1) -- the inner class ConcreteInvoker will now need to implement this new interface in order to have direct access to the constants.
public interface OrderOfEvaluation {
final int EAST_CONDITION = 0;
final int WEST_CONDITION = 1;
final int OTHER_CONDITION = 2;
final int LIMIT_CONDITION = 3;
final int MEMBER_CONDITION= 4;
}
To make use of these constants during loading, I introduce wrappers, called sequencers, that will wrap the target container class in a larger class that will know how to use the constants to maintain proper order. Each sequencer will provide an "add" method that will permit framework users to add conditions and rules in a familiar way. However, the method will require that the condition or rule be passed in with the appropriate constants. Then, the sequencer will directly place the condition or rule in its proper location in its target container class.
To show how all this works concretely, I have rewritten the loadConditions() and loadRules() methods of Listing 1, making use of sequencers. Let's begin with loadConditions() since it is the easier of the two. Here is the code for the conditions sequencer:
public class ConditionSequencer {
Vector conditions;
public ConditionSequencer(Vector conditions) {
this.conditions = conditions;
}
public void addCondition(Condition c, int position) throws RuleNotFoundException {
if(conditions == null) throw new RuleNotFoundException();
if(position >= conditions.capacity()) throw new RuleNotFoundException();
conditions.insertElementAt(c, position);
}
}
You instantiate ConditionSequencer by passing in the Vector of conditions that you need to load. You can then add conditions one-by-one using the addCondition() method. Notice that this method requires you to pass in the position at which the condition should be inserted in the conditions Vector. To do this, you just need to pass in the interface constant that corresponds to the particular condition. The sequencer then places the passed in condition in the specified location in conditions. You will also note that a RuleNotFoundException will be thrown if you fail to initialize conditions or fail to set its capacity to a sufficiently large value. (So, in this case, before using the sequencer, you would initialize the conditions Vector with the total number of conditions.) The reason I chose to use this particular exception at this point in the framework is that the loadConditions() method is part of the overall process in which the user is requesting the framework to look up a rule and fire off an action, initiated by the call to Invoker to execute(). The code displayed below shows how you would begin to rewrite the loadConditions() method in Listing 1, using this new approach:
public void loadConditions() throws IllegalExpressionException, RuleNotFoundException{
try {
conditions = new Vector(numConditions);
ConditionSequencer sequencer = new ConditionSequencer(conditions);
sequencer.addCondition(new Condition(db.getRegion(),DataBank.EAST_REGION),
EAST_CONDITION);
sequencer.addCondition(new Condition(db.getRegion(),DataBank.WEST_REGION),
WEST_CONDITION);
. . .
}
catch(Exception e){}
}
The technique for sequencing rules is similar but slightly more complicated. The step in the process of loading rules that requires attention to the order of evaluation is in the assembly of boolean Strings. A String like TFTF has been assembled properly only if the T at position 0 signifies that the 0th condition evaluates to true, and the F at position 1 signifies that condition number 1 evaluates to false, etc. I can use the interface constants to ensure that this match-up is occurring correctly by encapsulating the requirement in a small class that contains both a boolean value and the name of the condition to which it is supposed to refer. I call this class a ConditionValue -- a skeleton of the class appears below:
public class ConditionValue {
public ConditionValue(int pos, char c);
public char getValue();
public int getPosition();
public void setPosition(int pos);
public void setValue(char c);
}
The instance variable value in the class will always be a 'T', 'F' or '*'. And the variable position will always store the value of the appropriate interface constant.
Using this approach, arranging Ts and Fs into a boolean String amounts to placing ConditionValue instances into a set. I don't need to worry about arranging these in the correct order because all necessary information about preserving correct order is stored in the individual ConditionValues. Therefore, we need to create a class that plays the role of a Set in order to contain a collection of ConditionValues. Java 1.2 provides an interface Set for the creation of just the kind of class needed here; however, since I want to make this framework accessible to JDK 1.1 users, I have not made use of the new Collections API. Below I list a skeleton of the class that I will be using; it provides most of the methods that any implementation of the data type "set" should provide, specialized to my needs here:
public class ConditionValueSet implements Enumeration {
//constructors
public ConditionValueSet();
public ConditionValueSet(ConditionValue cv);
//public methods