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

RedBlackTree._delete() F
last analyzed 2017-05-26 05:56 UTC

↳ Parent: RedBlackTree

Complexity

Conditions

Size

Total Lines

Duplication

Lines	15
Ratio	50 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	12
c	1
b	0
f	0
dl	15
loc	30
rs	2.7855

How to fix Complexity

from abc import ABCMeta
from pyalgs.algorithms.commons.util import cmp
from pyalgs.data_structures.commons.queue import Queue


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

    left = None
    right = None

    count = 0
    red = 1

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

        if red is not None:
            self.red = red
        else:
            self.red = 0


def _count(x):
    if x is None:
        return 0
    return x.count


class BinarySearchTree(object):
    __metaclass__ = ABCMeta

    root = None

    def put(self, key, value):
        self.root = self._put(self.root, key, value)

    def _put(self, x, key, value):
        if x is None:
            return Node(key, value)

        compared = cmp(key, x.key)

        if compared < 0:
            x.left = self._put(x.left, key, value)
        elif compared > 0:
            x.right = self._put(x.right, key, value)
        else:
            x.value = value

        x.count = 1 + _count(x.left) + _count(x.right)

        return x

    def get(self, key):
        x = self._get(self.root, key)
        if x is None:
            return None
        return x.value

    def _get(self, x, key):
        if x is None:
            return None
        compared = cmp(key, x.key)
        if compared < 0:
            return self._get(x.left, key)
        elif compared > 0:
            return self._get(x.right, key)
        else:
            return x

    def size(self):
        return _count(self.root)

    def is_empty(self):
        return self.root is None

    def delete(self, key):
        self.root = self._delete(self.root, key)

    def _delete(self, x, key):
        if x is None:
            return None

        compared = cmp(key, x.key)
        if compared < 0:

            x.left = self._delete(x.left, key)
        elif compared > 0:
            x.right = self._delete(x.right, key)
        else:
            if x.left is None:
                return x.right
            elif x.right is None:
                return x.left
            else:
                m = self.min(x.right)
                m.right = self.del_min(x.right)
                m.left = x.left

                x = m

        x.count = 1 + _count(x.left) + _count(x.right)
        return x

    def min(self, x):
        if x.left is None:
            return x
        return self.min(x.left)

    def del_min(self, x):
        if x.left is None:
            return x.right
        x.left = self.del_min(x.left)
        return x

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

    def keys(self):
        queue = Queue.create()
        self.collect_keys(self.root, queue)
        return queue.iterate()

    def collect_keys(self, x, queue):
        if x is None:
            return

        self.collect_keys(x.left, queue)
        queue.enqueue(x.key)
        self.collect_keys(x.right, queue)

    @staticmethod
    def create():
        return BinarySearchTree()

    @staticmethod
    def create_red_black_tree():
        return RedBlackTree()


class RedBlackTree(BinarySearchTree):
    def put(self, key, value):
        self.root = self._put2(self.root, key, value)

    def _put2(self, x, key, value):
        if x is None:
            return Node(key, value, 1)
        compared = cmp(key, x.key)
        if compared < 0:
            x.left = self._put2(x.left, key, value)
        elif compared > 0:
            x.right = self._put2(x.right, key, value)
        else:
            x.value = value

        if self.is_red(x.right) and not self.is_red(x.left):
            x = self.rotate_left(x)
        if self.is_red(x.left) and self.is_red(x.left.left):
            x = self.rotate_right(x)
        if self.is_red(x.left) and self.is_red(x.right):
            x = self.flip_colors(x)

        x.count = 1 + _count(x.left) + _count(x.right)
        return x

    def _delete(self, x, key):
        if x is None:
            return None

        compared = cmp(key, x.key)
        if compared < 0:

            x.left = self._delete(x.left, key)
        elif compared > 0:
            x.right = self._delete(x.right, key)
        else:
            if x.left is None:
                return x.right
            elif x.right is None:
                return x.left
            else:
                m = self.min(x.right)
                m.right = self.del_min(x.right)
                m.left = x.left

                x = m

        if self.is_red(x.right) and not self.is_red(x.left):
            x = self.rotate_left(x)
        if self.is_red(x.left) and self.is_red(x.left.left):
            x = self.rotate_right(x)
        if self.is_red(x.left) and self.is_red(x.right):
            x = self.flip_colors(x)

        x.count = 1 + _count(x.left) + _count(x.right)
        return x

    def is_red(self, x):
        if x is None:
            return False
        return x.red == 1

    def rotate_left(self, x):
        m = x.right
        x.right = m.left
        m.left = x

        m.red = x.red
        x.red = 1

        x.count = 1 + _count(x.left) + _count(x.right)
        return m

    def rotate_right(self, x):
        m = x.left
        x.left = m.right
        m.right = x

        m.red = x.red
        x.red = 1

        x.count = 1 + _count(x.left) + _count(x.right)
        return m

    def flip_colors(self, x):
        if x.left is not None:
            x.left.red = 0
        if x.right is not None:
            x.right.red = 0
        x.red = 1
        return x



