Designing out duplicates items in the timeline

[poljar]

It would likely make sense to solve the de-duplication via a design change. We should switch towards using a HashMap and a Vec for the Timeline:

struct Timeline {
    items: HashMap<EventId, TimelineItem>,
    item_positions: Vec<EventId>,
}

Note that the exact types don't need to be Vec and HashMap but they should have properties that are equivalent to those two.

This would prevent us from ever inserting items that have the same EventId into the timeline. Another nice advantage of this approach is that, if we have an operation that requires us to find the event by its ID, we can find the event in O(1) time instead of O(N) where N is the number of elements in the timeline.

[jplatte]

We have two constraints here:

• We still need to present it as an ordered list of TimelineItems externally
• We need that ordered list to be observable similar to the current ObservableVector

I think the best solution, though it is complex, is to fork the im crate that ObservableVector uses as its backing representation and add an IndexMap to it that is a copy of im's existing HashMap, with index tracking logic adopted from the indexmap crate.

[Hywan]

A BTreeMap looks ideal. And im even has a OrdMap (based on b-trees). Is there any arguments in favor of IndexMap rather than OrdMap?

[Hywan]

What? That's probably an error from my side, sorry for that… I'm fine doing it by the way.

[jplatte]

Is there any arguments in favor of IndexMap rather than OrdMap?

Yes, timeline items have a defined order that we need to present to API users.

[Hywan]

IndexMap and OrdMap both maintain the key order, so why are you suggesting IndexMap over OrdMap (which is native to im)?

[jplatte]

IndexMap maintains order the way Vec does, OrdMap maintains the order of keys like BTreeMap. With the former two, you get a custom ordering that's unrelated to the key which is what we need; with the latter two you get an ordering that is inherited from the key's Ord implementation.