ZTUtils/Tree.py

   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
  14
  15 $Id: Tree.py,v 1.1 2002-08-30 08:25:34 richard Exp $'''
  16 __version__='$Revision: 1.1 $'[11:-2]
  17
  18 from Acquisition import Explicit
  19 from ComputedAttribute import ComputedAttribute
  20
  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)
  53
  54 _marker = []
  55
  56 class TreeMaker:
  57     '''Class for mapping a hierachy of objects into a tree of nodes.'''
  58
  59     __allow_access_to_unprotected_subobjects__ = 1
  60
  61     _id = 'tpId'
  62     _values = 'tpValues'
  63     _assume_children = 0
  64     _values_filter = None
  65     _values_function = None
  66     _expand_root = 1
  67
  68     def setChildAccess(self, attrname=_marker, filter=_marker,
  69                        function=_marker):
  70         '''Set the criteria for fetching child nodes.
  71
  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
  84
  85     def tree(self, root, expanded=None, subtree=0):
  86         '''Create a tree from root, with specified nodes expanded.
  87
  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
 112
 113     def node(self, object):
 114         node = TreeNode()
 115         node.object = object
 116         node.id = b2a(self.getId(object))
 117         return node
 118
 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)
 127
 128     def hasChildren(self, object):
 129         if self._assume_children:
 130             return 1
 131         return self.getChildren(object)
 132
 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)()
 140
 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))
 145
 146 def aqcallback(self, inst, parent, name, value, filter):
 147     return filter(self, inst, parent, name, value)
 148
 149 from binascii import b2a_base64, a2b_base64
 150 import string
 151 from string import split, join, translate
 152
 153 a2u_map = string.maketrans('+/=', '-._')
 154 u2a_map = string.maketrans('-._', '+/=')
 155
 156 def b2a(s):
 157     '''Encode a value as a cookie- and url-safe string.
 158
 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)
 168
 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, '')
 178
 179 def encodeExpansion(nodes):
 180     '''Encode the expanded node ids of a tree into a string.
 181
 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, ':')
 200
 201 def decodeExpansion(s, nth=None):
 202     '''Decode an expanded node map from a string.
 203
 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
 240