-1

I'm starting a school project: we have to code an efficient text editor in c. To command this i can use:

  • (row1,row2)c
  • (row1,row2)d
  • (row1,row2)p
  • (number)u
  • (number)r

These commands are used to change text between row1 and row2 (the c), delete text between row1 and row2 (the d, the text will be replaced with a single dot), print on stdout rows between row1 and row2 (the p), undo (number) times or redo (number times) (this last two commands doesn't affect print, just c and d). To start I was thinking what data structure I can use. I thought, for the rows, to use a single link list with number of row and a second list (for the text itself). This because the code has to be efficient in time and space But I don't find a good way to implement undo/redo in my case: I was thinking two create two stacks, one for undo and one for redo. Every command I give it's inserted in undo stack and, if I undo something i delete the first action in undo stack and put it in redo stack

But I don't know ho to write how to write these commands: i was thinking to save a complementary command, so I can run this command and return in a previous statement. Then, when I undo, i create complementary command in redo stack, and I delete this stack every new command to free space

I hope it's understandable, I just want your opinion about this possible structure NB I can code only in c11 with stdlib and stdio theoretically, but I can copy and modify other libraries' functions if it's needed

---UPDATE--- I was thinking if it's better to use a R/B Tree for keeping the rows structure. This because it would take O(log(n)) to search the X-th row and edit it, instead of O(n)

The only problem it's, when I have to change many rows in just a command (e.g 1,521c) it takes longer to search every row

Maybe a sort of hybrid could be a good choice: i use RBT structure to find the start row address, then I use the list structure to find the others. So every node of this tree has 2 address for RBT and 1 address for list

Alexei
  • 1
  • 1

2 Answers2

0

Your design ideas are spot on.

The part needed is how to represent the undo and redo entries.

  • A redo entry could be a struct that indicates what span of text to replace and the text to replace it with. A "span" here gives the offsets into the text, and since it could be an empty span (just a position), that suggests using a half-open interval [start .. end) or a start and length. That can express any single text-change operation. In theory the replacement text could be a 0-length string; if not yet, anticipate that future assignments may add feature requests.
  • An undo entry can be the same struct, describing as you noted the complementary text replacement operation.

The other design decision is how to represent the document text. The simplest thing is a sequential buffer of characters, in which case every insertion requires moving all following text downwards after ensuring the memory buffer is large enough.

An alternative is a list of lines of text, each line being a separate memory node. That way, inserting, deleting, and replacing lines doesn't have to move the bulk of the text around in memory, just some of the line node pointers. Furthermore, for line replacement commands the redo/undo entries can just list which range of line pointers to replace with other line pointers.

Jerry101
  • 12,157
  • 5
  • 44
  • 63
  • Probably I'll use the second one, because every line can have 1024 characters, so I think it's better to use a list and read the input from the last character (so I add on the head of the list other characters, better than adding on the tail I think) – Alexei Aug 08 '20 at 08:55
  • NB, if I want to change a line, I have to rewrite all the line. This is why I thought to do a list for representing rows in the document (with number and a pointer to the text itself) and to save all characters in a single row. For undo/redo, I was thinking, thanks to the other reply, to save every command and its "antidote" with two separate stacks; it would be very fast in undo/redo operations, but it takes double of the space. My original idea was to save only the "antidote" to commands and, for redo, generate the command when the user gives an undo command – Alexei Aug 08 '20 at 09:05
0

Suppose you create just one stack (array?) and call it 'history'. As commands are made, add their 'antidote' (or pointers to them) to the stack, and adjust a pointer/counter to the last command. As your user steps back ('undo'), replace each command with it's 'antidote' (The code to put it there in the first place could be reused), so it's there for subsequent 'redo', and reposition the counter as needed . You'll have to allocate storage for deleted text, and link it to the stack position (2 dimensional (pointer?) array, or perhaps a struct?). If your stack gets full, delete the oldest- it's now 'out of range', and move everything accordingly... Or... Just allocate more memory... ;-)

Just an idea...

Remember, if it works properly, it isn't wrong. Perhaps just not the most efficient or effective way of doing it...

Don't forget to clear the stack on 'save', and most importantly, release any allocated memory on 'terminate'.

Mike.

Dharman
  • 30,962
  • 25
  • 85
  • 135
nuts'nbolts
  • 21
  • 6
  • I can't use an array, because I have to accept infinite undoes. This is why I want to use a stack (or just a single linked list) for undo and one for redo. So I can't accept a full stack. So I have just to think how to code an "antidote" for every command, right? – Alexei Aug 08 '20 at 08:49
  • And what if I save on two stacks "antidote" for one command and the command itself? It would be very fast on undo/redo request, but I have to double the space needed – Alexei Aug 08 '20 at 08:59
  • Infinite undo's- You'd then need an infinitely large store for the user's action log. Suppose you allocate memory for a modest 'log' and realloc()- ate as needed. See (https://stackoverflow.com/questions/3536153/c-dynamically-growing-array). A stack is an array, albeit accessed sequentially (usually) last in, first out (LIFO).. just (in your mind- the computer doesn't care) arranged "vertically". Remember, You're Coding This (YCT), so you can make it work any way you want- even "upside down" (most recent to the "bottom" of the list). 'Antidote' coding? Right. 2 stacks? YCT- Your choice. – nuts'nbolts Aug 08 '20 at 21:40
  • Just seen your update. I've always understood undo/redo to apply to the last action (look at any commercial software). If the user has just typed in (say) line 423, and then deletes line 24, Undo() would reinstate line 24, undo() again deletes line 423. Redo() reinstates line 423. No need to search- your 'last action' (pointer, index, counter, whatever you call it) is updated as you go- it's always "there". – nuts'nbolts Aug 08 '20 at 22:36
  • As an aside, you might want to 'trap' (AKA 'catch') undo's prior to the first action (program close?), and redo beyond the last (it then becomes 'repeat') depending on your (and your tutor's) sense of humour... – nuts'nbolts Aug 08 '20 at 22:37