[IronLute-CVS] ironlute outline.py,1.1,1.2 nodeData.py,1.1,1.2
Status: Pre-Alpha
Brought to you by:
thejerf
Menu
▾
▴
[IronLute-CVS] ironlute outline.py,1.1,1.2 nodeData.py,1.1,1.2
|
From: Jeremy B. <th...@us...> - 2005-05-06 03:58:17
|
Update of /cvsroot/ironlute/ironlute In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv12730 Modified Files: outline.py nodeData.py Log Message: Convert outgoing link list into a linked list, instead of an array. This makes getting the next or previous link a very efficient thing to do, which eliminates an accidental O(n^2) algorithm. Index: nodeData.py =================================================================== RCS file: /cvsroot/ironlute/ironlute/nodeData.py,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** nodeData.py 10 Mar 2005 04:25:57 -0000 1.1 --- nodeData.py 6 May 2005 03:58:05 -0000 1.2 *************** *** 31,34 **** --- 31,35 ---- import weakref from sets import Set + import types from ilerrors import * *************** *** 48,52 **** self.data = "" self.config = {} ! self.outgoing = [] def getNode(self): --- 49,53 ---- self.data = "" self.config = {} ! self.outgoing = OutgoingLinkManager(self) def getNode(self): *************** *** 61,65 **** def addChild(self, newChild = None, pos = None, link = None): ! """addChild adds an already-existing node as position pos. Either a newChild (node) should be passed in, or a link should --- 62,66 ---- def addChild(self, newChild = None, pos = None, link = None): ! """addChild adds an already-existing node at position pos. Either a newChild (node) should be passed in, or a link should *************** *** 73,80 **** If you pass in a link, addChild will use it and only ! manipulate the source of the link. Otherwise, it will create ! one and use the default handling of the link, which is to add ! it to the end of the incoming list of the dest. (This means ! that it's the primary link if no other link existed before.)""" if newChild is None and link is None: --- 74,85 ---- If you pass in a link, addChild will use it and only ! manipulate the source of the link. ! ! @param newChild: The constructed node to add at the given ! position; either this or link should be passed in. ! @param pos: A position, preferably as a link representing the ! insertion point. ! @param link: The link to add at the given position; either ! this or newChild should be passed in.""" if newChild is None and link is None: *************** *** 118,134 **** if link is None: link = outline.Link() - - # Override default link placement behavior if necessary - if pos is not None: - if pos < 0: - pos += len(self.outgoing) - if pos < 0: - raise ValueError("Can't insert node in illegal " - "position.") - self.outgoing.insert(pos, link) link.dest = newChild # Attach link ! link.source = self.node def getChildIndex(self, node): --- 123,130 ---- if link is None: link = outline.Link() link.dest = newChild # Attach link ! link.setSource(self.node, pos) def getChildIndex(self, node): *************** *** 136,140 **** the children. ! Raises ValueError if the node is not in the children.""" # FIXME: Better implementation? --- 132,140 ---- the children. ! Raises ValueError if the node is not in the children. ! ! This function requires a linear search and is slow.""" ! ! #print "getChildIndex used; slow" # FIXME: Better implementation? *************** *** 151,155 **** def getChildCount(self): ! return len(self.getChildren()) def getChildren(self): --- 151,155 ---- def getChildCount(self): ! return len(self.outgoing) def getChildren(self): *************** *** 211,215 **** This is seperate because it may be possible to know the node has children without knowing how many in certain situations.""" ! return len(self.outgoing) > 0 def getAllData(self): --- 211,215 ---- This is seperate because it may be possible to know the node has children without knowing how many in certain situations.""" ! return bool(self.outgoing) def getAllData(self): *************** *** 236,237 **** --- 236,404 ---- return False + + class OutgoingLinkManager(object): + """The default Outgoing Link Manager for the outline node. + + The outgoing link manager objects aggregates functionality + relating to the doubly-linked list of outgoing links. It provides + a link to the head and tail of the list, and an iterator that can + walk it (assuming no changes during iteration).""" + def __init__(self, owner): + """@param owner: The NodeData instance that owns this manager.""" + self.head = None + self.tail = None + self.owner = owner + + def _assertLinkOwnership(self, link): + """This validates the passed-in link is actually owned by this + manager, i.e., the source of the link is the node this data is + attached to. Raises an exception if not.""" + if link.source is not self.owner.node: + raise WrongParentError("Link source is not the owner node.") + + def insertBefore(self, pos, link): + """Inserts the given link in front of pos. + + @param pos: The position to insert the node at. This can be a + link, in which case the new link will be inserted in front of + it, the value None in which case the link is placed on the end, + or a number which is interpreted as an index to put the new + link at. Note the latter should be a last resort, as it is the + slowest, triggering a linear crawl along the link list which + definately has an effect in practice.""" + + self._assertLinkOwnership(link) + + if type(pos) is types.IntType: + pos = self[pos] + + if pos is None: + # Update the link before and after. We can assume the link + # is currently detached, so we can do this freely. + currentTail = self.tail + link._prevLink = currentTail + link._nextLink = None # paranoia + if currentTail is None: + self.head = link + else: + currentTail._nextLink = link + self.tail = link + else: + # pos is a link + prevLink = pos._prevLink + nextLink = pos + link._prevLink = prevLink + link._nextLink = nextLink + pos._prevLink = link + if prevLink is None: + # new head + self.head = link + + def remove(self, link): + self._assertLinkOwnership(link) + linkPrev = link._prevLink + linkNext = link._nextLink + + if linkPrev is not None: + linkPrev._nextLink = linkNext + if linkNext is not None: + linkNext._prevLink = linkPrev + if link is self.head: + self.head = linkNext + if link is self.tail: + self.tail = linkPrev + + link._prevLink = None + link._nextLink = None + + def index(self, l): + """Returns the index of the given link. + + Raises an exception if the link doesn't belong to the + manager. + + @param l: The link to retrieve the index of.""" + try: + self._assertLinkOwnership(l) + except WrongParentError: + # convert to ValueError + raise ValueError("Link not in outgoing links.") + + for i, link in enumerate(self): + if link is l: + return i + raise ValueError("Link not in outgoing links.") + + def append(self, link): + """Appends the link to the tail.""" + self.insertBefore(None, link) + + def prepend(self, link): + """Prepends the link at the beginning.""" + self.insertBefore(self.head, link) + + def forwardIter(self, includeTerminalNone = False): + """This returns an iterator to move forward along the links. + + @param includeTerminalNone: A flag; if True, the terminal None + is included, which is useful internally. If False, only links + will be returned.""" + link = self.head + + while link is not None: + yield link + link = link._nextLink + + if includeTerminalNone: + yield None + + __iter__ = forwardIter + + def backwardIter(self, includeInitialNone = False): + """This returns an iterator to move backward along the links. + + @param includeInitialNone: If true, the first thing yielded + will be the None. If False, only Links will be yielded.""" + + if includeInitialNone: + yield none + + link = self.tail + while link is not None: + yield link + link = link._prevLink + + def __len__(self): + """Returns the number of links. Linear search; slow.""" + i = 0 + for _ in self: + i += 1 + return i + + def __getitem__(self, i): + """Returns the i'th link like Python lists do, or raise + ValueError. + + Note this requires a linear search and is slow if used + carelessly. However, used for small absolute values of i and + it can be the easiest way to retrieve the links that way.""" + #print "getitem in OutgoingLinkManager warning." + if i >= 0: + for count, link in enumerate(self.forwardIter()): + if count == i: + return link + raise IndexError("Link index out of range.") + else: + for count, link in enumerate(self.backwardIter()): + if -1 - count == i: + return link + raise IndexError("Link index out of range.") + + def __nonzero__(self): + return self.head is not None + + def __contains__(self, item): + for link in self.forwardIter(): + if link is item: + return True + return False Index: outline.py =================================================================== RCS file: /cvsroot/ironlute/ironlute/outline.py,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** outline.py 10 Mar 2005 04:25:57 -0000 1.1 --- outline.py 6 May 2005 03:58:04 -0000 1.2 *************** *** 16,20 **** __all__ = ["LinkHandle", "RootHandle", "Link", "BasicNode", ! "BasicDocument", "nodes", "Cursor", "quickMakeNodes"] # FIXME: How do I seperate "Document" from "What manipulations I want --- 16,20 ---- __all__ = ["LinkHandle", "RootHandle", "Link", "BasicNode", ! "BasicDocument", "Cursor", "quickMakeNodes", "EventPrinter"] # FIXME: How do I seperate "Document" from "What manipulations I want *************** *** 25,29 **** # Let's burn this bridge when we get to it. - # FIXME: node.data.outgoing -> node.outgoing # FIXME: handle.node.X -> handle.X # (need to double check that these things are non-overlapping) --- 25,28 ---- *************** *** 160,166 **** if self.creating: return "<Handle #%i under construction>" % self.id - if not hasattr(self, "id"): - import pdb - pdb.set_trace() return "<Handle #%i to link %s>" % (self.id, str(self.link)) --- 159,162 ---- *************** *** 380,395 **** "maximally dedented.") ! # Disconnect this link... ! self.link.source = None ! ! parentIndex = parentHandle.link.sourceIndex() # Inject the link into the grandparent and reconnect grandparentNode = grandparentHandle.getNode() grandparentData = grandparentNode.data ! grandparentData.outgoing.insert(parentIndex+1, self.link) ! self.link.source = grandparentNode ! # and this preserves the location of the link in the incoming ! # list of self.link.node . # Maintain handle information --- 376,385 ---- "maximally dedented.") ! parentLink = parentHandle.link # Inject the link into the grandparent and reconnect grandparentNode = grandparentHandle.getNode() grandparentData = grandparentNode.data ! self.link.setSource(grandparentNode, parentLink._nextLink) # Maintain handle information *************** *** 415,437 **** raise IndexError("Can't get a sibling of the root.") ! index = self.getIndex() ! if index is None: ! raise IndexError("Can't get a sibling because it seems " ! "this handle's parent doesn't know it has " ! "this handle's link as a child. (This is " ! "a bug.)" ) ! if index + delta < 0: ! raise IndexError("Can't get a sibling because the " ! "requested delta results in a " ! "negative index.") ! ! try: ! handle = parent[index + delta] ! except IndexError: ! raise IndexError("Can't get a sibling because there " ! "is no sibling corresponding to %s." ! % delta) ! return handle def deleteLink(self): --- 405,424 ---- raise IndexError("Can't get a sibling of the root.") ! # march backward or forward the given distance on the link ! # chain, then get that handle ! link = self.link ! newLink = link ! if delta < 0: ! incr, att = 1, "_prevLink" ! else: ! incr, att = -1, "_nextLink" ! while delta != 0: ! newLink = getattr(newLink, att) ! if newLink is None: ! raise IndexError("Can't get a sibling because it " ! "goes off the end of the list.") ! delta += incr ! return parent.getHandleForLink(newLink) def deleteLink(self): *************** *** 462,465 **** --- 449,453 ---- def notifyLinkEvent(self, event): """Pass events on, adding handle notation.""" + event = copy.copy(event) event.sourceHandle = self self.notifySubscribers(event) *************** *** 552,559 **** def notifyNodeEvent(self, event): """Pass events on, adding handle notation.""" event.sourceHandle = self self.notifySubscribers(event) - # FIXME: Automatically detach when source gets GC'ed? --- 540,547 ---- def notifyNodeEvent(self, event): """Pass events on, adding handle notation.""" + event = copy.copy(event) event.sourceHandle = self self.notifySubscribers(event) # FIXME: Automatically detach when source gets GC'ed? *************** *** 566,569 **** --- 554,561 ---- should do so, to preserve that information. + Links are also doubly-linked lists pointing back and forth to + their siblings, with None being the terminal pointer. This is used + mostly by Iron Lute internals. + Links subscribe to their dest node and will transmit any events from the source node to the link subscribers. *************** *** 588,591 **** --- 580,585 ---- self._dest = None self._source = None + self._prevLink = None + self._nextLink = None self.dest = dest self.source = source *************** *** 598,603 **** self.dest = None ! def attachSource(self): ! """Attaches the link to the source node in ._source.""" # This must never be called when the node is indeterminate --- 592,601 ---- self.dest = None ! def attachSource(self, pos = None): ! """Attaches the link to the source node in ._source. ! ! @param pos: An option position to attach the source in front ! of, as the link to attach in front of, None to append to the ! end, or an index of the link to attach in front of.""" # This must never be called when the node is indeterminate *************** *** 611,626 **** # If the link is already in the outgoing list, don't # add it; but do fire the event ! # FIXME: We really need a more explicit way of setting order ! # then the implicit way this provides ! if self not in source.data.outgoing: ! # Absent somebody manually inserting the node, put ! # it on the end. ! index = len(source.data.outgoing) ! source.data.outgoing.append(self) ! else: ! index = source.data.outgoing.index(self) event = subscriber.Event("child_added", source, ! node = self.dest, position = ! index) source.notifySubscribers(event) --- 609,616 ---- # If the link is already in the outgoing list, don't # add it; but do fire the event ! source.data.outgoing.insertBefore(pos, self) event = subscriber.Event("child_added", source, ! node = self.dest, ! prev = self._prevLink) source.notifySubscribers(event) *************** *** 663,670 **** dest.incoming.removeLink(self) ! def attach(self): ! """Attach both ends.""" self.attachDest() - self.attachSource() # If the dest has no document, set it to the source document. --- 653,668 ---- dest.incoming.removeLink(self) ! def attach(self, sourcePos = None): ! """Attach both ends. ! ! @private ! ! @param sourcePos: The source position, as either index, or the ! node to be inserted in front of. The sourcePos is allowed to ! be one past the end, if it is an index, to facilitate """ ! # The source is the more sensitive, since sourcePos can ! # be wrong, so make sure it runs correctly before attaching dest ! self.attachSource(sourcePos) self.attachDest() # If the dest has no document, set it to the source document. *************** *** 722,727 **** self.attach() ! def setSource(self, newSource): ! """Parallels setDest.""" # Assume newSource is different from oldSource --- 720,739 ---- self.attach() ! def setSource(self, newSource, pos = None): ! """Sets the source of the link. ! ! By default, or if used via the property, the node will be ! added to the end of the outgoing links, i.e., will be the last ! child. If you use the function call, you can set the pos. ! ! @param newSource: The node that the link comes from. ! @param pos: The pos of the new link, as either the link to ! insert the link in front of, or the position in the list to ! insert the link. (The former is highly preferred for ! performance reasons.) This can not be used to move a link ! around if the newSource is the same as the current source. ! The pos is allowed to be one past the end, which is equivalent ! to appending the node. Anything beyond that throws a value ! error.""" # Assume newSource is different from oldSource *************** *** 748,752 **** if not source: self._source = weakref.ref(newSource) ! self.attach() return --- 760,764 ---- if not source: self._source = weakref.ref(newSource) ! self.attach(pos) return *************** *** 777,780 **** --- 789,814 ---- source = property(getSource, setSource, delSource) + def moveUp(self): + """Tries to advance this link one entry up.""" + if self._prevLink is None: + raise ManipulationError("Can't move child up " + "past beginning of " + "children.") + prevLink = self._prevLink + source = self.source + self.source = None + self.setSource(source, prevLink) + + def moveDown(self): + """Tries to advance this link one entry down.""" + if self._nextLink is None: + raise ManipulationError("Can't move child down " + "past end of children.") + + nextLink = self._nextLink._nextLink + source = self.source + self.source = None + self.setSource(source, nextLink) + def notifyNodeEvent(self, event): """Adds the link annotation to the event and passes it on.""" *************** *** 972,977 **** --- 1006,1013 ---- def getChildLink(self, n): + #print "getChildLink n called, slow" return self.data.outgoing[n] def getChildLinkIndex(self, link): + #print "getChildLinkIndex called, slow" return self.data.outgoing.index(link) def getChildren(self): *************** *** 1001,1004 **** --- 1037,1045 ---- return len(self.data.outgoing) + def __iter__(self): + """Return each of the nodes that is a child of this node.""" + for link in self.data.outgoing: + yield link.dest + # FIXME as needed. def __deepcopy__(self, memo): *************** *** 1154,1186 **** return node - def swapChildren(self, aIndex, bIndex): - """Swaps the nodes indexed by aIndex and bIndex in the - children array.""" - - # It may seem easier to swap the dest nodes, but the problem - # is that would leave handles pointed at the wrong link->node. - # Thus, we need to actually switch at the source. - # also, - # out[aIndex], out[bIndex] = out[bIndex], out[aIndex] - # is not sufficient because it doesn't fire the right events - - if aIndex == bIndex: - return - - out = self.data.outgoing - if aIndex > len(out) or bIndex > len(out): - raise ValueError("Can't swap nodes because child indices " - "are out of range.") - if aIndex > bIndex: - aIndex, bIndex = bIndex, aIndex - firstLink = out[aIndex] - secondLink = out[bIndex] - firstLink.source = None - secondLink.source = None - self.data.outgoing.insert(aIndex, secondLink) - self.data.outgoing.insert(bIndex, firstLink) - secondLink.source = self - firstLink.source = self - def bases(cls): """Bases returns a list of base classes, starting with the --- 1195,1198 ---- |
