Oh oracle of the interwebs –<\/p>\n
I am writing a GPCE paper, and one of the contributions is a model of sequences (AKA collections) that has stable unshifting positions. Standard collections use an array abstraction where access is by integer ordinal position, which shifts under insertion and deletion. This manifests as the fact that iterators are broken by insertion and deletion operations. Linked list iterators also break under deletion.<\/p>\n
Does anyone know of alternative proposals with stable positions\/iterators? I don’t know of any, but I can’t be the first person to do this.<\/p>\n
[Thomas lord points out Emacs markers. I also know about Operational Transformation and Darcs. But have such ideas ever been abstracted into a general purpose collection class?] <\/p>\n
[OK – I seem to have confused everyone. Lets say you have the sequence: {a,b,c,d}. You are iterating along and see a, then b. Just then, some other code drives by and decides to insert something at the front: {foo, a, b, c, d}.
\nOr maybe they decide to delete the first element, leaving: {b, c, d}. Then you advance your iterator. In all cases you should get c as the result, not b, not d, and not an InvalidState exception.]<\/p>\n
[Thanks, everyone. Got some great references to related work. Maybe I should call this “blogademics”. Some people have asked about the use case for such a thing. It is to abstract editing operations. Collaborative editors have this problem, because edits can’t be propagated when their location is unstable. Version control systems like Darcs need something like it reorder patches. And I need it to express composable transformations<\/a> on code that don’t shift each other’s position.]<\/p>\n","protected":false},"excerpt":{"rendered":" Oh oracle of the interwebs – I am writing a GPCE paper, and one of the contributions is a model of sequences (AKA collections) that has stable unshifting positions. Standard collections use an array abstraction where access is by integer ordinal position, which shifts under insertion and deletion. This manifests as the fact that iterators … <\/p>\n