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:
2. A list delta is composed of primitives
Any delta can be expressed as a series of the following operations:
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.
