CODEWITHSUNDEEP
algorithmdata-structures
Geek_To_Learn
Geek_To_Learn

Reputation: 1956

Data Structure to Implement Text Editor?

Recently I was asked this question in an interview. The exact question was

What data structures will you use to implement a text editor. Size of editor can be changed and you also need to save the styling information for all the text like italic, bold etc ?

At that point of time, I tried to convince him using many different approaches like stack, Doubly Linked list and all.

From that point of time,This question is bugging me.

Upvotes: 8

Views: 4495

Answers (3)

ekostadinov
ekostadinov

Reputation: 6940

In addition to the previous answers, I would like to add that in order to get to the data structures, you need first to know your design - otherwise the options will be too broad selected.

As example let's assume that you'll need an editing functionality. Here the State and Memento design patterns will be a good fit. Very suitable structure will be the Cord, since it's

composed of smaller strings that is used for efficiently storing and manipulating a very long string.

In our case the text editing program

may use a rope to represent the text being edited, so that operations such as insertion, deletion, and random access can be done efficiently.

rope

Upvotes: 2

skypjack
skypjack

Reputation: 50550

It looks like they'd like to know if you were aware of the flyweight pattern and how to use it correctly.

A text editor is a common example while describing that pattern.

Maybe your interviewer was a lover of the GOF book. :-)

Upvotes: 2

Tyler Durden
Tyler Durden

Reputation: 11532

An open-ended question like this is designed more to see if you can think cogently about making a design that hangs together well, rather than having one, specific answer.

One specialized answer to the question is to use DOM/XML ("Document Object Model"). Markup "languages" are intended to solve this exact problem. You could store the data for the editor in a DOM. One of the advantages of using a DOM is that there are libraries like Xerces that have extensive support for building and managing DOMs, so a lot of your work is done for you. It is possible the interviewer intended this to be the ideal answer.

A more general answer is that any nested sequence structure can be used. The text can be seen as a sequence of strings. Each elment of the sequence, like rows in a database, can have multiple attributes (font type, font size, italic, bold, strikethrough, etc). Nesting (hierarchy) is useful because the document might have structure such as chapters, sections, paragraphs. For example, if a paragraph has its own styling (indent), then it may need to have its own level. So you have something like this:

Document
   Chapter
      Paragraph
         Text

To implement this, you would use a tree and each node of the tree would have multiple attributes. You would require different kinds of nodes (Chapter nodes, Paragraph nodes, etc). So, for example, a document like a paper would have multiple Section nodes and a Notes node inside a Document node, but a book-like document might have Chapter nodes inside a document node. The advantage of this approach is that it is more specific and hand-tailored to the problem than using a DOM, which is a more flexible approach.

You could also combine the two approaches, using a DOM as your base structure and the hierarchical structure described above as your DOM implementation.

(Note: in the future you should post questions like this to https://softwareengineering.stackexchange.com/)

Upvotes: 0

Related Questions