1		from abc import ABCMeta
2		from pyalgs.algorithms.commons.util import cmp
3		from pyalgs.data_structures.commons.queue import Queue
4
5
6		class Node(object):
7		key = None
8		value = None
9
10		left = None
11		right = None
12
13		count = 0
14		red = 1
15
16		def __init__(self, key, value, red=None):
17		self.key = key
18		self.value = value
19		self.count = 1
20
21		if red is not None:
22		self.red = red
23		else:
24		self.red = 0
25
26
27		def _count(x):
28		if x is None:
29		return 0
30		return x.count
31
32
33		class BinarySearchTree(object):
34		__metaclass__ = ABCMeta
35
36		root = None
37
38		def put(self, key, value):
39		self.root = self._put(self.root, key, value)
40
41		def _put(self, x, key, value):
42		if x is None:
43		return Node(key, value)
44
45		compared = cmp(key, x.key)
46
47		if compared < 0:
48		x.left = self._put(x.left, key, value)
49		elif compared > 0:
50		x.right = self._put(x.right, key, value)
51		else:
52		x.value = value
53
54		x.count = 1 + _count(x.left) + _count(x.right)
55
56		return x
57
58		def get(self, key):
59		x = self._get(self.root, key)
60		if x is None:
61		return None
62		return x.value
63
64		def _get(self, x, key):
65		if x is None:
66		return None
67		compared = cmp(key, x.key)
68		if compared < 0:
69		return self._get(x.left, key)
70		elif compared > 0:
71		return self._get(x.right, key)
72		else:
73		return x
74
75		def size(self):
76		return _count(self.root)
77
78		def is_empty(self):
79		return self.root is None
80
81		def delete(self, key):
82		self.root = self._delete(self.root, key)
83
84		def _delete(self, x, key):
85		if x is None:
86		return None
87
88		compared = cmp(key, x.key)
89	View Code Duplication	if compared < 0:
		0 ignored issues – show Duplication introduced 2017-05-26 05:56 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. Loading history...
90		x.left = self._delete(x.left, key)
91		elif compared > 0:
92		x.right = self._delete(x.right, key)
93		else:
94		if x.left is None:
95		return x.right
96		elif x.right is None:
97		return x.left
98		else:
99		m = self.min(x.right)
100		m.right = self.del_min(x.right)
101		m.left = x.left
102
103		x = m
104
105		x.count = 1 + _count(x.left) + _count(x.right)
106		return x
107
108		def min(self, x):
109		if x.left is None:
110		return x
111		return self.min(x.left)
112
113		def del_min(self, x):
114		if x.left is None:
115		return x.right
116		x.left = self.del_min(x.left)
117		return x
118
119		def contains_key(self, x):
120		return self.get(x) is not None
121
122		def keys(self):
123		queue = Queue.create()
124		self.collect_keys(self.root, queue)
125		return queue.iterate()
126
127		def collect_keys(self, x, queue):
128		if x is None:
129		return
130
131		self.collect_keys(x.left, queue)
132		queue.enqueue(x.key)
133		self.collect_keys(x.right, queue)
134
135		@staticmethod
136		def create():
137		return BinarySearchTree()
138
139		@staticmethod
140		def create_red_black_tree():
141		return RedBlackTree()
142
143
144		class RedBlackTree(BinarySearchTree):
145		def put(self, key, value):
146		self.root = self._put2(self.root, key, value)
147
148		def _put2(self, x, key, value):
149		if x is None:
150		return Node(key, value, 1)
151		compared = cmp(key, x.key)
152		if compared < 0:
153		x.left = self._put2(x.left, key, value)
154		elif compared > 0:
155		x.right = self._put2(x.right, key, value)
156		else:
157		x.value = value
158
159		if self.is_red(x.right) and not self.is_red(x.left):
160		x = self.rotate_left(x)
161		if self.is_red(x.left) and self.is_red(x.left.left):
162		x = self.rotate_right(x)
163		if self.is_red(x.left) and self.is_red(x.right):
164		x = self.flip_colors(x)
165
166		x.count = 1 + _count(x.left) + _count(x.right)
167		return x
168
169		def _delete(self, x, key):
170		if x is None:
171		return None
172
173		compared = cmp(key, x.key)
174	View Code Duplication	if compared < 0:
		0 ignored issues – show Duplication introduced 2017-05-26 05:56 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. Loading history...
175		x.left = self._delete(x.left, key)
176		elif compared > 0:
177		x.right = self._delete(x.right, key)
178		else:
179		if x.left is None:
180		return x.right
181		elif x.right is None:
182		return x.left
183		else:
184		m = self.min(x.right)
185		m.right = self.del_min(x.right)
186		m.left = x.left
187
188		x = m
189
190		if self.is_red(x.right) and not self.is_red(x.left):
191		x = self.rotate_left(x)
192		if self.is_red(x.left) and self.is_red(x.left.left):
193		x = self.rotate_right(x)
194		if self.is_red(x.left) and self.is_red(x.right):
195		x = self.flip_colors(x)
196
197		x.count = 1 + _count(x.left) + _count(x.right)
198		return x
199
200		def is_red(self, x):
201		if x is None:
202		return False
203		return x.red == 1
204
205		def rotate_left(self, x):
206		m = x.right
207		x.right = m.left
208		m.left = x
209
210		m.red = x.red
211		x.red = 1
212
213		x.count = 1 + _count(x.left) + _count(x.right)
214		return m
215
216		def rotate_right(self, x):
217		m = x.left
218		x.left = m.right
219		m.right = x
220
221		m.red = x.red
222		x.red = 1
223
224		x.count = 1 + _count(x.left) + _count(x.right)
225		return m
226
227		def flip_colors(self, x):
228		if x.left is not None:
229		x.left.red = 0
230		if x.right is not None:
231		x.right.red = 0
232		x.red = 1
233		return x
234
235

chen0040 / pyalgs

RedBlackTree._delete() F last analyzed 2017-05-26 05:56 UTC

Complexity

Size

Duplication

Importance

How to fix Complexity

Complexity

Duplication Side-by-Side

Filter issues like

RedBlackTree._delete() F
last analyzed 2017-05-26 05:56 UTC