Task list with re-ordering feature using Firebase/Firestore

Question

I want to make a list of tasks that can change their order, but I am not sure how to store this in a database.

I don't want to use array because I have to do some queries further in future.

Here is the screenshot of my database:

I'm trying to make something like Trello where the user adds tasks and can move tasks upward and downward according to their priority. I need to change the position of the tasks in the database as well to maintain the record. I'm unable to understand how to do that in any database. I'm an experienced developer and I have worked with mongodb and firebase but this is something unique for me.

Here is the code to create and get all tasks. When I try to move some task in collection. I maintained an index in each task. Let's say when I move a task from the position of index 5 to index 2 then I have to edit all the upcoming indexes by +1 is there a better approach?

Code Sample

class taskManager {
    static let shared = taskManager()
    typealias TasksCompletion = (_ tasks:[Task],_ error:String?)->Void
    typealias SucessCompletion = (_ error:String?)->Void

    func addTask(task:Task,completion:@escaping SucessCompletion){
        Firestore.firestore().collection("tasks").addDocument(data: task.toDic) { (err) in
            if err != nil {
                print(err?.localizedDescription as Any)
            }
            completion(nil)
        }
    }

    func getAllTask(completion:@escaping TasksCompletion){
        Firestore.firestore().collection("tasks")
            .addSnapshotListener { taskSnap, error in
                taskSnap?.documentChanges.forEach({ (task) in
                    let object = task.document.data()
                    let json = try! JSONSerialization.data(withJSONObject: object, options: .prettyPrinted)
                    var taskData = try! JSONDecoder().decode(Task.self, from: json)
                    taskData.id = task.document.documentID

                    if (task.type == .added) {
                        Task.shared.append(taskData)
                    }
                    if (task.type == .modified) {
                        let index = Task.shared.firstIndex(where: { $0.id ==  taskData.id})!
                        Task.shared[index] = taskData
                    }
                })
                if error == nil{
                    completion(Task.shared,nil)
                }else{
                    completion([],error?.localizedDescription)
                }
            }
    }
}

Answer 1

I think the question you're trying to ask about is more about database design.

When you want to be able to keep order with a group of items while being able to reorder them you will need a column to keep the order.

You run into an issue when you try to order them if they are sequentially ordered.

Example

For example if you wanted to move Item1 behind Item4:

Before

An item with an ordering index.

 1. Item1, order: 1
 2. Item2, order: 2
 3. Item3, order: 3
 4. Item4, order: 4
 5. Item5, order: 5
 6. Item6, order: 6

After

Problem: we had to update every record between the item being moved and where it was placed.

Why this is a problem: this is a Big O(n) - for every space we move we have to update that many records. As you get more tasks this becomes more of an issue as it will take longer and not scale well. It would be nice to have a Big O(1) where we have a constant amount of changes or as few as possible.

 1. Item2, order: 1 - Updated
 2. Item3, order: 2 - Updated
 3. Item4, order: 3 - Updated
 4. Item1, order: 4 - Updated
 5. Item5, order: 5
 6. Item6, order: 6

Possible Solution #1 (OK Maybe?) - Spacing

You could try to come up with a crafty method where you try to space the order numbers out so that you have holes that can be filled without updating multiple records.

This could get tricky though, and you may think, "Why not store Item1 at order: 4.5" I added a related question below that goes into that idea and why you should avoid it.

You may be able to verify the safety of the order client side and avoid hitting the database to determine the new order ID of the move.

This also has limitations as you may have to rebalance the spacing or maybe you run out of numbers to items. You may have to check for a conflict and when a conflict arises you perform a rebalance on everything or recursively the items around the conflict making sure that other balancing updates don't cause more conflicts and that additional conflicts are resolved.

 1. Item2, order: 200
 2. Item3, order: 300
 3. Item4, order: 400
 4. Item1, order: 450 - Updated
 5. Item5, order: 500
 6. Item6, order: 600

Possible Solution #2 (Better) - Linked Lists

As mentioned in the related link below you could use a data structure like a linked list. This retains a constant amount of changes to update so it is Big O(1). I will go into a linked list a bit in case you haven't played with the data structure yet.

As you can see below this change only required 3 updates, I believe the max would be 5 as shown in Expected Updates. You may be thinking, "Well it took about that many with the first original problem/example!" The thing is that this will always be a max of 5 updates compared to the possibility of thousands or millions with the original approach [Big O(n)].

 1. Item2, previous: null, next: Item3 - Updated // previous is now null
 2. Item3, previous: Item2, next: Item4
 3. Item4, previous: Item3, next: Item1 - Updated // next is now Item1
 4. Item1, previous: Item4, next: Item5 - Updated // previous & next updated
 5. Item5, previous: Item1, next: Item4 - Updated // previous is now Item1
 6. Item6, previous: Item6, next: null

Expected Updates

1. Item being moved (previous, next)
2. Old previous item's next
3. Old next item's previous
4. New previous item's next
5. New next item's previous

Linked Lists

I guess I used a double linked list. You probably could get away with just using a single linked list where it doesn't have a previous attribute and only a next instead.

The idea behind a linked list is to think of it a chain link, when you want to move one item you would decouple it from the link in front of it and behind it, then link those links together. Next you would open up where you would want to place it between, now it would have the new links on each side of it, and for those new links they would now be linked to the new link instead of each other.

Possible Solution #3 - Document/Json/Array Storage

You said you want to stay away from arrays, but you could utilize document storage. You could still have a searchable table of items, and then each collection of items would just have an array of item id/references.

Items Table

 - Item1, id: 1
 - Item2, id: 2
 - Item3, id: 3
 - Item4, id: 4
 - Item5, id: 5
 - Item6, id: 6

Item Collection

 [2, 3, 4, 1, 5, 6]

Related Question(s)

• Storing a reorderable list in a database

Resources on Big O

• A guide on Big O
• More on Big O
• Wiki Big O

Other Considerations

Your database design will depend on what you're trying to accomplish. Can items belong to multiple boards or users?

Can you offload some ordering to the client side and allow it to tell the server what the new order is? You should still avoid inefficient ordering algorithms on the client side, but you can get them to do some of the dirty work if you trust them and don't have any issues with data integrity if multiple people are working on the same items at the same time (those are other design problems, that may or may not be related to the DB, depending on how you handle them.)