Atom Feed SITE FEED   ADD TO GOOGLE READER

ListDeltas and the next generation of observable lists

Yesterday afternoon I had a great technical discussion with Joshua Bloch, a very highly respected API designer. We met to talk about something that's very close to my heart, observable lists. We explored this problem with a whiteboard and some code samples and came up with some interesting observations...

1. Deltas are useful beyond observers
Actually this was Zorzella's idea. Modeling changes between two lists has some interesting applications:
  • for history management: the history of a list can be stored as a series of deltas.
  • for networking: applications can exchange deltas rather than full copies of lists.
  • for branching and merging: to view and display the conflicts between different revisions of the same source.

    2. A list delta is composed of primitives
    Any delta can be expressed as a series of the following operations:
  • add a single element at some index
  • remove a single element at some index
  • replacing the element at some index with a different element
  • moving an element from one index to another

    3. There exists multiple deltas to go from any pair of lists A and B.
    Suppose we have lists L1 = { A, B, C } and L2 = { A, C, B }. The change can be expressed as { move "B" at 1 to 2 } or { move "C" at 2 to 1 } or even { remove "B" at 1, add "B" at 2 }.

    4. There exists some canonical form for a list delta
    Suppose we have a delta describing these changes: { remove D at 3, remove B at 1 }. When applied to the list { A, B, C, D, E } the end result is { A, C, E }. But the same change can also be expressed as { remove B at 1, remove D at 2 }. In the canonical form, the indices of changes are listed in non-decreasing order. This applies to everything but move events, for which I'm not yet sure what the orders are. I also don't know if the canonical forms are unique.

    5. The canonical form of a list delta may be smaller
    Natural list deltas can contain redundancy. For example { insert D at 2, insert B at 1, remove D at 3 }. The canonical form of this change is simply { insert B at 1 }, since D is inserted only to be later removed. Note that we now know less about the change. We no longer know about D. The canonical form loses the order that the changes were performed in. A nice analog to this is the duality between Collections.shuffle() and Collections.sort().

    7. Deltas are reversible
    The reverse of { remove B at 1, remove D at 2 } is { insert D at 2, insert B at 1 }. The canonical form of the reversal is { insert B at 1, insert D at 3 }. To reverse a change, reverse each operation and reverse the series.

    8. Deltas can be split and joined
    Suppose we have the following: Lists L1, L2, L3 and Deltas D1, D2, such that applying D1 to L1 gives D2, and applying D2 to L2 gives L3. Naturally we can concatenate deltas D1 and D2 to create delta D12. Naturally, applying D12 to L1 returns L3. As a consequence of point 5, the canonical form of D12, which I'll call D12', may be smaller than the sum of D1 and D2.

    Most of this knowledge exists deep in the Glazed Lists codebase, but this discussion really helped me to distill the problem domain to its primitives. I'm going to revise my original proposal so it treats ListDeltas as first-class objects and makes these functions available.
  • Hi Jesse,

    actually, if your primitives are just add and remove (since an add and remove together can describe each of the other two cases, move and replace), it is pretty clear what the canonical form looks like. After you've reduced the problem to adds and removes, you can re-introduce move and replace again by marking a pair of add and remove as belonging together. This allows clients to optimize replace and move if they care, or just treat everything as a list of adds and removes.

    The Eclipse data binding framework uses just a sequence of adds and removes for list diffs. I was planning to add the optimizations but ran out of time for our initial public release. I still plan to implement the additional API in a later release, and hope that I am right in that the optimizations can be added in a way that is binary upwards compatible.
    Boris, you're right. I actually hinted at a potential API for this.

    I'll make sure to read up on how Eclipse binding does observable collections to gather ideas. If you've got any suggestions or ideas, I'd love to hear 'em!
    Hello Jesse,

    ListEvent/ListEventBuilder from your previous post are quite nice, and I agree that a ListDeltas should be first class objects.

    Any chance at moving on to add observable support for other collection and map interfaces? I have a pet project at

    http://dishevelled.org/observable

    but it currently doesn't do fine-grain event notification. I'm too lazy to do much more with it, so here's hoping that you might come up with something better instead.