P2mmGFi2

1""" HashMap implementation. """
2from typing import Any
3import abc
4
5class Error(Exception):
6    """ Base class for custom exceptions raised by this module """
7
8class NoSuchKeyError(Error):
9    """ No such key exception. """
10
11class EmptyCapacityError(Error):
12    """ Empty capacity for the hash map exception. """
13
14class HashMapBase(abc.ABC):
15    """ Base class for hash map implementations. It defines API. """
16    @abc.abstractmethod
17    def __init__(self, **opts):
18        if 'capacity' in opts:
19            self.capacity = opts['capacity']
20    @abc.abstractmethod
21    def get(self, key: Any) -> Any:
22        """ Gets value for the specified key. """
23    @abc.abstractmethod
24    def set(self, key: Any, value: Any) -> None:
25        """ Sets value for the specified key. """
26    @abc.abstractmethod
27    def exists(self, key: Any) -> bool:
28        """ Checks if the given key exists in the hash map. """
29    @abc.abstractmethod
30    def remove(self, key: Any) -> None:
31        """ Removes the specified key from hash map. """
32
33    def hash(self, key: Any):
34        """ Calculates the hash number for the given key based on the current capacity. """
35        if self.capacity == 0:
36            return EmptyCapacityError()
37
38        return hash(key) % self.capacity
39
40class HashMap(HashMapBase):
41    """
42    One of possible hash map implementations based on closed addressing and list for every cell.
43    """
44    default_capacity = 1024
45
46    def __init__(self, **opts):
47        if 'capacity' not in opts:
48            opts['capacity'] = self.default_capacity
49        super().__init__(**opts)
50        self.data = [[] for _ in range(self.capacity)]
51
52    def resize(self):
53        """
54        Resizes object whenever it takes too much or too few space compared to the capacity.
55        This allows to keep number of collision and capacity appropriate to the current usage.
56        TODO: not implemented yet.
57        Most probably, we also need min and max fill factors in constructor for this.
58        """
59
60    def get(self, key: Any) -> Any:
61        hash_value = self.hash(key)
62        for cur_key, value in self.data[hash_value]:
63            if cur_key == key:
64                return value
65        raise NoSuchKeyError()
66
67    def exists(self, key: Any) -> bool:
68        hash_value = hash(key)
69        for cur_key, _ in self.data[hash_value]:
70            if cur_key == key:
71                return True
72        return False
73
74    def set(self, key: Any, value: Any) -> None:
75        # call it before set in order to prevent zero capacity problems
76        self.resize()
77
78        hash_value = self.hash(key)
79        for i, (cur_key, _) in enumerate(self.data[hash_value]):
80            if cur_key == key:
81                self.data[hash_value][i] = (key, value)
82                return
83        self.data[hash_value].append((key, value))
84
85    def remove(self, key: Any) -> None:
86        hash_value = self.hash(key)
87        for i, (cur_key, _) in enumerate(self.data[hash_value]):
88            if cur_key == key:
89                del self.data[hash_value][i]
90                self.resize()
91                return
92
93        raise NoSuchKeyError()
94