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/09/30 17:01:57 UTC
svn commit: r1177690 [5/7] - in /incubator/jena/Scratch/AFS/Dev/trunk:
Archive/ src-lib/main/java/libmisc/ src-lib/main/java/migrate/
src-lib/main/java/migrate/lib/ src-lib/main/java/migrate/lib/tuple/
src-lib/main/java/structure/ src-lib/main/java/str...
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/OrderedSetTestFactory.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/OrderedSetTestFactory.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/OrderedSetTestFactory.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/OrderedSetTestFactory.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,24 @@
+/**
+ * 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;
+
+public interface OrderedSetTestFactory
+{
+ public OrderedSet<Integer> create(int...recs) ;
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/OrderedSetTestLib.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/OrderedSetTestLib.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/OrderedSetTestLib.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/OrderedSetTestLib.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,134 @@
+/**
+ * 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;
+
+import org.openjena.atlas.iterator.Iter;
+
+import java.util.*;
+
+import static org.junit.Assert.* ;
+
+import org.openjena.atlas.test.ExecGenerator;
+import org.openjena.atlas.test.Gen;
+import org.openjena.atlas.test.RepeatExecution;
+
+public class OrderedSetTestLib
+{
+
+ public static void randTests(OrderedSetTestFactory factory, int maxValue, int maxNumKeys, int iterations, boolean showProgess)
+ {
+ ExecGenerator execGenerator = new OrderedSetTest(factory, maxValue, maxNumKeys) ;
+ RepeatExecution.repeatExecutions(execGenerator, iterations, showProgess) ;
+ }
+
+ public static void randTest(OrderedSetTestFactory factory, int maxValue, int numKeys)
+ {
+ // if ( numKeys >= 3000 )
+ // System.err.printf("Warning: too many keys\n") ;
+ //
+ int[] r1 = Gen.rand(numKeys, 0, maxValue) ;
+ int[] r2 = Gen.permute(r1, 4*numKeys) ;
+ try {
+ OrderedSet<Integer> sIndx = factory.create(r1) ;
+ check(sIndx, r1) ;
+ delete(sIndx, r2) ;
+ check(sIndx) ;
+ } catch (RuntimeException ex)
+ {
+ System.err.printf("int[] r1 = {%s} ;\n", Gen.strings(r1)) ;
+ System.err.printf("int[] r2 = {%s}; \n", Gen.strings(r2)) ;
+ throw ex ;
+ }
+ catch (Error ex)
+ {
+ System.err.printf("int[] r1 = {%s} ;\n", Gen.strings(r1)) ;
+ System.err.printf("int[] r2 = {%s}; \n", Gen.strings(r2)) ;
+ throw ex ;
+ }
+
+ }
+
+ public static OrderedSet<Integer> delete(OrderedSet<Integer> sIndx, int...recs)
+ {
+ for ( int i : recs )
+ sIndx.remove(i) ;
+ return sIndx ;
+ }
+
+ public static void check(OrderedSet<Integer> sIndx, int...recs)
+ {
+ sIndx.checkTree() ;
+ for ( int i : recs )
+ assertTrue(sIndx.contains(i)) ;
+
+ List<Integer> x = Iter.toList(sIndx.iterator()) ;
+ List<Integer> y = sIndx.elements() ;
+ assertEquals(x,y) ;
+
+ SortedSet<Integer> r = new TreeSet<Integer>() ;
+
+ // -- Sort to list.
+ for ( int i : recs )
+ r.add(i) ;
+
+ List<Integer> z = new ArrayList<Integer>() ;
+ for ( int i : r )
+ z.add(i) ;
+ // --
+
+ if ( ! z.equals(x) )
+ {
+ System.out.println("About to crash") ;
+ }
+
+ assertEquals(z, x) ;
+
+ if ( r.size() > 0 )
+ {
+ Integer min = z.get(0) ;
+ Integer max = z.get(r.size()-1) ;
+ assertEquals(min, sIndx.min()) ;
+ assertEquals(max, sIndx.max()) ;
+ }
+ }
+
+ public static void check(Iterator<Integer> iter, int...recs)
+ {
+ for ( int i : recs )
+ {
+ assertTrue("Iterator shorter than test answers", iter.hasNext()) ;
+ int j = iter.next() ;
+ assertEquals(i,j) ;
+ }
+ assertFalse("Iterator longer than test answers", iter.hasNext()) ;
+ }
+
+ public static void size(OrderedSet<Integer> sIdx, long size)
+ {
+ long x = sIdx.count() ;
+ long x2 = sIdx.size() ;
+ assertEquals(size, x) ;
+ assertEquals(size, x2) ;
+ if ( size == 0 )
+ assertTrue(sIdx.isEmpty()) ;
+ else
+ assertFalse(sIdx.isEmpty()) ;
+ }
+
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/TS_Structure.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/TS_Structure.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/TS_Structure.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/TS_Structure.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,38 @@
+/**
+ * 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;
+
+import org.junit.runner.RunWith;
+import org.junit.runners.Suite;
+import structure.avl.TestAVL;
+import structure.exthash.TestExtHashMem;
+import structure.skiplist.TestSkipList;
+import structure.ttree.TestTTree;
+
+@RunWith(Suite.class)
+@Suite.SuiteClasses( {
+ TestAVL.class
+ , TestExtHashMem.class
+ , TestSkipList.class
+ , TestTTree.class
+} )
+public class TS_Structure
+{
+
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/avl/TestAVL.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/avl/TestAVL.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/avl/TestAVL.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/avl/TestAVL.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,36 @@
+/**
+ * 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.avl;
+
+import structure.OrderedSet;
+import structure.OrderedSetTestBase;
+
+public class TestAVL extends OrderedSetTestBase
+{
+ static {
+ AVL.Checking = true ;
+ //AVL.Verbose = false ;
+ }
+
+ @Override
+ protected OrderedSet<Integer> create()
+ {
+ return new AVL<Integer>() ;
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/exthash/ExtHashMemTestBase.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/exthash/ExtHashMemTestBase.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/exthash/ExtHashMemTestBase.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/exthash/ExtHashMemTestBase.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,142 @@
+/**
+ * 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.exthash;
+import static org.openjena.atlas.lib.ListUtils.asList;
+import static org.openjena.atlas.lib.ListUtils.unique;
+import static org.openjena.atlas.lib.RandomLib.random;
+import static org.openjena.atlas.test.Gen.permute;
+import static org.openjena.atlas.test.Gen.rand;
+import static org.openjena.atlas.test.Gen.strings;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
+
+import java.util.Iterator;
+import java.util.List;
+
+import org.openjena.atlas.test.ExecGenerator;
+import org.openjena.atlas.test.RepeatExecution;
+
+public class ExtHashMemTestBase
+{
+ public static int BucketSize = 2 ;
+ public static void randTests(int maxValue, int maxNumKeys, int iterations, boolean showProgess)
+ {
+ ExtHashTest test = new ExtHashTest(maxValue, maxNumKeys) ;
+ RepeatExecution.repeatExecutions(test, iterations, showProgess) ;
+ }
+
+ static class ExtHashTest implements ExecGenerator
+ {
+ int maxNumKeys ;
+ int maxValue ;
+ ExtHashTest(int maxValue, int maxNumKeys)
+ {
+ if ( maxValue <= maxNumKeys )
+ throw new IllegalArgumentException("ExtHashTest: Max value less than number of keys") ;
+ this.maxValue = maxValue ;
+ this.maxNumKeys = maxNumKeys ;
+ }
+
+ @Override
+ public void executeOneTest()
+ {
+ int numKeys = random.nextInt(maxNumKeys)+1 ;
+ randTest(maxValue, numKeys) ;
+ }
+ }
+
+ public static void randTest(int maxValue, int numKeys)
+ {
+// if ( numKeys >= 3000 )
+// System.err.printf("Warning: too many keys\n") ;
+
+ int[] r1 = rand(numKeys, 0, maxValue) ;
+ int[] r2 = permute(r1, 4*numKeys) ;
+ runTest(r1, r2) ;
+ }
+
+ public static void runTest(int[] r1, int[] r2)
+ {
+ try {
+ ExtHashMem<Integer, String> table = create(r1) ;
+ check(table, r1) ;
+ delete(table, r2) ;
+ check(table) ;
+ } catch (RuntimeException ex)
+ {
+ System.err.println() ;
+ System.err.printf("int[] r1 = {%s} ;\n", strings(r1)) ;
+ System.err.printf("int[] r2 = {%s}; \n", strings(r2)) ;
+ throw ex ;
+ }
+ }
+
+ public static ExtHashMem<Integer, String> create(int...recs)
+ {
+ ExtHashMem<Integer, String> table = new ExtHashMem<Integer, String>(BucketSize) ;
+ for ( int i : recs )
+ {
+ table.put(i, "X"+i) ;
+ if ( false ) table.dump() ;
+ }
+ return table ;
+ }
+
+ public static ExtHashMem<Integer, String> delete(ExtHashMem<Integer, String> table, int...recs)
+ {
+ for ( int i : recs )
+ table.remove(i) ;
+ return table ;
+ }
+
+
+ public static void check(ExtHashMem<Integer, String> table, int...recs)
+ {
+ table.check();
+ for ( int i : recs )
+ assertNotNull(table.get(i)) ;
+ List<Integer> y = unique(asList(recs)) ;
+ assertEquals(y.size(), table.size());
+ }
+
+
+ public static void check(Iterator<Integer> iter, int...recs)
+ {
+ for ( int i : recs )
+ {
+ assertTrue("Iterator shorter than test answers", iter.hasNext()) ;
+ int j = iter.next() ;
+ assertEquals(i,j) ;
+ }
+ assertFalse("Iterator longer than test answers", iter.hasNext()) ;
+ }
+
+ public static void size(ExtHashMem<Integer, String> table, long size)
+ {
+// long x = avl.size() ;
+// assertEquals(size, x) ;
+// if ( size == 0 )
+// assertTrue(avl.isEmpty()) ;
+// else
+// assertFalse(avl.isEmpty()) ;
+ }
+
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/exthash/TestExtHashMem.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/exthash/TestExtHashMem.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/exthash/TestExtHashMem.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/exthash/TestExtHashMem.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,114 @@
+/**
+ * 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.exthash;
+
+import static structure.exthash.ExtHashMemTestBase.check;
+import static structure.exthash.ExtHashMemTestBase.create;
+import static structure.exthash.ExtHashMemTestBase.delete;
+import org.junit.AfterClass;
+import org.junit.BeforeClass;
+import org.junit.Test;
+import structure.exthash.ExtHashMem;
+import org.openjena.atlas.junit.BaseTest ;
+
+public class TestExtHashMem extends BaseTest
+{
+ @BeforeClass static public void setup()
+ {
+ ExtHashMem.NullOut = true ;
+ ExtHashMem.Checking = true ;
+ ExtHashMem.DefaultBucketSize = 4 ;
+ }
+
+ @AfterClass static public void teardown()
+ {
+
+ }
+
+ @Test public void create1()
+ {
+ ExtHashMem<Integer, String> eHash = new ExtHashMem<Integer, String>() ;
+ check(eHash) ;
+ }
+
+// @Test public void create2()
+// { ExtHash eHash = build() ; assertNotNull(eHash) ; }
+
+ @Test public void insert1()
+ {
+ ExtHashMem<Integer, String> eHash = create(1) ;
+ check(eHash, 1) ;
+ assertEquals(eHash.get(1), "X1") ;
+ assertEquals(1, eHash.size()) ;
+
+ }
+
+ @Test public void insert2()
+ {
+ ExtHashMem<Integer, String> eHash = create(1,2) ;
+ check(eHash, 1, 2) ;
+ assertEquals(eHash.get(1), "X1") ;
+ assertEquals(eHash.get(2), "X2") ;
+ assertEquals(2, eHash.size()) ;
+ }
+
+ @Test public void insert3()
+ {
+ ExtHashMem<Integer, String> eHash = create(1,2,3,4,5,6,7,8) ;
+ check(eHash, 1, 2, 3, 4, 5, 6, 7, 8) ;
+ }
+
+ // Nasty cases
+ @Test public void insert4()
+ {
+ ExtHashMem<Integer, String> eHash = create(0,2,4,8,16) ;
+ assertEquals(5, eHash.size()) ;
+ }
+
+ @Test public void delete1()
+ {
+ ExtHashMem<Integer, String> eHash = createAndCheck(1) ;
+ assertEquals(1, eHash.size()) ;
+ delete(eHash, 1) ;
+ assertFalse(eHash.contains(1)) ;
+ assertEquals(0, eHash.size()) ;
+ }
+
+ @Test public void delete2()
+ {
+ ExtHashMem<Integer, String> eHash = createAndCheck(1, 2, 3, 4, 5, 6, 7, 8) ;
+ delete(eHash, 1, 2, 3, 4, 5, 6, 7, 8) ;
+ check(eHash) ;
+ }
+
+ @Test public void delete3()
+ {
+ ExtHashMem<Integer, String> eHash = createAndCheck(1, 2, 3, 4, 5, 6, 7, 8) ;
+ delete(eHash, 8, 7, 6, 5, 4, 3, 2, 1) ;
+ check(eHash) ;
+ }
+
+ static private ExtHashMem<Integer, String> createAndCheck(int... keys)
+ {
+ ExtHashMem<Integer, String> eHash = create(keys) ;
+ check(eHash, keys);
+ assertEquals(keys.length, eHash.size()) ;
+ return eHash ;
+ }
+}
Added: 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=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/RadixRun.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/RadixRun.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,131 @@
+/**
+ * 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.util.ArrayList ;
+import java.util.Iterator ;
+import java.util.List ;
+
+import org.junit.runner.JUnitCore ;
+import org.junit.runner.Result ;
+import org.openjena.atlas.junit.TextListener2 ;
+import org.openjena.atlas.lib.Bytes ;
+import org.openjena.atlas.logging.Log ;
+
+public class RadixRun
+{
+ public static void main(String ...argv)
+ {
+ Log.setLog4j() ;
+ Log.enable(RadixTree.class) ;
+ RadixTree.logging = false ;
+ //RadixTree.logging = true ;
+
+ if ( false )
+ {
+ JUnitCore runner = new org.junit.runner.JUnitCore() ;
+ runner.addListener(new TextListener2(System.out)) ;
+ //TestRadix.beforeClass() ;
+ Result result = runner.run(TestRadix.class) ;
+ //TestRadix.afterClass() ;
+ System.exit(0) ;
+ }
+
+ 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) ;
+
+ RadixTree.logging = true ;
+ Iterator<byte[]> iter = trie.iterator(new byte[]{1,2}, null) ;
+ for ( ; iter.hasNext() ; )
+ {
+ byte[] b = iter.next();
+ System.out.println(Bytes.asHex(b)) ;
+ }
+ System.exit(0) ;
+
+ //RadixTree.logging = true ;
+
+ //for ( int i = entries.size()-1 ; i >= 0 ; i-- )
+ for ( int i = 0 ; i < entries.size(); i++ )
+ {
+ byte[] arr = entries.get(i) ;
+ delete(trie, arr) ;
+ }
+
+ System.exit(0) ;
+ }
+
+// static void search(RadixTree trie, byte[] key)
+// {
+// System.out.println("Search--'"+Bytes.asHex(key)+"'") ;
+// RadixNode node = trie.search(key) ;
+// System.out.println("Search>> "+node) ;
+// System.out.println() ;
+// }
+
+ static void find(RadixTree trie, byte[] key)
+ {
+ System.out.println("Find --'"+Bytes.asHex(key)+"'") ;
+ RadixNode node = trie.find(key) ;
+ System.out.println("Find >> "+node) ;
+ System.out.println() ;
+ }
+
+
+ static void insert(RadixTree trie, byte[] key)
+ {
+ System.out.println("Insert--'"+Bytes.asHex(key)+"'") ;
+ boolean b2 = ( trie.find(key) == null ) ;
+ boolean b = trie.insert(key) ;
+ System.out.print(" >> "+b+" ["+b2+"]") ;
+ System.out.print(": ") ;
+ trie.printLeaves() ;
+ //trie.print();
+ System.out.flush() ;
+ if ( b != b2 )
+ System.err.println("Inconsistent (insert)") ;
+ trie.check() ;
+ }
+
+ static void delete(RadixTree trie, byte[] key)
+ {
+ System.out.println("Delete--'"+Bytes.asHex(key)+"'") ;
+ boolean b2 = ( trie.find(key) != null ) ;
+ boolean b = trie.delete(key) ;
+ System.out.print(" >> "+b+" ["+b2+"]") ;
+ System.out.print(": ") ;
+ trie.printLeaves() ;
+ trie.print();
+ System.out.flush() ;
+ if ( b != b2 )
+ System.err.println("Inconsistent (delete)") ;
+ trie.check() ;
+ }
+
+}
Added: 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=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/TestRadix.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/TestRadix.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,85 @@
+/**
+ * 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 org.junit.Test;
+import org.openjena.atlas.junit.BaseTest ;
+
+public class TestRadix extends BaseTest
+{
+ // Test order : This sequence of keys triggers every case of insert.
+
+ static byte[] key1 = { 2 , 4 , 6 , 8 } ;
+
+ static byte[] key2 = { 2 , 4 , 6 , 10 } ;
+ // Insert - shorter key
+ static byte[] key3 = { 2 } ;
+
+ // Insert - existing leaf
+ static byte[] key4 = { 2 , 4 , 6, 8 , 10 } ;
+
+ // Insert - partial prefix match.
+ static byte[] key5 = { 2 , 4 , 3 , 1 } ;
+
+ static byte[] key6 = { 0 , 1 , 2 , 3 , 4 } ;
+
+ @Test public void radix_01()
+ {
+ RadixTree t = new RadixTree() ;
+ test(0, t) ;
+ }
+
+ @Test public void radix_02()
+ {
+ RadixTree t = new RadixTree() ;
+ t.insert(new byte[]{1,2,3,4}) ;
+ test(1, t) ;
+ }
+
+ @Test public void radix_03()
+ {
+ RadixTree t = new RadixTree() ;
+ t.insert(new byte[]{1,2,3,4}) ;
+ t.insert(new byte[]{0,1,2,3}) ;
+ test(2, t) ;
+ }
+
+ @Test public void radix_04()
+ {
+ RadixTree t = new RadixTree() ;
+ t.insert(new byte[]{0,1,2,3}) ;
+ t.insert(new byte[]{1,2,3,4}) ;
+ test(2, t) ;
+ }
+
+ private static void insert(RadixTree t, byte[] key)
+ {
+ t.insert(key) ;
+ t.check();
+ RadixNode n = t.find(key) ;
+ assertNotNull(n) ;
+ assertEquals(key.length, n.lenFinish) ;
+ }
+
+ private static void test(int size, RadixTree t)
+ {
+ t.check();
+ assertEquals(size, t.size()) ;
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/skiplist/SkipListTestBase.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/skiplist/SkipListTestBase.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/skiplist/SkipListTestBase.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/skiplist/SkipListTestBase.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,194 @@
+/**
+ * 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.skiplist;
+
+import static org.openjena.atlas.lib.RandomLib.random;
+import static org.openjena.atlas.test.Gen.permute;
+import static org.openjena.atlas.test.Gen.rand;
+import static org.openjena.atlas.test.Gen.strings;
+import static java.lang.String.format;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.SortedSet;
+import java.util.TreeSet;
+
+import org.openjena.atlas.junit.BaseTest ;
+import org.openjena.atlas.test.ExecGenerator;
+import org.openjena.atlas.test.RepeatExecution;
+public class SkipListTestBase extends BaseTest
+{
+ public static void randTests(int maxLevel, int maxValue, int maxNumKeys, int iterations, boolean showProgess)
+ {
+ SkipListTestGenerator test = new SkipListTestGenerator(maxLevel, maxValue, maxNumKeys) ;
+ RepeatExecution.repeatExecutions(test, iterations, showProgess) ;
+ }
+
+ static class SkipListTestGenerator implements ExecGenerator
+ {
+ int maxNumKeys ;
+ int maxValue ;
+ int maxLevel ;
+
+ SkipListTestGenerator(int maxLevel, int maxValue, int maxNumKeys)
+ {
+ if ( maxValue <= maxNumKeys )
+ throw new IllegalArgumentException("SkipListTest: Max value less than number of recs") ;
+ this.maxLevel = maxLevel ;
+ this.maxValue = maxValue ;
+ this.maxNumKeys = maxNumKeys ;
+ }
+
+ @Override
+ public void executeOneTest()
+ {
+ int numKeys = random.nextInt(maxNumKeys)+1 ;
+ SkipListTestBase.randTest(maxLevel, maxValue, numKeys) ;
+ }
+ }
+
+ public static SkipList<Integer> create(int...recs)
+ {
+ SkipList<Integer> skiplist = new SkipList<Integer>() ;
+ for ( int i : recs )
+ skiplist.insert(i) ;
+ return skiplist ;
+ }
+
+ public static SkipList<Integer> delete(SkipList<Integer> skiplist, int...recs)
+ {
+ for ( int i : recs )
+ skiplist.delete(i) ;
+ return skiplist ;
+ }
+
+ public static void check(SkipList<Integer> skiplist, int...recs)
+ {
+ skiplist.check() ;
+ for ( int r : recs )
+ assertTrue(skiplist.contains(r)) ;
+
+ // XXX
+// List<Integer> x = skiplist.calcRecords() ;
+// SortedSet<Integer> r = new TreeSet<Integer>() ;
+//
+// // -- Sort to list.
+// for ( int i : recs )
+// r.add(i) ;
+//
+// List<Integer> z = new ArrayList<Integer>() ;
+// for ( int i : r )
+// z.add(i) ;
+// // --
+//
+// assertEquals(z, x) ;
+//
+// if ( r.size() > 0 )
+// {
+// Integer min = z.get(0) ;
+// Integer max = z.get(r.size()-1) ;
+// assertEquals(min, skiplist.min()) ;
+// assertEquals(max, skiplist.max()) ;
+// }
+ }
+
+ /* One random test : print the recs if there was a problem */
+
+ public static void randTest(int maxLevel, int maxValue, int numKeys)
+ {
+ if ( numKeys >= 3000 )
+ System.err.printf("Warning: too many recs\n") ;
+
+ int[] recs1 = rand(numKeys, 0, maxValue) ;
+ int[] recs2 = permute(recs1, 4*numKeys) ;
+ try {
+ SkipList<Integer> skiplist = buildSkipList(maxLevel, recs1);
+ if ( true )
+ {
+ // Checking tests.
+ check(skiplist, recs2);
+ testIteration(skiplist, recs1, 10) ;
+ }
+ testDelete(skiplist, recs2) ;
+ } catch (RuntimeException ex)
+ {
+ System.err.printf("int maxLevel=%d ;\n", maxLevel) ;
+ System.err.printf("int[] recs1 = {%s} ;\n", strings(recs1)) ;
+ System.err.printf("int[] recs2 = {%s}; \n", strings(recs2)) ;
+ throw ex ;
+ }
+ }
+
+ private static SkipList<Integer> buildSkipList(int maxLevel, int[] records)
+ {
+ SkipList<Integer> skiplist = new SkipList<Integer>(maxLevel) ;
+ for ( int r : records )
+ skiplist.insert(r) ;
+ skiplist.check();
+ return skiplist ;
+ }
+
+ private static void testDelete(SkipList<Integer> skiplist, int[] recs)
+ {
+ for ( int r : recs )
+ skiplist.delete(r) ;
+ skiplist.check();
+ for ( int r : recs )
+ assertFalse(skiplist.contains(r)) ;
+ }
+
+ public static void testIteration(SkipList<Integer> skiplist, int[] recs, int numIterations)
+ {
+ for ( int r : recs )
+ assertTrue(skiplist.contains(r)) ;
+
+ // Shared across test-lets
+ SortedSet<Integer> x = new TreeSet<Integer>() ;
+ for ( int v : recs )
+ x.add(v) ;
+
+ for ( int i = 0 ; i < numIterations ; i++ )
+ {
+ int lo = random.nextInt(recs.length) ;
+ int hi = random.nextInt(recs.length) ;
+ if ( lo > hi )
+ {
+ int t = lo ;
+ lo = hi ;
+ hi = t ;
+ }
+ // Does not consider nulls - assumed to be part of functional testing.
+ // Tweak lo and hi
+ if ( lo != 0 && random.nextFloat() < 0.5 )
+ lo-- ; // Negatives confuse the int/record code.
+ if ( random.nextFloat() < 0.5 )
+ hi++ ;
+
+ List<Integer> slice = new ArrayList<Integer>(recs.length) ;
+ for ( int r : skiplist.records(lo, hi) )
+ slice.add(r) ;
+
+ List<Integer> expected = new ArrayList<Integer>(recs.length) ;
+ for ( Integer ii : x.subSet(lo, hi) )
+ expected.add(ii) ;
+ assertEquals(format("(%d,%d)",lo, hi), expected, slice) ;
+ }
+ }
+
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/skiplist/TestSkipList.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/skiplist/TestSkipList.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/skiplist/TestSkipList.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/skiplist/TestSkipList.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,155 @@
+/**
+ * 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.skiplist;
+
+import static java.lang.String.format;
+import static structure.skiplist.SkipListTestBase.create;
+import static structure.skiplist.SkipListTestBase.delete;
+import static structure.skiplist.SkipListTestBase.testIteration;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.junit.Test;
+import structure.skiplist.SkipList;
+import org.openjena.atlas.junit.BaseTest ;
+
+
+public class TestSkipList extends BaseTest
+{
+ static {
+ SkipList.Checking = true ;
+ //SkipList.Logging = false ;
+ }
+
+ @Test public void skiplist_01()
+ {
+ SkipList<Integer> sk = new SkipList<Integer>(3) ;
+ sk.check() ;
+ }
+
+ @Test public void skiplist_02()
+ {
+ SkipList<Integer> sk = new SkipList<Integer>(3) ;
+ sk.insert(3) ;
+ assertTrue(sk.contains(3)) ;
+ assertEquals(1, sk.size()) ;
+ sk.check() ;
+ }
+
+ @Test public void skiplist_03()
+ {
+ SkipList<Integer> sk = new SkipList<Integer>(3) ;
+ sk.insert(3) ;
+ sk.insert(3) ;
+ assertTrue(sk.contains(3)) ;
+ assertEquals(1, sk.size()) ;
+ sk.check() ;
+ }
+
+ @Test public void skiplist_04()
+ {
+ SkipList<Integer> sk = new SkipList<Integer>(3) ;
+ sk.insert(3) ;
+ sk.insert(4) ;
+ assertTrue(sk.contains(3)) ;
+ assertTrue(sk.contains(4)) ;
+ assertEquals(2, sk.size()) ;
+ sk.check() ;
+ }
+
+ @Test public void skiplist_05()
+ {
+ SkipList<Integer> sk = new SkipList<Integer>(3) ;
+ sk.insert(4) ;
+ sk.insert(3) ;
+ assertTrue(sk.contains(3)) ;
+ assertTrue(sk.contains(4)) ;
+ assertEquals(2, sk.size()) ;
+ sk.check() ;
+ }
+
+ @Test public void skiplist_06()
+ {
+ SkipList<Integer> sk = new SkipList<Integer>(3) ;
+ sk.insert(4) ;
+ assertTrue(sk.contains(4)) ;
+ sk.delete(4) ;
+ assertFalse(sk.contains(4)) ;
+ assertEquals(0, sk.size()) ;
+ sk.check() ;
+ }
+
+ @Test public void skiplist_07()
+ {
+ SkipList<Integer> sk = new SkipList<Integer>(3) ;
+ sk.insert(4) ;
+ assertTrue(sk.contains(4)) ;
+ sk.delete(3) ;
+ assertTrue(sk.contains(4)) ;
+ assertEquals(1, sk.size()) ;
+ sk.check() ;
+ }
+
+ @Test public void skiplist_08()
+ {
+ int[] r = { 1,2,3,4,5,6,7,8,9} ;
+ SkipList<Integer> sk = create(r) ;
+ sk.check() ;
+ delete(sk, r) ;
+ assertEquals(0, sk.size()) ;
+ sk.check() ;
+ }
+
+ @Test public void skiplist_09()
+ {
+ int[] r = { 1,2,3,4,5,6,7,8,9} ;
+ SkipList<Integer> sk = create(r) ;
+ sk.check() ;
+ testIteration(sk, r, 5) ;
+ }
+
+ @Test public void skiplist_10()
+ {
+ int[] r = { 1,2,3,4,5,6,7,8,9} ;
+ SkipList<Integer> sk = create(r) ;
+ testIter(sk, 2, 4, 2,3) ;
+ testIter(sk, -1,4, 1,2,3) ;
+ testIter(sk, -1,99, r) ;
+ }
+
+ static void testIter(SkipList<Integer> sk, Integer lo, Integer hi, int... ans)
+ {
+ List<Integer> x = new ArrayList<Integer>() ;
+ for ( int r : sk.records(lo, hi))
+ {
+ x.add(r) ;
+ }
+
+ assertEquals(ans.length, x.size()) ;
+
+
+ List<Integer> y = new ArrayList<Integer>() ;
+ for ( Integer ii : ans )
+ y.add(ii) ;
+ assertEquals(format("(%s,%s)",lo, hi), y, x) ;
+
+ }
+
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/tree/TestTree.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/tree/TestTree.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/tree/TestTree.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/tree/TestTree.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,61 @@
+/**
+ * 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.tree;
+
+import java.util.List;
+
+import org.junit.Test;
+import org.openjena.atlas.junit.BaseTest ;
+
+public class TestTree extends BaseTest
+{
+ static TreeNode<String> A = new TreeNode<String>("A") ;
+ static TreeNode<String> B = new TreeNode<String>("B") ;
+ static TreeNode<String> C = new TreeNode<String>("C") ;
+ static TreeNode<String> D = new TreeNode<String>("D") ;
+
+ @Test public void tree1()
+ {
+ TreeNode<String> x = new TreeNode<String>("A") ;
+ x.insert("B") ;
+ List<String> recs = x.records() ;
+ assertEquals(2, recs.size()) ;
+ assertEquals("A", recs.get(0)) ;
+ assertEquals("B", recs.get(1)) ;
+ }
+
+
+ @Test public void tree10()
+ {
+ TreeNode<String> x = new TreeNode<String>("K3", new TreeNode<String>("K1", A, new TreeNode<String>("K2", B, C)), D) ;
+ List<String> before = x.records() ;
+ x.pivotLeftRight() ;
+ List<String> after = x.records() ;
+ assertEquals(before, after) ;
+ }
+
+ @Test public void tree11()
+ {
+ TreeNode<String> x = new TreeNode<String>("K1", A, new TreeNode<String>("K3", new TreeNode<String>("K2", B, C), D)) ;
+ List<String> before = x.records() ;
+ x.pivotRightLeft() ;
+ List<String> after = x.records() ;
+ assertEquals(before, after) ;
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/ttree/MainTTree.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/ttree/MainTTree.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/ttree/MainTTree.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/ttree/MainTTree.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,71 @@
+/**
+ * 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.ttree;
+
+import structure.OrderedSet;
+import structure.OrderedSetTestLib;
+import org.openjena.atlas.io.IndentedWriter;
+import org.openjena.atlas.test.Gen;
+
+public class MainTTree
+{
+
+ public static void ttree()
+ {
+ // Insertion element to log. Set -1 for all logged, set very large for no logging
+// {
+// String a[] = { "perf", "50", "500" } ;
+// test.TTreeRun.main(a) ;
+// System.exit(0) ;
+// }
+
+ TTree.Logging = true ;
+
+ int[] r1 = {15, 99, 59, 94, 35, 45, 66} ;
+ int[] r2 = {66, 15, 45, 94, 99, 35, 59};
+ // int[] r1 = {8, 133, 22, 83, 74, 39, 72, 81, 91, 4, 26, 56, 0, 68} ;
+ // int[] r2 = {0, 83, 56, 133, 74, 72, 26, 39, 22, 68, 8, 91, 81, 4};
+
+ try {
+ OrderedSet<Integer> sIndx = new TTree<Integer>(4,3) ;
+ for ( int i : r1 )
+ sIndx.add(i) ;
+ OrderedSetTestLib.check(sIndx, r1) ; // These throw java.lang.AssertionError. - catch that
+ OrderedSetTestLib.delete(sIndx, r2) ;
+
+ sIndx.output(IndentedWriter.stdout) ;
+
+ OrderedSetTestLib.check(sIndx) ;
+ } catch (RuntimeException ex)
+ {
+ System.err.printf("int[] r1 = {%s} ;\n", Gen.strings(r1)) ;
+ System.err.printf("int[] r2 = {%s}; \n", Gen.strings(r2)) ;
+ throw ex ;
+ }
+ catch (AssertionError ex)
+ {
+ System.err.printf("int[] r1 = {%s} ;\n", Gen.strings(r1)) ;
+ System.err.printf("int[] r2 = {%s}; \n", Gen.strings(r2)) ;
+ throw ex ;
+ }
+ System.exit(0) ;
+
+ }
+
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/ttree/TestTTree.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/ttree/TestTTree.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/ttree/TestTTree.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/ttree/TestTTree.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,37 @@
+/**
+ * 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.ttree;
+
+import structure.OrderedSet;
+import structure.OrderedSetTestBase;
+
+public class TestTTree extends OrderedSetTestBase
+{
+ static {
+ TTree.Checking = true ;
+ TTree.Logging = false ;
+ TTree.Verbose = false ;
+ }
+
+ @Override
+ protected OrderedSet<Integer> create()
+ {
+ return new TTree<Integer>(3,2) ;
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/test/AVLRun.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/test/AVLRun.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/test/AVLRun.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/test/AVLRun.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,222 @@
+/**
+ * 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 test;
+
+import static org.openjena.atlas.lib.RandomLib.random ;
+import static org.openjena.atlas.test.Gen.permute ;
+import static org.openjena.atlas.test.Gen.rand ;
+import static org.openjena.atlas.test.Gen.strings ;
+
+import java.io.PrintStream ;
+import java.util.ArrayList ;
+import java.util.Arrays ;
+import java.util.List ;
+
+import org.openjena.atlas.logging.Log ;
+import org.openjena.atlas.test.ExecGenerator ;
+import org.openjena.atlas.test.RepeatExecution ;
+import structure.OrderedSet ;
+import structure.OrderedSetTestFactory ;
+import structure.OrderedSetTestLib ;
+import structure.avl.AVL ;
+
+public abstract class AVLRun
+{
+ // TODO Combine with TTreeRun
+ static boolean showProgress = true ;
+
+ static public void main(String...a)
+ {
+ List<String> args = new ArrayList<String>(Arrays.asList(a)) ;
+ if ( args.size() == 0 )
+ {
+ System.err.println("No subcommand") ;
+ System.exit(1) ;
+ }
+ String subCmd = args.remove(0) ;
+ if ( "test".equalsIgnoreCase(subCmd) )
+ new Test().exec(args) ;
+ else if ( "perf".equalsIgnoreCase(subCmd) )
+ {
+ showProgress = false ;
+ new Perf().exec(args) ;
+ }
+ else
+ {
+ System.err.println("Unknown subcommand: "+subCmd) ;
+ System.exit(1) ;
+ }
+ }
+
+ public void exec(List<String> args)
+ {
+ args = processArgs(args) ;
+ int numKeys = Integer.parseInt(args.get(0)) ;
+ int iterations = Integer.parseInt(args.get(1)) ;
+ exec(numKeys, iterations) ;
+ }
+
+ protected abstract void exec(int numKeys, int iterations) ;
+
+
+ // ---- Test
+ public static class Test extends AVLRun
+ {
+ @Override
+ protected void exec(int numKeys, int iterations)
+ {
+ showProgress = true ;
+ AVL.Checking = true ;
+ AVL.Verbose = false ;
+ AVL.Logging = false ;
+ OrderedSetTestLib.randTests(factory, 10*numKeys, numKeys, iterations, showProgress) ;
+ }
+ }
+
+ // ---- Performance
+ public static class Perf extends AVLRun
+ {
+ @Override
+ public void exec(List<String> args)
+ {
+ showProgress = false ;
+ AVL.Checking = false ;
+ AVL.Verbose = false ;
+ AVL.Logging = false ;
+ super.exec(args) ;
+ }
+
+ @Override
+ protected void exec(int numKeys, int iterations)
+ {
+ RandomGen rand = new RandomGen(100*numKeys, numKeys) ;
+ RepeatExecution.repeatExecutions(rand, iterations, showProgress) ;
+ }
+ }
+
+ List<String> processArgs(List<String> args)
+ {
+ Log.setLog4j() ;
+ int i = 0 ;
+ while ( args.size()>0 )
+ {
+ if ( !args.get(0).startsWith("-") )
+ break ;
+
+ String a = args.remove(0) ;
+ if ( a.startsWith("--") )
+ a = a.substring(2) ;
+ else
+ a = a.substring(1) ;
+
+ if ( a.equals("h") || a.equals("help") )
+ {
+ usage(System.out) ;
+ System.exit(0) ;
+ }
+ else if ( a.equalsIgnoreCase("check") )
+ {
+ AVL.Checking = true ;
+ }
+ else if ( a.equalsIgnoreCase("display") )
+ {
+ showProgress = ! showProgress ;
+ }
+ else
+ {
+ System.err.println("Unknown argument: "+a) ;
+ System.exit(1) ;
+ }
+ }
+
+ if ( args.size() != 2 )
+ {
+ usage(System.err) ;
+ System.exit(1) ;
+ }
+ return args ;
+ }
+
+ public static void usage(PrintStream printStream)
+ {
+ printStream.println("Usage: OPTIONS NumKeys Iterations") ;
+ printStream.println("Options:") ;
+ printStream.println(" --display") ;
+ printStream.println(" --check") ;
+ }
+
+
+ static class RandomGen implements ExecGenerator
+ {
+ int maxNumKeys ;
+ int maxValue ;
+
+ RandomGen(int maxValue, int maxNumKeys)
+ {
+ if ( maxValue <= maxNumKeys )
+ throw new IllegalArgumentException("AVLRun: Max value less than number of keys") ;
+ this.maxValue = maxValue ;
+ this.maxNumKeys = maxNumKeys ;
+ }
+
+ @Override
+ public void executeOneTest()
+ {
+ int numKeys = random.nextInt(maxNumKeys)+1 ;
+ perfTest(maxValue, numKeys) ;
+ }
+ }
+
+
+ /* Performance test : print the keys if there was a problem */
+
+ public static void perfTest(int maxValue, int numKeys)
+ {
+ if ( numKeys >= 3000 )
+ System.err.printf("Warning: too many keys\n") ;
+
+ int[] r1 = rand(numKeys, 0, maxValue) ;
+ int[] r2 = permute(r1, numKeys) ;
+ try {
+ OrderedSet<Integer> avl = factory.create(r1) ;
+ OrderedSetTestLib.delete(avl, r2) ;
+ } catch (RuntimeException ex)
+ {
+ System.err.printf("int[] r1 = {%s} ;\n", strings(r1)) ;
+ System.err.printf("int[] r2 = {%s}; \n", strings(r2)) ;
+ throw ex ;
+ }
+ }
+
+ static OrderedSetTestFactory factory = new OrderedSetTestFactory()
+ {
+
+ @Override
+ public OrderedSet<Integer> create(int ... recs)
+ {
+
+ AVL<Integer> avl = new AVL<Integer>() ;
+ for ( int i : recs )
+ avl.add(i) ;
+ return avl ;
+ }
+ } ;
+
+
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/test/ExtHashMemRun.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/test/ExtHashMemRun.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/test/ExtHashMemRun.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/test/ExtHashMemRun.java Fri Sep 30 15:01:53 2011
@@ -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 test;
+
+import static org.openjena.atlas.lib.RandomLib.random ;
+import static org.openjena.atlas.test.Gen.permute ;
+import static org.openjena.atlas.test.Gen.rand ;
+import static org.openjena.atlas.test.Gen.strings ;
+
+import java.io.PrintStream ;
+import java.util.ArrayList ;
+import java.util.Arrays ;
+import java.util.List ;
+
+import org.openjena.atlas.logging.Log ;
+import org.openjena.atlas.test.ExecGenerator ;
+import org.openjena.atlas.test.RepeatExecution ;
+import structure.exthash.ExtHashMem ;
+import structure.exthash.ExtHashMemTestBase ;
+
+import com.hp.hpl.jena.tdb.index.ext.ExtHash ;
+import com.hp.hpl.jena.tdb.sys.SystemTDB ;
+
+public abstract class ExtHashMemRun
+{
+ static boolean showProgress = true ;
+
+ static public void main(String...a)
+ {
+ List<String> args = new ArrayList<String>(Arrays.asList(a)) ;
+ if ( args.size() == 0 )
+ {
+ System.err.println("No subcommand") ;
+ System.exit(1) ;
+ }
+ String subCmd = args.remove(0) ;
+ if ( "test".equalsIgnoreCase(subCmd) )
+ new Test().exec(args) ;
+ else if ( "perf".equalsIgnoreCase(subCmd) )
+ new Perf().exec(args) ;
+ else
+ {
+ System.err.println("Unknown subcommand: "+subCmd) ;
+ System.exit(1) ;
+ }
+ }
+
+ public void exec(List<String> args)
+ {
+ args = processArgs(args) ;
+ int numKeys = Integer.parseInt(args.get(0)) ;
+ int iterations = Integer.parseInt(args.get(1)) ;
+ exec(numKeys, iterations) ;
+ }
+
+ protected abstract void exec(int numKeys, int iterations) ;
+
+ // ---- Test
+ public static class Test extends ExtHashMemRun
+ {
+ @Override
+ protected void exec(int numKeys, int iterations)
+ {
+ System.out.println("ExtHashMemTest") ;
+ ExtHashMemTestBase.randTests(10*numKeys, numKeys, iterations, showProgress) ;
+ }
+ }
+
+ // ---- Perfromance
+ public static class Perf extends ExtHashMemRun
+ {
+ @Override
+ public void exec(List<String> args)
+ {
+ showProgress = false ;
+ ExtHash.Checking = false ;
+ ExtHash.Logging = false ;
+ SystemTDB.NullOut = false ;
+ super.exec(args) ;
+ }
+
+ @Override
+ protected void exec(int numKeys, int iterations)
+ {
+ RandomGen rand = new RandomGen(100*numKeys, numKeys) ;
+ RepeatExecution.repeatExecutions(rand, iterations, showProgress) ;
+ }
+ }
+
+ static class RandomGen implements ExecGenerator
+ {
+ int maxNumKeys ;
+ int maxValue ;
+
+ RandomGen(int maxValue, int maxNumKeys)
+ {
+ if ( maxValue <= maxNumKeys )
+ throw new IllegalArgumentException("ExtHash: Max value less than number of keys") ;
+ this.maxValue = maxValue ;
+ this.maxNumKeys = maxNumKeys ;
+ }
+
+ @Override
+ public void executeOneTest()
+ {
+ int numKeys = random.nextInt(maxNumKeys)+1 ;
+ perfTest(maxValue, numKeys) ;
+ }
+
+ /* Performance test : print the keys if there was a problem */
+ public static void perfTest(int maxValue, int numKeys)
+ {
+ if ( numKeys >= 3000 )
+ System.err.printf("Warning: too many keys\n") ;
+
+ int[] keys1 = rand(numKeys, 0, maxValue) ;
+ int[] keys2 = permute(keys1, numKeys) ;
+ try {
+ ExtHashMem<Integer, String> table = ExtHashMemTestBase.create(keys1) ;
+ ExtHashMemTestBase.delete(table, keys2) ;
+ } catch (RuntimeException ex)
+ {
+ System.err.printf("int[] keys1 = {%s} ;\n", strings(keys1)) ;
+ System.err.printf("int[] keys2 = {%s}; \n", strings(keys2)) ;
+ throw ex ;
+ }
+ }
+ }
+
+ List<String> processArgs(List<String> args)
+ {
+ Log.setLog4j() ;
+ int i = 0 ;
+ while ( args.size()>0 )
+ {
+ if ( !args.get(0).startsWith("-") )
+ break ;
+
+ String a = args.remove(0) ;
+ if ( a.startsWith("--") )
+ a = a.substring(2) ;
+ else
+ a = a.substring(1) ;
+
+ if ( a.equals("h") || a.equals("help") )
+ {
+ usage(System.out) ;
+ System.exit(0) ;
+ }
+ else if ( a.equals("v") )
+ {}
+ else if ( a.equalsIgnoreCase("check") )
+ {
+ ExtHash.Checking = true ;
+ }
+ else if ( a.equalsIgnoreCase("display") )
+ {
+ showProgress = ! showProgress ;
+ }
+ else
+ {
+ System.err.println("Unknown argument: "+a) ;
+ System.exit(1) ;
+ }
+ }
+
+ if ( args.size() != 2 )
+ {
+ usage(System.err) ;
+ System.exit(1) ;
+ }
+ return args ;
+ }
+
+ public static void usage(PrintStream printStream)
+ {
+ printStream.println("Usage: OPTIONS NumKeys Iterations") ;
+ printStream.println("Options:") ;
+ printStream.println(" --check") ;
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/test/SkipListRun.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/test/SkipListRun.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/test/SkipListRun.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/test/SkipListRun.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,200 @@
+/**
+ * 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 test;
+
+import static org.openjena.atlas.lib.RandomLib.random ;
+import static org.openjena.atlas.test.Gen.permute ;
+import static org.openjena.atlas.test.Gen.rand ;
+import static org.openjena.atlas.test.Gen.strings ;
+import static structure.skiplist.SkipListTestBase.create ;
+import static structure.skiplist.SkipListTestBase.delete ;
+
+import java.io.PrintStream ;
+import java.util.ArrayList ;
+import java.util.Arrays ;
+import java.util.List ;
+
+import org.openjena.atlas.logging.Log ;
+import org.openjena.atlas.test.ExecGenerator ;
+import org.openjena.atlas.test.RepeatExecution ;
+import structure.avl.AVL ;
+import structure.skiplist.SkipList ;
+import structure.skiplist.SkipListTestBase ;
+
+public abstract class SkipListRun
+{
+ static boolean showProgress = true ;
+
+ static public void main(String...a)
+ {
+ List<String> args = new ArrayList<String>(Arrays.asList(a)) ;
+ if ( args.size() == 0 )
+ {
+ System.err.println("No subcommand") ;
+ System.exit(1) ;
+ }
+ String subCmd = args.remove(0) ;
+ if ( "test".equalsIgnoreCase(subCmd) )
+ new Test().exec(args) ;
+ else if ( "perf".equalsIgnoreCase(subCmd) )
+ new Perf().exec(args) ;
+ else
+ {
+ System.err.println("Unknown subcommand: "+subCmd) ;
+ System.exit(1) ;
+ }
+ }
+
+ public void exec(List<String> args)
+ {
+ args = processArgs(args) ;
+ int numKeys = Integer.parseInt(args.get(0)) ;
+ int iterations = Integer.parseInt(args.get(1)) ;
+
+ int maxLevel = 20 ;
+ if ( args.size() == 3 )
+ maxLevel = Integer.parseInt(args.get(2)) ;
+ exec(maxLevel ,numKeys, iterations) ;
+ }
+
+ protected abstract void exec(int maxLevel, int numKeys, int iterations) ;
+
+
+ // ---- Test
+ public static class Test extends SkipListRun
+ {
+ @Override
+ protected void exec(int maxLevel, int numKeys, int iterations)
+ {
+ SkipListTestBase.randTests(maxLevel, 10*numKeys, numKeys, iterations, showProgress) ;
+ }
+ }
+
+ // ---- Performance
+ public static class Perf extends SkipListRun
+ {
+ @Override
+ public void exec(List<String> args)
+ {
+ showProgress = false ;
+ SkipList.Checking = false ;
+ SkipList.Logging = false ;
+ super.exec(args) ;
+ }
+
+ @Override
+ protected void exec(int maxLevel, int numKeys, int iterations)
+ {
+ RandomGen rand = new RandomGen(100*numKeys, numKeys) ;
+ RepeatExecution.repeatExecutions(rand, iterations, showProgress) ;
+ }
+ }
+
+ List<String> processArgs(List<String> args)
+ {
+ Log.setLog4j() ;
+ int i = 0 ;
+ while ( args.size()>0 )
+ {
+ if ( !args.get(0).startsWith("-") )
+ break ;
+
+ String a = args.remove(0) ;
+ if ( a.startsWith("--") )
+ a = a.substring(2) ;
+ else
+ a = a.substring(1) ;
+
+ if ( a.equals("h") || a.equals("help") )
+ {
+ usage(System.out) ;
+ System.exit(0) ;
+ }
+ else if ( a.equalsIgnoreCase("check") )
+ {
+ AVL.Checking = true ;
+ }
+ else if ( a.equalsIgnoreCase("display") )
+ {
+ showProgress = ! showProgress ;
+ }
+ else
+ {
+ System.err.println("Unknown argument: "+a) ;
+ System.exit(1) ;
+ }
+ }
+
+ if ( args.size() != 2 && args.size() != 3 )
+ {
+ usage(System.err) ;
+ System.exit(1) ;
+ }
+ return args ;
+ }
+
+ public static void usage(PrintStream printStream)
+ {
+ printStream.println("Usage: OPTIONS NumKeys Iterations [max level]") ;
+ printStream.println("Options:") ;
+ printStream.println(" --display") ;
+ printStream.println(" --check") ;
+ }
+
+
+ static class RandomGen implements ExecGenerator
+ {
+ int maxNumKeys ;
+ int maxValue ;
+
+ RandomGen(int maxValue, int maxNumKeys)
+ {
+ if ( maxValue <= maxNumKeys )
+ throw new IllegalArgumentException("SkipList: Max value less than number of keys") ;
+ this.maxValue = maxValue ;
+ this.maxNumKeys = maxNumKeys ;
+ }
+
+ @Override
+ public void executeOneTest()
+ {
+ int numKeys = random.nextInt(maxNumKeys)+1 ;
+ perfTest(maxValue, numKeys) ;
+ }
+ }
+
+
+ /* Performance test : print the keys if there was a problem */
+
+ static void perfTest(int maxValue, int numKeys)
+ {
+ int[] keys1 = rand(numKeys, 0, maxValue) ;
+ int[] keys2 = permute(keys1, 4*numKeys) ;
+ try {
+ SkipList<Integer> skiplist = create(keys1);
+ delete(skiplist, keys2) ;
+ } catch (RuntimeException ex)
+ {
+ //System.err.printf("int maxLevel=%d ;\n", maxLevel) ;
+ System.err.printf("int[] keys1 = {%s} ;\n", strings(keys1)) ;
+ System.err.printf("int[] keys2 = {%s}; \n", strings(keys2)) ;
+ throw ex ;
+ }
+ }
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/test/TTreeRun.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/test/TTreeRun.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/test/TTreeRun.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/test/TTreeRun.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,222 @@
+/**
+ * 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 test;
+
+import static org.openjena.atlas.lib.RandomLib.random ;
+import static org.openjena.atlas.test.Gen.permute ;
+import static org.openjena.atlas.test.Gen.rand ;
+import static org.openjena.atlas.test.Gen.strings ;
+
+import java.io.PrintStream ;
+import java.util.ArrayList ;
+import java.util.Arrays ;
+import java.util.List ;
+
+import org.openjena.atlas.logging.Log ;
+import org.openjena.atlas.test.ExecGenerator ;
+import org.openjena.atlas.test.RepeatExecution ;
+import structure.OrderedSet ;
+import structure.OrderedSetTestFactory ;
+import structure.OrderedSetTestLib ;
+import structure.ttree.TTree ;
+
+public abstract class TTreeRun
+{
+ // TODO Combine with AVLRun
+ static boolean showProgress = true ;
+
+ static public void main(String...a)
+ {
+ List<String> args = new ArrayList<String>(Arrays.asList(a)) ;
+ if ( args.size() == 0 )
+ {
+ System.err.println("No subcommand") ;
+ System.exit(1) ;
+ }
+ String subCmd = args.remove(0) ;
+ if ( "test".equalsIgnoreCase(subCmd) )
+ new Test().exec(args) ;
+ else if ( "perf".equalsIgnoreCase(subCmd) )
+ {
+ showProgress = false ;
+ new Perf().exec(args) ;
+ }
+ else
+ {
+ System.err.println("Unknown subcommand: "+subCmd) ;
+ System.exit(1) ;
+ }
+ }
+
+ public void exec(List<String> args)
+ {
+ args = processArgs(args) ;
+ int numKeys = Integer.parseInt(args.get(0)) ;
+ int iterations = Integer.parseInt(args.get(1)) ;
+ exec(numKeys, iterations) ;
+ }
+
+ protected abstract void exec(int numKeys, int iterations) ;
+
+
+ // ---- Test
+ public static class Test extends TTreeRun
+ {
+ @Override
+ protected void exec(int numKeys, int iterations)
+ {
+ TTree.Checking = true ;
+ TTree.Logging = false ;
+ TTree.NullOut = true ;
+ TTree.Verbose = false ;
+ OrderedSetTestLib.randTests(factory, 10*numKeys, numKeys, iterations, showProgress) ;
+ }
+ }
+
+ // ---- Performance
+ public static class Perf extends TTreeRun
+ {
+ @Override
+ public void exec(List<String> args)
+ {
+ showProgress = false ;
+ TTree.Checking = false ;
+ TTree.Logging = false ;
+ TTree.NullOut = false ;
+ TTree.Verbose = false ;
+ super.exec(args) ;
+ }
+
+ @Override
+ protected void exec(int numKeys, int iterations)
+ {
+ RandomGen rand = new RandomGen(100*numKeys, numKeys) ;
+ RepeatExecution.repeatExecutions(rand, iterations, showProgress) ;
+ }
+ }
+
+ List<String> processArgs(List<String> args)
+ {
+ Log.setLog4j() ;
+ int i = 0 ;
+ while ( args.size()>0 )
+ {
+ if ( !args.get(0).startsWith("-") )
+ break ;
+
+ String a = args.remove(0) ;
+ if ( a.startsWith("--") )
+ a = a.substring(2) ;
+ else
+ a = a.substring(1) ;
+
+ if ( a.equals("h") || a.equals("help") )
+ {
+ usage(System.out) ;
+ System.exit(0) ;
+ }
+ else if ( a.equalsIgnoreCase("check") )
+ {
+ TTree.Checking = true ;
+ }
+ else if ( a.equalsIgnoreCase("display") )
+ {
+ showProgress = ! showProgress ;
+ }
+ else
+ {
+ System.err.println("Unknown argument: "+a) ;
+ System.exit(1) ;
+ }
+ }
+
+ if ( args.size() != 2 )
+ {
+ usage(System.err) ;
+ System.exit(1) ;
+ }
+ return args ;
+ }
+
+ public static void usage(PrintStream printStream)
+ {
+ printStream.println("Usage: OPTIONS NumKeys Iterations") ;
+ printStream.println("Options:") ;
+ printStream.println(" --display") ;
+ printStream.println(" --check") ;
+ }
+
+
+ static class RandomGen implements ExecGenerator
+ {
+ int maxNumKeys ;
+ int maxValue ;
+
+ RandomGen(int maxValue, int maxNumKeys)
+ {
+ if ( maxValue <= maxNumKeys )
+ throw new IllegalArgumentException("AVLRun: Max value less than number of keys") ;
+ this.maxValue = maxValue ;
+ this.maxNumKeys = maxNumKeys ;
+ }
+
+ @Override
+ public void executeOneTest()
+ {
+ int numKeys = random.nextInt(maxNumKeys)+1 ;
+ perfTest(maxValue, numKeys) ;
+ }
+ }
+
+
+ /* Performance test : print the keys if there was a problem */
+
+ public static void perfTest(int maxValue, int numKeys)
+ {
+ if ( numKeys >= 3000 )
+ System.err.printf("Warning: too many keys\n") ;
+
+ int[] r1 = rand(numKeys, 0, maxValue) ;
+ int[] r2 = permute(r1, numKeys) ;
+ try {
+ OrderedSet<Integer> avl = factory.create(r1) ;
+ OrderedSetTestLib.delete(avl, r2) ;
+ } catch (RuntimeException ex)
+ {
+ System.err.printf("int[] r1 = {%s} ;\n", strings(r1)) ;
+ System.err.printf("int[] r2 = {%s}; \n", strings(r2)) ;
+ throw ex ;
+ }
+ }
+
+ static OrderedSetTestFactory factory = new OrderedSetTestFactory()
+ {
+ @Override
+ public OrderedSet<Integer> create(int ... recs)
+ {
+
+ TTree<Integer> ttree = new TTree<Integer>(4,3) ;
+ for ( int i : recs )
+ ttree.add(i) ;
+ return ttree ;
+ }
+ } ;
+
+
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/algebra2/AlgebraEngine.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/algebra2/AlgebraEngine.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/algebra2/AlgebraEngine.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/algebra2/AlgebraEngine.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,57 @@
+/**
+ * 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 algebra2;
+
+import java.util.List ;
+
+import com.hp.hpl.jena.sparql.core.Var ;
+
+/**
+ * All the operations peformed on tables.
+ */
+public interface AlgebraEngine
+{
+ // ?? List<Expr> for conditions
+ // Table : guesstimates of stats.
+ // ?? All joins take a condition.
+
+ public Table mergeJoin(Table table1, Table table2) ;
+
+ public Table indexJoin(Table table1, Table table2) ;
+
+ public Table sort(Table table, List<Var> order) ;
+
+ public Table innerLoopJoin(Table table1, Table table2) ;
+
+ public Table semiJoin(Table table1, Table table2) ;
+
+ public Table antiJoin(Table table1, Table table2) ;
+
+ /** SPARQL MINUS - antiJoin with modified join condition */
+ public Table minus(Table table1, Table table2) ;
+
+ public Table union(Table table1, Table table2) ;
+ public Table intersection(Table table1, Table table2) ;
+
+ public Table diff(Table table1, Table table2) ;
+ public Table filter(Table table, Condition condition) ;
+
+ public Table leftJoin(Table table1, Table table2, Condition cond) ;
+
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/algebra2/Condition.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/algebra2/Condition.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/algebra2/Condition.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/algebra2/Condition.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,24 @@
+/**
+ * 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 algebra2;
+
+public interface Condition
+{
+
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/algebra2/JoinEngine.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/algebra2/JoinEngine.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/algebra2/JoinEngine.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/algebra2/JoinEngine.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,146 @@
+/**
+ * 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 algebra2;
+
+import java.util.Iterator ;
+import java.util.List ;
+
+import org.openjena.atlas.lib.Tuple ;
+
+import com.hp.hpl.jena.sparql.core.Var ;
+import com.hp.hpl.jena.tdb.store.NodeId ;
+
+public class JoinEngine
+{
+ static int compare(Tuple<NodeId> t1, Tuple<NodeId> t2, List<Var> vars, List<Integer> indexes)
+ {
+ return 0 ;
+ }
+
+ static void mergeJoin(Iterator<Tuple<NodeId>> iter1, Iterator<Tuple<NodeId>> iter2, List<Integer> indexes)
+ {
+ /*
+ static void SortMergeJoin(List<KeyValuePair<int, string>> people,
+ List<KeyValuePair<int, string>> purchases)
+ {
+ // first we sort both lists
+ people.Sort(Compare);
+ purchases.Sort(Compare);
+
+ // then we do an interleaved linear scan to merge the sorted lists
+ int i = 0, j = 0;
+
+ while(i<people.Count & j<purchases.Count)
+ {
+ if (people[i].Key < purchases[j].Key)
+ i++;
+ else if (people[i].Key > purchases[j].Key)
+ j++;
+ else // must be a match
+ {
+ Console.WriteLine("Name index {0}, {1}, bought some {2} ",
+ people[i].Key, people[i].Value, purchases[j].Value);
+ j++;
+ }
+ }
+ }
+
+ static int Compare(KeyValuePair<int, string> a, KeyValuePair<int, string> b)
+ {
+ if (a.Key > b.Key)
+ return 1;
+
+ if (a.Key == b.Key)
+ return 0;
+
+ return -1;
+ }
+
+ --
+ public class MergeJoin
+ {
+ // Assume that left and right are already sorted
+ public static Relation Sort(Relation left, Relation right)
+ {
+ Relation output = new Relation();
+ while (!left.IsPastEnd() && !right.IsPastEnd())
+ {
+ if (left.Key == right.Key)
+ {
+ output.Add(left.Key);
+ left.Advance();
+ right.Advance();
+ }
+ else if (left.Key < right.Key)
+ left.Advance();
+ else //(left.Key > right.Key)
+ right.Advance();
+ }
+ return output;
+ }
+ }
+
+ */
+
+ // Sort must be total, not just on common vars
+
+ if ( ! iter1.hasNext() ) return ;
+ if ( ! iter2.hasNext() ) return ;
+
+ Tuple<NodeId> slot1 = iter1.next() ;
+ Tuple<NodeId> slot2 = iter1.next() ;
+
+ while(true)
+ {
+ int x = compare(slot1, slot2, null, indexes) ;
+ if ( x > 0 )
+ {
+ // LHS > RHS : advance LHS
+ if ( ! iter1.hasNext() )
+ return ;
+ slot1 = iter1.next() ;
+ continue ;
+ }
+ if ( x < 0 )
+ {
+ // LHS < RHS : advance RHS
+ if ( ! iter2.hasNext() )
+ return ;
+ slot2 = iter2.next() ;
+ continue ;
+ }
+ // Compares.
+ // Advance each to count the number completely the same.
+ int N1 = 0 ;
+ int N2 = 0 ;
+
+
+ Tuple<NodeId> x1 = slot1 ;
+ Tuple<NodeId> x2 = slot2 ;
+
+
+
+ yield(slot1, slot2, N1*N2) ;
+ // Now what?
+ }
+ }
+
+ private static void yield(Tuple<NodeId> t1, Tuple<NodeId> t2, int number)
+ {}
+}
Added: incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/algebra2/Table.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/algebra2/Table.java?rev=1177690&view=auto
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/algebra2/Table.java (added)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/algebra2/Table.java Fri Sep 30 15:01:53 2011
@@ -0,0 +1,46 @@
+/**
+ * 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 algebra2;
+
+import java.util.Iterator ;
+
+import org.openjena.atlas.lib.Tuple;
+
+import com.hp.hpl.jena.sparql.core.Var ;
+import com.hp.hpl.jena.sparql.engine.binding.Binding ;
+
+/** Abstraction of a set of tuples (ragged - not every column is defined in every row) */
+public interface Table
+{
+ // Later : QueryIterator or QI adapter.
+
+ /** hint we may travserse multiple times */
+ public void materialize() ;
+
+ /** The bindings are ordered by these columns
+ * All these are guaranteed to be bound (??)
+ */
+ public Tuple<Var> sortOrder() ;
+
+ /** The rows */
+ public Iterator<Binding> iterator() ;
+
+ /** A guess at the length of the table - -1 for no idea */
+ public long estimatedSize() ;
+}