I want to implement Undo-Redo functionality using stacks. When the user presses Ctrl+Z the last node will be removed from the screen. When the user press again Ctrl+Z then the "last.last" node will be removed from the screen and if he presses Ctrl+Y then the last removed node will display again on the screen.
Below is my code:
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class Stack:
def __init__(self):
self.pointer = None
def push(self, x):
if not isinstance(x, Node):
x = Node(x)
if self.is_empty():
self.pointer = x
undo_stack = Stack()
undo_stack.undo(x)
else:
x.next = self.pointer
self.pointer = x
def pop(self):
if self.is_empty():
print(f'Stack Underflow')
else:
self.pointer = self.pointer.next
def is_empty(self):
return self.pointer is None
def __str__(self):
string = ''
current = self.pointer
while current:
string += f'{current.data}->'
current = current.next
if string:
print(f'Stack Pointer = {self.pointer.data}')
return f'[{string[:-2]}]'
return '[]'
def undo(self, x):
self.push(x)
print(x)
def redo(self, x):
self.pop(x)
print(x)
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)
print(stack)
Suppose I have a stack
Stack: [5->4->3->2->1]
When I press Control+Z, the undo() function calls the pop() function and removes the last added item from the stack.
5 popped. Stack: [4->3->2->1]
again I press Control+Z, then:
4 popped. Stack: [3->2->1]
When I press Control+Y the redo() function is called and the previously removed items appear on the terminal.
4 pushed. Stack: [4->3->2->1]
again I press Control+Y, then
5 pushed. Stack: [5->4->3->2->1]
RecursionError: maximum recursion depth exceeded while calling a Python object
I know why this error occurs because inside the push() I made a call to the undo(), and inside the undo() I made a call to the push(). What should I do to implement undo-redo functionality, should I make a new class and implement Undo/Redo on that class?
Any ideas/ code will be highly appreciatable.
There are a few errors in this. The main issue causing the infinite recursion is this:
undo_stack = Stack()
undo_stack.undo(x)
Here, you are combining two different approaches. You could either have two separate stacks in your UndoRedoStack class and swap elements back and forth when undo/redo is called, or you could have a single doubly-linked list of nodes and step up or down the list every time you want to undo/redo. Here, you seem to be doing both, and you are creating an infinite number of Stacks in the process.
Instead, all you need to do is add one line:
else:
x.next = self.pointer
self.pointer.prev = x # You forgot this
self.pointer = x
Then, you don't need to make any other stacks. You can just walk up/down the chain in both directions.
There were also a number of other small mistakes that would have prevented the class from working as intended. I've fixed those up here:
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
def __str__(self):
return f"Node({self.data})"
class Stack:
def __init__(self):
self.pointer = None
def push(self, x):
if not isinstance(x, Node):
x = Node(x)
if self.is_empty():
self.pointer = x
else:
x.next = self.pointer
self.pointer.prev = x
self.pointer = x
def pop(self):
if self.is_empty():
print(f'Stack Underflow')
else:
self.pointer = self.pointer.next
def is_empty(self):
return self.pointer is None
def __str__(self):
string = ''
current = self.pointer
while current:
string += f'{current.data}->'
current = current.next
if string:
print(f'Stack Pointer = {self.pointer.data}')
return f'[{string[:-2]}]'
return '[]'
def undo(self):
x = self.pointer
self.pop()
print(x)
def redo(self):
x = self.pointer.prev
if x is None:
print("nothing to redo")
else:
self.push(x)
print(x)
if __name__ == "__main__":
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)
print("stack is:")
print(stack)
print()
stack.undo()
print("after undo:")
print(stack)
print()
stack.redo()
print("after redo:")
print(stack)