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 ; }
+}