Data Structures in Action: Using stack for undo/redo functionality in a text editor

nqvinhtong
python 301 data structure undo/redo functionality a text editor

Problem

We want to implement undo/redo functionality in a text editor. When a user makes changes to the document, those edits should be stored for potential undo actions. Additionally, after undoing an edit, the user should be able to redo it.

Data Structures

  • Stack: We can use a stack to store the history of editing actions (insertions, deletions, etc.). Each element in the stack would represent a specific edit made to the document content.
  • Queue (Optional): An alternative approach might involve using a queue for storing redo actions. Whenever an undo operation is performed, the previous document state (before the undo) is pushed onto a queue, allowing the user to redo the action later.

Implementation

Stack

class Stack:
  def __init__(self):
    self.items = []

  def push(self, item):
    self.items.append(item)

  def pop(self):
    if not self.is_empty():
      return self.items.pop()

  def is_empty(self):
    return len(self.items) == 0

Class TechEditor

class TextEditor:
  def __init__(self):
    self.content = ""
    self.undo_history = Stack()

  def insert_text(self, text, position):
    self.content = self.content[:position] + text + self.content[position:]
    self.undo_history.push({"action": "insert", "text": text, "position": position})

  def delete_text(self, start, end):
    removed_text = self.content[start:end]
    self.content = self.content[:start] + self.content[end:]
    self.undo_history.push({"action": "delete", "text": removed_text, "start": start, "end": end})

  def undo(self):
    if not self.undo_history.is_empty():
      edit = self.undo_history.pop()
      if edit["action"] == "insert":
        self.content = self.content[:edit["position"]] + self.content[edit["position"] + len(edit["text"]) :]
      elif edit["action"] == "delete":
        self.content = self.content[:edit["start"]] + edit["text"] + self.content[edit["start"]:]

  def get_content(self):
    return self.content

Example usage

# Example usage
editor = TextEditor()
editor.insert_text("Hello", 0)
editor.insert_text(" Corgi", 5)
editor.delete_text(6, 11)  # Delete "Corgi"

print("Current content:", editor.get_content())  # Output: Hello

editor.undo()

print("Content after undo:", editor.get_content())  # Output: Hello Corgi

You can similarly implement a redo function using a queue (optional)

Explanation

  • We define Stack and TextEditor classes.
  • TextEditor stores the current document content and an undo history stack.
  • insert_text and delete_text edit the content and push the corresponding action onto the undo history stack.
  • undo pops the most recent edit from the stack and reverts the changes based on the edit type.

This example showcases how a stack can be used to maintain a history of edits, enabling users to undo their actions in a text editor. You could extend this concept to more complex scenarios involving different editing operations and potentially using a queue for redo functionality.

Related posts

Leave a Comment