Good collection for implementing Undo/Redo?

Question

I was reading around for undo/redo techniques, I understand how should it be implemented (I found it intuitive).

However I'm thinking about the collection that should be used as history,

A lot of people use stack, but C# stack is implemented as an array, and this is a problem: If I use a "limited" history (for example, for 2000 commands), when the limit is reached I don't have a way to remove items from the end of the stack, and if I find a way to do it, I have to move all elements of the array (and this for each time a command is done).

A LinkedList looks good, but it wastes a lot of memory.

My last option is a custom implementation of a linkedlist, a SingleLinkedList. A node of this list consist of Value property and a NextNode pointer property so I'm using double memory for each item (but nothing more,except if I'm using things smaller than "sizeof(void*)").

I'm also storing a pointer to the first element and a pointer to the last element in the collection.

I can easily add commands to the history and move them to the redohistory in this way, however I can't create a "limited" history because RemoveLast is not allowed (I have to go through the whole collection to remove the last item).

So my question is: Should I use a LinkedList or my custom SingleLinkedList?

Update 1:

Thanks for answers at the moment, in my situation I don't have a memory problem, well, I don't know who I am targeting, I'm creating an utility program and in my own idea of "utility program", they should waste least cpu/memory possible (obviusly don't tell me "write it in c++ so", because there is a big difference).

In my opinion, the singlelinkedlist works well, I don't really like to limit the History, I'm thinking about Photoshop where your history is "unlimited".

I'm only feared from what could happen when the undo history becomes really big, like 8 hours of use. That's why I was thinking about limiting it through a LinkedList.

As someone else stated however, if I limit the linkedlist to a big size, around 60000 commands (I think they should be enough), I'm only wasting a small amount of memory, (4 bytes * 60000) compared to singlelinkedlist.

That said, I think I'll use the LinkedList, however just to be sure, would have been ok if I've used an history without limit?

Update 2:

@Akash Kava Well, what you say it's important but you misunderstood WHY I want use a LinkedList and why I don't want use a stack. The main problem with Stack is that it's necessary to limit it's size, and there isn't a fast way to remove older commands when this limit is reached (it's an array and doubling it's dimension every time it's not something that we want).

