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/11/07 14:36:34 UTC
svn commit: r1198733 [7/13] - in /incubator/jena/Scratch/AFS/Dev/trunk:
src-archive/riot/comms/ src-archive/riot/comms/client/
src-archive/riot/comms/server0/ src-archive/riot/comms/server1/nio/
src-archive/riot/comms/server1/socket/ src-archive/riot/c...
Modified: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/tree/TreeException.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/tree/TreeException.java?rev=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/tree/TreeException.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/tree/TreeException.java Mon Nov 7 13:36:30 2011
@@ -1,4 +1,4 @@
-/**
+/*
* 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
@@ -16,27 +16,27 @@
* limitations under the License.
*/
-package structure.tree;
-
-public class TreeException extends RuntimeException
-{
- public TreeException()
- {
- super() ;
- }
-
- public TreeException(String message)
- {
- super(message) ;
- }
-
- public TreeException(String message, Throwable cause)
- {
- super(message, cause) ;
- }
-
- public TreeException(Throwable cause)
- {
- super(cause) ;
- }
+package structure.tree;
+
+public class TreeException extends RuntimeException
+{
+ public TreeException()
+ {
+ super() ;
+ }
+
+ public TreeException(String message)
+ {
+ super(message) ;
+ }
+
+ public TreeException(String message, Throwable cause)
+ {
+ super(message, cause) ;
+ }
+
+ public TreeException(Throwable cause)
+ {
+ super(cause) ;
+ }
}
Modified: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/tree/TreeNode.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/tree/TreeNode.java?rev=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/tree/TreeNode.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/tree/TreeNode.java Mon Nov 7 13:36:30 2011
@@ -1,4 +1,4 @@
-/**
+/*
* 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
@@ -16,257 +16,257 @@
* limitations under the License.
*/
-package structure.tree;
-
-import java.util.ArrayList ;
-import java.util.Iterator ;
-import java.util.List ;
-
-import org.openjena.atlas.io.IndentedWriter ;
-import org.openjena.atlas.io.PrintUtils ;
-import org.openjena.atlas.io.Printable ;
-
-
-/** Simple binary tree nodes, including operations that apply to all trees */
-
-public class TreeNode<R extends Comparable<R>> implements Printable
-{
- private TreeNode<R> left ;
- private TreeNode<R> right ;
- private R record ;
-
- public TreeNode(R record)
- {
- this.record = record ;
- }
-
- public TreeNode(R record, TreeNode<R> left, TreeNode<R> right)
- {
- this(record) ;
- this.left = left ;
- this.right = right ;
- }
-
- public R insert(R newRecord)
- { return insert(newRecord, true) ; }
-
- // Unbalanced insert - return the record if the record already present, else null if new.
- public R insert(R newRecord, boolean duplicates)
- {
- int x = this.record.compareTo(newRecord) ;
-
- if ( x > 0 )
- {
- if ( left == null )
- {
- left = new TreeNode<R>(newRecord) ;
- return null ;
- }
- return left.insert(newRecord, duplicates) ;
- }
-
- if ( x == 0 && ! duplicates )
- return this.record ;
-
- if ( right == null )
- {
- right = new TreeNode<R>(newRecord) ;
- return null ;
- }
- return right.insert(newRecord, duplicates) ;
- }
-
- // Naming: rotateRight means move the left child up to the root and the root to the right
- // The left is the pivot
- // == shift right
- // == clockwise
- // This is the wikipedia naming but that does not extend to the double rotations.
- // Different books have different namings, based on the location of the pivot (which would be a left rotate)
- // But when we talk about double rotations, the pivotLeft terminolgy works better.
- // pivotLeft (= case left left) , pivotLeftRight,
-
-
- // (K1 (K2 A B) C) ==> (K2 A (K1 B C))
- final public void rotateRight() { pivotLeft() ; }
- final public void pivotLeft()
- {
- // Validity checking?
- checkNotNull(left) ;
-
- R k1 = record ;
- R k2 = left.record ;
- TreeNode<R> a = left.left ;
- TreeNode<R> b = left.right ;
- TreeNode<R> c = right ;
-
- // Or reuse left.
- // TreeNode t = new TreeNode(k1, b, c) ;
- TreeNode<R> t = left ; t.record = k1 ; t.left = b ; t.right = c ;
-
- this.record = k2 ;
- this.left = a ;
- this.right = t ;
- }
-
- // (K1 A (K2 B C)) ==> (K2 (K1 A B) C)
- final public void rotateLeft() { pivotRight() ; }
- final public void pivotRight()
- {
- checkNotNull(right) ;
- R k1 = record ;
- R k2 = right.record ;
- TreeNode<R> a = left ;
- TreeNode<R> b = right.left ;
- TreeNode<R> c = right.right ;
-
- //TreeNode t = new TreeNode(k1, a, b) ;
- TreeNode<R> t = right ; right.record = k1 ; right.left = a ; right.right = b ;
-
- this.record = k2 ;
- this.left = t ;
- this.right = c ;
- }
-
- // LeftRight
- // (K3 (K1 A (K2 B C)) D) ==> (K2 (K1 A B) (K3 C D))
- //final public void rotateDoubleRight() { pivotLeftRight() ; }
- final public void pivotLeftRight()
- {
- checkNotNull(left) ;
- checkNotNull(left.right) ;
- R k3 = record ;
- R k1 = left.record ;
- R k2 = left.right.record ;
- TreeNode<R> a = left.left ;
- TreeNode<R> b = left.right.left ;
- TreeNode<R> c = left.right.right ;
- TreeNode<R> d = right ;
-
- this.record = k2 ;
-// this.left = new TreeNode<R>(k1, a, b) ; // Reuse LeftRight
-// this.right = new TreeNode<R>(k3, c, d) ; // reuse Left
-
- // XXX WRONG?
- this.left = left.right ;
- /*this.left.record = k1 ;*/ this.left.left = a ; this.left.right = b ;
- this.right = left ;
- /*this.right.record = k3 ;*/ this.right.left = c ; this.right.right = d ;
-
- }
-
- // RightLeft
- // (K1 A (K3 (K2 B C) D)) ==> (K2 (K1 A B) (K3 C D))
- //final public void rotateDoubleLeft() { pivotRightLeft() ; }
- final public void pivotRightLeft()
- {
- checkNotNull(right) ;
- checkNotNull(right.left) ;
-
- R k1 = record ;
- R k3 = right.record ;
- R k2 = right.left.record ;
- TreeNode<R> a = left ;
- TreeNode<R> b = right.left.left ;
- TreeNode<R> c = right.left.right ;
- TreeNode<R> d = right.right ;
-
- this.record = k2 ;
-// this.left = new TreeNode<R>(k1, a, b) ; // replace by in-place / RightLeft
-// this.right = new TreeNode<R>(k3, c, d) ; // Right
-
- // XXX WRONG?
- this.left = left.right ;
- /*this.left.record = k1 ; */this.left.left = a ; this.left.right = b ;
- this.right = left ;
- /*this.right.record = k3 ;*/ this.right.left = c ; this.right.right = d ;
-
- }
-
- // Not in this class
- public Iterator<R> records(R min, R max)
- {
- return null ;
- }
-
- //public Iterator<R> records()
-
- public List<R> records()
- {
- List<R> x = new ArrayList<R>() ;
- records(x) ;
- return x ; // .iterator() ;
- }
-
- public void records(List<R> x)
- {
- if ( left != null )
- left.records(x) ;
- x.add(record) ;
- if ( right != null )
- right.records(x) ;
-
- }
-
- @Override
- public String toString() { return PrintUtils.toString(this) ; }
-
- public void outputNested(IndentedWriter out)
- {
- if ( left == null && right == null )
- {
- out.print(record) ;
- return ;
- }
-
- // At least one of left and right.
-
- out.print('(') ;
- out.print(record) ;
- out.print(' ') ;
- out.incIndent() ;
- out.println() ;
- if ( left != null )
- left.output(out) ;
- else
- out.print("undef") ;
- out.println();
-
- if ( right != null )
- right.output(out) ;
- else
- out.print("undef") ;
- out.print(')') ;
- out.decIndent() ;
- }
-
- @Override
- public void output(IndentedWriter out)
- {
- if ( left == null && right == null )
- {
- out.print(record) ;
- return ;
- }
-
- out.print('(') ;
- out.print(record) ;
- if ( left != null )
- {
- out.print(' ') ;
- left.output(out) ;
- }
- if ( right != null )
- {
- out.print(' ') ;
- right.output(out) ;
- }
- out.print(')') ;
- }
-
- // Inline me :-)
- final private static void checkNotNull(Object object)
- {
- if ( object == null )
- throw new TreeException("Null") ;
- }
+package structure.tree;
+
+import java.util.ArrayList ;
+import java.util.Iterator ;
+import java.util.List ;
+
+import org.openjena.atlas.io.IndentedWriter ;
+import org.openjena.atlas.io.PrintUtils ;
+import org.openjena.atlas.io.Printable ;
+
+
+/** Simple binary tree nodes, including operations that apply to all trees */
+
+public class TreeNode<R extends Comparable<R>> implements Printable
+{
+ private TreeNode<R> left ;
+ private TreeNode<R> right ;
+ private R record ;
+
+ public TreeNode(R record)
+ {
+ this.record = record ;
+ }
+
+ public TreeNode(R record, TreeNode<R> left, TreeNode<R> right)
+ {
+ this(record) ;
+ this.left = left ;
+ this.right = right ;
+ }
+
+ public R insert(R newRecord)
+ { return insert(newRecord, true) ; }
+
+ // Unbalanced insert - return the record if the record already present, else null if new.
+ public R insert(R newRecord, boolean duplicates)
+ {
+ int x = this.record.compareTo(newRecord) ;
+
+ if ( x > 0 )
+ {
+ if ( left == null )
+ {
+ left = new TreeNode<R>(newRecord) ;
+ return null ;
+ }
+ return left.insert(newRecord, duplicates) ;
+ }
+
+ if ( x == 0 && ! duplicates )
+ return this.record ;
+
+ if ( right == null )
+ {
+ right = new TreeNode<R>(newRecord) ;
+ return null ;
+ }
+ return right.insert(newRecord, duplicates) ;
+ }
+
+ // Naming: rotateRight means move the left child up to the root and the root to the right
+ // The left is the pivot
+ // == shift right
+ // == clockwise
+ // This is the wikipedia naming but that does not extend to the double rotations.
+ // Different books have different namings, based on the location of the pivot (which would be a left rotate)
+ // But when we talk about double rotations, the pivotLeft terminolgy works better.
+ // pivotLeft (= case left left) , pivotLeftRight,
+
+
+ // (K1 (K2 A B) C) ==> (K2 A (K1 B C))
+ final public void rotateRight() { pivotLeft() ; }
+ final public void pivotLeft()
+ {
+ // Validity checking?
+ checkNotNull(left) ;
+
+ R k1 = record ;
+ R k2 = left.record ;
+ TreeNode<R> a = left.left ;
+ TreeNode<R> b = left.right ;
+ TreeNode<R> c = right ;
+
+ // Or reuse left.
+ // TreeNode t = new TreeNode(k1, b, c) ;
+ TreeNode<R> t = left ; t.record = k1 ; t.left = b ; t.right = c ;
+
+ this.record = k2 ;
+ this.left = a ;
+ this.right = t ;
+ }
+
+ // (K1 A (K2 B C)) ==> (K2 (K1 A B) C)
+ final public void rotateLeft() { pivotRight() ; }
+ final public void pivotRight()
+ {
+ checkNotNull(right) ;
+ R k1 = record ;
+ R k2 = right.record ;
+ TreeNode<R> a = left ;
+ TreeNode<R> b = right.left ;
+ TreeNode<R> c = right.right ;
+
+ //TreeNode t = new TreeNode(k1, a, b) ;
+ TreeNode<R> t = right ; right.record = k1 ; right.left = a ; right.right = b ;
+
+ this.record = k2 ;
+ this.left = t ;
+ this.right = c ;
+ }
+
+ // LeftRight
+ // (K3 (K1 A (K2 B C)) D) ==> (K2 (K1 A B) (K3 C D))
+ //final public void rotateDoubleRight() { pivotLeftRight() ; }
+ final public void pivotLeftRight()
+ {
+ checkNotNull(left) ;
+ checkNotNull(left.right) ;
+ R k3 = record ;
+ R k1 = left.record ;
+ R k2 = left.right.record ;
+ TreeNode<R> a = left.left ;
+ TreeNode<R> b = left.right.left ;
+ TreeNode<R> c = left.right.right ;
+ TreeNode<R> d = right ;
+
+ this.record = k2 ;
+// this.left = new TreeNode<R>(k1, a, b) ; // Reuse LeftRight
+// this.right = new TreeNode<R>(k3, c, d) ; // reuse Left
+
+ // XXX WRONG?
+ this.left = left.right ;
+ /*this.left.record = k1 ;*/ this.left.left = a ; this.left.right = b ;
+ this.right = left ;
+ /*this.right.record = k3 ;*/ this.right.left = c ; this.right.right = d ;
+
+ }
+
+ // RightLeft
+ // (K1 A (K3 (K2 B C) D)) ==> (K2 (K1 A B) (K3 C D))
+ //final public void rotateDoubleLeft() { pivotRightLeft() ; }
+ final public void pivotRightLeft()
+ {
+ checkNotNull(right) ;
+ checkNotNull(right.left) ;
+
+ R k1 = record ;
+ R k3 = right.record ;
+ R k2 = right.left.record ;
+ TreeNode<R> a = left ;
+ TreeNode<R> b = right.left.left ;
+ TreeNode<R> c = right.left.right ;
+ TreeNode<R> d = right.right ;
+
+ this.record = k2 ;
+// this.left = new TreeNode<R>(k1, a, b) ; // replace by in-place / RightLeft
+// this.right = new TreeNode<R>(k3, c, d) ; // Right
+
+ // XXX WRONG?
+ this.left = left.right ;
+ /*this.left.record = k1 ; */this.left.left = a ; this.left.right = b ;
+ this.right = left ;
+ /*this.right.record = k3 ;*/ this.right.left = c ; this.right.right = d ;
+
+ }
+
+ // Not in this class
+ public Iterator<R> records(R min, R max)
+ {
+ return null ;
+ }
+
+ //public Iterator<R> records()
+
+ public List<R> records()
+ {
+ List<R> x = new ArrayList<R>() ;
+ records(x) ;
+ return x ; // .iterator() ;
+ }
+
+ public void records(List<R> x)
+ {
+ if ( left != null )
+ left.records(x) ;
+ x.add(record) ;
+ if ( right != null )
+ right.records(x) ;
+
+ }
+
+ @Override
+ public String toString() { return PrintUtils.toString(this) ; }
+
+ public void outputNested(IndentedWriter out)
+ {
+ if ( left == null && right == null )
+ {
+ out.print(record) ;
+ return ;
+ }
+
+ // At least one of left and right.
+
+ out.print('(') ;
+ out.print(record) ;
+ out.print(' ') ;
+ out.incIndent() ;
+ out.println() ;
+ if ( left != null )
+ left.output(out) ;
+ else
+ out.print("undef") ;
+ out.println();
+
+ if ( right != null )
+ right.output(out) ;
+ else
+ out.print("undef") ;
+ out.print(')') ;
+ out.decIndent() ;
+ }
+
+ @Override
+ public void output(IndentedWriter out)
+ {
+ if ( left == null && right == null )
+ {
+ out.print(record) ;
+ return ;
+ }
+
+ out.print('(') ;
+ out.print(record) ;
+ if ( left != null )
+ {
+ out.print(' ') ;
+ left.output(out) ;
+ }
+ if ( right != null )
+ {
+ out.print(' ') ;
+ right.output(out) ;
+ }
+ out.print(')') ;
+ }
+
+ // Inline me :-)
+ final private static void checkNotNull(Object object)
+ {
+ if ( object == null )
+ throw new TreeException("Null") ;
+ }
}
Modified: 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=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTree.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTree.java Mon Nov 7 13:36:30 2011
@@ -1,4 +1,4 @@
-/**
+/*
* 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
@@ -16,882 +16,882 @@
* 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)) ; }
+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)) ; }
}
Modified: 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=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTreeException.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTreeException.java Mon Nov 7 13:36:30 2011
@@ -1,4 +1,4 @@
-/**
+/*
* 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
@@ -16,12 +16,12 @@
* 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) ; }
+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) ; }
}
Modified: 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=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTreeIterator.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/ttree/TTreeIterator.java Mon Nov 7 13:36:30 2011
@@ -1,4 +1,4 @@
-/**
+/*
* 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
@@ -16,207 +16,207 @@
* 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 ;
-// }
-//
+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 ;
+// }
+//
}