Word Prediction App Part 2: Adding Some O(nlogn) Searching to the List Filter.

The previous list filter utilized brute force in effort to focus on figuring out how Apple designed its MVC structure. Part 2 of the code only changes the model.

Here is the header:

@property (nonatomic, readwrite, strong) NSArray *tableData;
@property (nonatomic, readwrite, strong) NSArray *filteredList;

- (NSArray *)sortWithSquence:(NSString *)sequence;
- (NSArray *)getSubArray:(NSArray *)array bySeq:(NSString *)charSeq;
- (NSInteger) binarySearchForMutableStringArray:(NSArray *)array bySeq:(NSString *)charSeq findLast:(BOOL)last;

I made the arrays normal NSArrays as NSMutableArrays should only really be used if the model data is going to be changed. Since the idea is just to create smaller subarrays, NSArrays are more suitable.

Here is the main code now:

#import "ListModel.h"

@implementation ListModel

@synthesize tableData = _tableData;
@synthesize filteredList = _filteredList;

- (id) init
{
    if(self == [super init])
    {
        NSLog(@"Creating table data");
        
        // Path to the plist (in the application bundle)
        NSString *path = [[NSBundle mainBundle] pathForResource:
                          @"words" ofType:@"plist"];
        
        // Build the array from the plist
        _tableData  = [[NSArray alloc] initWithContentsOfFile:path];
        
        NSLog(@"Created %ld rows", _tableData.count);
    }
    return self;
}


- (NSArray *)sortWithSquence:(NSString *)sequence
{
    if([sequence isEqualToString:@""]) //if no filter, return the regular list
    {
        return _tableData;
    }
    return [self getSubArray:_tableData bySeq:sequence];
}

- (NSArray *)getSubArray:(NSArray *)array bySeq:(NSString *)charSeq
{
    NSInteger first = [self binarySearchForMutableStringArray:array bySeq:charSeq findLast:NO];
    NSInteger last = [self binarySearchForMutableStringArray:array bySeq:charSeq findLast:YES];
    if(last-first >= 0 && (last != -1 || first != -1))
    {
        NSLog(@"Range (%ld, %ld)", first, last);
        return [array subarrayWithRange:NSMakeRange(first, last-first+1)];
    }
    else
    {
        NSLog(@"No matches found");
        return nil;
    }
}

//binary search implemented with character sequences
- (NSInteger) binarySearchForMutableStringArray:(NSArray *)array bySeq:(NSString *)charSeq findLast:(BOOL)last
{
    NSInteger low = 0;
    NSInteger high = [array count];
    NSInteger result = -1;
    while(low <= high)
    {
        NSInteger mid = (low + high)/2;
        NSString *midObj = [array objectAtIndex:mid]; // get middle
        NSComparisonResult compare = [midObj compare:charSeq options:NSCaseInsensitiveSearch range:NSMakeRange(0, charSeq.length)];
        if(compare == NSOrderedAscending)
        {
            low = mid + 1;
        }
        else if(compare == NSOrderedDescending)
        {
            high = mid - 1;
        }
        else
        {
            result = mid; // key found
            if(last)
            {
                low = mid + 1;
            }
            else
            {
                high = mid - 1;
            }
        }
    }
    return result; //no occurance
}


@end

To move away from the ugly brute force method, I utilized the binary search algorithm. The idea is to find the first occurrence of a character sequence, find the last, determine the range and give back a new spliced array pointer. Using ranges, we can use various points to just point to different sections of the array. This takes away the need to create any new arrays.

In part 3, I will optimize the list by storing the filtered values as the character sequence increases. For example

“A” will provide a list of all words that start with “A”. When the user types “AP”, I will have the algorithm index the previously spliced list to increase the speed at which it finds the next character sequence. If the user hits backspace, the previous list can be provided if available in memory, if not then the algorithm will have to re-index the main list. This will optimize performance and speed as the user gets closer and closer to the word they wish to type.

Part 4 will then look into using Core Data to better store the pre-processed data and finally part 5 will use the list filter logic to create a fast word predictor.