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 [2/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/avl/AVL.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/avl/AVL.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/avl/AVL.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/avl/AVL.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,848 @@
+/**
+ * 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.avl;
+
+import static java.lang.String.format ;
+import static org.openjena.atlas.io.IndentedWriter.stderr ;
+import static org.openjena.atlas.io.IndentedWriter.stdout ;
+import static structure.avl.AvlNode.label ;
+
+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 ;
+import org.openjena.atlas.iterator.Iter ;
+import org.slf4j.Logger ;
+import org.slf4j.LoggerFactory ;
+import structure.OrderedSet ;
+import structure.tree.TreeException ;
+
+public class AVL<T extends Comparable<? super T>> implements Printable, OrderedSet<T>
+{
+ private static Logger log = LoggerFactory.getLogger(AVL.class) ;
+
+ /* ==== AVL TODO
+ * Reenable all of test "del_10"
+ * + Boolean returns on delete
+ * + Size by tracking ins/del
+ */
+
+ /* AVL Tree.
+ *
+ * http://en.wikipedia.org/wiki/AVL_tree
+ * and on the rotations aspect:
+ * http://en.wikipedia.org/wiki/Tree_rotation
+ *
+ * And this is useful:
+ * http://fortheloot.com/public/AVLTreeTutorial.rtf
+ * lance
+ *
+ * Balance factor: height(right) - height(left)
+ * and should in the range -2 to 2.
+ *
+ * (NB Some descriptions use "left-right")
+ *
+ * Notation: tuples of the form (A B C) are used to mean
+ * a node A with left B and right C
+ *
+ * A
+ * / \
+ * B C
+ *
+ * "A" "B" "C" for nodes, and "R1" "R2" "R3" are the record values:
+ *
+ * (R1 A (R2 B C)) is:
+ *
+ * R1
+ * / \
+ * A R2
+ * / \
+ * B C
+ */
+
+ // In rotations, the code keeps the top node object as the top node.
+ /** The height of node with no subtrees : a node below this (i.e. null) has height InitialHeight-1 */
+ static final int InitialHeight = 1 ;
+
+ public static boolean Checking = false ;
+ public static boolean Verbose = false ;
+ public static boolean Logging = false ;
+
+ private AvlNode<T> root = null ;
+
+ //---
+
+ public AVL()
+ {
+ }
+
+ @Override
+ public boolean contains(T record)
+ { return search(record) != null ; }
+
+ @Override
+ public boolean isEmpty()
+ { return root == null ; }
+
+ @Override
+ public T search(T record)
+ {
+ // Remember the input record may be a part key.
+ if ( root == null )
+ return null ;
+ AvlNode<T> n = find(record) ;
+ return record(n) ;
+ }
+
+ @Override
+ public boolean add(T newRecord)
+ {
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format(">> insert(%s)", newRecord)) ;
+ if ( Verbose )
+ output() ;
+ boolean b = insertAtNode(newRecord) ;
+
+ if ( Verbose )
+ output() ;
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format("<< insert(%s)", newRecord)) ;
+ checkTree() ;
+ return b ;
+ }
+
+ @Override
+ public boolean remove(T record)
+ {
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format(">> delete(%s)", record)) ;
+ if ( Verbose )
+ output() ;
+ if ( root == null )
+ return false ;
+
+ // TEMP - cirrect but two tree walks.
+// boolean b = contains(record) ;
+// root = delete1(record, root) ;
+
+ boolean b = delete(root, record) ;
+
+ if ( Verbose )
+ output() ;
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format("<< delete(%s)", record)) ;
+ checkTree() ;
+ return b ;
+ }
+
+ @Override
+ public T max()
+ {
+ if ( root == null )
+ return null ;
+ AvlNode<T> node = root ;
+ AvlNode<T> n2 = null ;
+
+ while ( node != null )
+ {
+ n2 = node ;
+ node = node.right ;
+ }
+ return n2.record ;
+ }
+
+ @Override
+ public T min()
+ {
+ if ( root == null )
+ return null ;
+ AvlNode<T> node = root ;
+ AvlNode<T> n2 = null ;
+ while ( node != null )
+ {
+ n2 = node ;
+ node = node.left ;
+ }
+ return n2.record ;
+ }
+
+ @Override
+ public void clear() { root = null ; }
+
+ // -------- Search
+
+ // Find the parent of maximal node
+ // i.e. for (A
+ // (B (D E) (F G))
+ // (H (I J) (K L)) )
+ // return H (max node is .right => L)
+
+ /** Find the record that is same as or least higher than the given record.
+ * Return null if no such node. */
+
+ public T findRecordAbove(T record)
+ {
+ AvlNode<T> n = findNodeAbove(record) ;
+ return record(n) ;
+ }
+
+ AvlNode<T> findNodeAbove(T record)
+ {
+ if ( record == null )
+ {
+ if ( root == null )
+ return null ;
+ AvlNode<T> node = root ;
+ while ( node.left != null )
+ node = node.left ;
+ return node ;
+ }
+
+ return findNodeAbove(root, record) ;
+ }
+
+
+ /** Find the record that is same as or greatest lower record than the given record.
+ * Return null if no such node.
+ */
+
+ public T findRecordBelow(T record)
+ {
+ AvlNode<T> n = findNodeBelow(record) ;
+ return record(n) ;
+ }
+
+ AvlNode<T> findNodeBelow(T record)
+ {
+ if ( record == null )
+ {
+ if ( root == null )
+ return null ;
+ AvlNode<T> node = root ;
+ while ( node.right != null )
+ node = node.right ;
+ return node ;
+ }
+
+ return findNodeBelow(root, record) ;
+ }
+
+ // Go down right until we find exact or overshoot.
+ private static <R extends Comparable<? super R>> AvlNode<R> findNodeAbove(AvlNode<R> node, R record)
+ {
+ if ( node == null )
+ return null ;
+ int x = record.compareTo(node.record) ;
+ if ( x < 0 )
+ // This node above - switch to phase2.
+ return findNodeAbove(node, record, node) ;
+ else if ( x > 0 )
+ // This node below - try right.
+ return findNodeAbove(node.right, record) ;
+ else
+ return node ;
+ }
+
+ private static <R extends Comparable<? super R>> AvlNode<R> findNodeAbove(AvlNode<R> node, R record, AvlNode<R> bestGuess)
+ {
+ if ( node == null )
+ // Hit bottom and still less.
+ return bestGuess ;
+
+ int x = record.compareTo(node.record) ;
+ if ( x < 0 )
+ // Somewhere in the left tree , but maybe this node.
+ return findNodeAbove(node.left, record, node) ;
+ else if ( x > 0 )
+ // This node is below the target.
+ return bestGuess ;
+ else
+ // Found.
+ return node ;
+ }
+
+ // Go down left until we find exact or undershoot.
+ private static <R extends Comparable<? super R>> AvlNode<R> findNodeBelow(AvlNode<R> node, R record)
+ {
+ if ( node == null )
+ return null ;
+ int x = record.compareTo(node.record) ;
+ if ( x < 0 )
+ // This node is above - keep looking
+ return findNodeBelow(node.left, record) ;
+ else if ( x > 0 )
+ // This node below - switch to phase 2
+ return findNodeBelow(node, record, node) ;
+ else
+ return node ;
+ }
+
+ private static <R extends Comparable<? super R>> AvlNode<R> findNodeBelow(AvlNode<R> node, R record, AvlNode<R> bestGuess)
+ {
+ if ( node == null )
+ // Hit bottom and still more
+ return bestGuess ;
+
+ int x = record.compareTo(node.record) ;
+ if ( x < 0 )
+ // This node is above the target.
+ return bestGuess ;
+ else if ( x > 0 )
+ // Somewhere in the right tree, but maybe this node.
+ return findNodeBelow(node.right, record, node) ;
+ else
+ // Found.
+ return node ;
+ }
+
+ private AvlNode<T> find(T record)
+ {
+ // Remember the input record may be a part key.
+ if ( root == null )
+ return null ;
+ AvlNode<T> node = root ;
+ //AvlNode<R> n2 = null ;
+
+ while ( node != null )
+ {
+ int x = record.compareTo(node.record) ;
+ if ( x < 0 )
+ node = node.left ;
+ else if ( x > 0 )
+ node = node.right ;
+ else
+ // Found.
+ return node ;
+ }
+ return null ;
+ }
+
+ // -------- Insert
+
+ // Insert a record - return true on change (i.e. not already in tree)
+ private boolean insertAtNode(T newRecord)
+ {
+ if ( root == null )
+ {
+ if ( Verbose )
+ log.debug("-- insertAtNode : new root") ;
+ root = new AvlNode<T>(newRecord, null) ;
+ return true ;
+ }
+
+ AvlNode<T> node = root ;
+ AvlNode<T> parent = root.parent ;
+
+ while( node != null )
+ {
+ int x = newRecord.compareTo(node.record) ;
+ if ( x < 0 )
+ {
+ parent = node ;
+ node = node.left ;
+ if ( node == null )
+ {
+ parent.left = new AvlNode<T>(newRecord, parent) ;
+ break ;
+ }
+ }
+ else if ( x > 0 )
+ {
+ parent = node ;
+ node = node.right ;
+ if ( node == null )
+ {
+ parent.right = new AvlNode<T>(newRecord, parent) ;
+ break ;
+ }
+ }
+ else // x == 0 : Same : no action needed, no rebalance.
+ {
+ if ( Verbose )
+ log.debug(format("insertAtNode same %s", label(node))) ;
+ T rec = node.record ;
+ node.record = newRecord ; // Records may be partial.
+ return ! rec.equals(newRecord) ;
+ }
+ }
+
+ // Bottom of tree. node == null.
+ // Set heights and rebalance.
+ rebalanceInsert(parent) ;
+ return true ;
+ }
+
+ private void rebalanceInsert(AvlNode<T> node)
+ {
+ // Need to abort early.
+ while ( node != null )
+ {
+ if ( ! rebalance(node) )
+ // This is still too conservative. ??
+ return ;
+ node = node.parent ;
+ }
+ return ;
+ }
+
+ private void rebalanceDelete(AvlNode<T> node)
+ {
+ while ( node != null )
+ {
+ rebalance(node) ;
+ node = node.parent ;
+ }
+ return ;
+ }
+
+ // -------- Delete
+
+ private boolean delete(AvlNode<T> node, T record)
+ {
+ checkNotNull(node) ;
+ while( node != null )
+ {
+ int x = record.compareTo(node.record) ;
+ if ( x < 0 )
+ node = node.left ;
+ else if ( x > 0 )
+ node = node.right ;
+ else // x == 0
+ break ;
+ }
+ if ( node == null )
+ // Not found.
+ return false ;
+
+ // -- swapNode is the node with the replacement record.
+ // If node is a leaf, then swapNode == node
+ AvlNode<T> swapNode ;
+ if ( node.left != null )
+ {
+ swapNode = getRightDeep(node.left) ;
+ // Swap in value from leaf.
+ node.record = swapNode.record ;
+ }
+ else if ( node.right != null )
+ {
+ swapNode = getLeftDeep(node.right) ;
+ // Swap in value from leaf.
+ node.record = swapNode.record ;
+ }
+ else
+ // Already a leaf : No record swap need
+ swapNode = node ;
+
+ // So swapNode is the min or max of a subtree below "node".
+ // It is a half-leaf or leaf (or it would not be a min or max).
+
+ // -- The replacement tree. Maybe null.
+ AvlNode<T> subTree ;
+ if ( swapNode.left != null )
+ subTree = swapNode.left ;
+ else if ( swapNode.right != null )
+ subTree = swapNode.right ;
+ else
+ // swapNode is a leaf.
+ subTree = null ;
+
+ if ( subTree != null )
+ // Half-leaf - splice out swapNode.
+ subTree.parent = swapNode.parent ;
+
+ if ( swapNode.parent == null )
+ {
+ // At root.
+ root = subTree ;
+ //rebalanceDelete(root) ;
+ return true ;
+ }
+
+ // Replace in parent.
+ if ( swapNode.parent.left == swapNode )
+ swapNode.parent.left = subTree ;
+ else
+ swapNode.parent.right = subTree ;
+ rebalanceDelete(swapNode.parent) ;
+ return true ;
+ }
+
+ // Uses the fact that that the pivot operations keep the original node object
+ // as the top of the pivoted structure.
+ // Returns whether the height of the node changed.
+
+ private boolean rebalance(AvlNode<T> node)
+ {
+ if ( node == null )
+ return false ;
+
+ if ( Verbose )
+ {
+ log.debug(format(">> Rebalance : %s", label(node))) ;
+ //output() ;
+ }
+
+ int bal = balance(node.left, node.right) ;
+
+ if ( bal < -2 || bal > 2 )
+ brokenTree(node, "Unbalanced") ;
+
+ int h = height(node) ;
+
+ if ( bal == 1 || bal == 0 || bal == -1 )
+ {
+ setHeight(node) ;
+ checkNode(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) ;
+ checkNode(node) ;
+
+ if ( Verbose )
+ log.debug(format("<< Rebalance : %s", label(node))) ;
+ return h != height(node) ;
+ }
+
+ private static <R extends Comparable<? super R>> R record(AvlNode<R> n)
+ {
+ return (n == null) ? null : n.record ;
+ }
+
+ private static <R extends Comparable<? super R>> void setHeight(AvlNode<R> node)
+ {
+ //if ( node == null ) return ;
+ node.height = Math.max(height(node.left), height(node.right)) + 1;
+ }
+
+ private static <R extends Comparable<? super R>> int height(AvlNode<R> node)
+ {
+ if ( node == null )
+ return InitialHeight-1 ;
+ return node.height ;
+ }
+
+ static <R extends Comparable<? super R>> int balance(AvlNode<R> left, AvlNode<R> right)
+ {
+ return height(right) - height(left) ;
+ }
+
+ // ---- Rotations
+ // Naming: pivotRight 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 (case left right), etc
+
+ // These operations act in-place : the nodes reused so the top node (the argument) remain the same object
+
+ // (R1 (R2 A B) C) ==> (R2 A (R1 B C))
+ private void pivotLeft(AvlNode<T> node)
+ {
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format(">> pivotLeft : %s", label(node))) ;
+
+ // Validity checking?
+ checkNotNull(node.left) ;
+
+ AvlNode<T> n = node.left ;
+ T r1 = node.record ;
+ T r2 = n.record ;
+
+ AvlNode<T> a = n.left ;
+ AvlNode<T> b = n.right ;
+ AvlNode<T> c = node.right ;
+
+ // Reuse n as the node (R1 B C)
+ n.set(r1, 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, node.parent, a, n) ;
+ setHeight(node) ;
+
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format("<< pivotLeft : %s", label(node))) ;
+ }
+
+ // (R1 A (R2 B C)) ==> (R2 (R1 A B) C)
+ private void pivotRight(AvlNode<T> node)
+ {
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format(">> pivotRight : %s", label(node))) ;
+
+ checkNotNull(node.right) ;
+ // Take nodes apart
+ AvlNode<T> n = node.right ;
+ T r1 = node.record ;
+ T r2 = n.record ;
+ AvlNode<T> a = node.left ;
+ AvlNode<T> b = n.left ;
+ AvlNode<T> c = n.right ;
+
+ // Reuse n as the node (R1 A B)
+ n.set(r1, 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, node.parent, n, c) ;
+ setHeight(node) ;
+
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format("<< pivotRight : %s", label(node))) ;
+ }
+
+ // LeftRight
+ // (R3 (R1 A (R2 B C)) D) ==> (R2 (R1 A B) (R3 C D))
+ private void pivotLeftRight(AvlNode<T> node)
+ {
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format(">> pivotLeftRight : %s", label(node))) ;
+ checkNotNull(node.left) ;
+ checkNotNull(node.left.right) ;
+
+ // Take apart ...
+ AvlNode<T> n1 = node.left ;
+ AvlNode<T> n2 = node.left.right ;
+
+ T r3 = node.record ;
+ T r1 = n1.record ;
+ T r2 = n2.record ;
+ AvlNode<T> a = n1.left ;
+ AvlNode<T> b = n2.left ;
+ AvlNode<T> c = n2.right ;
+ AvlNode<T> d = node.right ;
+
+ // Reuse nodes ; n1 becomes the R1 node, n2 the R3 node.
+ n1.set(r1, node, a, b) ;
+ setHeight(n1) ;
+ n2.set(r3, 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, node.parent, n1, n2) ;
+ setHeight(node) ;
+
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format("<< pivotLeftRight : %s", label(node))) ;
+ }
+
+ // RightLeft
+ // (R1 A (R3 (R2 B C) D)) ==> (R2 (R1 A B) (R3 C D))
+ private void pivotRightLeft(AvlNode<T> node)
+ {
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format(">> pivotRightLeft : %s", label(node))) ;
+ checkNotNull(node.right) ;
+ checkNotNull(node.right.left) ;
+ AvlNode<T> n1 = node.right ;
+ AvlNode<T> n2 = node.right.left ;
+
+ T r1 = node.record ;
+ T r3 = n1.record ;
+ T r2 = n2.record ;
+ AvlNode<T> a = node.left ;
+ AvlNode<T> b = n2.left ;
+ AvlNode<T> c = n2.right ;
+ AvlNode<T> d = n1.right ;
+
+ // Reuse nodes ; n1 becomes the R1 node, n2 the R3 node.
+ n1.set(r1, node, a, b) ;
+ setHeight(n1) ;
+ n2.set(r3, 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, node.parent, n1, n2) ;
+ setHeight(node) ;
+
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format("<< pivotRightLeft : %s", label(node))) ;
+ }
+
+ // ---- Iteration
+
+ @Override
+ public Iterator<T> iterator() { return iterator(null, null) ; }
+
+ @Override
+ public Iterator<T> iterator(T r1, T r2) { return AvlIterator.iterator(this, r1, r2) ; }
+
+ public Iterable<T> records() { return records(null, null) ; }
+
+ public Iterable<T> records(T r1, T r2) { return Iter.iter(AvlIterator.iterator(this, r1, r2)) ; }
+
+ public List<T> calcRecords() { return calcRecords(null, null) ; }
+
+ public List<T> calcRecords(T r1, T r2) { return AvlIterator.calcIter(root, r1, r2) ; }
+
+
+ static <R extends Comparable<? super R>> AvlNode<R> getRightDeep(AvlNode<R> node)
+ {
+ AvlNode<R> node2 = node.right ;
+ while( node2 != null )
+ {
+ node = node2 ;
+ node2 = node2.right ;
+ }
+ return node ;
+ }
+
+ static <R extends Comparable<? super R>> AvlNode<R> getLeftDeep(AvlNode<R> node)
+ {
+ AvlNode<R> node2 = node.left ;
+ while( node2 != null )
+ {
+ node = node2 ;
+ node2 = node2.left ;
+ }
+ return node ;
+ }
+
+
+ @Override
+ public long size() { return count() ; }
+
+ @Override
+ public long count()
+ {
+ if ( root == null )
+ return 0 ;
+ return root.count() ;
+ }
+
+ /** Collect all the elements in the AVL into a list and return the list. */
+ @Override
+ public List<T> elements()
+ {
+ List<T> x = new ArrayList<T>() ;
+ if ( root == null )
+ return x ;
+ 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();
+ }
+
+ private void checkNode(AvlNode<T> node)
+ {
+ if ( ! Checking )
+ return ;
+ checkNotNull(node) ;
+ try {
+ node.checkDeep() ;
+ } catch (TreeException ex)
+ {
+ try {
+ stderr.println("****") ;
+ output(stderr) ;
+ stderr.println("****") ;
+ stderr.flush();
+ } catch (Exception ex2) { stderr.ensureStartOfLine() ; } // try to dump tree
+ throw ex ;
+ }
+ }
+
+ @Override
+ final public void checkTree()
+ {
+ if ( ! Checking )
+ return ;
+ if ( root != null )
+ {
+ if ( root.parent != null )
+ brokenTree(root, "Root parent is not null") ;
+ root.checkDeep() ;
+ }
+
+ }
+
+
+ final static void checkNotNull(Object object)
+ {
+ if ( object == null )
+ throw new TreeException("Null") ;
+ }
+
+ final void brokenTree(AvlNode<T> node, String msg)
+ {
+ IndentedWriter.stderr.println();
+ output(IndentedWriter.stderr) ;
+ throw new TreeException(msg+" : "+node.toString()) ;
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/avl/AvlIterator.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/avl/AvlIterator.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/avl/AvlIterator.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/avl/AvlIterator.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,184 @@
+/**
+ * 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.avl;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+
+public class AvlIterator<R extends Comparable<? super R>> implements Iterator<R>
+{
+ public static <R extends Comparable<? super R>> Iterator<R> iterator(AVL<R> avl, R min, R max)
+ {
+ return new AvlIterator<R>(avl, min, max) ;
+ }
+
+ boolean finished = false ;
+ R record ; // Yield this before moving on
+ AvlNode<R> node ;
+ R max ;
+
+ AvlIterator(AVL<R> avl, R min, R max)
+ {
+ if ( min != null && max != null )
+ {
+ int x = min.compareTo(max) ;
+ if ( x >= 0 )
+ {
+ finished = true ;
+ return ;
+ }
+ }
+
+ node = avl.findNodeAbove(min) ;
+ if ( node == null )
+ {
+ record = null ;
+ finished = true ;
+ return ;
+ }
+
+ record = node.record ;
+ this.max = max ;
+ }
+
+ @Override
+ public boolean hasNext()
+ {
+ if ( finished )
+ return false ;
+
+ if ( record != null )
+ return true ;
+
+ // Record null, move to next node.
+ if ( node == null )
+ {
+ System.err.println("Happened!") ;
+ // Does not happen?
+ finished = true ;
+ return false ;
+ }
+
+ // Have yielded the value for "node" (and hence all 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
+
+ AvlNode<R> nextNode = node.right ;
+ if ( nextNode != null )
+ {
+ // There is a right tree to do.
+ // Find min (left chasing)
+ while ( nextNode.left != null )
+ nextNode = nextNode.left ;
+ }
+ else
+ {
+ // No right subtree from here.
+ // Walk up tree until we were not the right node of our parent.
+ AvlNode<R> n2 = node ;
+ AvlNode<R> n3 = n2.parent ;
+ while( n3 != null )
+ {
+ if ( n3.right != 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 ;
+ }
+
+ node = nextNode ;
+ return testAndSetRecord(nextNode) ;
+ }
+
+ private boolean testAndSetRecord(AvlNode<R> node)
+ {
+ if ( node == null )
+ {
+ record = null ;
+ finished = true ;
+ return false ;
+ }
+
+ if ( max != null )
+ {
+ int x = node.record.compareTo(max) ;
+ if ( x >= 0 )
+ {
+ // End
+ finished = true ;
+ return false ;
+ }
+ }
+ record = node.record ;
+ return true ;
+ }
+
+ @Override
+ public R next()
+ {
+ if ( ! hasNext())
+ throw new NoSuchElementException("AvlIterator") ;
+ R r = record ;
+ record = null ;
+ return r ;
+ }
+
+ @Override
+ public void remove()
+ { throw new UnsupportedOperationException("AvlIterator") ; }
+
+ // Calculate the iterator. For testing.
+ static <R extends Comparable<? super R>> List<R> calcIter(AvlNode<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/avl/AvlNode.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/avl/AvlNode.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/avl/AvlNode.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/avl/AvlNode.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,307 @@
+/**
+ * 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.avl;
+
+import static java.lang.String.format;
+
+import java.io.PrintStream;
+import java.util.ArrayList;
+import java.util.List;
+
+import structure.tree.TreeException;
+
+import org.openjena.atlas.io.IndentedWriter;
+import org.openjena.atlas.io.Printable;
+
+final class AvlNode<T extends Comparable<? super T>> implements Printable
+{
+ private static int counter = 0 ;
+
+ /* Only used for debugging. Remove for production (or, make static and ignore)
+ * But removing does not necesarily save space - Java seem to allocate in
+ * fixed size, quantized units and this id does not cause it to spill
+ * such a unit.
+ */
+ private int id ;
+
+ int height = AVL.InitialHeight ;
+ AvlNode<T> parent ;
+ AvlNode<T> left ;
+ AvlNode<T> right ;
+ T record ;
+
+ AvlNode(T record, AvlNode<T> parent) { this(record, parent, null, null) ; }
+
+ AvlNode(T record, AvlNode<T> parent, AvlNode<T> left, AvlNode<T> right)
+ {
+ set(record, parent, left, right) ;
+ id = (++counter) ;
+ }
+
+ void set(T record, AvlNode<T> parent, AvlNode<T> left, AvlNode<T> right)
+ {
+ this.record = record ;
+ this.parent = parent ;
+ this.left = left ;
+ this.right = right ;
+ this.parent = parent ;
+ }
+
+ public List<T> records()
+ {
+ List<T> x = new ArrayList<T>() ;
+ records(x) ;
+ return x ; // .iterator() ;
+ }
+
+ public void records(List<T> x)
+ {
+ if ( left != null )
+ left.records(x) ;
+ x.add(record) ;
+ if ( right != null )
+ right.records(x) ;
+
+ }
+
+ public long count()
+ {
+ long x = 1 ;
+ if ( left != null )
+ x = x + left.count() ;
+ if ( right != null )
+ x = x + right.count() ;
+ return x ;
+ }
+
+ boolean isLeaf() { return left == null && right == null ; }
+
+ void elements(List<T> acc)
+ {
+ if ( left != null )
+ left.elements(acc) ;
+ acc.add(record) ;
+ if ( right != null )
+ right.elements(acc) ;
+ }
+
+ @Override
+ public String toString()
+ {
+ //return record.toString() ;
+ return toString2() ;
+ }
+
+
+ public String toString2()
+ {
+ return format("[%s] rec=%s parent=%s [h=%d] left=%s, right=%s", label(this), record, label(parent), height, label(left), label(right)) ;
+ }
+
+ private static final String undef = "_" ;
+ static <R extends Comparable<? super R>> String label(AvlNode<R> n)
+ {
+ if ( n == null )
+ return undef ;
+ return Integer.toString(n.id) ;
+ }
+
+ public void debug()
+ {
+ debug(System.out) ;
+ }
+
+ public void debug(PrintStream ps)
+ {
+ IndentedWriter out = new IndentedWriter(ps) ;
+ this.outputNested(out, true) ;
+ out.println();
+ out.flush();
+ ps.flush();
+
+ }
+
+ /** print structured */
+ public void outputNested(IndentedWriter out, boolean detailed)
+ {
+ out.print('(') ;
+ if ( detailed )
+ out.print(toString2()) ;
+ else
+ out.print(this) ;
+
+ // Inline small things.
+ // Improve to "if left and right leafves and not detailed"
+ if ( left == null && right == null )
+ {
+ out.print(" ") ; out.print(undef) ; out.print(" ") ; out.print(undef) ;
+ out.print(')') ;
+ return ;
+ }
+
+
+ out.incIndent() ;
+ out.println() ;
+ if ( left != null )
+ left.outputNested(out, detailed) ;
+ else
+ out.print(undef) ;
+ out.println();
+
+ if ( right != null )
+ right.outputNested(out, detailed) ;
+ else
+ out.print(undef) ;
+ out.print(')') ;
+ out.decIndent() ;
+ }
+
+ /** Output the record of a subtree : Looses left/right distinction*/
+ @Override
+ public void output(IndentedWriter out)
+ {
+// if ( left == null && right == null )
+// {
+// out.print(record) ;
+// return ;
+// }
+//
+ out.print('(') ;
+ out.print(record) ;
+ out.print(' ') ;
+
+ if ( left != null )
+ left.output(out) ;
+ else
+ out.print('_') ;
+
+ out.print(' ') ;
+ if ( right != null )
+ right.output(out) ;
+ else
+ out.print('_') ;
+ out.print(')') ;
+ }
+
+ final void check()
+ {
+ if ( ! AVL.Checking )
+ return ;
+
+ if ( record == null ) error("Null record") ;
+
+ // -- Ordering checks
+ if ( left != null && record.compareTo(left.record) < 0 ) // If this less than left.
+ error("Out of order (left): [id=%s] %s/%s", label(left), record, left.record) ;
+
+ if ( right != null && record.compareTo(right.record) > 0 ) // If this more than right
+ error("Out of order (right): [id=%s] %s/%s", label(right), record, left.record) ;
+
+ // -- Balance checks
+ int x = AVL.balance(left, right) ;
+ if ( x < -1 || x > 1 )
+ error("Out of balance %d %s [h=%d] [left (%s),right (%s)]", x, record, height, label(left), label(right)) ;
+
+ // -- 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 - not %d or %d", left.height+1, right.height+1) ;
+ }
+ else
+ {
+ if ( height != AVL.InitialHeight )
+ error("Leaf node height not %d", AVL.InitialHeight) ;
+ }
+
+ // Parent.
+ 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 ( 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") ;
+ }
+
+ final void checkDeep()
+ {
+ if ( ! AVL.Checking )
+ return ;
+ check() ;
+ if ( left != null )
+ left.check();
+ if ( right != null )
+ right.check();
+ }
+
+ private void error(String msg, Object... args)
+ {
+ msg = format(msg, args) ;
+ System.out.printf("[%s] %s\n", label(this), msg) ;
+ System.out.flush();
+ this.outputNested(IndentedWriter.stderr, true) ;
+ IndentedWriter.stderr.ensureStartOfLine() ;
+ IndentedWriter.stderr.flush();
+ throw new TreeException(msg) ;
+ }
+
+
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/exthash/ExtHashMem.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/exthash/ExtHashMem.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/exthash/ExtHashMem.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/exthash/ExtHashMem.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,647 @@
+/**
+ * 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.exthash;
+
+import static org.openjena.atlas.lib.Alg.decodeIndex;
+import static java.lang.String.format;
+import static java.lang.System.arraycopy;
+import static java.util.Arrays.binarySearch;
+import org.openjena.atlas.io.IndentedLineBuffer;
+import org.openjena.atlas.io.IndentedWriter;
+
+import java.util.Arrays;
+
+import org.openjena.atlas.lib.BitsLong;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import com.hp.hpl.jena.tdb.base.StorageException;
+
+/** Extensible hashing
+ * http://en.wikipedia.org/wiki/Extendible_hashing
+ */
+public class ExtHashMem<K,V>
+{
+ // Purely in-memory version (for comparison and understanding)
+
+ /* Hashing.
+ * Extendible hashing is based on taking more of the bits of the hash
+ * value to address an expanding dictionary. This is a bit-trie, stored
+ * as an array. One bucket can be used for several hash slots.
+ *
+ * We need that the bits are used in decreasing signifance because we
+ * keep items in buckets in full-hash sorted order.
+ *
+ * Side effect: the whole structure is sorted by full hash, using
+ * dictionary and buckets.
+ *
+ * But.
+ * Java .hashCode() does not make suitable hash directly because either
+ * they are Object.hashCode (not too bad but it tends not to use high bits) or
+ * something like Integer.hashCode is the integer value itself. The
+ * latter is very bad as the hash is not using the high bits (most
+ * integers are small - especially sequentially allocated numbers).
+ *
+ * Solution: use the hashCode, 31 bits (arrays indexes are signed)
+ * but bit reversed so low bits of the original value are the most
+ * significant.
+ *
+ * All hash handling is encapulated in the internal routines.
+ */
+
+ static private Logger log = LoggerFactory.getLogger(ExtHashMem.class) ;
+
+ // Production: make these final and false.
+ public static boolean NullOut = true ; // Set released space to something not an valid entry.
+ public static boolean Checking = false ; // Perform internal checking
+ public static boolean Logging = false ; // Allow any logging code on critical paths
+
+ // Give each bucket a unique-per-hashtable id. Debugging.
+ private int bucketCounter = 0 ;
+
+ // Dictionary - can't have Java Arrays of generics. Could use List<>
+ private Object[] dictionary ; // mask(hash) -> Bucket
+
+ // Current length of trie bit used. Invariant: dictionary.length = 1<<bitLen
+ private int bitLen = 0 ;
+ // Number of things in the hash table.
+ private long size = 0 ;
+
+ public static int DefaultBucketSize = 10 ;
+ // Size of bucket
+ final int bucketSize ;
+
+
+ public ExtHashMem() { this(DefaultBucketSize) ; }
+
+ public ExtHashMem(int bucketSize) { this(bucketSize, 0) ; }
+
+ public ExtHashMem(int bucketSize, int initialBitLength)
+ {
+ this.bucketSize = bucketSize ;
+ int dictionarySize = 1<<initialBitLength ;
+ dictionary = new Object[dictionarySize] ;
+ Bucket<V> bucket = new Bucket<V>(0, initialBitLength, bucketSize, bucketCounter++) ;
+ dictionary[0] = bucket ;
+ bitLen = 0 ;
+ }
+
+ // =====================
+ // Hashing routines for converting to a bit-trie (i.e. highest bit
+ // is most significant in the trie).
+
+ //From java.util.HashMap
+// /**
+// * Applies a supplemental hash function to a given hashCode, which
+// * defends against poor quality hash functions. This is critical
+// * because HashMap uses power-of-two length hash tables, that
+// * otherwise encounter collisions for hashCodes that do not differ
+// * in lower bits. Note: Null keys always map to hash 0, thus index 0.
+// */
+// static int hash(int h) {
+// // This function ensures that hashCodes that differ only by
+// // constant multiples at each bit position have a bounded
+// // number of collisions (approximately 8 at default load factor).
+// h ^= (h >>> 20) ^ (h >>> 12);
+// return h ^ (h >>> 7) ^ (h >>> 4);
+// }
+
+ // The bit reverse of .hashCode so that integers are spread out.
+ // It's important that bits "appear" as the length changes in decreasing
+ // significance order.
+ // Use 31 bits (not the top hashCode bit) because array indexes are 32bit.
+
+ /** Turn a key into a bit trie has value */
+ protected static <K> int keyHash(K k) { return Integer.reverse(k.hashCode())>>>1 ; }
+
+ /** Calculate the array index for a key given the dictionary bit length */
+ protected static <K> int index(K k, int bitLen) { return index(keyHash(k), bitLen) ; }
+
+ /** Convert from full hash to array index for a dictionary bit length */
+ protected static <K> int index(int fullHash, int bitLen)
+ {
+ //return (int)Bits.unpack(fullHash, (31-bitLen), 31) ;
+ return fullHash >>> (31-bitLen) ;
+ }
+
+ // =====================
+
+ private void resizeDictionary()
+ {
+ int oldSize = 1<<bitLen ;
+ int newBitLen = bitLen+1 ;
+ int newSize = 1<<newBitLen ;
+
+ if ( Logging && log.isDebugEnabled() )
+ {
+ log.debug(format("resize: %d ==> %d", oldSize, newSize)) ;
+ System.out.println(">>>>Resize") ;
+ System.out.println(this) ;
+ System.out.println("----Resize") ;
+ }
+
+ Object[] newDictionary = new Object[newSize] ;
+ if ( dictionary != null )
+ {
+ // Fill new dictionary
+ // NB Fills from high to low so that it works if done "in place"
+ for ( int i = oldSize-1 ; i>=0 ; i-- )
+ {
+ newDictionary[2*i] = dictionary[i] ;
+ newDictionary[2*i+1] = dictionary[i] ;
+ }
+ }
+ dictionary = newDictionary ;
+ bitLen = newBitLen ;
+ if ( Logging && log.isDebugEnabled() )
+ {
+ System.out.println(this) ;
+ System.out.println("<<<<Resize") ;
+ }
+ internalCheck() ;
+ }
+
+ //@Override
+ public boolean contains(K key)
+ {
+ return get(key) != null ;
+ }
+
+ //@Override
+ public V get(K key)
+ {
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format(">> get(%s)", key)) ;
+ int i = index(key, bitLen) ;
+ @SuppressWarnings("unchecked")
+ Bucket<V> bucket = (Bucket<V>)dictionary[i] ;
+ // Maybe multiples
+ V value = bucket.find(keyHash(key)) ;
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format(">> get(%s) -> %s", key, value)) ;
+ return value ;
+ }
+
+ //@Override
+ public void put(K key, V value)
+ {
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format(">> put(%s,%s)", key, value)) ;
+ int h = keyHash(key) ;
+ boolean b = _put(key, value, h) ;
+ if ( b )
+ size++ ;
+ internalCheck() ;
+ if ( Logging && log.isDebugEnabled() )
+ {
+ log.debug(format("<< put(%s,%s)", key, value)) ;
+ dump() ;
+ }
+ }
+
+ //@Override
+ public void remove(K key)
+ {
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format(">> remove(%s)", key)) ;
+ int hash = keyHash(key) ;
+ int i = index(hash, bitLen) ;
+ @SuppressWarnings("unchecked")
+ Bucket<V> bucket = (Bucket<V>)dictionary[i] ;
+ boolean b = bucket.removeByHash(hash) ;
+ if ( b )
+ size-- ;
+ internalCheck() ;
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format("<< remove(%s)", key)) ;
+ }
+
+ //@Override
+ public long size()
+ {
+ return size ;
+ }
+
+ //@Override
+ public void sync()
+ {}
+
+ //@Override
+ public void close()
+ {}
+
+ // =====================
+ // Insert
+
+ // Reentrant part of "put"
+ private boolean _put(K key, V value, int hash)
+ {
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format("put(%s,%s,0x%08X)", key, value, hash)) ;
+
+ int idx = index(hash, bitLen) ;
+ @SuppressWarnings("unchecked")
+ Bucket<V> bucket = (Bucket<V>)dictionary[idx] ;
+
+ if ( bucket.hasRoom() )
+ {
+ boolean b = bucket.put(hash, value) ;
+ return b ;
+ }
+
+ // Bucket full.
+ if ( bitLen == bucket.bucketBitLen )
+ {
+ // Bucket not splitable..
+ // TODO Overflow buckets.
+ // Expand the dictionary.
+ resizeDictionary() ;
+ // Try again
+ return _put(key, value, hash) ;
+ }
+
+
+ // bitLen > bucket.bucketBitLen : bucket can be split
+ splitAndReorganise(bucket, idx, hash) ;
+
+ // Reorg done - try again.
+ return _put(key, value, hash) ;
+ }
+
+
+ private void splitAndReorganise(Bucket<V> bucket, int idx, int hash)
+ {
+ if ( Checking && log.isDebugEnabled() )
+ {
+ log.debug(format("splitAndReorganise: idx=%d, bitLen=%d, bucket.hashLength=%d",
+ idx, bitLen, bucket.bucketBitLen)) ;
+ dump() ;
+ }
+
+ if ( Checking && index(hash, bucket.bucketBitLen) != bucket.hash )
+ error("splitAndReorganise: idx=0x%X : hash=0x%X[0x%X,0x%X] : Inconsistency : %s",
+ idx, hash, index(hash, bucket.bucketBitLen), bucket.hash, bucket) ;
+
+ // Bucket did not have a full length hash so split it.
+ // Find the companion slots.
+ // Remember before messing with split.
+ int bucketHash = bucket.hash ;
+ int bucketHashLength = bucket.bucketBitLen ;
+
+ // Split the bucket in two. buckets2 is the upper bucket.
+ Bucket<V> bucket2 = split(idx, bucket) ;
+
+ // Determine the slots affected: all the dictionary entries that
+ // correspond to the extension of the but trie by a 0x1 in the next bit.
+ // A bitLen length bit pattern, with
+ // Top: bucket hash
+ // 1 (the ones with 0 are left with the original (and now smaller) bucket
+ // Bottom: All possible bits in lower bits
+ int trieUpperRoot = ((bucketHash<<1)|0x1) << (bitLen-bucketHashLength-1) ;
+ int trieUpperRange = (1<<(bitLen-bucketHashLength-1)) ;
+
+ for ( int j = 0 ; j < trieUpperRange ; j++ )
+ {
+ // j runs over the values of the unused bits of the trie start for the upper bucket positions.
+ int k = trieUpperRoot | j ;
+ if ( Checking )
+ {
+ if ( (trieUpperRoot&j) != 0 )
+ error("put: idx=%d : trieRoot=0x%X, sub=%d: Broken trie pattern ", idx, trieUpperRoot, j) ;
+ if ( ! BitsLong.isSet(k, (bitLen-(bucketHashLength+1)) ) )
+ error("put: Broken trie pattern (0x%X,%d)", trieUpperRoot, j) ;
+ if ( dictionary[k] != bucket )
+ error("put: Wrong bucket at trie (0x%X,%d)", trieUpperRoot, j) ;
+ }
+ dictionary[k] = bucket2 ;
+ }
+ if ( Logging && log.isDebugEnabled() )
+ {
+ log.debug("Reorg complete") ;
+ //dump() ;
+ }
+
+ }
+
+ private Bucket<V> split(int idx, Bucket<V> bucket)
+ {
+ // idx is the array offset to the lower of the bucket point pair.
+ if ( Logging && log.isDebugEnabled() )
+ {
+ log.debug(format("split: Bucket %d : size: %d; Bucket bitlength %d", idx, bucket.size, bucket.bucketBitLen)) ;
+ log.debug(format("split: %s", bucket)) ;
+ }
+
+ // Create new bucket, which will be the upper bucket.
+ // Low bucket will have the old hash value,
+ // lengthen the hash;
+ // The new will be one more.
+
+
+ bucket.bucketBitLen++ ;
+
+ int hash1 = bucket.hash << 1 ;
+ int hash2 = (bucket.hash << 1) | 0x1 ;
+
+ bucket.hash = hash1 ;
+ //log.debug(format("split: bucket hashes 0x%X 0x%X", hash1, hash2)) ;
+
+ Bucket<V> bucket2 = new Bucket<V>(hash2, bucket.bucketBitLen, bucketSize, bucketCounter++) ;
+
+ if ( Logging && log.isDebugEnabled() )
+ {
+ log.debug(format("split: old bucket %s", bucket)) ;
+ log.debug(format("split: new bucket %s", bucket2)) ;
+ }
+
+ // Split value is where hash2 starts - scaled up to align to full key length
+ int x = hash2 << (31-bucket.bucketBitLen) ;
+
+ // We keep buckets sorted by hash so revealing a new lower bit is
+ // finding by some split value.
+ int split = bucket.findIndex(x) ;
+ if ( split < 0 )
+ split = decodeIndex(split) ;
+
+ arraycopy(bucket.keys, split, bucket2.keys, 0, bucket.size-split) ;
+ arraycopy(bucket.items, split, bucket2.items, 0, bucket.size-split) ;
+
+ if ( NullOut )
+ {
+ Arrays.fill(bucket.keys, split, bucket.size, -1) ;
+ Arrays.fill(bucket.items, split, bucket.size, null) ;
+ }
+ bucket2.size = bucket.size-split ;
+ bucket.size = split ;
+ if ( Logging && log.isDebugEnabled() )
+ {
+ log.debug(format("split: bucket %s", bucket)) ;
+ log.debug(format("split: bucket2 %s", bucket2)) ;
+ }
+ return bucket2 ;
+ }
+
+ // =====================
+
+ @Override
+ public String toString()
+ {
+ IndentedLineBuffer buff = new IndentedLineBuffer() ;
+ dump(buff) ;
+ return buff.asString() ;
+ }
+
+ public void dump()
+ {
+ dump(IndentedWriter.stdout) ;
+ IndentedWriter.stdout.ensureStartOfLine() ;
+ IndentedWriter.stdout.flush() ;
+ }
+
+ private void dump(IndentedWriter out)
+ {
+ out.printf("Bitlen = %d \n" , bitLen) ;
+ out.printf("Dictionary = %d \n" , 1<<bitLen ) ;
+ out.incIndent(4) ;
+ for ( int i = 0 ; i < 1<<bitLen ; i++ )
+ {
+ out.ensureStartOfLine() ;
+ @SuppressWarnings("unchecked")
+ Bucket<V> bucket = (Bucket<V>)dictionary[i] ;
+ out.printf("%02d ", i) ;
+ out.printf(bucket.toString()) ;
+ }
+ out.decIndent(4) ;
+ }
+
+ public void check()
+ {
+ performCheck() ;
+ }
+
+ private final void internalCheck()
+ {
+ if ( Checking )
+ performCheck() ;
+ }
+
+ private final void performCheck()
+ {
+ int len = 1<<bitLen ;
+ if ( len != dictionary.length )
+ error("Dictionary size = %d : expected = %d", dictionary.length, len) ;
+ Bucket<V> prevBucket = null ;
+ for ( int i = 0 ; i < len ; i++ )
+ {
+ @SuppressWarnings("unchecked")
+ Bucket<V> bucket = (Bucket<V>)dictionary[i] ;
+ if ( prevBucket != bucket )
+ {
+ performCheck(i, bucket) ;
+ prevBucket = bucket ;
+ }
+ }
+ }
+
+ private void performCheck(int idx, Bucket<V> bucket)
+ {
+ if ( bucket.keys.length != bucket.items.length )
+ error("Bucket %d arrays of different sizes (keys=%d, items=%d)", idx, bucket.keys.length, bucket.items.length) ;
+ if ( bucket.bucketBitLen > bitLen )
+ error("Bucket %d has bit length longer than the dictionary's (%d, %d)", bucket.bucketBitLen, bitLen) ;
+
+ // Check the bucket hash against the slot it's in.
+ // Convert directory index to bucket hash
+ int tmp = (idx >>> (bitLen-bucket.bucketBitLen)) ;
+ if ( tmp != bucket.hash)
+ error("Bucket %d : hash prefix 0x%X, expected 0x%X : %s", idx, bucket.hash, tmp, bucket) ;
+
+ // Check the contents.
+ int prevKey = Integer.MIN_VALUE ;
+ for ( int i = 0 ; i < bucket.size ; i++ )
+ {
+ if ( bucket.keys[i] < prevKey )
+ error("Bucket %d: Not sorted (slot %d) : %s", idx, i, bucket) ;
+ prevKey = bucket.keys[i] ;
+ int x = index(bucket.keys[i], bucket.bucketBitLen) ;
+ // Check the key is bucket-compatible.
+ if ( x != bucket.hash )
+ error("Bucket %d: Key (0x%08X[0x%X]) does not match the hash (0x%X) : %s",
+ idx, bucket.keys[i], x, bucket.hash, bucket) ;
+ }
+
+ if ( NullOut )
+ {
+ for ( int i = bucket.size ; i < bucket.keys.length ; i++ )
+ {
+ if ( bucket.items[i] != null )
+ error("Bucket %d : overspill in items[%d]", idx, i) ;
+ if ( bucket.keys[i] != -1 )
+ error("Bucket %d : overspill in keys[%d]", idx, i) ;
+ }
+ }
+ }
+
+ private void error(String msg, Object... args)
+ {
+ msg = format(msg, args) ;
+ System.out.println("**************") ;
+ System.out.println(msg) ;
+ System.out.println() ;
+ System.out.flush();
+ try {
+ System.out.println(this) ;
+ } catch (Exception ex) {}
+ throw new StorageException(msg) ;
+ }
+
+ static final class Bucket<V>
+ {
+ // Don't assume unique key
+
+ // List<V> items = new ArrayList<V>() ;
+ // Parallel arrays.
+
+ // Keep sorted for faster find.
+
+ protected final int[] keys ;
+ protected final Object[] items ;
+
+ protected final int id ;
+ protected int hash ;
+ // How many bits are used for storing in this bucket.
+ protected int bucketBitLen ;
+ protected int size ;
+
+ Bucket(int hashValue, int bucketBitLen, int maxSize, int bucketId)
+ {
+ id = bucketId ;
+ keys = new int[maxSize] ;
+ if ( NullOut )
+ Arrays.fill(keys, -1) ;
+ items = new Object[maxSize] ;
+ size = 0 ;
+ this.bucketBitLen = bucketBitLen ;
+ this.hash = hashValue ;
+ }
+
+ // Find the index of the key, return insertion a point if not found as -(i+1)
+ final int findIndex(int key)
+ {
+ int i = binarySearch(keys, 0, size, key) ;
+ return i ;
+ }
+
+ final boolean hasRoom()
+ {
+ return size < keys.length ;
+ }
+
+ // Return true is added a new value
+ final boolean put(int key, V v)
+ {
+ int i = findIndex(key) ;
+ if ( i < 0 )
+ i = decodeIndex(i) ;
+ else
+ {
+ @SuppressWarnings("unchecked")
+ V v2 = (V)items[i] ;
+ if ( v2.equals(v) )
+ return false ;
+ i++ ;
+ }
+
+ if ( ! hasRoom() )
+ throw new StorageException("Bucket overflow") ;
+
+ for ( int j = size ; j > i ; j-- )
+ {
+ keys[j] = keys[j-1] ;
+ items[j] = items[j-1] ;
+ }
+ keys[i] = key ;
+ items[i] = v ;
+ size++ ;
+ return true ;
+ }
+
+ final boolean removeByHash(int key)
+ {
+ int i = findIndex(key) ;
+ if ( i < 0 )
+ return false ;
+ if ( i < size-1 )
+ {
+ System.arraycopy(keys, i+1, keys, i, size-i-1) ;
+ System.arraycopy(items, i+1, items, i, size-i-1) ;
+ }
+ size -- ;
+ if ( NullOut )
+ {
+ keys[size] = -1 ;
+ items[size] = null ;
+ }
+ return true ;
+ }
+
+ // Return the item in slot idx
+ final V get(int key, int idx)
+ {
+ if ( idx >= items.length )
+ return null ;
+ int k = keys[idx] ;
+ if ( k != key )
+ return null ;
+ @SuppressWarnings("unchecked")
+ V v = (V)items[idx] ;
+ return v ;
+ }
+
+ final V find(int key)
+ {
+ int i = findIndex(key) ;
+ if ( i < 0 )
+ return null ;
+ @SuppressWarnings("unchecked")
+ V v = (V)items[i] ;
+ return v ;
+ }
+
+ @Override
+ public String toString()
+ {
+ StringBuilder buff = new StringBuilder() ;
+ buff.append(format("<<[id=%02d, size=%s, len=%d, hash=0x%08X] ", id, size, bucketBitLen, hash)) ;
+ for ( int i = 0 ; i < size ; i++ )
+ {
+ if ( i != 0 )
+ buff.append(" ") ;
+ buff.append(format("(0x%X/0x%08X,%s)",
+ index(keys[i], bucketBitLen),
+ keys[i],
+ items[i].toString())) ;
+
+ }
+ buff.append(">>") ;
+ return buff.toString() ;
+
+ }
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixIndex.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixIndex.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixIndex.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixIndex.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,138 @@
+/**
+ * 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.radix;
+
+import java.util.Iterator ;
+
+import org.openjena.atlas.iterator.Iter ;
+import org.openjena.atlas.iterator.Transform ;
+
+import com.hp.hpl.jena.tdb.base.record.Record ;
+import com.hp.hpl.jena.tdb.base.record.RecordFactory ;
+import com.hp.hpl.jena.tdb.index.RangeIndex ;
+
+public class RadixIndex implements RangeIndex
+{
+ // DEBUG
+ public RadixTree radix = new RadixTree() ;
+ private RecordFactory recordFactory ;
+
+ public RadixIndex(RecordFactory recordFactory)
+ {
+ this.recordFactory = recordFactory ;
+ if ( recordFactory.hasValue() )
+ throw new UnsupportedOperationException("Records with values") ;
+ }
+
+ @Override
+ public Record find(Record record)
+ {
+ RadixNode radixNode = radix.find(record.getKey()) ;
+ if ( radixNode == null )
+ return null ;
+ return record ;
+ }
+
+ @Override
+ public boolean contains(Record record)
+ {
+ return find(record) != null ;
+ }
+
+ @Override
+ public boolean add(Record record)
+ {
+ return radix.insert(record.getKey()) ;
+ }
+
+ @Override
+ public boolean delete(Record record)
+ {
+ return radix.delete(record.getKey()) ;
+ }
+
+ Transform<byte[], Record> t = new Transform<byte[], Record>() {
+ @Override
+ public Record convert(byte[] item)
+ {
+ return recordFactory.create(item) ;
+ }} ;
+
+ @Override
+ public Iterator<Record> iterator()
+ {
+ return Iter.map(radix.iterator(), t) ;
+ }
+
+ @Override
+ public RecordFactory getRecordFactory()
+ {
+ return recordFactory ;
+ }
+
+ @Override
+ public void close()
+ {}
+
+ @Override
+ public boolean isEmpty()
+ {
+ return false ;
+ }
+
+ @Override
+ public void clear()
+ {}
+
+ @Override
+ public void check()
+ {}
+
+ @Override
+ public long size()
+ {
+ return radix.size() ;
+ }
+
+ @Override
+ public void sync()
+ {}
+
+ @Override
+ public Iterator<Record> iterator(Record recordMin, Record recordMax)
+ {
+ return Iter.map(radix.iterator(recordMin.getKey(), recordMax.getKey()), t) ;
+ }
+
+ @Override
+ public Record minKey()
+ {
+ // Better???
+ Iterator<byte[]> iter = radix.iterator() ;
+ if ( !iter.hasNext() ) return null ;
+ return t.convert(radix.iterator().next()) ;
+ }
+
+ @Override
+ public Record maxKey()
+ {
+ return null ;
+ }
+
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixNode.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixNode.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixNode.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixNode.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,286 @@
+/**
+ * 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.radix;
+
+import java.util.HashSet;
+import java.util.List ;
+import java.util.Set;
+
+import org.openjena.atlas.io.IndentedWriter ;
+import org.openjena.atlas.lib.Bytes ;
+import org.openjena.atlas.logging.Log;
+
+
+
+public final class RadixNode //extends PrintableBase implements Printable
+{
+ // Debugging? Needed for traversal?
+ // Not needed for deployment version (we only go down the tree).
+ /*package*/ int parentId ;
+ /*package*/ RadixNode parent ;
+
+ RadixNode(RadixNode parent)
+ {
+ this.parent = parent ;
+ this.parentId = (parent==null)?-1 : parent.id ;
+ }
+ /*
+ * http://en.wikipedia.org/wiki/Radix_tree
+ */
+
+ static int counter = 0 ;
+ int id = (counter++); // Debugging
+
+ // Prefix to this node from node above.
+
+ byte[] prefix ; // Null means "".
+
+ // Position of the end of the prefix in the overall key at this point.
+ int lenFinish ; // Debugging? Use tracking to know these values.
+ int lenStart ;
+
+ // The nodes below this one, corresponding to each possible next byte
+ List<RadixNode> nodes ; // When real, use an array[]; null for leaf.
+
+ // Space cost:
+ // parent
+ // prefix array (so 3 slot overhead)
+ // node array (can use array so 3 slot overhead)
+
+ // More (??) compact would be a giant, segemented array for
+ // each of the node arrays then
+
+ // Optimization (to do): nodes entry of null mean zero length prefix/leaf.
+
+ // --------
+ // Return
+ // Index of first non-matching byte.
+ // - (1+length) if key runs out
+ // prefix length means complete match
+
+ public final int countMatchPrefix(byte[] key)
+ {
+ for ( int i = 0 ; i < prefix.length ; i++ )
+ {
+ // Index into key.
+ int j = i+lenStart ;
+ if ( j == key.length )
+ // Key ran out.
+ return -(i+1) ;
+ if ( prefix[i] != key[j] )
+ return i ;
+ }
+ return prefix.length ;
+ }
+
+ @Override
+ public String toString()
+ {
+ String prefixStr = Bytes.asHex(prefix) ;
+ if ( isLeaf() )
+ return String.format("Leaf[%d/%d]: Length=(%d,%d) :: prefix = %s", id, parentId, lenStart, lenFinish, prefixStr) ;
+
+ StringBuilder b = new StringBuilder() ;
+ for ( RadixNode n : nodes )
+ {
+ b.append(" ") ;
+ b.append(n.id+"") ;
+ }
+ return String.format("Node[%d/%d]: Length=(%d,%d) :: prefix = %s -> Sub:%s", id, parentId, lenStart, lenFinish, prefixStr, b.toString() ) ;
+ }
+
+ /*public*/ void output(final IndentedWriter out)
+ {
+ RadixNodeVisitor<Object> v = new RadixNodeVisitorBase()
+ {
+ @Override
+ public void before(RadixNode node)
+ {
+ String str = node.toString() ;
+ out.print(str) ;
+ out.println();
+ out.incIndent() ;
+ }
+
+ @Override
+ public void after(RadixNode node)
+ {
+ out.decIndent() ;
+ }
+
+ } ;
+ this.visit(v) ;
+ }
+
+ // Re-consider for persistence - this looks into the subnode.
+ // Should pull up first byte (nibble?) for dispatch purposes.
+
+ /** Return the index of the node with this byte as the start of prefix
+ * or -(i+1) for insertion point if not found.
+ */
+ /*package*/ int locate(byte[] bytes, int start)
+ {
+// if ( RadixTree.logging && RadixTree.log.isDebugEnabled() )
+// {
+// RadixTree.log.debug("locate: <"+Bytes.asHex(bytes, start, bytes.length)) ;
+// }
+
+ if ( nodes == null )
+ return -1 ;
+ // Nothing to test -- so is there a subnode of prefix ""
+ if ( bytes.length == start )
+ {
+ if ( nodes.get(0).prefix.length == 0 )
+ return 0 ;
+ else
+ return -(0+1) ;
+ }
+
+ byte b = bytes[start] ;
+
+ // Only the root an have a prefix of no bytes
+ for ( int i = 0 ; i < nodes.size() ; i++ )
+ {
+// if ( RadixTree.logging && RadixTree.log.isDebugEnabled() )
+// RadixTree.log.debug("locate: >"+Bytes.asHex(nodes.get(i).prefix)) ;
+ // Look first byte only.
+ // Prefixes must differ at first byte
+ if ( nodes.get(i).prefix.length == 0 )
+ // No bytes is lowest
+ continue ;
+
+ int x = Bytes.compareByte(b, nodes.get(i).prefix[0]) ;
+ //int x = compare(bytes, start, nodes.get(i).prefix) ;
+ if ( x > 0 )
+ continue ;
+ if ( x < 0 )
+ // Overshoot.
+ return -(i+1) ;
+ //if ( keyByte == b )
+ return i ;
+ }
+ return -(nodes.size()+1) ;
+ }
+
+ private int compare(byte[] bytes, int start, byte[] nextPrefix)
+ {
+ int n = Math.min(bytes.length-start, nextPrefix.length) ;
+
+ for ( int i = 0 ; i < n ; i++ )
+ {
+ byte b1 = bytes[i+start] ;
+ byte b2 = nextPrefix[i] ;
+ if ( b1 == b2 )
+ continue ;
+ // Treat as unsigned values in the bytes.
+ return (b1&0xFF) - (b2&0xFF) ;
+ }
+
+ return (bytes.length-start) - nextPrefix.length ;
+ }
+
+ public void check()
+ {
+ _check(0, new HashSet<Integer>()) ;
+ }
+
+ private void _check(int length, Set<Integer> seen)
+ {
+ // It's a tree and so we seen nodes only once.
+ if ( seen.contains(this) )
+ {
+ error(this, "Node %d already seen",id) ;
+ return ;
+ }
+ seen.add(this.id) ;
+
+ if (parentId != -1 && !seen.contains(parentId) )
+ error(this, "Parent not seen") ;
+
+ if ( prefix == null )
+ error(this, "Null prefix") ;
+
+ if ( lenStart != length )
+ error(this, "Start length error %d/%d", lenStart, length) ;
+
+ if ( lenStart > lenFinish )
+ error(this, "Finish length error") ;
+
+ if ( lenFinish - lenStart != prefix.length )
+ error(this, "Prefix lenth error %d,%d", lenFinish - lenStart, prefix.length) ;
+
+ if ( nodes == null )
+ return ;
+
+ if ( nodes.size() < 2 )
+ error(this, "Internal node has length of "+nodes.size()) ;
+ // Check subnodes are sorted and start with a different byte
+ Set<Integer> bytes = new HashSet<Integer>() ;
+ int last = -2 ;
+ for ( RadixNode n : nodes )
+ {
+ int b = -1 ;
+ if ( n.prefix.length > 0 )
+ b = n.prefix[0] ;
+ if ( last >= b )
+ error(this, "Prefix start not strictly increasing") ;
+ if ( n.parentId != id )
+ error(this, "Child %d points to %d, not parent %d", n.id, n.parentId, id) ;
+ }
+
+ int nextStartLen = length+prefix.length ;
+ for ( RadixNode n : nodes )
+ n._check(nextStartLen, seen) ;
+ }
+
+ public boolean isLeaf()
+ {
+ return nodes == null ;
+ }
+
+ public <T> void visit(RadixNodeVisitor<T> visitor)
+ {
+ _visit(visitor, new HashSet<RadixNode>()) ;
+ }
+
+ private <T> void _visit(RadixNodeVisitor<T> visitor, Set<RadixNode> seen)
+ {
+ if ( seen.contains(this) )
+ {
+ Log.warn(this, "Bad tree: "+id) ;
+ return ;
+ }
+ seen.add(this) ;
+ visitor.before(this) ;
+ if ( nodes != null )
+ {
+ for ( RadixNode n : nodes )
+ n._visit(visitor, seen) ;
+ }
+ visitor.after(this) ;
+ }
+
+ private static void error(RadixNode node, String message, Object... args)
+ {
+ message = String.format(message, args) ;
+ System.err.println("Error: "+node) ;
+ System.err.println(message) ;
+ RadixTree.error(message) ;
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixNodeVisitor.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixNodeVisitor.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixNodeVisitor.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixNodeVisitor.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,32 @@
+/**
+ * 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.radix;
+
+// Or:
+//public interface Visitor<T, R> {
+// public void visit(String key, RadixNode parent, RadixNode node);
+// public R getResult();
+//}
+
+public interface RadixNodeVisitor<R>
+{
+ public void before(RadixNode node) ;
+ public void after(RadixNode node) ;
+ public R result() ;
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixNodeVisitorBase.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixNodeVisitorBase.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixNodeVisitorBase.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixNodeVisitorBase.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,29 @@
+/**
+ * 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.radix;
+
+public class RadixNodeVisitorBase implements RadixNodeVisitor<Object>
+{
+ @Override
+ public void after(RadixNode node) {}
+ @Override
+ public void before(RadixNode node) {}
+ @Override
+ public Object result() { return null ; }
+}