1

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?

1

2 Answers 2

2

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>();
4
  • 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, 2016 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. Mar 18, 2016 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. Mar 18, 2016 at 15:07
  • See also annotatorjs.org Mar 18, 2016 at 15:08
1

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.

1
  • That seems reasonable.
    – medonja
    Mar 18, 2016 at 20:12

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.