Which data structure are used for commenting text and which algorithms take care for updating the comment position? A commenting feature is present in every good word processor such as Microsoft Word, Google Docs etc.

I can imagine two approaches: One would be surrounding the commented text with some sort of markup (e.g. XML tags), which implicitly stores the position of the comment inside of the commented text. The user doesn't get to see the the XML tags, since it gets parsed beforehand by the word processor.

The other approach could be storing an array of all comments and their positions and updating the positions as the commented text changes.

Are there other possible approaches? What could be the caveats of a specific implementation?


I would do it with a simple collection of tuples containing the position and length of text to be annotated, and the annotation text.

For example

public class Annotation {
    public int Position;
    public int Length;
    public string Text;

In C#, the most favorable collection appears to be an OrderedDictionary. An OrderedDictionary allows you to lookup annotation by position, but you can also iterate the annotations in the order that they appear in the text. You can even hold a pointer to the nearest annotation as the user navigates through the text.

var dictionary = new OrderedDictionary<int, Annotation>();
| improve this answer | |
  • Thanks. This coincides with my idea about the array, but that would also mean that for every character typed or removed from the text, all annotations in the dictionary would have to be updated for their starting position. – medonja Mar 18 '16 at 14:59
  • I hadn't thought about that. It wouldn't be the end of the world, though, unless you had an enormous amount of annotations. The only alternative would be to track each character with its own id and a pointer to the next character, which seems a bit... excessive. – Robert Harvey Mar 18 '16 at 15:02
  • Note that Scintilla, the engine that powers Notepad++, supports annotations, and it's open-source. Potentially, you could crack open that code and see how they do it there. – Robert Harvey Mar 18 '16 at 15:07
  • See also annotatorjs.org – Robert Harvey Mar 18 '16 at 15:08

Based on your comment to Robert Harvey's answer, you could do a combination of both.

The markup/xml tag would hold the position along with some some sort of identifier to an item in the array. This way the tag is reduced in size since it doesn't have to hold the contents of the comment and can easily move along as items are entered before it.

You get the advantage of the array in a situation where you need to access or dump the contents of all the comments. Usually that wouldn't include positions, so you just need to access the array and not search through the document for the markup.

| improve this answer | |
  • That seems reasonable. – medonja Mar 18 '16 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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