CODEWITHSUNDEEP
java
Gabriele
Gabriele

Reputation: 466

How do I apply a sequence of insert/delete-character operations on a string?

I have a text like this:

My name is Bob and I live in America.

I have some reference to the characters of this string, for example:

from 3 to 7 chars, deleted
at 3 char, added "surname"
from 20 to 25, deleted
at 25 char ....

but these statements aren't ordered (and I can't order them).

So, this is the question: how can I modify the text without losing the reference of the characters? For example, if I apply the first sentence, my text became:

My is Bob and I live in America.

and my third sentence doesn't work correctly anymore, cause I've lost the reference to the original 20th character.

Keep in mind that the text is pretty long, so I can't use any indexes...

Upvotes: 1

Views: 338

Answers (5)

John Feminella
John Feminella

Reputation: 311615

First off, if this statement is true, the situation is hopeless:

but these statements aren't ordered (and I can't order them).

An unordered list of patch statements could lead to a conflict. It will not be possible to decide what the right answer is in an automated fashion. For instance, consider the following situation:

         0         1         2
 index:  012345678901234567890
 text:  "apple banana coconuts"
    - delete 5 characters from index 10
    - add "xyz" at index 10
    - delete 10 characters from index 5

You will wind up with different results depending on what order you execute these statements.

  • For instance, if you apply (1), then (2), then (3), you wind up with "apple banaconuts" --> "apple banaxyzconuts" --> "apple uts".

  • But if you apply (3), then (2), then (1), you wind up with "apple onuts" --> "apple onutsxyz" --> [error -- there aren't enough characters to delete!].

Either you need a repeatable, agreed-upon ordering of the statements, or you cannot proceed any further. Even worse, it turns out that discovering which orderings are valid (for example, eliminating all orderings where an impossible statement occurs, like "delete 10 characters from index 20", when there is no index 20) is an undecidable computer science problem.

If it turns out that the patches can be applied in a specific order (or at least in a repeatable, agreed-upon, deterministic order), the situation improves but is still obnoxious. Because the indices in any "patch" could be invalidated by any previous one, it's not going to be possible to straightforwardly apply each statement. Instead, you'll have to implement a small, pseudo-diff. Here's how I'd do it:

  • Scan through the list of patch-statements. Build a list of operations. An operation is an object with a command and some optional arguments, and an index to apply that command to. For example, your operations might look like:
  DeleteOperation(index 3, length 4)
  AddOperation(index 3, text "surname")
  DeleteOperation(index 20, length 5)

  • As you perform operations, keep a reference to the original string and store a "dirty pointer". This is the latest contiguous index in the string which has had no operations performed on it. Any operation you perform whose index exceeds the dirty pointer must first be pre-processed.

  • If you encounter a clean operation, one whose index is less than or equal to the dirty pointer, you can apply it with no further work. The dirty pointer now moves to that operation's index.

  • If you encounter a dirty operation, one whose index is greater than the dirty pointer, you'll have to do some work before you can apply it. Determine the real index of where the operation should be applied by looking at the previous operations, then make the appropriate offset and apply it.

  • Execute each operation in turn until there are no more operations to execute.

The result is your transformed string.

Upvotes: 7

ssr532
ssr532

Reputation: 117

What exactly are you trying to do here?

If you are trying to apply these "references" to your text,

My name is Bob and I live in America.

Keep this data unaltered. Copy this to another string, and apply your "reference" there every time you need to modify it.

Upvotes: 0

tim_yates
tim_yates

Reputation: 171144

Sounds like you are doing Operational Transforms

This article over here discusses them in theory and practice (and quite some depth)

Understanding and Applying Operational Transformation

If they aren't in any order though, how can you apply them? How do you know if one operation should be applied before or after another operation? Are none of the operations additive? (ie: do all of the operations only apply to the original String?)

Upvotes: 0

bezmax
bezmax

Reputation: 26142

Each time you execute a statement go over the whole list and modify indexes appropriately.

Upvotes: 0

Adrian Regan
Adrian Regan

Reputation: 2250

You will just have to track what you are doing to the string and add or subtract from future item indexes in your list of commands.

Upvotes: 0

Related Questions