1 ##############################################################################
2 #
3 # Copyright (c) 2001 Zope Corporation and Contributors. All Rights Reserved.
4 #
5 # This software is subject to the provisions of the Zope Public License,
6 # Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
7 # THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
8 # WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
9 # WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
10 # FOR A PARTICULAR PURPOSE
11 #
12 ##############################################################################
13 __doc__='''Tree manipulation classes
15 $Id: Tree.py,v 1.1 2002-08-30 08:25:34 richard Exp $'''
16 __version__='$Revision: 1.1 $'[11:-2]
18 from Acquisition import Explicit
19 from ComputedAttribute import ComputedAttribute
21 class TreeNode(Explicit):
22 __allow_access_to_unprotected_subobjects__ = 1
23 state = 0 # leaf
24 height = 1
25 size = 1
26 def __init__(self):
27 self._child_list = []
28 def _add_child(self, child):
29 'Add a child which already has all of its children.'
30 self._child_list.append(child)
31 self.height = max(self.height, child.height + 1)
32 self.size = self.size + child.size
33 def flat(self):
34 'Return a flattened preorder list of tree nodes'
35 items = []
36 self.walk(items.append)
37 return items
38 def walk(self, f, data=None):
39 'Preorder walk this tree, passing each node to a function'
40 if data is None:
41 f(self)
42 else:
43 f(self, data)
44 for child in self._child_list:
45 child.__of__(self).walk(f, data)
46 def _depth(self):
47 return self.aq_parent.depth + 1
48 depth = ComputedAttribute(_depth, 1)
49 def __getitem__(self, index):
50 return self._child_list[index].__of__(self)
51 def __len__(self):
52 return len(self._child_list)
54 _marker = []
56 class TreeMaker:
57 '''Class for mapping a hierachy of objects into a tree of nodes.'''
59 __allow_access_to_unprotected_subobjects__ = 1
61 _id = 'tpId'
62 _values = 'tpValues'
63 _assume_children = 0
64 _values_filter = None
65 _values_function = None
66 _expand_root = 1
68 def setChildAccess(self, attrname=_marker, filter=_marker,
69 function=_marker):
70 '''Set the criteria for fetching child nodes.
72 Child nodes can be accessed through either an attribute name
73 or callback function. Children fetched by attribute name can
74 be filtered through a callback function.
75 '''
76 if function is _marker:
77 self._values_function = None
78 if attrname is not _marker:
79 self._values = str(attrname)
80 if filter is not _marker:
81 self._values_filter = filter
82 else:
83 self._values_function = function
85 def tree(self, root, expanded=None, subtree=0):
86 '''Create a tree from root, with specified nodes expanded.
88 "expanded" must be false, true, or a mapping.
89 Each key of the mapping is the id of a top-level expanded
90 node, and each value is the "expanded" value for the
91 children of that node.
92 '''
93 node = self.node(root)
94 child_exp = expanded
95 if not simple_type(expanded):
96 # Assume a mapping
97 expanded = expanded.has_key(node.id)
98 child_exp = child_exp.get(node.id)
99 if expanded or (not subtree and self._expand_root):
100 children = self.getChildren(root)
101 if children:
102 node.state = 1 # expanded
103 for child in children:
104 node._add_child(self.tree(child, child_exp, 1))
105 elif self.hasChildren(root):
106 node.state = -1 # collapsed
107 if not subtree:
108 node.depth = 0
109 if hasattr(self, 'markRoot'):
110 self.markRoot(node)
111 return node
113 def node(self, object):
114 node = TreeNode()
115 node.object = object
116 node.id = b2a(self.getId(object))
117 return node
119 def getId(self, object):
120 id_attr = self._id
121 if hasattr(object, id_attr):
122 obid = getattr(object, id_attr)
123 if not simple_type(obid): obid = obid()
124 return obid
125 if hasattr(object, '_p_oid'): return str(object._p_oid)
126 return id(object)
128 def hasChildren(self, object):
129 if self._assume_children:
130 return 1
131 return self.getChildren(object)
133 def getChildren(self, object):
134 if self._values_function is not None:
135 return self._values_function(object)
136 if self._values_filter and hasattr(object, 'aq_acquire'):
137 return object.aq_acquire(self._values, aqcallback,
138 self._values_filter)()
139 return getattr(object, self._values)()
141 def simple_type(ob,
142 is_simple={type(''):1, type(0):1, type(0.0):1,
143 type(0L):1, type(None):1 }.has_key):
144 return is_simple(type(ob))
146 def aqcallback(self, inst, parent, name, value, filter):
147 return filter(self, inst, parent, name, value)
149 from binascii import b2a_base64, a2b_base64
150 import string
151 from string import split, join, translate
153 a2u_map = string.maketrans('+/=', '-._')
154 u2a_map = string.maketrans('-._', '+/=')
156 def b2a(s):
157 '''Encode a value as a cookie- and url-safe string.
159 Encoded string use only alpahnumeric characters, and "._-".
160 '''
161 s = str(s)
162 if len(s) <= 57:
163 return translate(b2a_base64(s)[:-1], a2u_map)
164 frags = []
165 for i in range(0, len(s), 57):
166 frags.append(b2a_base64(s[i:i + 57])[:-1])
167 return translate(join(frags, ''), a2u_map)
169 def a2b(s):
170 '''Decode a b2a-encoded string.'''
171 s = translate(s, u2a_map)
172 if len(s) <= 76:
173 return a2b_base64(s)
174 frags = []
175 for i in range(0, len(s), 76):
176 frags.append(a2b_base64(s[i:i + 76]))
177 return join(frags, '')
179 def encodeExpansion(nodes):
180 '''Encode the expanded node ids of a tree into a string.
182 Accepts a list of nodes, such as that produced by root.flat().
183 Marks each expanded node with an expansion_number attribute.
184 Since node ids are encoded, the resulting string is safe for
185 use in cookies and URLs.
186 '''
187 steps = []
188 last_depth = -1
189 n = 0
190 for node in nodes:
191 if node.state <=0: continue
192 dd = last_depth - node.depth + 1
193 last_depth = node.depth
194 if dd > 0:
195 steps.append('.' * dd)
196 steps.append(node.id)
197 node.expansion_number = n
198 n = n + 1
199 return join(steps, ':')
201 def decodeExpansion(s, nth=None):
202 '''Decode an expanded node map from a string.
204 If nth is an integer, also return the (map, key) pair for the nth entry.
205 '''
206 map = m = {}
207 mstack = []
208 pop = 0
209 nth_pair = None
210 if nth is not None:
211 nth_pair = (None, None)
212 for step in split(s, ':'):
213 if step[:1] == '.':
214 pop = len(step) - 1
215 continue
216 if pop < 0:
217 mstack.append(m)
218 m[obid] = {}
219 m = m[obid]
220 elif map:
221 m[obid] = None
222 if len(step) == 0:
223 return map
224 obid = step
225 if pop > 0:
226 m = mstack[-pop]
227 del mstack[-pop:]
228 pop = -1
229 if nth == 0:
230 nth_pair = (m, obid)
231 nth = None
232 elif nth is not None:
233 nth = nth - 1
234 m[obid] = None
235 if nth == 0:
236 return map, (m, obid)
237 if nth_pair is not None:
238 return map, nth_pair
239 return map