Algorithm and data structure for text comments

Question

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?

Answer 1

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>();

Answer 2

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.