HashedMapWithLinearProbing.__init__() - Code Metrics - Inspection of "Implement hashed map with linear probing" - chen0040/pyalgs - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 90dc7f...bdb684 )

by Xianshun

created 2017-04-26 06:32 UTC

HashedMapWithLinearProbing.init() A

↳ Parent: HashedMapWithLinearProbing

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	2
c	1
b	0
f	0
dl	0
loc	5
rs	9.4285

from abc import ABCMeta, abstractmethod

from pyalgs.algorithms.commons import util
from pyalgs.data_structures.commons.queue import Queue


class HashedMap(object):
    __metaclass__ = ABCMeta

    @abstractmethod
    def put(self, key, value):
        pass

    @abstractmethod
    def get(self, key):
        pass

    @abstractmethod
    def delete(self, key):
        pass

    @abstractmethod
    def size(self):
        pass

    @abstractmethod
    def is_empty(self):
        pass

    @abstractmethod
    def keys(self):
        pass

    @abstractmethod
    def contains_key(self, key):
        pass

    @staticmethod
    def create():
        return HashedMapWithSeparateChaining()


class Node(object):
    key = None
    value = None
    next_node = None

    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value


class HashedMapWithSeparateChaining(HashedMap):
    M = 97
    id = None
    N = 0

    def __init__(self, m=None):
        if m is None:
            m = 97
        self.M = m
        self.id = [None] * self.M

    def hash(self, key):
        return (hash(key) & 0x7fffffff) % self.M

    def is_empty(self):
        return self.N == 0

    def contains_key(self, key):
        return self.get(key) is not None

    def keys(self):
        for i in range(self.M):
            x = self.id[i]
            while x is not None:
                key = x.key
                x = x.next_node
                yield key

    def size(self):
        return self.N

    def get(self, key):
        i = self.hash(key)
        x = self.id[i]
        while x is not None:
            if util.cmp(x.key, key) == 0:
                return x.value
            x = x.next_node
        return None

    def delete(self, key):
        i = self.hash(key)
        x = self.id[i]
        prev_node = None
        while x is not None:
            if util.cmp(x.key, key) == 0:
                value = x.value
                next_node = x.next_node
                self.N -= 1
                if prev_node is not None:
                    prev_node.next_node = next_node
                if self.id[i] == x:
                    self.id[i] = None
                return value
            prev_node = x
            x = x.next_node
        return None

    def put(self, key, value):
        if key is None:
            raise ValueError('key cannot be None')

        i = self.hash(key)
        x = self.id[i]
        while x is not None:
            if util.cmp(x.key, key) == 0:
                x.value = value
                return
            x = x.next_node
        old_first = self.id[i]
        self.id[i] = Node(key, value)
        self.id[i].next_node = old_first
        self.N += 1


