Efficient data structure to implement simple text editor?
I was given this problem in an interview:
What data structure would you use to implement a simple text editor that does these 4 functions:
a) goto(line number)
b) insert(char input,location)
c) delete(location)
d) printAll() //print entire file
Given that i'm such a newb, i was stumped. I came up with making a 2d array that would allow for o(1) time for goto, but o(n) for everything else (shifting everything in the array). there were other downfalls too dealing with space issues and such, but he wanted me to optimize this data structure. I then came up with a linked list of arrays, but that had similar problems.
But thinking about it further is driving me a little crazy so I'm wondering if you guys have any suggestions on how to answer this question...
one thing that came to mind after is to implement the data structure as a binary tree, where each node contains
class Node
{
char theChar
int position;// ie 0 = first character in the file, and 81 could be the first character in the 2nd line
node left,right,parent;
}
so how it works is the cursor would know where the location was so i would know where to delete and insert within the tree.
insert{
//search for location to insert after (log n)
//create new character node and append to current node
//increment position for all subsequent children
}
delete(x){
searchfor x position
if found, remove node and decrement position valuefor all children
}
goto(line #){
return line # * 80 (or whatever max lengthfor a single line)
}
the major problem i see here is balancing the tree after every insert/delete
Thanks in advance.
