Minimum cpu and memory overhead data structure for editing text?

Question

I am creating a mind mapping application, and I was wondering what would be the best data structure for the "notes" editor. Notes might be just a few symbols, might be pages long, and are being updated, edited, shuffler around and so forth. The app is intended to run on mobile platforms so processing and memory overhead should be minimal.

My basic idea is to implement a rope / linked lists type structure that fragments notes during editing in order to avoid the overhead from reallocating notes if the container is full and to avoid allocating unnecessary space, for example with dynamically growing vectors.

However, fragmenting notes too much will inevitably introduce overhead on its own, so the second part of my implementation is planned to convert the rope structure, used during note editing into a sequential data structure for storage and fast reading.

So basically objects are stored and read from a sequential data structure, but when edited they are copied to a fragmented data structure, and when done with editing, the object is converted back.

It this a good idea? If not, then recommendations are welcome. Either way, anyone aware of some similar open source implementations I can learn from?

Answer 1

With regards to open source, there's always emacs:-). But I suspect that you're looking for something a bit simpler.

There is no one correct answer here. The traditional implementation that I've seen uses one very large buffer (std::vector<char> today), divided into three logical blocks: text before the cursor, free space, and text after the cursor. With this solution, moving the cursor entails shifting the text the cursor moves over, but inserting and deleting text at the cursor doesn't involve any shifts.

I'm not sure that the traditional approach is justified today (although maybe on an embedded machine). I'd start by just using std::vector<char> in a very naïve way, and only changing this once I had profiling data from typical editing sessions. I would wrap it, however, in a Buffer class, providing just the interface I need, in order to simplify future migration to a different strategy.

Answer 2

It depends upon the amount of text you actually plan in editing. Previous answer suggested std::vector<char> which works up to a limit.

You asked for suggestions: I learned a ton from Scintilla specifically the related section when implementing a Wiki editor.