5 ms·

Can anyone speculate on at least the class of algorithms they are using?

• mitko 17y ago
  I wouldn't be efficient wrt space to keep copy of every version of the file. Instead I suppose they keep the actions of the writer(s). Algorithmically it shouldn't be complicated. Maybe they just keep history of what happened in the environment and reproduce it. Maybe they even have some checkpoints saved so that there is no need to reconstruct it from the beginning every time. And maybe they can compress events. Instead of: (type a),(type s),(type k) they have just (type ask) and in case you want better granularity they have it recorded somewhere.
  • yan 17y ago
    I was thinking they're using something like video encoders, where differential changes are stored and every N frames (updates? characters?) it stores a copy of the file again for faster tracking and updating.
    • apotheon 17y ago
      In traditional cell animation, they'd call the guys who painted the "differential" frames "in-betweeners", and I think (my memory is hazy) the reference cells painted by the master animators are called "index frames".
• wwalker3 17y ago
  Probably the same as a normal text undo. You store the "actions" the user performs against the document on a stack. Each action is a replacement of one text string in the document with another (where strings can be zero-length and can start and end at any point). Actions can "do" and "undo" themselves against the document trivially. Then to save space, you compress adjacent actions into single actions (e.g. add('a', 0) and add('b', 1) compress to add("ab", 0)).