[Abora-cvs] abora-ash/src/org/abora/ash/ent EntException.java,1.1,1.2 ContentLeaf.java,1.1,1.2 EntNo
Status: Alpha
Brought to you by:
dgjones
Menu
▾
▴
[Abora-cvs] abora-ash/src/org/abora/ash/ent EntException.java,1.1,1.2 ContentLeaf.java,1.1,1.2 EntNode.java,1.1,1.2 CollectionLeaf.java,1.1,1.2 SplitNode.java,1.1,1.2 LeafNode.java,1.1,1.2 ChildNode.java,1.1,1.2 RootNode.java,1.1,1.2
Update of /cvsroot/abora/abora-ash/src/org/abora/ash/ent
In directory sc8-pr-cvs1:/tmp/cvs-serv11397/src/org/abora/ash/ent
Modified Files:
EntException.java ContentLeaf.java EntNode.java
CollectionLeaf.java SplitNode.java LeafNode.java
ChildNode.java RootNode.java
Log Message:
-STart leaf tests
Index: EntException.java
===================================================================
RCS file: /cvsroot/abora/abora-ash/src/org/abora/ash/ent/EntException.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** EntException.java 4 May 2003 18:32:06 -0000 1.1
--- EntException.java 8 May 2003 13:53:08 -0000 1.2
***************
*** 7,15 ****
package org.abora.ash.ent;
- import org.abora.ash.engine.AboraException;
/**
*/
! public class EntException extends AboraException {
/**
--- 7,14 ----
package org.abora.ash.ent;
/**
*/
! public class EntException extends RuntimeException {
/**
Index: ContentLeaf.java
===================================================================
RCS file: /cvsroot/abora/abora-ash/src/org/abora/ash/ent/ContentLeaf.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** ContentLeaf.java 4 May 2003 18:32:06 -0000 1.1
--- ContentLeaf.java 8 May 2003 13:53:09 -0000 1.2
***************
*** 27,33 ****
--- 27,49 ----
// !ContentLeaf methodsFor!
//
+
+ public BeContentElement getContentElement() {
+ return contentElement;
+ }
+
// contentElement
// ^contentElement!
//
+
+ private void setContentElement(BeContentElement contentElement) {
+ if (this.contentElement != null) {
+ this.contentElement.removeParent(this);
+ }
+ this.contentElement = contentElement;
+ if (contentElement != null) {
+ contentElement.addParent(this);
+ }
+ }
+
// contentElement: aContentElement
// contentElement notNil ifTrue: [contentElement removeParent: self].
***************
*** 88,91 ****
--- 104,112 ----
// mappings add: (Array with: globalRegion with: anotherRegion)]]!
//
+
+ public SplitNode splitAbout(int newSplit, int elementsPosition) {
+ throw new UnsupportedOperationException("should not implement");
+ }
+
// split: newSplit about: elementsPosition
// "Private - Answer a new SplitNode with two data children with elements before and equal and after elementsPosition."
***************
*** 125,129 ****
public ContentLeaf(SequenceNumber branch, int startPosition, BeContentElement contentElement) {
super(branch, startPosition);
! this.contentElement = contentElement;
}
--- 146,150 ----
public ContentLeaf(SequenceNumber branch, int startPosition, BeContentElement contentElement) {
super(branch, startPosition);
! setContentElement(contentElement);
}
Index: EntNode.java
===================================================================
RCS file: /cvsroot/abora/abora-ash/src/org/abora/ash/ent/EntNode.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** EntNode.java 4 May 2003 18:32:06 -0000 1.1
--- EntNode.java 8 May 2003 13:53:09 -0000 1.2
***************
*** 7,10 ****
--- 7,11 ----
package org.abora.ash.ent;
+ import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
***************
*** 23,29 ****
--- 24,47 ----
protected abstract void addToParent(EntNode node);
+ public List allEditions() {
+ List roots = allRoots();
+ List editions = new ArrayList(roots.size());
+ for (Iterator iter = roots.iterator(); iter.hasNext();) {
+ RootNode root = (RootNode) iter.next();
+ editions.add(root.getEdition());
+ }
+ return editions;
+ }
+
// allEditions
// ^self allRoots collect: [:root | root edition]!
//
+
+ public List allRoots() {
+ List roots = new ArrayList();
+ allRoots(roots);
+ return roots;
+ }
+
// allRoots
// | roots |
***************
*** 32,40 ****
// ^roots!
//
// allRoots: allRoots
// self parents do: [:parent | parent allRoots: allRoots]!
//
! protected EntNode basicParentSplit() {
return null;
}
--- 50,66 ----
// ^roots!
//
+
+ protected void allRoots(List allRoots) {
+ for (Iterator iter = getParents().iterator(); iter.hasNext();) {
+ EntNode node = (EntNode) iter.next();
+ node.allRoots(allRoots);
+ }
+ }
+
// allRoots: allRoots
// self parents do: [:parent | parent allRoots: allRoots]!
//
! protected SplitNode basicParentSplit() {
return null;
}
***************
*** 43,46 ****
--- 69,75 ----
// ^nil!
//
+
+ protected abstract EntNode basicSplayFor(SequenceNumber matchingBranch);
+
public SequenceNumber getBranch() {
return branch;
***************
*** 54,58 ****
//
! protected abstract List children();
// children
--- 83,87 ----
//
! public abstract List children();
// children
***************
*** 88,92 ****
protected abstract void setDspForChild(int dsp, EntNode child);
! protected abstract EntNode duplicateFor(SequenceNumber newBranch) throws EntException;
// duplicateFor: newBranch
--- 117,121 ----
protected abstract void setDspForChild(int dsp, EntNode child);
! public abstract EntNode duplicateFor(SequenceNumber newBranch) throws EntException;
// duplicateFor: newBranch
***************
*** 150,153 ****
--- 179,185 ----
// ^singleParent!
//
+
+ public abstract void insertLeaf(LeafNode leaf, int position, RootNode root);
+
protected boolean isCompatibleFor(SequenceNumber matchingBranch) {
return branch.isBranchingBeforeOrEqual(matchingBranch);
***************
*** 182,190 ****
//
! protected abstract List getParents();
// parents
// self subclassResponsibility!
//
// parentSplit: matchingBranch
// | parent |
--- 214,232 ----
//
! public abstract List getParents();
// parents
// self subclassResponsibility!
//
+
+ protected SplitNode parentSplit(SequenceNumber matchingBranch) {
+ EntNode parent = singleParentFor(matchingBranch);
+ if (parent != null) {
+ return parent.basicParentSplit();
+ } else {
+ return null;
+ }
+ }
+
// parentSplit: matchingBranch
// | parent |
Index: CollectionLeaf.java
===================================================================
RCS file: /cvsroot/abora/abora-ash/src/org/abora/ash/ent/CollectionLeaf.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** CollectionLeaf.java 4 May 2003 18:32:06 -0000 1.1
--- CollectionLeaf.java 8 May 2003 13:53:09 -0000 1.2
***************
*** 17,24 ****
protected IntegerRegion collectionRegion;
- public CollectionLeaf(SequenceNumber branch, int startPosition, byte[] contents) {
- super(branch, startPosition);
- //@todo
- }
// "Filed out from Dolphin Smalltalk 2002 release 5.00"!
//
--- 17,20 ----
***************
*** 114,117 ****
--- 110,123 ----
// mappings add: (Array with: selfRegion with: anotherRegion)]]]!
//
+
+ protected SplitNode splitAbout(int newSplit, int elementsPosition) {
+ if (elementsPosition < 1 || elementsPosition >= count()) {
+ throw new IndexOutOfBoundsException(String.valueOf(elementsPosition));
+ }
+ CollectionLeaf left = new CollectionLeaf(getBranch(), getStartPosition(), collectionHolder, IntegerRegion.startEnd(collectionRegion.getStartPosition(), collectionRegion.getStartPosition()+elementsPosition-1));
+ CollectionLeaf right = new CollectionLeaf(getBranch(), getStartPosition() + elementsPosition - 1, collectionHolder, IntegerRegion.startEnd(collectionRegion.getStartPosition() + elementsPosition - 1, collectionRegion.getEndPosition()));
+ return new SplitNode(getBranch(), newSplit, left, right);
+ }
+
// split: newSplit about: elementsPosition
// "Private - Answer a new SplitNode with two data children with elements before and equal and after elementsPosition."
***************
*** 174,177 ****
--- 180,192 ----
// !CollectionLeaf class methodsFor!
//
+
+ public CollectionLeaf(SequenceNumber branch, int startPosition, byte[] contents) {
+ this(branch, startPosition, new BeCollectionHolder(contents));
+ }
+
+ public CollectionLeaf(SequenceNumber branch, int startPosition, BeCollectionHolder dataCollection) {
+ this(branch, startPosition, dataCollection, IntegerRegion.startExtent(1, dataCollection.count()));
+ }
+
// branch: branch startPosition: startPosition collection: dataCollection
// ^self
***************
*** 181,184 ****
--- 196,206 ----
// region: (IntegerRegion startPosition: 1 endPosition: dataCollection collection size)!
//
+
+ public CollectionLeaf(SequenceNumber branch, int startPosition, BeCollectionHolder collectionHolder, IntegerRegion collectionRegion) {
+ super(branch, startPosition);
+ this.collectionHolder = collectionHolder;
+ this.collectionRegion = collectionRegion;
+ }
+
// branch: branch startPosition: startPosition collection: dataCollection region: collectionRegion
// ^(self basicNew)
Index: SplitNode.java
===================================================================
RCS file: /cvsroot/abora/abora-ash/src/org/abora/ash/ent/SplitNode.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** SplitNode.java 4 May 2003 18:32:06 -0000 1.1
--- SplitNode.java 8 May 2003 13:53:09 -0000 1.2
***************
*** 8,11 ****
--- 8,12 ----
import java.util.ArrayList;
+ import java.util.Iterator;
import java.util.List;
***************
*** 40,44 ****
return position + invertDsp(dsp);
}
[...984 lines suppressed...]
! // !SplitNode categoriesFor: #leftDsp:!accessing!private! !
! // !SplitNode categoriesFor: #nodeAt:!public! !
! // !SplitNode categoriesFor: #removeChild:branch:!public! !
! // !SplitNode categoriesFor: #removeChildLeft!private! !
! // !SplitNode categoriesFor: #removeChildLeftFromRoot!private! !
! // !SplitNode categoriesFor: #removeChildRightMaxElement!private! !
! // !SplitNode categoriesFor: #replaceChild:with:!public! !
! // !SplitNode categoriesFor: #right!accessing!private! !
! // !SplitNode categoriesFor: #right:!accessing!private! !
! // !SplitNode categoriesFor: #rightDsp!accessing!private! !
! // !SplitNode categoriesFor: #rightDsp:!accessing!private! !
! // !SplitNode categoriesFor: #singleRotateLeftFor:!private! !
! // !SplitNode categoriesFor: #singleRotateRightFor:!private! !
! // !SplitNode categoriesFor: #split!accessing!private! !
! // !SplitNode categoriesFor: #split:!accessing!private! !
! // !SplitNode categoriesFor: #transclusionsFrom:extent:found:!accessing!public! !
! //
! //
! //
}
Index: LeafNode.java
===================================================================
RCS file: /cvsroot/abora/abora-ash/src/org/abora/ash/ent/LeafNode.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** LeafNode.java 4 May 2003 18:32:06 -0000 1.1
--- LeafNode.java 8 May 2003 13:53:09 -0000 1.2
***************
*** 7,11 ****
--- 7,13 ----
package org.abora.ash.ent;
+ import java.util.ArrayList;
import java.util.Collections;
+ import java.util.Iterator;
import java.util.List;
***************
*** 14,288 ****
public abstract class LeafNode extends ChildNode {
protected int startPosition = 0;
!
protected LeafNode(SequenceNumber branch, int startPosition) {
super(branch);
this.startPosition = startPosition;
}
-
- // "Filed out from Dolphin Smalltalk 2002 release 5.00"!
- //
- // ChildNode subclass: #LeafNode
- // instanceVariableNames: 'startPosition'
- // classVariableNames: ''
- // poolDictionaries: ''
- // classInstanceVariableNames: ''!
- // LeafNode guid: (GUID fromString: '{F64D0B1E-54DA-4D5C-97C8-665909D3718D}')!
- // LeafNode comment: ''!
- // !LeafNode categoriesForClass!Kernel-Objects! !
- // !LeafNode methodsFor!
- //
- // basicInsert: dataLeaf at: position root: root
- // | index |
- // index := position - startPosition + 1.
- // (index < 1 or: [index > (self count + 1)]) ifTrue: [self errorSubscriptBounds: position].
- // index = 1
- // ifTrue:
- // ["insert before"
- //
- // (self isMinNodeFor: root branch)
- // ifTrue: [self basicInsertBeforeEnt: dataLeaf root: root]
- // ifFalse:
- // [^self
- // basicInsertBeforeSelf: dataLeaf
- // at: position
- // root: root]]
- // ifFalse:
- // [index <= self count
- // ifTrue:
- // ["split then insert"
- //
- // | splitNode |
- // splitNode := self replaceWithSplit: position about: index.
- // ^splitNode right
- // insert: dataLeaf
- // at: position
- // root: root]
- // ifFalse:
- // [(self isMaxNodeFor: root branch)
- // ifTrue: [self basicInsertAfterEnt: dataLeaf root: root]
- // ifFalse: [self errorSubscriptBounds: position]]]!
- //
- // basicInsertAfterEnt: dataLeaf root: root
- // "add to end of entire ent"
- //
- // | splitNode |
- // splitNode := SplitNode
- // branch: root branch
- // split: dataLeaf startPosition
- // left: root child
- // leftDsp: root dsp
- // right: dataLeaf.
- // root child: splitNode.
- // root dsp: 0!
- //
- // basicInsertBeforeEnt: dataLeaf root: root
- // "add to beginning of entire ent"
- //
- // | splitNode |
- // splitNode := SplitNode
- // branch: root branch
- // split: dataLeaf count + dataLeaf startPosition
- // left: dataLeaf
- // right: root child
- // rightDsp: dataLeaf count + root dsp.
- // root child: splitNode.
- // root dsp: 0!
- //
- // basicInsertBeforeSelf: dataLeaf at: position root: root
- // "add before self"
- //
- // | parent newBranch |
- // newBranch := root branch.
- // parent := self parentSplit: newBranch.
- // self assert: [parent notNil].
- // self assert: [parent left == self or: [parent right == self]].
- // (parent left == self or: [(parent parentSplit: newBranch) isNil])
- // ifTrue:
- // [| a b |
- // (root child isSameFor: newBranch) ifTrue: [root child right removeFromParent: root child].
- // a := SplitNode
- // branch: newBranch
- // split: dataLeaf startPosition + dataLeaf count
- // left: dataLeaf
- // right: root child right
- // rightDsp: dataLeaf count + root child rightDsp + root dsp.
- // (root child isSameFor: newBranch) ifTrue: [root child left removeFromParent: root child].
- // b := SplitNode
- // branch: newBranch
- // split: dataLeaf startPosition
- // left: root child left
- // leftDsp: root child leftDsp + root dsp
- // right: a.
- // root child: b.
- // root dsp: 0]
- // ifFalse:
- // ["Force self to other side of parent by splaying"
- //
- // parent basicSplayFor: newBranch.
- // ^self
- // basicInsert: dataLeaf
- // at: position
- // root: root]!
- //
- // basicSplayFor: matchingBranch
- // ^(self singleParentFor: matchingBranch) basicSplayFor: matchingBranch!
- //
- // children
- // ^#()
- // !
! public List children() {
! return Collections.EMPTY_LIST;
! }
! //
! // constrainedIndexFrom: position
! // | index |
! // index := position - self startPosition + 1.
! // (index < 1 or: [index > self count]) ifTrue: [self errorSubscriptBounds: index].
! // ^index!
! //
! // contents
! // ^self contentsFrom: self startPosition extent: self count!
! //
! // contentsAt: position
! // | index |
! // index := self constrainedIndexFrom: position.
! // ^self contentsAtConstrainedIndex: index!
! //
! // contentsAtConstrainedIndex: index
! // self subclassResponsibility!
! //
! // duplicateFor: newBranch
! // self shouldNotImplement!
! public EntNode duplicateFor(SequenceNumber newBranch) {
! throw new UnsupportedOperationException("duplicateFor");
!
! }
! //
! // firstNodeFrom: position extent: extent shouldSplit: shouldSplit
! // | index |
! // index := self constrainedIndexFrom: position.
! // shouldSplit ifFalse: [^self].
! // ^index > 1
! // ifTrue:
! // [| newParent |
! // newParent := self replaceWithSplit: position about: index.
! // newParent right
! // firstNodeFrom: position
! // extent: extent
! // shouldSplit: shouldSplit]
! // ifFalse:
! // [extent < self count
! // ifTrue:
! // [| newParent |
! // newParent := self replaceWithSplit: position + extent about: extent + 1.
! // newParent left]
! // ifFalse: [self]]!
! //
! // globalPositionFor: matchingBranch
! // ^self globalPositionFor: matchingBranch to: nil!
! //
! // globalPositionFor: matchingBranch to: topParent
! // | position node parent |
! // position := self startPosition.
! // node := self.
! // [(parent := node singleParentFor: matchingBranch) ~~ topParent] whileTrue:
! // [position := position + (parent dspForChild: node).
! // node := parent].
! // ^position!
! //
! // globalRegionFor: forBranch
! // ^IntegerRegion startPosition: (self globalPositionFor: forBranch) extent: self count!
! //
! // insert: dataLeaf at: position root: root
! // | index |
! // index := position - startPosition + 1.
! // (index < 1 or: [index > (self count + 1)]) ifTrue: [self errorSubscriptBounds: position].
! // self basicSplayFor: root branch.
! // self
! // basicInsert: dataLeaf
! // at: position
! // root: root!
! //
! // isMaxNodeFor: matchingBranch
! // | node parent |
! // node := self.
! // [(parent := node parentSplit: matchingBranch) notNil] whileTrue:
! // [parent right == node ifFalse: [^false].
! // node := parent].
! // ^true!
! //
! // isMinNodeFor: matchingBranch
! // | node parent |
! // node := self.
! // [(parent := node parentSplit: matchingBranch) notNil] whileTrue:
! // [parent left == node ifFalse: [^false].
! // node := parent].
! // ^true!
! //
! // maxNode
! // ^self!
! //
! // minNode
! // ^self!
! //
! // nodeAt: position
! // | index |
! // index := self constrainedIndexFrom: position.
! // ^self!
! //
! // removeFor: newBranch
! // self basicSplayFor: newBranch.
! // (self singleParentFor: newBranch) removeChild: self branch: newBranch!
! //
! // replaceWithSplit: newSplit about: elementsPosition
! // "Answer a new SplitNode with two data children with elements before and equal and after elementsPosition.
! // NOTE: This operation is unusual in that all parent versions are redirected to point to the replacement split node."
! //
! // | splitNode |
! // splitNode := self split: newSplit about: elementsPosition.
! // self parents do: [:parent | parent replaceChild: self with: splitNode].
! // self assert: [self parents isEmpty].
! // ^splitNode!
! //
! // split: newSplit about: elementsPosition
! // self subclassResponsibility!
! //
! // startPosition
! // ^startPosition!
! //
! // startPosition: anObject
! // startPosition := anObject! !
! // !LeafNode categoriesFor: #basicInsert:at:root:!private! !
! // !LeafNode categoriesFor: #basicInsertAfterEnt:root:!private! !
! // !LeafNode categoriesFor: #basicInsertBeforeEnt:root:!private! !
! // !LeafNode categoriesFor: #basicInsertBeforeSelf:at:root:!private! !
! // !LeafNode categoriesFor: #basicSplayFor:!private! !
! // !LeafNode categoriesFor: #children!public! !
! // !LeafNode categoriesFor: #constrainedIndexFrom:!private! !
! // !LeafNode categoriesFor: #contents!public! !
! // !LeafNode categoriesFor: #contentsAt:!public! !
! // !LeafNode categoriesFor: #contentsAtConstrainedIndex:!public! !
! // !LeafNode categoriesFor: #duplicateFor:!public! !
! // !LeafNode categoriesFor: #firstNodeFrom:extent:shouldSplit:!public! !
! // !LeafNode categoriesFor: #globalPositionFor:!public! !
! // !LeafNode categoriesFor: #globalPositionFor:to:!private! !
! // !LeafNode categoriesFor: #globalRegionFor:!public! !
! // !LeafNode categoriesFor: #insert:at:root:!public! !
! // !LeafNode categoriesFor: #isMaxNodeFor:!public! !
! // !LeafNode categoriesFor: #isMinNodeFor:!public! !
! // !LeafNode categoriesFor: #maxNode!public! !
! // !LeafNode categoriesFor: #minNode!public! !
! // !LeafNode categoriesFor: #nodeAt:!public! !
! // !LeafNode categoriesFor: #removeFor:!public! !
! // !LeafNode categoriesFor: #replaceWithSplit:about:!public! !
! // !LeafNode categoriesFor: #split:about:!public! !
! // !LeafNode categoriesFor: #startPosition!accessing!private! !
! // !LeafNode categoriesFor: #startPosition:!accessing!private! !
! //
! //
! //
protected void replaceChild(EntNode existingChild, EntNode newChild) {
throw new UnsupportedOperationException("no children");
--- 16,436 ----
public abstract class LeafNode extends ChildNode {
protected int startPosition = 0;
!
protected LeafNode(SequenceNumber branch, int startPosition) {
super(branch);
this.startPosition = startPosition;
}
! // "Filed out from Dolphin Smalltalk 2002 release 5.00"!
! //
! // ChildNode subclass: #LeafNode
! // instanceVariableNames: 'startPosition'
! // classVariableNames: ''
! // poolDictionaries: ''
! // classInstanceVariableNames: ''!
! // LeafNode guid: (GUID fromString: '{F64D0B1E-54DA-4D5C-97C8-665909D3718D}')!
! // LeafNode comment: ''!
! // !LeafNode categoriesForClass!Kernel-Objects! !
! // !LeafNode methodsFor!
! //
! protected void basicInsertChild(LeafNode leaf, int position, RootNode root) {
! int index = position - startPosition + 1;
! if (index < 0 || index > count()) {
! throw new IndexOutOfBoundsException(String.valueOf(position));
! }
! if (index == 0) {
! // Insert before
! if (isMinNodeFor(root.getBranch())) {
! basicInsertBeforeEnt(leaf, root);
! } else {
! basicInsertBeforeSelf(leaf, position, root);
! }
! } else {
! if (index < count()) {
! //TODO split then insert
! SplitNode splitNode = replaceWithSplit(position, index);
! splitNode.getRight().insertLeaf(leaf, position, root);
! } else {
! if (isMaxNodeFor(root.getBranch())) {
! basicInsertAfterEnt(leaf, root);
! } else {
! throw new IndexOutOfBoundsException(String.valueOf(position));
! }
! }
! }
! }
! // basicInsert: dataLeaf at: position root: root
! // | index |
! // index := position - startPosition + 1.
! // (index < 1 or: [index > (self count + 1)]) ifTrue: [self errorSubscriptBounds: position].
! // index = 1
! // ifTrue:
! // ["insert before"
! //
! // (self isMinNodeFor: root branch)
! // ifTrue: [self basicInsertBeforeEnt: dataLeaf root: root]
! // ifFalse:
! // [^self
! // basicInsertBeforeSelf: dataLeaf
! // at: position
! // root: root]]
! // ifFalse:
! // [index <= self count
! // ifTrue:
! // ["split then insert"
! //
! // | splitNode |
! // splitNode := self replaceWithSplit: position about: index.
! // ^splitNode right
! // insert: dataLeaf
! // at: position
! // root: root]
! // ifFalse:
! // [(self isMaxNodeFor: root branch)
! // ifTrue: [self basicInsertAfterEnt: dataLeaf root: root]
! // ifFalse: [self errorSubscriptBounds: position]]]!
! //
!
! protected void basicInsertAfterEnt(LeafNode leaf, RootNode root) {
! SplitNode splitNode = new SplitNode(root.getBranch(), leaf.getStartPosition(), root.getChild(), root.getDsp(), leaf);
! root.setChild(splitNode);
! root.setDspForChild(0, splitNode);
! }
!
! // basicInsertAfterEnt: dataLeaf root: root
! // "add to end of entire ent"
! //
! // | splitNode |
! // splitNode := SplitNode
! // branch: root branch
! // split: dataLeaf startPosition
! // left: root child
! // leftDsp: root dsp
! // right: dataLeaf.
! // root child: splitNode.
! // root dsp: 0!
! //
!
! protected void basicInsertBeforeEnt(LeafNode leaf, RootNode root) {
! SplitNode splitNode =
! new SplitNode(root.getBranch(), leaf.count() + leaf.getStartPosition(), leaf, root.getChild(), leaf.count() + root.getDsp());
! root.setChild(splitNode);
! root.setDspForChild(0, splitNode);
! }
!
! // basicInsertBeforeEnt: dataLeaf root: root
! // "add to beginning of entire ent"
! //
! // | splitNode |
! // splitNode := SplitNode
! // branch: root branch
! // split: dataLeaf count + dataLeaf startPosition
! // left: dataLeaf
! // right: root child
! // rightDsp: dataLeaf count + root dsp.
! // root child: splitNode.
! // root dsp: 0!
! //
!
! protected void basicInsertBeforeSelf(LeafNode leaf, int position, RootNode root) {
! SequenceNumber newBranch = root.getBranch();
! SplitNode parent = parentSplit(newBranch);
! assert parent != null;
! assert parent.getLeft() == this || parent.getRight() == this;
! if (parent.getLeft() == this || parent.parentSplit(newBranch) == null) {
! SplitNode rootChild = (SplitNode) root.getChild();
! if (rootChild.isSameFor(newBranch)) {
! rootChild.getRight().removeFromParent(rootChild);
! }
! SplitNode a =
! new SplitNode(
! newBranch,
! leaf.getStartPosition() + leaf.count(),
! leaf,
! rootChild.getRight(),
! leaf.count() + rootChild.getRightDsp() + root.getDsp());
! if (rootChild.isSameFor(newBranch)) {
! rootChild.getLeft().removeFromParent(root.getChild());
! }
! SplitNode b = new SplitNode(newBranch, leaf.getStartPosition(), rootChild.getLeft(), rootChild.getLeftDsp() + root.getDsp(), a);
! root.setChild(b);
! root.setDsp(0);
! } else {
! // Force self to other side of parent by re-splaying
! parent.basicSplayFor(newBranch);
! basicInsertChild(leaf, position, root);
! }
! }
!
! // basicInsertBeforeSelf: dataLeaf at: position root: root
! // "add before self"
! //
! // | parent newBranch |
! // newBranch := root branch.
! // parent := self parentSplit: newBranch.
! // self assert: [parent notNil].
! // self assert: [parent left == self or: [parent right == self]].
! // (parent left == self or: [(parent parentSplit: newBranch) isNil])
! // ifTrue:
! // [| a b |
! // (root child isSameFor: newBranch) ifTrue: [root child right removeFromParent: root child].
! // a := SplitNode
! // branch: newBranch
! // split: dataLeaf startPosition + dataLeaf count
! // left: dataLeaf
! // right: root child right
! // rightDsp: dataLeaf count + root child rightDsp + root dsp.
! // (root child isSameFor: newBranch) ifTrue: [root child left removeFromParent: root child].
! // b := SplitNode
! // branch: newBranch
! // split: dataLeaf startPosition
! // left: root child left
! // leftDsp: root child leftDsp + root dsp
! // right: a.
! // root child: b.
! // root dsp: 0]
! // ifFalse:
! // ["Force self to other side of parent by splaying"
! //
! // parent basicSplayFor: newBranch.
! // ^self
! // basicInsert: dataLeaf
! // at: position
! // root: root]!
! //
!
! protected EntNode basicSplayFor(SequenceNumber matchingBranch) {
! return singleParentFor(matchingBranch).basicSplayFor(matchingBranch);
! }
!
! // basicSplayFor: matchingBranch
! // ^(self singleParentFor: matchingBranch) basicSplayFor: matchingBranch!
! //
!
! public List children() {
! return Collections.EMPTY_LIST;
! }
!
! // children
! // ^#()
! // !
! //
! // constrainedIndexFrom: position
! // | index |
! // index := position - self startPosition + 1.
! // (index < 1 or: [index > self count]) ifTrue: [self errorSubscriptBounds: index].
! // ^index!
! //
! // contents
! // ^self contentsFrom: self startPosition extent: self count!
! //
! // contentsAt: position
! // | index |
! // index := self constrainedIndexFrom: position.
! // ^self contentsAtConstrainedIndex: index!
! //
! // contentsAtConstrainedIndex: index
! // self subclassResponsibility!
! //
!
! public EntNode duplicateFor(SequenceNumber newBranch) {
! throw new UnsupportedOperationException("duplicateFor");
!
! }
!
! // duplicateFor: newBranch
! // self shouldNotImplement!
! //
! // firstNodeFrom: position extent: extent shouldSplit: shouldSplit
! // | index |
! // index := self constrainedIndexFrom: position.
! // shouldSplit ifFalse: [^self].
! // ^index > 1
! // ifTrue:
! // [| newParent |
! // newParent := self replaceWithSplit: position about: index.
! // newParent right
! // firstNodeFrom: position
! // extent: extent
! // shouldSplit: shouldSplit]
! // ifFalse:
! // [extent < self count
! // ifTrue:
! // [| newParent |
! // newParent := self replaceWithSplit: position + extent about: extent + 1.
! // newParent left]
! // ifFalse: [self]]!
! //
! // globalPositionFor: matchingBranch
! // ^self globalPositionFor: matchingBranch to: nil!
! //
! // globalPositionFor: matchingBranch to: topParent
! // | position node parent |
! // position := self startPosition.
! // node := self.
! // [(parent := node singleParentFor: matchingBranch) ~~ topParent] whileTrue:
! // [position := position + (parent dspForChild: node).
! // node := parent].
! // ^position!
! //
! // globalRegionFor: forBranch
! // ^IntegerRegion startPosition: (self globalPositionFor: forBranch) extent: self count!
! //
!
! public void insertLeaf(LeafNode leaf, int position, RootNode root) {
! int index = position - startPosition + 1;
! if (index < 0 || index > count()) {
! throw new IndexOutOfBoundsException(String.valueOf(position));
! }
! basicSplayFor(root.getBranch());
! basicInsertChild(leaf, position, root);
! }
!
! // insert: dataLeaf at: position root: root
! // | index |
! // index := position - startPosition + 1.
! // (index < 1 or: [index > (self count + 1)]) ifTrue: [self errorSubscriptBounds: position].
! // self basicSplayFor: root branch.
! // self
! // basicInsert: dataLeaf
! // at: position
! // root: root!
! //
!
! public boolean isMaxNodeFor(SequenceNumber matchingBranch) {
! EntNode node = this;
! SplitNode splitParent;
! while ((splitParent = node.parentSplit(matchingBranch)) != null) {
! if (splitParent.getRight() != node) {
! return false;
! }
! node = splitParent;
! }
! return true;
! }
!
! // isMaxNodeFor: matchingBranch
! // | node parent |
! // node := self.
! // [(parent := node parentSplit: matchingBranch) notNil] whileTrue:
! // [parent right == node ifFalse: [^false].
! // node := parent].
! // ^true!
! //
!
! public boolean isMinNodeFor(SequenceNumber matchingBranch) {
! EntNode node = this;
! SplitNode splitParent;
! while ((splitParent = node.parentSplit(matchingBranch)) != null) {
! if (splitParent.getLeft() != node) {
! return false;
! }
! node = splitParent;
! }
! return true;
! }
!
! // isMinNodeFor: matchingBranch
! // | node parent |
! // node := self.
! // [(parent := node parentSplit: matchingBranch) notNil] whileTrue:
! // [parent left == node ifFalse: [^false].
! // node := parent].
! // ^true!
! //
!
! public EntNode maxNode() {
! return this;
! }
!
! // maxNode
! // ^self!
! //
!
! public EntNode minNode() {
! return this;
! }
!
! // minNode
! // ^self!
! //
! // nodeAt: position
! // | index |
! // index := self constrainedIndexFrom: position.
! // ^self!
! //
! // removeFor: newBranch
! // self basicSplayFor: newBranch.
! // (self singleParentFor: newBranch) removeChild: self branch: newBranch!
! //
!
! protected SplitNode replaceWithSplit(int newSplit, int elementsPosition) {
! SplitNode splitNode = splitAbout(newSplit, elementsPosition);
! List parentsCopy = new ArrayList(getParents());
! for (Iterator iter = parentsCopy.iterator(); iter.hasNext();) {
! EntNode parent = (EntNode) iter.next();
! parent.replaceChild(this, splitNode);
! }
! assert getParents().isEmpty();
! return splitNode;
! }
!
! // replaceWithSplit: newSplit about: elementsPosition
! // "Answer a new SplitNode with two data children with elements before and equal and after elementsPosition.
! // NOTE: This operation is unusual in that all parent versions are redirected to point to the replacement split node."
! //
! // | splitNode |
! // splitNode := self split: newSplit about: elementsPosition.
! // self parents do: [:parent | parent replaceChild: self with: splitNode].
! // self assert: [self parents isEmpty].
! // ^splitNode!
! //
!
! protected abstract SplitNode splitAbout(int newSplit, int elementsPosition);
!
! // split: newSplit about: elementsPosition
! // self subclassResponsibility!
! //
!
! public int getStartPosition() {
! return startPosition;
! }
!
! // startPosition
! // ^startPosition!
! //
! // startPosition: anObject
! // startPosition := anObject! !
! // !LeafNode categoriesFor: #basicInsert:at:root:!private! !
! // !LeafNode categoriesFor: #basicInsertAfterEnt:root:!private! !
! // !LeafNode categoriesFor: #basicInsertBeforeEnt:root:!private! !
! // !LeafNode categoriesFor: #basicInsertBeforeSelf:at:root:!private! !
! // !LeafNode categoriesFor: #basicSplayFor:!private! !
! // !LeafNode categoriesFor: #children!public! !
! // !LeafNode categoriesFor: #constrainedIndexFrom:!private! !
! // !LeafNode categoriesFor: #contents!public! !
! // !LeafNode categoriesFor: #contentsAt:!public! !
! // !LeafNode categoriesFor: #contentsAtConstrainedIndex:!public! !
! // !LeafNode categoriesFor: #duplicateFor:!public! !
! // !LeafNode categoriesFor: #firstNodeFrom:extent:shouldSplit:!public! !
! // !LeafNode categoriesFor: #globalPositionFor:!public! !
! // !LeafNode categoriesFor: #globalPositionFor:to:!private! !
! // !LeafNode categoriesFor: #globalRegionFor:!public! !
! // !LeafNode categoriesFor: #insert:at:root:!public! !
! // !LeafNode categoriesFor: #isMaxNodeFor:!public! !
! // !LeafNode categoriesFor: #isMinNodeFor:!public! !
! // !LeafNode categoriesFor: #maxNode!public! !
! // !LeafNode categoriesFor: #minNode!public! !
! // !LeafNode categoriesFor: #nodeAt:!public! !
! // !LeafNode categoriesFor: #removeFor:!public! !
! // !LeafNode categoriesFor: #replaceWithSplit:about:!public! !
! // !LeafNode categoriesFor: #split:about:!public! !
! // !LeafNode categoriesFor: #startPosition!accessing!private! !
! // !LeafNode categoriesFor: #startPosition:!accessing!private! !
! //
! //
! //
protected void replaceChild(EntNode existingChild, EntNode newChild) {
throw new UnsupportedOperationException("no children");
Index: ChildNode.java
===================================================================
RCS file: /cvsroot/abora/abora-ash/src/org/abora/ash/ent/ChildNode.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** ChildNode.java 4 May 2003 18:32:06 -0000 1.1
--- ChildNode.java 8 May 2003 13:53:09 -0000 1.2
***************
*** 26,30 ****
parents.remove(node);
}
! protected List getParents() {
return parents;
}
--- 26,30 ----
parents.remove(node);
}
! public List getParents() {
return parents;
}
Index: RootNode.java
===================================================================
RCS file: /cvsroot/abora/abora-ash/src/org/abora/ash/ent/RootNode.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** RootNode.java 4 May 2003 18:32:06 -0000 1.1
--- RootNode.java 8 May 2003 13:53:09 -0000 1.2
***************
*** 25,44 ****
}
public RootNode(BeEdition edition, SequenceNumber branch, ChildNode child) {
! super(branch);
! this.edition = edition;
! this.child = child;
}
public RootNode(BeEdition edition, SequenceNumber branch, ChildNode child, int dsp) {
super(branch);
this.edition = edition;
- this.child = child;
this.dsp = dsp;
}
// allRoots: allRoots
// allRoots add: self!
//
// applyDspTo: position
// | dspPosition |
--- 25,50 ----
}
public RootNode(BeEdition edition, SequenceNumber branch, ChildNode child) {
! this(edition, branch, child, 0);
}
public RootNode(BeEdition edition, SequenceNumber branch, ChildNode child, int dsp) {
super(branch);
this.edition = edition;
this.dsp = dsp;
+ setChild(child);
}
+ protected void allRoots(List allRoots) {
+ allRoots.add(this);
+ }
// allRoots: allRoots
// allRoots add: self!
//
+
+ protected int applyDspTo(int position) {
+ return position + invertDsp();
+ }
+
// applyDspTo: position
// | dspPosition |
***************
*** 56,59 ****
--- 62,72 ----
// self child ~~ node ifTrue: [EntError signal: 'unknown child of root']!
//
+
+ protected EntNode basicSplayFor(SequenceNumber matchingBranch) {
+ //TODO only called in the case of a single child
+ ensureSameFor(matchingBranch);
+ return getChild();
+ }
+
// basicSplayFor: matchingBranch
// "only called in the case of a single child"
***************
*** 92,96 ****
// aNodeOrNil notNil ifTrue: [aNodeOrNil addToParent: self]!
//
! protected List children() {
if (!hasChild())
return Collections.EMPTY_LIST;
--- 105,109 ----
// aNodeOrNil notNil ifTrue: [aNodeOrNil addToParent: self]!
//
! public List children() {
if (!hasChild())
return Collections.EMPTY_LIST;
***************
*** 140,143 ****
--- 153,160 ----
return dsp;
}
+
+ public void setDsp(int dsp) {
+ this.dsp = dsp;
+ }
// dsp
// ^dsp!
***************
*** 166,170 ****
// ^self dsp!
//
! protected EntNode duplicateFor(SequenceNumber newBranch) throws NonSameBranchException {
// Do not duplicate RootNodes at the moment, as this forced to happen on newEdition.
// @todo is this the right behaviour - not duplicating?
--- 183,187 ----
// ^self dsp!
//
! public EntNode duplicateFor(SequenceNumber newBranch) {
// Do not duplicate RootNodes at the moment, as this forced to happen on newEdition.
// @todo is this the right behaviour - not duplicating?
***************
*** 213,216 ****
--- 230,254 ----
// self dsp: 0.!
//
+
+
+ public void insert(LeafNode leaf) {
+ //TODO what abut dsp?
+ ensureSameFor(leaf.getBranch());
+ if (hasChild()) {
+ child.insertLeaf(leaf, applyDspTo(leaf.getStartPosition()), this);
+ } else {
+ //TODO review this default location of 1
+ if (leaf.getStartPosition() == 0) {
+ setChild(leaf);
+ } else {
+ throw new IndexOutOfBoundsException(String.valueOf(leaf.getStartPosition()));
+ }
+ }
+ }
+
+ public void insertLeaf(LeafNode leaf, int position, RootNode root) {
+ throw new UnsupportedOperationException();
+ }
+
// insert: dataLeaf
// "what about dsp?"
***************
*** 231,234 ****
--- 269,277 ----
// root: self]!
//
+
+ protected int invertDsp() {
+ return -dsp;
+ }
+
// invertDsp
// ^dsp negated!
|