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/03 18:35:53 UTC
svn commit: r1226893 - in /incubator/jena/Scratch/AFS/Dev/trunk/src-lib:
main/java/structure/radix/RLib.java main/java/structure/radix/RadixTree.java
test/java/structure/radix/RadixRun.java
Author: andy
Date: Tue Jan 3 17:35:53 2012
New Revision: 1226893
URL: http://svn.apache.org/viewvc?rev=1226893&view=rev
Log: (empty)
Modified:
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/RadixTree.java
incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/RadixRun.java
Modified: 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=1226893&r1=1226892&r2=1226893&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RLib.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RLib.java Tue Jan 3 17:35:53 2012
@@ -42,19 +42,21 @@ public class RLib
}
return sb.toString() ;
}
-
+
public static String str(byte[] bytes)
+ { return str(bytes, " ") ; }
+
+
+ public static String str(byte[] bytes, String sep)
{
StringBuilder sb = new StringBuilder() ;
- char sep = 0 ;
+ boolean first = true ;
for ( byte b : bytes )
{
- if ( sep != 0 )
+ if ( ! first )
sb.append(sep) ;
- else
- sep = ' ' ;
-
- sb.append(String.format("%02X", b)) ;
+ first = false ;
+ sb.append(String.format("0x%02X", b)) ;
}
return sb.toString() ;
}
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=1226893&r1=1226892&r2=1226893&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 Tue Jan 3 17:35:53 2012
@@ -218,9 +218,6 @@ 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 = RadixNode.alloc(node) ;
@@ -243,17 +240,25 @@ public final class RadixTree
// Spread the original subnodes nodes over the new subnodes.
if (node.nodes != null )
{
- int split = node.locate(node1.prefix, 0) ;
- int split_orig = split ;
- if ( checking )
+
+ if (logging && log.isDebugEnabled() )
{
- if ( split >= 0 )
- {
- node.locate(node1.prefix, 0) ;
- // Is it an error?
- error("Found prefix for new inserted key") ;
- }
+ log.debug("Locate: "+node.nodes) ;
+ log.debug("Prefix: "+RLib.str(node1.prefix)) ;
}
+
+ int split = node.locate(node1.prefix, 0) ;
+ int split_orig = split ;
+// if ( false && checking )
+// {
+// if ( split >= 0 )
+// {
+// node.locate(node1.prefix, 0) ;
+// // Is it an error?
+// error("Found prefix for new inserted key") ;
+// }
+// }
+
if ( split < 0 )
split = -(split+1) ;
@@ -265,7 +270,8 @@ public final class RadixTree
if ( logging && log.isDebugEnabled() )
log.debug("Spread nodes: "+split) ;
- // Splliting where there is a leaf. (which will be slot 0)
+ // *******
+ // Spliting 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() )
@@ -320,6 +326,9 @@ public final class RadixTree
public boolean insert(byte[] key)
{
+ if (logging && log.isDebugEnabled() )
+ log.debug("** Insert : "+Bytes.asHex(key)) ;
+
if ( root == null )
{
root = RadixNode.alloc(null) ;
@@ -333,6 +342,7 @@ public final class RadixTree
return applicator(root, key, insertAction) != null ;
}
+ // Is this the right code?
/** Insert - return true if the trie changed */
private boolean _insert(byte[] key)
{
@@ -678,7 +688,9 @@ public final class RadixTree
x.addLast(b) ;
if ( node.isLeaf() )
{
- System.out.println(Iter.iter(x.iterator()).map(hex).asString(", ")) ;
+ System.out.print("[") ;
+ System.out.print(Iter.iter(x.iterator()).map(hex).asString(", ")) ;
+ System.out.print("] ") ;
}
}
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=1226893&r1=1226892&r2=1226893&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 Tue Jan 3 17:35:53 2012
@@ -68,11 +68,17 @@ org.openjena.atlas.AtlasException: Found
if ( false )
{
- for ( int i = 0 ; i < 10 ; i++ )
+ RadixTree.logging = false ;
+ for ( int i = 0 ; i < 100 ; i++ )
{
RadixTree trie = new RadixTree() ;
- List<byte[]> x = gen(10, 5) ;
- exec(trie, x) ;
+ List<byte[]> x = gen(25, 5) ;
+ print(x) ;
+ exec(trie, x, false) ;
+ trie.printLeaves() ;
+
+
+ // print x, sorted.
System.out.println() ;
}
System.out.println("Done") ;
@@ -81,11 +87,19 @@ org.openjena.atlas.AtlasException: Found
RadixTree.logging = true ;
RadixTree trie = new RadixTree() ;
- exec(trie
- ,new int[]{0x09, 0x09, 0x08, 0x08}
- ,new int[]{0x09, 0x07, 0x04}
- ,new int[]{0x07, 0x09, 0x00, 0x03}
- ) ;
+
+ byte[][] data$ = {
+ {0x05,0x04,0x03,0x02}, {0x05,0x08,0x09,0x01}, {0x09,0x05,0x05,0x09}
+ //, {0x07,0x09,0x02}
+ //, {}
+// , {0x03,0x06,0x01,0x09}, {0x02}, {0x05,0x02,0x05,0x06}, {0x00}, {0x01,0x01,0x05}, {0x01,0x04}
+// , {0x07,0x01,0x00,0x04}, {0x03,0x00}, {0x06,0x06}, {0x02,0x09}, {0x05}, {0x04}
+// , {0x05,0x05,0x09,0x05}, {0x07,0x02,0x00}, {0x09}, {0x00,0x06}, {0x05,0x06,0x04}
+// , {0x04,0x07,0x00}, {0x05,0x06,0x06}, {0x03,0x03,0x06,0x08}
+ } ;
+ List<byte[]> data = Arrays.asList(data$) ;
+ print(data) ;
+ exec(trie, data, true) ;
System.out.println("Done") ;
System.exit(0) ;
}
@@ -134,27 +148,33 @@ org.openjena.atlas.AtlasException: Found
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[] 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) ;
- }
+// public static void exec(RadixTree trie, int[] ... e)
+// {
+// List<byte[]> entries = new ArrayList<byte[]>() ;
+// for ( int j = 0 ; j < e.length ; j++ )
+// {
+// 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, false) ;
+// }
- private static void exec(RadixTree trie, List<byte[]> entries)
+ private static void exec(RadixTree trie, List<byte[]> entries, boolean debugMode)
{
try {
for ( byte[] arr : entries )
{
+// if ( debugMode )
+// System.out.println("Insert: "+str(arr)) ;
insert(trie, arr) ;
- trie.print() ;
+ if ( debugMode )
+ {
+ trie.print() ;
+ System.out.println() ;
+ }
}
} catch (AtlasException ex)
{
@@ -176,6 +196,25 @@ org.openjena.atlas.AtlasException: Found
// System.out.println() ;
// }
+ private static void print(List<byte[]> entries)
+ {
+ boolean first = true ;
+ StringBuilder sb = new StringBuilder() ;
+ sb.append("byte[][] data = { ") ;
+ for ( byte[] e : entries )
+ {
+ if ( ! first )
+ sb.append(", ") ;
+ first = false ;
+
+ sb.append("{") ;
+ sb.append(str(e,"," )) ;
+ sb.append("}") ;
+ }
+ sb.append(" } ;") ;
+ System.out.println(sb.toString()) ;
+ }
+
private static String strall(List<byte[]> entries)
{
boolean first = true ;
@@ -218,7 +257,7 @@ org.openjena.atlas.AtlasException: Found
static void insert(RadixTree trie, byte[] key)
{
- System.out.println("Insert--'"+str(key)+"'") ;
+// System.out.println("Insert--'"+str(key)+"'") ;
boolean b2 = ( trie.find(key) == null ) ;
boolean b = trie.insert(key) ;
// System.out.print(" >> "+b+" ["+b2+"]") ;