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/04 22:48:34 UTC
svn commit: r1227341 - in /incubator/jena/Scratch/AFS/Dev/trunk/src-lib:
main/java/structure/radix/RadixNode.java
main/java/structure/radix/RadixTree.java
test/java/structure/radix/RadixRun.java
Author: andy
Date: Wed Jan 4 21:48:33 2012
New Revision: 1227341
URL: http://svn.apache.org/viewvc?rev=1227341&view=rev
Log: (empty)
Modified:
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
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=1227341&r1=1227340&r2=1227341&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 Wed Jan 4 21:48:33 2012
@@ -143,6 +143,7 @@ public final class RadixNode //extends P
*/
/*package*/ int locate(byte[] bytes, int start)
{
+ // XXX Should we use locate(byte b) only?
// if ( RadixTree.logging && RadixTree.log.isDebugEnabled() )
// {
// RadixTree.log.debug("locate: <"+Bytes.asHex(bytes, start, bytes.length)) ;
@@ -160,7 +161,11 @@ public final class RadixNode //extends P
}
byte b = bytes[start] ;
+ return locate(b) ;
+ }
+ /*package*/int locate(byte b)
+ {
for ( int i = 0 ; i < nodes.size() ; i++ )
{
// if ( RadixTree.logging && RadixTree.log.isDebugEnabled() )
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=1227341&r1=1227340&r2=1227341&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 Wed Jan 4 21:48:33 2012
@@ -152,6 +152,7 @@ public final class RadixTree
// Key already present - we ended at a leaf.
if ( N == node.prefix.length && node.lenFinish == key.length && node.isLeaf() )
{
+ // Or has a leaf of ""?
if (logging && log.isDebugEnabled() )
log.debug("insert: Already present") ;
return null ;
@@ -232,111 +233,25 @@ public final class RadixTree
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 )
+ // reset parent.
+ node2.nodes = node.nodes ;
+ if ( node.nodes != null )
{
-
- if (logging && log.isDebugEnabled() )
- {
- 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 ( logging && log.isDebugEnabled() )
- log.debug("Split: "+split) ;
-
- // Negative split: split byte did not occur in the subnodes
- // Positive split: split occurs at that index.
- if ( split < 0 )
- split = -split ; //-(split+1) ; // Note start of upper section.
-
- if ( split >= 0 )
- node1.nodes = new ArrayList<RadixNode>() ;
- if ( split < node.nodes.size() )
- node2.nodes = new ArrayList<RadixNode>() ;
-
- // *******
- // Spliting where there is a leaf. (which will be slot 0)
- // needs avoid leaving node of one itself having the leaf.
-
-// if ( split == 1 && node.nodes.get(0).isLeaf() )
-// {
-// 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(1) "+i+": "+x) ;
-//
-// // Fix the parents of subnodes.
-// x.parentId = node1.id ;
-// x.parent = node1 ;
-// node1.nodes.add(x) ;
-// }
-// }
-
- // Non-collapse version.
- // Revisit and check later for case of node1 is going to point to only a leaf
-
-
- for ( int i = 0 ; i < split ; i++ )
- {
- RadixNode x = node.nodes.get(i) ;
- if ( logging && log.isDebugEnabled() )
- log.debug("Push down(1) "+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++ )
+ for ( RadixNode n : node.nodes )
{
- RadixNode x = node.nodes.get(i) ;
- if ( logging && log.isDebugEnabled() )
- log.debug("Push down(2) "+i+": "+x) ;
- x.parentId = node2.id ;
- x.parent = node2 ;
- node2.nodes.add(x) ;
+ n.parent = node2 ;
+ n.parentId = node2.id ;
}
- }
+ }
+ // Swap if necessary
+ if ( Bytes.compare(prefix1, prefix2) > 0 )
+ { RadixNode t = node2 ; node2 = node1 ; node1 = t ; }
- // Alter the node in-place.
+ // Alter the node in-place, rather than create a new node and insert node1, node2.
+ // This keeps the root 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 = new ArrayList<RadixNode>() ;
node.nodes.add(node1) ;
node.nodes.add(node2) ;
return node ;
@@ -361,182 +276,6 @@ 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)
-// {
-// 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 = RadixNode.alloc(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 = 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 = RadixNode.alloc(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 = RadixNode.alloc(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 = RadixNode.alloc(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
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=1227341&r1=1227340&r2=1227341&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 Wed Jan 4 21:48:33 2012
@@ -19,8 +19,10 @@
package structure.radix;
import static structure.radix.RLib.str ;
+import java.nio.ByteBuffer ;
import java.util.ArrayList ;
import java.util.Arrays ;
+import java.util.Iterator ;
import java.util.List ;
import org.junit.runner.JUnitCore ;
@@ -28,6 +30,7 @@ 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 ;
@@ -66,13 +69,13 @@ org.openjena.atlas.AtlasException: Found
*/
- if ( false )
+ if ( true )
{
RadixTree.logging = false ;
for ( int i = 0 ; i < 100 ; i++ )
{
RadixTree trie = new RadixTree() ;
- List<byte[]> x = gen(25, 5) ;
+ List<byte[]> x = gen(250, 5) ;
print(x) ;
exec(trie, x, false) ;
trie.printLeaves() ;
@@ -245,6 +248,21 @@ org.openjena.atlas.AtlasException: Found
System.err.printf("size[%d] != count[%d]",N1, N2) ;
if ( N1 != keys.size() )
System.err.printf("size[%d] != length[%d]",N1, keys.size()) ;
+
+ // check ordered.
+ ByteBuffer prev = null ;
+ for ( Iterator<ByteBuffer> elements = trie.iterator() ; elements.hasNext() ; )
+ {
+ ByteBuffer here = elements.next() ;
+ if ( prev != null )
+ {
+ if ( Bytes.compare(prev.array(), here.array()) >= 0 )
+ System.err.println("Not increasing: "+str(prev.array())+" // "+str(here.array())) ;
+ }
+ prev = here ;
+ }
+
+
}
static void find(RadixTree trie, byte[] key)