How to maintain an ordered table with Core Data (or SQL) with insertions/deletions?

Question

This question is in the context of Core Data, but if I am not mistaken, it applies equally well to a more general SQL case.

I want to maintain an ordered table using Core Data, with the possibility for the user to:

• reorder rows
• insert new lines anywhere
• delete any existing line

What's the best data model to do that? I can see two ways:

1) Model it as an array: I add an int position property to my entity

2) Model it as a linked list: I add two one-to-one relations, next and previous from my entity to itself

1) makes it easy to sort, but painful to insert or delete as you then have to update the position of all objects that come after

2) makes it easy to insert or delete, but very difficult to sort. In fact, I don't think I know how to express a Sort Descriptor (SQL ORDER BY clause) for that case.

Now I can imagine a variation on 1):

3) add an int ordering property to the entity, but instead of having it count one-by-one, have it count 100 by 100 (for example). Then inserting is as simple as finding any number between the ordering of the previous and next existing objects. The expensive renumbering only has to occur when the 100 holes have been filled. Making that property a float rather than an int makes it even better: it's almost always possible to find a new float midway between two floats.

Am I on the right track with solution 3), or is there something smarter?

Deirdredeism

Answer 1

Since iOS 5 you can (and should) use NSOrderedSet and its mutable subclass. → Core Data Release Notes for OS X v10.7 and iOS 5.0

See the accepted answer at How can I preserve an ordered list in Core Data.

Spieler

Yep. You dug out an old question, and you are right :-). Despite some issues with NSOrderedSet (which has an API that is less complete than NSArray for example) and ordered relationships (which I believe are not fully supported by fetched result controllers). – Deirdredeism

Yeah, I tried getting NSFetchedResultsController to work with an ordered relationship. Successfully for the most part – but failed to intelligently update the table view, i.e. animating insertion or removal, instead of just doing [tableView reloadData]… So in the end I gave up on fetched results controllers and just pre-fetched the whole list :-/ – Spieler

Answer 2

If the ordering is arbitrary i.e. not inherent in the data being modeled, then you have no choice but to add an attribute or relationship to maintain the order.

I would advise the linked list since it is easiest to maintain. I'm not sure what you mean by a linked list being difficult to sort since you won't most likely won't be sorting on an arbitrary order anyway. Instead, you will just fetch the top most instance and walk your way down.

Ordering by a divisible float attribute is a good idea. You can create an near infinite number of intermediate indexes just by subtracting the lower existing index from higher existing index, dividing the result by two and then adding that result to the lower index.

You can also combine an divisible index with a linked list if you need an ordering for tables or the like. The linked list would make it easy to find existing indexes and the divisible index would make it easy to sort if you needed to.

Core Data resist this kind of ordering because it is usually unnecessary. You don't want to add something to the data model unless it is necessary to simulate the real world object, event or condition that the model describes. Usually, ordering/sorting are not inherent to the model but merely needed by the UI/view. In that case, you should have the sorting logic in the controller between the model and the view.

Think carefully before adding ordering to model when you may not need it.

Scan

If using a linked list, how would you set up the Core Data sort descriptor? One point of using Core Data (namely an NSFetchedResultController) is that it will hand you the results of a query in the correct order if you provide it with a sort descriptor. – Deirdredeism

The sort order is inherent in the data, only decided by the user. Think for example that you want to let the user decide in which order he wants her books put on her shelf. She might decide to move a book from position 7 to between position 14 and 15. Or to sell the book in position 12, or buy a new book and insert it in position 3. The next day, she'll decide to move that book to the very end of the shelf. The UI to do that is easy using a UITableView. My problem is with the best representation of such a "preference value" to make swapping/inserting/deleting easy and fast enough. – Deirdredeism

I think a linked list combined with the divisible index would be the fastest. For greater speed, I would move the ordering to another lightweight entity with a relationship to entity you want ordered. Do your fetches and sorts on the lightweight entity and then load the associated entity as needed. – Scan

I would remind you that premature optimization is the root of all evil. Don't spend a lot of time tweaking the ordering unless you've tested and found it to inefficient. In a normal Core Data app, you wouldn't see any performance issues unless you had thousands of complex entities. Unless you know you will have a huge amount of data, just pick the system easiest to implement and maintain. – Scan

Yes, I want to optimize my time as a programmer. The float divisible index approach seems the most lightweight from this perspective. – Deirdredeism

Be aware that all index systems must be periodically maintained. At some point you will need to go through and reindex everything even with the float system. If you just leave the index alone it will eventually saturate and miss-index. – Scan