prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  [BUG] Cannot pop from Cache during dispatch.
  ### Describe the bug.
  
  When running functions leading to delete events, for example `channel.purge` the cache encounters a KeyError and kills the whole Process.
  
  This is caused by the implementation of #482
  
  ### List the steps.
  
  n/A
  
  ### What you expected.
  
  n/A
  
  ### What you saw.
  ```
  Websocket have raised an exception, closing.
  Traceback (most recent call last):
    File "C:\Users\\Desktop\PycharmProjects\library\interactions\client\bot.py", line 440, in _login
      await self._websocket.run()
    File "C:\Users\\Desktop\PycharmProjects\library\interactions\api\gateway\client.py", line 279, in run
      await self._handle_stream(msg)
    File "C:\Users\\Desktop\PycharmProjects\library\interactions\api\gateway\client.py", line 332, in _handle_stream
      self._dispatch_event(event, data)
    File "C:\Users\\Desktop\PycharmProjects\library\interactions\api\gateway\client.py", line 562, in _dispatch_event
      _message_cache.pop(message_id)
    File "C:\Users\\Desktop\PycharmProjects\library\interactions\api\cache.py", line 131, in pop
      return self.values.pop(key, default)
    File "C:\Users\\Desktop\PycharmProjects\library\interactions\utils\dict_caches.py", line 39, in __getitem__
      self.move_to_end(key)
  KeyError: Snowflake(1040316644695756912)
  
  Process finished with exit code 0
  ```
  
  ### What version of the library did you use?
  
  unstable
  
  ### Version specification
  
  The unstable unstable version
  
  ### Code of Conduct
  
  - [X] I agree to follow the contribution requirements.
  [BUG] Cannot pop from Cache during dispatch.
  ### Describe the bug.
  
  When running functions leading to delete events, for example `channel.purge` the cache encounters a KeyError and kills the whole Process.
  
  This is caused by the implementation of #482
  
  ### List the steps.
  
  n/A
  
  ### What you expected.
  
  n/A
  
  ### What you saw.
  ```
  Websocket have raised an exception, closing.
  Traceback (most recent call last):
    File "C:\Users\\Desktop\PycharmProjects\library\interactions\client\bot.py", line 440, in _login
      await self._websocket.run()
    File "C:\Users\\Desktop\PycharmProjects\library\interactions\api\gateway\client.py", line 279, in run
      await self._handle_stream(msg)
    File "C:\Users\\Desktop\PycharmProjects\library\interactions\api\gateway\client.py", line 332, in _handle_stream
      self._dispatch_event(event, data)
    File "C:\Users\\Desktop\PycharmProjects\library\interactions\api\gateway\client.py", line 562, in _dispatch_event
      _message_cache.pop(message_id)
    File "C:\Users\\Desktop\PycharmProjects\library\interactions\api\cache.py", line 131, in pop
      return self.values.pop(key, default)
    File "C:\Users\\Desktop\PycharmProjects\library\interactions\utils\dict_caches.py", line 39, in __getitem__
      self.move_to_end(key)
  KeyError: Snowflake(1040316644695756912)
  
  Process finished with exit code 0
  ```
  
  ### What version of the library did you use?
  
  unstable
  
  ### Version specification
  
  The unstable unstable version
  
  ### Code of Conduct
  
  - [X] I agree to follow the contribution requirements.
  
  </issue>
  <code>
  [start of interactions/utils/dict_caches.py]
  1 from collections import OrderedDict
  2 from typing import Generic, TypeVar
  3 
  4 __all__ = ("FIFODict", "LRUDict")
  5 
  6 _KT = TypeVar("_KT")
  7 _VT = TypeVar("_VT")
  8 
  9 
  10 class FIFODict(OrderedDict, Generic[_KT, _VT]):
  11     """A dictionary that removes the old keys if over the item limit"""
  12 
  13     def __init__(self, *args, max_items: int = float("inf"), **kwargs):
  14         if max_items < 0:
  15             raise RuntimeError("You cannot set max_items to negative numbers.")
  16 
  17         super().__init__(*args, **kwargs)
  18         self._max_items = max_items
  19 
  20     def __setitem__(self, key: _KT, value: _VT):
  21         super().__setitem__(key, value)
  22 
  23         # Prevent buildup over time
  24         while len(self) > self._max_items:
  25             del self[next(iter(self))]
  26 
  27 
  28 class LRUDict(OrderedDict, Generic[_KT, _VT]):
  29     """A dictionary that removes the value that was the least recently used if over the item limit"""
  30 
  31     def __init__(self, *args, max_items: int = float("inf"), **kwargs):
  32         if max_items < 0:
  33             raise RuntimeError("You cannot set max_items to negative numbers.")
  34 
  35         super().__init__(*args, **kwargs)
  36         self._max_items = max_items
  37 
  38     def __getitem__(self, key: _KT) -> _VT:
  39         self.move_to_end(key)
  40         return super().__getitem__(key)
  41 
  42     def __setitem__(self, key: _KT, value: _VT):
  43         super().__setitem__(key, value)
  44 
  45         # Prevent buildup over time
  46         while len(self) > self._max_items:
  47             del self[next(iter(self))]
  48
  [end of interactions/utils/dict_caches.py]
  </code>
  
  I need you to solve this issue by generating a single patch file that I can apply directly to this repository using git apply. Please respond with a single patch file in the following format.
  <patch>
  diff --git a/file.py b/file.py
  --- a/file.py
  +++ b/file.py
  @@ -1,27 +1,35 @@
   def euclidean(a, b):
  -    while b:
  -        a, b = b, a % b
  -    return a
  +    if b == 0:
  +        return a
  +    return euclidean(b, a % b)
   
   
   def bresenham(x0, y0, x1, y1):
       points = []
       dx = abs(x1 - x0)
       dy = abs(y1 - y0)
  -    sx = 1 if x0 < x1 else -1
  -    sy = 1 if y0 < y1 else -1
  -    err = dx - dy
  +    x, y = x0, y0
  +    sx = -1 if x0 > x1 else 1
  +    sy = -1 if y0 > y1 else 1
   
  -    while True:
  -        points.append((x0, y0))
  -        if x0 == x1 and y0 == y1:
  -            break
  -        e2 = 2 * err
  -        if e2 > -dy:
  -            err -= dy
  -            x0 += sx
  -        if e2 < dx:
  -            err += dx
  -            y0 += sy
  +    if dx > dy:
  +        err = dx / 2.0
  +        while x != x1:
  +            points.append((x, y))
  +            err -= dy
  +            if err < 0:
  +                y += sy
  +                err += dx
  +            x += sx
  +    else:
  +        err = dy / 2.0
  +        while y != y1:
  +            points.append((x, y))
  +            err -= dx
  +            if err < 0:
  +                x += sx
  +                err += dy
  +            y += sy
  +
  +    points.append((x, y))
       return points
  
  </patch>
