jena-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From a...@apache.org
Subject svn commit: r1198733 [4/13] - in /incubator/jena/Scratch/AFS/Dev/trunk: src-archive/riot/comms/ src-archive/riot/comms/client/ src-archive/riot/comms/server0/ src-archive/riot/comms/server1/nio/ src-archive/riot/comms/server1/socket/ src-archive/riot/c...
Date Mon, 07 Nov 2011 13:36:34 GMT
Modified: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/Tuple4.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/Tuple4.java?rev=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/Tuple4.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/Tuple4.java Mon Nov  7 13:36:30 2011
@@ -1,4 +1,4 @@
-/**
+/*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
@@ -16,62 +16,62 @@
  * limitations under the License.
  */
 
-package migrate.lib.tuple;
-
-import org.openjena.atlas.lib.Lib;
-
-public class Tuple4<T> extends ZTuple<T>
-{
-    final T item1 ;
-    final T item2 ;
-    final T item3 ;
-    final T item4 ;
-
-    protected Tuple4(T item1, T item2, T item3, T item4) 
-    {
-        this.item1 = item1 ; 
-        this.item2 = item2 ; 
-        this.item3 = item3 ;
-        this.item4 = item4 ;
-    }
-    
-    @Override
-    protected final boolean equalElements(ZTuple<?> x)
-    {
-        Tuple4<?> x1 = (Tuple4<?>)x ;
-        return  Lib.equal(x1.item1, item1) && 
-                Lib.equal(x1.item2, item2) &&
-                Lib.equal(x1.item3, item3) &&
-                Lib.equal(x1.item4, item4) ;
-    }
-    
-    @Override
-    public final T get(int idx)
-    {
-        switch (idx)
-        {
-            case 0: return item1 ;
-            case 1: return item2 ;
-            case 2: return item3 ;
-            case 3: return item4 ;
-            default: throw new TupleException("Out of bounds: "+idx) ;
-        }
-    }
-
-    @Override
-    public final int hashCode()
-    {
-        int x = Lib.hashCodeObject(item1, ZTuple.NulItemHashCode) ; 
-        x = x<<1 ^ Lib.hashCodeObject(item2, ZTuple.NulItemHashCode) ; 
-        x = x<<1 ^ Lib.hashCodeObject(item3, ZTuple.NulItemHashCode) ; 
-        x = x<<1 ^ Lib.hashCodeObject(item4, ZTuple.NulItemHashCode) ; 
-        return x ;
-    }
-
-    @Override
-    public final int size()
-    {
-        return 4 ;
-    }
-
+package migrate.lib.tuple;
+
+import org.openjena.atlas.lib.Lib;
+
+public class Tuple4<T> extends ZTuple<T>
+{
+    final T item1 ;
+    final T item2 ;
+    final T item3 ;
+    final T item4 ;
+
+    protected Tuple4(T item1, T item2, T item3, T item4) 
+    {
+        this.item1 = item1 ; 
+        this.item2 = item2 ; 
+        this.item3 = item3 ;
+        this.item4 = item4 ;
+    }
+    
+    @Override
+    protected final boolean equalElements(ZTuple<?> x)
+    {
+        Tuple4<?> x1 = (Tuple4<?>)x ;
+        return  Lib.equal(x1.item1, item1) && 
+                Lib.equal(x1.item2, item2) &&
+                Lib.equal(x1.item3, item3) &&
+                Lib.equal(x1.item4, item4) ;
+    }
+    
+    @Override
+    public final T get(int idx)
+    {
+        switch (idx)
+        {
+            case 0: return item1 ;
+            case 1: return item2 ;
+            case 2: return item3 ;
+            case 3: return item4 ;
+            default: throw new TupleException("Out of bounds: "+idx) ;
+        }
+    }
+
+    @Override
+    public final int hashCode()
+    {
+        int x = Lib.hashCodeObject(item1, ZTuple.NulItemHashCode) ; 
+        x = x<<1 ^ Lib.hashCodeObject(item2, ZTuple.NulItemHashCode) ; 
+        x = x<<1 ^ Lib.hashCodeObject(item3, ZTuple.NulItemHashCode) ; 
+        x = x<<1 ^ Lib.hashCodeObject(item4, ZTuple.NulItemHashCode) ; 
+        return x ;
+    }
+
+    @Override
+    public final int size()
+    {
+        return 4 ;
+    }
+
 }

Modified: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/TupleException.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/TupleException.java?rev=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/TupleException.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/TupleException.java Mon Nov  7 13:36:30 2011
@@ -1,4 +1,4 @@
-/**
+/*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
@@ -16,9 +16,9 @@
  * limitations under the License.
  */
 
-package migrate.lib.tuple;
-
-public class TupleException extends RuntimeException
-{
-    public TupleException(String msg) { super(msg) ; }
+package migrate.lib.tuple;
+
+public class TupleException extends RuntimeException
+{
+    public TupleException(String msg) { super(msg) ; }
 }

Modified: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/TupleN.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/TupleN.java?rev=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/TupleN.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/TupleN.java Mon Nov  7 13:36:30 2011
@@ -1,4 +1,4 @@
-/**
+/*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
@@ -16,57 +16,57 @@
  * limitations under the License.
  */
 
-package migrate.lib.tuple;
-
-import org.openjena.atlas.lib.Lib;
-
-public final class TupleN<T> extends ZTuple<T>
-{
-    T[] tuple ;
-
-    protected TupleN(T...tuple) 
-    {
-        this.tuple = tuple ;
-    }
-    
-    @Override
-    public T[] tuple() { return tuple ; }
-    
-    @Override
-    protected boolean equalElements(ZTuple<?> x)
-    {
-        TupleN<?> x1 = (TupleN<?>)x ;
-        for ( int i = 0 ; i < tuple.length ; i++ )
-        {
-            Object obj1 = x1.tuple[i] ;
-            Object obj2 = tuple[i] ;
-            if ( ! Lib.equal(obj1, obj2) )
-                return false ;
-        }
-        return true ;
-    }
-    
-    @Override
-    public T get(int idx)
-    {
-        if ( idx < 0 || idx >= tuple.length )
-            throw new TupleException("Out of bounds: "+idx) ;
-        return tuple[idx] ;
-    }
-
-    @Override
-    public int hashCode()
-    {
-        int x = 0 ;
-        for ( T t: tuple)
-            x = x<<1 ^ Lib.hashCodeObject(t, ZTuple.NulItemHashCode) ; 
-        return x ;
-    }
-
-    @Override
-    public int size()
-    {
-        return tuple.length ;
-    }
-
+package migrate.lib.tuple;
+
+import org.openjena.atlas.lib.Lib;
+
+public final class TupleN<T> extends ZTuple<T>
+{
+    T[] tuple ;
+
+    protected TupleN(T...tuple) 
+    {
+        this.tuple = tuple ;
+    }
+    
+    @Override
+    public T[] tuple() { return tuple ; }
+    
+    @Override
+    protected boolean equalElements(ZTuple<?> x)
+    {
+        TupleN<?> x1 = (TupleN<?>)x ;
+        for ( int i = 0 ; i < tuple.length ; i++ )
+        {
+            Object obj1 = x1.tuple[i] ;
+            Object obj2 = tuple[i] ;
+            if ( ! Lib.equal(obj1, obj2) )
+                return false ;
+        }
+        return true ;
+    }
+    
+    @Override
+    public T get(int idx)
+    {
+        if ( idx < 0 || idx >= tuple.length )
+            throw new TupleException("Out of bounds: "+idx) ;
+        return tuple[idx] ;
+    }
+
+    @Override
+    public int hashCode()
+    {
+        int x = 0 ;
+        for ( T t: tuple)
+            x = x<<1 ^ Lib.hashCodeObject(t, ZTuple.NulItemHashCode) ; 
+        return x ;
+    }
+
+    @Override
+    public int size()
+    {
+        return tuple.length ;
+    }
+
 }

Modified: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/ZTuple.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/ZTuple.java?rev=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/ZTuple.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/ZTuple.java Mon Nov  7 13:36:30 2011
@@ -1,4 +1,4 @@
-/**
+/*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
@@ -16,90 +16,90 @@
  * limitations under the License.
  */
 
-package migrate.lib.tuple;
-
-import java.util.Arrays;
-import java.util.List;
-
-import org.openjena.atlas.lib.ColumnMap;
-import org.openjena.atlas.lib.Lib;
-import org.openjena.atlas.lib.NotImplemented;
-
-/** Tuples - use less space by specific implementations for 
- *  various sizes.  Saves the array overhead of 3 slots.  
- *  And 3 slots for two items might amount to a lot of space.
- */
-public abstract class ZTuple<T>
-{
-    static final int NulItemHashCode = 3 ;
-
-    public abstract T get(int idx) ;
-    // Immutable
-    // public abstract T set(int idx, T item) ;
-
-    public List<T> asList()
-    {
-        return Arrays.asList(tuple()) ;
-    }
-    
-    public T[] tuple() 
-    {
-        int N = size() ;
-        @SuppressWarnings("unchecked")
-        T[] array = (T[])new Object[N] ;
-        for (int i = 0; i < N; i++)
-            array[i] = get(i) ;
-        return array ;
-    }
-
-    /** Return a tuple with the column mapping applied */
-    public ZTuple<T> map(ColumnMap colMap)
-    {
-        //return colMap.map(this) ;
-        throw new NotImplemented("Tuple.map") ; 
-    }
-    
-    /** Return a tuple with the column mapping reversed */
-    public ZTuple<T> unmap(ColumnMap colMap)
-    {
-        //return colMap.unmap(this) ;
-        throw new NotImplemented("Tuple.unmap") ; 
-    }
-    
-    public abstract int size() ;
-    
-    // Cache?
-    @Override
-    public int hashCode()
-    { 
-        int x = 99 ;
-        for ( int i = 0; i < size() ; i++)
-            x ^= get(i).hashCode() ;
-        return x ;  
-    }
-    
-    @Override
-    public boolean equals(Object other) 
-    {
-        if ( this == other ) return true ;
-        if ( ! ( other instanceof ZTuple<?> ) )
-            return false ;
-        ZTuple<?> x = (ZTuple<?>)other ;
-        if ( x.size() != this.size() )
-            return false ;
-        return equalElements(x) ;
-    }
-        
-    protected boolean equalElements(ZTuple<?> tuple)
-    {
-        for ( int i = 0 ; i < tuple.size() ; i++ )
-        {
-            Object obj1 = get(i) ;
-            Object obj2 = tuple.get(i) ;
-            if ( ! Lib.equal(obj1, obj2) )
-                return false ;
-        }
-        return true ; 
-    }
-    
+package migrate.lib.tuple;
+
+import java.util.Arrays;
+import java.util.List;
+
+import org.openjena.atlas.lib.ColumnMap;
+import org.openjena.atlas.lib.Lib;
+import org.openjena.atlas.lib.NotImplemented;
+
+/** Tuples - use less space by specific implementations for 
+ *  various sizes.  Saves the array overhead of 3 slots.  
+ *  And 3 slots for two items might amount to a lot of space.
+ */
+public abstract class ZTuple<T>
+{
+    static final int NulItemHashCode = 3 ;
+
+    public abstract T get(int idx) ;
+    // Immutable
+    // public abstract T set(int idx, T item) ;
+
+    public List<T> asList()
+    {
+        return Arrays.asList(tuple()) ;
+    }
+    
+    public T[] tuple() 
+    {
+        int N = size() ;
+        @SuppressWarnings("unchecked")
+        T[] array = (T[])new Object[N] ;
+        for (int i = 0; i < N; i++)
+            array[i] = get(i) ;
+        return array ;
+    }
+
+    /** Return a tuple with the column mapping applied */
+    public ZTuple<T> map(ColumnMap colMap)
+    {
+        //return colMap.map(this) ;
+        throw new NotImplemented("Tuple.map") ; 
+    }
+    
+    /** Return a tuple with the column mapping reversed */
+    public ZTuple<T> unmap(ColumnMap colMap)
+    {
+        //return colMap.unmap(this) ;
+        throw new NotImplemented("Tuple.unmap") ; 
+    }
+    
+    public abstract int size() ;
+    
+    // Cache?
+    @Override
+    public int hashCode()
+    { 
+        int x = 99 ;
+        for ( int i = 0; i < size() ; i++)
+            x ^= get(i).hashCode() ;
+        return x ;  
+    }
+    
+    @Override
+    public boolean equals(Object other) 
+    {
+        if ( this == other ) return true ;
+        if ( ! ( other instanceof ZTuple<?> ) )
+            return false ;
+        ZTuple<?> x = (ZTuple<?>)other ;
+        if ( x.size() != this.size() )
+            return false ;
+        return equalElements(x) ;
+    }
+        
+    protected boolean equalElements(ZTuple<?> tuple)
+    {
+        for ( int i = 0 ; i < tuple.size() ; i++ )
+        {
+            Object obj1 = get(i) ;
+            Object obj2 = tuple.get(i) ;
+            if ( ! Lib.equal(obj1, obj2) )
+                return false ;
+        }
+        return true ; 
+    }
+    
 }

Modified: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/_Triple.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/_Triple.java?rev=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/_Triple.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/migrate/lib/tuple/_Triple.java Mon Nov  7 13:36:30 2011
@@ -1,4 +1,4 @@
-/**
+/*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
@@ -16,20 +16,20 @@
  * limitations under the License.
  */
 
-package migrate.lib.tuple;
-
-import com.hp.hpl.jena.graph.Node;
-
-public class _Triple extends Tuple3<Node>
-{
-
-    public _Triple(Node s, Node p, Node o)
-    {
-        super(s, p, o) ;
-    }
-
-    public Node getSubject()    { return get(0) ; }
-    public Node getPredicate()  { return get(1) ; }
-    public Node getObject()     { return get(2) ; }
-    
+package migrate.lib.tuple;
+
+import com.hp.hpl.jena.graph.Node;
+
+public class _Triple extends Tuple3<Node>
+{
+
+    public _Triple(Node s, Node p, Node o)
+    {
+        super(s, p, o) ;
+    }
+
+    public Node getSubject()    { return get(0) ; }
+    public Node getPredicate()  { return get(1) ; }
+    public Node getObject()     { return get(2) ; }
+    
 }

Modified: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/OrderedSet.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/OrderedSet.java?rev=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/OrderedSet.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/OrderedSet.java Mon Nov  7 13:36:30 2011
@@ -1,4 +1,4 @@
-/**
+/*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
@@ -16,51 +16,51 @@
  * limitations under the License.
  */
 
-package structure;
-
-import org.openjena.atlas.io.Printable;
-
-import java.util.Iterator;
-import java.util.List;
-
-// May change to allow duplicates -- OrderedBag
-public interface OrderedSet<T extends Comparable<? super T>> extends Iterable<T>, Printable
-{
-    /** Clear all elements */ 
-    public void clear() ;
-    
-    // This could be java.util.SortedSet - except that's quite large.
-
-    public boolean contains(T item);
-
-    public boolean isEmpty();
-    
-    public T search(T item);
-    
-    public boolean add(T item);
-    
-    public boolean remove(T item);
-    
-    public T max() ;
-
-    public T min() ;
-    
-    // hashCode
-    // equals
-    // Comparator<? super T>  comparator() ; 
-    // subset
-    // headSet
-    // tailSet
-    
-    /** Number of elements in the set */
-    public long size() ;
-    
-    /** Size by actually walking the tree and counting - mainly for testing */
-    public long count() ;
-    public void checkTree() ;
-    public List<T> elements() ;
-    
-    @Override
-    public Iterator<T> iterator() ;
-    public Iterator<T> iterator(T startInc, T endExc) ;
+package structure;
+
+import org.openjena.atlas.io.Printable;
+
+import java.util.Iterator;
+import java.util.List;
+
+// May change to allow duplicates -- OrderedBag
+public interface OrderedSet<T extends Comparable<? super T>> extends Iterable<T>, Printable
+{
+    /** Clear all elements */ 
+    public void clear() ;
+    
+    // This could be java.util.SortedSet - except that's quite large.
+
+    public boolean contains(T item);
+
+    public boolean isEmpty();
+    
+    public T search(T item);
+    
+    public boolean add(T item);
+    
+    public boolean remove(T item);
+    
+    public T max() ;
+
+    public T min() ;
+    
+    // hashCode
+    // equals
+    // Comparator<? super T>  comparator() ; 
+    // subset
+    // headSet
+    // tailSet
+    
+    /** Number of elements in the set */
+    public long size() ;
+    
+    /** Size by actually walking the tree and counting - mainly for testing */
+    public long count() ;
+    public void checkTree() ;
+    public List<T> elements() ;
+    
+    @Override
+    public Iterator<T> iterator() ;
+    public Iterator<T> iterator(T startInc, T endExc) ;
 }

Modified: 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=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/avl/AVL.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/avl/AVL.java Mon Nov  7 13:36:30 2011
@@ -1,4 +1,4 @@
-/**
+/*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
@@ -16,833 +16,833 @@
  * 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()) ;
-    }
+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()) ;
+    }
 }

Modified: 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=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/avl/AvlIterator.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/avl/AvlIterator.java Mon Nov  7 13:36:30 2011
@@ -1,4 +1,4 @@
-/**
+/*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
@@ -16,169 +16,169 @@
  * 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 ;
-    }
-
+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 ;
+    }
+
 }



Mime
View raw message