Take the 2-minute tour ×

Word processors (e.g. Microsoft Word) display documents to the user as styled text. The user can select a part of this text and apply styles to it, and edit the text.

The word processor must (I guess) have an internal representation of the document that indicates which bits of the text displayed to the user should be styled differently. But the user doesn't interact with this internal representation. They interact with the text, by using the caret and selecting portions of it.

What data structure might the word processor use to efficiently map the text with which the user interacts to its internal model of the document?

share|improve this question
The Gang of Four Design Patterns uses word processing for a significant number of its examples. It might be useful to look at those examples for solutions to various problems in word processor design. –  MichaelT Dec 27 '12 at 15:55
@MichaelT: it does indeed, that was my first thought too. I couldn't find any examples in it related to this particular question, although I should take another look. –  Paul D. Waite Dec 27 '12 at 15:56
Chapters 2.2 and 2.3 deal with the document structure and formatting. –  MichaelT Dec 27 '12 at 15:59
@MichaelT: yup, those were the chapters I looked at. They specifically deal with how to store the elements of a document as objects, and how to design their APIs so that they can render themselves. It doesn't discuss how to map the user's caret position/text selection to the document representation. –  Paul D. Waite Dec 27 '12 at 16:04
If you've ever used used VSTO or Office interop that might provide so insight, too. You get to explore Word's object model. eg. support.microsoft.com/kb/316384 –  Brad Dec 27 '12 at 16:16
show 2 more comments

3 Answers

There are an infinite number of ways to do it, but the basic concept isn't that hard. Say you used html for your internal representation:

<strong>bold text here</strong> non-bold.

If your GUI widget tells you the cursor is after the 4th character, all you have to do is count to the 4th character, but when you come to something inside angle brackets, you don't count it, but instead keep track of what formatting it is applying or unapplying.

Obviously, for a large document you don't want to count characters from the beginning every time you press a key, so they use more efficient data structures, but the basic concept is the same. You have some sort of mapping between visible characters and their metadata.

share|improve this answer
Gotcha. Do you have any examples of data structures that might be used for this mapping? –  Paul D. Waite Dec 27 '12 at 15:52
add comment

I would like to preface this post by saying that I haven't actually worked on any text editors yet. There may be some standard practice that I am unaware of...that being said, a tree doesn't seem to make much sense here; what would you have for siblings? If you tried to use a tree, I think you would end up with a linked list, which does work well here.

What is it that you want from your data structure? I assume you will need to move the cursor around quickly, making copy / pasting fast, etc. With a linked list, you have have constant time insertions, so moving the cursor is as simple as removing a special cursor node __c and inserting it one place forward.

(T) -> (h) -> (__c) -> (i) -> (s) 
(T) -> (h) -> (i) -> (__c) -> (s)

It also works well because the majority of a users navigation will be "linear"; they probably move the cursor one space forwards or backwards at a time. The usual downside to linked lists is indexing, but this behavior lends itself well to an iterator.

You will always have cases where the user uses the mouse to click and move the cursor to a much earlier position, and you might want to change the node structure to contain more than just one letter or you will end up iterating through thousands of nodes to move the cursor, but this is the general idea. Maybe you want to make each node a "paragraph" node that points to another linked list of characters? You might want to make the primary node a "formatting" node; the choice is yours.

share|improve this answer
add comment

I assume it is using some kind of tree representation. Nodes of this tree would define styling , eg. all text under this node has this style and end leafs of this tree would be raw text. Then by editing the leaves, you edit the raw text, but formatting remains same. This also allows for nesting of styles.

Selecting the text usually means picking node where selection starts and node where selection ends, thus allowing you select different styled and formatted text. Then by applying formatting to the selection, you apply complex modification to this tree.

Displaying this tree then might result in complex visual document.

You might also check out LaTex, which is pretty much creation of rich visual documents and DTP from it's internal representation. Because LaTex documents are by definition readable and processable by computers, it might also be used as internal representation of those documents.

share|improve this answer
Sure: my question though is about how to keep track of the link between the tree representation and the text displayed to the user. –  Paul D. Waite Dec 27 '12 at 15:51
add comment

Your Answer


