# zwiki Outline class (page hierarchy helper) from __future__ import nested_scopes from types import * class Outline: """ I represent and answer questions about a multi-root, multi-parent hierarchy of objects, usually strings, efficiently. This is based on Ken Manheimer's WikiNesting enhancement. For the moment, an Outline has _parentmap = {'Root':[],'Child':['Root'],'GrandChild':['Child'],'Single':[]} _childmap = {'Root':['Child'],'Child':['GrandChild'],'GrandChild':[],'Single':[]} _nesting = [['Root',['Child','GrandChild']],'Single'] A nesting represents outline nodes as follows: Leaves: the string name of the page Nodes with children: a list beginning with the parent node's name Nodes with omitted children (for brevity): list with one string. _childmap and _nesting are derived from _parentmap. Outlines and nestings should perhaps be the same thing. """ _parentmap = {} _childmap = {} _nesting = [] def parentmap(self): return self._parentmap def setParentmap(self,parentmap): self._parentmap = parentmap def childmap(self): return self._childmap def setChildmap(self,childmap): self._childmap = childmap def nesting(self): return self._nesting def setNesting(self,nesting): self._nesting = nesting def nodes(self): """Return a sorted list of all nodes.""" nodes = self.parentmap().keys() nodes.sort() return nodes def nodeCount(self): return len(self.nodes()) def hasNode(self,node): return node in self.nodes() def flat(self): """Return a flattened version of the outline, preserving order.""" return flatten(self.nesting()) def roots(self): """Return a sorted list of the root nodes.""" return filter(lambda x:not self.parents(x), self.nodes()) def leaves(self): """Return a sorted list of the leaf nodes.""" return filter(lambda x:not self.children(x), self.nodes()) def updateChildmap(self,reset=0): """Regenerate childmap from parentmap. childmap is the inverse of parentmap - except, it remembers any manual re-ordering of children. Unless reset is true we try to preserve the order of children, which complicates things badly. """ nodes = self.nodes() # XXX still problems with things not getting updated properly oldchildmap = self.childmap() if reset: childmap = {} else: # backwards compatibility: 0.39 might have set this to None childmap = self.childmap() or {} # remove any no-longer-existing nodes from childmap for p in childmap.keys()[:]: if not p in nodes: del childmap[p] else: for c in childmap[p][:]: # a copy if not c in nodes: childmap[p].remove(c) # make sure each existing node appears in the childmap for c in nodes: for p in self.parents(c): # each parent should have a childmap entry including this child if not childmap.has_key(p): childmap[p] = [c] elif not c in childmap[p]: childmap[p].append(c) # add a childmap entry for any nodes we missed (non-parents) for l in filter(lambda x:x not in childmap.keys(),nodes): childmap[l] = [] self.setChildmap(childmap) def updateNesting(self): """Regenerate nesting from childmap and roots.""" self.setNesting(self.offspring(self.roots())) def update(self): """Regenerate everything from the parentmap.""" self.updateChildmap() self.updateNesting() def __init__(self,parentmap={}): self.setParentmap(parentmap) self.update() def add(self,node,parents=[],update=1): """ Add node to the outline, under the specified parents if any. If node is already present, it will be reparented. """ parentmap = self.parentmap() parentmap[node] = parents[:] # use a copy self.setParentmap(parentmap) if update: self.update() def delete(self,node,update=1): """ Remove node from the outline. """ for c in self.children(node): self.reparent(c,self.parents(node),update=0) parentmap = self.parentmap() del parentmap[node] self.setParentmap(parentmap) if update: self.update() def replace(self,node,newnode,update=1): """ Replace node with newnode in the outline. If node wasn't there, just add newnode. This is useful for rename(). Should this sort of robustness check be done here or there ? Tries to preserve node's ordering among it's siblings, as in updateChildMap. """ parentmap = self.parentmap() # replace node with newnode, preserving node's parents parents = self.parents(node) if parentmap.has_key(node): del parentmap[node] parentmap[newnode] = parents # reparent node's children under newnode for c in filter(lambda x:node in parentmap[x],parentmap.keys()): parentmap[c].remove(node) parentmap[c].append(newnode) self.setParentmap(parentmap) # tweak childmap before updateChildMap, to preserve node's position childmap = self.childmap() for p in childmap.keys(): if node in childmap[p]: childmap[p][childmap[p].index(node)] = newnode self.setChildmap(childmap) if update: self.update() def reparent(self,node,newparents,update=1): """ Change node's parents to newparents in the outline. """ # help prepare childmap for updateChildMap childmap = self.childmap() for p in self.parents(node): childmap[p].remove(node) self.setChildmap(childmap) self.add(node,newparents,update) def reorder(self,node,child=None): """ Moves child one place to the left among node's children (in _childmap). If a child is not specified, sort all children alphabetically. """ childmap = self.childmap() #we do no error checking in this class IIRC #if not childmap.has_key(node): return children = childmap[node] if child: #if not child in children: return i = children.index(child) #if not i: return children[i-1], children[i] = children[i], children[i-1] else: children.sort() childmap[node] = children self.setChildmap(childmap) self.updateNesting() def first(self): """ Get the first node in the outline. """ list = self.flat() if list: return list[0] else: return None def last(self): """ Get the last node in the outline. """ list = self.flat() if list: return list[-1] else: return None def next(self,node,wrap=0): """ Get the next node in the outline. """ list = self.flat() if node in list: i = list.index(node) if i < len(list)-1: return list[i+1] elif wrap: return list[0] return None def previous(self,node,wrap=0): """ Get the previous node in the outline. """ list = self.flat() if node in list: i = list.index(node) if i > 0: return list[i-1] elif wrap: return list[-1] return None def ancestors(self,node): """ Return a nesting representing the ancestors of the specified node. node itself is included. """ ancestors = {} tops = {} offspring = {} todo = {node: None} # Go up, identifying all and topmost forebears: while todo: doing = todo todo = {} for n in doing.keys(): if ancestors.has_key(n): continue # already collected this one else: ancestors[n] = None parents = self.parents(n) if parents: for p in parents: if offspring.has_key(p): offspring[p].append(n) else: offspring[p] = [n] todo[p] = None else: tops[n] = None # Ok, now go back down, unravelling each forebear only once: tops = tops.keys() tops.sort did = {}; got = [] for t in tops: got.append(descend_ancestors(t, ancestors, did, offspring)) return got def ancestorsAndSiblings(self,node): """ Return a nesting representing the ancestors and siblings of node. """ ancestors = {} tops = {} offspring = {} todo = {node: None} # Go up, identifying all and topmost forebears: while todo: doing = todo todo = {} for n in doing.keys(): if ancestors.has_key(n): continue else: ancestors[n] = None parents = self.parents(n) if parents: for p in parents: if p != n: if offspring.has_key(p): offspring[p].append(n) else: offspring[p] = [n] todo[p] = None else: tops[n] = None # Ok, now go back down, unravelling each forebear only once: tops = tops.keys() tops.sort did = {}; got = [] for t in tops: if t == node: got.append([t]) else: got.append(descend_ancestors(t,ancestors,did,offspring)) return got def ancestorsAndChildren(self,node): """ Return a nesting representing the ancestors and children of node. """ # Go up, identifying all and topmost forebears: ancestors = {} tops = {} todo = {node: None} while todo: doing = todo todo = {} for n in doing.keys(): if ancestors.has_key(n): continue else: ancestors[n] = None parents = self.parents(n) if parents: for p in parents: todo[p] = None else: tops[n] = None ancestors[node] = None # Finesse inclusion of page's offspring # Ok, now go back down, showing offspring of all intervening ancestors: tops = tops.keys() tops.sort did = {}; got = [] for t in tops: got.append(descend_ancestors(t, ancestors, did, self.childmap())) return got def parents(self,node=None): """ Return a nesting/list representing node's immediate parents. """ return self.parentmap().get(node,[])[:] def firstParent(self,node): """ Return the first parent of node, if any. """ parents = self.parentmap().get(node,None) if parents: return parents[0] else: return None def siblings(self,node,include_me=False,sort_alpha=True): """ Return a nesting/list representing node's siblings. Ie, any other children of node's first parent. Any siblings by the other parents are not included. Optionally include the current page (node) in the list. Optionally suppress alphabetical sorting of result. """ parent = self.firstParent(node) sibs = self.children(parent) if not include_me: sibs.remove(node) if sort_alpha: sibs.sort() return sibs def children(self,node=None): """ Return a nesting/list representing node's immediate children. If node is None or [], return the roots. """ if self.hasNode(node): return self.childmap()[node][:] elif not node: return self.roots() else: return [] def offspring(self,nodes,did=None,depth=None): """ Return a nesting representing all descendants of all specified nodes. nodes is a list of nodes; these will be included in the nesting. did is used only for recursion. If depth is specified, descendendants beyond that depth will be ignored. XXX this is better done in the view layer, remove it. """ if did is None: did = {} got = [] for n in nodes: been_there = did.has_key(n) did[n] = None if self.childmap().has_key(n) and not depth==0: children = self.childmap()[n] if children: subgot = [n] if not been_there: subgot.extend( self.offspring(children, depth=(depth and depth-1), did=did)) got.append(subgot) else: got.append(n) else: got.append(n) return got # never index this object, so find all object in the catalog doesn't break def index_object(self,idxs=[],log=1): pass # helper functions def descend_ancestors(page, ancestors, did, children): """ Create nesting of ancestors leading to page. page is the name of the subject page. ancestors is a mapping whose keys are pages that are ancestors of page children is a mapping whose keys are pages children, and the values are the children's parents. Do not repeat ones we already did. """ got = [] for c in ((children.has_key(page) and children[page]) or []): if not ancestors.has_key(c): # We don't descend offspring that are not ancestors. got.append(c) elif ((children.has_key(c) and children[c]) or []): if did.has_key(c): # We only show offspring of ancestors once... got.append([c]) else: # ... and this is the first time. did[c] = None got.append(descend_ancestors(c, ancestors, did, children)) else: got.append(c) got.sort() # Terminals will come before composites. got.insert(0, page) return got # copied from Utils to avoid zope dependencies def flatten(recursiveList): """ Flatten a recursive list/tuple structure. """ flatList = [] for i in recursiveList: if type(i) in (ListType,TupleType): flatList.extend(flatten(list(i))) else: flatList.append(i) return flatList flatten2 = lambda l,f=lambda L,F : type(L) != type([]) and [L] or reduce(lambda a,b,F=F : a + F(b,F), L, []) :f(l,f)