Design paint editor with undo/redo

Implement a simplified Paint editor that supports drawing on a 2D canvas and reverting changes using undo and redo operations.

Canvas

You are given a 2D grid representing a canvas. Each cell can store:

• a color value (string or integer), or
• None for an empty cell.

You will initialize the canvas with a given width and height. Assume coordinates are zero-based and given as (x, y) where x is the column index and y is the row index. Coordinates are guaranteed to be within bounds.

Required Operations

You must design and implement a Paint class with the following methods:

1. draw(x, y, color)
   • Set the pixel at position (x, y) to the given color .
2. erase(x, y)
   • Remove whatever color is at (x, y) and set it back to empty ( None ).
3. fill(x, y, color)
   • Perform a flood fill operation starting at (x, y) :
     • Let orig be the color currently at (x, y) .
     • Replace the pixel at (x, y) with color .
     • Recursively replace any adjacent cells (up, down, left, right) that have color orig with color .
     • Stop expanding when encountering a different color or the canvas boundary.
   • If orig is already equal to color , the operation may be a no-op.
4. undo()
   • Revert the canvas to the state before the most recent modifying operation ( draw , erase , or fill ).
   • If there is no operation to undo, this may be a no-op.
5. redo()
   • Re-apply the most recently undone operation, restoring the canvas to the state after that operation.
   • If there is no operation to redo, this may be a no-op.

Behavior Rules

• Any operation that modifies the canvas ( draw , erase , fill ) should become an undoable action.
• Calling undo() moves the current state into a redo history so that it can be restored with redo() .
• Calling redo() re-applies that state and moves it back into the undo history.
• After performing a new modifying operation ( draw , erase , fill ), the redo history must be cleared.
• All operations should be deterministic and consistent.

Requirements

• Design and implement the Paint class and its methods.
• You may choose any reasonable data structures for representing:
  • The canvas.
  • Undo and redo histories.
• Your implementation must correctly maintain canvas state, undo/redo history, and fill behavior.

Assume reasonable constraints, e.g., canvas up to a few thousand by a few thousand cells and up to tens of thousands of operations.