TSNode.__init__() - Code Metrics - Inspection of "Fix some bugs in the R-way search tries" - chen0040/pyalgs - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 8703e1...dbd0e3 )

by Xianshun

created 2017-05-06 01:44 UTC

TSNode.init() A

↳ Parent: TSNode

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes

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

from abc import ABCMeta, abstractmethod

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


class SearchTries(object):
    __metaclass__ = ABCMeta

    @abstractmethod
    def put(self, key, value):
        pass

    @abstractmethod
    def get(self, key):
        pass

    @abstractmethod
    def is_empty(self):
        pass

    @abstractmethod
    def size(self):
        pass

    @abstractmethod
    def delete(self, key):
        pass

    @abstractmethod
    def keys(self):
        pass

    @abstractmethod
    def keys_with_prefix(self, prefix):
        pass

    @abstractmethod
    def contains_key(self, key):
        pass

    @staticmethod
    def create():
        return RWaySearchTries()


def char_at(key, d):
    return ord(key[d])


class Node(object):
    nodes = None
    value = None
    R = 256

    def __init__(self):
        self.nodes = [None] * Node.R


class RWaySearchTries(SearchTries):

    root = None
    N = 0

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

    def keys_with_prefix(self, prefix):
        x = self._get(self.root, prefix, 0)
        if x is None:
            return None

        queue = Queue.create()
        self.collect(x, prefix, queue)
        return queue.iterate()

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

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

        if x.value is not None:
            queue.enqueue(prefix)
            return

        for r in range(Node.R):
            self.collect(x.nodes[r], prefix + str(chr(r)), queue)

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

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

    def _get(self, x, key, d):
        if x is None:
            return None
        if len(key) == d:
            return x

        return self._get(x.nodes[char_at(key, d)], key, d + 1)

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

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

        if len(key) == d:
            if x.value is not None:
                self.N -= 1
            return None

        c = char_at(key, d)
        x.nodes[c] = self._delete(x.nodes[c], key, d + 1)
        return x

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

    def _put(self, x, key, value, d):
        if x is None:
            x = Node()
        if len(key) == d:
            if x.value is None:
                self.N += 1
            x.value = value
            return x

        c = char_at(key, d)
        x.nodes[c] = self._put(x.nodes[c], key, value, d + 1)
        return x

    def size(self):
        return self.N


class TSNode(object):
    value = None
    left = None
    mid = None
    right = None
    key = None

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


