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 2012/01/02 21:36:23 UTC
svn commit: r1226543 - in /incubator/jena/Scratch/AFS/Dev/trunk:
src-dev/dev/ src-lib/main/java/structure/radix/
src-lib/test/java/structure/radix/
Author: andy
Date: Mon Jan 2 20:36:22 2012
New Revision: 1226543
URL: http://svn.apache.org/viewvc?rev=1226543&view=rev
Log:
Progress radix trees
Added:
incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RLib.java
incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixIterator.java
Modified:
incubator/jena/Scratch/AFS/Dev/trunk/src-dev/dev/RunAFS.java
incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixIndex.java
incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixNode.java
incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixTree.java
incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/RadixRun.java
incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/TestRadix.java
Modified: incubator/jena/Scratch/AFS/Dev/trunk/src-dev/dev/RunAFS.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-dev/dev/RunAFS.java?rev=1226543&r1=1226542&r2=1226543&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-dev/dev/RunAFS.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-dev/dev/RunAFS.java Mon Jan 2 20:36:22 2012
@@ -18,12 +18,14 @@
package dev;
+import static structure.radix.RLib.str ;
+
+import java.nio.ByteBuffer ;
import java.util.Iterator ;
-import org.openjena.atlas.iterator.Iter ;
-import org.openjena.atlas.iterator.Transform ;
import org.openjena.atlas.logging.Log ;
import storage.varrecord.VarRecordBuffer ;
+import structure.radix.RadixRun ;
import structure.radix.RadixTree ;
import com.hp.hpl.jena.iri.IRI ;
@@ -49,84 +51,76 @@ public class RunAFS
static byte[] key5 = { 2 , 4 , 3 , 1 } ;
static byte[] key6 = { 0 , 1 , 2 , 3 , 4 } ;
- static void insertPrint( RadixTree t, byte[] k)
+ static void insert(RadixTree t, byte[] k)
{
System.out.println("Insert: "+str(k)) ;
t.insert(k) ;
t.print() ;
- Iterator<byte[]> iter = t.iterator() ;
+ t.check() ;
+ }
+
+ static void print( RadixTree t)
+ {
+ t.print() ;
+ Iterator<ByteBuffer> iter = t.iterator() ;
for ( ; iter.hasNext() ; )
{
- byte[] v = iter.next();
- System.out.println(" "+str(k)) ;
+ ByteBuffer v = iter.next();
+ System.out.println(" = "+str(v)) ;
}
- System.out.println("Tree : "+str(t)) ;
System.out.println() ;
- t.check() ;
}
public static void main(String ... args) throws Exception
{
+ RadixRun.main(args) ; exit(0) ;
- {
- RadixTree t = new RadixTree() ;
- insertPrint(t, key1) ;
- insertPrint(t, key2) ;
- insertPrint(t, key3) ;
- insertPrint(t, key4) ;
- insertPrint(t, key5) ;
- insertPrint(t, key6) ;
- exit(0) ;
- }
-
-
-
-
+ // RadixTree TODO
+ // Read through and check/optimize.
+ // ByteBuffers throughout => var length.
+// {
+// RadixTree.logging = false ;
+// RadixTree t = new RadixTree() ;
+// insert(t, key1) ;
+// //print(t) ;
+//
+// insert(t, key2) ;
+// //print(t) ;
+//
+// insert(t, key3) ;
+// //print(t) ;
+//
+// exit(0) ;
+// }
+ RadixTree.logging = false ;
+ RadixTree.checking = true ;
RadixTree t = new RadixTree() ;
byte[][] keys = { key1, key2, key3, key4, key5, key6 } ;
int i = 0 ;
for ( byte[]k : keys )
{
+ insert(t, k) ;
+ for ( int j = 0 ; j < i ; j++ )
+ {
+ if ( t.find(keys[j]) == null )
+ System.out.println("**** Not found: "+str(keys[j])) ;
+ }
i++ ;
- insertPrint(t, k) ;
}
- for ( Iterator<byte[]> iter = t.iterator() ; iter.hasNext() ; )
+ System.out.println() ;
+ t.print() ;
+
+ for ( Iterator<ByteBuffer> iter = t.iterator() ; iter.hasNext() ; )
{
- byte[] r = iter.next() ;
+ ByteBuffer r = iter.next() ;
System.out.println(str(r)) ;
}
-
- t.print() ;
}
- private static String str(RadixTree rt)
- {
- Iterator<String> iter = Iter.map(rt.iterator(), new Transform<byte[], String>(){
- @Override
- public String convert(byte[] item)
- {
- return "["+str(item)+"]" ;
- }}) ;
- return Iter.asString(iter, ", ") ;
- }
-
-// private static String str(byte[] array)
-// {
-// StringBuilder sb = new StringBuilder() ;
-// String sep = "" ;
-// for ( byte b : array )
-// {
-// sb.append(sep) ;
-// sb.append(b) ;
-// sep = ", " ;
-// }
-// return sb.toString() ;
-// }
-
- static IRIFactory iriFactory = new IRIFactory();
+ static IRIFactory iriFactory = new IRIFactory();
static {
// IRIFactory.iriImplementation() ...
iriFactory.useSpecificationIRI(true);
@@ -238,28 +232,9 @@ public class RunAFS
vrb.delete(1) ;
if ( PRINT ) vrb.dump();
System.out.println(vrb) ;
-
-
- }
-
- private static String str(byte[] bytes)
- {
- StringBuilder sb = new StringBuilder() ;
- char sep = 0 ;
- for ( byte b : bytes )
- {
- if ( sep != 0 )
- sb.append(sep) ;
- else
- sep = ' ' ;
-
- sb.append(String.format("%02X", b)) ;
- }
- return sb.toString() ;
}
-
- // ---- Helpers
+ // ---- Helpers
private static final String NL = "\n" ;
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RLib.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RLib.java?rev=1226543&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RLib.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RLib.java Mon Jan 2 20:36:22 2012
@@ -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.radix;
+
+import java.nio.ByteBuffer ;
+import java.util.Iterator ;
+
+import org.openjena.atlas.iterator.Iter ;
+import org.openjena.atlas.iterator.Transform ;
+
+public class RLib
+{
+ public static String str(ByteBuffer bytes)
+ {
+ StringBuilder sb = new StringBuilder() ;
+ char sep = 0 ;
+ for ( int i = bytes.position() ; i < bytes.limit() ; i++ )
+ {
+ byte b = bytes.get(i) ;
+ if ( sep != 0 )
+ sb.append(sep) ;
+ else
+ sep = ' ' ;
+
+ sb.append(String.format("%02X", b)) ;
+ }
+ return sb.toString() ;
+ }
+
+ public static String str(byte[] bytes)
+ {
+ StringBuilder sb = new StringBuilder() ;
+ char sep = 0 ;
+ for ( byte b : bytes )
+ {
+ if ( sep != 0 )
+ sb.append(sep) ;
+ else
+ sep = ' ' ;
+
+ sb.append(String.format("%02X", b)) ;
+ }
+ return sb.toString() ;
+ }
+
+ private static String str(RadixTree rt)
+ {
+ Iterator<String> iter = Iter.map(rt.iterator(), new Transform<ByteBuffer, String>(){
+ @Override
+ public String convert(ByteBuffer item)
+ {
+ return "["+str(item)+"]" ;
+ }}) ;
+ return Iter.asString(iter, ", ") ;
+ }
+
+}
+
Modified: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixIndex.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixIndex.java?rev=1226543&r1=1226542&r2=1226543&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixIndex.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixIndex.java Mon Jan 2 20:36:22 2012
@@ -18,6 +18,7 @@
package structure.radix;
+import java.nio.ByteBuffer ;
import java.util.Iterator ;
import org.openjena.atlas.iterator.Iter ;
@@ -67,11 +68,11 @@ public class RadixIndex implements Range
return radix.delete(record.getKey()) ;
}
- Transform<byte[], Record> t = new Transform<byte[], Record>() {
+ Transform<ByteBuffer, Record> t = new Transform<ByteBuffer, Record>() {
@Override
- public Record convert(byte[] item)
+ public Record convert(ByteBuffer item)
{
- return recordFactory.create(item) ;
+ return recordFactory.create(item.array()) ;
}} ;
@Override
@@ -124,7 +125,7 @@ public class RadixIndex implements Range
public Record minKey()
{
// Better???
- Iterator<byte[]> iter = radix.iterator() ;
+ Iterator<ByteBuffer> iter = radix.iterator() ;
if ( !iter.hasNext() ) return null ;
return t.convert(radix.iterator().next()) ;
}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixIterator.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixIterator.java?rev=1226543&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixIterator.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixIterator.java Mon Jan 2 20:36:22 2012
@@ -0,0 +1,197 @@
+/**
+ * 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.Iterator ;
+import java.util.NoSuchElementException ;
+
+import org.openjena.atlas.lib.ByteBufferLib ;
+
+class RadixIterator implements Iterator<ByteBuffer>
+ {
+ // Or parent.
+ // Deque<RadixNode> stack = new ArrayDeque<RadixNode>() ;
+ // Still need the place-in-parent.
+ RadixNode node ;
+ ByteBuffer slot = null ;
+ ByteBuffer prefix = null ;
+
+ byte[] finish = null ;
+
+ RadixIterator(RadixNode root, byte[] start, byte[] finish)
+ {
+ this.finish = finish ;
+ node = root ;
+ int N = -1 ;
+
+ if ( start != null )
+ {
+ // Find ....
+
+ prefix = ByteBuffer.allocate(start.length) ;
+ slot = prefix ;
+ 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.
+ prefix = 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
+ prefix = ByteBuffer.allocate(10) ; //Reallocating?
+ // Now move until leaf.
+ node = downToMinLeaf(node, prefix) ;
+ slot = prefix ;
+
+ // But we need to track the key for copying reasons.
+ if ( false && RadixTree.logging && RadixTree.log.isDebugEnabled() )
+ {
+ RadixTree.log.debug("Iterator start: "+node) ;
+ RadixTree.log.debug("Iterator start: "+slot) ;
+ }
+ }
+
+ static RadixNode downToMinLeaf(RadixNode node, ByteBuffer slot)
+ {
+ while(!node.isLeaf())
+ {
+ // Copy as we go.
+ slot = appendBytes(node.prefix, 0, node.prefix.length, slot) ;
+ node = node.nodes.get(0) ;
+ }
+ // Copy leaf details.
+ slot = appendBytes(node.prefix, 0, node.prefix.length, slot) ;
+ return node ;
+ }
+
+ /** 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 ;
+ if ( node == null )
+ // Ended
+ return false ;
+ // Go up one or more.
+ RadixNode node2 = gotoUpAndAcross(node) ;
+ if ( node2 == null )
+ {
+ node = null ;
+ return false ;
+ }
+// // clear.
+// // CHECK - better way?
+// for ( int j = node2.lenStart ; j < prefix.limit() ; j++ )
+// prefix.put(j, (byte)0xFF) ;
+ // Strip back
+ prefix.position(node2.lenStart) ;
+
+ // Now go down the next one
+ node2 = downToMinLeaf(node2, prefix) ;
+ slot = prefix ;
+ node = node2 ;
+ return true ;
+ }
+
+ private static RadixNode gotoUpAndAcross(RadixNode node2)
+ {
+ //System.out.println("gotoUpAndAcross: "+node2) ;
+
+ RadixNode parent = node2.parent ;
+ //System.out.println("gotoUpAndAcross: "+parent) ;
+ if ( parent == null )
+ return null ;
+ // Find self.
+ int N = parent.nodes.size() ;
+ int idx = 0 ;
+ for ( ; idx < N ; idx++ )
+ {
+ if ( parent.nodes.get(idx) == node2)
+ break ;
+ }
+ if ( idx >= N )
+ {
+ System.out.println("NOT FOUND") ;
+ System.out.println(" "+parent) ;
+ System.out.println(" "+node2) ;
+ }
+ idx++ ;
+ if ( idx != N )
+ return parent.nodes.get(idx) ;
+ // tail recursion - remove.
+ return gotoUpAndAcross(parent) ;
+ }
+
+ @Override
+ public ByteBuffer next()
+ {
+ if ( ! hasNext() )
+ throw new NoSuchElementException() ;
+ ByteBuffer x = ByteBuffer.allocate(slot.position()) ;
+ ByteBufferLib.bbcopy(slot, 0, x, 0, slot.position(), 1) ;
+ slot = null ;
+ return x ;
+ }
+
+ @Override
+ public void remove()
+ { throw new UnsupportedOperationException() ; }
+
+ }
Modified: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixNode.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixNode.java?rev=1226543&r1=1226542&r2=1226543&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixNode.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixNode.java Mon Jan 2 20:36:22 2012
@@ -23,6 +23,8 @@ import java.util.List ;
import java.util.Set;
import org.openjena.atlas.io.IndentedWriter ;
+import org.openjena.atlas.iterator.Iter ;
+import org.openjena.atlas.iterator.Transform ;
import org.openjena.atlas.lib.Bytes ;
import org.openjena.atlas.logging.Log;
@@ -32,14 +34,10 @@ public final class RadixNode //extends P
{
// Debugging? Needed for traversal?
// Not needed for deployment version (we only go down the tree).
+ // Iteration?
/*package*/ int parentId ;
/*package*/ RadixNode parent ;
- RadixNode(RadixNode parent)
- {
- this.parent = parent ;
- this.parentId = (parent==null)?-1 : parent.id ;
- }
/*
* http://en.wikipedia.org/wiki/Radix_tree
*/
@@ -58,6 +56,15 @@ public final class RadixNode //extends P
// The nodes below this one, corresponding to each possible next byte
List<RadixNode> nodes ; // When real, use an array[]; null for leaf.
+ static RadixNode alloc(RadixNode parent) { return new RadixNode(parent) ; }
+ static void dealloc(RadixNode node) { }
+
+ private RadixNode(RadixNode parent)
+ {
+ this.parent = parent ;
+ this.parentId = (parent==null)? -1 : parent.id ;
+ }
+
// Space cost:
// parent
// prefix array (so 3 slot overhead)
@@ -143,7 +150,7 @@ public final class RadixNode //extends P
if ( nodes == null )
return -1 ;
- // Nothing to test -- so is there a subnode of prefix ""
+ // Nothing to test -- so is there a subnode of prefix ""?
if ( bytes.length == start )
{
if ( nodes.get(0).prefix.length == 0 )
@@ -154,7 +161,7 @@ public final class RadixNode //extends P
byte b = bytes[start] ;
- // Only the root an have a prefix of no bytes
+ // Only the root can have a prefix of no bytes (check)
for ( int i = 0 ; i < nodes.size() ; i++ )
{
// if ( RadixTree.logging && RadixTree.log.isDebugEnabled() )
@@ -162,8 +169,9 @@ public final class RadixNode //extends P
// Look first byte only.
// Prefixes must differ at first byte
if ( nodes.get(i).prefix.length == 0 )
- // No bytes is lowest
+ // No bytes is lowest, so no match.
continue ;
+ //return -(i+1) ; // Would have throuhgt this was right.
int x = Bytes.compareByte(b, nodes.get(i).prefix[0]) ;
//int x = compare(bytes, start, nodes.get(i).prefix) ;
@@ -202,6 +210,11 @@ public final class RadixNode //extends P
private void _check(int length, Set<Integer> seen)
{
+ if ( RadixTree.logging && RadixTree.log.isDebugEnabled() )
+ {
+ RadixTree.log.debug("Check: "+this.id) ;
+ System.out.flush() ;
+ }
// It's a tree and so we seen nodes only once.
if ( seen.contains(this) )
{
@@ -225,11 +238,33 @@ public final class RadixNode //extends P
if ( lenFinish - lenStart != prefix.length )
error(this, "Prefix lenth error %d,%d", lenFinish - lenStart, prefix.length) ;
+ // Find self in parent.
+ if ( parent != null )
+ {
+ if ( parent.id != parentId )
+ error(this, "parent.id != parentId (%d != %d)", parent.id, parentId ) ;
+
+ int idx = 0 ;
+ int N = parent.nodes.size() ;
+ for ( ; idx < N ; idx++ )
+ {
+ if ( parent.nodes.get(idx) == this)
+ break ;
+ }
+
+ if (idx >= N )
+ error(this, "Not a child of the parent %s : %s", Iter.map(parent.nodes, idOfNode), parent) ;
+ }
+
if ( nodes == null )
return ;
+
+ // Legal?
+ // Yes - during push-dwn we can end pusing down one node.
+ // Should really avoid this.
- if ( nodes.size() < 2 )
- error(this, "Internal node has length of "+nodes.size()) ;
+// if ( nodes.size() < 2 )
+// error(this, "Internal node has length of "+nodes.size()) ;
// Check subnodes are sorted and start with a different byte
Set<Integer> bytes = new HashSet<Integer>() ;
int last = -2 ;
@@ -237,7 +272,7 @@ public final class RadixNode //extends P
{
int b = -1 ;
if ( n.prefix.length > 0 )
- b = n.prefix[0] ;
+ b = (n.prefix[0]&0xFF) ;
if ( last >= b )
error(this, "Prefix start not strictly increasing") ;
if ( n.parentId != id )
@@ -248,6 +283,14 @@ public final class RadixNode //extends P
for ( RadixNode n : nodes )
n._check(nextStartLen, seen) ;
}
+
+ static Transform<RadixNode, Integer> idOfNode = new Transform<RadixNode, Integer>(){
+
+ @Override
+ public Integer convert(RadixNode item)
+ {
+ return item.id ;
+ }} ;
public boolean isLeaf()
{
@@ -278,6 +321,7 @@ public final class RadixNode //extends P
private static void error(RadixNode node, String message, Object... args)
{
+ System.out.flush() ;
message = String.format(message, args) ;
System.err.println("Error: "+node) ;
System.err.println(message) ;
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=1226543&r1=1226542&r2=1226543&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 Jan 2 20:36:22 2012
@@ -23,12 +23,13 @@ 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.iterator.Transform ;
import org.openjena.atlas.lib.Bytes ;
+import org.openjena.atlas.lib.Chars ;
import org.slf4j.Logger ;
import org.slf4j.LoggerFactory ;
@@ -41,8 +42,8 @@ public final class RadixTree
// Value?
// Architecture : action visitor pattern - find&do (overhead?)
- static boolean logging = true ;
- static final boolean checking = true ;
+ static public boolean logging = true ;
+ static public /*final*/ boolean checking = true ;
static final byte[] bytes0 = new byte[]{} ;
static Logger log = LoggerFactory.getLogger(RadixTree.class) ;
@@ -168,7 +169,7 @@ public final class RadixTree
if ( node.isLeaf() )
{
node.nodes = new ArrayList<RadixNode>() ;
- RadixNode n = new RadixNode(node) ;
+ RadixNode n = RadixNode.alloc(node) ;
n.prefix = bytes0 ;
n.lenStart = node.lenFinish ;
n.lenFinish = node.lenFinish ;
@@ -182,7 +183,7 @@ public final class RadixTree
if (logging && log.isDebugEnabled() )
log.debug("Prefix new : "+Bytes.asHex(prefixNew)) ;
- RadixNode node1 = new RadixNode(node) ;
+ RadixNode node1 = RadixNode.alloc(node) ;
node1.prefix = prefixNew ;
node1.lenStart = node.lenFinish ;
node1.lenFinish = key.length ;
@@ -217,16 +218,19 @@ public final class RadixTree
log.debug("Prefix0 : "+Bytes.asHex(prefix0)) ;
log.debug("Prefix1 : "+Bytes.asHex(prefix1)) ;
log.debug("Prefix2 : "+Bytes.asHex(prefix2)) ;
+ if ( prefix0.length == 0 )
+ log.debug("HERE") ;
+
}
// This is the new leaf due to key added.
- RadixNode node1 = new RadixNode(node) ;
+ RadixNode node1 = RadixNode.alloc(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) ;
+ RadixNode node2 = RadixNode.alloc(node) ;
node2.prefix = prefix2 ;
node2.lenStart = node.lenStart+N ;
node2.lenFinish = node.lenFinish ;
@@ -240,12 +244,19 @@ public final class RadixTree
if (node.nodes != null )
{
int split = node.locate(node1.prefix, 0) ;
+ int split_orig = split ;
if ( checking )
{
if ( split >= 0 )
+ {
+ node.locate(node1.prefix, 0) ;
+ // Is it an error?
error("Found prefix for new inserted key") ;
+ }
}
- split = -(split+1) ;
+ if ( split < 0 )
+ split = -(split+1) ;
+
if ( split > 0 )
node1.nodes = new ArrayList<RadixNode>() ;
if ( split < node.nodes.size() )
@@ -254,18 +265,42 @@ public final class RadixTree
if ( logging && log.isDebugEnabled() )
log.debug("Spread nodes: "+split) ;
- for ( int i = 0 ; i < split ; i++ )
+ // Splliting where there is a leaf. (which will be slot 0)
+ // needs avoid leaving node of one itself having the leaf.
+ // Revisit and check later XXX
+ if ( split == 1 && node.nodes.get(0).isLeaf() )
{
- RadixNode x = node.nodes.get(i) ;
- // Fix the parents of subnodes.
- x.parentId = node1.id ;
- node1.nodes.add(x) ;
+ RadixNode x = node.nodes.get(0) ;
+ // Make node1 the prefix,
+ // loose x.
+ // Copy up x.
+ node1.nodes = null ; // Now a leaf.
+ x.parentId = node2.id ;
+ x.parent = node2 ;
+ node2.nodes.add(x) ; // Add a prefix.
}
-
+ else
+ {
+ for ( int i = 0 ; i < split ; i++ )
+ {
+ RadixNode x = node.nodes.get(i) ;
+ if ( logging && log.isDebugEnabled() )
+ log.debug("Push down "+i+": "+x) ;
+
+ // Fix the parents of subnodes.
+ x.parentId = node1.id ;
+ x.parent = node1 ;
+ node1.nodes.add(x) ;
+ }
+ }
+
for ( int i = split ; i < node.nodes.size() ; i++ )
{
RadixNode x = node.nodes.get(i) ;
+ if ( logging && log.isDebugEnabled() )
+ log.debug("Push down "+i+": "+x) ;
x.parentId = node2.id ;
+ x.parent = node2 ;
node2.nodes.add(x) ;
}
}
@@ -287,7 +322,7 @@ public final class RadixTree
{
if ( root == null )
{
- root = new RadixNode(null) ;
+ root = RadixNode.alloc(null) ;
root.prefix = key ;
root.lenStart = 0 ;
root.lenFinish = key.length ;
@@ -307,7 +342,7 @@ public final class RadixTree
key = Bytes.copyOf(key) ; // ??? Always copy later so no need - check
if ( root == null )
{
- root = new RadixNode(null) ;
+ root = RadixNode.alloc(null) ;
root.prefix = key ;
root.lenStart = 0 ;
root.lenFinish = key.length ;
@@ -378,14 +413,14 @@ public final class RadixTree
log.debug("Prefix2 : "+Bytes.asHex(prefix2)) ;
}
// This is the new leaf due to key added.
- RadixNode node1 = new RadixNode(node) ;
+ RadixNode node1 = RadixNode.alloc(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) ;
+ RadixNode node2 = RadixNode.alloc(node) ;
node2.prefix = prefix2 ;
node2.lenStart = node.lenStart+N ;
node2.lenFinish = node.lenFinish ;
@@ -445,7 +480,7 @@ public final class RadixTree
if ( node.isLeaf() )
{
node.nodes = new ArrayList<RadixNode>() ;
- RadixNode n = new RadixNode(node) ;
+ RadixNode n = RadixNode.alloc(node) ;
n.prefix = bytes0 ;
n.lenStart = node.lenFinish ;
n.lenFinish = node.lenFinish ;
@@ -458,7 +493,7 @@ public final class RadixTree
if (logging && log.isDebugEnabled() )
log.debug("Prefix new : "+Bytes.asHex(prefixNew)) ;
- RadixNode node1 = new RadixNode(node) ;
+ RadixNode node1 = RadixNode.alloc(node) ;
node1.prefix = prefixNew ;
node1.lenStart = node.lenFinish ;
node1.lenFinish = key.length ;
@@ -595,9 +630,9 @@ public final class RadixTree
return (Integer)v.result() ;
}
- public Iterator<byte[]> iterator() { return iterator(null, null) ; }
+ public Iterator<ByteBuffer> iterator() { return iterator(null, null) ; }
- public Iterator<byte[]> iterator(byte[] start, byte[] finish)
+ public Iterator<ByteBuffer> iterator(byte[] start, byte[] finish)
{
if ( logging && log.isDebugEnabled() )
{
@@ -614,113 +649,16 @@ public final class RadixTree
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 ;
- }
+ static Transform<Byte, String> hex = new Transform<Byte, String>(){
@Override
- public byte[] next()
+ public String convert(Byte item)
{
- if ( ! hasNext() )
- throw new NoSuchElementException() ;
- byte[] x = slot.array() ;
- slot = null ;
- return x ;
- }
-
- @Override
- public void remove()
- { throw new UnsupportedOperationException() ; }
-
- }
+ int hi = (item.byteValue() >> 4) & 0xF ;
+ int lo = item.byteValue() & 0xF ;
+
+ return "0x"+Chars.hexDigitsUC[hi]+Chars.hexDigitsUC[lo] ;
+ }} ;
public void printLeaves()
{
@@ -739,7 +677,9 @@ public final class RadixTree
for ( byte b : node.prefix )
x.addLast(b) ;
if ( node.isLeaf() )
- System.out.print(" "+x) ;
+ {
+ System.out.println(Iter.iter(x.iterator()).map(hex).asString(", ")) ;
+ }
}
@Override
Modified: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/RadixRun.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/RadixRun.java?rev=1226543&r1=1226542&r2=1226543&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/RadixRun.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/RadixRun.java Mon Jan 2 20:36:22 2012
@@ -17,14 +17,18 @@
*/
package structure.radix;
+import static structure.radix.RLib.str ;
+
import java.util.ArrayList ;
-import java.util.Iterator ;
+import java.util.Arrays ;
import java.util.List ;
import org.junit.runner.JUnitCore ;
import org.junit.runner.Result ;
+import org.openjena.atlas.AtlasException ;
+import org.openjena.atlas.iterator.Iter ;
import org.openjena.atlas.junit.TextListener2 ;
-import org.openjena.atlas.lib.Bytes ;
+import org.openjena.atlas.lib.RandomLib ;
import org.openjena.atlas.logging.Log ;
public class RadixRun
@@ -33,8 +37,7 @@ public class RadixRun
{
Log.setLog4j() ;
Log.enable(RadixTree.class) ;
- RadixTree.logging = false ;
- //RadixTree.logging = true ;
+ //RadixTree.logging = false ;
if ( false )
{
@@ -44,41 +47,125 @@ public class RadixRun
Result result = runner.run(TestRadix.class) ;
//TestRadix.afterClass() ;
System.exit(0) ;
- }
+ }
+ // Check/Bug:
+ // [0C 08 05] [11 04] [0B 0B 08] [09 02 13 0A] [02 09 04] [05 02 05 01] [0D] [04 00 0D 0B] [] [12 06 08 02] [12 0F 09 04] [0F 0E 01] [05 02 01] [10] [05 0D 09] [05 08] [0C] [12] [12 08] [0C 04] [0B] [0E] [07 0C 12] [13 0E] [03 03] [11 09 04] [05 09 05 0C] [04 02] [09 00] [11 0B 0C] [0B 0C 08 04] [08 03 0E] [06 0B 02] [01 12] [0E 03 03 0F] [02 07] [0E 0A 12] [07 0B 13] [13 11 04 0A] [08 0B 09 03] [09 0E] [10 03 06 0B] [13 04] [0D 0C 0C] [07 0C 0B] [08 06 11] [0D 11] [04 02 0E 10] [0D 10] [0F]
+ /*
+Insert--'09 09 08 08'
+Insert--'09 07 04'
+Insert--'07 09 00 03'
+org.openjena.atlas.AtlasException: Found prefix for new inserted key
+ at structure.radix.RadixTree.error(RadixTree.java:704)
+ at structure.radix.RadixTree$3.exec(RadixTree.java:252)
+ at structure.radix.RadixTree.applicator(RadixTree.java:70)
+ at structure.radix.RadixTree.insert(RadixTree.java:335)
+ at structure.radix.RadixRun.insert(RadixRun.java:214)
+ at structure.radix.RadixRun.exec(RadixRun.java:129)
+ at structure.radix.RadixRun.main(RadixRun.java:60)
+[09 09 08 08] [09 07 04] [07 09 00 03] [05 00 04 06] [00 01 07 04] [05 02] [] [00] [02] [09]
+ */
- List<byte[]> entries = new ArrayList<byte[]>() ;
- entries.add(new byte[]{1,4}) ;
- entries.add(new byte[]{1,2}) ;
- entries.add(new byte[]{1,2,3,4}) ;
- entries.add(new byte[]{1,2,8}) ;
- entries.add(new byte[]{1,2,3,4}) ; // repeat
- entries.add(new byte[]{1,5,8}) ;
- entries.add(new byte[]{0}) ;
- entries.add(new byte[]{}) ;
-
- RadixTree trie = new RadixTree() ;
- for ( byte[] arr : entries )
- insert(trie, arr) ;
+
+ if ( false )
+ {
+ for ( int i = 0 ; i < 10 ; i++ )
+ {
+ RadixTree trie = new RadixTree() ;
+ List<byte[]> x = gen(10, 5) ;
+ exec(trie, x) ;
+ System.out.println() ;
+ }
+ System.out.println("Done") ;
+ System.exit(0) ;
+ }
RadixTree.logging = true ;
- Iterator<byte[]> iter = trie.iterator(new byte[]{1,2}, null) ;
- for ( ; iter.hasNext() ; )
+ RadixTree trie = new RadixTree() ;
+ exec(trie
+ ,new int[]{0x09, 0x09, 0x08, 0x08}
+ ,new int[]{0x09, 0x07, 0x04}
+ ,new int[]{0x07, 0x09, 0x00, 0x03}
+ ) ;
+ System.out.println("Done") ;
+ System.exit(0) ;
+ }
+
+
+
+ // Generate N entries upto to nLen long
+ static List<byte[]> gen(int N, int nLen)
+ {
+ List<byte[]> entries = new ArrayList<byte[]>() ;
+
+ for ( int i = 0 ; i < N ; i++)
{
- byte[] b = iter.next();
- System.out.println(Bytes.asHex(b)) ;
+
+ while(true)
+ {
+ byte[] b = gen1(nLen) ;
+ if ( ! contains(b, entries) )
+ {
+ entries.add(b) ;
+ break ;
+ }
+ }
}
- System.exit(0) ;
- //RadixTree.logging = true ;
-
- //for ( int i = entries.size()-1 ; i >= 0 ; i-- )
- for ( int i = 0 ; i < entries.size(); i++ )
+ return entries ;
+ }
+
+ static boolean contains(byte[] b, List<byte[]> entries)
+ {
+ for ( byte[] e : entries )
+ {
+ if ( Arrays.equals(e, b) )
+ return true ;
+ }
+ return false ;
+ }
+
+ static int RANGE = 10 ;
+ static byte[] gen1(int nLen)
+ {
+ int len = RandomLib.qrandom.nextInt(nLen) ;
+ byte[] b = new byte[len] ;
+ for ( int i = 0 ; i < len ; i++ )
+ b[i] = (byte)(RandomLib.qrandom.nextInt(RANGE)&0xFF) ;
+ return b ;
+ }
+
+ public static void exec(RadixTree trie, int[] ... e)
+ {
+ List<byte[]> entries = new ArrayList<byte[]>() ;
+ for ( int j = 0 ; j < e.length ; j++ )
{
- byte[] arr = entries.get(i) ;
- delete(trie, arr) ;
+ byte[] b = new byte[e[j].length] ;
+ for ( int i = 0 ; i < e[j].length ; i++ )
+ b[i] = (byte)(e[j][i]) ;
+ entries.add(b) ;
}
+ exec(trie, entries) ;
+ }
- System.exit(0) ;
+
+ private static void exec(RadixTree trie, List<byte[]> entries)
+ {
+ try {
+ for ( byte[] arr : entries )
+ {
+ insert(trie, arr) ;
+ trie.print() ;
+ }
+ } catch (AtlasException ex)
+ {
+ System.out.flush() ;
+ ex.printStackTrace(System.err) ;
+ System.err.println(strall(entries)) ;
+ trie.print() ;
+ return ;
+ }
+
+ check(trie, entries) ;
}
// static void search(RadixTree trie, byte[] key)
@@ -89,23 +176,55 @@ public class RadixRun
// System.out.println() ;
// }
+ private static String strall(List<byte[]> entries)
+ {
+ boolean first = true ;
+ StringBuilder sb = new StringBuilder() ;
+ for ( byte[] e : entries )
+ {
+ if ( ! first )
+ sb.append(" ") ;
+ first = false ;
+ sb.append("[") ;
+ sb.append(str(e)) ;
+ sb.append("]") ;
+ }
+ return sb.toString() ;
+ }
+
+ static void check(RadixTree trie, List<byte[]> keys)
+ {
+ for ( byte[] k : keys )
+ {
+ if ( trie.find(k) == null )
+ System.err.println("Did not find: "+str(k)) ;
+ }
+
+ long N1 = trie.size() ;
+ long N2 = Iter.count(trie.iterator()) ;
+ if ( N1 != N2 )
+ System.err.printf("size[%d] != count[%d]",N1, N2) ;
+ if ( N1 != keys.size() )
+ System.err.printf("size[%d] != length[%d]",N1, keys.size()) ;
+ }
+
static void find(RadixTree trie, byte[] key)
{
- System.out.println("Find --'"+Bytes.asHex(key)+"'") ;
+// System.out.println("Find --'"+Bytes.asHex(key)+"'") ;
RadixNode node = trie.find(key) ;
- System.out.println("Find >> "+node) ;
- System.out.println() ;
+// System.out.println("Find >> "+node) ;
+// System.out.println() ;
}
-
static void insert(RadixTree trie, byte[] key)
{
- System.out.println("Insert--'"+Bytes.asHex(key)+"'") ;
+ System.out.println("Insert--'"+str(key)+"'") ;
boolean b2 = ( trie.find(key) == null ) ;
boolean b = trie.insert(key) ;
- System.out.print(" >> "+b+" ["+b2+"]") ;
- System.out.print(": ") ;
- trie.printLeaves() ;
+// System.out.print(" >> "+b+" ["+b2+"]") ;
+// System.out.print(": ") ;
+// trie.print() ;
+// trie.printLeaves() ;
//trie.print();
System.out.flush() ;
if ( b != b2 )
@@ -115,14 +234,14 @@ public class RadixRun
static void delete(RadixTree trie, byte[] key)
{
- System.out.println("Delete--'"+Bytes.asHex(key)+"'") ;
+// System.out.println("Delete--'"+str(key)+"'") ;
boolean b2 = ( trie.find(key) != null ) ;
boolean b = trie.delete(key) ;
- System.out.print(" >> "+b+" ["+b2+"]") ;
- System.out.print(": ") ;
+// System.out.print(" >> "+b+" ["+b2+"]") ;
+// System.out.print(": ") ;
trie.printLeaves() ;
trie.print();
- System.out.flush() ;
+// System.out.flush() ;
if ( b != b2 )
System.err.println("Inconsistent (delete)") ;
trie.check() ;
Modified: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/TestRadix.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/TestRadix.java?rev=1226543&r1=1226542&r2=1226543&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/TestRadix.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/TestRadix.java Mon Jan 2 20:36:22 2012
@@ -18,11 +18,7 @@
package structure.radix;
-import java.util.Iterator ;
-
import org.junit.Test ;
-import org.openjena.atlas.iterator.Iter ;
-import org.openjena.atlas.iterator.Transform ;
import org.openjena.atlas.junit.BaseTest ;
public class TestRadix extends BaseTest
@@ -87,50 +83,17 @@ public class TestRadix extends BaseTest
// t.check() ;
// t.insert(key6) ;
// t.check() ;
-
-
byte[][] keys = { key1, key2, key3, key4, key5, key6 } ;
int i = 0 ;
for ( byte[]k : keys )
{
i++ ;
- System.out.println("Insert: "+str(k)) ;
t.insert(k) ;
-
- System.out.println(Iter.count(t.iterator())) ;
-
- System.out.println("Tree : "+str(t)) ;
- //t.print() ;
t.check() ;
}
- t.print() ;
test(keys.length, t) ;
}
- private String str(RadixTree rt)
- {
- Iterator<String> iter = Iter.map(rt.iterator(), new Transform<byte[], String>(){
- @Override
- public String convert(byte[] item)
- {
- return "["+str(item)+"]" ;
- }}) ;
- return Iter.asString(iter, ", ") ;
- }
-
- private String str(byte[] array)
- {
- StringBuilder sb = new StringBuilder() ;
- String sep = "" ;
- for ( byte b : array )
- {
- sb.append(sep) ;
- sb.append(b) ;
- sep = ", " ;
- }
- return sb.toString() ;
- }
-
private static void insert(RadixTree t, byte[] key)
{
t.insert(key) ;