5
$\begingroup$

I'm looking for a confluentially persistent data structure for a string - so far I'm looking at finger trees. That is, how would I resolve two edits to the same base tree, and would I be able to preserve the undo history? I'm assuming that some mutations would be mutually exclusive, and I'd need to reject one. That is, I'm under the impression that order matters.

Some specifics - I'll have a copy of the tree in each thread - each will be sending updates to a central thread that updates all the others. Each thread will be based on the central thread's tree.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

What you seem to be looking for is not a data structure for strings themselves, but a grammar for representing concurrent actions on strings. The field of study for this is Operational Transformation: http://en.wikipedia.org/wiki/Operational_transformation

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is higher level than I was asking at but incredibly helpful and probably the best answer that exists. $\endgroup$
    – Jonathan
    Jan 4, 2011 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.