t**d
发帖数: 352 | 1 Design a data structure for a text editor. require better than linear for
both line search and insert a new line.
for example, you can use String[] to store lines in a page. then search for
a particular line is constant time, but add a new line is linear.
you can chose to use LinkedList, but now insert is constant time while
search is linear. | j*****u
发帖数: 1133 | 2 "for example, you can use String[] to store lines in a page. then search for
a particular line is constant time"
why this is constant not liner?
You could use a LinkedList or incremental array (e.g. List) + an
index like hash table or tree that provides better search than liner | t**d
发帖数: 352 | 3 String[] use line number to index the array. so search based on line number
is constant time.
I don't think LinkedList + hashtable can do the trick. if you want to insert
line 5, all the entry in hashtable below line 5 need to be updated to
refelect a new line number, so insert is linear. | l*****g
发帖数: 685 | 4 use BST's in-order traversal as line number sequence.
Search a line number is O(logN);
Insert a new line before or after an existing line involves O(logN) search
plus constant insertion.
Only drawback is that the tree has to be regularly optimized for balance.
number
insert
【在 t**d 的大作中提到】
: String[] use line number to index the array. so search based on line number
: is constant time.
: I don't think LinkedList + hashtable can do the trick. if you want to insert
: line 5, all the entry in hashtable below line 5 need to be updated to
: refelect a new line number, so insert is linear.
| j*****u
发帖数: 1133 | 5 okay... I thought you meant searching "by line string". If what you wanted
is searching "by index" then it is accessing by index not searching.
Then simply an incremental array (e.g. vector,List,ArrayList) will do it.
internally, copy happens when the array is full but on average the inserting
is constant
number
insert
【在 t**d 的大作中提到】
: String[] use line number to index the array. so search based on line number
: is constant time.
: I don't think LinkedList + hashtable can do the trick. if you want to insert
: line 5, all the entry in hashtable below line 5 need to be updated to
: refelect a new line number, so insert is linear.
| t**d
发帖数: 352 | 6 BST is a good idea. any other ideas?
incremental array won't work since worst for insert is still linear. | d******u
发帖数: 397 | 7 Using BST is a nice idea.
However, one question: what is the key for each node of the BST?
If the keys are the line numbers, do we need to change the key values that
are no less than the newly inserted line ?
Then, that would still be linear, right? (even though you don't need to move
the data entries as in the array case).
If you don't use line numbers as the keys of the nodes, search will not be
logN. Right?
【在 t**d 的大作中提到】
: BST is a good idea. any other ideas?
: incremental array won't work since worst for insert is still linear.
| l*****g
发帖数: 685 | 8 Good question!
I was wrong. It's not really a BST, but rather a BT.
The nodes don't have explicit keys, and line numbers are implied by the in-
order traveral of the tree. Each node holds prevCount, number of all lines
before it, and nextCount, number of all lines after it.
Here is a rough implementation of this idea.
class Line
{
public:
//char * text;
Line * prev;
Line * next;
int prevCount;
int nextCount;
Line(char * text)
{
// clone text data
prev = next = null;
prevCount = nextCount = 0;
}
};
Line * Search(Line * root, int lineNo)
{
// suppose line is 1-based.
if (!root || lineNo < 1 ||
lineNo > (root->nextCount + root->prevCount + 1))
return null;
if (lineNo == (root->prevCount + 1))
return root;
if (lineNo <= root->prevCount)
return Search(root->prev, lineNo);
return Search(root->next, (lineNo - root->prevCount - 1));
}
bool InsertBefore(Line *root, int lineNo, char *text)
{
if (!root || lineNo < 1 ||
lineNo > (root->nextCount + root->prevCount + 1))
return false;
if (lineNo == (root->prevCount + 1))
{
root->prevCount++;
Line *newLine = new Line(text);
if (!root->prev)
{
root->prev = newLine;
}
else {
Line *cur = root->prev;
do
{
cur->nextCount++;
cur = cur->next;
}
while (cur->next);
cur->next = newLine;
}
return true;
}
if (lineNo <= root->prevCount)
{
root->prevCount++;
return InsertBefore(root->prev, lineNo, text);
}
root->nextCount++;
return InsertBefore(root->next, (lineNo - root->prevCount - 1), text);
}
bool InsertAfter(Line *root, int lineNo, char *text)
{
if (!root || lineNo < 1 ||
lineNo > (root->nextCount + root->prevCount + 1))
return false;
if (lineNo == (root->prevCount + 1))
{
root->nextCount++;
Line *newLine = new Line(text);
if (!root->next)
{
root->next = newLine;
}
else {
Line * cur = root->next;
do
{
cur->prevCount++;
cur = cur->prev;
}
while (cur->prev);
cur->prev = newLine;
}
return true;
}
if (lineNo <= root->prevCount)
{
root->prevCount++;
return InsertAfter(root->prev, lineNo, text);
}
root->nextCount++;
return InsertAfter(root->next, (lineNo - root->prevCount - 1), text);
}
move
【在 d******u 的大作中提到】
: Using BST is a nice idea.
: However, one question: what is the key for each node of the BST?
: If the keys are the line numbers, do we need to change the key values that
: are no less than the newly inserted line ?
: Then, that would still be linear, right? (even though you don't need to move
: the data entries as in the array case).
: If you don't use line numbers as the keys of the nodes, search will not be
: logN. Right?
| d******u
发帖数: 397 | 9 Thank you for the reply and the code.
Maybe I misunderstood and please correct me if I am wrong.
Keeping the two counters on each node up-to-date requires linear
complexity (in the following two loops), right? So the insertion is
still linear...
do
{
cur->nextCount++;
cur = cur->next;
}
while (cur->next);
do
{
cur->prevCount++;
cur = cur->prev;
}
while (cur->prev);
the in-
lines
【在 l*****g 的大作中提到】
: Good question!
: I was wrong. It's not really a BST, but rather a BT.
: The nodes don't have explicit keys, and line numbers are implied by the in-
: order traveral of the tree. Each node holds prevCount, number of all lines
: before it, and nextCount, number of all lines after it.
: Here is a rough implementation of this idea.
: class Line
: {
: public:
: //char * text;
| l*****g
发帖数: 685 | 10 No, it's O(logN) because it only updates the nodes on the path from root to
the insertion point.
If you're talking about worst case, yes, O(n) is possible in case the tree
is extremely unbalanced.
【在 d******u 的大作中提到】
: Thank you for the reply and the code.
: Maybe I misunderstood and please correct me if I am wrong.
: Keeping the two counters on each node up-to-date requires linear
: complexity (in the following two loops), right? So the insertion is
: still linear...
: do
: {
: cur->nextCount++;
: cur = cur->next;
: }
| d******u
发帖数: 397 | 11 yeah, you are right. Thanks again! ^_^ |
|
