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?

Answer 1

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.