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.

**PREPARING A TABLE**

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"];

**PRE-SORTING THE TABLES**

**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; } [/sourcecode] <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). <strong>DOING TABLE LOOKUPS IN PDQFORMS</strong> This stack-trace depicts the tax calculation mechanism: <strong>[PDQAbstractWidget evaluateExpression: theTableLookup]</strong> Table lookups are processed as a special case by evaluateExpression. e.g. =TAXTABLE("TAXTABLE","6",INCOME,FILING_STATUS) evaluateExpression calls doTableLookup. <strong>[PDQAbstractWidget doTableLookup: theTableLookup]</strong> doTableLookup is analagous to evaluateFunction, but for tableLookups. doTableLookup packages the call's parameters and calls "execute." Note that quoted parameters are passed in as literal strings. <strong>[NSString+PDQFunctionAdditions execute: parameterArray]</strong> execute dispatches the call to taxTableLookup. <strong>[NSString+PDQFunctionAdditions taxtablelookup: parameterArray]</strong> taxTableLookup unpacks the parameters, finds the taxBracket and uses it to determine the tax. <strong>[NSArray+PDQTableAdditions taxBracket]</strong> taxBracket is the recursive binary search algorithm, initially called from taxTableLookup, that does the "heavy lifting." taxBracket calls the helper routine taxInTuple <strong>[NSArray+PDQTableAdditions taxInTuple]</strong> taxInTuple tests to see if taxable income falls within a bracket, to its left, or to its right. If income isn't in the current tax bracket taxInTuple's return value is then used 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; } else if (comparison == 1) { tupleIndex = [self taxBracket: income tupleWidth: tupleSize startingWith: middleTuple+1 andEndingWith: lastTuple]; } else 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 Reply