File: tree.py

package info (click to toggle)
logilab-common 0.50.3-1
  • links: PTS, VCS
  • area: main
  • in suites: squeeze
  • size: 1,128 kB
  • ctags: 1,953
  • sloc: python: 10,740; makefile: 55; sh: 11
file content (372 lines) | stat: -rw-r--r-- 10,666 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
# copyright 2003-2010 LOGILAB S.A. (Paris, FRANCE), all rights reserved.
# contact http://www.logilab.fr/ -- mailto:contact@logilab.fr
#
# This file is part of logilab-common.
#
# logilab-common is free software: you can redistribute it and/or modify it under
# the terms of the GNU Lesser General Public License as published by the Free
# Software Foundation, either version 2.1 of the License, or (at your option) any
# later version.
#
# logilab-common is distributed in the hope that it will be useful, but WITHOUT
# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
# FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more
# details.
#
# You should have received a copy of the GNU Lesser General Public License along
# with logilab-common.  If not, see <http://www.gnu.org/licenses/>.
"""Base class to represent a tree structure.




"""
__docformat__ = "restructuredtext en"

import sys

from logilab.common import flatten
from logilab.common.visitor import VisitedMixIn, FilteredIterator, no_filter

## Exceptions #################################################################

class NodeNotFound(Exception):
    """raised when a node has not been found"""

EX_SIBLING_NOT_FOUND = "No such sibling as '%s'"
EX_CHILD_NOT_FOUND = "No such child as '%s'"
EX_NODE_NOT_FOUND = "No such node as '%s'"


# Base node ###################################################################

class Node(object):
    """a basic tree node, characterized by an id"""

    def __init__(self, nid=None) :
        self.id = nid
        # navigation
        self.parent = None
        self.children = []

    def __iter__(self):
        return iter(self.children)

    def __str__(self, indent=0):
        s = ['%s%s %s' % (' '*indent, self.__class__.__name__, self.id)]
        indent += 2
        for child in self.children:
            try:
                s.append(child.__str__(indent))
            except TypeError:
                s.append(child.__str__())
        return '\n'.join(s)

    def is_leaf(self):
        return not self.children

    def append(self, child):
        """add a node to children"""
        self.children.append(child)
        child.parent = self

    def remove(self, child):
        """remove a child node"""
        self.children.remove(child)
        child.parent = None

    def insert(self, index, child):
        """insert a child node"""
        self.children.insert(index, child)
        child.parent = self

    def replace(self, old_child, new_child):
        """replace a child node with another"""
        i = self.children.index(old_child)
        self.children.pop(i)
        self.children.insert(i, new_child)
        new_child.parent = self

    def get_sibling(self, nid):
        """return the sibling node that has given id"""
        try:
            return self.parent.get_child_by_id(nid)
        except NodeNotFound :
            raise NodeNotFound(EX_SIBLING_NOT_FOUND % nid)

    def next_sibling(self):
        """
        return the next sibling for this node if any
        """
        parent = self.parent
        if parent is None:
            # root node has no sibling
            return None
        index = parent.children.index(self)
        try:
            return parent.children[index+1]
        except IndexError:
            return None

    def previous_sibling(self):
        """
        return the previous sibling for this node if any
        """
        parent = self.parent
        if parent is None:
            # root node has no sibling
            return None
        index = parent.children.index(self)
        if index > 0:
            return parent.children[index-1]
        return None

    def get_node_by_id(self, nid):
        """
        return node in whole hierarchy that has given id
        """
        root = self.root()
        try:
            return root.get_child_by_id(nid, 1)
        except NodeNotFound :
            raise NodeNotFound(EX_NODE_NOT_FOUND % nid)

    def get_child_by_id(self, nid, recurse=None):
        """
        return child of given id
        """
        if self.id == nid:
            return self
        for c in self.children :
            if recurse:
                try:
                    return c.get_child_by_id(nid, 1)
                except NodeNotFound :
                    continue
            if c.id == nid :
                return c
        raise NodeNotFound(EX_CHILD_NOT_FOUND % nid)

    def get_child_by_path(self, path):
        """
        return child of given path (path is a list of ids)
        """
        if len(path) > 0 and path[0] == self.id:
            if len(path) == 1 :
                return self
            else :
                for c in self.children :
                    try:
                        return c.get_child_by_path(path[1:])
                    except NodeNotFound :
                        pass
        raise NodeNotFound(EX_CHILD_NOT_FOUND % path)

    def depth(self):
        """
        return depth of this node in the tree
        """
        if self.parent is not None:
            return 1 + self.parent.depth()
        else :
            return 0

    def depth_down(self):
        """
        return depth of the tree from this node
        """
        if self.children:
            return 1 + max([c.depth_down() for c in self.children])
        return 1

    def width(self):
        """
        return the width of the tree from this node
        """
        return len(self.leaves())

    def root(self):
        """
        return the root node of the tree
        """
        if self.parent is not None:
            return self.parent.root()
        return self

    def leaves(self):
        """
        return a list with all the leaves nodes descendant from this node
        """
        leaves = []
        if self.children:
            for child in self.children:
                leaves += child.leaves()
            return leaves
        else:
            return [self]

    def __iter__(self):
        return iter(self.children)

    def flatten(self, _list=None):
        """
        return a list with all the nodes descendant from this node
        """
        if _list is None:
            _list = []
        _list.append(self)
        for c in self.children:
            c.flatten(_list)
        return _list

    def lineage(self):
        """
        return list of parents up to root node
        """
        lst = [self]
        if self.parent is not None:
            lst.extend(self.parent.lineage())
        return lst

