You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jena.apache.org by an...@apache.org on 2011/11/07 14:36:34 UTC
svn commit: r1198733 [6/13] - in /incubator/jena/Scratch/AFS/Dev/trunk:
src-archive/riot/comms/ src-archive/riot/comms/client/
src-archive/riot/comms/server0/ src-archive/riot/comms/server1/nio/
src-archive/riot/comms/server1/socket/ src-archive/riot/c...
Modified: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixTree.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixTree.java?rev=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixTree.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixTree.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,755 +16,755 @@
* 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() ;
- }
+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() ;
+ }
}
Modified: 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=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipList.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipList.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,442 +16,442 @@
* 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) ;
- }
+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) ;
+ }
}
Modified: 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=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipListException.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipListException.java Mon Nov 7 13:36:30 2011
@@ -1,4 +1,4 @@
-/**
+/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
@@ -16,27 +16,27 @@
* limitations under the License.
*/
-package structure.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) ;
- }
+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) ;
+ }
}
Modified: 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=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipListIterator.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipListIterator.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,59 +16,59 @@
* 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") ; }
-
+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") ; }
+
}
Modified: 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=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipListNode.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/skiplist/SkipListNode.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,66 +16,66 @@
* 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("} ]") ;
- }
+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("} ]") ;
+ }
}