IndexMinPQ.__init__() - Code Metrics - Inspection of "Implement Prim's eager MST implementation" - chen0040/pyalgs - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( a35e0e...167e73 )

by Xianshun

created 2017-04-27 03:47 UTC

IndexMinPQ.init() A

↳ Parent: IndexMinPQ

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	4
rs	10

from pyalgs.algorithms.commons.util import less, exchange, greater


class MinPQ(object):

    pq = None
    N = 0

    def __init__(self, capacity=None):
        if capacity is None:
            capacity = 10
        self.pq = [0] * capacity

    def enqueue(self, key):
        self.N += 1
        if self.N == len(self.pq):
            self.resize(len(self.pq) * 2)

        self.pq[self.N] = key
        self.swim(self.N)

    def swim(self, k):
        while k > 1:
            parent = k // 2
            if less(self.pq[k], self.pq[parent]):
                exchange(self.pq, k, parent)
                k = parent
            else:
                break

    def del_min(self):
        if self.is_empty():
            return None

        key = self.pq[1]
        exchange(self.pq, 1, self.N)
        self.N -= 1
        if self.N == len(self.pq) // 4:
            self.resize(len(self.pq) // 2)

        self.sink(self.pq, 1, self.N)
        return key

    @staticmethod
    def sink(tmp, k, n):

        while k * 2 <= n:
            child = k * 2
            if child < n and less(tmp[child + 1], tmp[child]):
                child = child + 1
            if less(tmp[child], tmp[k]):
                exchange(tmp, child, k)
                k = child
            else:
                break

    def resize(self, new_size):
        tmp = [0] * new_size
        for k in range(min(new_size, len(self.pq))):
            tmp[k] = self.pq[k]
        self.pq = tmp

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

    def size(self):
        return self.N

    def iterate(self):
        tmp = [0] * (self.N + 1)
        for k in range(self.N + 1):
            tmp[k] = self.pq[k]

        n = self.N
        while n >= 1:
            key = tmp[1]
            exchange(tmp, 1, n)
            n -= 1
            self.sink(tmp, 1, n)
            yield key

    @staticmethod
    def create():
        return MinPQ()



class MaxPQ(object):
    pq = None
    N = 0

    def __init__(self, capacity=None):
        if capacity is None:
            capacity = 10
        self.pq = [0] * capacity

    def enqueue(self, key):
        if self.N == len(self.pq):
            self.resize(len(self.pq) * 2)
        self.N += 1
        self.pq[self.N] = key
        self.swim(self.N)

    def swim(self, k):
        while k > 1:
            parent = k // 2
            if greater(self.pq[k], self.pq[parent]):
                exchange(self.pq, k, parent)
                k = parent
            else:
                break

    def del_max(self):
        if self.is_empty():
            return None

        key = self.pq[1]
        exchange(self.pq, 1, self.N)
        self.N -= 1
        if self.N == len(self.pq) // 4:
            self.resize(len(self.pq) // 2)

        self.sink(self.pq, 1, self.N)
        return key

    @staticmethod
    def sink(tmp, k, n):

        while k * 2 <= n:
            child = k * 2
            if child < n and greater(tmp[child + 1], tmp[child]):
                child = child + 1
            if greater(tmp[child], tmp[k]):
                exchange(tmp, child, k)
                k = child
            else:
                break

    def resize(self, new_size):
        tmp = [0] * new_size
        for k in range(min(new_size, len(self.pq))):
            tmp[k] = self.pq[k]
        self.pq = tmp

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

    def size(self):
        return self.N

    def iterate(self):
        tmp = [0] * (self.N + 1)
        for k in range(self.N + 1):
            tmp[k] = self.pq[k]

        n = self.N
        while n >= 1:
            key = tmp[1]
            exchange(tmp, 1, n)
            n -= 1
            self.sink(tmp, 1, n)
            yield key

    @staticmethod
    def create():
        return MaxPQ()


class IndexMinPQ(object):

    keys = None
    pq = None
    qp = None
    N = 0

    def __init__(self, size):
        self.keys = [None] * (size+1)
        self.pq = [0] * (size+1)
        self.qp = [0] * (size+1)

    def insert(self, index, key):
        self.keys[index] = key
        self.N += 1
        self.pq[self.N] = index
        self.qp[index] = self.N

        self.swim(self.N)

    def decrease_key(self, index, key):
        self.keys[index] = key
        k = self.qp[index]
        self.swim(k)

    def contains_index(self, index):
        return self.keys[index] is not None

    def swim(self, k):
        while k > 1:
            parent = k / 2
            if less(self.keys[self.pq[k]], self.keys[self.pq[parent]]):

                exchange(self.pq, k, parent)
                self.qp[self.pq[k]] = k
                self.qp[self.pq[parent]] = parent
                k = parent
            else:
                break

    def get(self, index):
        return self.keys[index]

    def min_key(self):
        return self.keys[self.pq[1]]

    def del_min(self):
        index = self.pq[1]
        exchange(self.pq, 1, self.N)
        self.qp[self.pq[1]] = 1
        self.qp[self.pq[self.N]] = self.N

        self.N -= 1
        self.sink(1)

        return index

    def sink(self, k):
        while 2 * k <= self.N:
            child = 2 * k
            if child < self.N and less(self.keys[self.pq[child]], self.keys[self.pq[child+1]]):
                child = child+1
            if less(self.keys[self.pq[child]], self.keys[self.pq[k]]):

                exchange(self.pq, k, child)
                self.qp[self.pq[k]] = k
                self.qp[self.pq[child]] = child
                k = child
            else:
                break

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

    def size(self):
        return self.N


1		from pyalgs.algorithms.commons.util import less, exchange, greater
2
3
4	View Code Duplication	class MinPQ(object):
		0 ignored issues – show Duplication introduced 2017-04-25 16:58 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. Loading history...
5		pq = None
6		N = 0
7
8		def __init__(self, capacity=None):
9		if capacity is None:
10		capacity = 10
11		self.pq = [0] * capacity
12
13		def enqueue(self, key):
14		self.N += 1
15		if self.N == len(self.pq):
16		self.resize(len(self.pq) * 2)
17
18		self.pq[self.N] = key
19		self.swim(self.N)
20
21		def swim(self, k):
22		while k > 1:
23		parent = k // 2
24		if less(self.pq[k], self.pq[parent]):
25		exchange(self.pq, k, parent)
26		k = parent
27		else:
28		break
29
30		def del_min(self):
31		if self.is_empty():
32		return None
33
34		key = self.pq[1]
35		exchange(self.pq, 1, self.N)
36		self.N -= 1
37		if self.N == len(self.pq) // 4:
38		self.resize(len(self.pq) // 2)
39
40		self.sink(self.pq, 1, self.N)
41		return key
42
43		@staticmethod
44		def sink(tmp, k, n):
45
46		while k * 2 <= n:
47		child = k * 2
48		if child < n and less(tmp[child + 1], tmp[child]):
49		child = child + 1
50		if less(tmp[child], tmp[k]):
51		exchange(tmp, child, k)
52		k = child
53		else:
54		break
55
56		def resize(self, new_size):
57		tmp = [0] * new_size
58		for k in range(min(new_size, len(self.pq))):
59		tmp[k] = self.pq[k]
60		self.pq = tmp
61
62		def is_empty(self):
63		return self.N == 0
64
65		def size(self):
66		return self.N
67
68		def iterate(self):
69		tmp = [0] * (self.N + 1)
70		for k in range(self.N + 1):
71		tmp[k] = self.pq[k]
72
73		n = self.N
74		while n >= 1:
75		key = tmp[1]
76		exchange(tmp, 1, n)
77		n -= 1
78		self.sink(tmp, 1, n)
79		yield key
80
81		@staticmethod
82		def create():
83		return MinPQ()
84
85	View Code Duplication
		0 ignored issues – show Duplication introduced 2017-04-26 15:29 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. Loading history...
86		class MaxPQ(object):
87		pq = None
88		N = 0
89
90		def __init__(self, capacity=None):
91		if capacity is None:
92		capacity = 10
93		self.pq = [0] * capacity
94
95		def enqueue(self, key):
96		if self.N == len(self.pq):
97		self.resize(len(self.pq) * 2)
98		self.N += 1
99		self.pq[self.N] = key
100		self.swim(self.N)
101
102		def swim(self, k):
103		while k > 1:
104		parent = k // 2
105		if greater(self.pq[k], self.pq[parent]):
106		exchange(self.pq, k, parent)
107		k = parent
108		else:
109		break
110
111		def del_max(self):
112		if self.is_empty():
113		return None
114
115		key = self.pq[1]
116		exchange(self.pq, 1, self.N)
117		self.N -= 1
118		if self.N == len(self.pq) // 4:
119		self.resize(len(self.pq) // 2)
120
121		self.sink(self.pq, 1, self.N)
122		return key
123
124		@staticmethod
125		def sink(tmp, k, n):
126
127		while k * 2 <= n:
128		child = k * 2
129		if child < n and greater(tmp[child + 1], tmp[child]):
130		child = child + 1
131		if greater(tmp[child], tmp[k]):
132		exchange(tmp, child, k)
133		k = child
134		else:
135		break
136
137		def resize(self, new_size):
138		tmp = [0] * new_size
139		for k in range(min(new_size, len(self.pq))):
140		tmp[k] = self.pq[k]
141		self.pq = tmp
142
143		def is_empty(self):
144		return self.N == 0
145
146		def size(self):
147		return self.N
148
149		def iterate(self):
150		tmp = [0] * (self.N + 1)
151		for k in range(self.N + 1):
152		tmp[k] = self.pq[k]
153
154		n = self.N
155		while n >= 1:
156		key = tmp[1]
157		exchange(tmp, 1, n)
158		n -= 1
159		self.sink(tmp, 1, n)
160		yield key
161
162		@staticmethod
163		def create():
164		return MaxPQ()
165
166
167		class IndexMinPQ(object):
168
169		keys = None
170		pq = None
171		qp = None
172		N = 0
173
174		def __init__(self, size):
175		self.keys = [None] * (size+1)
176		self.pq = [0] * (size+1)
177		self.qp = [0] * (size+1)
178
179		def insert(self, index, key):
180		self.keys[index] = key
181		self.N += 1
182		self.pq[self.N] = index
183		self.qp[index] = self.N
184
185		self.swim(self.N)
186
187		def decrease_key(self, index, key):
188		self.keys[index] = key
189		k = self.qp[index]
190		self.swim(k)
191
192		def contains_index(self, index):
193		return self.keys[index] is not None
194
195		def swim(self, k):
196		while k > 1:
197		parent = k / 2
198	View Code Duplication	if less(self.keys[self.pq[k]], self.keys[self.pq[parent]]):
		0 ignored issues – show Duplication introduced 2017-04-27 03:48 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. Loading history...
199		exchange(self.pq, k, parent)
200		self.qp[self.pq[k]] = k
201		self.qp[self.pq[parent]] = parent
202		k = parent
203		else:
204		break
205
206		def get(self, index):
207		return self.keys[index]
208
209		def min_key(self):
210		return self.keys[self.pq[1]]
211
212		def del_min(self):
213		index = self.pq[1]
214		exchange(self.pq, 1, self.N)
215		self.qp[self.pq[1]] = 1
216		self.qp[self.pq[self.N]] = self.N
217
218		self.N -= 1
219		self.sink(1)
220
221		return index
222
223		def sink(self, k):
224		while 2 * k <= self.N:
225		child = 2 * k
226		if child < self.N and less(self.keys[self.pq[child]], self.keys[self.pq[child+1]]):
227		child = child+1
228	View Code Duplication	if less(self.keys[self.pq[child]], self.keys[self.pq[k]]):
		0 ignored issues – show Duplication introduced 2017-04-27 03:48 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. Loading history...
229		exchange(self.pq, k, child)
230		self.qp[self.pq[k]] = k
231		self.qp[self.pq[child]] = child
232		k = child
233		else:
234		break
235
236		def is_empty(self):
237		return self.N == 0
238
239		def size(self):
240		return self.N
241

chen0040 / pyalgs

Push — master ( a35e0e...167e73 )

IndexMinPQ.__init__() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

IndexMinPQ.init() A