Problem Description

Implement a simplified Paint editor that allows users to draw on a 2D canvas and manage changes using undo and redo operations.

Canvas

The canvas is represented as a 2D grid. Each cell within this grid can store either a color value (which can be a string or an integer) or None to indicate an empty cell. The canvas is initialized with a specified width and height. Coordinates are zero-based, given as (x, y) where x is the column index and y is the row index. All provided coordinates are guaranteed to be within the canvas boundaries.

Required Operations

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

• draw(x, y, color): Sets the pixel at the given (x, y) position to the specified color.
• erase(x, y): Removes the color at (x, y) by setting the cell back to empty (None).
• fill(x, y, color): Performs a flood fill operation starting from (x, y).
  • Let orig be the color currently present at (x, y).
  • The pixel at (x, y) is replaced with the new color.
  • Recursively, any adjacent cells (up, down, left, right) that also have the orig color are replaced with the new color.
  • The fill operation stops expanding when it encounters a cell with a different color or reaches the canvas boundary.
  • If orig is already equal to color, this operation may be a no-op.
• undo(): Reverts the canvas to the state immediately preceding the most recent modifying operation (draw, erase, or fill). If there are no operations to undo, this method performs no action.
• redo(): Re-applies the most recently undone operation, restoring the canvas to its state after that operation. If there is no operation to redo, this method performs no action.

Behavior Rules for Undo/Redo

• Any operation that modifies the canvas (draw, erase, fill) must be treated as an undoable action.
• When undo() is called, the reverted state is moved into a redo history, making it available for redo().
• When redo() is called, the re-applied state is moved back into the undo history.
• Performing any new modifying operation (draw, erase, fill) must clear the entire redo history.
• All operations must be deterministic and consistent.

Constraints and Assumptions

• The canvas dimensions can be up to a few thousand by a few thousand cells (e.g., 2000x2000).
• The system should support up to tens of thousands of operations (e.g., 50,000 operations).
• You are free to choose any reasonable data structures for representing the canvas and managing the undo/redo histories.
• Your implementation must correctly maintain the canvas state, the undo/redo history, and the flood fill behavior.