Smart Reordering for UITableView

For my current project zutun.io I’m implementing the reordering of entries as described in the Apple Documentation.

Algorithm Idea

The goal is to perform as few operations on the database as possible, therefore I use a floating point number as the sort property. The basic idea is simple:

To put an entry between ordering numbers A and B choose a number that is greater than A and smaller than B.

The trick is to choose a random number to avoid conflicts when synching the data later on.

Implementation

First of all lets create a little helper that will create random floating numbers in a range:

#import <math.h>

static inline double hxRandomDouble(double min, double max) {
    double _min = MIN(min, max);
    double _max = MAX(min, max);
    double _rnd = ((double)arc4random() / (double)(UINT32_MAX-1));
    return _min + ((_max - _min) * _rnd);
}

Lets say our entries are defined like this:

@interface TodoRecord : NSObject
@property NSString *title;
@property NSNumber *order;
@end

In our view controller we’ll store the entries in the property objects. Adding a new entry is then as easy as:

TodoRecord *rec = [[TodoRecord alloc] init];
rec.title = title;

NSNumber *max = [self.objects valueForKeyPath:@"@max.order"] ?: @1;
rec.order = @(max.doubleValue + hxRandomDouble(1., 2.));

This will create a new entry with a distance of at least 1 to the previous one.

Now comes the tricky part. We will first allow reordering in general, which only makes sense if we have at least 2 entries. I consider the rest of the editing code as trivial, like calling setEditing: etc.:

- (BOOL)tableView:(UITableView *)tableView canEditRowAtIndexPath:(NSIndexPath *)indexPath {
    return self.objects.count > 1;
}

The following code is the heart of the code that applies the movement. It is basically the implementation of the described idea. It will just do one database operation and sync nicely.

- (void)tableView:(UITableView *)tableView moveRowAtIndexPath:(NSIndexPath *)sourceIndexPath toIndexPath:(NSIndexPath *)destinationIndexPath {
    NSInteger src = sourceIndexPath.row;
    NSInteger dst = destinationIndexPath.row;

    // Nothing to do
    if (src == dst) return;

    // Move the entry in the representing NSMutableArray, see Apple Docs
    TodoRecord *rec = (id)[self.objects objectAtIndex:src];
    [self.objects removeObjectAtIndex:src];
    [self.objects insertObject:rec atIndex:dst];

    // Find the new neighbours of our entry
    NSInteger len = self.objects.count;
    TodoRecord *beforeRec = dst - 1 >= 0 ? (id)self.objects[dst - 1] : nil;
    TodoRecord *afterRec = dst + 1 < len ? (id)self.objects[dst + 1] : nil;

    // Find the range for the new ordering number
    double before = beforeRec.order.doubleValue;
    double after = afterRec.order.doubleValue;
    double current = rec.order.doubleValue;

    // At the ends add some margin
    if (!beforeRec) before = after + 2.5;
    if (!afterRec)  after = before - 2.5;

    // If not alread inside of the range...
    if (before < current || after > current) {
        // ... put somewhere middleish
        double dist = (before - after) / 3.;
        rec.order = @(hxRandomDouble(after + dist,
                                     before - dist));
    }
}

Conclusion

There may be theoretical limits for this implementation, but the complications are minimal compared to the benefit of the algorithm.

You would like to comment on it? Send me a message on @holtwick

Update 2018-02-27

I made some tests to see when the first collisions will occur. For the example above this will usually be around 50 steps. That means you can move items 50 times between a specific pair of entries before the order number will converge to identical values.

I then tried the same with int32_t and it turned out it reached about 30 steps without collision, which makes sense for a 32bit number divided by 2 in each step ;)

So sadly infinity in reality isn’t to far away. But I still think that the edge cases will not often be reached and then it is still enough time to do apply the classic approaches again and have room for another 30-50 rounds.