class VNode(Node, VisitedMixIn):
    """a visitable node
    """
    pass


class BinaryNode(VNode):
    """a binary node (i.e. only two children
    """
    def __init__(self, lhs=None, rhs=None) :
        VNode.__init__(self)
        if lhs is not None or rhs is not None:
            assert lhs and rhs
            self.append(lhs)
            self.append(rhs)

    def remove(self, child):
        """remove the child and replace this node with the other child
        """
        self.children.remove(child)
        self.parent.replace(self, self.children[0])

    def get_parts(self):
        """
        return the left hand side and the right hand side of this node
        """
        return self.children[0], self.children[1]



if sys.version_info[0:2] >= (2, 2):
    list_class = list
else:
    from UserList import UserList
    list_class = UserList

class ListNode(VNode, list_class):
    """Used to manipulate Nodes as Lists
    """
    def __init__(self):
        list_class.__init__(self)
        VNode.__init__(self)
        self.children = self

    def __str__(self, indent=0):
        return '%s%s %s' % (indent*' ', self.__class__.__name__,
                            ', '.join([str(v) for v in self]))

    def append(self, child):
        """add a node to children"""
        list_class.append(self, child)
        child.parent = self

    def insert(self, index, child):
        """add a node to children"""
        list_class.insert(self, index, child)
        child.parent = self

    def remove(self, child):
        """add a node to children"""
        list_class.remove(self, child)
        child.parent = None

    def pop(self, index):
        """add a node to children"""
        child = list_class.pop(self, index)
        child.parent = None

    def __iter__(self):
        return list_class.__iter__(self)

# construct list from tree ####################################################

def post_order_list(node, filter_func=no_filter):
    """
    create a list with tree nodes for which the <filter> function returned true
    in a post order fashion
    """
    l, stack = [], []
    poped, index = 0, 0
    while node:
        if filter_func(node):
            if node.children and not poped:
                stack.append((node, index))
                index = 0
                node = node.children[0]
            else:
                l.append(node)
                index += 1
                try:
                    node = stack[-1][0].children[index]
                except IndexError:
                    node = None
        else:
            node = None
        poped = 0
        if node is None and stack:
            node, index = stack.pop()
            poped = 1
    return l

def pre_order_list(node, filter_func=no_filter):
    """
    create a list with tree nodes for which the <filter> function returned true
    in a pre order fashion
    """
    l, stack = [], []
    poped, index = 0, 0
    while node:
        if filter_func(node):
            if not poped:
                l.append(node)
            if node.children and not poped:
                stack.append((node, index))
                index = 0
                node = node.children[0]
            else:
                index += 1
                try:
                    node = stack[-1][0].children[index]
                except IndexError:
                    node = None
        else:
            node = None
        poped = 0
        if node is None and len(stack) > 1:
            node, index = stack.pop()
            poped = 1
    return l

class PostfixedDepthFirstIterator(FilteredIterator):
    """a postfixed depth first iterator, designed to be used with visitors
    """
    def __init__(self, node, filter_func=None):
        FilteredIterator.__init__(self, node, post_order_list, filter_func)

class PrefixedDepthFirstIterator(FilteredIterator):
    """a prefixed depth first iterator, designed to be used with visitors
    """
    def __init__(self, node, filter_func=None):
        FilteredIterator.__init__(self, node, pre_order_list, filter_func)