1 | from abc import ABCMeta, abstractmethod |
||
2 | |||
3 | from pyalgs.algorithms.commons import util |
||
4 | from pyalgs.data_structures.commons.queue import Queue |
||
5 | |||
6 | |||
7 | class HashedSet(object): |
||
8 | __metaclass__ = ABCMeta |
||
9 | |||
10 | @abstractmethod |
||
11 | def add(self, key): |
||
12 | pass |
||
13 | |||
14 | @abstractmethod |
||
15 | def delete(self, key): |
||
16 | pass |
||
17 | |||
18 | @abstractmethod |
||
19 | def size(self): |
||
20 | pass |
||
21 | |||
22 | @abstractmethod |
||
23 | def is_empty(self): |
||
24 | pass |
||
25 | |||
26 | @abstractmethod |
||
27 | def iterate(self): |
||
28 | pass |
||
29 | |||
30 | @abstractmethod |
||
31 | def contains(self, key): |
||
32 | pass |
||
33 | |||
34 | @staticmethod |
||
35 | def create(): |
||
36 | return HashedSetWithSeparateChaining() |
||
37 | |||
38 | |||
39 | class Node(object): |
||
40 | key = None |
||
41 | next_node = None |
||
42 | |||
43 | def __init__(self, key=None): |
||
44 | self.key = key |
||
45 | |||
46 | |||
47 | class HashedSetWithSeparateChaining(HashedSet): |
||
48 | M = 97 |
||
49 | id = None |
||
50 | N = 0 |
||
51 | |||
52 | def __init__(self, m=None): |
||
53 | if m is None: |
||
54 | m = 97 |
||
55 | self.M = m |
||
56 | self.id = [None] * self.M |
||
57 | |||
58 | def hash(self, key): |
||
59 | return (hash(key) & 0x7fffffff) % self.M |
||
60 | |||
61 | def is_empty(self): |
||
62 | return self.N == 0 |
||
63 | |||
64 | def iterate(self): |
||
65 | for i in range(self.M): |
||
66 | x = self.id[i] |
||
67 | while x is not None: |
||
68 | key = x.key |
||
69 | x = x.next_node |
||
70 | yield key |
||
71 | |||
72 | def size(self): |
||
73 | return self.N |
||
74 | |||
75 | def contains(self, key): |
||
76 | i = self.hash(key) |
||
77 | x = self.id[i] |
||
78 | while x is not None: |
||
79 | if util.cmp(x.key, key) == 0: |
||
80 | return True |
||
81 | x = x.next_node |
||
82 | return False |
||
83 | |||
84 | View Code Duplication | def delete(self, key): |
|
0 ignored issues
–
show
Duplication
introduced
by
Loading history...
|
|||
85 | i = self.hash(key) |
||
86 | x = self.id[i] |
||
87 | prev_node = None |
||
88 | while x is not None: |
||
89 | if util.cmp(x.key, key) == 0: |
||
90 | next_node = x.next_node |
||
91 | self.N -= 1 |
||
92 | if prev_node is not None: |
||
93 | prev_node.next_node = next_node |
||
94 | if self.id[i] == x: |
||
95 | self.id[i] = None |
||
96 | return True |
||
97 | prev_node = x |
||
98 | x = x.next_node |
||
99 | return False |
||
100 | |||
101 | def add(self, key): |
||
102 | if key is None: |
||
103 | raise ValueError('key cannot be None') |
||
104 | |||
105 | i = self.hash(key) |
||
106 | x = self.id[i] |
||
107 | while x is not None: |
||
108 | if util.cmp(x.key, key) == 0: |
||
109 | return |
||
110 | x = x.next_node |
||
111 | old_first = self.id[i] |
||
112 | self.id[i] = Node(key) |
||
113 | self.id[i].next_node = old_first |
||
114 | self.N += 1 |
||
115 | |||
116 | |||
117 | class HashedSetWithLinearProbing(HashedSet): |
||
118 | |||
119 | M = 97 |
||
120 | id = None |
||
121 | N = 0 |
||
122 | |||
123 | def __init__(self, m=None): |
||
124 | if m is None: |
||
125 | m = 97 |
||
126 | self.M = m |
||
127 | self.id = [None] * self.M |
||
128 | |||
129 | def hash(self, key): |
||
130 | return (hash(key) & 0x7fffffff) % self.M |
||
131 | |||
132 | def is_empty(self): |
||
133 | return self.N == 0 |
||
134 | |||
135 | def iterate(self): |
||
136 | for i in range(self.M): |
||
137 | x = self.id[i] |
||
138 | if x is not None: |
||
139 | yield x.key |
||
140 | |||
141 | def size(self): |
||
142 | return self.N |
||
143 | |||
144 | def contains(self, key): |
||
145 | i = self.hash(key) |
||
146 | for j in range(self.M): |
||
147 | k = (i + j) % self.M |
||
148 | x = self.id[k] |
||
149 | if x is None: |
||
150 | return False |
||
151 | if util.cmp(key, x.key) == 0: |
||
152 | return True |
||
153 | |||
154 | def delete(self, key): |
||
155 | i = self.hash(key) |
||
156 | for j in range(self.M): |
||
157 | k = (i + j) % self.M |
||
158 | x = self.id[k] |
||
159 | if x is None: |
||
160 | return False |
||
161 | if util.cmp(key, x.key) == 0: |
||
162 | self.id[k] = None |
||
163 | self.N -= 1 |
||
164 | if self.N == self.M // 4: |
||
165 | self.resize(self.M // 2) |
||
166 | return True |
||
167 | |||
168 | View Code Duplication | def add(self, key): |
|
0 ignored issues
–
show
|
|||
169 | i = self.hash(key) |
||
170 | for j in range(self.M): |
||
171 | k = (i + j) % self.M |
||
172 | x = self.id[k] |
||
173 | if x is None: |
||
174 | self.id[k] = Node(key) |
||
175 | self.N += 1 |
||
176 | if self.N == self.M // 2: |
||
177 | self.resize(self.M * 2) |
||
178 | break |
||
179 | if util.cmp(x.key, key) == 0: |
||
180 | break |
||
181 | |||
182 | def resize(self, new_size): |
||
183 | clone = HashedSetWithLinearProbing(new_size) |
||
184 | for i in range(self.M): |
||
185 | x = self.id[i] |
||
186 | if x is not None: |
||
187 | clone.add(x.key) |
||
188 | self.M = clone.M |
||
189 | self.id = clone.id |
||
190 |