class TernarySearchTries(SearchTries):

    root = None
    N = 0

    def contains_key(self, key):
        x = self._get(self.root, key, 0)
        return x is not None and x.value is not None

    def size(self):
        return self.N

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

    def collect(self, x, prefix, queue):
        if x is None:
            return
        if x.value is not None:
            queue.enqueue(prefix)
        c = chr(x.key)
        self.collect(x.left, prefix, queue)
        self.collect(x.mid, prefix + str(c), queue)
        self.collect(x.right, prefix, queue)

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

    def _get(self, x, key, d):
        if x is None:
            return None
        c = char_at(key, d)
        compared = util.cmp(c, x.key)
        if compared < 0:
            return self._get(x.left, key, d)
        elif compared > 0:
            return self._get(x.right, key, d)
        elif len(key)-1 == d:
            return x
        else:
            return self._get(x.mid, key, d+1)

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

    def _put(self, x, key, value, d):
        c = char_at(key, d)
        if x is None:
            x = TSNode(c)
        compared = util.cmp(c, x.key)
        if compared < 0:
            x.left = self._put(x.left, key, value, d)
        elif compared > 0:
            x.right = self._put(x.right, key, value, d)
        elif len(key)-1 == d:
            if x.value is None:
                self.N += 1
            x.value = value
        else:
            x.mid = self._put(x.mid, key, value, d+1)

        return x

    def delete(self, key):
        x = self._get(self.root, key, 0)
        if x is not None:
            if x.value is not None:
                self.N -= 1
            x.value = None

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

    def keys_with_prefix(self, prefix):
        x = self._get(self.root, prefix, 0)
        if x is None:
            return None
        queue = Queue.create()
        self.collect(x, prefix, queue)
        return queue.iterate()

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 SearchTries(object):
8			__metaclass__ = ABCMeta
9
10			@abstractmethod
11			def put(self, key, value):
12			pass
13
14			@abstractmethod
15			def get(self, key):
16			pass
17
18			@abstractmethod
19			def is_empty(self):
20			pass
21
22			@abstractmethod
23			def size(self):
24			pass
25
26			@abstractmethod
27			def delete(self, key):
28			pass
29
30			@abstractmethod
31			def keys(self):
32			pass
33
34			@abstractmethod
35			def keys_with_prefix(self, prefix):
36			pass
37
38			@abstractmethod
39			def contains_key(self, key):
40			pass
41
42			@staticmethod
43			def create():
44			return RWaySearchTries()
45
46
47			def char_at(key, d):
48			return ord(key[d])
49
50
51			class Node(object):
52			nodes = None
53			value = None
54			R = 256
55
56			def __init__(self):
57			self.nodes = [None] * Node.R
58
59
60			class RWaySearchTries(SearchTries):
61
62			root = None
63			N = 0
64
65			def contains_key(self, key):
66			x = self._get(self.root, key, 0)
67			if x is None:
68			return None
69			return x.value
70
71			def keys_with_prefix(self, prefix):
72			x = self._get(self.root, prefix, 0)
73			if x is None:
74			return None
75
76			queue = Queue.create()
77			self.collect(x, prefix, queue)
78			return queue.iterate()
79
80			def keys(self):
81			queue = Queue.create()
82			self.collect(self.root, '', queue)
83			return queue.iterate()
84
85			def collect(self, x, prefix, queue):
86			if x is None:
87			return
88
89			if x.value is not None:
90			queue.enqueue(prefix)
91			return
92
93			for r in range(Node.R):
94			self.collect(x.nodes[r], prefix + str(chr(r)), queue)
95
96			def is_empty(self):
97			return self.N == 0
98
99			def get(self, key):
100			x = self._get(self.root, key, 0)
101			if x is not None:
102			return x.value
103			return None
104
105			def _get(self, x, key, d):
106			if x is None:
107			return None
108			if len(key) == d:
109			return x
110
111			return self._get(x.nodes[char_at(key, d)], key, d + 1)
112
113			def delete(self, key):
114			self.root = self._delete(self.root, key, 0)
115
116			def _delete(self, x, key, d):
117			if x is None:
118			return None
119
120			if len(key) == d:
121			if x.value is not None:
122			self.N -= 1
123			return None
124
125			c = char_at(key, d)
126			x.nodes[c] = self._delete(x.nodes[c], key, d + 1)
127			return x
128
129			def put(self, key, value):
130			self.root = self._put(self.root, key, value, 0)
131
132			def _put(self, x, key, value, d):
133			if x is None:
134			x = Node()
135			if len(key) == d:
136			if x.value is None:
137			self.N += 1
138			x.value = value
139			return x
140
141			c = char_at(key, d)
142			x.nodes[c] = self._put(x.nodes[c], key, value, d + 1)
143			return x
144
145			def size(self):
146			return self.N
147
148
149			class TSNode(object):
150			value = None
151			left = None
152			mid = None
153			right = None
154			key = None
155
156			def __init__(self, c):
157			self.key = c
158
159
160			class TernarySearchTries(SearchTries):
161
162			root = None
163			N = 0
164
165			def contains_key(self, key):
166			x = self._get(self.root, key, 0)
167			return x is not None and x.value is not None
168
169			def size(self):
170			return self.N
171
172			def keys(self):
173			queue = Queue.create()
174			self.collect(self.root, '', queue)
175			return queue.iterate()
176
177			def collect(self, x, prefix, queue):
178			if x is None:
179			return
180			if x.value is not None:
181			queue.enqueue(prefix)
182			c = chr(x.key)
183			self.collect(x.left, prefix, queue)
184			self.collect(x.mid, prefix + str(c), queue)
185			self.collect(x.right, prefix, queue)
186
187			def get(self, key):
188			x = self._get(self.root, key, 0)
189			if x is None:
190			return None
191			return x.value
192
193			def _get(self, x, key, d):
194			if x is None:
195			return None
196			c = char_at(key, d)
197			compared = util.cmp(c, x.key)
198			if compared < 0:
199			return self._get(x.left, key, d)
200			elif compared > 0:
201			return self._get(x.right, key, d)
202			elif len(key)-1 == d:
203			return x
204			else:
205			return self._get(x.mid, key, d+1)
206
207			def put(self, key, value):
208			self.root = self._put(self.root, key, value, 0)
209
210			def _put(self, x, key, value, d):
211			c = char_at(key, d)
212			if x is None:
213			x = TSNode(c)
214			compared = util.cmp(c, x.key)
215			if compared < 0:
216			x.left = self._put(x.left, key, value, d)
217			elif compared > 0:
218			x.right = self._put(x.right, key, value, d)
219			elif len(key)-1 == d:
220			if x.value is None:
221			self.N += 1
222			x.value = value
223			else:
224			x.mid = self._put(x.mid, key, value, d+1)
225
226			return x
227
228			def delete(self, key):
229			x = self._get(self.root, key, 0)
230			if x is not None:
231			if x.value is not None:
232			self.N -= 1
233			x.value = None
234
235			def is_empty(self):
236			return self.N == 0
237
238			def keys_with_prefix(self, prefix):
239			x = self._get(self.root, prefix, 0)
240			if x is None:
241			return None
242			queue = Queue.create()
243			self.collect(x, prefix, queue)
244			return queue.iterate()

chen0040 / pyalgs

Push — master ( 8703e1...dbd0e3 )

TSNode.__init__() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

TSNode.init() A