How to create a mutable string class that can be used as an actual string?

Question

I want to create a python class that represents a string, but can be modified efficiently. I thought about implementing a treelike data structure, but I don't know how to make it behave like a string, such that it can be used in all kind of string functions, for instance in regular expressions.

Of course one could construct a string from the data structure each time it is needed, but that isn't very efficient, and wastes the efficiency of the data structure.

Any ideas?

Answer 1

I think one needs to implement both "sequence" and "buffer" Python protocols, which are only available from C. There is one library I know about which does this, though it's a bit dated:

https://code.google.com/p/gapbuffer/