golden_diff: diff --git a/interactions/utils/dict_caches.py b/interactions/utils/dict_caches.py
  --- a/interactions/utils/dict_caches.py
  +++ b/interactions/utils/dict_caches.py
  @@ -1,6 +1,8 @@
   from collections import OrderedDict
   from typing import Generic, TypeVar
   
  +from .missing import MISSING
  +
   __all__ = ("FIFODict", "LRUDict")
   
   _KT = TypeVar("_KT")
  @@ -45,3 +47,14 @@
           # Prevent buildup over time
           while len(self) > self._max_items:
               del self[next(iter(self))]
  +
  +    __marker = object()
  +
  +    def pop(self, key: _KT, default: _VT = __marker) -> _VT:
  +        if key in self:
  +            result = self[key]
  +            del self[key]
  +            return result
  +        if default is MISSING:
  +            raise KeyError(key)
  +        return default
  
verification_info: {"golden_diff": "diff --git a/interactions/utils/dict_caches.py b/interactions/utils/dict_caches.py\n--- a/interactions/utils/dict_caches.py\n+++ b/interactions/utils/dict_caches.py\n@@ -1,6 +1,8 @@\n from collections import OrderedDict\n from typing import Generic, TypeVar\n \n+from .missing import MISSING\n+\n __all__ = (\"FIFODict\", \"LRUDict\")\n \n _KT = TypeVar(\"_KT\")\n@@ -45,3 +47,14 @@\n         # Prevent buildup over time\n         while len(self) > self._max_items:\n             del self[next(iter(self))]\n+\n+    __marker = object()\n+\n+    def pop(self, key: _KT, default: _VT = __marker) -> _VT:\n+        if key in self:\n+            result = self[key]\n+            del self[key]\n+            return result\n+        if default is MISSING:\n+            raise KeyError(key)\n+        return default\n", "issue": "[BUG] Cannot pop from Cache during dispatch.\n### Describe the bug.\r\n\r\nWhen running functions leading to delete events, for example `channel.purge` the cache encounters a KeyError and kills the whole Process.\r\n\r\nThis is caused by the implementation of #482\r\n\r\n### List the steps.\r\n\r\nn/A\r\n\r\n### What you expected.\r\n\r\nn/A\r\n\r\n### What you saw.\r\n```\r\nWebsocket have raised an exception, closing.\r\nTraceback (most recent call last):\r\n  File \"C:\\Users\\\\Desktop\\PycharmProjects\\library\\interactions\\client\\bot.py\", line 440, in _login\r\n    await self._websocket.run()\r\n  File \"C:\\Users\\\\Desktop\\PycharmProjects\\library\\interactions\\api\\gateway\\client.py\", line 279, in run\r\n    await self._handle_stream(msg)\r\n  File \"C:\\Users\\\\Desktop\\PycharmProjects\\library\\interactions\\api\\gateway\\client.py\", line 332, in _handle_stream\r\n    self._dispatch_event(event, data)\r\n  File \"C:\\Users\\\\Desktop\\PycharmProjects\\library\\interactions\\api\\gateway\\client.py\", line 562, in _dispatch_event\r\n    _message_cache.pop(message_id)\r\n  File \"C:\\Users\\\\Desktop\\PycharmProjects\\library\\interactions\\api\\cache.py\", line 131, in pop\r\n    return self.values.pop(key, default)\r\n  File \"C:\\Users\\\\Desktop\\PycharmProjects\\library\\interactions\\utils\\dict_caches.py\", line 39, in __getitem__\r\n    self.move_to_end(key)\r\nKeyError: Snowflake(1040316644695756912)\r\n\r\nProcess finished with exit code 0\r\n```\r\n\r\n### What version of the library did you use?\r\n\r\nunstable\r\n\r\n### Version specification\r\n\r\nThe unstable unstable version\r\n\r\n### Code of Conduct\r\n\r\n- [X] I agree to follow the contribution requirements.\n[BUG] Cannot pop from Cache during dispatch.\n### Describe the bug.\r\n\r\nWhen running functions leading to delete events, for example `channel.purge` the cache encounters a KeyError and kills the whole Process.\r\n\r\nThis is caused by the implementation of #482\r\n\r\n### List the steps.\r\n\r\nn/A\r\n\r\n### What you expected.\r\n\r\nn/A\r\n\r\n### What you saw.\r\n```\r\nWebsocket have raised an exception, closing.\r\nTraceback (most recent call last):\r\n  File \"C:\\Users\\\\Desktop\\PycharmProjects\\library\\interactions\\client\\bot.py\", line 440, in _login\r\n    await self._websocket.run()\r\n  File \"C:\\Users\\\\Desktop\\PycharmProjects\\library\\interactions\\api\\gateway\\client.py\", line 279, in run\r\n    await self._handle_stream(msg)\r\n  File \"C:\\Users\\\\Desktop\\PycharmProjects\\library\\interactions\\api\\gateway\\client.py\", line 332, in _handle_stream\r\n    self._dispatch_event(event, data)\r\n  File \"C:\\Users\\\\Desktop\\PycharmProjects\\library\\interactions\\api\\gateway\\client.py\", line 562, in _dispatch_event\r\n    _message_cache.pop(message_id)\r\n  File \"C:\\Users\\\\Desktop\\PycharmProjects\\library\\interactions\\api\\cache.py\", line 131, in pop\r\n    return self.values.pop(key, default)\r\n  File \"C:\\Users\\\\Desktop\\PycharmProjects\\library\\interactions\\utils\\dict_caches.py\", line 39, in __getitem__\r\n    self.move_to_end(key)\r\nKeyError: Snowflake(1040316644695756912)\r\n\r\nProcess finished with exit code 0\r\n```\r\n\r\n### What version of the library did you use?\r\n\r\nunstable\r\n\r\n### Version specification\r\n\r\nThe unstable unstable version\r\n\r\n### Code of Conduct\r\n\r\n- [X] I agree to follow the contribution requirements.\n", "before_files": [{"content": "from collections import OrderedDict\nfrom typing import Generic, TypeVar\n\n__all__ = (\"FIFODict\", \"LRUDict\")\n\n_KT = TypeVar(\"_KT\")\n_VT = TypeVar(\"_VT\")\n\n\nclass FIFODict(OrderedDict, Generic[_KT, _VT]):\n    \"\"\"A dictionary that removes the old keys if over the item limit\"\"\"\n\n    def __init__(self, *args, max_items: int = float(\"inf\"), **kwargs):\n        if max_items < 0:\n            raise RuntimeError(\"You cannot set max_items to negative numbers.\")\n\n        super().__init__(*args, **kwargs)\n        self._max_items = max_items\n\n    def __setitem__(self, key: _KT, value: _VT):\n        super().__setitem__(key, value)\n\n        # Prevent buildup over time\n        while len(self) > self._max_items:\n            del self[next(iter(self))]\n\n\nclass LRUDict(OrderedDict, Generic[_KT, _VT]):\n    \"\"\"A dictionary that removes the value that was the least recently used if over the item limit\"\"\"\n\n    def __init__(self, *args, max_items: int = float(\"inf\"), **kwargs):\n        if max_items < 0:\n            raise RuntimeError(\"You cannot set max_items to negative numbers.\")\n\n        super().__init__(*args, **kwargs)\n        self._max_items = max_items\n\n    def __getitem__(self, key: _KT) -> _VT:\n        self.move_to_end(key)\n        return super().__getitem__(key)\n\n    def __setitem__(self, key: _KT, value: _VT):\n        super().__setitem__(key, value)\n\n        # Prevent buildup over time\n        while len(self) > self._max_items:\n            del self[next(iter(self))]\n", "path": "interactions/utils/dict_caches.py"}]}