class HashedMapWithLinearProbing(HashedMap):

    M = 97
    id = None
    N = 0

    def __init__(self, m=None):
        if m is None:
            m = 97
        self.M = m
        self.id = [None] * self.M

    def hash(self, key):
        return (hash(key) & 0x7fffffff) % self.M

    def contains_key(self, key):
        return self.get(key) is not None

    def is_empty(self):
        return self.N == 0

    def keys(self):
        for i in range(self.M):
            x = self.id[i]
            if x is not None:
                yield x.value

    def size(self):
        return self.N

    def get(self, key):
        i = self.hash(key)
        for j in range(self.M):
            k = (i + j) % self.M
            x = self.id[k]
            if x is None:
                return None
            if util.cmp(key, x.key) == 0:
                return x.value

    def delete(self, key):
        i = self.hash(key)
        for j in range(self.M):
            k = (i + j) % self.M
            x = self.id[k]
            if x is None:
                return None
            if util.cmp(key, x.key) == 0:
                self.id[k] = None
                self.N -= 1
                if self.N == self.M // 4:
                    self.resize(self.M // 2)
                return x.value

    def put(self, key, value):
        i = self.hash(key)
        for j in range(self.M):
            k = (i + j) % self.M
            x = self.id[k]
            if x is None:
                self.id[k] = Node(key, value)
                self.N += 1
                if self.N == self.M // 2:
                    self.resize(self.M * 2)
                break
            if util.cmp(x.key, key) == 0:
                self.id[k].value = value
                break

    def resize(self, new_size):
        clone = HashedMapWithLinearProbing(new_size)
        for i in range(self.M):
            x = self.id[i]
            if x is not None:
                clone.put(x.key, x.value)
        self.M = clone.M
        self.id = clone.id


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 HashedMap(object):
8			__metaclass__ = ABCMeta
9
10			@abstractmethod
11			def put(self, key, value):
12			pass
13
14			@abstractmethod
15			def get(self, key):
16			pass
17
18			@abstractmethod
19			def delete(self, key):
20			pass
21
22			@abstractmethod
23			def size(self):
24			pass
25
26			@abstractmethod
27			def is_empty(self):
28			pass
29
30			@abstractmethod
31			def keys(self):
32			pass
33
34			@abstractmethod
35			def contains_key(self, key):
36			pass
37
38			@staticmethod
39			def create():
40			return HashedMapWithSeparateChaining()
41
42
43			class Node(object):
44			key = None
45			value = None
46			next_node = None
47
48			def __init__(self, key=None, value=None):
49			self.key = key
50			self.value = value
51
52
53			class HashedMapWithSeparateChaining(HashedMap):
54			M = 97
55			id = None
56			N = 0
57
58			def __init__(self, m=None):
59			if m is None:
60			m = 97
61			self.M = m
62			self.id = [None] * self.M
63
64			def hash(self, key):
65			return (hash(key) & 0x7fffffff) % self.M
66
67			def is_empty(self):
68			return self.N == 0
69
70			def contains_key(self, key):
71			return self.get(key) is not None
72
73			def keys(self):
74			for i in range(self.M):
75			x = self.id[i]
76			while x is not None:
77			key = x.key
78			x = x.next_node
79			yield key
80
81			def size(self):
82			return self.N
83
84			def get(self, key):
85			i = self.hash(key)
86			x = self.id[i]
87			while x is not None:
88			if util.cmp(x.key, key) == 0:
89			return x.value
90			x = x.next_node
91			return None
92
93			def delete(self, key):
94			i = self.hash(key)
95			x = self.id[i]
96			prev_node = None
97			while x is not None:
98			if util.cmp(x.key, key) == 0:
99			value = x.value
100			next_node = x.next_node
101			self.N -= 1
102			if prev_node is not None:
103			prev_node.next_node = next_node
104			if self.id[i] == x:
105			self.id[i] = None
106			return value
107			prev_node = x
108			x = x.next_node
109			return None
110
111			def put(self, key, value):
112			if key is None:
113			raise ValueError('key cannot be None')
114
115			i = self.hash(key)
116			x = self.id[i]
117			while x is not None:
118			if util.cmp(x.key, key) == 0:
119			x.value = value
120			return
121			x = x.next_node
122			old_first = self.id[i]
123			self.id[i] = Node(key, value)
124			self.id[i].next_node = old_first
125			self.N += 1
126
127
128			class HashedMapWithLinearProbing(HashedMap):
129
130			M = 97
131			id = None
132			N = 0
133
134			def __init__(self, m=None):
135			if m is None:
136			m = 97
137			self.M = m
138			self.id = [None] * self.M
139
140			def hash(self, key):
141			return (hash(key) & 0x7fffffff) % self.M
142
143			def contains_key(self, key):
144			return self.get(key) is not None
145
146			def is_empty(self):
147			return self.N == 0
148
149			def keys(self):
150			for i in range(self.M):
151			x = self.id[i]
152			if x is not None:
153			yield x.value
154
155			def size(self):
156			return self.N
157
158			def get(self, key):
159			i = self.hash(key)
160			for j in range(self.M):
161			k = (i + j) % self.M
162			x = self.id[k]
163			if x is None:
164			return None
165			if util.cmp(key, x.key) == 0:
166			return x.value
167
168			def delete(self, key):
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			return None
175			if util.cmp(key, x.key) == 0:
176			self.id[k] = None
177			self.N -= 1
178			if self.N == self.M // 4:
179			self.resize(self.M // 2)
180			return x.value
181
182			def put(self, key, value):
183			i = self.hash(key)
184			for j in range(self.M):
185			k = (i + j) % self.M
186			x = self.id[k]
187			if x is None:
188			self.id[k] = Node(key, value)
189			self.N += 1
190			if self.N == self.M // 2:
191			self.resize(self.M * 2)
192			break
193			if util.cmp(x.key, key) == 0:
194			self.id[k].value = value
195			break
196
197			def resize(self, new_size):
198			clone = HashedMapWithLinearProbing(new_size)
199			for i in range(self.M):
200			x = self.id[i]
201			if x is not None:
202			clone.put(x.key, x.value)
203			self.M = clone.M
204			self.id = clone.id
205

chen0040 / pyalgs

Push — master ( 90dc7f...bdb684 )

HashedMapWithLinearProbing.__init__() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

HashedMapWithLinearProbing.init() A