diff options
Diffstat (limited to 'test')
68 files changed, 1113 insertions, 230 deletions
diff --git a/test/de/lmu/ifi/dbs/elki/AllTests.java b/test/de/lmu/ifi/dbs/elki/AllTests.java index cc0e1af6..84f8e407 100644 --- a/test/de/lmu/ifi/dbs/elki/AllTests.java +++ b/test/de/lmu/ifi/dbs/elki/AllTests.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/JUnit4Test.java b/test/de/lmu/ifi/dbs/elki/JUnit4Test.java index 023d0905..fc44d409 100644 --- a/test/de/lmu/ifi/dbs/elki/JUnit4Test.java +++ b/test/de/lmu/ifi/dbs/elki/JUnit4Test.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/AbstractSimpleAlgorithmTest.java b/test/de/lmu/ifi/dbs/elki/algorithm/AbstractSimpleAlgorithmTest.java index 894a314f..7b6fbbfa 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/AbstractSimpleAlgorithmTest.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/AbstractSimpleAlgorithmTest.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -34,7 +34,6 @@ import java.util.Iterator; import java.util.List; import de.lmu.ifi.dbs.elki.algorithm.clustering.trivial.ByLabelClustering; -import de.lmu.ifi.dbs.elki.algorithm.clustering.trivial.ByLabelHierarchicalClustering; import de.lmu.ifi.dbs.elki.data.Cluster; import de.lmu.ifi.dbs.elki.data.Clustering; import de.lmu.ifi.dbs.elki.data.model.Model; @@ -46,7 +45,7 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.datasource.FileBasedDatabaseConnection; import de.lmu.ifi.dbs.elki.datasource.filter.FixedDBIDsFilter; -import de.lmu.ifi.dbs.elki.evaluation.paircounting.PairCountingFMeasure; +import de.lmu.ifi.dbs.elki.evaluation.clustering.ClusterContingencyTable; import de.lmu.ifi.dbs.elki.evaluation.roc.ComputeROCCurve; import de.lmu.ifi.dbs.elki.logging.Logging; import de.lmu.ifi.dbs.elki.result.Result; @@ -155,26 +154,9 @@ public abstract class AbstractSimpleAlgorithmTest { ByLabelClustering bylabel = new ByLabelClustering(); Clustering<Model> rbl = bylabel.run(database); - double score = PairCountingFMeasure.compareClusterings(clustering, rbl, 1.0); - if(logger.isVerbose()) { - logger.verbose(this.getClass().getSimpleName() + " score: " + score + " expect: " + expected); - } - org.junit.Assert.assertEquals(this.getClass().getSimpleName() + ": Score does not match.", expected, score, 0.0001); - } - - /** - * Test the clustering result by comparing the score with an expected value. - * - * @param database Database to test - * @param clustering Clustering result - * @param expected Expected score - */ - protected <O> void testFMeasureHierarchical(Database database, Clustering<?> clustering, double expected) { - // Run by-label as reference - ByLabelHierarchicalClustering bylabel = new ByLabelHierarchicalClustering(); - Clustering<Model> rbl = bylabel.run(database); - - double score = PairCountingFMeasure.compareClusterings(clustering, rbl, 1.0, false, true); + ClusterContingencyTable ct = new ClusterContingencyTable(true, false); + ct.process(clustering, rbl); + double score = ct.getPaircount().f1Measure(); if(logger.isVerbose()) { logger.verbose(this.getClass().getSimpleName() + " score: " + score + " expect: " + expected); } diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/TestKNNJoin.java b/test/de/lmu/ifi/dbs/elki/algorithm/TestKNNJoin.java index fa5dbc14..c846aa6b 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/TestKNNJoin.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/TestKNNJoin.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -37,9 +37,9 @@ import de.lmu.ifi.dbs.elki.database.QueryUtil; import de.lmu.ifi.dbs.elki.database.StaticArrayDatabase; import de.lmu.ifi.dbs.elki.database.datastore.DataStore; import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; +import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.datasource.FileBasedDatabaseConnection; import de.lmu.ifi.dbs.elki.datasource.filter.FixedDBIDsFilter; @@ -102,7 +102,7 @@ public class TestKNNJoin implements JUnit4Test { MeanVariance meansize = new MeanVariance(); for(DBID id : relation.iterDBIDs()) { - List<DistanceResultPair<DoubleDistance>> knnlist = knnq.getKNNForDBID(id, 2); + KNNResult<DoubleDistance> knnlist = knnq.getKNNForDBID(id, 2); meansize.put(knnlist.size()); } org.junit.Assert.assertEquals("Euclidean mean 2NN", mean2nnEuclid, meansize.getMean(), 0.00001); @@ -115,7 +115,7 @@ public class TestKNNJoin implements JUnit4Test { MeanVariance meansize = new MeanVariance(); for(DBID id : relation.iterDBIDs()) { - List<DistanceResultPair<DoubleDistance>> knnlist = knnq.getKNNForDBID(id, 2); + KNNResult<DoubleDistance> knnlist = knnq.getKNNForDBID(id, 2); meansize.put(knnlist.size()); } org.junit.Assert.assertEquals("Manhattan mean 2NN", mean2nnManhattan, meansize.getMean(), 0.00001); @@ -213,4 +213,4 @@ public class TestKNNJoin implements JUnit4Test { org.junit.Assert.assertEquals("Manhattan variance 2NN", var2nnManhattan, meansize.getSampleVariance(), 0.00001); } } -} +}
\ No newline at end of file diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestDBSCANResults.java b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestDBSCANResults.java index 025a6f4f..1e95165a 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestDBSCANResults.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestDBSCANResults.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.clustering; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestDeLiCluResults.java b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestDeLiCluResults.java index 9fc898f6..7b62b913 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestDeLiCluResults.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestDeLiCluResults.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.clustering; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -27,10 +27,13 @@ import org.junit.Test; import de.lmu.ifi.dbs.elki.JUnit4Test; import de.lmu.ifi.dbs.elki.algorithm.AbstractSimpleAlgorithmTest; +import de.lmu.ifi.dbs.elki.algorithm.clustering.trivial.ByLabelClustering; import de.lmu.ifi.dbs.elki.data.Clustering; +import de.lmu.ifi.dbs.elki.data.model.Model; import de.lmu.ifi.dbs.elki.database.Database; import de.lmu.ifi.dbs.elki.database.StaticArrayDatabase; import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; +import de.lmu.ifi.dbs.elki.evaluation.clustering.ClusterContingencyTable; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu.DeLiCluTreeFactory; import de.lmu.ifi.dbs.elki.utilities.ClassGenericsUtil; import de.lmu.ifi.dbs.elki.utilities.optionhandling.ParameterException; @@ -70,7 +73,15 @@ public class TestDeLiCluResults extends AbstractSimpleAlgorithmTest implements J // run DeLiClu on database Clustering<?> clustering = opticsxi.run(db); - testFMeasure(db, clustering, 0.8765283); - testClusterSizes(clustering, new int[] { 108, 121, 210, 271 }); + + // Test F-Measure + ByLabelClustering bylabel = new ByLabelClustering(); + Clustering<Model> rbl = bylabel.run(db); + ClusterContingencyTable ct = new ClusterContingencyTable(true, false); + ct.process(clustering, rbl); + double score = ct.getPaircount().f1Measure(); + // We cannot test exactly - due to Hashing, DeLiClu sequence is not + // identical each time, the results will vary slightly. + org.junit.Assert.assertTrue(this.getClass().getSimpleName() + ": Score does not match: " + score, score > 0.85); } }
\ No newline at end of file diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestEMResults.java b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestEMResults.java index 16edcf94..d9f6e7e6 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestEMResults.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestEMResults.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.clustering; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -27,6 +27,7 @@ import org.junit.Test; import de.lmu.ifi.dbs.elki.JUnit4Test; import de.lmu.ifi.dbs.elki.algorithm.AbstractSimpleAlgorithmTest; +import de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.AbstractKMeans; import de.lmu.ifi.dbs.elki.data.Clustering; import de.lmu.ifi.dbs.elki.data.DoubleVector; import de.lmu.ifi.dbs.elki.data.model.EMModel; @@ -56,7 +57,7 @@ public class TestEMResults extends AbstractSimpleAlgorithmTest implements JUnit4 // Setup algorithm ListParameterization params = new ListParameterization(); - params.addParameter(EM.SEED_ID, 1); + params.addParameter(AbstractKMeans.SEED_ID, 1); params.addParameter(EM.K_ID, 5); EM<DoubleVector> em = ClassGenericsUtil.parameterizeOrAbort(EM.class, params); testParameterizationOk(params); diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestOPTICSResults.java b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestOPTICSResults.java index d91c1060..dde81a0f 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestOPTICSResults.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestOPTICSResults.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.clustering; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestSLINKResults.java b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestSLINKResults.java index b1a89360..18a16e0e 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestSLINKResults.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestSLINKResults.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.clustering; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestSNNClusteringResults.java b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestSNNClusteringResults.java index 43ae1a60..ba13af08 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestSNNClusteringResults.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestSNNClusteringResults.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.clustering; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestCASHResults.java b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestCASHResults.java index 33ba56c5..f6d4aba5 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestCASHResults.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestCASHResults.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.clustering.correlation; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -73,11 +73,8 @@ public class TestCASHResults extends AbstractSimpleAlgorithmTest implements JUni // run CASH on database Clustering<Model> result = cash.run(db); - testFMeasureHierarchical(db, result, 0.64102); + testFMeasure(db, result, 0.49055); // with hierarchical pairs: 0.64102 testClusterSizes(result, new int[] { 37, 71, 76, 442 }); - // Old heap scored worse? - // testFMeasureHierarchical(db, result, 0.638727); - // testClusterSizes(result, new int[] { 13, 65, 74, 75, 442 }); } /** diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestCOPACResults.java b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestCOPACResults.java index 2fbe8401..8af036bf 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestCOPACResults.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestCOPACResults.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.clustering.correlation; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestERiCResults.java b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestERiCResults.java index ec030ec1..92a61e5e 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestERiCResults.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestERiCResults.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.clustering.correlation; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -87,7 +87,7 @@ public class TestERiCResults extends AbstractSimpleAlgorithmTest implements JUni // run ERiC on database Clustering<CorrelationModel<DoubleVector>> result = eric.run(db); - testFMeasureHierarchical(db, result, 0.9204825); + testFMeasure(db, result, 0.714207); // Hierarchical pairs scored: 0.9204825 testClusterSizes(result, new int[] { 109, 184, 307 }); } diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestFourCResults.java b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestFourCResults.java index bfbddd64..8604a5f0 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestFourCResults.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestFourCResults.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.clustering.correlation; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -67,7 +67,7 @@ public class TestFourCResults extends AbstractSimpleAlgorithmTest implements JUn // run 4C on database Clustering<Model> result = fourc.run(db); - testFMeasureHierarchical(db, result, 0.79467); + testFMeasure(db, result, 0.498048); // Hierarchical pairs scored: 0.79467 testClusterSizes(result, new int[] { 5, 595 }); } diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestORCLUSResults.java b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestORCLUSResults.java index 48b84d04..2660c586 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestORCLUSResults.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/correlation/TestORCLUSResults.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.clustering.correlation; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -68,7 +68,7 @@ public class TestORCLUSResults extends AbstractSimpleAlgorithmTest implements JU // run ORCLUS on database Clustering<Model> result = orclus.run(db); - testFMeasureHierarchical(db, result, 0.789113); + testFMeasure(db, result, 0.640306); // Hierarchical pairs scored: 0.789113 testClusterSizes(result, new int[] { 22, 27, 401 }); } diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestKMeansResults.java b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/kmeans/TestKMeansResults.java index d4557e8f..c35a7194 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/TestKMeansResults.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/kmeans/TestKMeansResults.java @@ -1,10 +1,10 @@ -package de.lmu.ifi.dbs.elki.algorithm.clustering; +package de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans; /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -27,6 +27,7 @@ import org.junit.Test; import de.lmu.ifi.dbs.elki.JUnit4Test; import de.lmu.ifi.dbs.elki.algorithm.AbstractSimpleAlgorithmTest; +import de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMeansLloyd; import de.lmu.ifi.dbs.elki.data.Clustering; import de.lmu.ifi.dbs.elki.data.DoubleVector; import de.lmu.ifi.dbs.elki.data.model.MeanModel; @@ -53,14 +54,37 @@ public class TestKMeansResults extends AbstractSimpleAlgorithmTest implements JU * @throws ParameterException */ @Test - public void testKMeansResults() { + public void testKMeansLloyd() { Database db = makeSimpleDatabase(UNITTEST + "different-densities-2d-no-noise.ascii", 1000); // Setup algorithm ListParameterization params = new ListParameterization(); - params.addParameter(KMeans.K_ID, 5); - params.addParameter(KMeans.SEED_ID, 3); - KMeans<DoubleVector, DoubleDistance> kmeans = ClassGenericsUtil.parameterizeOrAbort(KMeans.class, params); + params.addParameter(AbstractKMeans.K_ID, 5); + params.addParameter(AbstractKMeans.SEED_ID, 3); + AbstractKMeans<DoubleVector, DoubleDistance> kmeans = ClassGenericsUtil.parameterizeOrAbort(KMeansLloyd.class, params); + testParameterizationOk(params); + + // run KMeans on database + Clustering<MeanModel<DoubleVector>> result = kmeans.run(db); + testFMeasure(db, result, 0.998005); + testClusterSizes(result, new int[] { 199, 200, 200, 200, 201 }); + } + + /** + * Run KMeans with fixed parameters and compare the result to a golden + * standard. + * + * @throws ParameterException + */ + @Test + public void testKMeansMacQueen() { + Database db = makeSimpleDatabase(UNITTEST + "different-densities-2d-no-noise.ascii", 1000); + + // Setup algorithm + ListParameterization params = new ListParameterization(); + params.addParameter(AbstractKMeans.K_ID, 5); + params.addParameter(AbstractKMeans.SEED_ID, 3); + AbstractKMeans<DoubleVector, DoubleDistance> kmeans = ClassGenericsUtil.parameterizeOrAbort(KMeansMacQueen.class, params); testParameterizationOk(params); // run KMeans on database diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestCLIQUEResults.java b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestCLIQUEResults.java index d2cacf1b..726efd76 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestCLIQUEResults.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestCLIQUEResults.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.clustering.subspace; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -27,13 +27,10 @@ import org.junit.Test; import de.lmu.ifi.dbs.elki.JUnit4Test; import de.lmu.ifi.dbs.elki.algorithm.AbstractSimpleAlgorithmTest; -import de.lmu.ifi.dbs.elki.algorithm.clustering.trivial.ByLabelClustering; import de.lmu.ifi.dbs.elki.data.Clustering; import de.lmu.ifi.dbs.elki.data.DoubleVector; -import de.lmu.ifi.dbs.elki.data.model.Model; import de.lmu.ifi.dbs.elki.data.model.SubspaceModel; import de.lmu.ifi.dbs.elki.database.Database; -import de.lmu.ifi.dbs.elki.evaluation.paircounting.PairCountingFMeasure; import de.lmu.ifi.dbs.elki.utilities.ClassGenericsUtil; import de.lmu.ifi.dbs.elki.utilities.optionhandling.ParameterException; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.ListParameterization; @@ -69,12 +66,9 @@ public class TestCLIQUEResults extends AbstractSimpleAlgorithmTest implements JU // run CLIQUE on database Clustering<SubspaceModel<DoubleVector>> result = clique.run(db); - // Run by-label as reference - ByLabelClustering bylabel = new ByLabelClustering(true, null); - Clustering<Model> rbl = bylabel.run(db); - double score = PairCountingFMeasure.compareClusterings(result, rbl, 1.0); - org.junit.Assert.assertEquals(this.getClass().getSimpleName() + ": Score does not match.", 0.9882, score, 0.0001); + // PairCounting is not appropriate here: overlapping clusterings! + // testFMeasure(db, result, 0.9882); testClusterSizes(result, new int[] { 200, 200, 216, 400 }); } @@ -97,7 +91,8 @@ public class TestCLIQUEResults extends AbstractSimpleAlgorithmTest implements JU // run CLIQUE on database Clustering<SubspaceModel<DoubleVector>> result = clique.run(db); - testFMeasure(db, result, 0.433661); + // PairCounting is not appropriate here: overlapping clusterings! + // testFMeasure(db, result, 0.433661); testClusterSizes(result, new int[] { 255, 409, 458, 458, 480 }); } }
\ No newline at end of file diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestDiSHResults.java b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestDiSHResults.java index ca8f55b4..c7be9747 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestDiSHResults.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestDiSHResults.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.clustering.subspace; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -66,7 +66,7 @@ public class TestDiSHResults extends AbstractSimpleAlgorithmTest implements JUni // run DiSH on database Clustering<SubspaceModel<DoubleVector>> result = dish.run(db); - testFMeasureHierarchical(db, result, 0.9991258); + testFMeasure(db, result, 0.996976); // Hierarchical pairs scored: 0.9991258 testClusterSizes(result, new int[] { 51, 199, 200 }); } diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestPROCLUSResults.java b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestPROCLUSResults.java index 48dbe9c3..c5f37c88 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestPROCLUSResults.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestPROCLUSResults.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.clustering.subspace; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestPreDeConResults.java b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestPreDeConResults.java index 9e04d6d3..4d2bf7d0 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestPreDeConResults.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestPreDeConResults.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.clustering.subspace; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestSUBCLUResults.java b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestSUBCLUResults.java index 9f0e1550..817687c5 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestSUBCLUResults.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/clustering/subspace/TestSUBCLUResults.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.clustering.subspace; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -67,7 +67,8 @@ public class TestSUBCLUResults extends AbstractSimpleAlgorithmTest implements JU // run SUBCLU on database Clustering<SubspaceModel<DoubleVector>> result = subclu.run(db); - testFMeasure(db, result, 0.9090); + // PairCounting is not appropriate here: overlapping clusterings! + // testFMeasure(db, result, 0.9090); testClusterSizes(result, new int[] { 191, 194, 395 }); } @@ -90,7 +91,8 @@ public class TestSUBCLUResults extends AbstractSimpleAlgorithmTest implements JU // run SUBCLU on database Clustering<SubspaceModel<DoubleVector>> result = subclu.run(db); - testFMeasure(db, result, 0.49279033); + // PairCounting is not appropriate here: overlapping clusterings! + // testFMeasure(db, result, 0.49279033); testClusterSizes(result, new int[] { 99, 247, 303, 323, 437, 459 }); } }
\ No newline at end of file diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestABOD.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestABOD.java index 022c448c..3490ce9a 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestABOD.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestABOD.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestAggarwalYuEvolutionary.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestAggarwalYuEvolutionary.java index c2f8c016..1eb0c713 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestAggarwalYuEvolutionary.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestAggarwalYuEvolutionary.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestAggarwalYuNaive.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestAggarwalYuNaive.java index 92c74f3c..937977f2 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestAggarwalYuNaive.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestAggarwalYuNaive.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestDBOutlierDetection.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestDBOutlierDetection.java index 79c596ff..0d6fc7f6 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestDBOutlierDetection.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestDBOutlierDetection.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestDBOutlierScore.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestDBOutlierScore.java index 875eceb3..b34c071e 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestDBOutlierScore.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestDBOutlierScore.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestGaussianModel.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestGaussianModel.java index 52c20bbe..e18c2f46 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestGaussianModel.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestGaussianModel.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestGaussianUniformMixture.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestGaussianUniformMixture.java index e0c54380..c02da8a5 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestGaussianUniformMixture.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestGaussianUniformMixture.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestINFLO.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestINFLO.java index 2323e512..39dd9bc0 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestINFLO.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestINFLO.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestKNNOutlier.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestKNNOutlier.java index a6708171..7d0457df 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestKNNOutlier.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestKNNOutlier.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestKNNWeightOutlier.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestKNNWeightOutlier.java index be5e2704..bbb1bdfb 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestKNNWeightOutlier.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestKNNWeightOutlier.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestLDOF.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestLDOF.java index 210a9e71..70a5b170 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestLDOF.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestLDOF.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -55,7 +55,7 @@ public class TestLDOF extends AbstractSimpleAlgorithmTest implements JUnit4Test // run LDOF on database OutlierResult result = ldof.run(db); - testSingleScore(result, 1025, 0.8976268846182947); testAUC(db, "Noise", result, 0.9637948717948718); + testSingleScore(result, 1025, 0.8976268846182947); } }
\ No newline at end of file diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestLOCI.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestLOCI.java index 3d2cd32e..d95b362c 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestLOCI.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestLOCI.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -55,7 +55,7 @@ public class TestLOCI extends AbstractSimpleAlgorithmTest implements JUnit4Test // run LOCI on database OutlierResult result = loci.run(db); - testAUC(db, "Noise", result, 0.954444); - testSingleScore(result, 146, 4.14314916); + testAUC(db, "Noise", result, 0.96222222); + testSingleScore(result, 146, 3.8054382); } }
\ No newline at end of file diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestLOF.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestLOF.java index e4d71111..a1ef967b 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestLOF.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestLOF.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestLoOP.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestLoOP.java index 18d759c5..653f4a29 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestLoOP.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestLoOP.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -55,7 +55,7 @@ public class TestLoOP extends AbstractSimpleAlgorithmTest implements JUnit4Test // run LoOP on database OutlierResult result = loop.run(db); - testSingleScore(result, 945, 0.39805457858293325); testAUC(db, "Noise", result, 0.9443796296296296); + testSingleScore(result, 945, 0.39805457858293325); } }
\ No newline at end of file diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestOPTICSOF.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestOPTICSOF.java index be6779ff..ed9e1533 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestOPTICSOF.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestOPTICSOF.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestOnlineLOF.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestOnlineLOF.java index 4c875917..10cff737 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestOnlineLOF.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestOnlineLOF.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestReferenceBasedOutlierDetection.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestReferenceBasedOutlierDetection.java index 901f5a3e..5b6d3bde 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestReferenceBasedOutlierDetection.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestReferenceBasedOutlierDetection.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestSOD.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestSOD.java index cab95aff..de637957 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestSOD.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/TestSOD.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -29,6 +29,7 @@ import de.lmu.ifi.dbs.elki.JUnit4Test; import de.lmu.ifi.dbs.elki.algorithm.AbstractSimpleAlgorithmTest; import de.lmu.ifi.dbs.elki.data.DoubleVector; import de.lmu.ifi.dbs.elki.database.Database; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.index.preprocessed.snn.SharedNearestNeighborPreprocessor; import de.lmu.ifi.dbs.elki.result.outlier.OutlierResult; import de.lmu.ifi.dbs.elki.utilities.ClassGenericsUtil; @@ -50,7 +51,7 @@ public class TestSOD extends AbstractSimpleAlgorithmTest implements JUnit4Test { params.addParameter(SharedNearestNeighborPreprocessor.Factory.NUMBER_OF_NEIGHBORS_ID, 19); // setup Algorithm - SOD<DoubleVector> sod = ClassGenericsUtil.parameterizeOrAbort(SOD.class, params); + SOD<DoubleVector, DoubleDistance> sod = ClassGenericsUtil.parameterizeOrAbort(SOD.class, params); testParameterizationOk(params); // run SOD on database diff --git a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/meta/TestFeatureBagging.java b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/meta/TestFeatureBagging.java index 0c568578..18e5c6ac 100644 --- a/test/de/lmu/ifi/dbs/elki/algorithm/outlier/meta/TestFeatureBagging.java +++ b/test/de/lmu/ifi/dbs/elki/algorithm/outlier/meta/TestFeatureBagging.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier.meta; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -79,6 +79,6 @@ public class TestFeatureBagging extends AbstractSimpleAlgorithmTest implements J OutlierResult result = fb.run(db); testSingleScore(result, 1293, 1.321709879); - testAUC(db, "Noise", result, 0.88466106); + testAUC(db, "Noise", result, 0.884212); } }
\ No newline at end of file diff --git a/test/de/lmu/ifi/dbs/elki/data/spatial/TestPolygon.java b/test/de/lmu/ifi/dbs/elki/data/spatial/TestPolygon.java index 1294c91a..60d7f678 100644 --- a/test/de/lmu/ifi/dbs/elki/data/spatial/TestPolygon.java +++ b/test/de/lmu/ifi/dbs/elki/data/spatial/TestPolygon.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.data.spatial; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/distance/distancefunction/SpatialPrimitiveDistanceFunctionTest.java b/test/de/lmu/ifi/dbs/elki/distance/distancefunction/SpatialPrimitiveDistanceFunctionTest.java new file mode 100644 index 00000000..1c459717 --- /dev/null +++ b/test/de/lmu/ifi/dbs/elki/distance/distancefunction/SpatialPrimitiveDistanceFunctionTest.java @@ -0,0 +1,148 @@ +package de.lmu.ifi.dbs.elki.distance.distancefunction; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; + +import java.util.ArrayList; +import java.util.List; +import java.util.Random; + +import org.junit.Test; + +import de.lmu.ifi.dbs.elki.JUnit4Test; +import de.lmu.ifi.dbs.elki.data.ModifiableHyperBoundingBox; +import de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.distance.distancefunction.colorhistogram.HistogramIntersectionDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.math.linearalgebra.Vector; + +/** + * Validate spatial distance functions by ensuring that mindist <= distance for + * random objects. + * + * @author Erich Schubert + * + */ +public class SpatialPrimitiveDistanceFunctionTest implements JUnit4Test { + @Test + public void testSpatialDistanceConsistency() { + final Random rnd = new Random(0); + final int dim = 7; + final int iters = 10000; + + List<SpatialPrimitiveDistanceFunction<? super NumberVector<?, ?>, ?>> dists = new ArrayList<SpatialPrimitiveDistanceFunction<? super NumberVector<?, ?>, ?>>(); + dists.add(EuclideanDistanceFunction.STATIC); + dists.add(ManhattanDistanceFunction.STATIC); + dists.add(MaximumDistanceFunction.STATIC); + dists.add(MinimumDistanceFunction.STATIC); + dists.add(new LPNormDistanceFunction(3)); + dists.add(new LPNormDistanceFunction(.5)); + dists.add(CanberraDistanceFunction.STATIC); + // Histogram intersection distance isn't proper for negative values + // dists.add(HistogramIntersectionDistanceFunction.STATIC); + dists.add(SquaredEuclideanDistanceFunction.STATIC); + dists.add(ArcCosineDistanceFunction.STATIC); + dists.add(CosineDistanceFunction.STATIC); + + double[] d1 = new double[dim]; + double[] d2 = new double[dim]; + double[] d3 = new double[dim]; + double[] d4 = new double[dim]; + Vector v1 = new Vector(d1); + ModifiableHyperBoundingBox mbr = new ModifiableHyperBoundingBox(d2, d3); + Vector v2 = new Vector(d4); + for(int i = 0; i < iters; i++) { + for(int d = 0; d < dim; d++) { + d1[d] = (rnd.nextDouble() - .5) * 2E4; + d2[d] = (rnd.nextDouble() - .5) * 2E4; + d3[d] = (rnd.nextDouble() - .5) * 2E4; + if(d2[d] > d3[d]) { + double t = d2[d]; + d2[d] = d3[d]; + d3[d] = t; + } + double m = rnd.nextDouble(); + d4[d] = m * d2[d] + (1 - m) * d3[d]; + } + for(SpatialPrimitiveDistanceFunction<? super NumberVector<?, ?>, ?> dis : dists) { + compareDistances(v1, mbr, v2, dis); + } + } + } + + @Test + public void testSpatialDistanceConsistencyPositive() { + final Random rnd = new Random(1); + final int dim = 7; + final int iters = 10000; + + List<SpatialPrimitiveDistanceFunction<? super NumberVector<?, ?>, ?>> dists = new ArrayList<SpatialPrimitiveDistanceFunction<? super NumberVector<?, ?>, ?>>(); + dists.add(EuclideanDistanceFunction.STATIC); + dists.add(ManhattanDistanceFunction.STATIC); + dists.add(MaximumDistanceFunction.STATIC); + dists.add(MinimumDistanceFunction.STATIC); + dists.add(new LPNormDistanceFunction(3)); + dists.add(new LPNormDistanceFunction(.5)); + dists.add(CanberraDistanceFunction.STATIC); + dists.add(HistogramIntersectionDistanceFunction.STATIC); + dists.add(SquaredEuclideanDistanceFunction.STATIC); + dists.add(ArcCosineDistanceFunction.STATIC); + dists.add(CosineDistanceFunction.STATIC); + + double[] d1 = new double[dim]; + double[] d2 = new double[dim]; + double[] d3 = new double[dim]; + double[] d4 = new double[dim]; + Vector v1 = new Vector(d1); + ModifiableHyperBoundingBox mbr = new ModifiableHyperBoundingBox(d2, d3); + Vector v2 = new Vector(d4); + for(int i = 0; i < iters; i++) { + for(int d = 0; d < dim; d++) { + d1[d] = rnd.nextDouble() * 2E4; + d2[d] = rnd.nextDouble() * 2E4; + d3[d] = rnd.nextDouble() * 2E4; + if(d2[d] > d3[d]) { + double t = d2[d]; + d2[d] = d3[d]; + d3[d] = t; + } + double m = rnd.nextDouble(); + d4[d] = m * d2[d] + (1 - m) * d3[d]; + } + for(SpatialPrimitiveDistanceFunction<? super NumberVector<?, ?>, ?> dis : dists) { + compareDistances(v1, mbr, v2, dis); + } + } + } + + protected <D extends Distance<D>> void compareDistances(Vector v1, ModifiableHyperBoundingBox mbr, Vector v2, SpatialPrimitiveDistanceFunction<? super NumberVector<?, ?>, D> dist) { + D exact = dist.distance(v1, v2); + D mind = dist.minDist(v1, v2); + D mbrd = dist.minDist(v1, mbr); + assertEquals("Not same: " + dist.toString(), exact, mind); + assertTrue("Not smaller:" + dist.toString() + " " + mbrd + " > " + exact + " " + mbr + " " + v1, mbrd.compareTo(exact) <= 0); + } +}
\ No newline at end of file diff --git a/test/de/lmu/ifi/dbs/elki/evaluation/TestPairCountingFMeasure.java b/test/de/lmu/ifi/dbs/elki/evaluation/paircounting/TestClusterContingencyTable.java index 123e2e4f..42188f56 100644 --- a/test/de/lmu/ifi/dbs/elki/evaluation/TestPairCountingFMeasure.java +++ b/test/de/lmu/ifi/dbs/elki/evaluation/paircounting/TestClusterContingencyTable.java @@ -1,10 +1,10 @@ -package de.lmu.ifi.dbs.elki.evaluation; +package de.lmu.ifi.dbs.elki.evaluation.paircounting; /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -39,18 +39,18 @@ import de.lmu.ifi.dbs.elki.database.Database; import de.lmu.ifi.dbs.elki.database.StaticArrayDatabase; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.datasource.FileBasedDatabaseConnection; -import de.lmu.ifi.dbs.elki.evaluation.paircounting.PairCountingFMeasure; +import de.lmu.ifi.dbs.elki.evaluation.clustering.ClusterContingencyTable; import de.lmu.ifi.dbs.elki.utilities.ClassGenericsUtil; import de.lmu.ifi.dbs.elki.utilities.optionhandling.ParameterException; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.ListParameterization; /** - * Validate {@link PairCountingFMeasure} with respect to its ability to compare + * Validate {@link ClusterContingencyTable} with respect to its ability to compare * data clusterings. * * @author Erich Schubert */ -public class TestPairCountingFMeasure implements JUnit4Test { +public class TestClusterContingencyTable implements JUnit4Test { // the following values depend on the data set used! String dataset = "data/testdata/unittests/hierarchical-3d2d1d.csv"; @@ -58,7 +58,7 @@ public class TestPairCountingFMeasure implements JUnit4Test { int shoulds = 600; /** - * Validate {@link PairCountingFMeasure} with respect to its ability to + * Validate {@link ClusterContingencyTable} with respect to its ability to * compare data clusterings. * * @throws ParameterException on errors. @@ -89,13 +89,19 @@ public class TestPairCountingFMeasure implements JUnit4Test { ByLabelClustering bylabel = new ByLabelClustering(); Clustering<?> rbl = bylabel.run(db); - assertEquals(1.0, PairCountingFMeasure.compareClusterings(rai, rai), Double.MIN_VALUE); - assertEquals(1.0, PairCountingFMeasure.compareClusterings(ran, ran), Double.MIN_VALUE); - assertEquals(1.0, PairCountingFMeasure.compareClusterings(rbl, rbl), Double.MIN_VALUE); + assertEquals(1.0, computeFMeasure(rai, rai, false), Double.MIN_VALUE); + assertEquals(1.0, computeFMeasure(ran, ran, false), Double.MIN_VALUE); + assertEquals(1.0, computeFMeasure(rbl, rbl, false), Double.MIN_VALUE); - assertEquals(0.009950248756218905, PairCountingFMeasure.compareClusterings(ran, rbl, true, false), Double.MIN_VALUE); - assertEquals(0.0033277870216306157, PairCountingFMeasure.compareClusterings(rai, ran, true, false), Double.MIN_VALUE); + assertEquals(0.009950248756218905, computeFMeasure(ran, rbl, true), Double.MIN_VALUE); + assertEquals(0.0033277870216306157, computeFMeasure(rai, ran, true), Double.MIN_VALUE); - assertEquals(0.5 /* 0.3834296724470135 */, PairCountingFMeasure.compareClusterings(rai, rbl), Double.MIN_VALUE); + assertEquals(0.5 /* 0.3834296724470135 */, computeFMeasure(rai, rbl, false), Double.MIN_VALUE); + } + + private double computeFMeasure(Clustering<?> c1, Clustering<?> c2, boolean noise) { + ClusterContingencyTable ct = new ClusterContingencyTable(true, noise); + ct.process(c1, c2); + return ct.getPaircount().f1Measure(); } }
\ No newline at end of file diff --git a/test/de/lmu/ifi/dbs/elki/evaluation/TestComputeROC.java b/test/de/lmu/ifi/dbs/elki/evaluation/roc/TestComputeROC.java index 2ad7c11f..206fbcfd 100644 --- a/test/de/lmu/ifi/dbs/elki/evaluation/TestComputeROC.java +++ b/test/de/lmu/ifi/dbs/elki/evaluation/roc/TestComputeROC.java @@ -1,10 +1,10 @@ -package de.lmu.ifi.dbs.elki.evaluation; +package de.lmu.ifi.dbs.elki.evaluation.roc; /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -42,7 +42,6 @@ import de.lmu.ifi.dbs.elki.utilities.pairs.Pair; * Test to validate ROC curve computation. * * @author Erich Schubert - * */ public class TestComputeROC implements JUnit4Test { /** diff --git a/test/de/lmu/ifi/dbs/elki/index/TestIndexStructures.java b/test/de/lmu/ifi/dbs/elki/index/TestIndexStructures.java index 53801e09..4ce9dc6e 100644 --- a/test/de/lmu/ifi/dbs/elki/index/TestIndexStructures.java +++ b/test/de/lmu/ifi/dbs/elki/index/TestIndexStructures.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -39,6 +39,7 @@ import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; +import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult; import de.lmu.ifi.dbs.elki.database.query.knn.LinearScanKNNQuery; import de.lmu.ifi.dbs.elki.database.query.range.LinearScanRangeQuery; import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery; @@ -56,7 +57,7 @@ import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query.DoubleDistance import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query.DoubleDistanceRStarTreeRangeQuery; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar.RStarTree; import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar.RStarTreeFactory; -import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.util.ApproximateLeastOverlapInsertionStrategy; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert.ApproximativeLeastOverlapInsertionStrategy; import de.lmu.ifi.dbs.elki.utilities.ClassGenericsUtil; import de.lmu.ifi.dbs.elki.utilities.optionhandling.ParameterException; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.ListParameterization; @@ -140,8 +141,8 @@ public class TestIndexStructures implements JUnit4Test { public void testRStarTreeFast() { ListParameterization spatparams = new ListParameterization(); spatparams.addParameter(StaticArrayDatabase.INDEX_ID, RStarTreeFactory.class); - spatparams.addParameter(AbstractRStarTreeFactory.INSERTION_STRATEGY_ID, ApproximateLeastOverlapInsertionStrategy.class); - spatparams.addParameter(ApproximateLeastOverlapInsertionStrategy.Parameterizer.INSERTION_CANDIDATES_ID, 1); + spatparams.addParameter(AbstractRStarTreeFactory.INSERTION_STRATEGY_ID, ApproximativeLeastOverlapInsertionStrategy.class); + spatparams.addParameter(ApproximativeLeastOverlapInsertionStrategy.Parameterizer.INSERTION_CANDIDATES_ID, 1); spatparams.addParameter(TreeIndexFactory.PAGE_SIZE_ID, 300); testFileBasedDatabaseConnection(spatparams, DoubleDistanceRStarTreeKNNQuery.class, DoubleDistanceRStarTreeRangeQuery.class); } @@ -185,7 +186,7 @@ public class TestIndexStructures implements JUnit4Test { DoubleVector dv = new DoubleVector(querypoint); KNNQuery<DoubleVector, DoubleDistance> knnq = db.getKNNQuery(dist, k); assertTrue("Returned knn query is not of expected class.", expectKNNQuery.isAssignableFrom(knnq.getClass())); - List<DistanceResultPair<DoubleDistance>> ids = knnq.getKNNForObject(dv, k); + KNNResult<DoubleDistance> ids = knnq.getKNNForObject(dv, k); assertEquals("Result size does not match expectation!", shouldd.length, ids.size()); // verify that the neighbors match. diff --git a/test/de/lmu/ifi/dbs/elki/index/preprocessed/TestMaterializedKNNAndRKNNPreprocessor.java b/test/de/lmu/ifi/dbs/elki/index/preprocessed/TestMaterializedKNNAndRKNNPreprocessor.java index e3948fef..f2372d7a 100644 --- a/test/de/lmu/ifi/dbs/elki/index/preprocessed/TestMaterializedKNNAndRKNNPreprocessor.java +++ b/test/de/lmu/ifi/dbs/elki/index/preprocessed/TestMaterializedKNNAndRKNNPreprocessor.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.index.preprocessed; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -44,6 +44,7 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; +import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult; import de.lmu.ifi.dbs.elki.database.query.knn.LinearScanKNNQuery; import de.lmu.ifi.dbs.elki.database.query.rknn.LinearScanRKNNQuery; import de.lmu.ifi.dbs.elki.database.query.rknn.RKNNQuery; @@ -155,11 +156,11 @@ public class TestMaterializedKNNAndRKNNPreprocessor implements JUnit4Test { private void testKNNQueries(Relation<DoubleVector> rep, KNNQuery<DoubleVector, DoubleDistance> lin_knn_query, KNNQuery<DoubleVector, DoubleDistance> preproc_knn_query, int k) { ArrayDBIDs sample = DBIDUtil.ensureArray(rep.getDBIDs()); - List<List<DistanceResultPair<DoubleDistance>>> lin_knn_ids = lin_knn_query.getKNNForBulkDBIDs(sample, k); - List<List<DistanceResultPair<DoubleDistance>>> preproc_knn_ids = preproc_knn_query.getKNNForBulkDBIDs(sample, k); + List<KNNResult<DoubleDistance>> lin_knn_ids = lin_knn_query.getKNNForBulkDBIDs(sample, k); + List<KNNResult<DoubleDistance>> preproc_knn_ids = preproc_knn_query.getKNNForBulkDBIDs(sample, k); for(int i = 0; i < rep.size(); i++) { - List<DistanceResultPair<DoubleDistance>> lin_knn = lin_knn_ids.get(i); - List<DistanceResultPair<DoubleDistance>> pre_knn = preproc_knn_ids.get(i); + KNNResult<DoubleDistance> lin_knn = lin_knn_ids.get(i); + KNNResult<DoubleDistance> pre_knn = preproc_knn_ids.get(i); if(!lin_knn.equals(pre_knn)) { System.out.println("LIN kNN " + lin_knn); System.out.println("PRE kNN " + pre_knn); diff --git a/test/de/lmu/ifi/dbs/elki/logging/TestOutputStreamLogger.java b/test/de/lmu/ifi/dbs/elki/logging/TestOutputStreamLogger.java index 7d0a9317..1ae0e71d 100644 --- a/test/de/lmu/ifi/dbs/elki/logging/TestOutputStreamLogger.java +++ b/test/de/lmu/ifi/dbs/elki/logging/TestOutputStreamLogger.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.logging; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/math/TestAffineTransformation.java b/test/de/lmu/ifi/dbs/elki/math/TestAffineTransformation.java index 0ac6b1a6..926c111c 100644 --- a/test/de/lmu/ifi/dbs/elki/math/TestAffineTransformation.java +++ b/test/de/lmu/ifi/dbs/elki/math/TestAffineTransformation.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.math; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/math/TestKernelDensityFitting.java b/test/de/lmu/ifi/dbs/elki/math/TestKernelDensityFitting.java index 7533a235..c7ebfec2 100644 --- a/test/de/lmu/ifi/dbs/elki/math/TestKernelDensityFitting.java +++ b/test/de/lmu/ifi/dbs/elki/math/TestKernelDensityFitting.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.math; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -42,6 +42,7 @@ import de.lmu.ifi.dbs.elki.math.linearalgebra.fitting.GaussianFittingFunction; import de.lmu.ifi.dbs.elki.math.linearalgebra.fitting.LevenbergMarquardtMethod; import de.lmu.ifi.dbs.elki.math.statistics.GaussianKernelDensityFunction; import de.lmu.ifi.dbs.elki.math.statistics.KernelDensityEstimator; +import de.lmu.ifi.dbs.elki.math.statistics.distribution.NormalDistribution; import de.lmu.ifi.dbs.elki.utilities.ClassGenericsUtil; import de.lmu.ifi.dbs.elki.utilities.optionhandling.ParameterException; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.ListParameterization; @@ -138,8 +139,8 @@ public class TestKernelDensityFitting implements JUnit4Test { params[0] = mv.getMean(); params[1] = mv.getSampleStddev(); // guess initial amplitude for an gaussian distribution. - double c1 = MathUtil.erf(Math.abs(data[0] - params[0]) / (params[1] * Math.sqrt(2))); - double c2 = MathUtil.erf(Math.abs(data[data.length - 1] - params[0]) / (params[1] * Math.sqrt(2))); + double c1 = NormalDistribution.erf(Math.abs(data[0] - params[0]) / (params[1] * Math.sqrt(2))); + double c2 = NormalDistribution.erf(Math.abs(data[data.length - 1] - params[0]) / (params[1] * Math.sqrt(2))); params[2] = 1.0 / Math.min(c1, c2); // System.out.println("Mean: " + params[0] + " Stddev: " + params[1] + // " Amp: " + params[2]); diff --git a/test/de/lmu/ifi/dbs/elki/math/TestLevenbergMarquardtGaussianFitting.java b/test/de/lmu/ifi/dbs/elki/math/TestLevenbergMarquardtGaussianFitting.java index 46676c9b..54376c52 100644 --- a/test/de/lmu/ifi/dbs/elki/math/TestLevenbergMarquardtGaussianFitting.java +++ b/test/de/lmu/ifi/dbs/elki/math/TestLevenbergMarquardtGaussianFitting.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.math; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/math/TestMathUtil.java b/test/de/lmu/ifi/dbs/elki/math/TestMathUtil.java index 16dfe77c..d8211741 100644 --- a/test/de/lmu/ifi/dbs/elki/math/TestMathUtil.java +++ b/test/de/lmu/ifi/dbs/elki/math/TestMathUtil.java @@ -1,17 +1,19 @@ package de.lmu.ifi.dbs.elki.math; -import static org.junit.Assert.*; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; import java.util.Random; import org.junit.Test; import de.lmu.ifi.dbs.elki.JUnit4Test; + /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -42,17 +44,57 @@ public class TestMathUtil implements JUnit4Test { double[] weight2 = new double[size]; Random r = new Random(seed); - for (int i = 0; i < size; i++) { + for(int i = 0; i < size; i++) { data1[i] = r.nextDouble(); data2[i] = r.nextDouble(); weight1[i] = 1.0; weight2[i] = 0.1; } - + double pear = MathUtil.pearsonCorrelationCoefficient(data1, data2); double wpear1 = MathUtil.weightedPearsonCorrelationCoefficient(data1, data2, weight1); double wpear2 = MathUtil.weightedPearsonCorrelationCoefficient(data1, data2, weight2); assertEquals("Pearson and weighted pearson should be the same with constant weights.", pear, wpear1, 1E-10); assertEquals("Weighted pearsons should be the same with constant weights.", wpear1, wpear2, 1E-10); } -} + + @Test + public void testBitMath() { + assertEquals("Bit math issues", 1024, MathUtil.nextPow2Int(912)); + assertEquals("Bit math issues", 8, MathUtil.nextPow2Int(5)); + assertEquals("Bit math issues", 4, MathUtil.nextPow2Int(4)); + assertEquals("Bit math issues", 4, MathUtil.nextPow2Int(3)); + assertEquals("Bit math issues", 2, MathUtil.nextPow2Int(2)); + assertEquals("Bit math issues", 1, MathUtil.nextPow2Int(1)); + assertEquals("Bit math issues", 0, MathUtil.nextPow2Int(0)); + assertEquals("Bit math issues", 1024L, MathUtil.nextPow2Long(912L)); + assertEquals("Bit math issues", 0, MathUtil.nextPow2Int(-1)); + assertEquals("Bit math issues", 0, MathUtil.nextPow2Int(-2)); + assertEquals("Bit math issues", 0, MathUtil.nextPow2Int(-99)); + assertEquals("Bit math issues", 15, MathUtil.nextAllOnesInt(8)); + assertEquals("Bit math issues", 7, MathUtil.nextAllOnesInt(4)); + assertEquals("Bit math issues", 3, MathUtil.nextAllOnesInt(3)); + assertEquals("Bit math issues", 3, MathUtil.nextAllOnesInt(2)); + assertEquals("Bit math issues", 1, MathUtil.nextAllOnesInt(1)); + assertEquals("Bit math issues", 0, MathUtil.nextAllOnesInt(0)); + assertEquals("Bit math issues", -1, MathUtil.nextAllOnesInt(-1)); + assertEquals("Bit math issues", 0, 0 >>> 1); + } + + @Test + public void testFloatToDouble() { + Random r = new Random(1l); + for(int i = 0; i < 10000; i++) { + final double dbl = Double.longBitsToDouble(r.nextLong()); + final float flt = (float) dbl; + final double uppd = MathUtil.floatToDoubleUpper(flt); + final float uppf = (float) uppd; + final double lowd = MathUtil.floatToDoubleLower(flt); + final float lowf = (float) lowd; + assertTrue("Expected value to become larger, but " + uppd + " < " + dbl, uppd >= dbl || Double.isNaN(dbl)); + assertTrue("Expected value to round to the same float.", flt == uppf || Double.isNaN(flt)); + assertTrue("Expected value to become smaller, but " + lowd + " > " + dbl, lowd <= dbl || Double.isNaN(dbl)); + assertTrue("Expected value to round to the same float.", flt == lowf || Double.isNaN(flt)); + } + } +}
\ No newline at end of file diff --git a/test/de/lmu/ifi/dbs/elki/math/TestMatrix.java b/test/de/lmu/ifi/dbs/elki/math/TestMatrix.java index 0d22d19a..55c266d8 100644 --- a/test/de/lmu/ifi/dbs/elki/math/TestMatrix.java +++ b/test/de/lmu/ifi/dbs/elki/math/TestMatrix.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.math; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/math/TestWeightFunctions.java b/test/de/lmu/ifi/dbs/elki/math/TestWeightFunctions.java index f07be82a..c24bab2e 100644 --- a/test/de/lmu/ifi/dbs/elki/math/TestWeightFunctions.java +++ b/test/de/lmu/ifi/dbs/elki/math/TestWeightFunctions.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.math; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/math/TestFlexiHistogram.java b/test/de/lmu/ifi/dbs/elki/math/histograms/TestFlexiHistogram.java index b3db5b85..bcc7f330 100644 --- a/test/de/lmu/ifi/dbs/elki/math/TestFlexiHistogram.java +++ b/test/de/lmu/ifi/dbs/elki/math/histograms/TestFlexiHistogram.java @@ -1,10 +1,10 @@ -package de.lmu.ifi.dbs.elki.math; +package de.lmu.ifi.dbs.elki.math.histograms; /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -30,7 +30,7 @@ import org.junit.Test; import de.lmu.ifi.dbs.elki.JUnit4Test; import de.lmu.ifi.dbs.elki.utilities.iterator.IterableUtil; -import de.lmu.ifi.dbs.elki.utilities.pairs.Pair; +import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleObjPair; /** * JUnit test to test the {@link ReplacingHistogram} class. @@ -68,15 +68,15 @@ public class TestFlexiHistogram implements JUnit4Test { // compare results via Iterator. int off = 0; - for(Pair<Double, Double> pair : hist) { - assertEquals("Array iterator bin position", -0.1 + 0.2 * off, pair.getFirst(), 0.00001); + for(DoubleObjPair<Double> pair : hist) { + assertEquals("Array iterator bin position", -0.1 + 0.2 * off, pair.first, 0.00001); assertEquals("Array iterator bin contents", resized[off], pair.getSecond(), 0.00001); off++; } // backwards... off--; - for(Pair<Double, Double> pair : IterableUtil.fromIterator(hist.reverseIterator())) { - assertEquals("Array iterator bin position", -0.1 + 0.2 * off, pair.getFirst(), 0.00001); + for(DoubleObjPair<Double> pair : IterableUtil.fromIterator(hist.reverseIterator())) { + assertEquals("Array iterator bin position", -0.1 + 0.2 * off, pair.first, 0.00001); assertEquals("Array iterator bin contents", resized[off], pair.getSecond(), 0.00001); off--; } diff --git a/test/de/lmu/ifi/dbs/elki/math/TestReplacingHistogram.java b/test/de/lmu/ifi/dbs/elki/math/histograms/TestReplacingHistogram.java index 266a437f..455a880a 100644 --- a/test/de/lmu/ifi/dbs/elki/math/TestReplacingHistogram.java +++ b/test/de/lmu/ifi/dbs/elki/math/histograms/TestReplacingHistogram.java @@ -1,10 +1,10 @@ -package de.lmu.ifi.dbs.elki.math; +package de.lmu.ifi.dbs.elki.math.histograms; /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -29,7 +29,7 @@ import static org.junit.Assert.assertEquals; import org.junit.Test; import de.lmu.ifi.dbs.elki.JUnit4Test; -import de.lmu.ifi.dbs.elki.utilities.pairs.Pair; +import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleObjPair; /** * JUnit test to test the {@link ReplacingHistogram} class. @@ -66,8 +66,8 @@ public class TestReplacingHistogram implements JUnit4Test { // compare results via Iterator. int off = 0; - for(Pair<Double, Double> pair : hist) { - assertEquals("Array iterator bin position", -0.15 + 0.1 * off, pair.getFirst(), 0.00001); + for(DoubleObjPair<Double> pair : hist) { + assertEquals("Array iterator bin position", -0.15 + 0.1 * off, pair.first, 0.00001); assertEquals("Array iterator bin contents", resized[off], pair.getSecond(), 0.00001); off++; } diff --git a/test/de/lmu/ifi/dbs/elki/visualization/TestLinearScale.java b/test/de/lmu/ifi/dbs/elki/math/scales/TestLinearScale.java index e4ca972b..f593902c 100644 --- a/test/de/lmu/ifi/dbs/elki/visualization/TestLinearScale.java +++ b/test/de/lmu/ifi/dbs/elki/math/scales/TestLinearScale.java @@ -1,10 +1,10 @@ -package de.lmu.ifi.dbs.elki.visualization; +package de.lmu.ifi.dbs.elki.math.scales; /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -28,7 +28,7 @@ import static org.junit.Assert.assertEquals; import org.junit.Test; import de.lmu.ifi.dbs.elki.JUnit4Test; -import de.lmu.ifi.dbs.elki.visualization.scales.LinearScale; +import de.lmu.ifi.dbs.elki.math.scales.LinearScale; /** * Test class to test rounding of the linear scale. diff --git a/test/de/lmu/ifi/dbs/elki/persistent/TestByteArrayUtil.java b/test/de/lmu/ifi/dbs/elki/persistent/TestByteArrayUtil.java index 769b3fe2..21848a04 100644 --- a/test/de/lmu/ifi/dbs/elki/persistent/TestByteArrayUtil.java +++ b/test/de/lmu/ifi/dbs/elki/persistent/TestByteArrayUtil.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.persistent; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/persistent/TestOnDiskArray.java b/test/de/lmu/ifi/dbs/elki/persistent/TestOnDiskArray.java index 910e4898..4483a29e 100644 --- a/test/de/lmu/ifi/dbs/elki/persistent/TestOnDiskArray.java +++ b/test/de/lmu/ifi/dbs/elki/persistent/TestOnDiskArray.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.persistent; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/persistent/TestOnDiskUpperTriangleMatrix.java b/test/de/lmu/ifi/dbs/elki/persistent/TestOnDiskUpperTriangleMatrix.java index 2690a651..c5997615 100644 --- a/test/de/lmu/ifi/dbs/elki/persistent/TestOnDiskUpperTriangleMatrix.java +++ b/test/de/lmu/ifi/dbs/elki/persistent/TestOnDiskUpperTriangleMatrix.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.persistent; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/utilities/TestBitsUtil.java b/test/de/lmu/ifi/dbs/elki/utilities/TestBitsUtil.java new file mode 100644 index 00000000..504e5764 --- /dev/null +++ b/test/de/lmu/ifi/dbs/elki/utilities/TestBitsUtil.java @@ -0,0 +1,186 @@ +package de.lmu.ifi.dbs.elki.utilities; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import static org.junit.Assert.*; + +import java.math.BigInteger; +import java.util.BitSet; +import java.util.Random; + +import org.junit.Test; + +import de.lmu.ifi.dbs.elki.JUnit4Test; +import de.lmu.ifi.dbs.elki.utilities.BitsUtil; + +public class TestBitsUtil implements JUnit4Test { + @Test + public void testAgainstBigInteger() { + BigInteger bigint = new BigInteger("123"); + long[] bituti = BitsUtil.make(Long.SIZE, 123); + assertEquals("Bit strings do not agree.", bigint.toString(2), BitsUtil.toString(bituti)); + + bigint = bigint.shiftLeft(13); + BitsUtil.shiftLeftI(bituti, 13); + assertEquals("Bit strings do not agree.", bigint.toString(2), BitsUtil.toString(bituti)); + + bigint = bigint.shiftRight(15); + BitsUtil.shiftRightI(bituti, 15); + assertEquals("Bit strings do not agree.", bigint.toString(2), BitsUtil.toString(bituti)); + } + + @Test + public void testSimpleOperations() { + long[] test = BitsUtil.zero(128); + BitsUtil.setI(test, 5); + BitsUtil.setI(test, 7); + assertEquals(BitsUtil.toString(test), "10100000"); + assertEquals(BitsUtil.numberOfTrailingZerosSigned(test), 5); + BitsUtil.truncateI(test, 7); + assertEquals(BitsUtil.toString(test), "100000"); + assertEquals(BitsUtil.numberOfTrailingZerosSigned(test), 5); + BitsUtil.setI(test, 7); + assertEquals(BitsUtil.toString(test), "10100000"); + assertEquals(BitsUtil.numberOfTrailingZerosSigned(test), 5); + BitsUtil.cycleRightI(test, 6, 8); + assertEquals(BitsUtil.toString(test), "10000010"); + assertEquals(BitsUtil.numberOfTrailingZerosSigned(test), 1); + + BitsUtil.zeroI(test); + BitsUtil.setI(test, 125); + BitsUtil.setI(test, 60); + BitsUtil.cycleRightI(test, 70, 128); + assertTrue(BitsUtil.get(test, 55)); + assertTrue(BitsUtil.get(test, 118)); + assertEquals(BitsUtil.cardinality(test), 2); + BitsUtil.cycleLeftI(test, 70, 128); + assertTrue(BitsUtil.get(test, 125)); + assertTrue(BitsUtil.get(test, 60)); + assertEquals(BitsUtil.cardinality(test), 2); + } + + @Test + public void testSorting() { + final Random r = new Random(0); + final int cnt = 100; + long[] rnds = new long[cnt]; + long[][] bits = new long[cnt][]; + for(int i = 0; i < cnt; i++) { + rnds[i] = Math.abs(r.nextLong()); + bits[i] = BitsUtil.make(Long.SIZE, rnds[i]); + } + + for(int i = 0; i < cnt; i++) { + for(int j = 0; j < cnt; j++) { + assertEquals(compare(rnds[i], rnds[j]), BitsUtil.compare(bits[i], bits[j])); + } + } + + for(int i = 0; i < cnt; i++) { + long[] btmp = BitsUtil.copy(bits[i], 64 + r.nextInt(500)); + assertEquals(BitsUtil.compare(btmp, bits[i]), 0); + for(int j = 0; j < cnt; j++) { + assertEquals(compare(rnds[i], rnds[j]), BitsUtil.compare(btmp, bits[j])); + } + } + + for(int i = 0; i < cnt; i++) { + long[] btmp = BitsUtil.truncateI(BitsUtil.copy(bits[i]), 47); + for(int j = 0; j < cnt; j++) { + assertEquals(compare(rnds[i] & ((1 << 48) - 1), rnds[j]), BitsUtil.compare(btmp, bits[j])); + } + } + + for(int i = 0; i < cnt; i++) { + long[] btmp = BitsUtil.cycleRightI(BitsUtil.copy(bits[i]), 13, Long.SIZE - 32); + long ltmp = BitsUtil.cycleRightC(rnds[i], 13, Long.SIZE - 32); + for(int j = 0; j < cnt; j++) { + assertEquals(compare(ltmp, rnds[j]), BitsUtil.compare(btmp, bits[j])); + } + } + } + + /** + * Not jet in Java 6. To come in JDK7 as Long.copmare + * + * @param x + * @param y + * @return + */ + public static int compare(long x, long y) { + return (x < y) ? -1 : ((x == y) ? 0 : 1); + } + + @Test + public void testAgainstBitSet() { + BitSet bitset = new BitSet(); + long[] bituti = BitsUtil.zero(Long.SIZE); + for (int i = 0; i >= 0;) { + assertEquals("Bit strings do not agree.", bitset.nextSetBit(i), BitsUtil.nextSetBit(bituti, i)); + i = bitset.nextSetBit(i + 1); + } + // Java 7: + // assertEquals("Bit strings do not agree.", BitsUtil.toString(bitset.toLongArray()), BitsUtil.toString(bituti)); + + bitset.set(4); + BitsUtil.setI(bituti, 4); + for (int i = 0; i >= 0;) { + assertEquals("Bit strings do not agree.", bitset.nextSetBit(i), BitsUtil.nextSetBit(bituti, i)); + i = bitset.nextSetBit(i + 1); + } + // Java 7: + // assertEquals("Bit strings do not agree.", BitsUtil.toString(bitset.toLongArray()), BitsUtil.toString(bituti)); + + bitset.set(15); + BitsUtil.setI(bituti, 15); + for (int i = 0; i >= 0;) { + assertEquals("Bit strings do not agree.", bitset.nextSetBit(i), BitsUtil.nextSetBit(bituti, i)); + i = bitset.nextSetBit(i + 1); + } + // Java 7: + // assertEquals("Bit strings do not agree.", BitsUtil.toString(bitset.toLongArray()), BitsUtil.toString(bituti)); + + assertEquals(bitset.nextSetBit(0), BitsUtil.nextSetBit(bituti, 0)); + assertEquals(bitset.nextSetBit(4), BitsUtil.nextSetBit(bituti, 4)); + assertEquals(bitset.nextSetBit(5), BitsUtil.nextSetBit(bituti, 5)); + // previousSetBit is not in JDK6. + // assertEquals(bitset.previousSetBit(64), BitsUtil.previousSetBit(bituti, 64)); + // assertEquals(bitset.previousSetBit(15), BitsUtil.previousSetBit(bituti, 15)); + // assertEquals(bitset.previousSetBit(14), BitsUtil.previousSetBit(bituti, 14)); + } + + @Test + public void testGrayCoding() { + long[] bits = BitsUtil.zero(123); + long[] ones = BitsUtil.ones(123); + BitsUtil.flipI(bits, 122); + BitsUtil.invgrayI(bits); + BitsUtil.xorI(bits, ones); + assertTrue(BitsUtil.isZero(bits)); + BitsUtil.xorI(bits, ones); + BitsUtil.grayI(bits); + assertTrue(BitsUtil.get(bits, 122)); + assertEquals(1, BitsUtil.cardinality(bits)); + } +}
\ No newline at end of file diff --git a/test/de/lmu/ifi/dbs/elki/utilities/datastructures/TestHeap.java b/test/de/lmu/ifi/dbs/elki/utilities/datastructures/TestHeap.java deleted file mode 100644 index fcdc28d2..00000000 --- a/test/de/lmu/ifi/dbs/elki/utilities/datastructures/TestHeap.java +++ /dev/null @@ -1,64 +0,0 @@ -package de.lmu.ifi.dbs.elki.utilities.datastructures; - -/* - This file is part of ELKI: - Environment for Developing KDD-Applications Supported by Index-Structures - - Copyright (C) 2011 - Ludwig-Maximilians-Universität München - Lehr- und Forschungseinheit für Datenbanksysteme - ELKI Development Team - - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU Affero General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU Affero General Public License for more details. - - You should have received a copy of the GNU Affero General Public License - along with this program. If not, see <http://www.gnu.org/licenses/>. - */ - -import static org.junit.Assert.assertEquals; - -import java.util.Collections; - -import org.junit.Test; - -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap; - -/** - * Test the in-memory heap class. - * - * @author Erich Schubert - */ -public class TestHeap { - /** - * Puts 10 integers into both an ascending and a descending heap and verifies - * they come out in sequence. - */ - @Test - public void testHeap() { - Integer[] data = { 5, 3, 4, 2, 7, 1, 9, 8, 10, 6 }; - Integer[] asc = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; - Integer[] desc = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }; - Heap<Integer> hasc = new Heap<Integer>(); - Heap<Integer> hdesc = new Heap<Integer>(Collections.reverseOrder()); - for(Integer i : data) { - hasc.add(i); - hdesc.add(i); - } - for(int i = 0; i < asc.length; i++) { - final Integer gota = hasc.poll(); - assertEquals("Objects sorted incorrectly at ascending position " + i, asc[i], gota); - } - for(int i = 0; i < desc.length; i++) { - final Integer gotd = hdesc.poll(); - assertEquals("Objects sorted incorrectly at descending position " + i, desc[i], gotd); - } - } -} diff --git a/test/de/lmu/ifi/dbs/elki/math/TestQuickSelect.java b/test/de/lmu/ifi/dbs/elki/utilities/datastructures/TestQuickSelect.java index 132be182..b9030d59 100644 --- a/test/de/lmu/ifi/dbs/elki/math/TestQuickSelect.java +++ b/test/de/lmu/ifi/dbs/elki/utilities/datastructures/TestQuickSelect.java @@ -1,10 +1,10 @@ -package de.lmu.ifi.dbs.elki.math; +package de.lmu.ifi.dbs.elki.utilities.datastructures; /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -31,7 +31,7 @@ import java.util.Random; import org.junit.Test; import de.lmu.ifi.dbs.elki.JUnit4Test; -import de.lmu.ifi.dbs.elki.math.statistics.QuickSelect; +import de.lmu.ifi.dbs.elki.utilities.datastructures.QuickSelect; /** * Test the QuickSelect math class. @@ -96,10 +96,10 @@ public class TestQuickSelect implements JUnit4Test { @Test public void testPartialArray() { double data[] = new double[] { 0.1, 0.2, 1, 2, 3, 0.9, 0.95 }; - assertEquals("Partial median incorrect.", 1, QuickSelect.median(data, 2, 2), Double.MIN_VALUE); - assertEquals("Partial median incorrect.", 3, QuickSelect.median(data, 4, 4), Double.MIN_VALUE); + assertEquals("Partial median incorrect.", 1, QuickSelect.median(data, 2, 3), Double.MIN_VALUE); + assertEquals("Partial median incorrect.", 3, QuickSelect.median(data, 4, 5), Double.MIN_VALUE); // Note: do not change the order, since this modifies the array. - assertEquals("Partial median incorrect.", 2, QuickSelect.median(data, 2, 4), Double.MIN_VALUE); + assertEquals("Partial median incorrect.", 2, QuickSelect.median(data, 2, 5), Double.MIN_VALUE); // Note: do not change the order, since this modifies the array. assertEquals("Full median incorrect.", 0.95, QuickSelect.median(data), Double.MIN_VALUE); } diff --git a/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestHeap.java b/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestHeap.java new file mode 100644 index 00000000..33ebdfae --- /dev/null +++ b/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestHeap.java @@ -0,0 +1,235 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; + +import java.util.Collections; +import java.util.Random; + +import org.junit.Test; + +import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap; + +/** + * Test the in-memory heap class. + * + * @author Erich Schubert + */ +public class TestHeap { + /** + * Puts 10 integers into both an ascending and a descending heap and verifies + * they come out in sequence. + */ + @Test + public void testHeap() { + int dup = 2; + Integer[] data = { 5, 3, 4, 2, 7, 1, 9, 8, 10, 6 }; + Integer[] asc = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; + Integer[] desc = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }; + Heap<Integer> hasc = new Heap<Integer>(null); + Heap<Integer> hdesc = new Heap<Integer>(Collections.reverseOrder()); + for(Integer i : data) { + for(int j = 0; j < dup; j++) { + hasc.add(i); + hdesc.add(i); + } + } + // Empty + for(int i = 0; i < asc.length; i++) { + for(int j = 0; j < dup; j++) { + final Integer gota = hasc.poll(); + assertEquals("Objects sorted incorrectly at ascending position " + i, asc[i], gota); + final Integer gotd = hdesc.poll(); + assertEquals("Objects sorted incorrectly at descending position " + i, desc[i], gotd); + } + } + // Refill + for(Integer i : data) { + for(int j = 0; j < dup; j++) { + hasc.add(i); + hdesc.add(i); + } + } + // Empty halfway + for(int i = 0; i < 5; i++) { + for(int j = 0; j < dup; j++) { + final Integer gota = hasc.poll(); + assertEquals("Objects sorted incorrectly at ascending position " + i, asc[i], gota); + final Integer gotd = hdesc.poll(); + assertEquals("Objects sorted incorrectly at descending position " + i, desc[i], gotd); + } + } + // Re-add + for(int i = 0; i < 5; i++) { + for(int j = 0; j < dup; j++) { + hasc.add(asc[i]); + hdesc.add(desc[i]); + } + } + // Empty again + for(int i = 0; i < asc.length; i++) { + for(int j = 0; j < dup; j++) { + final Integer gota = hasc.poll(); + assertEquals("Objects sorted incorrectly at ascending position " + i, asc[i], gota); + final Integer gotd = hdesc.poll(); + assertEquals("Objects sorted incorrectly at descending position " + i, desc[i], gotd); + } + } + // Sequential insert + for(int i : asc) { + for(int j = 0; j < dup; j++) { + hasc.add(i); + hdesc.add(i); + } + } + // Empty halfway + for(int i = 0; i < 5; i++) { + for(int j = 0; j < dup; j++) { + final Integer gota = hasc.poll(); + assertEquals("Objects sorted incorrectly at ascending position " + i, asc[i], gota); + final Integer gotd = hdesc.poll(); + assertEquals("Objects sorted incorrectly at descending position " + i, desc[i], gotd); + } + } + // Re-add + for(int i = 0; i < 5; i++) { + for(int j = 0; j < dup; j++) { + hasc.add(asc[i]); + hdesc.add(desc[i]); + } + } + // Empty again + for(int i = 0; i < asc.length; i++) { + for(int j = 0; j < dup; j++) { + final Integer gota = hasc.poll(); + assertEquals("Objects sorted incorrectly at ascending position " + i, asc[i], gota); + final Integer gotd = hdesc.poll(); + assertEquals("Objects sorted incorrectly at descending position " + i, desc[i], gotd); + } + } + + // Bonus: Sequential insert lower part only + for(int i = 0; i < asc.length >> 1; i++) { + for(int j = 0; j < dup << 1; j++) { + hasc.add(asc[i]); + hdesc.add(desc[i]); + } + } + // Empty halfway + for(int i = 0; i < 3; i++) { + for(int j = 0; j < dup << 1; j++) { + final Integer gota = hasc.poll(); + assertEquals("Objects sorted incorrectly at ascending position " + i, asc[i], gota); + final Integer gotd = hdesc.poll(); + assertEquals("Objects sorted incorrectly at descending position " + i, desc[i], gotd); + } + } + // Add upper half + for(int i = asc.length >> 1; i < asc.length; i++) { + for(int j = 0; j < dup; j++) { + hasc.add(asc[i]); + hdesc.add(desc[i]); + } + } + //System.err.println(hasc.toString() + " " + hasc.validSize); + // Empty again + for(int i = 3; i < asc.length; i++) { + int f = (i < (asc.length >> 1)) ? 2 : 1; + for(int j = 0; j < dup * f; j++) { + final Integer gota = hasc.poll(); + //System.err.println(hasc.toString() + " " + hasc.validSize); + assertEquals("Objects sorted incorrectly at ascending position " + i, asc[i], gota); + final Integer gotd = hdesc.poll(); + assertEquals("Objects sorted incorrectly at descending position " + i, desc[i], gotd); + } + } + } + + /** + * Puts 10 integers into both an ascending and a descending heap and verifies + * they come out in sequence. + */ + @Test + public void testHeapRandomInt() { + int size = 10000; + Random r = new Random(123L); + Heap<Integer> hasc = new Heap<Integer>(); + Heap<Integer> hdesc = new Heap<Integer>(Collections.reverseOrder()); + for(int i = 0; i < size; i++) { + int in = r.nextInt(); + hasc.add(in); + hdesc.add(in); + } + int last = Integer.MIN_VALUE; + for(int i = 0; i < size; i++) { + final Integer gota = hasc.poll(); + assertTrue("Objects sorted incorrectly at ascending position " + i, gota >= last); + last = gota; + } + last = Integer.MAX_VALUE; + for(int i = 0; i < size; i++) { + final Integer gotd = hdesc.poll(); + assertTrue("Objects sorted incorrectly at descending position " + i, gotd <= last); + last = gotd; + } + // Rerun, but only halfway down + for(int i = 0; i < size; i++) { + int in = r.nextInt(); + hasc.add(in); + hdesc.add(in); + } + last = Integer.MIN_VALUE; + for(int i = 0; i < size >>> 1; i++) { + final Integer gota = hasc.poll(); + assertTrue("Objects sorted incorrectly at ascending position " + i, gota >= last); + last = gota; + } + last = Integer.MAX_VALUE; + for(int i = 0; i < size >>> 1; i++) { + final Integer gotd = hdesc.poll(); + assertTrue("Objects sorted incorrectly at descending position " + i, gotd <= last); + last = gotd; + } + // Refill: + for(int i = size >>> 1; i < size; i++) { + int in = r.nextInt(); + hasc.add(in); + hdesc.add(in); + } + last = Integer.MIN_VALUE; + for(int i = 0; i < size; i++) { + final Integer gota = hasc.poll(); + assertTrue("Objects sorted incorrectly at ascending position " + i, gota >= last); + last = gota; + } + last = Integer.MAX_VALUE; + for(int i = 0; i < size; i++) { + final Integer gotd = hdesc.poll(); + assertTrue("Objects sorted incorrectly at descending position " + i, gotd <= last); + last = gotd; + } + } +}
\ No newline at end of file diff --git a/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestHeapPerformance.java b/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestHeapPerformance.java new file mode 100644 index 00000000..2f990e30 --- /dev/null +++ b/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestHeapPerformance.java @@ -0,0 +1,113 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; +import java.util.PriorityQueue; +import java.util.Queue; +import java.util.Random; + +import org.junit.Test; + +import de.lmu.ifi.dbs.elki.JUnit4Test; +import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap; + +/** + * Unit test to ensure that our heap is not significantly worse than SUN javas + * regular PriorityQueue. + * + * @author Erich Schubert + */ +public class TestHeapPerformance implements JUnit4Test { + final private int queueSize = 100000; + + final private int iterations = 20; + + final private long seed = 123456L; + + @Test + public void testRuntime() throws Exception { + // prepare the data set + final List<Integer> elements = new ArrayList<Integer>(queueSize); + { + final Random random = new Random(seed); + for(int i = 0; i < queueSize; i++) { + elements.add(i); + } + Collections.shuffle(elements, random); + } + + // Pretest, to trigger hotspot compiler, hopefully. + { + for(int j = 0; j < iterations; j++) { + Heap<Integer> pq = new Heap<Integer>(); + testQueue(elements, pq); + } + for(int j = 0; j < iterations; j++) { + PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); // 11, + testQueue(elements, pq); + } + } + + long hstart = System.nanoTime(); + { + for(int j = 0; j < iterations; j++) { + Heap<Integer> pq = new Heap<Integer>(); + testQueue(elements, pq); + } + } + long htime = System.nanoTime() - hstart; + + long pqstart = System.nanoTime(); + { + for(int j = 0; j < iterations; j++) { + PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); // 11 + testQueue(elements, pq); + } + } + long pqtime = System.nanoTime() - pqstart; + System.err.println("Heap performance test: us: " + htime*1E-9 + " java: " + pqtime*1E-9); + assertTrue("Heap performance regression - run test individually, since the hotspot optimizations may make the difference! " + htime + " >>= " + pqtime, htime < 1.05 * pqtime); + // 1.05 allows some difference in measuring + } + + private void testQueue(final List<Integer> elements, Queue<Integer> pq) { + // Insert all + for(int i = 0; i < elements.size(); i++) { + pq.add(elements.get(i)); + } + // Poll first half. + for(int i = 0; i < elements.size() >> 1; i++) { + assertEquals((int) pq.poll(), i); + // assertEquals((int) pq.poll(), queueSize - 1 - i); + } + assertTrue("Heap not half-empty?", pq.size() == (elements.size() >> 1)); + pq.clear(); + } +}
\ No newline at end of file diff --git a/test/de/lmu/ifi/dbs/elki/utilities/datastructures/TestTiedTopBoundedHeap.java b/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestTiedTopBoundedHeap.java index cb4492b8..8059a873 100644 --- a/test/de/lmu/ifi/dbs/elki/utilities/datastructures/TestTiedTopBoundedHeap.java +++ b/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestTiedTopBoundedHeap.java @@ -1,10 +1,10 @@ -package de.lmu.ifi.dbs.elki.utilities.datastructures; +package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestTiedTopBoundedUpdatableHeap.java b/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestTiedTopBoundedUpdatableHeap.java new file mode 100644 index 00000000..b5ad9b2c --- /dev/null +++ b/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestTiedTopBoundedUpdatableHeap.java @@ -0,0 +1,114 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.Random; + +import org.junit.Test; + +import de.lmu.ifi.dbs.elki.JUnit4Test; + +public class TestTiedTopBoundedUpdatableHeap implements JUnit4Test { + @Test + public void testTiedTopBoundedUpdatableHeap() { + final int iters = 100; + final int maxid = 5000; + final int bsize = 1000; + final int limit = 200; + final Random r = new Random(1); + ArrayList<IntegerPriorityObject<Integer>> simulate = new ArrayList<IntegerPriorityObject<Integer>>(1000); + TiedTopBoundedUpdatableHeap<IntegerPriorityObject<Integer>> heap = new TiedTopBoundedUpdatableHeap<IntegerPriorityObject<Integer>>(limit); + for(int i = 0; i < iters; i++) { + int batchsize = r.nextInt(bsize); + for(int j = 0; j < batchsize; j++) { + int id = r.nextInt(maxid); + int score = r.nextInt(10000); + IntegerPriorityObject<Integer> nobj = new IntegerPriorityObject<Integer>(score, id); + // Update heap + heap.offer(nobj); + // Enabling the followig assertion *hides* certain problems! + // assertTrue("Heap not valid at i="+i, heap.checkHeap()); + // Update simulation + boolean found = false; + for(IntegerPriorityObject<Integer> ent : simulate) { + if(ent.getObject().equals(id)) { + if(score > ent.priority) { + ent.priority = score; + } + found = true; + break; + } + } + if(!found) { + simulate.add(nobj); + } + Collections.sort(simulate, Collections.reverseOrder()); + while(simulate.size() > limit) { + int max = simulate.get(limit - 1).priority; + if(simulate.get(simulate.size() - 1).priority == max) { + break; + } + else { + assertTrue(simulate.get(simulate.size() - 1).priority > max); + simulate.remove(simulate.size() - 1); + } + } + if(simulate.size() != heap.size()) { + System.err.println("Lost synchronization " + i + "/" + j + ": " + id + " to " + score + "(" + found + ") sizes: " + simulate.size() + " " + heap.size()); + System.err.println("Sim: " + simulate.get(simulate.size() - 1) + " <=> Heap: " + heap.peek()); + } + assertEquals("Sizes don't match!", simulate.size(), heap.size()); + } + assertEquals("Heap not valid at i=" + i, null, heap.checkHeap()); + + // System.err.println("Sim: " + simulate.get(simulate.size() - 1) + + // " <=> Heap: " + heap.peek()); + // System.err.println(simulate.size() + " <=> " + heap.size()); + int remove = r.nextInt(simulate.size()); + for(int j = 0; j < remove; j++) { + // System.out.println(heap.toString()); + IntegerPriorityObject<Integer> fromheap = heap.poll(); + IntegerPriorityObject<Integer> fromsim = simulate.remove(simulate.size() - 1); + assertEquals("Priority doesn't agree.", fromheap.priority, fromsim.priority); + if(j + 1 == remove) { + while(heap.size() > 0) { + assertEquals("Priority doesn't agree.", heap.peek().priority, simulate.get(simulate.size() - 1).priority); + if(heap.peek().priority == fromheap.priority) { + fromheap = heap.poll(); + fromsim = simulate.remove(simulate.size() - 1); + } + else { + break; + } + } + } + } + } + } +} diff --git a/test/de/lmu/ifi/dbs/elki/utilities/datastructures/TestTopBoundedHeap.java b/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestTopBoundedHeap.java index f0160d5e..7586556c 100644 --- a/test/de/lmu/ifi/dbs/elki/utilities/datastructures/TestTopBoundedHeap.java +++ b/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestTopBoundedHeap.java @@ -1,10 +1,10 @@ -package de.lmu.ifi.dbs.elki.utilities.datastructures; +package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestUpdatableHeap.java b/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestUpdatableHeap.java new file mode 100644 index 00000000..7e0e8650 --- /dev/null +++ b/test/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TestUpdatableHeap.java @@ -0,0 +1,88 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import static org.junit.Assert.*; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.Random; + +import org.junit.Test; + +import de.lmu.ifi.dbs.elki.JUnit4Test; + +public class TestUpdatableHeap implements JUnit4Test { + @Test + public void testUpdatableHeap() { + final int iters = 100; + final int maxid = 5000; + final int bsize = 100; + final Random r = new Random(1); + ArrayList<IntegerPriorityObject<Integer>> simulate = new ArrayList<IntegerPriorityObject<Integer>>(1000); + UpdatableHeap<IntegerPriorityObject<Integer>> heap = new UpdatableHeap<IntegerPriorityObject<Integer>>(); + for(int i = 0; i < iters; i++) { + int batchsize = r.nextInt(bsize); + for(int j = 0; j < batchsize; j++) { + int id = r.nextInt(maxid); + int score = r.nextInt(10000); + // Update heap + heap.add(new IntegerPriorityObject<Integer>(score, id)); + // Update simulation + boolean found = false; + for(IntegerPriorityObject<Integer> ent : simulate) { + if(ent.getObject().equals(id)) { + if(score > ent.priority) { + // System.err.println("Updating in ArrayList: " + ent + " to " + score); + ent.priority = score; + } + found = true; + break; + } + } + if(!found) { + simulate.add(new IntegerPriorityObject<Integer>(score, id)); + } + } + // Keeping the simulation list reverse is a bit faster for removal + Collections.sort(simulate, Collections.reverseOrder()); + // System.err.println(simulate.size() + " <=> " + heap.size()); + assertEquals("Sizes don't match!", simulate.size(), heap.size()); + int remove = r.nextInt(simulate.size()); + for(int j = 0; j < remove; j++) { + // System.out.println(heap.toString()); + IntegerPriorityObject<Integer> fromheap = heap.poll(); + IntegerPriorityObject<Integer> fromsim = simulate.remove(simulate.size() - 1); + //System.out.println(fromheap+" <=> "+fromsim); + assertEquals("Priority doesn't agree.", fromheap.priority, fromsim.priority); + if(fromheap.getObject() != fromsim.getObject()) { + // Ties + if(j + 1 == remove && heap.size() > 0) { + j++; + } + } + } + } + } +} |