A single linked list (think about how it's built) is fast as a stack (all stack operations are O(1)) and doesn't have a limit. However in this case it's needed not to have a limit, otherwise we have the same problem as stack, we don't have a fast way to remove last element of our singlelinkedlist (which behaves like a stack),because we don't know our previous node element from the last node.

In this case it's quite easy, so, to think about a LinkedList, where you have the Previous pointer. However we are using 2 additional pointers for each element of our "Stack" (which is built through a linkedlist this time), which is like using 3 times more memory than what it's necessary to store a Command (with an array we have normal memory usage, singlelinkedlist has 2 times memory usage and linkedlist has 3 times memory usage).

So what I was basically asking is which is the "best" collection to implement a stack for undo-redo pattern.

Your answer made me think that even if I create 60000 command in 1 program it's around 5MB of memory in a program, which is not so much.

Basically if you want to limit your undo/redo history you need a LinkedList, otherwise a SingleLinkedList is better.

Obreption

Not exact answer but have you looked to Undo Framework implementation: undo.codeplex.com ? – Cryometer

Have a look at the memento design pattern.- codeproject.com/KB/cs/generic_undo_redo.aspx – Upstate

Answer 1

Use a LinkedList, or any standard solution, for now, but be careful how you implement it. Put all your undo/redo actions behind a well designed abstraction. Then, if the extra memory that LinkedList is consuming really proves to be a problem (unlikely), you can replace it with your own implementation.

We do this all the time; wrap existing functionality in an abstraction so we can tinker with it if needs be because sometimes domain-specific conditions may offer a chance for extra efficiency. This is your case here; the linked list will work, but your problem domain suggests efficiencies may be possible at the cost of implementation.

Nonrigid

LinkedList would be preferred for data modification controls. Because when you have to commit changes (which are not applied immediately) to data source, you will have to convert Stack to Queue in order to merge all changes to actual data source. – Aside

Answer 2

LinkedList is first attempt however it becomes little complicated to enable/disable buttons and maintain state so I found better approach.

Stack<Action> undoStack;
Stack<Action> redoStack;

Can Undo/Redo conditions are simple

undoStack.Count > 0 (We can undo)
redoStack.Count > 0 (We can redo)

While modifying, we have to clear redoStack as we modify anything in active document, you can notice this clearly in VS, when you edit anything, redo goes disabled.

redoStack.Clear() <-- important step
undoStack.Push(action);

While undoing

Action action = undoStack.Pop();
redoStack.Push(action); <-- necessary...

While redoing

Action action = redoStack.Pop();
undoStack.Push(action);

Same can be implemented with linked list but it becomes complicated to manage head and tails and maintain the current pointer.

After reading your point I think you can use single linked list to implement undo and redo stack as you will only need one directional pointer. I just gave you a different way to look at how to solve this using stack (single linked list) that uses less memory and does not have state related issues.

Agitato

I answered to you in the question (I wrote a long answer) – Obreption

I see it, but Stack can be implemented via linked list or you can just consider two linked lists one for undo and one for redo. I just recently implemented it and found out that keeping one history store(linked list) leads to some state management problems so I divided them with two stacks or two linked lists. As you can implement stack usin single linked list, as you will never need next node as it will be part of other redo stack. – Agitato

Infact, I use everything as a stack, I was just thinking about which is the better collection to be used as a stack, I still think is SingleLinkedList if you want unlimited undo/redo stacks – Obreption

Answer 3

If you want a linked list, you should use a LinkedList. Why rewrite code that already exists? to save 16MB of RAM?

Jodhpurs

Answer 4

As I stated and as someone else suggested, having 1 addictional pointer per Node instead of an array is not a big problem, also let's suppose our value is another pointer, in case of 60000 commands we have 8 byte per node. 480 KB, a really low value if we think about it.

That said I think the best collection in this case is SingleLinkedList, allowing us unlimited undo/redo "stacks" (built around SingleLinkedList).

If is necessary to limit our stack size, a LinkedList is required.

Obreption

Answer 5

I'll come in with a weird answer and just say "whatever you want", because this is generally not a performance-critical case, especially with a limited history that starts popping off the oldest entries when reaching just 2000 undoable operations.

A doubly-linked list works fine. A double-ended queue works fine. A contiguous structure like ArrayList which requires you to remove from the front in linear-time like might still work just fine if each operation is just an object reference stored in it. A circular array can also work well if you have a fixed limit on the number of undo operations which can be recorded (in which case you can size the circular array in advance and it'll automatically start overwriting the oldest entries when it exceeds a certain capacity).

Since the only things you do with this are push back one time for an entire user operation, pop back one time for an entire undo operation, and maybe pop an element from the front if the user records an operation and the history starts getting full or using too much memory. It's not performance-critical at all. Unless you have a very unusual case where the user can record like ten thousand operations per second (would be pretty impressed just to see someone click that fast), there's just not that much that can happen since it's very bound by user input.

Of course what you store inside a single undo operation could be quite performance-critical, and there you might want a very efficient data representation that minimizes memory use (depending on how much state you store inside an undoable entry). But the outer undo stack/history really isn't very performance-critical at all, and I think just about all options are reasonable in such a case. This is coming from a guy who likes to reduce memory use to improve performance, but in this case your undo stack memory is "cold". A lot of it isn't accessed frequently (ex: not accessed every single frame) -- just when the user hits the undo button or records a new operation, unless you're targeting very limited hardware.

But if you want to squash things down which I don't think is really necessary, then an unrolled linked list sort of thing can work quite well. It's basically a linked list where each node stores more than one element inside. In that case the memory use of the links is trivialized. You can do something like this:

struct Node
{
     Command commands[n];
     Node next;
     Node prev;
     int first;
     int last;
}

When you undo, you can decrement the last counter of the tail node. If last == first, then pop it off and free it and make the previous node the new tail. When you record an operation, you can increment the last counter. If last == n, then allocate a new node and make that the new tail. When you want to start reducing the size of the history (i.e., remove an undo entry from the front), increment the first counter of the head node. If first == last, then deallocate the node and set the next node as the new head. That'll give you constant-time push backs, pop backs, and pop fronts while using very little memory on on a per-undo basis since you don't have to store the node data like the links on a per-undo basis (just once for every n undo entries you store, and you can make n a big number like 512, reducing the linked list overhead to 1/512 or ~1.95%) and improving locality of reference.

Cluster

Answer 6

You coud use a array with rotating startindex, and endindex values. Abstract the element retrieval and addition process in the synchronized class methods which also maintain startIndex, and endIndex, This method would have just a o(2) increase in memory instead of plain array backed stack.

Rake