You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jena.apache.org by an...@apache.org on 2011/09/30 17:01:57 UTC
svn commit: r1177690 [4/7] - in /incubator/jena/Scratch/AFS/Dev/trunk:
Archive/ src-lib/main/java/libmisc/ src-lib/main/java/migrate/
src-lib/main/java/migrate/lib/ src-lib/main/java/migrate/lib/tuple/
src-lib/main/java/structure/ src-lib/main/java/str...
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTree.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTree.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTree.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTree.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,897 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package structure.ttree;
+
+import static org.openjena.atlas.io.IndentedWriter.stdout;
+import static structure.ttree.TTreeNode.label;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+import migrate.lib.ArrayOps;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+import structure.OrderedSet;
+import structure.tree.TreeException;
+import org.openjena.atlas.io.IndentedWriter;
+import org.openjena.atlas.io.PrintUtils;
+import org.openjena.atlas.io.Printable;
+
+public final
+class TTree<T extends Comparable<? super T>> implements Printable , OrderedSet<T>
+{
+ /* T*Tree : in each leaf or half-leaf, have pointer to successor node.
+ * Speeds traversal. But need to know it's a threading pointer.
+ * "T*-tree : A Main Memory Database Index Structure for Real Time Applications" / 1996
+ */
+
+ /* TODO
+ + Sort out workers - TTreeNode has similar.
+ lib.log(Logger, fmt, args)
+ + size by counting successful ins/del
+ + Delete mods: do before fixup, then fixup.
+ Amalgamate rules come simpler?
+ + Remove id logging from TTreeNodes
+ + Check the rebalanceDelete and termination criterion
+ */
+
+ /* Notes:
+ * See:
+ * http://en.wikipedia.org/wiki/T-tree
+ *
+ * Tobin J. Lehman and Michael J. Carey
+ * "A Study of Index Structures for Main Memory Database Management Systems"
+ * VLDB 1986 -- http://www.vldb.org/conf/1986/P294.PDF
+ *
+ * Deletion:
+ *
+ * The paper allow half-leaves to become less than the min size (3.2.1 - deletion algorithm - step 2)
+ * These can be merged (step 3) but that means we can still have overly small leaves (not mergeable).
+ * These can become internal nodes through rotation resulting in internal nodes that are
+ * not full, which is something that T-Trees try to avoid.
+ * Solution: pull up elements from leaves into a half leaf.
+ *
+ * Rotations cause a branch to become shorter.
+ *
+ * Rebalance after insertion:
+ * Only leaves are added
+ * Rebalance can stop after one rotation occurs
+ * But need to reset heights in tree all the way to the root.
+ * Rebalance after deletion:
+ * One rotation can cause a shorter subtree
+ * Stop when an evenly balanced node is found
+ * But need to reset heights in tree all the way to the root.
+ */
+
+ static Logger log = LoggerFactory.getLogger(TTree.class) ;
+
+ /*
+ * The algorithm of T-Trees goes in this class - the TTreeNode class is
+ * just a structure to be manipulated.
+ */
+ public static boolean NullOut = true ;
+ public static boolean Checking = true ;
+ public static boolean Logging = true ;
+ public static boolean Verbose = false ;
+
+ public final int NodeSize = 2 ; // Maximum node size.
+ public final int NodeSizeMin = 2 ; // Limit at which we rebalance on delete in internal nodes to keep nodes full.
+
+ static int InitialHeight = 1 ; // The height of a node with no nodes below it.
+
+ TTreeNode<T> root ;
+
+ public TTree(int nodeSize)
+ {
+ this(nodeSize, nodeSize) ;
+ }
+
+ public TTree(int nodeSize, int intNodeSize)
+ {
+
+ root = newRoot() ;
+ }
+
+
+ // public TTree(int NodeSize, Comparator<T> comparator)
+// {
+// root = newNode(null) ;
+//
+// comparator = new Comparator<T>()
+// {
+// @Override
+// public int compare(T obj1, T obj2)
+// { return obj1.compareTo(obj2) ; }
+// } ;
+// }
+
+ private TTreeNode<T> newRoot()
+ {
+ return newNode(null) ;
+ }
+
+ private TTreeNode<T> newNode(TTreeNode<T> parent)
+ {
+ TTreeNode<T> n = new TTreeNode<T>(parent, NodeSize) ;
+ if ( Logging )
+ log("** New node: %s [parent=%s]", label(n), label(parent)) ;
+ return n ;
+ }
+
+ @Override
+ public boolean isEmpty()
+ {
+ if ( root == null ) return true ;
+ return root.isEmpty() ;
+ }
+
+ @Override
+ public boolean contains(T item)
+ { return search(item) != null ; }
+
+
+ @Override
+ public T search(T item)
+ {
+ // findBoundingNode checks down the tree using min/max only.
+ // Assuming a tree of non-trivial depth, this is faster than calling
+ // node.find on each node traversed as binary search does not
+ // touch min/max until last.
+
+ if ( root == null )
+ return null ;
+
+ TTreeNode<T> node = findBoundingNode(root, item) ;
+ int x = node.find(item) ;
+ if ( x < 0 )
+ return null ;
+ return node.elements[x] ;
+ }
+
+ @Override
+ public boolean add(T item)
+ {
+ if ( Logging )
+ log.debug(">> Insert: "+item) ;
+ if ( root.isEmpty() )
+ return root.add(item) ;
+
+ TTreeNode<T> node = findBoundingNode(root, item) ;
+ if ( Logging )
+ log.debug("Bounding node: "+node) ;
+
+ boolean b = insertBoundingNode(node, item) ;
+
+ if ( Checking )
+ checkTree() ;
+ if ( Logging )
+ log.debug("<< Insert: "+item) ;
+
+ return b ;
+ }
+
+ @Override
+ public void clear() { root = newRoot() ; }
+
+ private boolean insertBoundingNode(TTreeNode<T> node, T item)
+ {
+ if ( Logging )
+ log("insertBoundingNode(%s, %s)", label(node), item) ;
+ int idx = node.find(item) ;
+ if ( idx >= 0 )
+ {
+ // Duplicate.
+ if ( Logging )
+ log("insertBoundingNode: duplicate") ;
+ return node.add(item) ; // Key same - value may not be.
+ }
+
+ if ( ! node.isFull() )
+ {
+ if ( Logging )
+ log("insertBoundingNode: node not full") ;
+ return node.add(item) ;
+ }
+
+ // Remove minimal element.
+ // Insert item (at decode(idx))
+ // Use minimal element as new insert into left substree.
+ // (Modification: do on right as no shift).
+ // Or put a null and shift down to insert.
+
+ // -1 is encodeIndex(0)
+
+ if ( idx == -1 )
+ {
+ if ( Logging )
+ log("Insert at min point: (%s, %s)", label(node), item) ;
+ // Insert at min in a full node.
+ if ( Checking )
+ {
+ if ( node.left != null ) error("Left not null") ;
+ }
+ node.left = newNode(node) ;
+ node.left.add(item) ;
+ rebalanceInsert(node) ;
+ return true ;
+ }
+
+ // Improve this
+ T min = node.removeBottom() ;
+ node.add(item) ;
+ if ( Logging )
+ log("ShiftDown/add->%s: (%s)", min, node) ;
+
+ // Insert min
+ if ( node.left == null )
+ {
+ if ( Logging )
+ log("Insert new left") ;
+ TTreeNode<T> newNode = newNode(node) ;
+ node.left = newNode ;
+ boolean b = newNode.add(min) ;
+ rebalanceInsert(node) ;
+ return b ;
+ }
+
+ // Insert at greatest lower bound.
+ node = TTreeNode.getRightDeep(node.left) ;
+ int idx2 = node.find(min) ; // Only for same key storage
+ if ( idx2 > 0 || ! node.isFull() )
+ {
+ boolean b = node.add(min) ;
+ if ( Logging )
+ log("Replace GLB: %s", node) ;
+ return b ;
+ }
+
+ // Node full; not a replacement. Add new right and place one element in it.
+ if ( Logging )
+ log("Insert new right") ;
+ TTreeNode<T> newNode = newNode(node) ;
+ node.right = newNode ;
+ boolean b = node.right.add(min) ;
+ rebalanceInsert(node) ;
+ return b ;
+ }
+
+ private void rebalanceInsert(TTreeNode<T> node)
+ {
+ // Need to abort early.
+ while ( node != null )
+ {
+ if ( ! rebalanceNode(node) )
+ return ;
+ node = node.parent ;
+ }
+ return ;
+ }
+
+ private void rebalanceDelete(TTreeNode<T> node)
+ {
+ while ( node != null )
+ {
+ // Need to work all the way up to the tree root.
+// if ( ! rebalanceNode(node) )
+// return ;
+ rebalanceNode(node) ;
+ node = node.parent ;
+ }
+ return ;
+ }
+
+ static <T extends Comparable<? super T>>
+ TTreeNode<T> findBoundingNode(TTreeNode<T> node, T item)
+ {
+ for ( ;; )
+ {
+ // Avoid tail recursion. Sigh.
+ int x = item.compareTo(node.getMin()) ;
+ if ( x < 0 )
+ {
+ if ( node.left == null )
+ return node ;
+ node = node.left ;
+ continue ;
+ }
+
+ x = item.compareTo(node.getMax()) ;
+ if ( x > 0 )
+ {
+ if ( node.right == null )
+ return node ;
+ node = node.right ;
+ continue ;
+ }
+ // Between min and max - this node.
+ x = 0 ;
+ return node ;
+ }
+ }
+
+ @Override public boolean remove(T item)
+ {
+ if ( Logging )
+ {
+ log.debug(">> Delete: "+item) ;
+ output() ;
+ }
+
+ if ( root == null || root.isEmpty() )
+ return false ;
+
+ TTreeNode<T> node = findBoundingNode(root, item) ;
+ boolean b = node.delete(item) ;
+ if ( b )
+ {
+ TTreeNode<T> fixupNode = node ;
+
+ if ( node.isInternal() )
+ {
+ // Internal node - find GLB (must exist for an internal node)
+ // and insert the GLB here, then fixup from bottom node.
+ TTreeNode<T> n2 = TTreeNode.getRightDeep(node.left) ;
+ T glb = n2.removeTop() ;
+ node.add(glb) ;
+ fixupNode = n2 ;
+ }
+
+ fixupDelete(fixupNode) ;
+ }
+
+ if ( Checking )
+ checkTree() ;
+ if ( Logging )
+ log.debug("<< Delete: "+item) ;
+
+ return b ;
+ }
+
+ /** Fix up a node - it is the node that has changed size. */
+ private void fixupDelete(TTreeNode<T> node)
+ {
+ if ( node.nodeSize() >= NodeSizeMin ) return ;
+ if ( Checking && node.isInternal() ) error("Attempt to fixup internal node") ;
+
+ if ( node.isLeaf() )
+ {
+ if ( node.nodeSize() > 0 )
+ {
+ // Check whether to amalgamate with parent (if half leaf??)
+ // Modified deletion: half-leaves are always nearly full.
+ return ;
+ }
+
+ // Empty leaf. Remove in parent.
+
+ if ( node.parent == null )
+ {
+ //root = newRoot() ;
+ // Root now empty.
+ return ;
+ }
+ if ( node.parent.left == node )
+ {
+ // Fix parent height : might have chnaged.
+ node.parent.left = null ;
+ if ( node.parent.right == null )
+ node.parent.height = node.parent.height-1 ;
+ }
+ else
+ {
+ node.parent.right = null ;
+ if ( node.parent.left == null )
+ node.parent.height = node.parent.height-1 ;
+ }
+
+ rebalanceDelete(node.parent) ;
+ return ;
+ }
+
+ if ( node.isLeftHalfLeaf() )
+ {
+ TTreeNode<T> leaf = node.right ;
+ if ( Checking && ! leaf.isLeaf() )
+ error("Expected leaf to right") ;
+ if ( node.nodeSize + leaf.nodeSize <= NodeSize )
+ {
+ // Amalgamate: copy leaf elements to parent half-leaf.
+ System.arraycopy(leaf.elements, 0, node.elements, node.nodeSize, leaf.nodeSize) ;
+ node.nodeSize += leaf.nodeSize ;
+ node.right = null ;
+ node.height = 1 ;
+ rebalanceDelete(node) ;
+ }
+ else // Deletion modification
+ {
+ T item = leaf.removeBottom() ;
+ node.insertAt(node.nodeSize, item) ;
+ }
+ return ;
+ }
+
+ if ( node.isRightHalfLeaf() )
+ {
+ TTreeNode<T> leaf = node.left ;
+ if ( Checking && ! leaf.isLeaf() ) error("Expected leaf to left") ;
+ if ( node.nodeSize + leaf.nodeSize <= NodeSize )
+ {
+ // Amalgamate
+ if ( node.nodeSize > 0 )
+ ArrayOps.shiftUpN(node.elements, 0, leaf.nodeSize, node.nodeSize) ;
+ System.arraycopy(leaf.elements, 0, node.elements, 0, leaf.nodeSize) ;
+ node.nodeSize += leaf.nodeSize ;
+ node.left = null ;
+ rebalanceDelete(node) ;
+ }
+ else
+ {
+ T item = leaf.removeTop() ;
+ node.insertAt(0, item) ;
+ }
+ return ;
+ }
+
+ error("Unknown node type");
+ }
+
+ @Override public T max()
+ {
+ TTreeNode<T> node = TTreeNode.getRightDeep(root) ;
+ return node.getMax() ;
+ }
+
+ @Override public T min()
+ {
+ TTreeNode<T> node = TTreeNode.getLeftDeep(root) ;
+ return node.getMin() ;
+ }
+
+ /** Rebalance one node - return true if a rotation is performed */
+ // Currently returns true if the height changes
+ private boolean rebalanceNode(TTreeNode<T> node)
+ {
+ if ( node == null )
+ return false ;
+
+ if ( Logging )
+ {
+ log(">> Rebalance : %s", node) ;
+ output() ;
+ }
+
+
+ int bal = balance(node) ;
+ if ( Logging )
+ log("-- Rebalance : %d", bal) ;
+
+ if ( bal < -2 || bal > 2 )
+ brokenTree(node, "Unbalanced") ;
+
+ int h = height(node) ;
+
+ if ( bal == 1 || bal == 0 || bal == -1 )
+ {
+ setHeight(node) ; // Propagate height up tree
+ if ( Logging )
+ log("<< Rebalance : %s", node) ;
+ return h != height(node) ;
+ }
+
+ if ( bal == 2 )
+ {
+ // Right heavy :
+ // If we added to the right under a right add then pivotRight
+ // If we added to the left under a right add then pivotRightLeft
+ if ( height(node.right.left) > height(node.right.right) )
+ // Right, then left subnode heavy - double rotation.
+ pivotRightLeft(node) ;
+ else
+ // Right-right heavy
+ pivotRight(node) ;
+ }
+ else// if ( bal == -2 )
+ {
+ // Right, then left heavy:
+ if ( height(node.left.right) > height(node.left.left) )
+ pivotLeftRight(node) ;
+ else
+ pivotLeft(node) ;
+ }
+ setHeight(node) ;
+
+ if ( Logging )
+ log("<< Rebalance : %s", node) ;
+ return h != height(node) ;
+ }
+
+ static <T extends Comparable<? super T>> int balance(TTreeNode<T> node)
+ {
+ if ( node == null )
+ return 0 ;
+ return height(node.right) - height(node.left) ;
+ }
+
+ private static <T extends Comparable<? super T>> void setHeight(TTreeNode<T> node)
+ {
+ //if ( node == null ) return ;
+ node.height = Math.max(height(node.left), height(node.right)) + 1;
+ }
+
+ private static <T extends Comparable<? super T>> int height(TTreeNode<T> node)
+ {
+ if ( node == null )
+ return InitialHeight-1 ;
+ return node.height ;
+ }
+
+ private void pivotLeft(TTreeNode<T> node)
+ {
+ if ( Logging )
+ log(">> pivotLeft : %s", label(node)) ;
+
+ if ( Verbose )
+ output() ;
+
+ // Validity checking?
+ if ( Checking ) checkNotNull(node.left) ;
+
+ TTreeNode<T> n = node.left ;
+ T[] r1 = node.elements ;
+ int r1Size = node.nodeSize ;
+ T[] r2 = n.elements ;
+ int r2Size = n.nodeSize ;
+
+ TTreeNode<T> a = n.left ;
+ TTreeNode<T> b = n.right ;
+ TTreeNode<T> c = node.right ;
+
+ // Reuse n as the node (R1 B C)
+ n.set(r1, r1Size, node, b, c) ;
+ setHeight(n) ;
+
+ // Move to set?
+ if ( a != null ) a.parent = node ;
+ if ( b != null ) b.parent = n ; // No-op
+ if ( c != null ) c.parent = n ;
+
+ node.set(r2, r2Size, node.parent, a, n) ;
+ setHeight(node) ;
+
+ if ( Checking )
+ node.checkDeep(this) ;
+ if ( Logging )
+ log("<< pivotLeft : %s", label(node)) ;
+ }
+
+ // (R1 A (R2 B C)) ==> (R2 (R1 A B) C)
+ private void pivotRight(TTreeNode<T> node)
+ {
+ if ( Logging )
+ log(">> pivotRight : %s", label(node)) ;
+
+ if ( Verbose )
+ output() ;
+
+ if ( Checking )
+ checkNotNull(node.right) ;
+ // Take nodes apart
+ TTreeNode<T> n = node.right ;
+ T[] r1 = node.elements ;
+ int r1Size = node.nodeSize ;
+ T[] r2 = n.elements ;
+ int r2Size = n.nodeSize ;
+
+ TTreeNode<T> a = node.left ;
+ TTreeNode<T> b = n.left ;
+ TTreeNode<T> c = n.right ;
+
+ // Reuse n as the node (R1 A B)
+ n.set(r1, r1Size, node, a, b) ;
+ setHeight(n) ;
+
+ if ( a != null ) a.parent = n ;
+ if ( b != null ) b.parent = n ;
+ if ( c != null ) c.parent = node ;
+
+ node.set(r2, r2Size, node.parent, n, c) ;
+ setHeight(node) ;
+
+ if ( Checking )
+ node.checkDeep(this) ;
+ if ( Logging )
+ log("<< pivotRight : %s", label(node)) ;
+ }
+
+ // LeftRight
+ // (R3 (R1 A (R2 B C)) D) ==> (R2 (R1 A B) (R3 C D))
+ private void pivotLeftRight(TTreeNode<T> node)
+ {
+ if ( Logging )
+ log(">> pivotLeftRight : %s", label(node)) ;
+
+ if ( Verbose )
+ output() ;
+
+
+ if ( Checking )
+ {
+ checkNotNull(node.left) ;
+ checkNotNull(node.left.right) ;
+ }
+
+ // Take apart ...
+ TTreeNode<T> n1 = node.left ;
+ TTreeNode<T> n2 = node.left.right ;
+
+ T[] r3 = node.elements ;
+ int r3Size = node.nodeSize ;
+
+ T[] r1 = n1.elements ;
+ int r1Size = n1.nodeSize ;
+
+ T[] r2 = n2.elements ;
+ int r2Size = n2.nodeSize ;
+ // Check new top node (leaf becomes internal)
+ if ( r2Size == 1 )
+ {
+ // From the T-Tree paper:
+ // A is r3 = node
+ // B is r1 = n1
+ // C is r2 = n2
+ // Slide els from B to C
+ if ( Logging )
+ log("** Special case LR") ;
+ if ( Checking )
+ {
+ if ( ! n2.isLeaf() ) warn("LR: Not a leaf (C)") ;
+ if ( ! n1.isLeftHalfLeaf() ) warn("LR: Not a left half-leaf (B)") ;
+ if ( ! node.isRightHalfLeaf() ) warn("LR: Not a right half-leaf (A)") ;
+ }
+ // Slide els from B(r1) to C(r2)
+ // Old C element
+ T x = r2[0] ;
+ // New C elements
+ System.arraycopy(r1, 1, r2, 0, r1Size-1) ;
+ r2[r1Size-1] = x ;
+ r2Size = r1Size ;
+ n2.nodeSize = r1Size ;
+ // New B element (singular)
+ ArrayOps.clear(r1, 1, r1Size-1) ;
+ n1.nodeSize = 1 ;
+ r1Size = 1 ;
+ }
+
+
+ TTreeNode<T> a = n1.left ;
+ TTreeNode<T> b = n2.left ;
+ TTreeNode<T> c = n2.right ;
+ TTreeNode<T> d = node.right ;
+
+ // Reuse nodes ; n1 becomes the R1 node, n2 the R3 node.
+ n1.set(r1, r1Size, node, a, b) ;
+ setHeight(n1) ;
+ n2.set(r3, r3Size, node, c, d) ;
+ setHeight(n2) ;
+
+ if ( a != null ) a.parent = n1 ;
+ if ( b != null ) b.parent = n1 ;
+ if ( c != null ) c.parent = n2 ;
+ if ( d != null ) d.parent = n2 ;
+
+ node.set(r2, r2Size, node.parent, n1, n2) ;
+ setHeight(node) ;
+
+ if ( Checking )
+ node.checkDeep(this) ;
+
+ if ( Logging )
+ log("<< pivotLeftRight : %s", label(node)) ;
+ }
+
+ // RightLeft
+ // (R1 A (R3 (R2 B C) D)) ==> (R2 (R1 A B) (R3 C D))
+ private void pivotRightLeft(TTreeNode<T> node)
+ {
+ if ( Logging )
+ log(">> pivotRightLeft : %s", label(node)) ;
+
+ if ( Verbose )
+ output() ;
+
+ if ( Checking )
+ {
+ checkNotNull(node.right) ;
+ checkNotNull(node.right.left) ;
+ }
+ TTreeNode<T> n1 = node.right ;
+ TTreeNode<T> n2 = node.right.left ;
+
+ T[] r1 = node.elements ;
+ int r1Size = node.nodeSize ;
+
+ T[] r3 = n1.elements ;
+ int r3Size = n1.nodeSize ;
+
+ T[] r2 = n2.elements ;
+ int r2Size = n2.nodeSize ;
+ // Check new top node (leaf becomes internal)
+ if ( r2Size == 1 )
+ {
+ // A = node ; B = n1 ; C = n2
+ if ( Logging )
+ log("** Special case RL") ;
+ if ( Checking )
+ {
+ if ( ! n2.isLeaf() ) warn("RL: Not a leaf (C)") ;
+ if ( ! n1.isRightHalfLeaf() ) warn("RL: Not a right half-leaf (B)") ;
+ if ( ! node.isLeftHalfLeaf() ) warn("RL: Not a left half-leaf (A)") ;
+ }
+ // Slide els from B(r1) to C(r2)
+ // Old C element
+ T x = r2[0] ;
+ // New C elements
+ System.arraycopy(r1, 1, r2, 0, r1Size-1) ;
+ r2[r1Size-1] = x ;
+ r2Size = r1Size ;
+ n2.nodeSize = r1Size ;
+ // New B element (singular)
+ ArrayOps.clear(r1, 1, r1Size-1) ;
+ n1.nodeSize = 1 ;
+ r1Size = 1 ;
+ }
+
+ TTreeNode<T> a = node.left ;
+ TTreeNode<T> b = n2.left ;
+ TTreeNode<T> c = n2.right ;
+ TTreeNode<T> d = n1.right ;
+
+ // Reuse nodes ; n1 becomes the R1 node, n2 the R3 node.
+ n1.set(r1, r1Size, node, a, b) ;
+ setHeight(n1) ;
+ n2.set(r3, r3Size, node, c, d) ;
+ setHeight(n2) ;
+
+ if ( a != null ) a.parent = n1 ;
+ if ( b != null ) b.parent = n1 ;
+ if ( c != null ) c.parent = n2 ;
+ if ( d != null ) d.parent = n2 ;
+
+ node.set(r2, r2Size, node.parent, n1, n2) ;
+ setHeight(node) ;
+
+ if ( Checking )
+ node.checkDeep(this) ;
+
+ if ( Logging )
+ log("<< pivotRightLeft : %s", label(node)) ;
+ }
+
+
+ @Override
+ final public void checkTree()
+ {
+ if ( ! Checking )
+ return ;
+ if ( root != null )
+ {
+ if ( root.parent != null )
+ brokenTree(root, "Root parent is not null") ;
+ root.checkDeep(this) ;
+ }
+
+ }
+
+ final static void checkNotNull(Object object)
+ {
+ if ( object == null )
+ throw new TreeException("Null") ;
+ }
+
+ final void brokenTree(TTreeNode<T> node, String msg)
+ {
+ IndentedWriter.stderr.println();
+ output(IndentedWriter.stderr) ;
+ throw new TTreeException(msg+" : "+node.toString()) ;
+ }
+
+ @Override
+ public Iterator<T> iterator() { return iterator(null, null) ; }
+
+
+ @Override
+ public Iterator<T> iterator(T fromItem, T toItem)
+ { return TTreeIterator.iterator(this, fromItem, toItem) ; }
+
+ @Override
+ public long size()
+ { return count() ; }
+
+ // Size by actually counting the tree
+ @Override
+ public long count()
+ {
+ if ( root == null )
+ return 0 ;
+ return root.sizeDeep() ;
+ }
+
+ /** Collect all the elements in the TTree into a list and return the list. */
+ @Override
+ public List<T> elements()
+ {
+ List<T> x = new ArrayList<T>() ;
+ if ( root == null )
+ return x ;
+ // Avoids using an iterator but instead directly goes to the tree structure
+ // Can test the iterator code with this!
+ root.elements(x) ;
+ return x ;
+ }
+
+
+ @Override
+ public String toString() { return PrintUtils.toString(this) ; }
+
+ public void output()
+ {
+ output(stdout) ;
+ }
+
+ @Override
+ public void output(IndentedWriter out)
+ {
+ if ( root == null )
+ out.print("<empty>") ;
+ else
+ root.outputNested(out, true) ;
+ out.ensureStartOfLine() ;
+ out.flush();
+ }
+
+ // ---- Workers
+ private static void log(String msg)
+ {
+ if ( log.isDebugEnabled() )
+ log.debug(msg) ;
+ }
+
+ private static void log(String fmt, Object ...args)
+ {
+ if ( log.isDebugEnabled() )
+ log.debug(String.format(fmt, args)) ;
+ }
+
+ static void warn(String msg)
+ {
+ System.out.flush() ;
+ System.err.println(msg) ;
+ }
+
+
+ static void warn(String fmt, Object ...args)
+ { warn(String.format(fmt, args)) ; }
+
+ static void error(String msg)
+ { throw new TTreeException(msg) ; }
+
+ static void error(String fmt, Object ...args)
+ { error(String.format(fmt, args)) ; }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTreeException.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTreeException.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTreeException.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTreeException.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,27 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package structure.ttree;
+
+import structure.tree.TreeException;
+
+public class TTreeException extends TreeException
+{
+ public TTreeException(String msg) { super(msg) ; }
+ public TTreeException(String msg, Throwable th) { super(msg, th) ; }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTreeIterator.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTreeIterator.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTreeIterator.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTreeIterator.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,222 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package structure.ttree;
+
+import java.util.Iterator ;
+import java.util.NoSuchElementException ;
+
+import org.openjena.atlas.iterator.Iter ;
+import org.openjena.atlas.iterator.IteratorArray ;
+import org.openjena.atlas.lib.Alg ;
+
+public class TTreeIterator<T extends Comparable<? super T>> implements Iterator<T>
+{
+ public static <T extends Comparable<? super T>> Iterator<T> iterator(TTree<T> ttree, T min, T max)
+ {
+ if ( ttree.root == null )
+ return Iter.nullIterator() ;
+
+ return new TTreeIterator<T>(ttree, min, max) ;
+ }
+
+ boolean finished = false ;
+ Iterator<T> nodeIter ;
+ TTreeNode<T> node ;
+ T slot ;
+ T max ;
+
+ TTreeIterator(TTree<T> ttree, T min, T max)
+ {
+ this.max = max ;
+ this.finished = false ;
+ this.slot = null ;
+
+ if ( min != null )
+ {
+ node = TTree.findBoundingNode(ttree.root, min) ;
+ int idx = node.find(min) ;
+ // Does not short-cut min being larger than all elements in the tree.
+ if ( idx < 0 )
+ {
+ idx = Alg.decodeIndex(idx) ;
+ // idx may actually be out of the array - that means this node is "finished" with
+ if ( idx > node.nodeSize )
+ nodeIter = null ;
+ else
+ nodeIter = IteratorArray.create(node.elements, idx, node.nodeSize) ;
+ }
+ else
+ nodeIter = IteratorArray.create(node.elements, idx, node.nodeSize) ;
+ }
+ else
+ {
+ //min == null
+ node = ttree.root ;
+ while(node.left != null)
+ node = node.left ;
+ nodeIter = IteratorArray.create(node.elements, 0, node.nodeSize) ;
+ }
+
+ }
+
+ @Override
+ public boolean hasNext()
+ {
+ if ( finished )
+ return false ;
+
+ if ( slot != null )
+ return true ;
+
+ if ( nodeIter != null && nodeIter.hasNext() )
+ {
+ T item = nodeIter.next() ;
+ return testAndSetSlot(item) ;
+ }
+
+ // End of current node elements.
+ // Slot == null
+ // Have yielded the value for this tree node (and hence all relevant left subtree)
+
+ // Move the left-est node of the right subtree.
+ // If no right subtree
+ // Go up to parent.
+ // Check we were the left subtree of parent, not right.
+ // If no parent (this is the root), and we were left of parent,
+ // go down to min of left.
+
+ TTreeNode<T> nextNode = node.right ;
+
+ // There is a right
+ if ( nextNode != null )
+ nextNode = TTreeNode.getLeftDeep(nextNode) ;
+ else
+ //if ( nextNode == null )
+ {
+ // No right subtree from here.
+ // Walk up tree until we were not the right node of our parent.
+ TTreeNode<T> n2 = node ;
+ TTreeNode<T> n3 = n2.parent ;
+ while( n3 != null )
+ {
+ if ( n3.right != n2 ) // Same as n3.left == n2
+ {
+ n2 = n3 ;
+ break ;
+ }
+
+ n2 = n3 ;
+ n3 = n2.parent ;
+ }
+
+ if ( n3 == null )
+ {
+ finished = true ;
+ return false ;
+ }
+
+ // Now at the first node upwards when we're the left
+ // (i.e. less than the value)
+
+ nextNode = n2 ;
+ }
+
+ // On exit nextNode is the node of interest.
+ // Yield it's elements
+
+ node = nextNode ;
+ nodeIter = IteratorArray.create(node.elements, 0, node.nodeSize) ;
+ // And try again.
+ // Rafactor.
+ if ( ! nodeIter.hasNext() )
+ return false ;
+
+ T item = nodeIter.next() ;
+ return testAndSetSlot(item) ;
+ }
+
+ private boolean testAndSetSlot(T item)
+ {
+ if ( max != null )
+ {
+ int x = max.compareTo(item) ;
+ if ( x <= 0 )
+ {
+ // End
+ finished = true ;
+ slot = null ;
+ return false ;
+ }
+ }
+ slot = item ;
+ return true ;
+ }
+
+ @Override
+ public T next()
+ {
+ if ( ! hasNext())
+ throw new NoSuchElementException("TTreeIterator") ;
+ T rc = slot ;
+ slot = null ;
+ return rc ;
+ }
+
+ @Override
+ public void remove()
+ { throw new UnsupportedOperationException("TTreeIterator") ; }
+
+//
+//
+// // Iterator of zero
+// static <R extends Comparable<? super R>> Iter<R> nothing()
+// {
+// return Iter.nullIter() ;
+// }
+//
+// // Iterator of one
+// static <R extends Comparable<? super R>> Iter<R> singleton(R singleton)
+// {
+// return Iter.singletonIter(singleton) ;
+// }
+//
+// // Iterator of a pair of iterators concatenated
+// static <R extends Comparable<? super R>> Iter<R> concat(Iter<R> iter1, Iter<R> iter2)
+// {
+// return Iter.concat(iter1, iter2) ;
+// }
+//
+// // Calculate the iterator. For testing.
+// static <R extends Comparable<? super R>> List<R> calcIter(TTreeNode<R> node, R min, R max)
+// {
+// List<R> x = new ArrayList<R>() ;
+// if ( node == null )
+// return x ;
+// node.records(x) ; // Sorted.
+// if ( min != null )
+// while ( x.size() > 0 && x.get(0).compareTo(min) < 0 )
+// x.remove(0) ;
+//
+// if ( max != null )
+// while ( x.size() > 0 && x.get(x.size()-1).compareTo(max) >= 0 )
+// x.remove(x.size()-1) ;
+// return x ;
+// }
+//
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTreeNode.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTreeNode.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTreeNode.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTreeNode.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,492 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package structure.ttree;
+
+import static structure.ttree.TTree.Checking ;
+import static structure.ttree.TTree.error ;
+
+import java.util.List ;
+
+import migrate.lib.ArrayOps ;
+import org.openjena.atlas.io.IndentedWriter ;
+import org.openjena.atlas.io.PrintUtils ;
+import org.openjena.atlas.io.Printable ;
+import org.openjena.atlas.lib.Alg ;
+import org.openjena.atlas.lib.Lib ;
+
+final
+class TTreeNode<T extends Comparable<? super T>> implements Printable
+{
+ // Debug
+ private static int counter = 0 ;
+ // Make this static (or remove).
+ private int id ;
+
+ int height = TTree.InitialHeight ; // New nodes are always leaves.
+ TTreeNode<T> parent ;
+ TTreeNode<T> left ;
+ TTreeNode<T> right ;
+ // Need to record start and stop if want slicing.
+ // Or nulls at low end during insert into a full node.
+ int nodeSize ;
+ T elements[] ;
+
+ /** Create a new T-Tree node */
+ @SuppressWarnings("unchecked")
+ TTreeNode(TTreeNode<T>parent, int size)
+ {
+ id = (++counter) ;
+ this.elements = (T[])new Comparable[size] ;
+ this.nodeSize = 0 ;
+ this.height = TTree.InitialHeight ;
+ this.parent = parent ;
+ //Arrays.fill(elements, null) ;
+ }
+
+ void set(T[] elements, int els, TTreeNode<T> parent, TTreeNode<T> left, TTreeNode<T> right)
+ {
+ this.elements = elements ;
+ this.nodeSize = els ;
+ this.parent = parent ;
+ this.left = left ;
+ this.right = right ;
+ this.parent = parent ;
+ this.height = -1 ;
+ }
+
+ /** Insert a item into a node.
+ *
+ * @param item
+ * @return true if the node changed (replace a different element or insert the element)
+ */
+ boolean add(T item)
+ {
+ int idx = find(item) ;
+
+ if ( idx < 0 )
+ {
+ if ( elements.length == nodeSize )
+ error("Already full") ;
+ insertAt(Alg.decodeIndex(idx), item) ;
+ return true ;
+ }
+ else
+ {
+ T orig = elements[idx] ;
+ if ( Lib.equal(item, orig) )
+ return false ;
+ elements[idx] = item ;
+ return true ;
+ }
+ }
+
+ void insertAt(int idx,T item)
+ {
+ ArrayOps.insert(elements, idx, item) ;
+ nodeSize++ ;
+ }
+
+ T removeBottom()
+ {
+ if ( Checking && isEmpty() )
+ throw new TTreeException("node empty") ;
+ T item = elements[0] ;
+ ArrayOps.shiftDown(elements, 0, nodeSize) ;
+ nodeSize-- ;
+ return item ;
+ }
+
+ T removeTop()
+ {
+ if ( Checking && isEmpty() )
+ throw new TTreeException("node empty") ;
+ T item = elements[nodeSize-1] ;
+ if ( TTree.NullOut ) elements[nodeSize-1] = null ;
+ nodeSize-- ;
+ return item ;
+ }
+
+ /** Find an item - return the index in the array or -(index+1)
+ * encoding the insertion point.
+ *
+ * @param item
+ * @return encoded index.
+ */
+ int find(T item)
+ {
+ int x = Alg.binarySearch(elements, 0, nodeSize, item) ;
+ return x ;
+ }
+
+ /** Delete from this TTreeNode
+ *
+ * @param item
+ * @return true if a change to the node occurred
+ */
+ boolean delete(T item)
+ {
+ if ( elements.length == 0 )
+ error("Already empty") ;
+ int idx = find(item) ;
+ if ( idx < 0 )
+ return false ;
+ T item2 = ArrayOps.delete(elements, idx) ;
+ nodeSize-- ;
+ //if ( Checking ) check() ; // Can be invalid pending fixup
+ return true ;
+ }
+
+ boolean isFull() { return nodeSize == elements.length ; }
+ boolean isEmpty() { return nodeSize == 0 ; }
+
+ /** Both sides have nodes below them */
+ boolean isInternal() { return left != null && right != null ; }
+
+ /** One side or the other has a node, the other does not */
+ boolean isHalfLeaf() { return isLeftHalfLeaf() || isRightHalfLeaf() ; }
+
+ /** LeftHalfLeaf - no node below on the left, but there is one on the right */
+ boolean isLeftHalfLeaf() { return left == null && right != null ; }
+ /** LeftHalfLeaf - node below on the left, but not on the right */
+ boolean isRightHalfLeaf() { return left != null && right == null ; }
+
+ /** No nodes below this one, to left or to the right */
+ boolean isLeaf() { return left == null && right == null ; }
+
+ int nodeSize() { return nodeSize ; }
+
+ private static final String undef = "_" ;
+ /** Only makes sense when the "id" is being allocated for all nodes */
+ static <T extends Comparable<? super T>> String label(TTreeNode<T> n)
+ {
+ if ( n == null )
+ return undef ;
+ return Integer.toString(n.id) ;
+ }
+
+
+ T getMin()
+ {
+ if ( isEmpty() )
+ return null ;
+ return elements[0] ;
+ }
+
+ T getMax()
+ {
+ if ( isEmpty() )
+ return null ;
+ return elements[nodeSize-1] ;
+ }
+
+// T getGreatestLowerBound()
+// {
+// if ( isEmpty() )
+// return null ;
+// TTreeNode<T> node = this ;
+// if ( node.left != null )
+// node = getRightDeep(node.left) ;
+// return node.getMax() ;
+// }
+//
+// T getLeastUpperBound()
+// {
+// if ( isEmpty() )
+// return null ;
+// TTreeNode<T> node = this ;
+// if ( node.right != null )
+// node = getLeftDeep(node.right) ;
+// return node.getMin() ;
+// }
+
+ static <T extends Comparable<? super T>> TTreeNode<T> getLeftDeep(TTreeNode<T> node)
+ {
+ TTreeNode<T> node2 = node.left ;
+ while( node2 != null )
+ {
+ node = node2 ;
+ node2 = node2.left ;
+ }
+ return node ;
+ }
+
+ static <T extends Comparable<? super T>> TTreeNode<T> getRightDeep(TTreeNode<T> node)
+ {
+ TTreeNode<T> node2 = node.right ;
+ while( node2 != null )
+ {
+ node = node2 ;
+ node2 = node2.right ;
+ }
+ return node ;
+ }
+
+// TTreeNode<T> getParent()
+// {
+// return parent ;
+// }
+//
+// TTreeNode<T> getLeft()
+// {
+// return left ;
+// }
+//
+// TTreeNode<T> getRight()
+// {
+// return right ;
+// }
+
+ void elements(List<T> acc)
+ {
+ if ( left != null )
+ left.elements(acc) ;
+ for ( T item : elements )
+ {
+ if ( item == null ) break ;
+ acc.add(item) ;
+ }
+ if ( right != null )
+ right.elements(acc) ;
+ }
+
+ long sizeDeep()
+ {
+ long size = 0 ;
+ if ( left != null )
+ size += left.sizeDeep() ;
+ size += nodeSize ;
+ if ( right != null )
+ size += right.sizeDeep() ;
+ return size ;
+ }
+
+ // ---- Output
+ @Override
+ public void output(IndentedWriter out)
+ {
+ out.printf("id=%d parent=%s h=%d len=%d left=%s right=%s [",id, label(parent), height, nodeSize, label(left), label(right)) ;
+ for ( int i = 0 ; i < nodeSize ; i++ )
+ {
+ if ( i != 0 ) out.print(" ") ;
+ out.print(elements[i]) ;
+ }
+ out.print("]") ;
+ }
+
+ /** Print structured */
+ void outputNested(IndentedWriter out, boolean detailed)
+ {
+ out.print("(") ;
+ output(out) ;
+ if ( left == null && right == null )
+ {
+ out.println(")") ;
+ return ;
+ }
+ out.println() ;
+
+
+ out.incIndent() ;
+ if ( left != null )
+ {
+ out.ensureStartOfLine() ;
+ left.outputNested(out, detailed) ;
+ }
+ else
+ {
+ out.ensureStartOfLine() ;
+ out.println("()") ;
+ }
+ out.decIndent() ;
+
+ out.incIndent() ;
+ if ( right != null )
+ {
+ out.ensureStartOfLine() ;
+ right.outputNested(out, detailed) ;
+ }
+ else
+ {
+ out.ensureStartOfLine() ;
+ out.println("()") ;
+ }
+ out.decIndent() ;
+ out.print(")") ;
+ }
+
+ @Override
+ public String toString() { return PrintUtils.toString(this) ; }
+
+ // ---- Check
+
+ final void checkDeep(TTree<T> ttree)
+ {
+ if ( ! Checking )
+ return ;
+ check(ttree) ;
+ if ( left != null )
+ left.checkDeep(ttree);
+ if ( right != null )
+ right.checkDeep(ttree);
+ }
+
+ final void check(TTree<T> ttree)
+ {
+ if ( ! Checking )
+ return ;
+ if ( nodeSize > elements.length )
+ error("Node size %d, Array size: %d : %s", nodeSize, elements.length, this) ;
+
+ // -- Structure checks
+ if ( parent != null )
+ {
+ if ( parent.left == this )
+ {
+ if ( parent.left.id != this.id )
+ error("Parent.left does not point to this node by id") ;
+ }
+ else if ( parent.right == this )
+ {
+ if ( parent.right.id != this.id )
+ error("Parent.right does not point to this node by id") ;
+ }
+ else
+ error("Parent does not point to this node") ;
+ }
+
+ if ( isInternal() || isHalfLeaf() )
+ {
+ if ( ttree != null )
+ {
+ // Internal nodes are always full
+ // Half-leaves are always full (by modified half-leaf rule on deletion)
+ if ( nodeSize < ttree.NodeSizeMin )
+ error("Internal node too small") ;
+ }
+ }
+ else if ( isLeftHalfLeaf() )
+ {
+ if ( ! right.isLeaf() )
+ error("LeftHalfLeaf has no leaf to the right") ;
+ }
+ else if ( isRightHalfLeaf() )
+ {
+ if ( ! left.isLeaf() )
+ error("RightHalfLeaf has no leaf to the left") ;
+ }
+ else if ( isLeaf())
+ {
+ if ( parent != null && nodeSize <= 0 )
+ error("Zero length node") ;
+ }
+ else
+ error("Node has no leaf status") ;
+
+ // Children checks
+ if ( left != null && left.parent != this )
+ error("Left child does not point back to this node") ;
+
+ if ( left != null && left.parent.id != this.id )
+ error("Left child does not point back to this node by id") ;
+
+ if ( right != null && right.parent != this )
+ error("Right child does not point back to this node") ;
+
+ if ( right != null && right.parent.id != this.id )
+ error("Right child does not point back to this node by id") ;
+
+ // -- Ordering checks
+ // Order within this node
+ T prev = null ;
+ for ( int i = 0 ; i < nodeSize ; i++ )
+ {
+ if ( elements[i] == null )
+ error("Null array entry idx=%d : %s", i, this) ;
+ if ( prev != null )
+ {
+ if ( prev.compareTo(elements[i]) >= 0 )
+ error("Unordered: idx=%d : %s %s : %s", i, prev, elements[i], this) ;
+ }
+ prev = elements[i] ;
+ }
+ // Check upper area is cleared.
+ if ( TTree.NullOut )
+ {
+ for ( int i = nodeSize ; i < elements.length ; i++ )
+ {
+ if ( elements[i] != null )
+ error("Not null array entry idx=%d : %s", i, this) ;
+ }
+ }
+
+ if ( nodeSize > 0 )
+ {
+ // Check ordering from left and right.
+ if ( left != null && left.nodeSize>0 && left.getMax().compareTo(getMin()) > 0 ) // If this less than left.
+ error("Out of order (left): [id=%s] %s/%s", label(left), left.getMax(), getMin()) ;
+
+ if ( left != null && left.nodeSize>0 && left.getMax().compareTo(getMin()) == 0 ) // Duplicate.
+ error("Duplicate (left): [id=%s] %s/%s", label(left), left.getMax(), getMin()) ;
+
+ if ( right != null && right.nodeSize>0 && right.getMin().compareTo(getMax()) < 0 ) // If this more than right
+ error("Out of order (right): [id=%s] %s/%s", label(right), right.getMin(), getMax()) ;
+
+ if ( right != null && right.nodeSize>0 && right.getMin().compareTo(getMax()) == 0 ) // Duplicate.
+ error("Duplicate (right): [id=%s] %s/%s", label(right), right.getMin(), getMin()) ;
+ }
+
+ // -- Balance checks
+ int x = TTree.balance(this) ;
+ if ( x < -1 || x > 1 )
+ error("Out of balance %d: %s", x, this) ;
+
+ // -- Height checks
+
+ if ( left != null && height < left.height )
+ error("Height error (left) [%d,%d]", height, left.height) ;
+
+ if ( right != null && height < right.height )
+ error("Height error (right) [%d,%d]", height, right.height) ;
+
+ if ( left == null && right != null )
+ {
+ if ( height != right.height+1 )
+ error("Bad height (right) - not %d", right.height+1) ;
+ }
+ else if ( left != null && right == null )
+ {
+ if ( height != left.height+1 )
+ error("Bad height (left) - not %d", left.height+1) ;
+
+ }
+ else if ( left != null && right != null )
+ {
+ if ( height < left.height || height < right.height )
+ {}
+
+ if ( height != left.height+1 && height != right.height+1 )
+ error("Bad height (%d) - not %d or %d", id, left.height+1, right.height+1) ;
+ }
+ else
+ {
+ if ( height != TTree.InitialHeight )
+ error("Leaf node height not %d", TTree.InitialHeight) ;
+ }
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/migrate/lib/TestArrayOps.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/migrate/lib/TestArrayOps.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/migrate/lib/TestArrayOps.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/migrate/lib/TestArrayOps.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,303 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package migrate.lib;
+
+import java.util.Iterator;
+
+import migrate.lib.ArrayOps;
+import org.junit.BeforeClass;
+import org.junit.Test;
+import org.openjena.atlas.junit.BaseTest ;
+
+public class TestArrayOps extends BaseTest
+{
+ @BeforeClass public static void beforeClass()
+ {
+ //ArrayOps.NullOut = true ;
+ ArrayOps.Checking = true ;
+ }
+
+ // ---- Clear
+ @Test public void clear1()
+ {
+ String[] array = {"a", "b", "c", null, null } ;
+ String[] array2 = {null, "b", "c", null, null } ;
+ ArrayOps.clear(array, 0, 1 ) ;
+ assertArrayEquals(array2,array) ;
+ }
+
+ @Test public void clear2()
+ {
+ String[] array = {"a", "b", "c", "d", null } ;
+ String[] array2 = {"a", null, null, "d", null } ;
+ ArrayOps.clear(array, 1, 2 ) ;
+ assertArrayEquals(array2,array) ;
+ }
+
+ @Test public void clear3()
+ {
+ String[] array = {"a", "b", "c"} ;
+ String[] array2 = {null, null, null} ;
+ ArrayOps.clear(array) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ // ---- Shift Up
+ // Should shift extends the array? Yes.
+ @Test public void shift_up_1()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {null, "a", "b", "c", "e"} ; // Extends to length 4.
+ ArrayOps.shiftUp(array, 0, 3) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test public void shift_up_2()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"a", "b", "c", null, "d"} ;
+ ArrayOps.shiftUp(array, 3, array.length-1) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test public void shift_up_3()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"a", "b", "c", "d", null} ;
+ ArrayOps.shiftUp(array, 4, 5) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test public void shift_up_4()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"a", "b", "c", null, "d" } ;
+ // Shift at top
+ ArrayOps.shiftUp(array, 3, 4) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test public void shift_up_5()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"a", null, null, "b", "c"} ;
+ ArrayOps.shiftUpN(array, 1, 2, 5) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test public void shift_up_6()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {null, null, null, null, null} ;
+ ArrayOps.shiftUpN(array, 0, 5, 3) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test(expected=ArrayOps.ArrayException.class)
+ public void shift_up_7()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {null, null, null, null, null} ;
+ ArrayOps.shiftUpN(array, 0, 6, 3) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ // ---- Shift Down
+
+ @Test public void shift_down_1()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"b", "c", null, "d", "e"} ;
+ ArrayOps.shiftDown(array, 0, 3) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test public void shift_down_2()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"a", "c", null, "d", "e"} ;
+ ArrayOps.shiftDown(array, 1, 3) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test public void shift_down_3()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"a", "b", null, "d", "e"} ;
+ ArrayOps.shiftDown(array, 2, 3) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test(expected=ArrayOps.ArrayException.class)
+ public void shift_down_4()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {} ;
+ ArrayOps.shiftDown(array, 3, 3) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test public void shift_down_5()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"a", "b", "c", "d", null } ;
+ ArrayOps.shiftDown(array, 4, 5) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test public void shift_down_6()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"a", "b", "c", null, null } ;
+ ArrayOps.shiftDownN(array, 3, 2, 5) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test(expected=ArrayOps.ArrayException.class)
+ public void shift_down_7()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {} ;
+ ArrayOps.shiftDownN(array, 4, 2, 5) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ // ---- Insert
+
+ @Test public void insert1()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"z", "a", "b", "c", "e"} ;
+ ArrayOps.insert(array, 0, "z", 3) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test public void insert2()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"a", "z", "b", "c", "e" } ;
+ ArrayOps.insert(array, 1, "z", 3) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test public void insert3()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"a", "b", "z", "c", "e" } ;
+ ArrayOps.insert(array, 2, "z", 3) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test public void insert4()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"a", "b", "c", "d", "z" } ;
+ ArrayOps.insert(array, 4, "z", 4) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test public void insert5()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"a", "b", "c", "d", "z" } ;
+ ArrayOps.insert(array, 4, "z", 5) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test public void insert7()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"z", "a", "b", "c", "d"} ;
+ ArrayOps.insert(array, 0, "z", 5) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test(expected=ArrayOps.ArrayException.class)
+ public void insert8()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {} ;
+ ArrayOps.insert(array, 5, "z", 5) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ @Test(expected=ArrayOps.ArrayException.class)
+ public void insert9()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {} ;
+ ArrayOps.insert(array, 5, "z", 4) ;
+ assertArrayEquals(array2, array) ;
+ }
+
+ // ---- Delete
+
+ @Test public void delete1()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"b", "c", null, "d", "e"} ;
+ String x = ArrayOps.delete(array, 0, 3) ;
+ assertArrayEquals(array2, array) ;
+ assertEquals("a", x) ;
+ }
+
+ @Test public void delete2()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"a", "c", null, "d", "e"} ;
+ String x = ArrayOps.delete(array, 1, 3) ;
+ assertArrayEquals(array2, array) ;
+ assertEquals("b", x) ;
+ }
+
+ @Test public void delete3()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"a", "b", null, "d", "e"} ;
+ String x = ArrayOps.delete(array, 2, 3) ;
+ assertArrayEquals(array2, array) ;
+ assertEquals("c", x) ;
+ }
+
+ @Test public void delete4()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"a", "b", "d", "e", null} ;
+ String x = ArrayOps.delete(array, 2, 5) ;
+ assertArrayEquals(array2, array) ;
+ assertEquals("c", x) ;
+ }
+
+ @Test public void delete5()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ String[] array2 = {"a", "b", "c", "d", null} ;
+ String x = ArrayOps.delete(array, 4, 5) ;
+ assertArrayEquals(array2, array) ;
+ assertEquals("e", x) ;
+ }
+
+ @Test public void iterate1()
+ {
+ String[] array = {"a", "b", "c", "d", "e" } ;
+ Iterator<String> iter = ArrayOps.iterator(array) ;
+ for ( int i = 0 ; iter.hasNext() ; i++ )
+ assertEquals(array[i], iter.next()) ;
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/migrate/lib/TestByteArray.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/migrate/lib/TestByteArray.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/migrate/lib/TestByteArray.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/migrate/lib/TestByteArray.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,47 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package migrate.lib;
+
+import org.junit.Test ;
+import org.openjena.atlas.junit.BaseTest ;
+
+public class TestByteArray extends BaseTest
+{
+ @Test public void bytearray_01()
+ {
+ ByteArray b = new ByteArray() ;
+ compare(b, new byte[]{}) ;
+ }
+
+ @Test public void bytearray_02()
+ {
+ ByteArray b = new ByteArray() ;
+ b.add((byte)1) ;
+ compare(b, new byte[]{1}) ;
+ }
+
+
+ private static void compare(ByteArray bytes, byte[] contents)
+ {
+ assertEquals(bytes.length(), contents.length) ;
+ for ( int i = 0 ; i < contents.length ; i++ )
+ assertEquals(contents[i], bytes.get(i)) ;
+
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/migrate/lib/TestVarInteger.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/migrate/lib/TestVarInteger.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/migrate/lib/TestVarInteger.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/migrate/lib/TestVarInteger.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,163 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package migrate.lib;
+
+import java.nio.ByteBuffer ;
+
+import org.junit.Test ;
+import org.openjena.atlas.junit.BaseTest ;
+import org.openjena.atlas.lib.ByteBufferLib ;
+
+public class TestVarInteger extends BaseTest
+{
+ @Test public void varint_01()
+ {
+ VarInteger vint = VarInteger.valueOf(0) ;
+ assertEquals(1, vint.length()) ;
+ assertEquals((byte)0, vint.bytes()[0]) ;
+ assertEquals(0L, vint.value()) ;
+ }
+
+ @Test public void varint_02()
+ {
+ VarInteger vint = VarInteger.valueOf(1) ;
+ assertEquals(1, vint.length()) ;
+ assertEquals((byte)1, vint.bytes()[0]) ;
+ assertEquals(1L, vint.value()) ;
+ }
+
+ @Test public void varint_03()
+ {
+ VarInteger vint = VarInteger.valueOf(127) ;
+ assertEquals(1, vint.length()) ;
+ assertEquals((byte)0x7F, vint.bytes()[0]) ;
+ assertEquals(127L, vint.value()) ;
+ }
+
+ @Test public void varint_04()
+ {
+ VarInteger vint = VarInteger.valueOf(128) ;
+ assertEquals(2, vint.length()) ;
+ assertEquals((byte)0x80, vint.bytes()[0]) ;
+ assertEquals((byte)0x01, vint.bytes()[1]) ;
+ assertEquals(128L, vint.value()) ;
+ }
+
+ @Test public void varint_05()
+ {
+ VarInteger vint = VarInteger.valueOf(129) ;
+ assertEquals(2, vint.length()) ;
+ assertEquals((byte)0x81, vint.bytes()[0]) ;
+ assertEquals((byte)0x01, vint.bytes()[1]) ;
+ assertEquals(129L, vint.value()) ;
+ }
+
+ @Test public void varint_10()
+ {
+ VarInteger vint = VarInteger.valueOf(1L<<45) ;
+ //assertEquals(2, vint.length()) ;
+ assertEquals(1L<<45, vint.value()) ;
+ }
+
+ // General hammering.
+ @Test public void varint_N()
+ {
+ for ( long x = 0 ; x < (1L<<17) ; x++ )
+ {
+ VarInteger vint = VarInteger.valueOf(x) ;
+ assertEquals(x, vint.value()) ;
+ }
+ }
+
+ @Test public void varint_eq_1()
+ {
+ VarInteger x = VarInteger.valueOf(0) ;
+ VarInteger x0 = VarInteger.valueOf(0) ;
+ VarInteger x1 = VarInteger.valueOf(1) ;
+ assertEquals(x.hashCode(), x0.hashCode()) ;
+ assertNotEquals(x.hashCode(), x1.hashCode()) ;
+ assertEquals(x, x0) ;
+ assertNotEquals(x, x1) ;
+ }
+
+ @Test public void varint_eq_2()
+ {
+ VarInteger x = VarInteger.valueOf(1) ;
+ VarInteger x0 = VarInteger.valueOf(0) ;
+ VarInteger x1 = VarInteger.valueOf(1) ;
+ assertEquals(x.hashCode(), x1.hashCode()) ;
+ assertNotEquals(x.hashCode(), x0.hashCode()) ;
+ assertEquals(x, x1) ;
+ assertNotEquals(x, x0) ;
+ }
+
+ private static void eq(long value)
+ {
+ VarInteger x0 = VarInteger.valueOf(value) ;
+ VarInteger x1 = VarInteger.valueOf(value) ;
+ assertEquals(x0.hashCode(), x1.hashCode()) ;
+ assertEquals(x0, x1) ;
+ }
+
+ @Test public void varint_eq_3() { eq(127) ; }
+ @Test public void varint_eq_4() { eq(128) ; }
+ @Test public void varint_eq_5() { eq(129) ; }
+
+ @Test public void varint_bb_1()
+ {
+ ByteBuffer bb = ByteBuffer.allocate(8) ;
+ ByteBufferLib.fill(bb, (byte)0) ;
+ VarInteger.encode(bb, 1, 2L<<14) ;
+ assertEquals(0, bb.get(0)) ;
+ }
+
+ @Test public void varint_extract_1()
+ {
+ VarInteger x0 = VarInteger.valueOf(113) ;
+ VarInteger x1 = VarInteger.make(x0.bytes) ;
+ assertEquals(x0, x1) ;
+ }
+
+ @Test public void varint_extract_2()
+ {
+ VarInteger x0 = VarInteger.valueOf(113) ;
+ ByteBuffer bb = ByteBuffer.wrap(x0.bytes()) ;
+ VarInteger x1 = VarInteger.make(bb,0) ;
+ assertEquals(x0, x1) ;
+ }
+
+ @Test public void varint_extract_3()
+ {
+ VarInteger x0 = VarInteger.valueOf(11377) ;
+ ByteBuffer bb = ByteBuffer.wrap(x0.bytes()) ;
+ VarInteger x1 = VarInteger.make(bb,0) ;
+ assertEquals(x0, x1) ;
+ }
+
+ @Test public void varint_length_1()
+ {
+ assertEquals(1, VarInteger.lengthOf(0)) ;
+ assertEquals(1, VarInteger.lengthOf(1)) ;
+ assertEquals(1, VarInteger.lengthOf(127)) ;
+ assertEquals(2, VarInteger.lengthOf(128)) ;
+ assertEquals(2, VarInteger.lengthOf(1L<<14-1)) ;
+ assertEquals(3, VarInteger.lengthOf(1L<<14)) ;
+ assertEquals(8, VarInteger.lengthOf(1L<<56-1)) ;
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/OrderedSetTest.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/OrderedSetTest.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/OrderedSetTest.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/OrderedSetTest.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,45 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package structure;
+
+import static org.openjena.atlas.lib.RandomLib.random;
+import org.openjena.atlas.test.ExecGenerator;
+
+class OrderedSetTest implements ExecGenerator
+{
+ int maxNumKeys ;
+ int maxValue ;
+ OrderedSetTestFactory factory ;
+
+ OrderedSetTest(OrderedSetTestFactory factory, int maxValue, int maxNumKeys)
+ {
+ if ( maxValue <= maxNumKeys )
+ throw new IllegalArgumentException("SortedIndexTest: Max value less than number of keys") ;
+ this.maxValue = maxValue ;
+ this.maxNumKeys = maxNumKeys ;
+ this.factory = factory ;
+ }
+
+ @Override
+ public void executeOneTest()
+ {
+ int numKeys = random.nextInt(maxNumKeys)+1 ;
+ OrderedSetTestLib.randTest(factory, maxValue, numKeys) ;
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/OrderedSetTestBase.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/OrderedSetTestBase.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/OrderedSetTestBase.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/OrderedSetTestBase.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,440 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package structure;
+
+import java.util.Iterator;
+
+import org.junit.Test;
+import org.openjena.atlas.junit.BaseTest ;
+
+public abstract class OrderedSetTestBase extends BaseTest
+{
+ protected abstract OrderedSet<Integer> create() ;
+
+ protected OrderedSet<Integer> create(int[] items)
+ {
+ OrderedSet<Integer> index = create() ;
+ for ( int i : items )
+ index.add(i) ;
+ return index ;
+
+ }
+
+ @Test public void ins_00()
+ {
+ int[] r = { } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ }
+
+ @Test public void ins_01()
+ {
+ int[] r = { 1 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ }
+
+ @Test public void ins_02()
+ {
+ int[] r = { 1, 2 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ }
+
+ @Test public void ins_03()
+ {
+ int[] r = { 2 , 1 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ }
+
+ @Test public void ins_04()
+ {
+ int[] r = { 1, 2, 3, 4, 5 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ }
+
+ @Test public void ins_05()
+ {
+ int[] r = { 5, 4, 3, 2, 1 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ }
+
+ @Test public void ins_06()
+ {
+ int[] r = { 1, 3, 5, 7, 2, 4, 6 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ }
+
+ // Causes a pivotLeftRight (RightLeft) in AVL
+ @Test public void ins_07()
+ {
+ int[] r = { 1, 6, 3, 4, 5, 2, 7, 0 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ }
+
+ @Test public void ins_08()
+ {
+ int[] r = { 1, 3, 2 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ }
+
+ @Test public void ins_09()
+ {
+ int[] r = { 3, 1, 2 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ }
+
+ @Test public void ins_10()
+ {
+ int[] r = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ }
+
+ @Test public void ins_11()
+ {
+ int[] r = { 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ }
+
+ @Test public void ins_12()
+ {
+ int[] r = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ }
+
+ @Test public void ins_13()
+ {
+ int[] r = { 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ }
+
+ @Test public void ins_14()
+ {
+ int[] r = { 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 19, 17, 15, 13, 11, 9, 7, 5, 3, 1 };
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ }
+
+ @Test public void ins_15()
+ {
+ int[] r = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 19, 17, 15, 13, 11, 9, 7, 5, 3, 1 };
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ }
+
+ @Test public void ins_16()
+ {
+ int[] r = { 1, 4, 5, 2, 3, 6, 11, 14, 15, 22, 23, 26 };
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ assertTrue(index.add(7)) ;
+ assertFalse(index.add(7)) ;
+
+ for ( int i : r )
+ assertFalse(index.add(i)) ;
+ }
+
+
+ @Test public void del_01_1()
+ {
+ int[] r = { 1 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ OrderedSetTestLib.delete(index, r) ;
+ OrderedSetTestLib.size(index, 0) ;
+ }
+
+ @Test public void del_01_2()
+ {
+ int[] r = { 1 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ OrderedSetTestLib.delete(index, 2) ;
+ OrderedSetTestLib.check(index, r) ;
+ }
+
+
+ @Test public void del_02_1()
+ {
+ int[] r1 = { 1, 2 } ;
+ int[] r2 = { 1, 2 } ;
+ OrderedSet<Integer> index = create(r1) ;
+ OrderedSetTestLib.check(index, r1) ;
+ OrderedSetTestLib.delete(index, r2) ;
+ OrderedSetTestLib.size(index, 0) ;
+ }
+
+ @Test public void del_02_2()
+ {
+ int[] r1 = { 1, 2 } ;
+ int[] r2 = { 2, 1 } ;
+ OrderedSet<Integer> index = create(r1) ;
+ OrderedSetTestLib.check(index, r1) ;
+ OrderedSetTestLib.delete(index, r2) ;
+ OrderedSetTestLib.size(index, 0) ;
+ }
+
+
+ @Test public void del_03_1()
+ {
+ int[] r1 = { 2 , 1 } ;
+ int[] r2 = { 1 , 2 } ;
+ OrderedSet<Integer> index = create(r1) ;
+ OrderedSetTestLib.check(index, r1) ;
+ OrderedSetTestLib.delete(index, r2) ;
+ OrderedSetTestLib.size(index, 0) ;
+ }
+
+ @Test public void del_03_2()
+ {
+ int[] r1 = { 2 , 1 } ;
+ int[] r2 = { 2 , 1 } ;
+ OrderedSet<Integer> index = create(r1) ;
+ OrderedSetTestLib.check(index, r1) ;
+ OrderedSetTestLib.delete(index, r2) ;
+ OrderedSetTestLib.size(index, 0) ;
+ }
+
+ @Test public void del_03_3()
+ {
+ int[] r1 = { 2, 3, 4, 1 } ;
+ int[] r2 = { 3 } ;
+ OrderedSet<Integer> index = create(r1) ;
+ OrderedSetTestLib.check(index, r1) ;
+ OrderedSetTestLib.delete(index, r2) ;
+ OrderedSetTestLib.check(index, 1, 2, 4) ;
+ }
+
+ @Test public void del_03_4()
+ {
+ int[] r1 = { 3, 2, 1, 4 } ;
+ int[] r2 = { 2 } ;
+ OrderedSet<Integer> index = create(r1) ;
+ OrderedSetTestLib.check(index, r1) ;
+ OrderedSetTestLib.delete(index, r2) ;
+ OrderedSetTestLib.check(index, 1, 3, 4) ;
+ }
+
+ @Test public void del_04_1()
+ {
+ int[] r1 = { 1, 2, 3, 4, 5 } ;
+ int[] r2 = { 1, 2, 3, 4, 5 } ;
+ OrderedSet<Integer> index = create(r1) ;
+ OrderedSetTestLib.check(index, r1) ;
+ OrderedSetTestLib.delete(index, r2) ;
+ OrderedSetTestLib.size(index, 0) ;
+ }
+
+ @Test public void del_04_2()
+ {
+ int[] r1 = { 1, 2, 3, 4, 5 } ;
+ int[] r2 = { 5, 4, 3, 2, 1 } ;
+ OrderedSet<Integer> index = create(r1) ;
+ OrderedSetTestLib.check(index, r1) ;
+ OrderedSetTestLib.delete(index, r2) ;
+ OrderedSetTestLib.size(index, 0) ;
+ }
+
+ @Test public void del_04_3()
+ {
+ int[] r1 = { 1, 2, 3, 4, 5 } ;
+ int[] r2 = { 1, 3, 5 } ;
+ OrderedSet<Integer> index = create(r1) ;
+ OrderedSetTestLib.check(index, r1) ;
+ OrderedSetTestLib.delete(index, r2) ;
+ OrderedSetTestLib.check(index, 2, 4) ;
+ }
+
+ @Test public void del_04_4()
+ {
+ int[] r1 = { 1, 2, 3, 4, 5 } ;
+ int[] r2 = { 4, 2 } ;
+ OrderedSet<Integer> index = create(r1) ;
+ OrderedSetTestLib.check(index, r1) ;
+ OrderedSetTestLib.delete(index, r2) ;
+ OrderedSetTestLib.check(index, 1,3,5) ;
+ }
+
+ @Test public void del_04_5()
+ {
+ int[] r1 = { 1, 2, 3, 4, 5 } ;
+ int[] r2 = { 4, 2 } ;
+ OrderedSet<Integer> index = create(r1) ;
+ OrderedSetTestLib.check(index, r1) ;
+ OrderedSetTestLib.delete(index, r2) ;
+ OrderedSetTestLib.check(index, 1,3,5) ;
+ OrderedSetTestLib.delete(index, 9) ;
+ OrderedSetTestLib.check(index, 1,3,5) ;
+ }
+
+ @Test public void del_05_1()
+ {
+ int[] r1 = { 5, 4, 3, 2, 1 } ;
+ int[] r2 = { 1, 2, 3, 4, 5 } ;
+ OrderedSet<Integer> index = create(r1) ;
+ OrderedSetTestLib.check(index, r1) ;
+ OrderedSetTestLib.delete(index, r2) ;
+ OrderedSetTestLib.size(index, 0) ;
+ }
+
+ @Test public void del_05_2()
+ {
+ int[] r1 = { 5, 4, 3, 2, 1 } ;
+ int[] r2 = { 1, 3, 5 } ;
+ OrderedSet<Integer> index = create(r1) ;
+ OrderedSetTestLib.check(index, r1) ;
+ OrderedSetTestLib.delete(index, r2) ;
+ OrderedSetTestLib.check(index, 2,4) ;
+ }
+
+ @Test public void del_06_1()
+ {
+ int[] r1 = { 1, 3, 5, 7, 2, 4, 6 } ;
+ int[] r2 = { 1, 3, 5, 7, 2, 4, 6 } ;
+ OrderedSet<Integer> index = create(r1) ;
+ OrderedSetTestLib.check(index, r1) ;
+ OrderedSetTestLib.delete(index, r2) ;
+ OrderedSetTestLib.size(index, 0) ;
+ }
+
+ @Test public void del_07()
+ {
+ int[] r1 = { 1, 6, 3, 4, 5, 2, 7, 0 } ;
+ int[] r2 = { 1, 6, 3, 4, 5, 2, 7, 0 } ;
+ OrderedSet<Integer> index = create(r1) ;
+ OrderedSetTestLib.check(index, r1) ;
+ OrderedSetTestLib.delete(index, r2) ;
+ OrderedSetTestLib.size(index, 0) ;
+ }
+
+ @Test public void del_08()
+ {
+ int[] r1 = { 1, 6, 3, 4, 5, 2, 7, 0 } ;
+ int[] r2 = { 4, 6, 3, 5 } ;
+ int[] r3 = { 1, 7, 0, 2 } ;
+ OrderedSet<Integer> index = create(r1) ;
+ OrderedSetTestLib.check(index, r1) ;
+ OrderedSetTestLib.delete(index, r2) ;
+ OrderedSetTestLib.check(index, r3) ;
+ OrderedSetTestLib.size(index, 4) ;
+ }
+
+
+ @Test public void del_10()
+ {
+ int[] r = { 1, 16, 3, 14, 5, 2, 37, 11, 6, 23, 4, 25, 12, 7, 40 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ // Some things not in the ordered set
+ assertFalse(index.remove(99)) ;
+ assertFalse(index.remove(0)) ;
+ assertFalse(index.remove(20)) ;
+
+ for ( int i : r )
+ assertTrue("remove i="+i,index.remove(i)) ;
+ }
+
+ @Test public void iter_01()
+ {
+ int[] r = { 3, 1, 2 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ Iterator<Integer> iter = index.iterator() ;
+ OrderedSetTestLib.check(iter, 1,2,3) ;
+ }
+
+ @Test public void iter_02()
+ {
+ int[] r = { 1, 2, 3, 4 , 5 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ Iterator<Integer> iter = index.iterator() ;
+ OrderedSetTestLib.check(iter, 1,2,3,4,5) ;
+ }
+
+ @Test public void iter_03()
+ {
+ int[] r = { 10, 8, 6, 4, 2 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ Iterator<Integer> iter = index.iterator(2,4) ;
+ OrderedSetTestLib.check(iter, 2) ;
+
+ iter = index.iterator(-99,4) ;
+ OrderedSetTestLib.check(iter, 2) ;
+
+ }
+
+ @Test public void iter_04()
+ {
+ int[] r = { 2, 4, 6, 8, 10 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ Iterator<Integer> iter = index.iterator(-99,4) ;
+ OrderedSetTestLib.check(iter, 2) ;
+ }
+
+ @Test public void iter_05()
+ {
+ int[] r = { 2, 4, 6, 8, 10 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ Iterator<Integer> iter = index.iterator(6,99) ;
+ OrderedSetTestLib.check(iter, 6,8,10) ;
+ }
+
+ @Test public void iter_06()
+ {
+ int[] r = { 2, 4, 6, 8, 10 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ Iterator<Integer> iter = index.iterator(null,null) ;
+ OrderedSetTestLib.check(iter, r) ;
+ }
+
+ @Test public void iter_07()
+ {
+ int[] r = { 2 } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ Iterator<Integer> iter = index.iterator(null,null) ;
+ OrderedSetTestLib.check(iter, r) ;
+ }
+
+ @Test public void iter_08()
+ {
+ int[] r = { } ;
+ OrderedSet<Integer> index = create(r) ;
+ OrderedSetTestLib.check(index, r) ;
+ Iterator<Integer> iter = index.iterator(null,null) ;
+ OrderedSetTestLib.check(iter, r) ;
+ }
+
+}