add functions to support original key value hash

Question

for a hash data structure, it should have 'get', 'set', 'delete' functions, but it also needs to implement 'undo' and 'redo' operations. I am not sure what data structure can support 'undo' or 'redo' operation. Does stack in python can record the previous operations and support undo/redo. Following is original existing hash operations.

class Bucket:

    def __init__(self):
        self.bucket = []
    
    def get(self, key):
        for(k, v) in self.bucket:
            if k == key:
                return v
        return -1
    
    def update(self, key, value):
        found = False
        for i, kv in enumerate(self.bucket):
            if key == kv[0]:
                self.bucket[i] = (key, value)
                found = True
                break
        if not found:
            self.bucket.append((key, value))


    def remove(self, key):
        for i, kv in enumerate(self.bucket):
            if key == kv[0]:
                del self.bucket[i]


class MyHashMap:

    def __init__(self):
        self.key_space = 2069
        self.hash_table = [Bucket() for i in range(self.key_space)]
        

    def put(self, key: int, value: int) -> None:
        hash_key = key % self.key_space
        self.hash_table[hash_key].update(key, value)
        

    def get(self, key: int) -> int:
        hash_key = key % self.key_space
        return self.hash_table[hash_key].get(key)
        

    def remove(self, key: int) -> None:
        hash_key = key % self.key_space
        self.hash_table[hash_key].remove(key)
    

Answer 1

It seems you interpreted the challenge as if you were not allowed to use -- and extend -- the native dict, and tried to implement hashing from scratch.

As far as I understood, that is not the intention of the challenge.

The challenge is to add undo/redo functionality to the already existing dictionary features that are available in Python.

You can achieve this by maintaining a standard dict and add undo/redo stacks to the instance. With each call of set and delete you would do three things:

• Apply that action on the native dict
• Append the opposite action to the undo stack.
• Clear the redo stack

Then when the new undo method is called, pop the latest action from that undo stack and do two things:

• Apply that action on the native dict
• Append the opposite action on the redo stack.

The redo method is similar, just that it pops the action from the redo stack and appends the opposite action on the undo stack.

Here is an implementation:

class UndoableDict():
    def __init__(self):
        self.dict = {}
        self.undostack = []
        self.redostack = []

    def get(self, key):
        return self.dict.get(key)

    def set(self, key, value):
        if key in self.dict:
            prev = self.dict[key]
            self.dict[key] = value
            self.undostack.append(("update", key, prev))
        else:
            self.dict[key] = value
            self.undostack.append(("delete", key, None))
        self.redostack.clear()
        
    def delete(self, key):
        if key in self.dict:
            self.undostack.append(("add", key, self.dict.pop(key)))
            self.redostack.clear()

    # Common algorithm for undo and redo, just with different stacks:
    def _roll(self, fromstack, tostack):
        action, key, value = fromstack.pop()
        if action == "delete":
            tostack.append(("add", key, self.dict[key]))
            self.dict.pop(key)
        elif action == "add":
            tostack.append(("delete", key, None))
            self.dict[key] = value
        else:
            tostack.append(("update", key, self.dict[key]))
            self.dict[key] = value
    
    def undo(self):
        self._roll(self.undostack, self.redostack)

    def redo(self):
        self._roll(self.redostack, self.undostack)