jena-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From a...@apache.org
Subject 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
Date Wed, 04 Jan 2012 21:48:34 GMT
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)



Mime
View raw message