diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/database')
119 files changed, 2758 insertions, 894 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/database/AbstractDatabase.java b/src/de/lmu/ifi/dbs/elki/database/AbstractDatabase.java index f20efcec..f9582039 100644 --- a/src/de/lmu/ifi/dbs/elki/database/AbstractDatabase.java +++ b/src/de/lmu/ifi/dbs/elki/database/AbstractDatabase.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database; 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 @@ -26,6 +26,7 @@ package de.lmu.ifi.dbs.elki.database; import java.util.Collection; import java.util.Collections; import java.util.List; +import java.util.ListIterator; import de.lmu.ifi.dbs.elki.data.type.NoSupportedDataTypeException; import de.lmu.ifi.dbs.elki.data.type.TypeInformation; @@ -106,7 +107,7 @@ public abstract class AbstractDatabase extends AbstractHierarchicalResult implem } @Override - public Collection<Index> getIndexes() { + public List<Index> getIndexes() { return Collections.unmodifiableList(this.indexes); } @@ -151,6 +152,14 @@ public abstract class AbstractDatabase extends AbstractHierarchicalResult implem return (Relation<O>) relation; } } + if (getLogger().isDebugging()) { + StringBuffer buf = new StringBuffer(); + buf.append("No matching relation for type ").append(restriction.toString()).append(":\n"); + for(Relation<?> relation : relations) { + buf.append(relation.getDataTypeInformation().toString()).append(","); + } + getLogger().debug(buf); + } throw new NoSupportedDataTypeException(restriction); } @@ -175,8 +184,13 @@ public abstract class AbstractDatabase extends AbstractHierarchicalResult implem if(distanceQuery == null) { throw new AbortException("kNN query requested for 'null' distance!"); } - for(Index idx : getIndexes()) { + ListIterator<Index> iter = indexes.listIterator(indexes.size()); + while(iter.hasPrevious()) { + Index idx = iter.previous(); if(idx instanceof KNNIndex) { + if(getLogger().isDebuggingFinest()) { + getLogger().debugFinest("Considering index for kNN Query: " + idx); + } @SuppressWarnings("unchecked") final KNNIndex<O> knnIndex = (KNNIndex<O>) idx; KNNQuery<O, D> q = knnIndex.getKNNQuery(distanceQuery, hints); @@ -200,8 +214,13 @@ public abstract class AbstractDatabase extends AbstractHierarchicalResult implem if(distanceQuery == null) { throw new AbortException("Range query requested for 'null' distance!"); } - for(Index idx : getIndexes()) { + ListIterator<Index> iter = indexes.listIterator(indexes.size()); + while(iter.hasPrevious()) { + Index idx = iter.previous(); if(idx instanceof RangeIndex) { + if(getLogger().isDebuggingFinest()) { + getLogger().debugFinest("Considering index for range query: " + idx); + } @SuppressWarnings("unchecked") final RangeIndex<O> rangeIndex = (RangeIndex<O>) idx; RangeQuery<O, D> q = rangeIndex.getRangeQuery(distanceQuery, hints); @@ -225,8 +244,13 @@ public abstract class AbstractDatabase extends AbstractHierarchicalResult implem if(distanceQuery == null) { throw new AbortException("RKNN query requested for 'null' distance!"); } - for(Index idx : getIndexes()) { + ListIterator<Index> iter = indexes.listIterator(indexes.size()); + while(iter.hasPrevious()) { + Index idx = iter.previous(); if(idx instanceof RKNNIndex) { + if(getLogger().isDebuggingFinest()) { + getLogger().debugFinest("Considering index for RkNN Query: " + idx); + } @SuppressWarnings("unchecked") final RKNNIndex<O> rknnIndex = (RKNNIndex<O>) idx; RKNNQuery<O, D> q = rknnIndex.getRKNNQuery(distanceQuery, hints); diff --git a/src/de/lmu/ifi/dbs/elki/database/Database.java b/src/de/lmu/ifi/dbs/elki/database/Database.java index 1b216fd0..a931d5c8 100644 --- a/src/de/lmu/ifi/dbs/elki/database/Database.java +++ b/src/de/lmu/ifi/dbs/elki/database/Database.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database; 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,6 @@ import de.lmu.ifi.dbs.elki.data.type.TypeInformation; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreEvent; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreListener; import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.StaticDBIDs; 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.range.RangeQuery; @@ -43,6 +42,7 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.distance.similarityfunction.SimilarityFunction; import de.lmu.ifi.dbs.elki.index.Index; import de.lmu.ifi.dbs.elki.result.HierarchicalResult; +import de.lmu.ifi.dbs.elki.utilities.InspectionUtilFrequentlyScanned; /** * Database specifies the requirements for any database implementation. Note @@ -60,7 +60,7 @@ import de.lmu.ifi.dbs.elki.result.HierarchicalResult; * @apiviz.has Index oneway - - manages * @apiviz.uses DataStoreListener oneway - - invokes */ -public interface Database extends HierarchicalResult { +public interface Database extends HierarchicalResult, InspectionUtilFrequentlyScanned { /** * Initialize the database, for example by loading the input data. (Since this * should NOT be done on construction time!) @@ -68,14 +68,6 @@ public interface Database extends HierarchicalResult { public void initialize(); /** - * Returns the number of objects contained in this Database. - * - * @return the number of objects in this Database - */ - @Deprecated - int size(); - - /** * Get all relations of a database. * * @return All relations in the database @@ -93,18 +85,6 @@ public interface Database extends HierarchicalResult { <O> Relation<O> getRelation(TypeInformation restriction, Object... hints) throws NoSupportedDataTypeException; /** - * Get all matching object representations. - * - * @param <O> Object type - * @param restriction Type restriction - * @param hints Optimizer hints - * @return Object representation - */ - // TODO: add - // <O> Collection<DataQuery<O>> getObjectQueries(TypeInformation restriction, - // Object... hints); - - /** * Get the distance query for a particular distance function. * * @param <O> Object type @@ -210,17 +190,6 @@ public interface Database extends HierarchicalResult { // MultipleObjectsBundle getBundles(DBIDs id) throws ObjectNotFoundException; /** - * Returns a list comprising all IDs currently in use. - * - * The list returned shall not be linked to any actual list possibly hold in - * the database implementation. - * - * @return a list comprising all IDs currently in use - */ - @Deprecated - StaticDBIDs getDBIDs(); - - /** * Add a new index to the database. * * @param index Index to add diff --git a/src/de/lmu/ifi/dbs/elki/database/DatabaseEventManager.java b/src/de/lmu/ifi/dbs/elki/database/DatabaseEventManager.java index 333ac1eb..633be46f 100644 --- a/src/de/lmu/ifi/dbs/elki/database/DatabaseEventManager.java +++ b/src/de/lmu/ifi/dbs/elki/database/DatabaseEventManager.java @@ -3,7 +3,7 @@ package de.lmu.ifi.dbs.elki.database; 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/src/de/lmu/ifi/dbs/elki/database/HashmapDatabase.java b/src/de/lmu/ifi/dbs/elki/database/HashmapDatabase.java index a4c31379..e94bcfb1 100644 --- a/src/de/lmu/ifi/dbs/elki/database/HashmapDatabase.java +++ b/src/de/lmu/ifi/dbs/elki/database/HashmapDatabase.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database; 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 @@ -33,8 +33,7 @@ import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; -import de.lmu.ifi.dbs.elki.database.ids.StaticDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.TreeSetModifiableDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.relation.DBIDView; import de.lmu.ifi.dbs.elki.database.relation.MaterializedRelation; import de.lmu.ifi.dbs.elki.database.relation.Relation; @@ -75,7 +74,7 @@ public class HashmapDatabase extends AbstractDatabase implements UpdatableDataba /** * IDs of this database */ - private TreeSetModifiableDBIDs ids; + private HashSetModifiableDBIDs ids; /** * The DBID representation we use @@ -96,7 +95,7 @@ public class HashmapDatabase extends AbstractDatabase implements UpdatableDataba public HashmapDatabase(DatabaseConnection databaseConnection, Collection<IndexFactory<?, ?>> indexFactories) { super(); this.databaseConnection = databaseConnection; - this.ids = DBIDUtil.newTreeSet(); + this.ids = DBIDUtil.newHashSet(); this.idrep = new DBIDView(this, this.ids); this.relations.add(idrep); this.addChildResult(idrep); @@ -284,18 +283,6 @@ public class HashmapDatabase extends AbstractDatabase implements UpdatableDataba restoreID(id); } - @Deprecated - @Override - public final int size() { - return ids.size(); - } - - @Deprecated - @Override - public StaticDBIDs getDBIDs() { - return DBIDUtil.makeUnmodifiable(ids); - } - /** * Makes the given id reusable for new insertion operations. * diff --git a/src/de/lmu/ifi/dbs/elki/database/ProxyDatabase.java b/src/de/lmu/ifi/dbs/elki/database/ProxyDatabase.java index 4fc2455c..0f411cb4 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ProxyDatabase.java +++ b/src/de/lmu/ifi/dbs/elki/database/ProxyDatabase.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database; 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 @@ -25,9 +25,7 @@ package de.lmu.ifi.dbs.elki.database; import java.util.Arrays; -import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; -import de.lmu.ifi.dbs.elki.database.ids.StaticDBIDs; import de.lmu.ifi.dbs.elki.database.relation.DBIDView; import de.lmu.ifi.dbs.elki.database.relation.ProxyView; import de.lmu.ifi.dbs.elki.database.relation.Relation; @@ -120,18 +118,6 @@ public class ProxyDatabase extends AbstractDatabase { this.relations.add(relation); } - @Deprecated - @Override - public int size() { - return ids.size(); - } - - @Deprecated - @Override - public StaticDBIDs getDBIDs() { - return DBIDUtil.makeUnmodifiable(ids); - } - @Override protected Logging getLogger() { return logger; diff --git a/src/de/lmu/ifi/dbs/elki/database/QueryUtil.java b/src/de/lmu/ifi/dbs/elki/database/QueryUtil.java index 9e335f51..f65b3cba 100644 --- a/src/de/lmu/ifi/dbs/elki/database/QueryUtil.java +++ b/src/de/lmu/ifi/dbs/elki/database/QueryUtil.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database; 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/src/de/lmu/ifi/dbs/elki/database/StaticArrayDatabase.java b/src/de/lmu/ifi/dbs/elki/database/StaticArrayDatabase.java index 9d96a55f..79143ad8 100644 --- a/src/de/lmu/ifi/dbs/elki/database/StaticArrayDatabase.java +++ b/src/de/lmu/ifi/dbs/elki/database/StaticArrayDatabase.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database; 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 @@ -25,7 +25,6 @@ package de.lmu.ifi.dbs.elki.database; import java.util.BitSet; import java.util.Collection; -import java.util.Collections; import de.lmu.ifi.dbs.elki.data.type.SimpleTypeInformation; import de.lmu.ifi.dbs.elki.data.type.TypeUtil; @@ -33,7 +32,6 @@ import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; -import de.lmu.ifi.dbs.elki.database.ids.StaticDBIDs; import de.lmu.ifi.dbs.elki.database.relation.DBIDView; import de.lmu.ifi.dbs.elki.database.relation.MaterializedRelation; import de.lmu.ifi.dbs.elki.database.relation.Relation; @@ -65,7 +63,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; * @apiviz.uses DatabaseConnection */ @Description("Database using an in-memory hashtable and at least providing linear scans.") -public class StaticArrayDatabase extends AbstractDatabase implements Database, Parameterizable { +public class StaticArrayDatabase extends AbstractDatabase implements Parameterizable { /** * Our logger */ @@ -185,21 +183,14 @@ public class StaticArrayDatabase extends AbstractDatabase implements Database, P @Override public void addIndex(Index index) { + if(logger.isDebuggingFiner()) { + logger.debugFine("Adding index: " + index); + } this.indexes.add(index); // TODO: actually add index to the representation used? this.addChildResult(index); } - @Override - public Collection<Index> getIndexes() { - return Collections.unmodifiableList(this.indexes); - } - - @Override - public void removeIndex(Index index) { - this.indexes.remove(index); - this.getHierarchy().remove(this, index); - } /** * Find an DBID column. @@ -263,18 +254,6 @@ public class StaticArrayDatabase extends AbstractDatabase implements Database, P return relation; } - @Deprecated - @Override - public final int size() { - return ids.size(); - } - - @Deprecated - @Override - public StaticDBIDs getDBIDs() { - return DBIDUtil.makeUnmodifiable(ids); - } - @Override protected Logging getLogger() { return logger; diff --git a/src/de/lmu/ifi/dbs/elki/database/UpdatableDatabase.java b/src/de/lmu/ifi/dbs/elki/database/UpdatableDatabase.java index b74ebc1d..56a988f8 100644 --- a/src/de/lmu/ifi/dbs/elki/database/UpdatableDatabase.java +++ b/src/de/lmu/ifi/dbs/elki/database/UpdatableDatabase.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database; 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/src/de/lmu/ifi/dbs/elki/database/datastore/DataStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/DataStore.java index 1b0a714c..8d7f73ce 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/DataStore.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/DataStore.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.datastore; 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/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreEvent.java b/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreEvent.java index a6849360..5c0a6836 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreEvent.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreEvent.java @@ -3,7 +3,7 @@ package de.lmu.ifi.dbs.elki.database.datastore; 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/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreFactory.java b/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreFactory.java index d83c9a1c..65a1265d 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreFactory.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.datastore; 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,34 +42,35 @@ public interface DataStoreFactory { * Static storage factory */ public static DataStoreFactory FACTORY = new MemoryDataStoreFactory(); - + /** * Storage will be used only temporary. */ public final static int HINT_TEMP = 0x01; - + /** * "Hot" data, that will be used a lot, preferring memory storage. */ public final static int HINT_HOT = 0x02; - + /** * "static" data, that will not change often */ public final static int HINT_STATIC = 0x04; - + /** * Data that might require sorted access (so hashmaps are suboptimal) */ public final static int HINT_SORTED = 0x08; - + /** * Data that is the main database. Includes HOT, STATIC, SORTED */ public final static int HINT_DB = 0x1E; - + /** - * Make a new storage, to associate the given ids with an object of class dataclass. + * Make a new storage, to associate the given ids with an object of class + * dataclass. * * @param <T> stored data type * @param ids DBIDs to store data for @@ -78,9 +79,20 @@ public interface DataStoreFactory { * @return new data store */ public <T> WritableDataStore<T> makeStorage(DBIDs ids, int hints, Class<? super T> dataclass); - + + /** + * Make a new storage, to associate the given ids with an object of class + * dataclass. + * + * @param ids DBIDs to store data for + * @param hints Hints for the storage manager + * @return new data store + */ + public WritableDoubleDataStore makeDoubleStorage(DBIDs ids, int hints); + /** - * Make a new record storage, to associate the given ids with an object of class dataclass. + * Make a new record storage, to associate the given ids with an object of + * class dataclass. * * @param ids DBIDs to store data for * @param hints Hints for the storage manager diff --git a/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreIDMap.java b/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreIDMap.java index 21b876ce..ead75709 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreIDMap.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreIDMap.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.datastore; 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/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreListener.java b/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreListener.java index 02d5db77..609fe67d 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreListener.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreListener.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.datastore; 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/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreUtil.java b/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreUtil.java index 6e7af03d..f299c1e8 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreUtil.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreUtil.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.datastore; 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 @@ -48,6 +48,17 @@ public final class DataStoreUtil { } /** + * Make a new storage, to associate the given ids with an object of class dataclass. + * + * @param ids DBIDs to store data for + * @param hints Hints for the storage manager + * @return new data store + */ + public static WritableDoubleDataStore makeDoubleStorage(DBIDs ids, int hints) { + return DataStoreFactory.FACTORY.makeDoubleStorage(ids, hints); + } + + /** * Make a new record storage, to associate the given ids with an object of class dataclass. * * @param ids DBIDs to store data for diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/TreeSetDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/datastore/DoubleDataStore.java index 43fff9ef..ee315a0c 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/TreeSetDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/DoubleDataStore.java @@ -1,10 +1,12 @@ -package de.lmu.ifi.dbs.elki.database.ids; +package de.lmu.ifi.dbs.elki.database.datastore; + +import de.lmu.ifi.dbs.elki.database.ids.DBID; /* 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 @@ -23,12 +25,20 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ - /** - * Marker for sorted, tree-organized DBIDs + * Double-valued data store (avoids boxing/unboxing). * * @author Erich Schubert */ -public interface TreeSetDBIDs extends SetDBIDs { - // Empty -} +public interface DoubleDataStore extends DataStore<Double> { + @Deprecated + public Double get(DBID id); + + /** + * Retrieves an object from the storage. + * + * @param id Database ID. + * @return Double value + */ + public double doubleValue(DBID id); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/datastore/RangeIDMap.java b/src/de/lmu/ifi/dbs/elki/database/datastore/RangeIDMap.java index 85a0f4c4..7fc0ed7f 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/RangeIDMap.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/RangeIDMap.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.datastore; 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/src/de/lmu/ifi/dbs/elki/database/datastore/RecordStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/RecordStore.java index 31bbbc3b..508dae8e 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/RecordStore.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/RecordStore.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.datastore; 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/src/de/lmu/ifi/dbs/elki/database/datastore/WritableDataStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/WritableDataStore.java index a06c4b3f..7f1fbf52 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/WritableDataStore.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/WritableDataStore.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.datastore; 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/src/de/lmu/ifi/dbs/elki/database/datastore/WritableDoubleDataStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/WritableDoubleDataStore.java new file mode 100644 index 00000000..313e4adc --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/WritableDoubleDataStore.java @@ -0,0 +1,59 @@ +package de.lmu.ifi.dbs.elki.database.datastore; + +import de.lmu.ifi.dbs.elki.database.ids.DBID; + +/* + 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/>. + */ + +/** + * Data store specialized for doubles. Avoids boxing/unboxing. + * + * @author Erich Schubert + */ +public interface WritableDoubleDataStore extends DoubleDataStore, WritableDataStore<Double> { + @Override + @Deprecated + public Double put(DBID id, Double value); + + /** + * Associates the specified value with the specified id in this storage. If + * the storage previously contained a value for the id, the previous value is + * replaced by the specified value. + * + * @param id Database ID. + * @param value Value to store. + * @return previous value + */ + public double putDouble(DBID id, double value); + + /** + * Associates the specified value with the specified id in this storage. If + * the storage previously contained a value for the id, the previous value is + * replaced by the specified value. + * + * @param id Database ID. + * @param value Value to store. + * @return previous value + */ + public double put(DBID id, double value); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/datastore/WritableRecordStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/WritableRecordStore.java index 749acb0a..775d201b 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/WritableRecordStore.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/WritableRecordStore.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.datastore; 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/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayDoubleStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayDoubleStore.java new file mode 100644 index 00000000..433547a5 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayDoubleStore.java @@ -0,0 +1,121 @@ +package de.lmu.ifi.dbs.elki.database.datastore.memory; + +/* + 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 de.lmu.ifi.dbs.elki.database.datastore.DataStoreIDMap; +import de.lmu.ifi.dbs.elki.database.datastore.WritableDoubleDataStore; +import de.lmu.ifi.dbs.elki.database.ids.DBID; + +/** + * A class to answer representation queries using the stored Array. + * + * @author Erich Schubert + * + * @apiviz.composedOf de.lmu.ifi.dbs.elki.database.datastore.DataStoreIDMap + */ +public class ArrayDoubleStore implements WritableDoubleDataStore { + /** + * Data array + */ + private double[] data; + + /** + * DBID to index map + */ + private DataStoreIDMap idmap; + + /** + * Constructor. + * + * @param size Size + * @param idmap ID map + */ + public ArrayDoubleStore(int size, DataStoreIDMap idmap) { + super(); + this.data = new double[size]; + this.idmap = idmap; + } + + @Override + @Deprecated + public Double get(DBID id) { + try { + return data[idmap.map(id)]; + } + catch(ArrayIndexOutOfBoundsException e) { + return null; + } + } + + @Override + @Deprecated + public Double put(DBID id, Double value) { + final int off = idmap.map(id); + double ret = data[off]; + data[off] = value; + return ret; + } + + @Override + public double doubleValue(DBID id) { + return data[idmap.map(id)]; + } + + @Override + public double putDouble(DBID id, double value) { + final int off = idmap.map(id); + final double ret = data[off]; + data[off] = value; + return ret; + } + + @Override + public double put(DBID id, double value) { + final int off = idmap.map(id); + final double ret = data[off]; + data[off] = value; + return ret; + } + + @Override + public void destroy() { + data = null; + idmap = null; + } + + @Override + public void delete(DBID id) { + throw new UnsupportedOperationException("Can't delete from a static array storage."); + } + + @Override + public String getLongName() { + return "raw"; + } + + @Override + public String getShortName() { + return "raw"; + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayRecordStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayRecordStore.java index 507fe15b..7be68c97 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayRecordStore.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayRecordStore.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.datastore.memory; 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 @@ -33,8 +33,8 @@ import de.lmu.ifi.dbs.elki.database.ids.DBID; * * @author Erich Schubert * - * @apiviz.composedOf de.lmu.ifi.dbs.elki.database.datastore.DataStoreIDMap - * @apiviz.has de.lmu.ifi.dbs.elki.database.datastore.memory.ArrayRecordStore.StorageAccessor oneway - - projectsTo + * @apiviz.composedOf DataStoreIDMap + * @apiviz.has ArrayRecordStore.StorageAccessor oneway - - projectsTo */ public class ArrayRecordStore implements WritableRecordStore { /** diff --git a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayStore.java index 96cadddf..a41a444d 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayStore.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayStore.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.datastore.memory; 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/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDDoubleStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDDoubleStore.java new file mode 100644 index 00000000..ae06dc00 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDDoubleStore.java @@ -0,0 +1,98 @@ +package de.lmu.ifi.dbs.elki.database.datastore.memory; +/* + 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 gnu.trove.map.TIntDoubleMap; +import gnu.trove.map.hash.TIntDoubleHashMap; +import de.lmu.ifi.dbs.elki.database.datastore.WritableDoubleDataStore; +import de.lmu.ifi.dbs.elki.database.ids.DBID; + +/** + * Writable data store for double values. + * + * @author Erich Schubert + */ +public class MapIntegerDBIDDoubleStore implements WritableDoubleDataStore { + /** + * Data storage + */ + private TIntDoubleMap map; + + /** + * Constructor. + * + * @param size Expected size + */ + public MapIntegerDBIDDoubleStore(int size) { + super(); + map = new TIntDoubleHashMap(size, 0.5f, Integer.MIN_VALUE, Double.NaN); + } + + @Override + @Deprecated + public Double get(DBID id) { + return map.get(id.getIntegerID()); + } + + @Override + public double doubleValue(DBID id) { + return map.get(id.getIntegerID()); + } + + @Override + public String getLongName() { + return "raw"; + } + + @Override + public String getShortName() { + return "raw"; + } + + @Override + @Deprecated + public Double put(DBID id, Double value) { + return map.put(id.getIntegerID(), value); + } + + @Override + public void destroy() { + map.clear(); + map = null; + } + + @Override + public void delete(DBID id) { + map.remove(id.getIntegerID()); + } + + @Override + public double putDouble(DBID id, double value) { + return map.put(id.getIntegerID(), value); + } + + @Override + public double put(DBID id, double value) { + return map.put(id.getIntegerID(), value); + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDRecordStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDRecordStore.java new file mode 100644 index 00000000..8272fb2e --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDRecordStore.java @@ -0,0 +1,191 @@ +package de.lmu.ifi.dbs.elki.database.datastore.memory; + +/* + 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 gnu.trove.map.TIntObjectMap; +import gnu.trove.map.hash.TIntObjectHashMap; +import de.lmu.ifi.dbs.elki.database.datastore.WritableDataStore; +import de.lmu.ifi.dbs.elki.database.datastore.WritableRecordStore; +import de.lmu.ifi.dbs.elki.database.ids.DBID; + +/** + * A class to answer representation queries using a map and an index within the + * record. + * + * @author Erich Schubert + * + * @apiviz.has MapIntegerDBIDRecordStore.StorageAccessor oneway - - projectsTo + */ +public class MapIntegerDBIDRecordStore implements WritableRecordStore { + /** + * Record length + */ + private final int rlen; + + /** + * Storage Map + */ + private final TIntObjectMap<Object[]> data; + + /** + * Constructor with existing data. + * + * @param rlen Number of columns (record length) + * @param data Existing data map + */ + public MapIntegerDBIDRecordStore(int rlen, TIntObjectMap<Object[]> data) { + super(); + this.rlen = rlen; + this.data = data; + } + + /** + * Constructor without existing data. + * + * @param rlen Number of columns (record length) + */ + public MapIntegerDBIDRecordStore(int rlen) { + this(rlen, new TIntObjectHashMap<Object[]>()); + } + + /** + * Constructor without existing data. + * + * @param size Expected size + * @param rlen Number of columns (record length) + */ + public MapIntegerDBIDRecordStore(int size, int rlen) { + this(rlen, new TIntObjectHashMap<Object[]>(size)); + } + + @Override + public <T> WritableDataStore<T> getStorage(int col, Class<? super T> datatype) { + // TODO: add type checking? + return new StorageAccessor<T>(col); + } + + /** + * Actual getter + * + * @param id Database ID + * @param index column index + * @return current value + */ + @SuppressWarnings("unchecked") + protected <T> T get(DBID id, int index) { + Object[] d = data.get(id.getIntegerID()); + if(d == null) { + return null; + } + try { + return (T) d[index]; + } + catch(ClassCastException e) { + return null; + } + catch(ArrayIndexOutOfBoundsException e) { + return null; + } + } + + /** + * Actual setter + * + * @param id Database ID + * @param index column index + * @param value new value + * @return previous value + */ + @SuppressWarnings("unchecked") + protected <T> T set(DBID id, int index, T value) { + Object[] d = data.get(id.getIntegerID()); + if(d == null) { + d = new Object[rlen]; + data.put(id.getIntegerID(), d); + } + T ret = (T) d[index]; + d[index] = value; + return ret; + } + + /** + * Access a single record in the given data. + * + * @author Erich Schubert + * + * @param <T> Object data type to access + */ + protected class StorageAccessor<T> implements WritableDataStore<T> { + /** + * Representation index. + */ + private final int index; + + /** + * Constructor. + * + * @param index In-record index + */ + protected StorageAccessor(int index) { + super(); + this.index = index; + } + + @SuppressWarnings("unchecked") + @Override + public T get(DBID id) { + return (T) MapIntegerDBIDRecordStore.this.get(id, index); + } + + @Override + public T put(DBID id, T value) { + return MapIntegerDBIDRecordStore.this.set(id, index, value); + } + + @Override + public void destroy() { + throw new UnsupportedOperationException("Record storage accessors cannot be destroyed."); + } + + @Override + public void delete(DBID id) { + throw new UnsupportedOperationException("Record storage values cannot be deleted."); + } + + @Override + public String getLongName() { + return "raw"; + } + + @Override + public String getShortName() { + return "raw"; + } + } + + @Override + public boolean remove(DBID id) { + return data.remove(id.getIntegerID()) != null; + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDStore.java new file mode 100644 index 00000000..4deb929d --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDStore.java @@ -0,0 +1,104 @@ +package de.lmu.ifi.dbs.elki.database.datastore.memory; + +/* + 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 gnu.trove.map.TIntObjectMap; +import gnu.trove.map.hash.TIntObjectHashMap; +import de.lmu.ifi.dbs.elki.database.datastore.WritableDataStore; +import de.lmu.ifi.dbs.elki.database.ids.DBID; + +/** + * A class to answer representation queries using a map. Basically, it is just a + * wrapper around a regular map. + * + * @author Erich Schubert + * + * @param <T> Representation object type + */ +public class MapIntegerDBIDStore<T> implements WritableDataStore<T> { + /** + * Storage Map + */ + private TIntObjectMap<T> data; + + /** + * Constructor. + * + * @param data Existing map + */ + public MapIntegerDBIDStore(TIntObjectMap<T> data) { + super(); + this.data = data; + } + + /** + * Constructor. + */ + public MapIntegerDBIDStore() { + super(); + this.data = new TIntObjectHashMap<T>(); + } + + /** + * Constructor. + * + * @param size Expected size + */ + public MapIntegerDBIDStore(int size) { + this.data = new TIntObjectHashMap<T>(size); + } + + @Override + public T get(DBID id) { + return data.get(id.getIntegerID()); + } + + @Override + public T put(DBID id, T value) { + if(value == null) { + return data.remove(id.getIntegerID()); + } + return data.put(id.getIntegerID(), value); + } + + @Override + public void destroy() { + data = null; + } + + @Override + public void delete(DBID id) { + data.remove(id.getIntegerID()); + } + + @Override + public String getLongName() { + return "raw"; + } + + @Override + public String getShortName() { + return "raw"; + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapRecordStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapRecordStore.java index 31efc613..5a98966f 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapRecordStore.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapRecordStore.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.datastore.memory; 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 @@ -36,7 +36,7 @@ import de.lmu.ifi.dbs.elki.database.ids.DBID; * * @author Erich Schubert * - * @apiviz.has de.lmu.ifi.dbs.elki.database.datastore.memory.MapRecordStore.StorageAccessor oneway - - projectsTo + * @apiviz.has MapRecordStore.StorageAccessor oneway - - projectsTo */ public class MapRecordStore implements WritableRecordStore { /** diff --git a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapStore.java index e8a806ec..27cd9f63 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapStore.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapStore.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.datastore.memory; 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/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MemoryDataStoreFactory.java b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MemoryDataStoreFactory.java index 2c64ee55..3e3ce017 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MemoryDataStoreFactory.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MemoryDataStoreFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.datastore.memory; 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 @@ -26,14 +26,17 @@ package de.lmu.ifi.dbs.elki.database.datastore.memory; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory; import de.lmu.ifi.dbs.elki.database.datastore.RangeIDMap; import de.lmu.ifi.dbs.elki.database.datastore.WritableDataStore; +import de.lmu.ifi.dbs.elki.database.datastore.WritableDoubleDataStore; import de.lmu.ifi.dbs.elki.database.datastore.WritableRecordStore; import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; /** - * Simple factory class that will store all data in memory using object arrays or hashmaps. + * Simple factory class that will store all data in memory using object arrays + * or hashmaps. * - * Hints are currently not used by this implementation, since everything is in-memory. + * Hints are currently not used by this implementation, since everything is + * in-memory. * * @author Erich Schubert * @@ -46,23 +49,36 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDs; public class MemoryDataStoreFactory implements DataStoreFactory { @Override public <T> WritableDataStore<T> makeStorage(DBIDs ids, int hints, Class<? super T> dataclass) { - if (ids instanceof DBIDRange) { + if(ids instanceof DBIDRange) { DBIDRange range = (DBIDRange) ids; Object[] data = new Object[range.size()]; return new ArrayStore<T>(data, new RangeIDMap(range)); - } else { - return new MapStore<T>(); + } + else { + return new MapIntegerDBIDStore<T>(ids.size()); + } + } + + @Override + public WritableDoubleDataStore makeDoubleStorage(DBIDs ids, int hints) { + if(ids instanceof DBIDRange) { + DBIDRange range = (DBIDRange) ids; + return new ArrayDoubleStore(range.size(), new RangeIDMap(range)); + } + else { + return new MapIntegerDBIDDoubleStore(ids.size()); } } @Override public WritableRecordStore makeRecordStorage(DBIDs ids, int hints, Class<?>... dataclasses) { - if (ids instanceof DBIDRange) { + if(ids instanceof DBIDRange) { DBIDRange range = (DBIDRange) ids; Object[][] data = new Object[range.size()][dataclasses.length]; return new ArrayRecordStore(data, new RangeIDMap(range)); - } else { - return new MapRecordStore(dataclasses.length); + } + else { + return new MapIntegerDBIDRecordStore(ids.size(), dataclasses.length); } } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/package-info.java b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/package-info.java index c0f41618..6200bb46 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/package-info.java @@ -5,7 +5,7 @@ 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/src/de/lmu/ifi/dbs/elki/database/datastore/package-info.java b/src/de/lmu/ifi/dbs/elki/database/datastore/package-info.java index 02ef6f6c..dccd8d4e 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/package-info.java @@ -14,7 +14,7 @@ * <h2>How to use:</h2> * <pre>{@code * // Storage for the outlier score of each ID. - * final WritableDataStore<Double> scores = DataStoreFactory.FACTORY.makeStorage(ids, DataStoreFactory.HINT_STATIC, Double.class); + * final WritableDoubleDataStore scores = DataStoreFactory.FACTORY.makeDoubleStorage(ids, DataStoreFactory.HINT_STATIC); * }</pre> * * @apiviz.exclude datastore.memory @@ -23,7 +23,7 @@ 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/src/de/lmu/ifi/dbs/elki/database/ids/ArrayDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/ArrayDBIDs.java index 015d881a..13d6ea58 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/ArrayDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/ArrayDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; 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 @@ -23,20 +23,43 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.List; - /** * Interface for array based DBIDs. * * @author Erich Schubert */ -public interface ArrayDBIDs extends DBIDs, List<DBID> { +public interface ArrayDBIDs extends DBIDs { /** * Get the i'th entry (starting at 0) * * @param i Index * @return DBID of i'th entry. */ - // In List<DBID> which confuses the java compiler - /* public DBID get(int i); */ + public DBID get(int i); + + /** + * Iterable + * + * @return Iterator + */ + public DBIDIter iter(); + + /** + * Size of the DBID "collection". + * + * @return size + */ + public int size(); + + /** + * Search for the position of the given key, assuming that the data set is + * sorted. + * + * For keys not found, <code>-(1+insertion position)</code> is returned, as + * for Java {@link java.util.Collections#binarySearch} + * + * @param key Key to search for + * @return Offset of key + */ + public int binarySearch(DBID key); } diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/ArrayModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/ArrayModifiableDBIDs.java index 1320ba4e..e9a6c8e0 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/ArrayModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/ArrayModifiableDBIDs.java @@ -1,10 +1,12 @@ package de.lmu.ifi.dbs.elki.database.ids; +import java.util.Comparator; + /* 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 @@ -23,13 +25,38 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.List; - /** * Array-oriented implementation of a modifiable DBID collection. * * @author Erich Schubert */ -public interface ArrayModifiableDBIDs extends ModifiableDBIDs, ArrayDBIDs, List<DBID> { - // Empty interface +public interface ArrayModifiableDBIDs extends ModifiableDBIDs, ArrayDBIDs { + /** + * Sort the DBID set. + */ + void sort(); + + /** + * Sort the DBID set. + * + * @param comparator Comparator to use + */ + void sort(Comparator<? super DBID> comparator); + + /** + * Remove the i'th entry (starting at 0) + * + * @param i Index + * @return value removed + */ + public DBID remove(int i); + + /** + * Replace the i'th entry (starting at 0) + * + * @param i Index + * @param newval New value + * @return previous value + */ + public DBID set(int i, DBID newval); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/ArrayStaticDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/ArrayStaticDBIDs.java index 2cf0f030..a14eac0c 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/ArrayStaticDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/ArrayStaticDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; 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/src/de/lmu/ifi/dbs/elki/database/ids/DBID.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBID.java index 41e67c4e..1391b75b 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBID.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBID.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; 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 @@ -23,8 +23,6 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ - - /** * Database ID object. * @@ -39,7 +37,7 @@ package de.lmu.ifi.dbs.elki.database.ids; * * @apiviz.landmark */ -public interface DBID extends Comparable<DBID>, ArrayStaticDBIDs { +public interface DBID extends Comparable<DBID>, ArrayDBIDs { /** * Return the integer value of the object ID, if possible. * diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDFactory.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDFactory.java index cc5be115..f35f390b 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDFactory.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; 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 @@ -111,13 +111,6 @@ public interface DBIDFactory { public HashSetModifiableDBIDs newHashSet(); /** - * Make a new (modifiable) tree set of DBIDs. - * - * @return New tree set - */ - public TreeSetModifiableDBIDs newTreeSet(); - - /** * Make a new (modifiable) array of DBIDs. * * @param size Size hint @@ -134,14 +127,6 @@ public interface DBIDFactory { public HashSetModifiableDBIDs newHashSet(int size); /** - * Make a new (modifiable) tree set of DBIDs. - * - * @param size Size hint - * @return New tree set - */ - public TreeSetModifiableDBIDs newTreeSet(int size); - - /** * Make a new (modifiable) array of DBIDs. * * @param existing existing DBIDs to use @@ -158,14 +143,6 @@ public interface DBIDFactory { public HashSetModifiableDBIDs newHashSet(DBIDs existing); /** - * Make a new (modifiable) tree set of DBIDs. - * - * @param existing existing DBIDs to use - * @return New tree set - */ - public TreeSetModifiableDBIDs newTreeSet(DBIDs existing); - - /** * Get a serializer for DBIDs * * @return DBID serializer diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDIter.java new file mode 100644 index 00000000..a41284f4 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDIter.java @@ -0,0 +1,79 @@ +package de.lmu.ifi.dbs.elki.database.ids; + +/* + 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/>. + */ +/** + * Iterator for DBIDs. + * + * Important note: this iterator has a <em>significantly</em> different syntax + * and semantics than the Java iterators. It is much more aligned with C than + * with Java, but at the same time, the syntax is much more compatible with for + * loops. + * + * Usage example: <blockquote><code>{@code + * for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + * iter.getDBID(); + * } + * }</code></blockquote> + * + * We list some fundamental differences. + * <ul> + * <li>{@link DBIDIter#valid() iter.valid()} refers to the current element, + * {@code Iterator.next()} to the next.</li> + * <li>{@link DBIDIter#advance() iter.advance()} does not return an element. Use + * {@code get...} to access it.</li> + * <li>{@code DBIDIter.get...} do not advance the iterator.</li> + * </ul> + * + * @author Erich Schubert + */ +public interface DBIDIter { + /** + * Returns true if the iterator currently points to a valid object. + * + * @return a <code>boolean</code> value + */ + public boolean valid(); + + /** + * Moves the iterator forward to the next entry. + * + * @throws java.util.NoSuchElementException if the iterator is already + * exhausted + */ + public void advance(); + + /** + * Return the integer value of the object ID, if possible. + * + * @return integer id + */ + public int getIntegerID(); + + /** + * Get the current DBID. + * + * @return current DBID + */ + public DBID getDBID(); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDPair.java index fdaff560..8f03e279 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDPair.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDPair.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; 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/src/de/lmu/ifi/dbs/elki/database/ids/DBIDRange.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDRange.java index 4143c570..48a1f0ba 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDRange.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDRange.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; 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/src/de/lmu/ifi/dbs/elki/database/ids/DBIDUtil.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDUtil.java index 3a62c222..cd2bd4e0 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDUtil.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDUtil.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; 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 @@ -133,15 +133,6 @@ public final class DBIDUtil { } /** - * Make a new (modifiable) tree set of DBIDs. - * - * @return New tree set - */ - public static TreeSetModifiableDBIDs newTreeSet() { - return DBIDFactory.FACTORY.newTreeSet(); - } - - /** * Make a new (modifiable) array of DBIDs. * * @param size Size hint @@ -162,16 +153,6 @@ public final class DBIDUtil { } /** - * Make a new (modifiable) tree set of DBIDs. - * - * @param size Size hint - * @return New tree set - */ - public static TreeSetModifiableDBIDs newTreeSet(int size) { - return DBIDFactory.FACTORY.newTreeSet(size); - } - - /** * Make a new (modifiable) array of DBIDs. * * @param existing Existing DBIDs @@ -192,16 +173,6 @@ public final class DBIDUtil { } /** - * Make a new (modifiable) tree set of DBIDs. - * - * @param existing Existing DBIDs - * @return New tree set - */ - public static TreeSetModifiableDBIDs newTreeSet(DBIDs existing) { - return DBIDFactory.FACTORY.newTreeSet(existing); - } - - /** * Compute the set intersection of two sets. * * @param first First set @@ -285,11 +256,8 @@ public final class DBIDUtil { * @return Array DBIDs. */ public static SetDBIDs ensureSet(DBIDs ids) { - if(ids instanceof HashSetDBIDs) { - return (HashSetDBIDs) ids; - } - else if(ids instanceof TreeSetDBIDs) { - return (TreeSetDBIDs) ids; + if(ids instanceof SetDBIDs) { + return (SetDBIDs) ids; } else { return newHashSet(ids); @@ -313,9 +281,6 @@ public final class DBIDUtil { if(ids instanceof HashSetDBIDs) { return newHashSet(ids); } - if(ids instanceof TreeSetDBIDs) { - return newTreeSet(ids); - } return newArray(ids); } } @@ -340,11 +305,29 @@ public final class DBIDUtil { * @param seed Random generator seed * @return new DBIDs */ - public static ModifiableDBIDs randomSample(DBIDs source, int k, long seed) { + public static ModifiableDBIDs randomSample(DBIDs source, int k, int seed) { + return randomSample(source, k, (long) seed); + } + + /** + * Produce a random sample of the given DBIDs + * + * @param source Original DBIDs + * @param k k Parameter + * @param seed Random generator seed + * @return new DBIDs + */ + public static ModifiableDBIDs randomSample(DBIDs source, int k, Long seed) { if(k <= 0 || k > source.size()) { throw new IllegalArgumentException("Illegal value for size of random sample: " + k); } - Random random = new Random(seed); + final Random random; + if(seed != null) { + random = new Random(seed); + } + else { + random = new Random(); + } // TODO: better balancing for different sizes // Two methods: constructive vs. destructive if(k < source.size() / 2) { diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDs.java index c1a52d6a..ef83ba69 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; 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 @@ -23,7 +23,6 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collection; import java.util.Iterator; /** @@ -36,13 +35,6 @@ import java.util.Iterator; */ public interface DBIDs extends Iterable<DBID> { /** - * Retrieve collection access to the IDs - * - * @return a collection of IDs - */ - public Collection<DBID> asCollection(); - - /** * Retrieve Iterator access to the IDs. * * @return an iterator for the IDs @@ -51,20 +43,26 @@ public interface DBIDs extends Iterable<DBID> { public Iterator<DBID> iterator(); /** + * Get a DBIDIterator (a more efficient API). + * + * @return iterator + */ + public DBIDIter iter(); + + /** * Retrieve the collection / data size. * * @return collection size */ public int size(); - + /** * Test whether an ID is contained. - * Signature compatible with {@link Collection}. * * @param o object to test * @return true when contained */ - public boolean contains(Object o); + public boolean contains(DBID o); /** * Test for an empty DBID collection. diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/EmptyDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/EmptyDBIDs.java index bee2faab..5a7d6991 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/EmptyDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/EmptyDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; 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 @@ -23,10 +23,8 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.AbstractList; -import java.util.ArrayList; -import java.util.Collection; import java.util.Iterator; +import java.util.NoSuchElementException; import de.lmu.ifi.dbs.elki.utilities.iterator.EmptyIterator; @@ -35,14 +33,21 @@ import de.lmu.ifi.dbs.elki.utilities.iterator.EmptyIterator; * * @author Erich Schubert */ -class EmptyDBIDs extends AbstractList<DBID> implements ArrayStaticDBIDs { - @Override - public Collection<DBID> asCollection() { - return new ArrayList<DBID>(0); +public class EmptyDBIDs implements ArrayStaticDBIDs, SetDBIDs { + /** + * Empty DBID iterator + */ + public static final EmptyDBIDIterator EMPTY_ITERATOR = new EmptyDBIDIterator(); + + /** + * Constructor. + */ + protected EmptyDBIDs() { + super(); } @Override - public boolean contains(Object o) { + public boolean contains(DBID o) { return false; } @@ -65,4 +70,41 @@ class EmptyDBIDs extends AbstractList<DBID> implements ArrayStaticDBIDs { public DBID get(int i) { throw new ArrayIndexOutOfBoundsException(); } + + @Override + public DBIDIter iter() { + return EMPTY_ITERATOR; + } + + @Override + public int binarySearch(DBID key) { + return -1; // Not found + } + + /** + * Iterator for empty DBIDs + * + * @author Erich Schubert + */ + protected static class EmptyDBIDIterator implements DBIDIter { + @Override + public boolean valid() { + return false; + } + + @Override + public void advance() { + assert (false) : "Misplaced call to advance()"; + } + + @Override + public int getIntegerID() { + throw new NoSuchElementException(); + } + + @Override + public DBID getDBID() { + throw new NoSuchElementException(); + } + } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/HashSetDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/HashSetDBIDs.java index f449180f..5ff0bc97 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/HashSetDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/HashSetDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; 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/src/de/lmu/ifi/dbs/elki/database/ids/HashSetModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/HashSetModifiableDBIDs.java index 03805590..f7c8b551 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/HashSetModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/HashSetModifiableDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; 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 @@ -23,14 +23,12 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Set; - /** * Set-oriented implementation of a modifiable DBID collection. * * @author Erich Schubert */ -public interface HashSetModifiableDBIDs extends Set<DBID>, HashSetDBIDs, ModifiableDBIDs { +public interface HashSetModifiableDBIDs extends HashSetDBIDs, ModifiableDBIDs { /** * Retain all elements that also are in the second set. * diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/ModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/ModifiableDBIDs.java index 57d8c578..97646902 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/ModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/ModifiableDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; 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 @@ -23,14 +23,16 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collection; - /** * Interface for a generic modifiable DBID collection. * + * Note: we had this use the Java Collections API for a long time, however this + * prevented certain optimizations. So it now only mimics the Collections API + * <em>deliberately</em>. + * * @author Erich Schubert */ -public interface ModifiableDBIDs extends DBIDs, Collection<DBID> { +public interface ModifiableDBIDs extends DBIDs { /** * Add DBIDs to collection. * @@ -38,7 +40,7 @@ public interface ModifiableDBIDs extends DBIDs, Collection<DBID> { * @return {@code true} when modified */ boolean addDBIDs(DBIDs ids); - + /** * Remove DBIDs from collection. * @@ -46,4 +48,23 @@ public interface ModifiableDBIDs extends DBIDs, Collection<DBID> { * @return {@code true} when modified */ boolean removeDBIDs(DBIDs ids); -} + + /** + * Add a single DBID to the collection. + * + * @param id ID to add + */ + boolean add(DBID id); + + /** + * Remove a single DBID from the collection. + * + * @param id ID to remove + */ + boolean remove(DBID id); + + /** + * Clear this collection. + */ + void clear(); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/SetDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/SetDBIDs.java index 6509a57f..7fd28326 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/SetDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/SetDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; 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 @@ -23,7 +23,6 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Set; /** * Interface for DBIDs that support fast "set" operations, in particular @@ -31,6 +30,6 @@ import java.util.Set; * * @author Erich Schubert */ -public interface SetDBIDs extends DBIDs, Set<DBID> { +public interface SetDBIDs extends DBIDs { // empty marker interface }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/StaticDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/StaticDBIDs.java index 08676215..ce616da3 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/StaticDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/StaticDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; 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/src/de/lmu/ifi/dbs/elki/database/ids/generic/DBIDIterAdapter.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/DBIDIterAdapter.java new file mode 100644 index 00000000..c517ea9f --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/generic/DBIDIterAdapter.java @@ -0,0 +1,82 @@ +package de.lmu.ifi.dbs.elki.database.ids.generic; + +import java.util.Iterator; + +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; + +/* + 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/>. + */ + +/** + * Iterator for classic collections. + * + * @author Erich Schubert + */ +public class DBIDIterAdapter implements DBIDIter { + /** + * Current DBID + */ + DBID cur = null; + + /** + * The real iterator + */ + Iterator<DBID> iter; + + /** + * Constructor. + * + * @param iter Iterator + */ + public DBIDIterAdapter(Iterator<DBID> iter) { + super(); + this.iter = iter; + advance(); + } + + @Override + public boolean valid() { + return cur != null; + } + + @Override + public void advance() { + if(iter.hasNext()) { + cur = iter.next(); + } + else { + cur = null; + } + } + + @Override + public int getIntegerID() { + return cur.getIntegerID(); + } + + @Override + public DBID getDBID() { + return cur; + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericArrayModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericArrayModifiableDBIDs.java index 0316f82d..f271180d 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericArrayModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericArrayModifiableDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; 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 @@ -24,26 +24,27 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; */ import java.util.ArrayList; -import java.util.Collection; +import java.util.Collections; +import java.util.Comparator; import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; - /** * Array-oriented implementation of a modifiable DBID collection. * - * This should only be instantiated by a {@link de.lmu.ifi.dbs.elki.database.ids.DBIDFactory}! + * This should only be instantiated by a + * {@link de.lmu.ifi.dbs.elki.database.ids.DBIDFactory}! * * Use {@link de.lmu.ifi.dbs.elki.database.ids.DBIDUtil#newArray}! * * @author Erich Schubert * - * @apiviz.uses de.lmu.ifi.dbs.elki.database.ids.DBID + * @apiviz.uses DBID */ -// TODO: implement this optimized for integers? -public class GenericArrayModifiableDBIDs extends ArrayList<DBID> implements ArrayModifiableDBIDs { +public class GenericArrayModifiableDBIDs extends ArrayList<DBID> implements ArrayModifiableDBIDs { /** * Serial version */ @@ -71,21 +72,56 @@ public class GenericArrayModifiableDBIDs extends ArrayList<DBID> implements Arra * @param c Existing DBIDs. */ public GenericArrayModifiableDBIDs(DBIDs c) { - super(c.asCollection()); + super(c.size()); + addDBIDs(c); } @Override - public Collection<DBID> asCollection() { - return this; + public boolean addDBIDs(DBIDs ids) { + super.ensureCapacity(size() + ids.size()); + boolean changed = false; + for(DBID id : ids) { + changed |= add(id); + } + return changed; } @Override - public boolean addDBIDs(DBIDs ids) { - return super.addAll(ids.asCollection()); + public boolean removeDBIDs(DBIDs ids) { + boolean changed = false; + for(DBID id : ids) { + changed |= super.remove(id); + } + return changed; } @Override - public boolean removeDBIDs(DBIDs ids) { - return super.removeAll(ids.asCollection()); + public boolean remove(DBID id) { + return super.remove(id); + } + + @Override + public void sort() { + Collections.sort(this); + } + + @Override + public void sort(Comparator<? super DBID> comparator) { + Collections.sort(this, comparator); + } + + @Override + public DBIDIter iter() { + return new DBIDIterAdapter(iterator()); + } + + @Override + public int binarySearch(DBID key) { + return Collections.binarySearch(this, key); + } + + @Override + public boolean contains(DBID o) { + return super.contains(o); } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericHashSetModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericHashSetModifiableDBIDs.java index 6d251cd8..31a8602c 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericHashSetModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericHashSetModifiableDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; 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 @@ -23,25 +23,26 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collection; import java.util.HashSet; +import java.util.Iterator; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; /** * Set-oriented implementation of a modifiable DBID collection. * - * This should only be instantiated by a {@link de.lmu.ifi.dbs.elki.database.ids.DBIDFactory}! + * This should only be instantiated by a + * {@link de.lmu.ifi.dbs.elki.database.ids.DBIDFactory}! * * Use {@link de.lmu.ifi.dbs.elki.database.ids.DBIDUtil#newHashSet}! * * @author Erich Schubert * - * @apiviz.uses de.lmu.ifi.dbs.elki.database.ids.DBID + * @apiviz.uses DBID */ -// TODO: implement this optimized for integers? public class GenericHashSetModifiableDBIDs extends HashSet<DBID> implements HashSetModifiableDBIDs { /** * Serial version @@ -70,26 +71,55 @@ public class GenericHashSetModifiableDBIDs extends HashSet<DBID> implements Hash * @param c Existing DBIDs. */ public GenericHashSetModifiableDBIDs(DBIDs c) { - super(c.asCollection()); + super(c.size()); + for(DBID id : c) { + add(id); + } } @Override - public Collection<DBID> asCollection() { - return this; + public boolean addDBIDs(DBIDs ids) { + boolean changed = false; + for(DBID id : ids) { + changed |= add(id); + } + return changed; } @Override - public boolean addDBIDs(DBIDs ids) { - return super.addAll(ids.asCollection()); + public boolean removeDBIDs(DBIDs ids) { + boolean changed = false; + for(DBID id : ids) { + changed |= super.remove(id); + } + return changed; } @Override - public boolean removeDBIDs(DBIDs ids) { - return super.removeAll(ids.asCollection()); + public boolean remove(DBID id) { + return super.remove(id); } @Override public boolean retainAll(DBIDs ids) { - return super.retainAll(ids.asCollection()); + boolean modified = false; + Iterator<DBID> it = iterator(); + while(it.hasNext()) { + if(!ids.contains(it.next())) { + it.remove(); + modified = true; + } + } + return modified; + } + + @Override + public DBIDIter iter() { + return new DBIDIterAdapter(iterator()); + } + + @Override + public boolean contains(DBID o) { + return super.contains(o); } -} +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericTreeSetModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericTreeSetModifiableDBIDs.java deleted file mode 100644 index afd56730..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericTreeSetModifiableDBIDs.java +++ /dev/null @@ -1,90 +0,0 @@ -package de.lmu.ifi.dbs.elki.database.ids.generic; - -/* - 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 java.util.Collection; -import java.util.TreeSet; - -import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.DBIDs; -import de.lmu.ifi.dbs.elki.database.ids.TreeSetModifiableDBIDs; - -/** - * Set-oriented implementation of a modifiable DBID collection. - * - * This should only be instantiated by a {@link de.lmu.ifi.dbs.elki.database.ids.DBIDFactory}! - * - * Use {@link de.lmu.ifi.dbs.elki.database.ids.DBIDUtil#newTreeSet}! - * - * @author Erich Schubert - * - * @apiviz.uses de.lmu.ifi.dbs.elki.database.ids.DBID - */ -// TODO: implement this optimized for integers? -public class GenericTreeSetModifiableDBIDs extends TreeSet<DBID> implements TreeSetModifiableDBIDs { - /** - * Serial version - */ - private static final long serialVersionUID = 1L; - - /** - * Constructor with size hint. - * - * @param initialCapacity Size hint - */ - public GenericTreeSetModifiableDBIDs(int initialCapacity) { - super(); - } - - /** - * Constructor without extra hints - */ - public GenericTreeSetModifiableDBIDs() { - super(); - } - - /** - * Constructor from existing DBIDs. - * - * @param c Existing DBIDs. - */ - public GenericTreeSetModifiableDBIDs(DBIDs c) { - super(c.asCollection()); - } - - @Override - public Collection<DBID> asCollection() { - return this; - } - - @Override - public boolean addDBIDs(DBIDs ids) { - return super.addAll(ids.asCollection()); - } - - @Override - public boolean removeDBIDs(DBIDs ids) { - return super.removeAll(ids.asCollection()); - } -} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/MaskedDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/MaskedDBIDs.java index 77d5c063..67c84290 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/MaskedDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/generic/MaskedDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; 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 @@ -23,13 +23,12 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.AbstractCollection; import java.util.BitSet; -import java.util.Collection; import java.util.Iterator; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; /** @@ -39,7 +38,7 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDs; * * @apiviz.uses de.lmu.ifi.dbs.elki.database.ids.DBIDs */ -public class MaskedDBIDs extends AbstractCollection<DBID> implements DBIDs, Collection<DBID> { +public class MaskedDBIDs implements DBIDs { /** * Data storage */ @@ -80,8 +79,13 @@ public class MaskedDBIDs extends AbstractCollection<DBID> implements DBIDs, Coll } @Override - public Collection<DBID> asCollection() { - return this; + public DBIDIter iter() { + if(inverse) { + return new InvDBIDItr(); + } + else { + return new DBIDItr(); + } } @Override @@ -94,6 +98,22 @@ public class MaskedDBIDs extends AbstractCollection<DBID> implements DBIDs, Coll } } + @Override + public boolean contains(DBID o) { + // TODO: optimize. + for(DBID id : this) { + if(id.equals(o)) { + return true; + } + } + return false; + } + + @Override + public boolean isEmpty() { + return size() == 0; + } + /** * Iterator over set bits * @@ -133,6 +153,47 @@ public class MaskedDBIDs extends AbstractCollection<DBID> implements DBIDs, Coll } /** + * Iterator over set bits + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected class DBIDItr implements DBIDIter { + /** + * Next position. + */ + private int pos; + + /** + * Constructor + */ + protected DBIDItr() { + this.pos = bits.nextSetBit(0); + } + + @Override + public boolean valid() { + return pos >= 0; + } + + @Override + public void advance() { + pos = bits.nextSetBit(pos + 1); + } + + @Override + public int getIntegerID() { + return data.get(pos).getIntegerID(); + } + + @Override + public DBID getDBID() { + return data.get(pos); + } + } + + /** * Iterator over unset elements. * * @author Erich Schubert @@ -170,18 +231,44 @@ public class MaskedDBIDs extends AbstractCollection<DBID> implements DBIDs, Coll } } - @Override - public boolean add(DBID e) { - throw new UnsupportedOperationException(); - } + /** + * Iterator over set bits + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected class InvDBIDItr implements DBIDIter { + /** + * Next position. + */ + private int pos; - @Override - public boolean remove(Object o) { - throw new UnsupportedOperationException(); - } + /** + * Constructor + */ + protected InvDBIDItr() { + this.pos = bits.nextClearBit(0); + } - @Override - public void clear() { - throw new UnsupportedOperationException(); + @Override + public boolean valid() { + return pos >= 0; + } + + @Override + public void advance() { + pos = bits.nextClearBit(pos + 1); + } + + @Override + public int getIntegerID() { + return data.get(pos).getIntegerID(); + } + + @Override + public DBID getDBID() { + return data.get(pos); + } } } diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/MergedDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/MergedDBIDs.java index ce28ac38..97743867 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/MergedDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/generic/MergedDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; 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 @@ -23,12 +23,12 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collection; import java.util.Iterator; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; - +import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; /** * Merge the IDs of multiple layers into one. @@ -38,12 +38,12 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDs; * @apiviz.uses de.lmu.ifi.dbs.elki.database.ids.DBIDs */ // TODO: include ID mapping? -public class MergedDBIDs implements DBIDs, Collection<DBID> { +public class MergedDBIDs implements DBIDs { /** * Childs to merge */ DBIDs childs[]; - + /** * Constructor. * @@ -55,14 +55,13 @@ public class MergedDBIDs implements DBIDs, Collection<DBID> { } @Override - public Collection<DBID> asCollection() { - return this; + public Iterator<DBID> iterator() { + throw new AbortException("Merged iterators not completely implemented yet!"); } @Override - public Iterator<DBID> iterator() { - // TODO Auto-generated method stub - return null; + public DBIDIter iter() { + throw new AbortException("Merged iterators not completely implemented yet!"); } @Override @@ -80,32 +79,7 @@ public class MergedDBIDs implements DBIDs, Collection<DBID> { } @Override - public Object[] toArray() { - return toArray(new Object[size()]); - } - - @SuppressWarnings("unchecked") - @Override - public <T> T[] toArray(T[] a) { - final int si = size(); - T[] r = a; - if(a.length < si) { - r = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), si); - } - int i = 0; - for (Iterator<DBID> iter = iterator(); iter.hasNext(); i++) { - DBID id = iter.next(); - r[i] = (T) id; - } - // zero-terminate array - if(r.length > si) { - r[si] = null; - } - return r; - } - - @Override - public boolean contains(Object o) { + public boolean contains(DBID o) { for(DBIDs child : childs) { if(child.contains(o)) { return true; @@ -113,45 +87,4 @@ public class MergedDBIDs implements DBIDs, Collection<DBID> { } return false; } - - @Override - public boolean containsAll(Collection<?> c) { - Iterator<?> e = c.iterator(); - while(e.hasNext()) { - if(!contains(e.next())) { - return false; - } - } - return true; - } - - @Override - public void clear() { - throw new UnsupportedOperationException(MergedDBIDs.class.getName() + " are unmodifiable!"); - } - - @Override - public boolean add(DBID e) { - throw new UnsupportedOperationException(MergedDBIDs.class.getName() + " are unmodifiable!"); - } - - @Override - public boolean addAll(Collection<? extends DBID> c) { - throw new UnsupportedOperationException(MergedDBIDs.class.getName() + " are unmodifiable!"); - } - - @Override - public boolean remove(Object o) { - throw new UnsupportedOperationException(MergedDBIDs.class.getName() + " are unmodifiable!"); - } - - @Override - public boolean removeAll(Collection<?> c) { - throw new UnsupportedOperationException(MergedDBIDs.class.getName() + " are unmodifiable!"); - } - - @Override - public boolean retainAll(Collection<?> c) { - throw new UnsupportedOperationException(MergedDBIDs.class.getName() + " are unmodifiable!"); - } -} +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/UnmodifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/UnmodifiableDBIDs.java index 908dabd3..bd68e2fb 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/UnmodifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/generic/UnmodifiableDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; 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 @@ -23,11 +23,10 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collection; -import java.util.Collections; import java.util.Iterator; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.StaticDBIDs; import de.lmu.ifi.dbs.elki.utilities.iterator.UnmodifiableIterator; @@ -56,12 +55,7 @@ public class UnmodifiableDBIDs implements StaticDBIDs { } @Override - public Collection<DBID> asCollection() { - return Collections.unmodifiableCollection(inner.asCollection()); - } - - @Override - public boolean contains(Object o) { + public boolean contains(DBID o) { return inner.contains(o); } @@ -74,6 +68,11 @@ public class UnmodifiableDBIDs implements StaticDBIDs { public Iterator<DBID> iterator() { return new UnmodifiableIterator<DBID>(inner.iterator()); } + + @Override + public DBIDIter iter() { + return inner.iter(); + } @Override public int size() { diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/package-info.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/package-info.java index cdf4c487..890b9c0a 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/generic/package-info.java @@ -7,7 +7,7 @@ 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/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayStaticDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayStaticDBIDs.java index b617b4c4..ef4aee94 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayStaticDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayStaticDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; 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 @@ -24,22 +24,22 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; */ import java.util.AbstractList; -import java.util.Collection; +import java.util.Arrays; import java.util.Iterator; -import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.ArrayStaticDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; - +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; /** * Static (no modifications allowed) set of Database Object IDs. * * @author Erich Schubert * - * @apiviz.composedOf IntegerDBID + * @apiviz.has IntegerDBID */ -public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements ArrayDBIDs { +public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements ArrayStaticDBIDs { /** * The actual storage. */ @@ -59,7 +59,12 @@ public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements Array public Iterator<DBID> iterator() { return new Itr(); } - + + @Override + public DBIDIter iter() { + return new DBIDItr(); + } + /** * Iterator class. * @@ -77,7 +82,7 @@ public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements Array @Override public DBID next() { - DBID ret = DBIDFactory.FACTORY.importInteger(ids[off]); + DBID ret = new IntegerDBID(ids[off]); off++; return ret; } @@ -88,22 +93,49 @@ public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements Array } } + /** + * DBID iterator in ELKI/C style. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected class DBIDItr implements DBIDIter { + int pos = 0; + + @Override + public boolean valid() { + return pos < ids.length; + } + + @Override + public void advance() { + pos++; + } + + @Override + public int getIntegerID() { + return ids[pos]; + } + + @Override + public DBID getDBID() { + return new IntegerDBID(ids[pos]); + } + + } + @Override public int size() { return ids.length; } - - /* - * "Contains" operations - */ + @Override - public boolean contains(Object o) { - if(o instanceof DBID) { - int oid = ((DBID) o).getIntegerID(); - for(int i = 0; i < ids.length; i++) { - if(ids[i] == oid) { - return true; - } + public boolean contains(DBID o) { + final int oid = o.getIntegerID(); + for(int i = 0; i < ids.length; i++) { + if(ids[i] == oid) { + return true; } } return false; @@ -132,7 +164,7 @@ public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements Array } @Override - public Collection<DBID> asCollection() { - return this; + public int binarySearch(DBID key) { + return Arrays.binarySearch(ids, key.getIntegerID()); } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java index 2842ca75..f9e83294 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; 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 @@ -24,11 +24,10 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; */ import java.nio.ByteBuffer; -import java.util.AbstractList; -import java.util.Collection; import java.util.Iterator; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.persistent.ByteArrayUtil; import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; @@ -50,7 +49,7 @@ import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; * @apiviz.composedOf DynamicSerializer * @apiviz.composedOf StaticSerializer */ -class IntegerDBID extends AbstractList<DBID> implements DBID { +class IntegerDBID implements DBID { /** * The actual object ID. */ @@ -113,13 +112,16 @@ class IntegerDBID extends AbstractList<DBID> implements DBID { } @Override - public Collection<DBID> asCollection() { - return this; + public DBIDIter iter() { + return new DBIDItr(); } @Override - public boolean contains(Object o) { - return this.equals(o); + public DBID get(int i) { + if(i != 0) { + throw new ArrayIndexOutOfBoundsException(); + } + return this; } @Override @@ -128,10 +130,20 @@ class IntegerDBID extends AbstractList<DBID> implements DBID { } @Override + public boolean contains(DBID o) { + return o.getIntegerID() == id; + } + + @Override public int size() { return 1; } + @Override + public int binarySearch(DBID key) { + return equals(key) ? 0 : -1; + } + /** * Pseudo iterator for DBIDs interface. * @@ -163,21 +175,45 @@ class IntegerDBID extends AbstractList<DBID> implements DBID { } } - @Override - public boolean isEmpty() { - return false; - } + /** + * Pseudo iterator for DBIDs interface. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected class DBIDItr implements DBIDIter { + /** + * Whether we've already returned our object. + */ + boolean first = true; - @Override - public DBID get(int i) { - if(i == 0) { - return this; + @Override + public void advance() { + first = false; } - else { - throw new ArrayIndexOutOfBoundsException(); + + @Override + public int getIntegerID() { + return id; + } + + @Override + public DBID getDBID() { + return IntegerDBID.this; + } + + @Override + public boolean valid() { + return first; } } + @Override + public boolean isEmpty() { + return false; + } + /** * Dynamic sized serializer, using varint. * diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDPair.java index 742bab57..e716f5b5 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDPair.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDPair.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; 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 de.lmu.ifi.dbs.elki.database.ids.DBIDPair; * * @author Erich Schubert * - * @apiviz.composedOf IntegerDBID + * @apiviz.has IntegerDBID */ public class IntegerDBIDPair implements DBIDPair { /** diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java index 1142f1a6..debe39a4 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; 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 @@ -24,32 +24,31 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; */ import java.util.AbstractList; -import java.util.Collection; import java.util.Iterator; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; - /** * Representing a DBID range allocation * * @author Erich Schubert * - * @apiviz.composedOf IntegerDBID + * @apiviz.has IntegerDBID */ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { /** * Start value */ protected final int start; - + /** * Length value */ protected final int len; - + /** * Constructor. * @@ -72,6 +71,11 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { return new Itr(); } + @Override + public DBIDIter iter() { + return new DBIDItr(); + } + /** * Iterator class. * @@ -89,7 +93,7 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { @Override public DBID next() { - DBID ret = DBIDFactory.FACTORY.importInteger(pos + start); + DBID ret = new IntegerDBID(pos + start); pos++; return ret; } @@ -100,22 +104,48 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { } } - /* - * "Contains" operations + /** + * Iterator in ELKI/C++ style. + * + * @author Erich Schubert + * + * @apiviz.exclude */ + protected class DBIDItr implements DBIDIter { + int pos = 0; + + @Override + public boolean valid() { + return pos < len; + } + + @Override + public void advance() { + pos++; + } + + @Override + public int getIntegerID() { + return start + pos; + } + + @Override + public DBID getDBID() { + return new IntegerDBID(start + pos); + } + + } + @Override - public boolean contains(Object o) { - if(o instanceof DBID) { - int oid = ((DBID) o).getIntegerID(); - if(oid < start) { - return false; - } - if(oid >= start + len) { - return false; - } - return true; + public boolean contains(DBID o) { + int oid = o.getIntegerID(); + if(oid < start) { + return false; } - return false; + if(oid >= start + len) { + return false; + } + return true; } @SuppressWarnings("unchecked") @@ -137,11 +167,11 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { @Override public DBID get(int i) { - if (i > len || i < 0) { + if(i > len || i < 0) { throw new ArrayIndexOutOfBoundsException(); } return DBIDFactory.FACTORY.importInteger(start + i); - } + } /** * For storage array offsets. @@ -155,7 +185,15 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { } @Override - public Collection<DBID> asCollection() { - return this; + public int binarySearch(DBID key) { + int keyid = key.getIntegerID(); + if(keyid < start) { + return -1; + } + final int off = keyid - start; + if(off < len) { + return off; + } + return -(len + 1); } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/ReusingDBIDFactory.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/ReusingDBIDFactory.java index 8e4600db..01e42fe9 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/ReusingDBIDFactory.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/ReusingDBIDFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; 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/src/de/lmu/ifi/dbs/elki/database/ids/integer/SimpleDBIDFactory.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/SimpleDBIDFactory.java index 3348701e..59fa34b5 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/SimpleDBIDFactory.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/SimpleDBIDFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; 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,21 +27,17 @@ import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; import de.lmu.ifi.dbs.elki.database.ids.DBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; -import de.lmu.ifi.dbs.elki.database.ids.TreeSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericArrayModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericHashSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericTreeSetModifiableDBIDs; import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; /** - * Simple DBID management, that never reuses IDs. - * Statically allocated DBID ranges are given positive values, - * Dynamically allocated DBIDs are given negative values. + * Simple DBID management, that never reuses IDs. Statically allocated DBID + * ranges are given positive values, Dynamically allocated DBIDs are given + * negative values. * * @author Erich Schubert * @@ -50,21 +46,20 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; * @apiviz.uses IntegerDBID oneway - - «create» * @apiviz.uses IntegerDBIDPair oneway - - «create» * @apiviz.uses IntegerDBIDRange oneway - - «create» - * @apiviz.uses GenericArrayModifiableDBIDs oneway - - «create» - * @apiviz.uses GenericHashSetModifiableDBIDs oneway - - «create» - * @apiviz.uses GenericTreeSetModifiableDBIDs oneway - - «create» + * @apiviz.uses TroveArrayModifiableDBIDs oneway - - «create» + * @apiviz.uses TroveHashSetModifiableDBIDs oneway - - «create» */ public class SimpleDBIDFactory implements DBIDFactory { /** * Keep track of the smallest dynamic DBID offset not used */ int dynamicids = 0; - + /** * The starting point for static DBID range allocations. */ int rangestart = 0; - + /** * Constructor */ @@ -74,7 +69,7 @@ public class SimpleDBIDFactory implements DBIDFactory { @Override public synchronized DBID generateSingleDBID() { - if (dynamicids == Integer.MIN_VALUE) { + if(dynamicids == Integer.MIN_VALUE) { throw new AbortException("DBID range allocation error - too many objects allocated!"); } dynamicids--; @@ -88,7 +83,7 @@ public class SimpleDBIDFactory implements DBIDFactory { @Override public synchronized DBIDRange generateStaticDBIDRange(int size) { - if (rangestart >= Integer.MAX_VALUE - size) { + if(rangestart >= Integer.MAX_VALUE - size) { throw new AbortException("DBID range allocation error - too many objects allocated!"); } DBIDRange alloc = new IntegerDBIDRange(rangestart, size); @@ -108,47 +103,32 @@ public class SimpleDBIDFactory implements DBIDFactory { @Override public ArrayModifiableDBIDs newArray() { - return new GenericArrayModifiableDBIDs(); + return new TroveArrayModifiableDBIDs(); } @Override public HashSetModifiableDBIDs newHashSet() { - return new GenericHashSetModifiableDBIDs(); - } - - @Override - public TreeSetModifiableDBIDs newTreeSet() { - return new GenericTreeSetModifiableDBIDs(); + return new TroveHashSetModifiableDBIDs(); } @Override public ArrayModifiableDBIDs newArray(int size) { - return new GenericArrayModifiableDBIDs(size); + return new TroveArrayModifiableDBIDs(size); } @Override public HashSetModifiableDBIDs newHashSet(int size) { - return new GenericHashSetModifiableDBIDs(size); - } - - @Override - public TreeSetModifiableDBIDs newTreeSet(int size) { - return new GenericTreeSetModifiableDBIDs(size); + return new TroveHashSetModifiableDBIDs(size); } @Override public ArrayModifiableDBIDs newArray(DBIDs existing) { - return new GenericArrayModifiableDBIDs(existing); + return new TroveArrayModifiableDBIDs(existing); } @Override public HashSetModifiableDBIDs newHashSet(DBIDs existing) { - return new GenericHashSetModifiableDBIDs(existing); - } - - @Override - public TreeSetModifiableDBIDs newTreeSet(DBIDs existing) { - return new GenericTreeSetModifiableDBIDs(existing); + return new TroveHashSetModifiableDBIDs(existing); } @Override diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TrivialDBIDFactory.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TrivialDBIDFactory.java index ee49e2f1..b38286fe 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TrivialDBIDFactory.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TrivialDBIDFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; 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,13 +29,9 @@ import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; import de.lmu.ifi.dbs.elki.database.ids.DBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; -import de.lmu.ifi.dbs.elki.database.ids.TreeSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericArrayModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericHashSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericTreeSetModifiableDBIDs; import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; @@ -52,9 +48,8 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; * @apiviz.uses IntegerDBID oneway - - «create» * @apiviz.uses IntegerDBIDPair oneway - - «create» * @apiviz.uses IntegerDBIDRange oneway - - «create» - * @apiviz.uses GenericArrayModifiableDBIDs oneway - - «create» - * @apiviz.uses GenericHashSetModifiableDBIDs oneway - - «create» - * @apiviz.uses GenericTreeSetModifiableDBIDs oneway - - «create» + * @apiviz.uses TroveArrayModifiableDBIDs oneway - - «create» + * @apiviz.uses TroveHashSetModifiableDBIDs oneway - - «create» */ public class TrivialDBIDFactory implements DBIDFactory { /** @@ -106,47 +101,32 @@ public class TrivialDBIDFactory implements DBIDFactory { @Override public ArrayModifiableDBIDs newArray() { - return new GenericArrayModifiableDBIDs(); + return new TroveArrayModifiableDBIDs(); } @Override public HashSetModifiableDBIDs newHashSet() { - return new GenericHashSetModifiableDBIDs(); - } - - @Override - public TreeSetModifiableDBIDs newTreeSet() { - return new GenericTreeSetModifiableDBIDs(); + return new TroveHashSetModifiableDBIDs(); } @Override public ArrayModifiableDBIDs newArray(int size) { - return new GenericArrayModifiableDBIDs(size); + return new TroveArrayModifiableDBIDs(size); } @Override public HashSetModifiableDBIDs newHashSet(int size) { - return new GenericHashSetModifiableDBIDs(size); - } - - @Override - public TreeSetModifiableDBIDs newTreeSet(int size) { - return new GenericTreeSetModifiableDBIDs(size); + return new TroveHashSetModifiableDBIDs(size); } @Override public ArrayModifiableDBIDs newArray(DBIDs existing) { - return new GenericArrayModifiableDBIDs(existing); + return new TroveArrayModifiableDBIDs(existing); } @Override public HashSetModifiableDBIDs newHashSet(DBIDs existing) { - return new GenericHashSetModifiableDBIDs(existing); - } - - @Override - public TreeSetModifiableDBIDs newTreeSet(DBIDs existing) { - return new GenericTreeSetModifiableDBIDs(existing); + return new TroveHashSetModifiableDBIDs(existing); } @Override diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java new file mode 100644 index 00000000..a060c6b8 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java @@ -0,0 +1,133 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + 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 gnu.trove.list.TIntList; + +import java.util.Iterator; + +import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; + +/** + * Abstract base class for GNU Trove array based lists. + * + * @author Erich Schubert + * + * @apiviz.has IntegerDBID + * @apiviz.has TroveIteratorAdapter + */ +public abstract class TroveArrayDBIDs implements ArrayDBIDs { + /** + * Get the array store + * + * @return the store + */ + abstract protected TIntList getStore(); + + @Override + public Iterator<DBID> iterator() { + return new TroveIteratorAdapter(getStore().iterator()); + } + + @Override + public DBIDIter iter() { + return new DBIDItr(getStore()); + } + + @Override + public DBID get(int index) { + return new IntegerDBID(getStore().get(index)); + } + + @Override + public int size() { + return getStore().size(); + } + + @Override + public boolean isEmpty() { + return getStore().isEmpty(); + } + + @Override + public boolean contains(DBID o) { + return getStore().contains(o.getIntegerID()); + } + + @Override + public int binarySearch(DBID key) { + return getStore().binarySearch(key.getIntegerID()); + } + + /** + * Iterate over a Trove IntList, ELKI/C-style + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected static class DBIDItr implements DBIDIter { + /** + * Current position + */ + int pos = 0; + + /** + * The actual store we use + */ + TIntList store; + + /** + * Constructor. + * + * @param store The actual trove store + */ + public DBIDItr(TIntList store) { + super(); + this.store = store; + } + + @Override + public boolean valid() { + return pos < store.size(); + } + + @Override + public void advance() { + pos++; + } + + @Override + public int getIntegerID() { + return store.get(pos); + } + + @Override + public DBID getDBID() { + return new IntegerDBID(store.get(pos)); + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java new file mode 100644 index 00000000..abcbba14 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java @@ -0,0 +1,144 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + 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 gnu.trove.list.array.TIntArrayList; + +import java.util.Arrays; +import java.util.Comparator; + +import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDs; + +/** + * Class using a GNU Trove int array list as storage. + * + * @author Erich Schubert + */ +class TroveArrayModifiableDBIDs extends TroveArrayDBIDs implements ArrayModifiableDBIDs { + /** + * The actual trove array list + */ + private TIntArrayList store; + + /** + * Constructor. + * + * @param size Initial size + */ + protected TroveArrayModifiableDBIDs(int size) { + super(); + this.store = new TIntArrayList(size); + } + + /** + * Constructor. + */ + protected TroveArrayModifiableDBIDs() { + super(); + this.store = new TIntArrayList(); + } + + /** + * Constructor. + * + * @param existing Existing ids + */ + protected TroveArrayModifiableDBIDs(DBIDs existing) { + this(existing.size()); + this.addDBIDs(existing); + } + + @Override + protected TIntArrayList getStore() { + return store; + } + + @Override + public boolean addDBIDs(DBIDs ids) { + boolean success = false; + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + success |= store.add(iter.getIntegerID()); + } + return success; + } + + @Override + public boolean removeDBIDs(DBIDs ids) { + boolean success = false; + for(DBID id : ids) { + success |= store.remove(id.getIntegerID()); + } + return success; + } + + @Override + public boolean add(DBID e) { + return store.add(e.getIntegerID()); + } + + @Override + public boolean remove(DBID o) { + return store.remove(o.getIntegerID()); + } + + @Override + public DBID set(int index, DBID element) { + int prev = store.set(index, element.getIntegerID()); + return new IntegerDBID(prev); + } + + @Override + public DBID remove(int index) { + return new IntegerDBID(store.removeAt(index)); + } + + @Override + public void clear() { + store.clear(); + } + + @Override + public void sort() { + store.sort(); + } + + @Override + public void sort(Comparator<? super DBID> comparator) { + // FIXME: optimize, avoid the extra copy. + // Clone data + DBID[] data = new DBID[store.size()]; + for(int i = 0; i < store.size(); i++) { + data[i] = new IntegerDBID(store.get(i)); + } + // Sort + Arrays.sort(data, comparator); + // Copy back + for(int i = 0; i < store.size(); i++) { + store.set(i, data[i].getIntegerID()); + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/TreeSetModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayStaticDBIDs.java index 4212f847..53ab34d4 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/TreeSetModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayStaticDBIDs.java @@ -1,10 +1,9 @@ -package de.lmu.ifi.dbs.elki.database.ids; - +package de.lmu.ifi.dbs.elki.database.ids.integer; /* 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 @@ -23,13 +22,32 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.NavigableSet; +import gnu.trove.list.TIntList; +import de.lmu.ifi.dbs.elki.database.ids.ArrayStaticDBIDs; /** - * Set-oriented implementation of a modifiable DBID collection. + * Class accessing a trove int array. * * @author Erich Schubert */ -public interface TreeSetModifiableDBIDs extends ModifiableDBIDs, TreeSetDBIDs, NavigableSet<DBID> { - // empty -}
\ No newline at end of file +class TroveArrayStaticDBIDs extends TroveArrayDBIDs implements ArrayStaticDBIDs { + /** + * Actual trove store + */ + private final TIntList store; + + /** + * Constructor. + * + * @param store Actual trove store. + */ + protected TroveArrayStaticDBIDs(TIntList store) { + super(); + this.store = store; + } + + @Override + protected TIntList getStore() { + return store; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java new file mode 100644 index 00000000..11fe669c --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java @@ -0,0 +1,193 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +import java.util.Iterator; + +import gnu.trove.impl.hash.THashPrimitiveIterator; +import gnu.trove.impl.hash.TIntHash; +import gnu.trove.set.hash.TIntHashSet; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDs; +import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; + +/* + 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/>. + */ + +/** + * Implementation using GNU Trove Int Hash Sets. + * + * @author Erich Schubert + * + * @apiviz.has IntegerDBID + * @apiviz.has TroveIteratorAdapter + */ +class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs { + /** + * The actual store. + */ + TIntHashSet store; + + /** + * Constructor. + * + * @param size Initial size + */ + protected TroveHashSetModifiableDBIDs(int size) { + super(); + this.store = new TIntHashSet(size); + } + + /** + * Constructor. + */ + protected TroveHashSetModifiableDBIDs() { + super(); + this.store = new TIntHashSet(); + } + + /** + * Constructor. + * + * @param existing Existing IDs + */ + protected TroveHashSetModifiableDBIDs(DBIDs existing) { + this(existing.size()); + this.addDBIDs(existing); + } + + @Override + public DBIDIter iter() { + return new DBIDItr(store); + } + + @Override + public boolean addDBIDs(DBIDs ids) { + boolean success = false; + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + success |= store.add(iter.getIntegerID()); + } + return success; + } + + @Override + public boolean removeDBIDs(DBIDs ids) { + boolean success = false; + for(DBID id : ids) { + success |= store.remove(id.getIntegerID()); + } + return success; + } + + @Override + public boolean add(DBID e) { + return store.add(e.getIntegerID()); + } + + @Override + public boolean remove(DBID o) { + return store.remove(o.getIntegerID()); + } + + @Override + public boolean retainAll(DBIDs set) { + boolean modified = false; + Iterator<DBID> it = iterator(); + while(it.hasNext()) { + if(!set.contains(it.next())) { + it.remove(); + modified = true; + } + } + return modified; + } + + @Override + public Iterator<DBID> iterator() { + return new TroveIteratorAdapter(store.iterator()); + } + + @Override + public int size() { + return store.size(); + } + + @Override + public boolean isEmpty() { + return store.isEmpty(); + } + + @Override + public void clear() { + store.clear(); + } + + @Override + public boolean contains(DBID o) { + return store.contains(o.getIntegerID()); + } + + /** + * Iterator over trove hashs. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected static class DBIDItr extends THashPrimitiveIterator implements DBIDIter { + /** + * The has we access + */ + private TIntHash hash; + + /** + * Constructor. + * + * @param hash Trove hash + */ + public DBIDItr(TIntHash hash) { + super(hash); + this.hash = hash; + this._index = nextIndex(); // Find first element + } + + @Override + public boolean valid() { + return _index >= 0; + } + + @Override + public void advance() { + this._index = nextIndex(); + } + + @Override + public int getIntegerID() { + return hash._set[_index]; + } + + @Override + public DBID getDBID() { + return new IntegerDBID(hash._set[_index]); + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveIteratorAdapter.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveIteratorAdapter.java new file mode 100644 index 00000000..2f596f47 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveIteratorAdapter.java @@ -0,0 +1,66 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + 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 gnu.trove.iterator.TIntIterator; + +import java.util.Iterator; + +import de.lmu.ifi.dbs.elki.database.ids.DBID; + +/** + * Adapter for using GNU Trove iterators. + * + * @author Erich Schubert + */ +class TroveIteratorAdapter implements Iterator<DBID> { + /** + * The actual iterator. + */ + private TIntIterator iterator; + + /** + * Constructor. + * + * @param iterator Trove iterator + */ + protected TroveIteratorAdapter(TIntIterator iterator) { + this.iterator = iterator; + } + + @Override + public boolean hasNext() { + return iterator.hasNext(); + } + + @Override + public DBID next() { + return new IntegerDBID(iterator.next()); + } + + @Override + public void remove() { + iterator.remove(); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/package-info.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/package-info.java index d7ab7304..2508c930 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/package-info.java @@ -10,7 +10,7 @@ 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/src/de/lmu/ifi/dbs/elki/database/ids/package-info.java b/src/de/lmu/ifi/dbs/elki/database/ids/package-info.java index ce8d1f39..2c7de1c5 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/package-info.java @@ -17,19 +17,16 @@ * <th></th> * <th style="border-bottom: 2px">{@link de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs ArrayDBIDs}</th> * <th style="border-bottom: 2px">{@link de.lmu.ifi.dbs.elki.database.ids.HashSetDBIDs HashSetDBIDs}</th> - * <th style="border-bottom: 2px">{@link de.lmu.ifi.dbs.elki.database.ids.TreeSetDBIDs TreeSetDBIDs}</th> * </tr> * <tr> * <th style="border-right: 2px">{@link de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs ModifiableDBIDs}</th> * <td>{@link de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs ArrayModifiableDBIDs}</td> * <td>{@link de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs HashSetModifiableDBIDs}</td> - * <td>{@link de.lmu.ifi.dbs.elki.database.ids.TreeSetModifiableDBIDs TreeSetModifiableDBIDs}</td> * </tr> * <tr> * <th style="border-right: 2px">{@link de.lmu.ifi.dbs.elki.database.ids.StaticDBIDs StaticDBIDs}</th> * <td>{@link de.lmu.ifi.dbs.elki.database.ids.ArrayStaticDBIDs ArrayStaticDBIDs}</td> * <td>n/a</td> - * <td>n/a</td> * </tr> * </table> * @@ -47,8 +44,6 @@ * ArrayModifiableDBIDs array = DBIDUtil.newArraySet(123); * // new DBID hash set with minimum initial capacity * ModifiableDBIDs hash = DBIDUtil.newHashSet(); - * // initialize a tree set with the IDs of the database. - * ModifiableDBIDs tree = DBIDUtil.newTreeSet(database.getIDs()); * * // add all DBIDs from the hash * tree.addDBIDs(hash) @@ -78,25 +73,25 @@ * @apiviz.exclude java.* */ /* -This file is part of ELKI: -Environment for Developing KDD-Applications Supported by Index-Structures + 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 + 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 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. + 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/>. -*/ + 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/>. + */ package de.lmu.ifi.dbs.elki.database.ids;
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/package-info.java b/src/de/lmu/ifi/dbs/elki/database/package-info.java index e6c6077c..c39600f7 100644 --- a/src/de/lmu/ifi/dbs/elki/database/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/package-info.java @@ -5,7 +5,7 @@ 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/src/de/lmu/ifi/dbs/elki/database/query/AbstractDataBasedQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/AbstractDataBasedQuery.java index bb913602..d9accf4f 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/AbstractDataBasedQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/AbstractDataBasedQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query; 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 @@ -49,9 +49,9 @@ public abstract class AbstractDataBasedQuery<O> implements DatabaseQuery { } /** - * Give access to the underlying data query. + * Get the queries relation. * - * @return data query instance + * @return Relation */ public Relation<? extends O> getRelation() { return relation; diff --git a/src/de/lmu/ifi/dbs/elki/database/query/DatabaseQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/DatabaseQuery.java index 5d56a012..28c89ee3 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/DatabaseQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/DatabaseQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query; 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/src/de/lmu/ifi/dbs/elki/database/query/DistanceResultPair.java b/src/de/lmu/ifi/dbs/elki/database/query/DistanceResultPair.java index ccdef3ef..e7403628 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/DistanceResultPair.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/DistanceResultPair.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query; 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/src/de/lmu/ifi/dbs/elki/database/query/DistanceSimilarityQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/DistanceSimilarityQuery.java index 44f735ec..9b9367fb 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/DistanceSimilarityQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/DistanceSimilarityQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query; 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/src/de/lmu/ifi/dbs/elki/database/query/DoubleDistanceResultPair.java b/src/de/lmu/ifi/dbs/elki/database/query/DoubleDistanceResultPair.java index cbe2cb23..e0be7c40 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/DoubleDistanceResultPair.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/DoubleDistanceResultPair.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query; 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/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceResultPair.java b/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceResultPair.java index 19f17c48..4b838560 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceResultPair.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceResultPair.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query; 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/src/de/lmu/ifi/dbs/elki/database/query/LinearScanQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/LinearScanQuery.java index 80f2c5b5..4cace1cf 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/LinearScanQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/LinearScanQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query; 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/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDatabaseDistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDatabaseDistanceQuery.java index fff15c93..92c116e3 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDatabaseDistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDatabaseDistanceQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; 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/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDistanceQuery.java index e29ccc5e..10dde0ad 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/AbstractDistanceQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; 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/src/de/lmu/ifi/dbs/elki/database/query/distance/DBIDDistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/DBIDDistanceQuery.java index cf650b0f..2bb45623 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/DBIDDistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/DBIDDistanceQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; 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/src/de/lmu/ifi/dbs/elki/database/query/distance/DistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/DistanceQuery.java index 63be8fe5..1986b246 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/DistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/DistanceQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; 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/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceQuery.java index 6c056a0b..5015dee1 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; 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/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceSimilarityQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceSimilarityQuery.java index 7013c693..4988c925 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceSimilarityQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/PrimitiveDistanceSimilarityQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; 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/src/de/lmu/ifi/dbs/elki/database/query/distance/SpatialDistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/SpatialDistanceQuery.java index c37c5b18..59f6534b 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/SpatialDistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/SpatialDistanceQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; 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 @@ -60,28 +60,6 @@ public interface SpatialDistanceQuery<V extends SpatialComparable, D extends Dis D minDist(SpatialComparable mbr, DBID id); /** - * Computes the distance between the two given MBRs according to this distance - * function. - * - * @param mbr1 the first MBR object - * @param mbr2 the second MBR object - * @return the distance between the two given MBRs according to this distance - * function - */ - D mbrDist(SpatialComparable mbr1, SpatialComparable mbr2); - - /** - * Computes the distance between the centroids of the two given MBRs according - * to this distance function. - * - * @param mbr1 the first MBR object - * @param mbr2 the second MBR object - * @return the distance between the centroids of the two given MBRs according - * to this distance function - */ - D centerDistance(SpatialComparable mbr1, SpatialComparable mbr2); - - /** * Get the inner distance function. * * @return Distance function diff --git a/src/de/lmu/ifi/dbs/elki/database/query/distance/SpatialPrimitiveDistanceQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/SpatialPrimitiveDistanceQuery.java index ddafc622..550c2c5c 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/SpatialPrimitiveDistanceQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/SpatialPrimitiveDistanceQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.distance; 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 @@ -54,16 +54,6 @@ public class SpatialPrimitiveDistanceQuery<V extends SpatialComparable, D extend } @Override - public D centerDistance(SpatialComparable mbr1, SpatialComparable mbr2) { - return distanceFunction.centerDistance(mbr1, mbr2); - } - - @Override - public D mbrDist(SpatialComparable mbr1, SpatialComparable mbr2) { - return distanceFunction.minDist(mbr1, mbr2); - } - - @Override public D minDist(SpatialComparable mbr, V v) { return distanceFunction.minDist(mbr, v); } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/distance/package-info.java b/src/de/lmu/ifi/dbs/elki/database/query/distance/package-info.java index 71b54314..2257eb98 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/distance/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/distance/package-info.java @@ -6,7 +6,7 @@ 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/src/de/lmu/ifi/dbs/elki/database/query/knn/AbstractDistanceKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/AbstractDistanceKNNQuery.java index 296a3950..731148e8 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/AbstractDistanceKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/AbstractDistanceKNNQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.knn; 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 @@ -23,11 +23,8 @@ package de.lmu.ifi.dbs.elki.database.query.knn; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.List; - import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; -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.distance.distancevalue.Distance; @@ -53,18 +50,8 @@ public abstract class AbstractDistanceKNNQuery<O, D extends Distance<D>> extends } @Override - abstract public List<DistanceResultPair<D>> getKNNForDBID(DBID id, int k); - - @Override - abstract public List<DistanceResultPair<D>> getKNNForObject(O obj, int k); + abstract public KNNResult<D> getKNNForDBID(DBID id, int k); @Override - public DistanceQuery<O, D> getDistanceQuery() { - return distanceQuery; - } - - @Override - public D getDistanceFactory() { - return distanceQuery.getDistanceFactory(); - } + abstract public KNNResult<D> getKNNForObject(O obj, int k); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNQuery.java index 81b4ded8..80d91180 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.knn; 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,9 +29,6 @@ import java.util.Map; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; -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.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; @@ -41,7 +38,7 @@ import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; * @author Erich Schubert * * @apiviz.landmark - * @apiviz.uses DistanceResultPair oneway - - «create» + * @apiviz.has KNNResult oneway - - «create» * * @param <O> Object type * @param <D> Distance type @@ -54,7 +51,7 @@ public interface KNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k Number of neighbors requested * @return neighbors */ - public List<DistanceResultPair<D>> getKNNForDBID(DBID id, int k); + public KNNResult<D> getKNNForDBID(DBID id, int k); /** * Bulk query method @@ -63,7 +60,7 @@ public interface KNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k Number of neighbors requested * @return neighbors */ - public List<List<DistanceResultPair<D>>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k); + public List<KNNResult<D>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k); /** * Bulk query method configured by a map. @@ -82,24 +79,5 @@ public interface KNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k Number of neighbors requested * @return neighbors */ - // TODO: return KNNList<D> instead? - public List<DistanceResultPair<D>> getKNNForObject(O obj, int k); - - /** - * Get the distance query for this function. - */ - // TODO: remove? - public DistanceQuery<O, D> getDistanceQuery(); - - /** - * Get the distance data type of the function. - */ - public D getDistanceFactory(); - - /** - * Access the underlying data query. - * - * @return data query in use - */ - public abstract Relation<? extends O> getRelation(); + public KNNResult<D> getKNNForObject(O obj, int k); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNResult.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNResult.java new file mode 100644 index 00000000..d45fd8d7 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNResult.java @@ -0,0 +1,83 @@ +package de.lmu.ifi.dbs.elki.database.query.knn; + +/* + 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 java.util.Collection; +import java.util.List; + +import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; +import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; + +/** + * Interface for kNN results - List<> like. + * + * @author Erich Schubert + * + * @param <D> Distance type + * + * @apiviz.composedOf DistanceResultPair + */ +public interface KNNResult<D extends Distance<D>> extends Collection<DistanceResultPair<D>> { + /** + * Size + */ + @Override + public int size(); + + /** + * Get the K parameter (note: this may be less than the size of the list!) + * + * @return K + */ + public int getK(); + + /** + * Direct object access. + * + * @param index + */ + public DistanceResultPair<D> get(int index); + + /** + * Get the distance to the k nearest neighbor, or maxdist otherwise. + * + * @return Maximum distance + */ + public D getKNNDistance(); + + /** + * View as ArrayDBIDs + * + * @return Static DBIDs + */ + public ArrayDBIDs asDBIDs(); + + /** + * View as list of distances + * + * @return List of distances view + */ + public List<D> asDistanceList(); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNUtil.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNUtil.java new file mode 100644 index 00000000..1179edb5 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNUtil.java @@ -0,0 +1,417 @@ +package de.lmu.ifi.dbs.elki.database.query.knn; + +/* + 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 java.util.AbstractCollection; +import java.util.AbstractList; +import java.util.Iterator; +import java.util.List; + +import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; + +/** + * Helper classes for kNN results. + * + * @author Erich Schubert + * + * @apiviz.uses KNNResult + */ +public final class KNNUtil { + /** + * Sublist of an existing result to contain only the first k elements. + * + * @author Erich Schubert + * + * @param <D> Distance + */ + protected static class KNNSubList<D extends Distance<D>> extends AbstractCollection<DistanceResultPair<D>> implements KNNResult<D> { + /** + * Parameter k + */ + private final int k; + + /** + * Actual size, including ties + */ + private final int size; + + /** + * Wrapped inner result. + */ + private final KNNResult<D> inner; + + /** + * Constructor. + * + * @param inner Inner instance + * @param k k value + */ + public KNNSubList(KNNResult<D> inner, int k) { + this.inner = inner; + this.k = k; + // Compute list size + // TODO: optimize for double distances. + { + DistanceResultPair<D> dist = inner.get(k); + int i = k; + while(i + 1 < inner.size()) { + if(dist.compareByDistance(inner.get(i + 1)) < 0) { + break; + } + i++; + } + size = i; + } + } + + @Override + public int getK() { + return k; + } + + @Override + public DistanceResultPair<D> get(int index) { + assert (index < size) : "Access beyond design size of list."; + return inner.get(index); + } + + @Override + public D getKNNDistance() { + return inner.get(k).getDistance(); + } + + @Override + public ArrayDBIDs asDBIDs() { + return KNNUtil.asDBIDs(this); + } + + @Override + public List<D> asDistanceList() { + return KNNUtil.asDistanceList(this); + } + + @Override + public Iterator<DistanceResultPair<D>> iterator() { + return new Itr(); + } + + @Override + public int size() { + return size; + } + + /** + * Iterator for the sublist. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + private class Itr implements Iterator<DistanceResultPair<D>> { + /** + * Current position + */ + private int pos = -1; + + @Override + public boolean hasNext() { + return pos + 1 < size; + } + + @Override + public DistanceResultPair<D> next() { + pos++; + return inner.get(pos); + } + + @Override + public void remove() { + throw new UnsupportedOperationException("kNN results are unmodifiable."); + } + } + } + + /** + * Proxy iterator for accessing DBIDs. + * + * @author Erich Schubert + */ + protected static class DBIDIterator implements Iterator<DBID> { + /** + * The real iterator. + */ + Iterator<? extends DistanceResultPair<?>> itr; + + /** + * Constructor. + */ + protected DBIDIterator(Iterator<? extends DistanceResultPair<?>> itr) { + super(); + this.itr = itr; + } + + @Override + public boolean hasNext() { + return itr.hasNext(); + } + + @Override + public DBID next() { + return itr.next().getDBID(); + } + + @Override + public void remove() { + itr.remove(); + } + } + + /** + * Proxy iterator for accessing DBIDs. + * + * @author Erich Schubert + */ + protected static class DBIDItr implements DBIDIter { + /** + * Current result + */ + DistanceResultPair<?> cur; + + /** + * The real iterator. + */ + Iterator<? extends DistanceResultPair<?>> itr; + + /** + * Constructor. + */ + protected DBIDItr(Iterator<? extends DistanceResultPair<?>> itr) { + super(); + this.itr = itr; + advance(); + } + + @Override + public boolean valid() { + return cur != null; + } + + @Override + public void advance() { + if(itr.hasNext()) { + cur = itr.next(); + } + else { + cur = null; + } + } + + @Override + public int getIntegerID() { + return cur.getDBID().getIntegerID(); + } + + @Override + public DBID getDBID() { + return cur.getDBID(); + } + } + + /** + * A view on the DBIDs of the result + * + * @author Erich Schubert + */ + protected static class DBIDView implements ArrayDBIDs { + /** + * The true list. + */ + final KNNResult<?> parent; + + /** + * Constructor. + * + * @param parent Owner + */ + public DBIDView(KNNResult<?> parent) { + super(); + this.parent = parent; + } + + @Override + public DBID get(int i) { + return parent.get(i).getDBID(); + } + + @Override + public Iterator<DBID> iterator() { + return new DBIDIterator(parent.iterator()); + } + + @Override + public DBIDIter iter() { + return new DBIDItr(parent.iterator()); + } + + @Override + public int size() { + return parent.size(); + } + + @Override + public boolean contains(DBID o) { + for(DBID id : this) { + if(id.equals(o)) { + return true; + } + } + return false; + } + + @Override + public boolean isEmpty() { + return parent.size() == 0; + } + + /** + * A binary search does not make sense here, as the (read-only) result is sorted by + * distance, not DBID. Thus unsupported. + */ + @Override + @Deprecated + public int binarySearch(DBID key) { + throw new UnsupportedOperationException("Since the result is usually not sorted, a binary Search does not make sense!"); + } + } + + /** + * Proxy iterator for accessing DBIDs. + * + * @author Erich Schubert + */ + protected static class DistanceItr<D extends Distance<D>> implements Iterator<D> { + /** + * The real iterator. + */ + Iterator<? extends DistanceResultPair<D>> itr; + + /** + * Constructor. + */ + protected DistanceItr(Iterator<? extends DistanceResultPair<D>> itr) { + super(); + this.itr = itr; + } + + @Override + public boolean hasNext() { + return itr.hasNext(); + } + + @Override + public D next() { + return itr.next().getDistance(); + } + + @Override + public void remove() { + itr.remove(); + } + } + + /** + * A view on the Distances of the result + * + * @author Erich Schubert + */ + protected static class DistanceView<D extends Distance<D>> extends AbstractList<D> implements List<D> { + /** + * The true list. + */ + final KNNResult<D> parent; + + /** + * Constructor. + * + * @param parent Owner + */ + public DistanceView(KNNResult<D> parent) { + super(); + this.parent = parent; + } + + @Override + public D get(int i) { + return parent.get(i).getDistance(); + } + + @Override + public Iterator<D> iterator() { + return new DistanceItr<D>(parent.iterator()); + } + + @Override + public int size() { + return parent.size(); + } + } + + /** + * View as ArrayDBIDs + * + * @param list Result to proxy + * @return Static DBIDs + */ + public static ArrayDBIDs asDBIDs(KNNResult<?> list) { + return new DBIDView(list); + } + + /** + * View as list of distances + * + * @param list Result to proxy + * @return List of distances view + */ + public static <D extends Distance<D>> List<D> asDistanceList(KNNResult<D> list) { + return new DistanceView<D>(list); + } + + /** + * Get a subset of the KNN result. + * + * @param list Existing list + * @param k k + * @return Subset + */ + public static <D extends Distance<D>> KNNResult<D> subList(KNNResult<D> list, int k) { + if(k >= list.size()) { + return list; + } + return new KNNSubList<D>(list, k); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanKNNQuery.java index b52c6dec..d6492f43 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanKNNQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.knn; 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 @@ -32,7 +32,6 @@ import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.LinearScanQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.distance.PrimitiveDistanceQuery; @@ -76,7 +75,7 @@ public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistan } @Override - public List<DistanceResultPair<D>> getKNNForDBID(DBID id, int k) { + public KNNResult<D> getKNNForDBID(DBID id, int k) { KNNHeap<D> heap = new KNNHeap<D>(k); if(PrimitiveDistanceQuery.class.isInstance(distanceQuery)) { O obj = relation.get(id); @@ -89,11 +88,11 @@ public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistan heap.add(distanceQuery.distance(id, candidateID), candidateID); } } - return heap.toSortedArrayList(); + return heap.toKNNList(); } @Override - public List<List<DistanceResultPair<D>>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<KNNResult<D>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { final int size = ids.size(); final List<KNNHeap<D>> heaps = new ArrayList<KNNHeap<D>>(size); for(int i = 0; i < size; i++) { @@ -101,9 +100,9 @@ public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistan } linearScanBatchKNN(ids, heaps); // Serialize heaps - List<List<DistanceResultPair<D>>> result = new ArrayList<List<DistanceResultPair<D>>>(size); + List<KNNResult<D>> result = new ArrayList<KNNResult<D>>(size); for(KNNHeap<D> heap : heaps) { - result.add(heap.toSortedArrayList()); + result.add(heap.toKNNList()); } return result; } @@ -121,12 +120,12 @@ public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistan } @Override - public List<DistanceResultPair<D>> getKNNForObject(O obj, int k) { + public KNNResult<D> getKNNForObject(O obj, int k) { KNNHeap<D> heap = new KNNHeap<D>(k); for(DBID candidateID : relation.iterDBIDs()) { O candidate = relation.get(candidateID); heap.add(distanceQuery.distance(obj, candidate), candidateID); } - return heap.toSortedArrayList(); + return heap.toKNNList(); } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanPrimitiveDistanceKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanPrimitiveDistanceKNNQuery.java index 8af7e549..07632a34 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanPrimitiveDistanceKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanPrimitiveDistanceKNNQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.knn; 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,6 @@ import java.util.Map.Entry; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; 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.PrimitiveDistanceQuery; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; @@ -75,12 +74,12 @@ public class LinearScanPrimitiveDistanceKNNQuery<O, D extends Distance<D>> exten } @Override - public List<DistanceResultPair<D>> getKNNForDBID(DBID id, int k) { + public KNNResult<D> getKNNForDBID(DBID id, int k) { return getKNNForObject(relation.get(id), k); } @Override - public List<List<DistanceResultPair<D>>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<KNNResult<D>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { final int size = ids.size(); final List<KNNHeap<D>> heaps = new ArrayList<KNNHeap<D>>(size); List<O> objs = new ArrayList<O>(size); @@ -90,9 +89,9 @@ public class LinearScanPrimitiveDistanceKNNQuery<O, D extends Distance<D>> exten } linearScanBatchKNN(objs, heaps); - List<List<DistanceResultPair<D>>> result = new ArrayList<List<DistanceResultPair<D>>>(heaps.size()); + List<KNNResult<D>> result = new ArrayList<KNNResult<D>>(heaps.size()); for(KNNHeap<D> heap : heaps) { - result.add(heap.toSortedArrayList()); + result.add(heap.toKNNList()); } return result; } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanRawDoubleDistanceKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanRawDoubleDistanceKNNQuery.java index 63652e5b..3f7dc04f 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanRawDoubleDistanceKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/LinearScanRawDoubleDistanceKNNQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.knn; 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,7 +27,6 @@ import java.util.Arrays; import java.util.List; 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.DoubleDistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.PrimitiveDistanceQuery; import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDoubleDistanceFunction; @@ -57,12 +56,12 @@ public class LinearScanRawDoubleDistanceKNNQuery<O> extends LinearScanPrimitiveD } @Override - public List<DistanceResultPair<DoubleDistance>> getKNNForDBID(DBID id, int k) { + public KNNResult<DoubleDistance> getKNNForDBID(DBID id, int k) { return getKNNForObject(relation.get(id), k); } @Override - public List<DistanceResultPair<DoubleDistance>> getKNNForObject(O obj, int k) { + public KNNResult<DoubleDistance> getKNNForObject(O obj, int k) { @SuppressWarnings("unchecked") final PrimitiveDoubleDistanceFunction<O> rawdist = (PrimitiveDoubleDistanceFunction<O>) distanceQuery.getDistanceFunction(); // Optimization for double distances. @@ -78,7 +77,7 @@ public class LinearScanRawDoubleDistanceKNNQuery<O> extends LinearScanPrimitiveD } } } - return heap.toSortedArrayList(); + return heap.toKNNList(); } @Override diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/PreprocessorKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/PreprocessorKNNQuery.java index d82fc20e..93321609 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/PreprocessorKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/PreprocessorKNNQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.knn; 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 @@ -32,11 +32,9 @@ import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; 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.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.index.preprocessed.knn.AbstractMaterializeKNNPreprocessor; -import de.lmu.ifi.dbs.elki.index.preprocessed.knn.MaterializeKNNPreprocessor; import de.lmu.ifi.dbs.elki.logging.LoggingUtil; import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; @@ -46,11 +44,11 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; * * @author Erich Schubert */ -public class PreprocessorKNNQuery<O, D extends Distance<D>> extends AbstractDataBasedQuery<O> implements KNNQuery<O, D> { +public class PreprocessorKNNQuery<O, D extends Distance<D>, T extends KNNResult<D>> extends AbstractDataBasedQuery<O> implements KNNQuery<O, D> { /** * The last preprocessor result */ - final private MaterializeKNNPreprocessor<O, D> preprocessor; + final private AbstractMaterializeKNNPreprocessor<O, D, T> preprocessor; /** * Warn only once. @@ -63,7 +61,7 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>> extends AbstractData * @param database Database to query * @param preprocessor Preprocessor instance to use */ - public PreprocessorKNNQuery(Relation<O> database, MaterializeKNNPreprocessor<O, D> preprocessor) { + public PreprocessorKNNQuery(Relation<O> database, AbstractMaterializeKNNPreprocessor<O, D, T> preprocessor) { super(database); this.preprocessor = preprocessor; } @@ -74,17 +72,17 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>> extends AbstractData * @param database Database to query * @param preprocessor Preprocessor to use */ - public PreprocessorKNNQuery(Relation<O> database, MaterializeKNNPreprocessor.Factory<O, D> preprocessor) { + public PreprocessorKNNQuery(Relation<O> database, AbstractMaterializeKNNPreprocessor.Factory<O, D, T> preprocessor) { this(database, preprocessor.instantiate(database)); } @Override - public List<DistanceResultPair<D>> getKNNForDBID(DBID id, int k) { + public KNNResult<D> getKNNForDBID(DBID id, int k) { if(!warned && k > preprocessor.getK()) { LoggingUtil.warning("Requested more neighbors than preprocessed!"); } if(!warned && k < preprocessor.getK()) { - List<DistanceResultPair<D>> dr = preprocessor.get(id); + KNNResult<D> dr = preprocessor.get(id); int subk = k; D kdist = dr.get(subk - 1).getDistance(); while(subk < dr.size()) { @@ -98,7 +96,7 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>> extends AbstractData } } if(subk < dr.size()) { - return dr.subList(0, subk); + return KNNUtil.subList(dr, subk); } else { return dr; @@ -108,14 +106,14 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>> extends AbstractData } @Override - public List<List<DistanceResultPair<D>>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<KNNResult<D>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k) { if(!warned && k > preprocessor.getK()) { LoggingUtil.warning("Requested more neighbors than preprocessed!"); } - List<List<DistanceResultPair<D>>> result = new ArrayList<List<DistanceResultPair<D>>>(ids.size()); + List<KNNResult<D>> result = new ArrayList<KNNResult<D>>(ids.size()); if(k < preprocessor.getK()) { for(DBID id : ids) { - List<DistanceResultPair<D>> dr = preprocessor.get(id); + KNNResult<D> dr = preprocessor.get(id); int subk = k; D kdist = dr.get(subk - 1).getDistance(); while(subk < dr.size()) { @@ -129,7 +127,7 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>> extends AbstractData } } if(subk < dr.size()) { - result.add(dr.subList(0, subk)); + result.add(KNNUtil.subList(dr, subk)); } else { result.add(dr); @@ -156,7 +154,7 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>> extends AbstractData } @Override - public List<DistanceResultPair<D>> getKNNForObject(O obj, int k) { + public KNNResult<D> getKNNForObject(O obj, int k) { throw new AbortException("Preprocessor KNN query only supports ID queries."); } @@ -165,18 +163,7 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>> extends AbstractData * * @return preprocessor instance */ - public AbstractMaterializeKNNPreprocessor<O, D> getPreprocessor() { + public AbstractMaterializeKNNPreprocessor<O, D, T> getPreprocessor() { return preprocessor; } - - @Override - public D getDistanceFactory() { - return preprocessor.getDistanceFactory(); - } - - @Override - public DistanceQuery<O, D> getDistanceQuery() { - // TODO: remove? throw an exception? - return preprocessor.getDistanceQuery(); - } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/knn/package-info.java b/src/de/lmu/ifi/dbs/elki/database/query/knn/package-info.java index 71d5433f..891ed296 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/knn/package-info.java @@ -7,7 +7,7 @@ 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/src/de/lmu/ifi/dbs/elki/database/query/package-info.java b/src/de/lmu/ifi/dbs/elki/database/query/package-info.java index 42c9bab6..05c635a0 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/package-info.java @@ -78,7 +78,7 @@ 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/src/de/lmu/ifi/dbs/elki/database/query/range/AbstractDistanceRangeQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/range/AbstractDistanceRangeQuery.java index e35cb99f..60426034 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/AbstractDistanceRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/AbstractDistanceRangeQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.range; 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 @@ -23,10 +23,8 @@ package de.lmu.ifi.dbs.elki.database.query.range; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.ArrayList; import java.util.List; -import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; @@ -63,18 +61,4 @@ public abstract class AbstractDistanceRangeQuery<O, D extends Distance<D>> exten @Override abstract public List<DistanceResultPair<D>> getRangeForObject(O obj, D range); - - @Override - public List<List<DistanceResultPair<D>>> getRangeForBulkDBIDs(ArrayDBIDs ids, D range) { - final List<List<DistanceResultPair<D>>> lists = new ArrayList<List<DistanceResultPair<D>>>(ids.size()); - for(DBID id : ids) { - lists.add(getRangeForDBID(id, range)); - } - return lists; - } - - @Override - public D getDistanceFactory() { - return distanceQuery.getDistanceFactory(); - } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanPrimitiveDistanceRangeQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanPrimitiveDistanceRangeQuery.java index 6031a30e..dfe0b581 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanPrimitiveDistanceRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanPrimitiveDistanceRangeQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.range; 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/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRangeQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRangeQuery.java index d4b7296e..a7bb7db9 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRangeQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.range; 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/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRawDoubleDistanceRangeQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRawDoubleDistanceRangeQuery.java index b33c871e..18d1d173 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRawDoubleDistanceRangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/LinearScanRawDoubleDistanceRangeQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.range; 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/src/de/lmu/ifi/dbs/elki/database/query/range/RangeQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/range/RangeQuery.java index 7d9ebd42..c2dbecd6 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/RangeQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/RangeQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.range; 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 @@ -25,11 +25,9 @@ package de.lmu.ifi.dbs.elki.database.query.range; import java.util.List; -import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; -import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** @@ -54,15 +52,6 @@ public interface RangeQuery<O, D extends Distance<D>> extends DatabaseQuery { public List<DistanceResultPair<D>> getRangeForDBID(DBID id, D range); /** - * Bulk query method - * - * @param ids query object IDs - * @param range Query range - * @return neighbors - */ - public List<List<DistanceResultPair<D>>> getRangeForBulkDBIDs(ArrayDBIDs ids, D range); - - /** * Get the nearest neighbors for a particular object in a given query range * * @param obj Query object @@ -70,16 +59,4 @@ public interface RangeQuery<O, D extends Distance<D>> extends DatabaseQuery { * @return neighbors */ public List<DistanceResultPair<D>> getRangeForObject(O obj, D range); - - /** - * Get the distance data type of the function. - */ - public D getDistanceFactory(); - - /** - * Access the underlying data query. - * - * @return data query in use - */ - public abstract Relation<? extends O> getRelation(); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/range/package-info.java b/src/de/lmu/ifi/dbs/elki/database/query/range/package-info.java index 21bd4f9a..a176e43d 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/range/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/range/package-info.java @@ -7,7 +7,7 @@ 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/src/de/lmu/ifi/dbs/elki/database/query/rknn/AbstractRKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/rknn/AbstractRKNNQuery.java index 5cecaf88..86e82c7e 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/rknn/AbstractRKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/rknn/AbstractRKNNQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.rknn; 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 @@ -54,9 +54,4 @@ public abstract class AbstractRKNNQuery<O, D extends Distance<D>> extends Abstra @Override abstract public List<DistanceResultPair<D>> getRKNNForDBID(DBID id, int k); - - @Override - public D getDistanceFactory() { - return distanceQuery.getDistanceFactory(); - } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/rknn/LinearScanRKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/rknn/LinearScanRKNNQuery.java index b3e581e7..1449d7f0 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/rknn/LinearScanRKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/rknn/LinearScanRKNNQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.rknn; 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 @@ -35,6 +35,7 @@ import de.lmu.ifi.dbs.elki.database.query.GenericDistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.LinearScanQuery; 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.distance.distancevalue.Distance; /** @@ -72,11 +73,11 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ ArrayList<DistanceResultPair<D>> rNNlist = new ArrayList<DistanceResultPair<D>>(); ArrayDBIDs allIDs = DBIDUtil.ensureArray(relation.getDBIDs()); - List<List<DistanceResultPair<D>>> kNNLists = knnQuery.getKNNForBulkDBIDs(allIDs, k); + List<? extends KNNResult<D>> kNNLists = knnQuery.getKNNForBulkDBIDs(allIDs, k); int i = 0; for(DBID qid : allIDs) { - List<DistanceResultPair<D>> knn = kNNLists.get(i); + KNNResult<D> knn = kNNLists.get(i); int last = Math.min(k - 1, knn.size() - 1); D dist = distanceQuery.distance(obj, qid); if(last < k - 1 || dist.compareTo(knn.get(last).getDistance()) < 1) { @@ -101,15 +102,15 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ } ArrayDBIDs allIDs = DBIDUtil.ensureArray(relation.getDBIDs()); - List<List<DistanceResultPair<D>>> kNNList = knnQuery.getKNNForBulkDBIDs(allIDs, k); + List<? extends KNNResult<D>> kNNList = knnQuery.getKNNForBulkDBIDs(allIDs, k); int i = 0; for(DBID qid : allIDs) { - List<DistanceResultPair<D>> knn = kNNList.get(i); + KNNResult<D> knn = kNNList.get(i); for(DistanceResultPair<D> n : knn) { int j = 0; for(DBID id : ids) { - if(n.getDBID() == id) { + if(n.getDBID().equals(id)) { List<DistanceResultPair<D>> rNN = rNNList.get(j); rNN.add(new GenericDistanceResultPair<D>(n.getDistance(), qid)); } diff --git a/src/de/lmu/ifi/dbs/elki/database/query/rknn/PreprocessorRKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/rknn/PreprocessorRKNNQuery.java index 5303666f..2f8e841a 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/rknn/PreprocessorRKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/rknn/PreprocessorRKNNQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.rknn; 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 @@ -32,7 +32,6 @@ import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.index.preprocessed.knn.AbstractMaterializeKNNPreprocessor; import de.lmu.ifi.dbs.elki.index.preprocessed.knn.MaterializeKNNAndRKNNPreprocessor; import de.lmu.ifi.dbs.elki.logging.LoggingUtil; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; @@ -98,18 +97,4 @@ public class PreprocessorRKNNQuery<O, D extends Distance<D>> extends AbstractDat } return result; } - - /** - * Get the preprocessor instance. - * - * @return preprocessor instance - */ - public AbstractMaterializeKNNPreprocessor<O, D> getPreprocessor() { - return preprocessor; - } - - @Override - public D getDistanceFactory() { - return preprocessor.getDistanceFactory(); - } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/rknn/RKNNQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/rknn/RKNNQuery.java index df5ac43c..e707b6ce 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/rknn/RKNNQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/rknn/RKNNQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.rknn; 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,6 @@ import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; -import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** @@ -69,16 +68,4 @@ public interface RKNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @return reverse k nearest neighbors */ public List<List<DistanceResultPair<D>>> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k); - - /** - * Get the distance data type of the function. - */ - public D getDistanceFactory(); - - /** - * Access the underlying data query. - * - * @return data query in use - */ - public abstract Relation<? extends O> getRelation(); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/rknn/package-info.java b/src/de/lmu/ifi/dbs/elki/database/query/rknn/package-info.java index 80bcd988..a7e2bf37 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/rknn/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/rknn/package-info.java @@ -7,7 +7,7 @@ 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/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractDBIDSimilarityQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractDBIDSimilarityQuery.java index 2e263cd9..1af1c624 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractDBIDSimilarityQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractDBIDSimilarityQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.similarity; 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/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractSimilarityQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractSimilarityQuery.java index 3dba474e..316d155c 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractSimilarityQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/similarity/AbstractSimilarityQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.similarity; 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/src/de/lmu/ifi/dbs/elki/database/query/similarity/PrimitiveSimilarityQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/similarity/PrimitiveSimilarityQuery.java index 71dc0c4a..f57e0bd5 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/similarity/PrimitiveSimilarityQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/similarity/PrimitiveSimilarityQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.similarity; 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/src/de/lmu/ifi/dbs/elki/database/query/similarity/SimilarityQuery.java b/src/de/lmu/ifi/dbs/elki/database/query/similarity/SimilarityQuery.java index 91d7b84b..c3fdaaa4 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/similarity/SimilarityQuery.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/similarity/SimilarityQuery.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.query.similarity; 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/src/de/lmu/ifi/dbs/elki/database/query/similarity/package-info.java b/src/de/lmu/ifi/dbs/elki/database/query/similarity/package-info.java index a6dca739..d601d0a4 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/similarity/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/query/similarity/package-info.java @@ -6,7 +6,7 @@ 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/src/de/lmu/ifi/dbs/elki/database/relation/ConvertToStringView.java b/src/de/lmu/ifi/dbs/elki/database/relation/ConvertToStringView.java index 55015fa9..9d9ad672 100644 --- a/src/de/lmu/ifi/dbs/elki/database/relation/ConvertToStringView.java +++ b/src/de/lmu/ifi/dbs/elki/database/relation/ConvertToStringView.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.relation; 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/src/de/lmu/ifi/dbs/elki/database/relation/DBIDView.java b/src/de/lmu/ifi/dbs/elki/database/relation/DBIDView.java index 72b278a6..62a6fd36 100644 --- a/src/de/lmu/ifi/dbs/elki/database/relation/DBIDView.java +++ b/src/de/lmu/ifi/dbs/elki/database/relation/DBIDView.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.relation; 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/src/de/lmu/ifi/dbs/elki/database/relation/MaterializedRelation.java b/src/de/lmu/ifi/dbs/elki/database/relation/MaterializedRelation.java index 14aa54ea..af65e84d 100644 --- a/src/de/lmu/ifi/dbs/elki/database/relation/MaterializedRelation.java +++ b/src/de/lmu/ifi/dbs/elki/database/relation/MaterializedRelation.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.relation; 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/src/de/lmu/ifi/dbs/elki/database/relation/ProjectedView.java b/src/de/lmu/ifi/dbs/elki/database/relation/ProjectedView.java new file mode 100644 index 00000000..190b15c6 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/relation/ProjectedView.java @@ -0,0 +1,114 @@ +package de.lmu.ifi.dbs.elki.database.relation; + +import de.lmu.ifi.dbs.elki.data.projection.Projection; +import de.lmu.ifi.dbs.elki.data.type.SimpleTypeInformation; +import de.lmu.ifi.dbs.elki.database.Database; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDs; +import de.lmu.ifi.dbs.elki.result.AbstractHierarchicalResult; +import de.lmu.ifi.dbs.elki.utilities.iterator.IterableIterator; + +/* + 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/>. + */ + +/** + * Projected relation view (non-materialized) + * + * @author Erich Schubert + * + * @param <IN> Vector type + * @param <OUT> Vector type + */ +public class ProjectedView<IN, OUT> extends AbstractHierarchicalResult implements Relation<OUT> { + /** + * The wrapped representation where we get the IDs from. + */ + private final Relation<IN> inner; + + /** + * The projection we use. + */ + private Projection<IN, OUT> projection; + + /** + * Constructor. + * + * @param inner Inner relation + * @param projection Projection function + */ + public ProjectedView(Relation<IN> inner, Projection<IN, OUT> projection) { + super(); + this.inner = inner; + this.projection = projection; + } + + @Override + public String getLongName() { + return "projection"; + } + + @Override + public String getShortName() { + return "projection"; + } + + @Override + public Database getDatabase() { + return inner.getDatabase(); + } + + @Override + public OUT get(DBID id) { + return projection.project(inner.get(id)); + } + + @Override + public void set(DBID id, OUT val) { + throw new UnsupportedOperationException("Projections are read-only."); + } + + @Override + public void delete(DBID id) { + inner.delete(id); + } + + @Override + public SimpleTypeInformation<OUT> getDataTypeInformation() { + return projection.getOutputDataTypeInformation(); + } + + @Override + public DBIDs getDBIDs() { + return inner.getDBIDs(); + } + + @Override + public IterableIterator<DBID> iterDBIDs() { + return inner.iterDBIDs(); + } + + @Override + public int size() { + return inner.size(); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/relation/ProxyView.java b/src/de/lmu/ifi/dbs/elki/database/relation/ProxyView.java index e7a6396f..1ae761f3 100644 --- a/src/de/lmu/ifi/dbs/elki/database/relation/ProxyView.java +++ b/src/de/lmu/ifi/dbs/elki/database/relation/ProxyView.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.relation; 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 @@ -88,13 +88,13 @@ public class ProxyView<O> extends AbstractHierarchicalResult implements Relation @Override public O get(DBID id) { - assert (idview.contains(id)); + assert (idview.contains(id)) : "Accessing object not included in view."; return inner.get(id); } @Override public void set(DBID id, O val) { - assert (idview.contains(id)); + assert (idview.contains(id)) : "Accessing object not included in view."; inner.set(id, val); } diff --git a/src/de/lmu/ifi/dbs/elki/database/relation/Relation.java b/src/de/lmu/ifi/dbs/elki/database/relation/Relation.java index 75f91aa7..ebe1be3c 100644 --- a/src/de/lmu/ifi/dbs/elki/database/relation/Relation.java +++ b/src/de/lmu/ifi/dbs/elki/database/relation/Relation.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.relation; 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/src/de/lmu/ifi/dbs/elki/database/relation/package-info.java b/src/de/lmu/ifi/dbs/elki/database/relation/package-info.java index 2c9c0690..12ecf968 100644 --- a/src/de/lmu/ifi/dbs/elki/database/relation/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/relation/package-info.java @@ -5,7 +5,7 @@ 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 |