June 23, 2009


Filed under: Uncategorized — frameworker @ 5:26 am

Since some tax forms use tables as well as formulae, I had to implement a tax table lookup algorithm. Things were complicated by the fact that these tables were not always available in sorted format.

I first tried using the unsorted tax tables. This required doing a comparison of each table entry until the proper tax bracket was found. But tax lookup tends to occur whenever you change any numeric field on the form, since this usually affects taxable income. So, doing a comparison for each entry, while easy, was way too slow! Suddenly I was seeing a totally unacceptable delay.

The solution was to pre-sort the tables, shifting the performance burden completely out of the user’s work flow, and then to use an efficient, recursive binary search, algorithm to do the table lookup in PDQForms.


Copy the table from the tax handbook into a text file and clean-out any patches of non-table data. Fortunately, the topology of non-table data is amenable to doing this, and also, the table data consists of an integral number of tuples on each line.

Finally, filter-out commas, and prepend TUPLESIZE to the table.

The table we’re creating will have the same name as the form it applies to, but with a suffix that’s specified in the call to createTupleTable. Here it’s “tax”.

    NSString * theTableContents = [self createTupleTable: theTableData named: @"tax"];


1. Put the elements (NSStrings) of each tuple into an array (NSArray)

2. Put these tuples into an array so they can be sorted.

3. Sort the array of tuples, from smallest to largest, using “sortedArrayUsingFunction”
and passing it the comparison function “sortByValue”:

    NSArray *sortedTuples = [tuples sortedArrayUsingFunction: sortByValue context: 0];

    NSInteger sortByValue(id tuple1, id tuple2, void *context)
        double value1 = [[tuple1 objectAtIndex: 0] doubleValue];
        double value2 = [[tuple2 objectAtIndex: 0] doubleValue];
        if      (value1 > value2) return NSOrderedDescending;
        else if (value1 < value2) return NSOrderedAscending;
        else                      return NSOrderedSame;


<strong>4.</strong> Convert the sorted tuples back into a single NSString.

<strong>5.</strong> Finally, "bake" the table data into the pdq file using PDFKit (10.5).


This stack-trace depicts the tax calculation mechanism:

<strong>[PDQAbstractWidget evaluateExpression: theTableLookup]</strong>
Table lookups are processed as a special case by evaluateExpression.  
evaluateExpression calls doTableLookup. 

&nbsp;    <strong>[PDQAbstractWidget doTableLookup: theTableLookup]</strong>
&nbsp;    doTableLookup is analagous to evaluateFunction, but for tableLookups.
&nbsp;    doTableLookup packages the call's parameters and calls "execute."
&nbsp;    Note that quoted parameters are passed in as literal strings.

&nbsp; &nbsp;        <strong>[NSString+PDQFunctionAdditions execute: parameterArray]</strong>
&nbsp; &nbsp;        execute dispatches the call to taxTableLookup.

&nbsp; &nbsp;                <strong>[NSString+PDQFunctionAdditions taxtablelookup: parameterArray]</strong>
&nbsp; &nbsp;                taxTableLookup unpacks the parameters, finds the taxBracket 
&nbsp; &nbsp;                and uses it to determine the tax.

&nbsp; &nbsp; &nbsp;                    <strong>[NSArray+PDQTableAdditions taxBracket]</strong>
&nbsp; &nbsp; &nbsp;                    taxBracket is the recursive binary search algorithm,
&nbsp; &nbsp; &nbsp;                    initially called from taxTableLookup,
&nbsp; &nbsp; &nbsp;                    that does the "heavy lifting."
&nbsp; &nbsp; &nbsp;                    taxBracket calls the helper routine taxInTuple

&nbsp; &nbsp; &nbsp;                <strong>[NSArray+PDQTableAdditions taxInTuple]</strong>
&nbsp; &nbsp; &nbsp;                taxInTuple tests to see if taxable income falls
&nbsp; &nbsp; &nbsp;                within a bracket, to its left, or to its right.
&nbsp; &nbsp; &nbsp;                If income isn't in the current tax bracket
&nbsp; &nbsp; &nbsp;                taxInTuple's return value is then used 
&nbsp; &nbsp; &nbsp;                to seed recursive calls to taxBracket.

taxBracket and taxInTuple are shown below.

- (int) taxBracket: (double) income 
        tupleWidth: (int) tupleSize 
      startingWith: (int) firstTuple 
     andEndingWith: (int) lastTuple
    int tupleIndex = -1;

    int comparison;

    int middleTuple = firstTuple+(lastTuple-firstTuple)/2;

    comparison = [self taxInTuple: income 
                          atIndex: middleTuple 
                       tupleWidth: tupleSize];
    if (comparison == 0)
        tupleIndex = middleTuple;
    if (comparison == 1)
        tupleIndex = [self taxBracket: income 
                           tupleWidth: tupleSize 
                         startingWith: middleTuple+1 
                        andEndingWith: lastTuple];
    if (comparison == -1)
        tupleIndex = [self taxBracket: income 
                           tupleWidth: tupleSize 
                         startingWith: firstTuple 
                        andEndingWith: middleTuple-1];

    return tupleIndex;

// Tuples are laid out end to end as one long array.
// The first two items of a tuple are its income bracket.
// the trailing items are the tax for each filing status
// in that tuple’s income bracket.
– (int) taxInTuple: (double) income
atIndex: (int) tupleIndex
tupleWidth: (int) tupleSize
int leftIndex = tupleIndex*tupleSize;
int rightIndex = leftIndex + 1;

NSString * leftItem = [self objectAtIndex: leftIndex];
NSString * rightItem = [self objectAtIndex: rightIndex];

double leftValue = [leftItem doubleValue];
double rightValue = [rightItem doubleValue];

// Test if intervals overlap:
// IF YES use <= for right value // IF NO use < for right value. // CA brackets don't overlap // they're [x,y] [y+1,z]. // So when income is exactly "y" // we want to match the ONLY bracket containing "y", // not the higher of two brackets! // One even, one odd means the intervals shouldn't "overlap." if ((int)leftValue%2 != (int)rightValue%2) { if ((income >= leftValue) && (income <= rightValue)) { return 0; } } else // IRS brackets are [x,y] [y,z] so when income is exactly "y" // we want to match the higher of the two brackets! { if ((income >= leftValue) && (income < rightValue)) { return 0; } } if (income < leftValue) { return -1; } else { return 1; } } [/sourcecode]


Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at

%d bloggers like this: