HashedMapWithSeparateChaining.hash() - Code Metrics - chen0040/pyalgs - Measure and Improve Code Quality continuously with Scrutinizer

HashedMapWithSeparateChaining.hash() A
last analyzed 2017-05-26 05:56 UTC

↳ Parent: HashedMapWithSeparateChaining

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

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

from abc import ABCMeta, abstractmethod

from pyalgs.algorithms.commons import util


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.key

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

chen0040 / pyalgs

HashedMapWithSeparateChaining.hash() A last analyzed 2017-05-26 05:56 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

HashedMapWithSeparateChaining.hash() A
last analyzed 2017-05-26 05:56 UTC