HashedSetWithSeparateChaining.iterate() - Code Metrics - Inspection of "Implement hashed set" - chen0040/pyalgs - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 0d1037...35965b )

by Xianshun

created 2017-04-26 07:16 UTC

HashedSetWithSeparateChaining.iterate() A

↳ Parent: HashedSetWithSeparateChaining

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	3
c	1
b	0
f	0
dl	0
loc	7
rs	9.4285

from abc import ABCMeta, abstractmethod

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


class HashedSet(object):
    __metaclass__ = ABCMeta

    @abstractmethod
    def add(self, key):
        pass

    @abstractmethod
    def delete(self, key):
        pass

    @abstractmethod
    def size(self):
        pass

    @abstractmethod
    def is_empty(self):
        pass

    @abstractmethod
    def iterate(self):
        pass

    @abstractmethod
    def contains(self, key):
        pass

    @staticmethod
    def create():
        return HashedSetWithSeparateChaining()


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

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


class HashedSetWithSeparateChaining(HashedSet):
    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 iterate(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 contains(self, key):
        i = self.hash(key)
        x = self.id[i]
        while x is not None:
            if util.cmp(x.key, key) == 0:
                return True
            x = x.next_node
        return False

    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:
                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 True
            prev_node = x
            x = x.next_node
        return False

    def add(self, key):
        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:
                return
            x = x.next_node
        old_first = self.id[i]
        self.id[i] = Node(key)
        self.id[i].next_node = old_first
        self.N += 1


class HashedSetWithLinearProbing(HashedSet):

    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 iterate(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 contains(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 False
            if util.cmp(key, x.key) == 0:
                return True

    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 False
            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 True

    def add(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:
                self.id[k] = Node(key)
                self.N += 1
                if self.N == self.M // 2:
                    self.resize(self.M * 2)
                break
            if util.cmp(x.key, key) == 0:
                break

    def resize(self, new_size):
        clone = HashedSetWithLinearProbing(new_size)
        for i in range(self.M):
            x = self.id[i]
            if x is not None:
                clone.add(x.key)
        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 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 2017-04-26 07:17 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. 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 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...
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

chen0040 / pyalgs

Push — master ( 0d1037...35965b )

HashedSetWithSeparateChaining.iterate() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like