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 [3/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/radix/RadixTree.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixTree.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixTree.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixTree.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,771 @@
+/**
+ * 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.nio.ByteBuffer ;
+import java.util.ArrayDeque ;
+import java.util.ArrayList ;
+import java.util.Deque ;
+import java.util.Iterator ;
+import java.util.NoSuchElementException ;
+
+import org.openjena.atlas.AtlasException ;
+import org.openjena.atlas.io.IndentedWriter ;
+import org.openjena.atlas.iterator.Iter ;
+import org.openjena.atlas.lib.Bytes ;
+import org.slf4j.Logger ;
+import org.slf4j.LoggerFactory ;
+
+/* http://en.wikipedia.org/wiki/Radix_tree */
+public final class RadixTree
+{
+ // TODO
+ // More checking, all if'ed out
+ // Iteration
+ // Value?
+ // Architecture : action visitor pattern - find&do (overhead?)
+
+ static boolean logging = true ;
+ static final boolean checking = true ;
+ static final byte[] bytes0 = new byte[]{} ;
+
+ static Logger log = LoggerFactory.getLogger(RadixTree.class) ;
+ private RadixNode root = null ;
+
+ public RadixNode getRoot() { return root ; }
+
+ private interface Action { RadixNode exec(byte[] key, RadixNode node, int N, RadixNode parentNode) ; }
+
+ /** Find the starting point - call the action */
+ private static RadixNode applicator(RadixNode root, byte[] key, Action action)
+ {
+ // A convoluted way to "return" with three results by calling on to a handler.
+ // Assumes root is not null.
+ RadixNode nodePrev = null ; // Last node.
+ RadixNode node = root ; // The current node.
+
+ for(;;)
+ {
+ // Does the prefix (partially) match?
+ int N = node.countMatchPrefix(key) ;
+ if ( N < node.prefix.length ) // Includes negative N
+ return action.exec(key, node, N, nodePrev) ;
+ // else matched up to end of prefix.
+ // Longer or same length key.
+ int j = node.locate(key, node.lenFinish) ;
+ if ( j < 0 || j == node.nodes.size() )
+ // No match across subnodes - this node is the point of longest match.
+ return action.exec(key, node, node.prefix.length, nodePrev) ;
+ // There is a next node down to try.
+ nodePrev = node ;
+ node = node.nodes.get(j) ;
+ }
+ // Does not happen
+ }
+
+ private RadixNode _find(byte[] key)
+ {
+ RadixNode node = search(key) ;
+ int N = node.countMatchPrefix(key) ;
+
+ if ( N == node.prefix.length && node.lenFinish == key.length && node.isLeaf() )
+ // Exact match
+ return node ;
+ return null ;
+ }
+
+ public RadixNode find(byte[] key)
+ {
+ if ( root == null )
+ return null ;
+ return applicator(root, key, findAction) ;
+ }
+
+
+ private static Action findAction = new Action() {
+
+ @Override
+ public RadixNode exec(byte[] key, RadixNode node, int N, RadixNode nodePrev)
+ {
+ if ( N == node.prefix.length && node.lenFinish == key.length && node.isLeaf() )
+ // Exact match
+ return node ;
+ return null ;
+ }
+ } ;
+
+ private static Action identityAction = new Action() {
+
+ @Override
+ public RadixNode exec(byte[] key, RadixNode node, int N, RadixNode nodePrev)
+ {
+ return node ;
+ }
+ } ;
+
+ private RadixNode search(byte[] key)
+ {
+ if ( root == null )
+ return null ;
+ return applicator(root, key, identityAction) ;
+ }
+
+ // Return top changed node.
+ private static Action insertAction = new Action()
+ {
+ @Override
+ public RadixNode exec(byte[] key, RadixNode node, int N, RadixNode nodePrev)
+ {
+ if (logging && log.isDebugEnabled() )
+ {
+ log.debug("insert: search => "+node) ;
+ log.debug("insert N = "+N) ;
+ }
+ /* Cases:
+ * Not a leaf node (tested above):
+ * 0/ key same as prefix and it's a leaf => already there
+ * 1/ key longer than prefix : N == node.prefix.length
+ * 2/ key same as prefix : N == node.prefix.length but not already in tree.
+ * 3/ key shorter than prefix : 0 <= N < node.prefix.length
+ * 4/ key diverges from prefix : N < 0
+ *
+ */
+
+ // Key already present - we ended at a leaf.
+ if ( N == node.prefix.length && node.lenFinish == key.length && node.isLeaf() )
+ {
+ if (logging && log.isDebugEnabled() )
+ log.debug("insert: Already present") ;
+ return null ;
+ }
+
+ /* Actions
+ * 1 => split, then as 3 ?
+ * 2 => split, then as 3 ?
+ * 3 => new subnode.
+ * 4 => new subnode ""
+ */
+
+ if ( N == node.prefix.length )
+ {
+ // We will modify the node array
+ if ( node.isLeaf() )
+ {
+ node.nodes = new ArrayList<RadixNode>() ;
+ RadixNode n = new RadixNode(node) ;
+ n.prefix = bytes0 ;
+ n.lenStart = node.lenFinish ;
+ n.lenFinish = node.lenFinish ;
+ n.nodes = null ;
+ node.nodes.add(0, n) ;
+ }
+
+ // Key ends here but it's not a leaf already
+ byte[] prefixNew = Bytes.copyOf(key, node.lenFinish, key.length - node.lenFinish) ;
+
+ if (logging && log.isDebugEnabled() )
+ log.debug("Prefix new : "+Bytes.asHex(prefixNew)) ;
+
+ RadixNode node1 = new RadixNode(node) ;
+ node1.prefix = prefixNew ;
+ node1.lenStart = node.lenFinish ;
+ node1.lenFinish = key.length ;
+ node1.nodes = null ; // It's a leaf.
+
+ int i = node.locate(prefixNew, 0) ;
+
+ if ( i > 0 )
+ error("Duplicate start byte") ;
+ i = -(i+1) ;
+ node.nodes.add(i, node1) ;
+ return node ;
+ }
+
+ // Key diverges or is shorter than prefix.
+ byte[] prefix1 ;
+ if ( N < 0 )
+ {
+ // Short key.
+ prefix1 = bytes0 ;
+ N = -(N+1) ;
+ }
+ else
+ prefix1 = Bytes.copyOf(key, N+node.lenStart) ;
+
+ // The two parts of the prefix.
+ byte[] prefix0 = Bytes.copyOf(node.prefix, 0, N) ;
+ byte[] prefix2 = Bytes.copyOf(node.prefix, N) ;
+
+ if (logging && log.isDebugEnabled() )
+ {
+ log.debug("Prefix0 : "+Bytes.asHex(prefix0)) ;
+ log.debug("Prefix1 : "+Bytes.asHex(prefix1)) ;
+ log.debug("Prefix2 : "+Bytes.asHex(prefix2)) ;
+ }
+ // This is the new leaf due to key added.
+ RadixNode node1 = new RadixNode(node) ;
+ node1.prefix = prefix1 ;
+ node1.lenStart = node.lenStart+N ;
+ node1.lenFinish = key.length ;
+ node1.nodes = null ; // ??
+
+ // This the tail of the original data
+ RadixNode node2 = new RadixNode(node) ;
+ node2.prefix = prefix2 ;
+ node2.lenStart = node.lenStart+N ;
+ node2.lenFinish = node.lenFinish ;
+ node2.nodes = null ;
+
+ // Swap if necessary
+ if ( Bytes.compare(prefix1, prefix2) > 0 )
+ { RadixNode t = node2 ; node2 = node1 ; node1 = t ; }
+
+ // Spread the original subnodes nodes over the new subnodes.
+ if (node.nodes != null )
+ {
+ int split = node.locate(node1.prefix, 0) ;
+ if ( checking )
+ {
+ if ( split >= 0 )
+ error("Found prefix for new inserted key") ;
+ }
+ split = -(split+1) ;
+ if ( split > 0 )
+ node1.nodes = new ArrayList<RadixNode>() ;
+ if ( split < node.nodes.size() )
+ node2.nodes = new ArrayList<RadixNode>() ;
+
+ if ( logging && log.isDebugEnabled() )
+ log.debug("Spread nodes: "+split) ;
+
+ for ( int i = 0 ; i < split ; i++ )
+ {
+ RadixNode x = node.nodes.get(i) ;
+ // Fix the parents of subnodes.
+ x.parentId = node1.id ;
+ node1.nodes.add(x) ;
+ }
+
+ for ( int i = split ; i < node.nodes.size() ; i++ )
+ {
+ RadixNode x = node.nodes.get(i) ;
+ x.parentId = node2.id ;
+ node2.nodes.add(x) ;
+ }
+ }
+
+ // Alter the node in-place.
+ node.prefix = prefix0 ;
+ node.lenFinish = prefix0.length+node.lenStart ;
+ if ( node.nodes == null )
+ node.nodes = new ArrayList<RadixNode>() ;
+ else
+ node.nodes.clear() ;
+ node.nodes.add(node1) ;
+ node.nodes.add(node2) ;
+ return node ;
+ }
+ } ;
+
+ public boolean insert(byte[] key)
+ {
+ if ( root == null )
+ {
+ root = new RadixNode(null) ;
+ root.prefix = key ;
+ root.lenStart = 0 ;
+ root.lenFinish = key.length ;
+ root.nodes = null ;
+ return true ;
+ }
+
+ return applicator(root, key, insertAction) != null ;
+ }
+
+ /** Insert - return true if the trie changed */
+ private boolean _insert(byte[] key)
+ {
+ if (logging && log.isDebugEnabled() )
+ log.debug("Insert : "+Bytes.asHex(key)) ;
+
+ key = Bytes.copyOf(key) ; // ??? Always copy later so no need - check
+ if ( root == null )
+ {
+ root = new RadixNode(null) ;
+ root.prefix = key ;
+ root.lenStart = 0 ;
+ root.lenFinish = key.length ;
+ root.nodes = null ;
+ return true ;
+ }
+
+ // Location the node that leads to the key.
+ // Returned node will have:
+ // prefix longer than or equal to the key
+ //
+
+ final RadixNode node = search(key) ;
+ if (logging && log.isDebugEnabled() )
+ log.debug("insert: search => "+node) ;
+
+ int N = node.countMatchPrefix(key) ;
+ if (logging && log.isDebugEnabled() )
+ log.debug("insert N = "+N) ;
+
+ /* Cases:
+ * Not a leaf node (tested above):
+ * 0/ key same as prefix and it's a leaf => already there
+ * 1/ key shorter than prefix : 0 <= N < node.prefix.length
+ * 2/ key diverges from prefix : N < 0
+ * 3/ key longer than prefix : N == node.prefix.length
+ * 4/ key same as prefix : N == node.prefix.length
+ * but not already in tree.
+ */
+
+ // Key already present - we ended at a leaf.
+ if ( N == node.prefix.length && node.lenFinish == key.length && node.isLeaf() )
+ {
+ if (logging && log.isDebugEnabled() )
+ log.debug("insert: Already present") ;
+ return false ;
+ }
+
+ /* Actions
+ * 1 => split, then as 3 ?
+ * 2 => split, then as 3 ?
+ * 3 => new subnode.
+ * 4 => new subnode ""
+ */
+
+ if ( N < node.prefix.length )
+ {
+ // Cases 1 and 2.
+ // Key diverges or is shorter
+ byte[] prefix1 ;
+ if ( N < 0 )
+ {
+ // Short key.
+ prefix1 = bytes0 ;
+ N = -(N+1) ;
+ }
+ else
+ prefix1 = Bytes.copyOf(key, N+node.lenStart) ;
+
+ byte[] prefix0 = Bytes.copyOf(node.prefix, 0, N) ;
+ // Remainder of prefix : Bytes.slice
+ byte[] prefix2 = Bytes.copyOf(node.prefix, N) ;
+
+ if (logging && log.isDebugEnabled() )
+ {
+ log.debug("Prefix0 : "+Bytes.asHex(prefix0)) ;
+ log.debug("Prefix1 : "+Bytes.asHex(prefix1)) ;
+ log.debug("Prefix2 : "+Bytes.asHex(prefix2)) ;
+ }
+ // This is the new leaf due to key added.
+ RadixNode node1 = new RadixNode(node) ;
+ node1.prefix = prefix1 ;
+ node1.lenStart = node.lenStart+N ;
+ node1.lenFinish = key.length ;
+ node1.nodes = null ; // ??
+
+ // This the tail of the original data
+ RadixNode node2 = new RadixNode(node) ;
+ node2.prefix = prefix2 ;
+ node2.lenStart = node.lenStart+N ;
+ node2.lenFinish = node.lenFinish ;
+ node2.nodes = null ;
+
+ // Swap if necessary
+ if ( Bytes.compare(prefix1, prefix2) > 0 )
+ {
+ RadixNode t = node2 ; node2 = node1 ; node1 = t ;
+ }
+
+ // Spread the original subnodes nodes over the new subnodes.
+ if (node.nodes != null )
+ {
+ int split = node.locate(node1.prefix, 0) ;
+ if ( checking )
+ {
+ if ( split > 0 )
+ error("Found prefix for new inserted key") ;
+ }
+ split = -(split+1) ;
+ if ( split > 0 )
+ node1.nodes = new ArrayList<RadixNode>() ;
+ if ( split < node.nodes.size() )
+ node2.nodes = new ArrayList<RadixNode>() ;
+
+ if ( logging && log.isDebugEnabled() )
+ log.debug("Spread nodes: "+split) ;
+
+ for ( int i = 0 ; i < split ; i++ )
+ {
+ RadixNode x = node.nodes.get(i) ;
+ x.parentId = node1.id ;
+ node1.nodes.add(x) ;
+ }
+
+ for ( int i = split ; i < node.nodes.size() ; i++ )
+ {
+ RadixNode x = node.nodes.get(i) ;
+ x.parentId = node2.id ;
+ node2.nodes.add(x) ;
+ }
+ }
+
+ node.prefix = prefix0 ;
+ node.lenFinish = prefix0.length+node.lenStart ;
+ if ( node.nodes == null )
+ node.nodes = new ArrayList<RadixNode>() ;
+ else
+ node.nodes.clear() ;
+ node.nodes.add(node1) ;
+ node.nodes.add(node2) ;
+ return true ;
+ }
+
+ // We will modify the node array
+ if ( node.isLeaf() )
+ {
+ node.nodes = new ArrayList<RadixNode>() ;
+ RadixNode n = new RadixNode(node) ;
+ n.prefix = bytes0 ;
+ n.lenStart = node.lenFinish ;
+ n.lenFinish = node.lenFinish ;
+ n.nodes = null ;
+ node.nodes.add(0, n) ;
+ }
+
+ byte[] prefixNew = Bytes.copyOf(key, node.lenFinish, key.length - node.lenFinish) ;
+
+ if (logging && log.isDebugEnabled() )
+ log.debug("Prefix new : "+Bytes.asHex(prefixNew)) ;
+
+ RadixNode node1 = new RadixNode(node) ;
+ node1.prefix = prefixNew ;
+ node1.lenStart = node.lenFinish ;
+ node1.lenFinish = key.length ;
+ node1.nodes = null ; // It's a leaf.
+
+ int i = node.locate(prefixNew, 0) ;
+
+ if ( i > 0 )
+ error("Duplicate start byte") ;
+ i = -(i+1) ;
+ node.nodes.add(i, node1) ;
+ return true ;
+ }
+
+ private static Action deleteAction = new Action()
+ {
+ @Override
+ public RadixNode exec(byte[] key, RadixNode leaf, int N, RadixNode node)
+ {
+ // Key not already present - not a full match (short, diverges) or not-a-leaf.
+ if ( N != leaf.prefix.length || leaf.lenFinish != key.length || ! leaf.isLeaf() )
+ {
+ if (logging && log.isDebugEnabled() )
+ log.debug("delete: Not present") ;
+ return null ;
+ }
+
+ if (logging && log.isDebugEnabled() )
+ {
+ log.debug("delete: "+Bytes.asHex(key)) ;
+ log.debug(" "+leaf) ;
+ log.debug(" "+node) ;
+ }
+
+ if ( node == null )
+ {
+ // Root - deleting the last key.
+ return leaf ;
+ }
+
+ // Then work on the parent.
+ int i = node.locate(key, leaf.lenStart) ;
+ if ( i < 0 )
+ error("Can't find child in parent") ;
+
+ {
+ RadixNode x = node.nodes.remove(i) ;
+ if ( checking && x != leaf )
+ error("Removing the wrong node") ;
+ }
+
+ if ( node.nodes.size() == 1 )
+ {
+ // This other node subnode.
+ // Collapse n into node - that is, pull up all n into node.
+
+ RadixNode n = node.nodes.remove(0) ;
+ if ( logging && log.isDebugEnabled() )
+ {
+ log.debug("Collapse node") ;
+ log.debug(" node: "+node) ;
+ log.debug(" n : "+n) ;
+ }
+
+ int len = node.prefix.length + n.prefix.length ;
+ node.nodes = n.nodes ;
+ // fix up children of n
+ if ( node.nodes != null )
+ {
+ for ( RadixNode x : node.nodes )
+ {
+ x.parent = node ;
+ x.parentId = node.id ;
+ }
+ }
+ node.lenFinish = n.lenFinish ;
+
+ byte [] a = new byte[len] ;
+ System.arraycopy(node.prefix, 0, a, 0, node.prefix.length) ;
+ System.arraycopy(n.prefix, 0, a, node.prefix.length, n.prefix.length) ;
+ if ( logging && log.isDebugEnabled() )
+ log.debug("New prefix: "+Bytes.asHex(a)) ;
+
+ node.prefix = a ;
+ if ( logging && log.isDebugEnabled() )
+ log.debug(" --> : "+node) ;
+ }
+ return node ;
+ }
+ } ;
+ /** Delete - return true if the tree changed (i.e the key was present and so was removed) */
+ public boolean delete(byte[] key)
+ {
+ if ( root == null )
+ return false ;
+ boolean b = root.isLeaf() ;
+ RadixNode n = applicator(root, key, deleteAction) ;
+ if ( b && n != null )
+ root = null ;
+ return n != null ;
+ }
+
+ public void print()
+ {
+ if ( root == null )
+ {
+ System.out.println("<empty>") ;
+ return ;
+ }
+ root.output(IndentedWriter.stdout) ;
+ IndentedWriter.stdout.flush();
+ }
+
+ public long size()
+ {
+ if ( root == null )
+ return 0 ;
+
+ RadixNodeVisitor<Object> v = new RadixNodeVisitorBase()
+ {
+ int count = 0 ;
+ @Override
+ public void before(RadixNode node)
+ {
+ if (node.isLeaf())
+ count++ ;
+ }
+
+ @Override
+ public Object result()
+ { return count ; }
+ } ;
+ root.visit(v) ;
+ return (Integer)v.result() ;
+ }
+
+ public Iterator<byte[]> iterator() { return iterator(null, null) ; }
+
+ public Iterator<byte[]> iterator(byte[] start, byte[] finish)
+ {
+ if ( logging && log.isDebugEnabled() )
+ {
+ log.debug("iterator: start: "+((start==null)?"null":Bytes.asHex(start))) ;
+ log.debug("iterator: finish: "+((finish==null)?"null":Bytes.asHex(finish))) ;
+ }
+
+ if ( root == null )
+ {
+ if ( logging && log.isDebugEnabled() )
+ log.debug("iterator: empty tree") ;
+ return Iter.nullIterator() ;
+ }
+ return new RadixIterator(root, start, finish) ;
+ }
+
+ private static class RadixIterator implements Iterator<byte[]>
+ {
+ RadixNode node ;
+ ByteBuffer slot = null ;
+ byte[] finish = null ;
+
+ RadixIterator(RadixNode root, byte[] start, byte[] finish)
+ {
+
+ this.finish = finish ;
+ node = root ;
+ int N = -1 ;
+
+ if ( start != null )
+ {
+ // Find ....
+
+ slot = ByteBuffer.allocate(start.length) ;
+ for(;;)
+ {
+ // Does the prefix (partially) match?
+ N = node.countMatchPrefix(start) ;
+ int numMatch = N ;
+ if ( numMatch < 0 )
+ numMatch = -(numMatch+1) ;
+ // else matched up to end of prefix.
+
+ // Copy all bytes that match.
+ slot = appendBytes(node.prefix, 0, numMatch, slot) ;
+
+ if ( N < node.prefix.length ) // Includes negative N
+ break ;
+ // Longer or same length key.
+ int j = node.locate(start, node.lenFinish) ;
+ if ( j < 0 || j == node.nodes.size() )
+ // No match across subnodes - this node is the point of longest match.
+ break ;
+ // There is a next node down to try.
+ node = node.nodes.get(j) ;
+ }
+ }
+ else
+ slot = ByteBuffer.allocate(10) ; //Reallocating?
+ // Now move until leaf.
+ while(!node.isLeaf())
+ {
+ // Copy as we go.
+ slot = appendBytes(node.prefix, 0, node.prefix.length, slot) ;
+ node = node.nodes.get(0) ;
+ }
+ // But we need to track the key for copying reasons.
+ if ( false && logging && log.isDebugEnabled() )
+ {
+ log.debug("Iterator start: "+node) ;
+ log.debug("Iterator start: "+slot) ;
+ }
+
+ }
+
+ /** Copy bytes from the array ([], start, length) to the end of a ByteBuffer */
+ static ByteBuffer appendBytes(byte[] array, int start, int length, ByteBuffer bb)
+ {
+ if ( bb.position()+length > bb.capacity() )
+ {
+ ByteBuffer bb2 = ByteBuffer.allocate(bb.capacity()*2 ) ;
+ System.arraycopy(bb.array(), 0, bb2.array(), 0, bb.position()) ;
+ return bb2 ;
+ }
+// System.arraycopy(bb.array(), bb.position(), array, 0, length) ;
+// bb.position((bb.position()+length)) ;
+ try {
+ bb.put(array, start, length) ;
+ } catch (java.nio.BufferOverflowException ex)
+ {
+ System.err.println() ;
+ System.err.println(bb) ;
+ System.err.printf("([%d], %d, %d)", array.length, start, length) ;
+ throw ex ;
+ }
+ return bb ;
+ }
+
+ @Override
+ public boolean hasNext()
+ {
+ if ( slot != null )
+ return true ;
+ // Move to next leaf.
+ // TODO
+
+ return false ;
+ }
+
+ @Override
+ public byte[] next()
+ {
+ if ( ! hasNext() )
+ throw new NoSuchElementException() ;
+ byte[] x = slot.array() ;
+ slot = null ;
+ return x ;
+ }
+
+ @Override
+ public void remove()
+ { throw new UnsupportedOperationException() ; }
+
+ }
+
+ public void printLeaves()
+ {
+ if ( root == null )
+ {
+ System.out.println("Tree: empty") ;
+ return ;
+ }
+
+ final Deque<Byte> x = new ArrayDeque<Byte>() ;
+ RadixNodeVisitor<Object> v = new RadixNodeVisitorBase()
+ {
+ @Override
+ public void before(RadixNode node)
+ {
+ for ( byte b : node.prefix )
+ x.addLast(b) ;
+ if ( node.isLeaf() )
+ System.out.print(" "+x) ;
+ }
+
+ @Override
+ public void after(RadixNode node)
+ {
+ for ( int i = node.lenStart ; i < node.lenFinish ; i++ )
+ x.removeLast() ;
+ }
+
+ } ;
+
+
+ root.visit(v) ;
+ System.out.println() ;
+ System.out.flush() ;
+ }
+
+ static void error(String string)
+ {
+ throw new AtlasException(string) ;
+ }
+
+ public void check()
+ {
+ if ( root != null )
+ root.check() ;
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipList.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipList.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipList.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipList.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,457 @@
+/**
+ * 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.skiplist;
+
+import static java.lang.String.format ;
+
+import java.util.Iterator ;
+import java.util.Random ;
+
+import org.openjena.atlas.io.IndentedLineBuffer ;
+import org.openjena.atlas.io.IndentedWriter ;
+import org.openjena.atlas.io.Printable ;
+import org.openjena.atlas.iterator.Iter ;
+import org.openjena.atlas.lib.RandomLib ;
+import org.slf4j.Logger ;
+import org.slf4j.LoggerFactory ;
+
+final
+public class SkipList <R extends Comparable<? super R>> implements Printable, Iterable<R>
+{
+ static public boolean Checking = false ;
+ static public /*final*/ boolean Logging = false ; // Even faster than log.isDebugEnabled.
+ private static Logger log = LoggerFactory.getLogger(SkipList.class) ;
+
+ // Expensive? Do a caching call?
+ private static Random rand = RandomLib.qrandom ;
+ static int DftMaxLevel = 20 ;
+
+ // This list
+ int maxLevel = DftMaxLevel ; // Maximum levels allowed for this list
+ int currentLevel = 0 ; // Current largest in-use level
+ // This node is special. It does not have a record - it's just the forward pointers.
+ SkipListNode<R> root = null ;
+ int size = 0 ;
+ //private int randomSeed;
+
+ //SkipListNode<R> infinity = new SkipListNode<R>(null, 0) ; -- use nulls instead.
+
+ public SkipList()
+ {
+ root = new SkipListNode<R>(null, DftMaxLevel) ;
+ }
+
+ public SkipList(int maxLevel)
+ {
+ this.maxLevel = maxLevel ;
+ this.currentLevel = 0 ;
+ root = new SkipListNode<R>(null, maxLevel) ;
+ //randomSeed = RandomLib.random.nextInt() | 0x0100; // ensure nonzero
+ }
+
+ public boolean contains(R record)
+ { return find(record) != null ; }
+
+ public R find(R record)
+ {
+ if ( record == null )
+ return null ;
+
+ SkipListNode<R> x = root ;
+ for ( int i = currentLevel-1 ; i >= 0; i-- )
+ {
+ while (cmpNR(x.get(i), record) <= 0 )
+ x = x.get(i) ;
+ }
+ if ( cmpNR(x, record) == 0 ) return x.record ;
+ return null ;
+ }
+
+ private SkipListNode<R> findBefore(R record)
+ {
+ SkipListNode<R> x = root ;
+ // Find strictly less than node.
+ for ( int i = currentLevel-1 ; i >= 0; i-- )
+ {
+ while (cmpNR(x.get(i), record) < 0 )
+ x = x.get(i) ;
+ }
+ return x ;
+ }
+
+
+ SkipListNode<R> notANode = new SkipListNode<R>(null, 0) ;
+
+ public R findDebug(R record)
+ {
+ SkipListNode<R> x = root ;
+ // Find node.
+ // Speed up by avaoid unnecessary comparisons (see Skiplist cookbook 3.5)
+
+ SkipListNode<R> lastCompare = notANode ;
+
+ loop1: for ( int i = currentLevel-1 ; i >= 0; i-- )
+ {
+ System.out.printf("Search level=%-2d %s\n",i, x) ;
+ while ( true )
+ {
+ SkipListNode<R> y = x.get(i) ;
+ if ( lastCompare == y )
+ {
+ // Same as before.
+ System.out.printf("Skip: %s\n", y) ;
+ continue loop1;
+ }
+
+ //
+ System.out.printf("Compare %s %s\n", y, record) ;
+ int cmp = cmpNR(y, record) ;
+ lastCompare = y ;
+
+ if ( cmp == 0 )
+ {
+ System.out.printf("Found: %s\n", x.get(i)) ;
+ return x.get(i).record ;
+ }
+ if ( cmp > 0 )
+ break ;
+ x = y ;
+ System.out.printf("Advance: %s \n", x) ;
+ }
+ }
+ System.out.println("Not found") ;
+ return null ;
+ }
+
+ public R insert(R record)
+ {
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format(">> Insert : %s", record)) ;
+
+ Object update[] = new Object[maxLevel] ;
+ SkipListNode<R> x = opSetUp(update, record) ;
+
+ if ( cmpNR(x, record) == 0 )
+ {
+ // Replace
+ x.record = record ;
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format("<< Insert : %s (replace)", record)) ;
+ return x.record ;
+ }
+
+ int lvl = randomLevel() ;
+ if ( lvl > currentLevel )
+ {
+ // If very large insert, point to first node (root)
+ for ( int i = currentLevel ; i < lvl ; i++ )
+ update[i] = root ;
+ currentLevel = lvl ;
+ }
+ x = new SkipListNode<R>(record, lvl) ;
+ for ( int i = 0 ; i < lvl ; i++ )
+ {
+ @SuppressWarnings("unchecked")
+ SkipListNode<R> y = ((SkipListNode<R>)update[i]) ;
+
+// x.set(i, y.get(i)) ;
+// y.set(i, x) ;
+
+ x.forward[i] = y.get(i) ;
+ y.forward[i] = x ;
+ }
+
+ if ( Logging && log.isDebugEnabled() )
+ log.debug(format("<< Insert : %s (addition)", record)) ;
+
+ // New
+ size++ ;
+ return null ;
+ }
+
+ public R delete(R record)
+ {
+ SkipListNode<?> update[] = new SkipListNode<?>[maxLevel] ;
+ SkipListNode<R> x = opSetUp(update, record) ;
+
+ if ( cmpNR(x, record) != 0 )
+ // Not found.
+ return null ;
+
+ record = x.record ;
+
+ for ( int i = 0 ; i < currentLevel ; i++ )
+ {
+ @SuppressWarnings("unchecked")
+ SkipListNode<R> y = ((SkipListNode<R>)update[i]) ;
+ if ( y.get(i) != x )
+ break ;
+ //y.set(i, x.get(i)) ;
+ y.forward[i] = x.get(i) ;
+ // free x
+ // Reset current level.
+ // XXX
+ }
+ size -- ;
+ return record ;
+ }
+
+ // Common setup for insert and delete
+ final private SkipListNode<R> opSetUp(Object[] update, R record)
+ {
+ SkipListNode<R> x = root ;
+
+ // Find less than or equal node, remembering pointers as we go down levels.
+ for ( int i = currentLevel-1 ; i >= 0; i-- )
+ {
+ while ( cmpNR(x.get(i), record) < 0 )
+ x = x.get(i) ;
+ update[i] = x ;
+ }
+ // Advance to same or greater
+ return x.get(0) ;
+ }
+
+ public boolean isEmpty()
+ {
+ return root.get(0) == null ;
+ }
+
+ public int size()
+ {
+ return size ;
+ }
+
+ // Min - inclusive; max - exclusive
+
+ public Iterator<R> iterator(R min, R max)
+ {
+ SkipListNode<R> x = null ;
+ if ( min != null )
+ {
+ x = findBefore(min) ;
+ x = x.get(0) ; // Move forward (possibly over)
+ }
+ else
+ x = root.get(0) ;
+ return new SkipListIterator<R>(x, max) ;
+
+ }
+
+ @Override
+ public Iterator<R> iterator()
+ {
+ return iterator(null,null) ;
+ }
+
+ public Iterable<R> records()
+ {
+ return Iter.iter(iterator()) ;
+ }
+
+ public Iterable<R> records(R min, R max)
+ {
+ return Iter.iter(iterator(min, max)) ;
+ }
+
+ @Override
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder() ;
+ boolean first = true ;
+ for ( R r : this )
+ {
+ if ( ! first ) sb.append(" ") ;
+ first = false ;
+ sb.append(r) ;
+ }
+ return sb.toString() ;
+ }
+
+ @Override
+ public void output(IndentedWriter out)
+ {
+ SkipListNode<R> x = root ;
+
+ boolean first = true ;
+ while( x != null )
+ {
+ if ( ! first ) out.print(" ") ;
+ first = false ;
+ x.output(out) ;
+ x = x.get(0) ;
+ }
+ }
+
+ // -----
+// /**
+// * Returns a random level for inserting a new node.
+// * Hardwired to k=1, p=0.5, max 31 (see above and
+// * Pugh's "Skip List Cookbook", sec 3.4).
+// *
+// * This uses the simplest of the generators described in George
+// * Marsaglia's "Xorshift RNGs" paper. This is not a high-quality
+// * generator but is acceptable here.
+// */
+
+ // Very, very slow for some reason. Linear lists?
+// private int randomLevel() {
+// int x = randomSeed;
+// x ^= x << 13;
+// x ^= x >>> 17;
+// randomSeed = x ^= x << 5;
+// if ((x & 0x8001) != 0) // test highest and lowest bits
+// return 0;
+// int level = 1;
+// while (((x >>>= 1) & 1) != 0) ++level;
+// return level;
+// }
+
+
+ private static final int OneOverP = 2;
+ // Log distibution.
+ private int randomLevel()
+ {
+ int level = 1;
+ while ( rand.nextInt(OneOverP) == 0 && level < maxLevel )
+ level ++ ;
+ return level ;
+ }
+ // -----
+
+ // The infinite node is marked by null pointers.
+ private static <R extends Comparable<? super R>> int cmpNR(SkipListNode<R> node, R record)
+ {
+ if ( node == null )
+ return (record == null ) ? 0 : 1 ;
+ return cmpRR(node.record, record) ;
+ }
+
+ static <R extends Comparable<? super R>> int cmpRR(R record1, R record2)
+ {
+ // A null record is the lowest element (exists in the root node)
+ if ( record1 == null )
+ return (record2 == null ) ? 0 : -1 ;
+ if ( record2 == null )
+ return 1 ;
+
+ return record1.compareTo(record2) ;
+ }
+
+ private static <R extends Comparable<? super R>> int cmpNodeRecord(SkipListNode<R> node1, SkipListNode<R> node2)
+ {
+ if ( node1 == null )
+ return (node2 == null ) ? 0 : 1 ;
+ if ( node2 == null )
+ return -1 ;
+ return cmpRR(node1.record, node2.record) ;
+ }
+
+ public void check()
+ { checkList() ; }
+
+ private static <R extends Comparable<? super R>> void internalCheck(SkipList<R> list)
+ {
+ if ( ! Checking )
+ return ;
+ if ( list == null )
+ error("Null pointer for list") ;
+ list.checkList() ;
+ }
+
+ private void checkList()
+ {
+ SkipListNode<R> x = root ;
+ while( x != null )
+ {
+ check(x) ;
+ x = x.get(0) ;
+ }
+ R rec1 = null ;
+ for ( R rec2 : this )
+ {
+ if ( rec1 != null )
+ {
+ if ( rec1.compareTo(rec2) > 0 )
+ error("Output order %s,%s", rec1, rec2) ;
+ }
+ rec1 = rec2 ;
+ }
+ }
+
+ private void check(SkipListNode<R> node)
+ {
+ if ( node == null )
+ error("check: Null node") ;
+ SkipListNode<R> z = null ;
+ for ( int i = node.forward.length-1 ; i >= 0 ; i-- )
+ {
+ SkipListNode<R> n = node.get(i) ;
+ if ( cmpNodeRecord(z,n) < 0 )
+ error("Greater node has lesser record: %s %s", debug(z), debug(n)) ;
+ if ( n != null && n.forward.length < i )
+ error("Pointing to a smaller node %s %s", debug(z), debug(n)) ;
+ z = n ;
+ }
+ }
+
+ private static <R extends Comparable<? super R>> String debug(SkipListNode<R> node)
+ {
+ if ( node == null ) return "_" ;
+ return node.debug() ;
+ }
+
+ public String debug()
+ {
+ if ( isEmpty() )
+ return "<empty>" ;
+
+ IndentedLineBuffer out = new IndentedLineBuffer() ;
+
+ boolean first = true ;
+ SkipListNode<R> x = root ;
+ while ( x != null )
+ {
+ //if ( ! first ) out.print(" ") ;
+ first = false ;
+ x.outputFull(out) ;
+ out.println();
+ x = x.get(0) ;
+ }
+ return out.toString() ;
+ }
+
+ public static <R extends Comparable<? super R>> String label(SkipListNode<R> node)
+ {
+ if ( node == null ) return "_" ;
+ return Integer.toString(node.id) ;
+ }
+
+
+ private static void error(String format, Object ... args)
+ {
+ String x = format(format, args) ;
+ System.err.print(x) ;
+ if ( ! x.endsWith("\n") )
+ System.err.println() ;
+ else
+ x = x.substring(0, x.length()-1) ;
+ throw new SkipListException(x) ;
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipListException.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipListException.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipListException.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipListException.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,42 @@
+/**
+ * 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.skiplist;
+
+public class SkipListException extends RuntimeException
+{
+ public SkipListException()
+ {
+ super() ;
+ }
+
+ public SkipListException(String message)
+ {
+ super(message) ;
+ }
+
+ public SkipListException(String message, Throwable cause)
+ {
+ super(message, cause) ;
+ }
+
+ public SkipListException(Throwable cause)
+ {
+ super(cause) ;
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipListIterator.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipListIterator.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipListIterator.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipListIterator.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,74 @@
+/**
+ * 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.skiplist;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+final
+public class SkipListIterator <R extends Comparable<? super R>> implements Iterator<R>
+{
+ boolean finished = false ;
+ SkipListNode<R> node ;
+ R limit ; // Exclusive
+
+ SkipListIterator(SkipListNode<R> node)
+ {
+ this(node, null) ;
+ }
+
+ SkipListIterator(SkipListNode<R> node, R limit)
+ {
+ this.node = node ;
+ this.limit = limit ;
+ }
+
+ @Override
+ public boolean hasNext()
+ {
+ if ( finished ) return false ;
+ if ( node != null )
+ {
+ if ( limit != null && SkipList.cmpRR(node.record, limit) >= 0 )
+ {
+ finished = true ;
+ return false ;
+ }
+ }
+
+ return node != null ;
+ }
+
+ @Override
+ public R next()
+ {
+ if ( ! hasNext() )
+ throw new NoSuchElementException("SkipListIterator") ;
+
+ // Move on - test for limit is doen in hasNext
+ R rec = node.record ;
+ node = node.get(0) ;
+ return rec ;
+ }
+
+ @Override
+ public void remove()
+ { throw new UnsupportedOperationException("SkipListIterator.remove") ; }
+
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipListNode.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipListNode.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipListNode.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipListNode.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,81 @@
+/**
+ * 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.skiplist;
+
+import static java.lang.String.format ;
+import org.openjena.atlas.io.IndentedLineBuffer ;
+import org.openjena.atlas.io.IndentedWriter ;
+import org.openjena.atlas.io.Printable ;
+
+final
+public class SkipListNode <R extends Comparable<? super R>> implements Printable
+{
+ static int counter = 1 ;
+ int id = (counter++) ;
+
+ R record ;
+ // Arrays are a bit yukky in Java - they are objects+length so the overhead is 3*4 bytes (32 bit Java).
+ // Alternative is link lists across and down.
+
+ SkipListNode<R> forward[] ;
+
+ @SuppressWarnings("unchecked")
+ SkipListNode(R record, int len)
+ {
+ this.record = record ;
+ //forward = new ArrayList<SkipListNode<R>>(len) ;
+ forward = (SkipListNode<R>[])new SkipListNode<?>[len] ;
+ }
+
+ SkipListNode<R> get(int i)
+ { return forward[i] ; }
+
+// void set(int i, SkipListNode<?> v)
+// { forward[i] = v ; }
+
+ public String debug()
+ {
+ IndentedLineBuffer buff = new IndentedLineBuffer() ;
+ this.outputFull(buff) ;
+ return buff.toString() ;
+ }
+
+ @Override
+ public String toString() { return debug() ; }
+
+ @Override
+ public void output(IndentedWriter out)
+ {
+ out.print(record.toString()) ;
+ }
+
+ public void outputFull(IndentedWriter out)
+ {
+ out.print(format("[ id=%-2d rec=%-4s {", id, record)) ;
+ boolean first = true ;
+ for ( int i = 0 ; i < forward.length ; i++ )
+ {
+ if ( ! first ) out.print(" ") ;
+ first = false ;
+ SkipListNode<R> n = get(i) ;
+ out.print(SkipList.label(n)) ;
+ }
+ out.print("} ]") ;
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/tree/TreeException.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/tree/TreeException.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/tree/TreeException.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/tree/TreeException.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,42 @@
+/**
+ * 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.tree;
+
+public class TreeException extends RuntimeException
+{
+ public TreeException()
+ {
+ super() ;
+ }
+
+ public TreeException(String message)
+ {
+ super(message) ;
+ }
+
+ public TreeException(String message, Throwable cause)
+ {
+ super(message, cause) ;
+ }
+
+ public TreeException(Throwable cause)
+ {
+ super(cause) ;
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/tree/TreeNode.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/tree/TreeNode.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/tree/TreeNode.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/tree/TreeNode.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,272 @@
+/**
+ * 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.tree;
+
+import java.util.ArrayList ;
+import java.util.Iterator ;
+import java.util.List ;
+
+import org.openjena.atlas.io.IndentedWriter ;
+import org.openjena.atlas.io.PrintUtils ;
+import org.openjena.atlas.io.Printable ;
+
+
+/** Simple binary tree nodes, including operations that apply to all trees */
+
+public class TreeNode<R extends Comparable<R>> implements Printable
+{
+ private TreeNode<R> left ;
+ private TreeNode<R> right ;
+ private R record ;
+
+ public TreeNode(R record)
+ {
+ this.record = record ;
+ }
+
+ public TreeNode(R record, TreeNode<R> left, TreeNode<R> right)
+ {
+ this(record) ;
+ this.left = left ;
+ this.right = right ;
+ }
+
+ public R insert(R newRecord)
+ { return insert(newRecord, true) ; }
+
+ // Unbalanced insert - return the record if the record already present, else null if new.
+ public R insert(R newRecord, boolean duplicates)
+ {
+ int x = this.record.compareTo(newRecord) ;
+
+ if ( x > 0 )
+ {
+ if ( left == null )
+ {
+ left = new TreeNode<R>(newRecord) ;
+ return null ;
+ }
+ return left.insert(newRecord, duplicates) ;
+ }
+
+ if ( x == 0 && ! duplicates )
+ return this.record ;
+
+ if ( right == null )
+ {
+ right = new TreeNode<R>(newRecord) ;
+ return null ;
+ }
+ return right.insert(newRecord, duplicates) ;
+ }
+
+ // Naming: rotateRight means move the left child up to the root and the root to the right
+ // The left is the pivot
+ // == shift right
+ // == clockwise
+ // This is the wikipedia naming but that does not extend to the double rotations.
+ // Different books have different namings, based on the location of the pivot (which would be a left rotate)
+ // But when we talk about double rotations, the pivotLeft terminolgy works better.
+ // pivotLeft (= case left left) , pivotLeftRight,
+
+
+ // (K1 (K2 A B) C) ==> (K2 A (K1 B C))
+ final public void rotateRight() { pivotLeft() ; }
+ final public void pivotLeft()
+ {
+ // Validity checking?
+ checkNotNull(left) ;
+
+ R k1 = record ;
+ R k2 = left.record ;
+ TreeNode<R> a = left.left ;
+ TreeNode<R> b = left.right ;
+ TreeNode<R> c = right ;
+
+ // Or reuse left.
+ // TreeNode t = new TreeNode(k1, b, c) ;
+ TreeNode<R> t = left ; t.record = k1 ; t.left = b ; t.right = c ;
+
+ this.record = k2 ;
+ this.left = a ;
+ this.right = t ;
+ }
+
+ // (K1 A (K2 B C)) ==> (K2 (K1 A B) C)
+ final public void rotateLeft() { pivotRight() ; }
+ final public void pivotRight()
+ {
+ checkNotNull(right) ;
+ R k1 = record ;
+ R k2 = right.record ;
+ TreeNode<R> a = left ;
+ TreeNode<R> b = right.left ;
+ TreeNode<R> c = right.right ;
+
+ //TreeNode t = new TreeNode(k1, a, b) ;
+ TreeNode<R> t = right ; right.record = k1 ; right.left = a ; right.right = b ;
+
+ this.record = k2 ;
+ this.left = t ;
+ this.right = c ;
+ }
+
+ // LeftRight
+ // (K3 (K1 A (K2 B C)) D) ==> (K2 (K1 A B) (K3 C D))
+ //final public void rotateDoubleRight() { pivotLeftRight() ; }
+ final public void pivotLeftRight()
+ {
+ checkNotNull(left) ;
+ checkNotNull(left.right) ;
+ R k3 = record ;
+ R k1 = left.record ;
+ R k2 = left.right.record ;
+ TreeNode<R> a = left.left ;
+ TreeNode<R> b = left.right.left ;
+ TreeNode<R> c = left.right.right ;
+ TreeNode<R> d = right ;
+
+ this.record = k2 ;
+// this.left = new TreeNode<R>(k1, a, b) ; // Reuse LeftRight
+// this.right = new TreeNode<R>(k3, c, d) ; // reuse Left
+
+ // XXX WRONG?
+ this.left = left.right ;
+ /*this.left.record = k1 ;*/ this.left.left = a ; this.left.right = b ;
+ this.right = left ;
+ /*this.right.record = k3 ;*/ this.right.left = c ; this.right.right = d ;
+
+ }
+
+ // RightLeft
+ // (K1 A (K3 (K2 B C) D)) ==> (K2 (K1 A B) (K3 C D))
+ //final public void rotateDoubleLeft() { pivotRightLeft() ; }
+ final public void pivotRightLeft()
+ {
+ checkNotNull(right) ;
+ checkNotNull(right.left) ;
+
+ R k1 = record ;
+ R k3 = right.record ;
+ R k2 = right.left.record ;
+ TreeNode<R> a = left ;
+ TreeNode<R> b = right.left.left ;
+ TreeNode<R> c = right.left.right ;
+ TreeNode<R> d = right.right ;
+
+ this.record = k2 ;
+// this.left = new TreeNode<R>(k1, a, b) ; // replace by in-place / RightLeft
+// this.right = new TreeNode<R>(k3, c, d) ; // Right
+
+ // XXX WRONG?
+ this.left = left.right ;
+ /*this.left.record = k1 ; */this.left.left = a ; this.left.right = b ;
+ this.right = left ;
+ /*this.right.record = k3 ;*/ this.right.left = c ; this.right.right = d ;
+
+ }
+
+ // Not in this class
+ public Iterator<R> records(R min, R max)
+ {
+ return null ;
+ }
+
+ //public Iterator<R> records()
+
+ public List<R> records()
+ {
+ List<R> x = new ArrayList<R>() ;
+ records(x) ;
+ return x ; // .iterator() ;
+ }
+
+ public void records(List<R> x)
+ {
+ if ( left != null )
+ left.records(x) ;
+ x.add(record) ;
+ if ( right != null )
+ right.records(x) ;
+
+ }
+
+ @Override
+ public String toString() { return PrintUtils.toString(this) ; }
+
+ public void outputNested(IndentedWriter out)
+ {
+ if ( left == null && right == null )
+ {
+ out.print(record) ;
+ return ;
+ }
+
+ // At least one of left and right.
+
+ out.print('(') ;
+ out.print(record) ;
+ out.print(' ') ;
+ out.incIndent() ;
+ out.println() ;
+ if ( left != null )
+ left.output(out) ;
+ else
+ out.print("undef") ;
+ out.println();
+
+ if ( right != null )
+ right.output(out) ;
+ else
+ out.print("undef") ;
+ out.print(')') ;
+ out.decIndent() ;
+ }
+
+ @Override
+ public void output(IndentedWriter out)
+ {
+ if ( left == null && right == null )
+ {
+ out.print(record) ;
+ return ;
+ }
+
+ out.print('(') ;
+ out.print(record) ;
+ if ( left != null )
+ {
+ out.print(' ') ;
+ left.output(out) ;
+ }
+ if ( right != null )
+ {
+ out.print(' ') ;
+ right.output(out) ;
+ }
+ out.print(')') ;
+ }
+
+ // Inline me :-)
+ final private static void checkNotNull(Object object)
+ {
+ if ( object == null )
+ throw new TreeException("Null") ;
+ }
+}