BinarySearchTree.collect_keys() - Code Metrics - Inspection of "Implement hashed map with separate chaining" - chen0040/pyalgs - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 5fe484...18079e )

by Xianshun

created 2017-04-26 03:31 UTC

BinarySearchTree.collect_keys() A

↳ Parent: BinarySearchTree

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	7
rs	9.4285

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 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			if compared < 0:
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 is_red(self, x):
170			if x is None:
171			return False
172			return x.red == 1
173
174			def rotate_left(self, x):
175			m = x.right
176			x.right = m.left
177			m.left = x
178
179			m.red = x.red
180			x.red = 1
181
182			x.count = 1 + _count(x.left) + _count(x.right)
183			return m
184
185			def rotate_right(self, x):
186			m = x.left
187			x.left = m.right
188			m.right = x
189
190			m.red = x.red
191			x.red = 1
192
193			x.count = 1 + _count(x.left) + _count(x.right)
194			return m
195
196			def flip_colors(self, x):
197			if x.left is not None:
198			x.left.red = 0
199			if x.right is not None:
200			x.right.red = 0
201			x.red = 1
202			return x
203
204

chen0040 / pyalgs

Push — master ( 5fe484...18079e )

BinarySearchTree.collect_keys() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like