Design pattern to keep track UITableView rows correspondance to underlying data in constant time.

Question

When my model changes I want to animate changes in UITableView by inserting/deleting rows. For that I need to know the ordinal of the given row (so I can construct NSIndexPath), which I find hard to do in better-than-linear time.

For example, consider that I have a list of addressbook entries which are manualy sorted by the user, i.e. there is no ordering "key" that represents the sort order. There is also a corresponding UITableView that shows one row per addressbook entry. When UITableView queries the datasource I query the NSMUtableArray populated with my entries and return required data in constant time for each row.

However, if there is a change in underlying model I am getting a notification "Joe Smith, id#123 has been removed". Now I have a dilemma. A naive approach would be to scan the array, determine the index at which Joe Smith is and then ask UITableView to remove that precise row from the view, also removing it form the array. However, the scan will take linear time to finish.

Now I could have an NSDictionary which allows me to find Joe Smith in constant time, but that doesn't do me a lot of good because I still need to find his ordinal index within the array in order to instruct UITableView to remove that row, which is again a linear search. I could further decide to store each object's ordinal inside the object itself to make it constant, but it will become outdated after first such update as all subsequent index values will have changed due to removal of an object.

So what is the correct design pattern to accurately reflect model changes in the UITableView in costant (or at least logarithmic) time?

Answer 1

I would add a Key Field to your address field so you could perform a binary tree search. For example, lets say your data model that feeds the UITableView looks like:

NSString  *name;
NSString  *address;

You might think of adding a key field like:

NSInteger keyIndex;
NSString  *name;
NSString  *address;

If you do not want the key associated with the data model (since it is an abstraction of the view controller and might just represent the order that the array should be in to be sorted), you could keep a sidecar NSMutableArray of NSNumber (or if performance is really critical use a custom managed C-Array with malloc/calloc/free) next to the Data Model.

The keyIndex is then filled in when you initialize your data source (or feed the data to the UITableView after a reload message). This then gives an ordered key field to do very fast and should be in the order of O*ln(n).

You will need to maintain the Key field as the user deletes and modifies the order. However you do this, without a key field somewhere, I do not believe you are going to get out of a linear search.