diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/database')
106 files changed, 3917 insertions, 2391 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/database/AbstractDatabase.java b/src/de/lmu/ifi/dbs/elki/database/AbstractDatabase.java index e0fc6bf2..b62db142 100644 --- a/src/de/lmu/ifi/dbs/elki/database/AbstractDatabase.java +++ b/src/de/lmu/ifi/dbs/elki/database/AbstractDatabase.java @@ -32,7 +32,7 @@ import java.util.ListIterator; import de.lmu.ifi.dbs.elki.data.type.NoSupportedDataTypeException; import de.lmu.ifi.dbs.elki.data.type.TypeInformation; 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.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; @@ -72,7 +72,7 @@ public abstract class AbstractDatabase extends AbstractHierarchicalResult implem * Key: {@code -db.index} * </p> */ - public static final OptionID INDEX_ID = OptionID.getOrCreateOptionID("db.index", "Database indexes to add."); + public static final OptionID INDEX_ID = new OptionID("db.index", "Database indexes to add."); /** * The event manager, collects events and fires them on demand. @@ -85,12 +85,12 @@ public abstract class AbstractDatabase extends AbstractHierarchicalResult implem protected final List<Relation<?>> relations = new java.util.Vector<Relation<?>>(); /** - * Indexes + * Indexes. */ protected final List<Index> indexes = new java.util.Vector<Index>(); /** - * Index factories + * Index factories. */ protected final Collection<IndexFactory<?, ?>> indexFactories = new java.util.Vector<IndexFactory<?, ?>>(); @@ -120,7 +120,7 @@ public abstract class AbstractDatabase extends AbstractHierarchicalResult implem } @Override - public SingleObjectBundle getBundle(DBID id) { + public SingleObjectBundle getBundle(DBIDRef id) { assert (id != null); // TODO: ensure that the ID actually exists in the database? try { @@ -302,5 +302,5 @@ public abstract class AbstractDatabase extends AbstractHierarchicalResult implem return "database"; } - abstract protected Logging getLogger(); + protected abstract Logging getLogger(); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/Database.java b/src/de/lmu/ifi/dbs/elki/database/Database.java index a931d5c8..e5b9f7ff 100644 --- a/src/de/lmu/ifi/dbs/elki/database/Database.java +++ b/src/de/lmu/ifi/dbs/elki/database/Database.java @@ -29,7 +29,7 @@ import de.lmu.ifi.dbs.elki.data.type.NoSupportedDataTypeException; 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.DBIDRef; 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; @@ -58,7 +58,7 @@ import de.lmu.ifi.dbs.elki.utilities.InspectionUtilFrequentlyScanned; * @apiviz.has RKNNQuery oneway - - provides * @apiviz.has Relation oneway - - contains * @apiviz.has Index oneway - - manages - * @apiviz.uses DataStoreListener oneway - - invokes + * @apiviz.has DataStoreListener oneway - - invokes */ public interface Database extends HierarchicalResult, InspectionUtilFrequentlyScanned { /** @@ -177,7 +177,7 @@ public interface Database extends HierarchicalResult, InspectionUtilFrequentlySc * @param id the id of the Object to be obtained from the Database * @return Bundle containing the objects' data */ - SingleObjectBundle getBundle(DBID id); + SingleObjectBundle getBundle(DBIDRef id); /** * Returns the DatabaseObject represented by the specified id. @@ -248,4 +248,4 @@ public interface Database extends HierarchicalResult, InspectionUtilFrequentlySc * @see DataStoreEvent */ void flushDataStoreEvents(); -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/database/DatabaseEventManager.java b/src/de/lmu/ifi/dbs/elki/database/DatabaseEventManager.java index 633be46f..ce6e4d9a 100644 --- a/src/de/lmu/ifi/dbs/elki/database/DatabaseEventManager.java +++ b/src/de/lmu/ifi/dbs/elki/database/DatabaseEventManager.java @@ -30,7 +30,7 @@ import javax.swing.event.EventListenerList; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreEvent;
import de.lmu.ifi.dbs.elki.database.datastore.DataStoreEvent.Type;
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.DBIDRef;
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.HashSetModifiableDBIDs;
@@ -175,8 +175,8 @@ public class DatabaseEventManager { * @see #fireObjectsChanged
* @see de.lmu.ifi.dbs.elki.database.datastore.DataStoreEvent.Type#INSERT
*/
- public void fireObjectInserted(DBID insertion) {
- fireObjectsChanged(insertion, DataStoreEvent.Type.INSERT);
+ public void fireObjectInserted(DBIDRef insertion) {
+ fireObjectChanged(insertion, DataStoreEvent.Type.INSERT);
}
/**
@@ -211,8 +211,8 @@ public class DatabaseEventManager { * @see #fireObjectsChanged
* @see de.lmu.ifi.dbs.elki.database.datastore.DataStoreEvent.Type#DELETE
*/
- protected void fireObjectRemoved(DBID deletion) {
- fireObjectsChanged(deletion, DataStoreEvent.Type.DELETE);
+ protected void fireObjectRemoved(DBIDRef deletion) {
+ fireObjectChanged(deletion, DataStoreEvent.Type.DELETE);
}
/**
@@ -245,6 +245,35 @@ public class DatabaseEventManager { }
/**
+ * Handles a DataStoreEvent with the specified type. If the current event type
+ * is not equal to the specified type, the events accumulated up to now will
+ * be fired first.
+ *
+ * The new event will be aggregated and fired on demand if
+ * {@link #accumulateDataStoreEvents} is set, otherwise all registered
+ * <code>DataStoreListener</code> will be notified immediately that the
+ * content of the database has been changed.
+ *
+ * @param object the object that has been changed, i.e. inserted, deleted
+ * or updated
+ */
+ private void fireObjectChanged(DBIDRef object, DataStoreEvent.Type type) {
+ // flush first
+ if(currentDataStoreEventType != null && !currentDataStoreEventType.equals(type)) {
+ flushDataStoreEvents();
+ }
+ if (this.dataStoreObjects == null) {
+ this.dataStoreObjects = DBIDUtil.newHashSet();
+ }
+ this.dataStoreObjects.add(object);
+ currentDataStoreEventType = type;
+
+ if(!accumulateDataStoreEvents) {
+ flushDataStoreEvents();
+ }
+ }
+
+ /**
* Informs all registered <code>ResultListener</code> that a new result was
* added.
*
diff --git a/src/de/lmu/ifi/dbs/elki/database/HashmapDatabase.java b/src/de/lmu/ifi/dbs/elki/database/HashmapDatabase.java index a92c4427..069de73e 100644 --- a/src/de/lmu/ifi/dbs/elki/database/HashmapDatabase.java +++ b/src/de/lmu/ifi/dbs/elki/database/HashmapDatabase.java @@ -32,6 +32,7 @@ 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.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; 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.HashSetModifiableDBIDs; @@ -42,6 +43,7 @@ import de.lmu.ifi.dbs.elki.datasource.DatabaseConnection; import de.lmu.ifi.dbs.elki.datasource.FileBasedDatabaseConnection; import de.lmu.ifi.dbs.elki.datasource.bundle.MultipleObjectsBundle; import de.lmu.ifi.dbs.elki.datasource.bundle.ObjectBundle; +import de.lmu.ifi.dbs.elki.datasource.bundle.SingleObjectBundle; import de.lmu.ifi.dbs.elki.index.Index; import de.lmu.ifi.dbs.elki.index.IndexFactory; import de.lmu.ifi.dbs.elki.logging.Logging; @@ -70,7 +72,7 @@ public class HashmapDatabase extends AbstractDatabase implements UpdatableDataba /** * Our logger */ - private static final Logging logger = Logging.getLogger(HashmapDatabase.class); + private static final Logging LOG = Logging.getLogger(HashmapDatabase.class); /** * IDs of this database @@ -102,7 +104,7 @@ public class HashmapDatabase extends AbstractDatabase implements UpdatableDataba this.addChildResult(idrep); // Add indexes. - if(indexFactories != null) { + if (indexFactories != null) { this.indexFactories.addAll(indexFactories); } } @@ -120,7 +122,7 @@ public class HashmapDatabase extends AbstractDatabase implements UpdatableDataba */ @Override public void initialize() { - if(databaseConnection != null) { + if (databaseConnection != null) { this.insert(databaseConnection.loadData()); // Run at most once. databaseConnection = null; @@ -129,7 +131,7 @@ public class HashmapDatabase extends AbstractDatabase implements UpdatableDataba @Override public DBIDs insert(ObjectBundle objpackages) { - if(objpackages.dataLength() == 0) { + if (objpackages.dataLength() == 0) { return DBIDUtil.EMPTYDBIDS; } // insert into db @@ -137,29 +139,28 @@ public class HashmapDatabase extends AbstractDatabase implements UpdatableDataba Relation<?>[] targets = alignColumns(objpackages); int idrepnr = -1; - for(int i = 0; i < targets.length; i++) { - if(targets[i] == idrep) { + for (int i = 0; i < targets.length; i++) { + if (targets[i] == idrep) { idrepnr = i; break; } } - for(int j = 0; j < objpackages.dataLength(); j++) { + for (int j = 0; j < objpackages.dataLength(); j++) { // insert object final DBID newid; - if(idrepnr < 0) { + if (idrepnr < 0) { newid = DBIDUtil.generateSingleDBID(); - } - else { + } else { newid = (DBID) objpackages.data(j, idrepnr); } - if(ids.contains(newid)) { + if (ids.contains(newid)) { throw new AbortException("Duplicate DBID conflict."); } ids.add(newid); - for(int i = 0; i < targets.length; i++) { + for (int i = 0; i < targets.length; i++) { // DBIDs were handled above. - if(i == idrepnr) { + if (i == idrepnr) { continue; } @SuppressWarnings("unchecked") @@ -170,7 +171,7 @@ public class HashmapDatabase extends AbstractDatabase implements UpdatableDataba } // Notify indexes of insertions - for(Index index : indexes) { + for (Index index : indexes) { index.insertAll(newids); } @@ -191,19 +192,19 @@ public class HashmapDatabase extends AbstractDatabase implements UpdatableDataba Relation<?>[] targets = new Relation<?>[pack.metaLength()]; { BitSet used = new BitSet(relations.size()); - for(int i = 0; i < targets.length; i++) { + for (int i = 0; i < targets.length; i++) { SimpleTypeInformation<?> meta = pack.meta(i); // TODO: aggressively try to match exact metas first? // Try to match unused representations only - for(int j = used.nextClearBit(0); j >= 0 && j < relations.size(); j = used.nextClearBit(j + 1)) { + for (int j = used.nextClearBit(0); j >= 0 && j < relations.size(); j = used.nextClearBit(j + 1)) { Relation<?> relation = relations.get(j); - if(relation.getDataTypeInformation().isAssignableFromType(meta)) { + if (relation.getDataTypeInformation().isAssignableFromType(meta)) { targets[i] = relation; used.set(j); break; } } - if(targets[i] == null) { + if (targets[i] == null) { targets[i] = addNewRelation(meta); used.set(relations.size() - 1); } @@ -225,8 +226,8 @@ public class HashmapDatabase extends AbstractDatabase implements UpdatableDataba relations.add(relation); getHierarchy().add(this, relation); // Try to add indexes where appropriate - for(IndexFactory<?, ?> factory : indexFactories) { - if(factory.getInputTypeRestriction().isAssignableFromType(meta)) { + for (IndexFactory<?, ?> factory : indexFactories) { + if (factory.getInputTypeRestriction().isAssignableFromType(meta)) { @SuppressWarnings("unchecked") final IndexFactory<Object, ?> ofact = (IndexFactory<Object, ?>) factory; @SuppressWarnings("unchecked") @@ -238,14 +239,16 @@ public class HashmapDatabase extends AbstractDatabase implements UpdatableDataba } /** - * Removes the objects from the database (by calling {@link #doDelete(DBID)} + * Removes the objects from the database (by calling {@link #doDelete(DBIDRef)} * for each object) and indexes and fires a deletion event. + * + * {@inheritDoc} */ @Override public MultipleObjectsBundle delete(DBIDs ids) { // Prepare bundle to return MultipleObjectsBundle bundle = new MultipleObjectsBundle(); - for(Relation<?> relation : relations) { + for (Relation<?> relation : relations) { ArrayList<Object> data = new ArrayList<Object>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { data.add(relation.get(iter)); @@ -254,11 +257,10 @@ public class HashmapDatabase extends AbstractDatabase implements UpdatableDataba } // remove from db for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - DBID id = iter.getDBID(); - doDelete(id); + doDelete(iter); } // Remove from indexes - for(Index index : indexes) { + for (Index index : indexes) { index.deleteAll(ids); } // fire deletion event @@ -268,35 +270,50 @@ public class HashmapDatabase extends AbstractDatabase implements UpdatableDataba } /** + * Removes the object from the database (by calling {@link #doDelete(DBIDRef)}) + * and indexes and fires a deletion event. + * + * {@inheritDoc} + */ + @Override + public SingleObjectBundle delete(DBIDRef id) { + // Prepare bundle to return + SingleObjectBundle bundle = new SingleObjectBundle(); + for (Relation<?> relation : relations) { + bundle.append(relation.getDataTypeInformation(), relation.get(id)); + } + doDelete(id); + // Remove from indexes + for (Index index : indexes) { + index.delete(id); + } + // fire deletion event + eventManager.fireObjectRemoved(id); + + return bundle; + } + + /** * Removes the object with the specified id from this database. * * @param id id the id of the object to be removed */ - private void doDelete(DBID id) { + private void doDelete(DBIDRef id) { // Remove id ids.remove(id); // Remove from all representations. - for(Relation<?> relation : relations) { + for (Relation<?> relation : relations) { // ID has already been removed, and this would loop... - if(relation != idrep) { + if (relation != idrep) { relation.delete(id); } } - restoreID(id); - } - - /** - * Makes the given id reusable for new insertion operations. - * - * @param id the id to become reusable - */ - private void restoreID(final DBID id) { DBIDFactory.FACTORY.deallocateSingleDBID(id); } @Override protected Logging getLogger() { - return logger; + return LOG; } /** @@ -322,12 +339,12 @@ public class HashmapDatabase extends AbstractDatabase implements UpdatableDataba super.makeOptions(config); // Get database connection. final ObjectParameter<DatabaseConnection> dbcP = new ObjectParameter<DatabaseConnection>(OptionID.DATABASE_CONNECTION, DatabaseConnection.class, FileBasedDatabaseConnection.class); - if(config.grab(dbcP)) { + if (config.grab(dbcP)) { databaseConnection = dbcP.instantiateClass(config); } // Get indexes. final ObjectListParameter<IndexFactory<?, ?>> indexFactoryP = new ObjectListParameter<IndexFactory<?, ?>>(INDEX_ID, IndexFactory.class, true); - if(config.grab(indexFactoryP)) { + if (config.grab(indexFactoryP)) { indexFactories = indexFactoryP.instantiateClasses(config); } } @@ -337,4 +354,4 @@ public class HashmapDatabase extends AbstractDatabase implements UpdatableDataba return new HashmapDatabase(databaseConnection, indexFactories); } } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ProxyDatabase.java b/src/de/lmu/ifi/dbs/elki/database/ProxyDatabase.java index 0f411cb4..3f41326a 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ProxyDatabase.java +++ b/src/de/lmu/ifi/dbs/elki/database/ProxyDatabase.java @@ -40,7 +40,7 @@ public class ProxyDatabase extends AbstractDatabase { /** * Logger class. */ - private static final Logging logger = Logging.getLogger(ProxyDatabase.class); + private static final Logging LOG = Logging.getLogger(ProxyDatabase.class); /** * Our DBIDs @@ -120,6 +120,6 @@ public class ProxyDatabase extends AbstractDatabase { @Override protected Logging getLogger() { - return logger; + return LOG; } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/StaticArrayDatabase.java b/src/de/lmu/ifi/dbs/elki/database/StaticArrayDatabase.java index 79143ad8..c2d66f5c 100644 --- a/src/de/lmu/ifi/dbs/elki/database/StaticArrayDatabase.java +++ b/src/de/lmu/ifi/dbs/elki/database/StaticArrayDatabase.java @@ -31,6 +31,7 @@ import de.lmu.ifi.dbs.elki.data.type.TypeUtil; 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.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.relation.DBIDView; import de.lmu.ifi.dbs.elki.database.relation.MaterializedRelation; @@ -67,7 +68,7 @@ public class StaticArrayDatabase extends AbstractDatabase implements Parameteriz /** * Our logger */ - private static final Logging logger = Logging.getLogger(StaticArrayDatabase.class); + private static final Logging LOG = Logging.getLogger(StaticArrayDatabase.class); /** * IDs of this database @@ -116,8 +117,8 @@ public class StaticArrayDatabase extends AbstractDatabase implements Parameteriz @Override public void initialize() { if(databaseConnection != null) { - if(logger.isDebugging()) { - logger.debugFine("Loading data from database connection."); + if(LOG.isDebugging()) { + LOG.debugFine("Loading data from database connection."); } MultipleObjectsBundle objpackages = databaseConnection.loadData(); // Run at most once. @@ -146,9 +147,9 @@ public class StaticArrayDatabase extends AbstractDatabase implements Parameteriz // insert into db - note: DBIDs should have been prepared before this! Relation<?>[] targets = alignColumns(objpackages); - for(int j = 0; j < objpackages.dataLength(); j++) { + DBIDIter newid = ids.iter(); + for(int j = 0; j < objpackages.dataLength(); j++, newid.advance()) { // insert object - final DBID newid = ids.get(j); for(int i = 0; i < targets.length; i++) { // DBIDs were handled above. if(i == idrepnr) { @@ -183,8 +184,8 @@ public class StaticArrayDatabase extends AbstractDatabase implements Parameteriz @Override public void addIndex(Index index) { - if(logger.isDebuggingFiner()) { - logger.debugFine("Adding index: " + index); + if(LOG.isDebuggingFiner()) { + LOG.debugFine("Adding index: " + index); } this.indexes.add(index); // TODO: actually add index to the representation used? @@ -256,7 +257,7 @@ public class StaticArrayDatabase extends AbstractDatabase implements Parameteriz @Override protected Logging getLogger() { - return logger; + return LOG; } /** diff --git a/src/de/lmu/ifi/dbs/elki/database/UpdatableDatabase.java b/src/de/lmu/ifi/dbs/elki/database/UpdatableDatabase.java index 56a988f8..86555a86 100644 --- a/src/de/lmu/ifi/dbs/elki/database/UpdatableDatabase.java +++ b/src/de/lmu/ifi/dbs/elki/database/UpdatableDatabase.java @@ -23,8 +23,10 @@ package de.lmu.ifi.dbs.elki.database; along with this program. If not, see <http://www.gnu.org/licenses/>. */ +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.datasource.bundle.ObjectBundle; +import de.lmu.ifi.dbs.elki.datasource.bundle.SingleObjectBundle; import de.lmu.ifi.dbs.elki.utilities.exceptions.UnableToComplyException; /** @@ -52,4 +54,14 @@ public interface UpdatableDatabase extends Database { * @throws UnableToComplyException if deletion is not possible */ ObjectBundle delete(DBIDs ids); + + /** + * Removes and returns the specified objects with the given ids from the + * database. + * + * @param id the id of the object to be removed from the database + * @return the object that have been removed + * @throws UnableToComplyException if deletion is not possible + */ + SingleObjectBundle delete(DBIDRef id); }
\ 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/datastore/DBIDDataStore.java index 2f596f47..7941219f 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveIteratorAdapter.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/DBIDDataStore.java @@ -1,4 +1,4 @@ -package de.lmu.ifi.dbs.elki.database.ids.integer; +package de.lmu.ifi.dbs.elki.database.datastore; /* This file is part of ELKI: @@ -23,44 +23,30 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; 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; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; /** - * Adapter for using GNU Trove iterators. + * DBID-valued data store (avoids boxing/unboxing). * * @author Erich Schubert */ -class TroveIteratorAdapter implements Iterator<DBID> { +public interface DBIDDataStore extends DataStore<DBID> { /** - * The actual iterator. + * Getter, but using objects. + * + * @deprecated Use {@link #assignVar} and a {@link DBIDVar} instead, to avoid boxing/unboxing cost. */ - private TIntIterator iterator; + @Override + @Deprecated + public DBID get(DBIDRef id); /** - * Constructor. + * Retrieves an object from the storage. * - * @param iterator Trove iterator + * @param id Database ID. + * @param var Variable to update. */ - 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 + public void assignVar(DBIDRef id, DBIDVar var); +} 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 2ed9f536..aca5b86f 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreFactory.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreFactory.java @@ -46,27 +46,27 @@ public interface DataStoreFactory { /** * Storage will be used only temporary. */ - public final static int HINT_TEMP = 0x01; + public static final int HINT_TEMP = 0x01; /** * "Hot" data, that will be used a lot, preferring memory storage. */ - public final static int HINT_HOT = 0x02; + public static final int HINT_HOT = 0x02; /** * "static" data, that will not change often */ - public final static int HINT_STATIC = 0x04; + public static final int HINT_STATIC = 0x04; /** * Data that might require sorted access (so hashmaps are suboptimal) */ - public final static int HINT_SORTED = 0x08; + public static final int HINT_SORTED = 0x08; /** * Data that is the main database. Includes HOT, STATIC, SORTED */ - public final static int HINT_DB = 0x1E; + public static final int HINT_DB = 0x1E; /** * Make a new storage, to associate the given ids with an object of class @@ -88,6 +88,16 @@ public interface DataStoreFactory { * @param hints Hints for the storage manager * @return new data store */ + public WritableDBIDDataStore makeDBIDStorage(DBIDs ids, int hints); + + /** + * 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); /** 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 dada881a..cba8e4c9 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreIDMap.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreIDMap.java @@ -32,10 +32,10 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; */ public interface DataStoreIDMap { /** - * Map a DBID to a database id. + * Map a DBID to an array offset. * * @param dbid DBID * @return record id {@code id >= 0} */ - public int map(DBIDRef dbid); + int mapDBIDToOffset(DBIDRef dbid); } 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 a8afeaec..a9052f87 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreUtil.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/DataStoreUtil.java @@ -26,16 +26,18 @@ package de.lmu.ifi.dbs.elki.database.datastore; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; /** - * Storage utility class. Mostly a shorthand for {@link DataStoreFactory#FACTORY}. + * Storage utility class. Mostly a shorthand for + * {@link DataStoreFactory#FACTORY}. * * @author Erich Schubert - * + * * @apiviz.landmark * @apiviz.composedOf de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory */ public final class DataStoreUtil { /** - * 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 @@ -46,9 +48,22 @@ public final class DataStoreUtil { public static <T> WritableDataStore<T> makeStorage(DBIDs ids, int hints, Class<? super T> dataclass) { return DataStoreFactory.FACTORY.makeStorage(ids, hints, 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 static WritableDBIDDataStore makeDBIDStorage(DBIDs ids, int hints) { + return DataStoreFactory.FACTORY.makeDBIDStorage(ids, hints); + } + /** - * 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 ids DBIDs to store data for * @param hints Hints for the storage manager @@ -57,9 +72,10 @@ public final class DataStoreUtil { public static WritableDoubleDataStore makeDoubleStorage(DBIDs ids, int hints) { return DataStoreFactory.FACTORY.makeDoubleStorage(ids, hints); } - + /** - * 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 ids DBIDs to store data for * @param hints Hints for the storage manager @@ -69,9 +85,10 @@ public final class DataStoreUtil { public static WritableDoubleDataStore makeDoubleStorage(DBIDs ids, int hints, double def) { return DataStoreFactory.FACTORY.makeDoubleStorage(ids, hints, def); } - + /** - * 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 ids DBIDs to store data for * @param hints Hints for the storage manager @@ -80,9 +97,10 @@ public final class DataStoreUtil { public static WritableIntegerDataStore makeIntegerStorage(DBIDs ids, int hints) { return DataStoreFactory.FACTORY.makeIntegerStorage(ids, hints); } - + /** - * 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 ids DBIDs to store data for * @param hints Hints for the storage manager @@ -92,9 +110,10 @@ public final class DataStoreUtil { public static WritableIntegerDataStore makeIntegerStorage(DBIDs ids, int hints, int def) { return DataStoreFactory.FACTORY.makeIntegerStorage(ids, hints, def); } - + /** - * 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 @@ -104,4 +123,4 @@ public final class DataStoreUtil { public static WritableRecordStore makeRecordStorage(DBIDs ids, int hints, Class<?>... dataclasses) { return DataStoreFactory.FACTORY.makeRecordStorage(ids, hints, dataclasses); } -}
\ 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/DoubleDistanceDataStore.java index e00f9ff8..f74b681a 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/RangeIDMap.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/DoubleDistanceDataStore.java @@ -23,31 +23,29 @@ package de.lmu.ifi.dbs.elki.database.datastore; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; /** - * Mapping a static DBID range to storage IDs. + * Double-valued data store (avoids boxing/unboxing). * * @author Erich Schubert */ -public class RangeIDMap implements DataStoreIDMap { +public interface DoubleDistanceDataStore extends DataStore<DoubleDistance> { /** - * Start offset + * Getter, but using objects. + * + * @deprecated Use {@link #doubleValue} instead, to avoid boxing/unboxing cost. */ - final DBIDRange range; - + @Override + @Deprecated + public DoubleDistance get(DBIDRef id); + /** - * Constructor from a static DBID range allocation. + * Retrieves an object from the storage. * - * @param range DBID range to use + * @param id Database ID. + * @return Double value */ - public RangeIDMap(DBIDRange range) { - this.range = range; - } - - @Override - public int map(DBIDRef dbid) { - return range.getOffset(dbid); - } -} + public double doubleValue(DBIDRef id); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/datastore/WritableDBIDDataStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/WritableDBIDDataStore.java new file mode 100644 index 00000000..960b79ac --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/WritableDBIDDataStore.java @@ -0,0 +1,63 @@ +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) 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.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; + +/** + * Data store specialized for doubles. Avoids boxing/unboxing. + * + * @author Erich Schubert + */ +public interface WritableDBIDDataStore extends DBIDDataStore, WritableDataStore<DBID> { + /** + * Setter, but using materialized DBIDs. + * + * @deprecated Use {@link #putDBID} instead, to avoid boxing/unboxing cost. + */ + @Override + @Deprecated + public DBID put(DBIDRef id, DBID 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. + */ + public void putDBID(DBIDRef id, DBIDRef 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. + */ + public void put(DBIDRef id, DBIDRef value); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/datastore/WritableDoubleDistanceDataStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/WritableDoubleDistanceDataStore.java new file mode 100644 index 00000000..03a3e75e --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/WritableDoubleDistanceDataStore.java @@ -0,0 +1,65 @@ +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) 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.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; + +/** + * Data store specialized for doubles. Avoids boxing/unboxing. + * + * @author Erich Schubert + */ +public interface WritableDoubleDistanceDataStore extends DoubleDistanceDataStore, WritableDataStore<DoubleDistance> { + /** + * Setter, but using objects. + * + * @deprecated Use {@link #putDouble} instead, to avoid boxing/unboxing cost. + */ + @Override + @Deprecated + public DoubleDistance put(DBIDRef id, DoubleDistance 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(DBIDRef 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(DBIDRef id, double value); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayDBIDStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayDBIDStore.java new file mode 100644 index 00000000..c9bc6438 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayDBIDStore.java @@ -0,0 +1,125 @@ +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.WritableDBIDDataStore; +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.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; + +/** + * 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 ArrayDBIDStore implements WritableDBIDDataStore { + /** + * Data array + */ + private ArrayModifiableDBIDs data; + + /** + * DBID to index map + */ + private DataStoreIDMap idmap; + + /** + * Constructor. + * + * @param size Size + * @param idmap ID map + */ + public ArrayDBIDStore(int size, DataStoreIDMap idmap) { + super(); + this.data = DBIDUtil.newArray(size); + // Initialize + DBIDRef inv = DBIDUtil.invalid(); + for (int i = 0; i < size; i++) { + data.add(inv); + } + this.idmap = idmap; + } + + @Override + @Deprecated + public DBID get(DBIDRef id) { + try { + return data.get(idmap.mapDBIDToOffset(id)); + } catch (ArrayIndexOutOfBoundsException e) { + return null; + } + } + + @Override + public void assignVar(DBIDRef id, DBIDVar var) { + data.assign(idmap.mapDBIDToOffset(id), var); + } + + @Override + @Deprecated + public DBID put(DBIDRef id, DBID value) { + final int off = idmap.mapDBIDToOffset(id); + DBID ret = data.get(off); + data.set(off, value); + return ret; + } + + @Override + public void putDBID(DBIDRef id, DBIDRef value) { + final int off = idmap.mapDBIDToOffset(id); + data.set(off, value); + } + + @Override + public void put(DBIDRef id, DBIDRef value) { + final int off = idmap.mapDBIDToOffset(id); + data.set(off, value); + } + + @Override + public void destroy() { + data = null; + idmap = null; + } + + @Override + public void delete(DBIDRef id) { + throw new UnsupportedOperationException("Can't delete from a static array storage."); + } + + @Override + public String getLongName() { + return "raw"; + } + + @Override + public String getShortName() { + return "raw"; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayDoubleDistanceStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayDoubleDistanceStore.java new file mode 100644 index 00000000..99ec1382 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayDoubleDistanceStore.java @@ -0,0 +1,138 @@ +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 java.util.Arrays; + +import de.lmu.ifi.dbs.elki.database.datastore.DataStoreIDMap; +import de.lmu.ifi.dbs.elki.database.datastore.WritableDoubleDistanceDataStore; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; + +/** + * 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 ArrayDoubleDistanceStore implements WritableDoubleDistanceDataStore { + /** + * Data array + */ + private double[] data; + + /** + * DBID to index map + */ + private DataStoreIDMap idmap; + + /** + * Constructor. + * + * @param size Size + * @param idmap ID map + */ + public ArrayDoubleDistanceStore(int size, DataStoreIDMap idmap) { + this(size, idmap, Double.NaN); + } + + /** + * Constructor. + * + * @param size Size + * @param idmap ID map + * @param def Default value + */ + public ArrayDoubleDistanceStore(int size, DataStoreIDMap idmap, double def) { + super(); + this.data = new double[size]; + if(def != 0) { + Arrays.fill(this.data, def); + } + this.idmap = idmap; + } + + @Override + @Deprecated + public DoubleDistance get(DBIDRef id) { + try { + return new DoubleDistance(data[idmap.mapDBIDToOffset(id)]); + } + catch(ArrayIndexOutOfBoundsException e) { + return null; + } + } + + @Override + @Deprecated + public DoubleDistance put(DBIDRef id, DoubleDistance value) { + final int off = idmap.mapDBIDToOffset(id); + double ret = data[off]; + data[off] = value.doubleValue(); + return new DoubleDistance(ret); + } + + @Override + public double doubleValue(DBIDRef id) { + return data[idmap.mapDBIDToOffset(id)]; + } + + @Override + public double putDouble(DBIDRef id, double value) { + final int off = idmap.mapDBIDToOffset(id); + final double ret = data[off]; + data[off] = value; + return ret; + } + + @Override + public double put(DBIDRef id, double value) { + final int off = idmap.mapDBIDToOffset(id); + final double ret = data[off]; + data[off] = value; + return ret; + } + + @Override + public void destroy() { + data = null; + idmap = null; + } + + @Override + public void delete(DBIDRef 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/ArrayDoubleStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayDoubleStore.java index de22a6b3..1d8920bf 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayDoubleStore.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayDoubleStore.java @@ -77,7 +77,7 @@ public class ArrayDoubleStore implements WritableDoubleDataStore { @Deprecated public Double get(DBIDRef id) { try { - return data[idmap.map(id)]; + return Double.valueOf(data[idmap.mapDBIDToOffset(id)]); } catch(ArrayIndexOutOfBoundsException e) { return null; @@ -87,20 +87,20 @@ public class ArrayDoubleStore implements WritableDoubleDataStore { @Override @Deprecated public Double put(DBIDRef id, Double value) { - final int off = idmap.map(id); + final int off = idmap.mapDBIDToOffset(id); double ret = data[off]; - data[off] = value; - return ret; + data[off] = value.doubleValue(); + return Double.valueOf(ret); } @Override public double doubleValue(DBIDRef id) { - return data[idmap.map(id)]; + return data[idmap.mapDBIDToOffset(id)]; } @Override public double putDouble(DBIDRef id, double value) { - final int off = idmap.map(id); + final int off = idmap.mapDBIDToOffset(id); final double ret = data[off]; data[off] = value; return ret; @@ -108,7 +108,7 @@ public class ArrayDoubleStore implements WritableDoubleDataStore { @Override public double put(DBIDRef id, double value) { - final int off = idmap.map(id); + final int off = idmap.mapDBIDToOffset(id); final double ret = data[off]; data[off] = value; return ret; diff --git a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayIntegerStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayIntegerStore.java index 8caa7ec3..bb250164 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayIntegerStore.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/ArrayIntegerStore.java @@ -77,7 +77,7 @@ public class ArrayIntegerStore implements WritableIntegerDataStore { @Deprecated public Integer get(DBIDRef id) { try { - return data[idmap.map(id)]; + return Integer.valueOf(data[idmap.mapDBIDToOffset(id)]); } catch(ArrayIndexOutOfBoundsException e) { return null; @@ -87,20 +87,20 @@ public class ArrayIntegerStore implements WritableIntegerDataStore { @Override @Deprecated public Integer put(DBIDRef id, Integer value) { - final int off = idmap.map(id); + final int off = idmap.mapDBIDToOffset(id); int ret = data[off]; - data[off] = value; - return ret; + data[off] = value.intValue(); + return Integer.valueOf(ret); } @Override public int intValue(DBIDRef id) { - return data[idmap.map(id)]; + return data[idmap.mapDBIDToOffset(id)]; } @Override public int putInt(DBIDRef id, int value) { - final int off = idmap.map(id); + final int off = idmap.mapDBIDToOffset(id); final int ret = data[off]; data[off] = value; return ret; @@ -108,7 +108,7 @@ public class ArrayIntegerStore implements WritableIntegerDataStore { @Override public int put(DBIDRef id, int value) { - final int off = idmap.map(id); + final int off = idmap.mapDBIDToOffset(id); final int ret = data[off]; data[off] = value; return ret; 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 6e578b61..4dd9a684 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 @@ -75,7 +75,7 @@ public class ArrayRecordStore implements WritableRecordStore { @SuppressWarnings("unchecked") protected <T> T get(DBIDRef id, int index) { try { - return (T) data[idmap.map(id)][index]; + return (T) data[idmap.mapDBIDToOffset(id)][index]; } catch(ArrayIndexOutOfBoundsException e) { return null; @@ -98,8 +98,8 @@ public class ArrayRecordStore implements WritableRecordStore { */ @SuppressWarnings("unchecked") protected <T> T set(DBIDRef id, int index, T value) { - T ret = (T) data[idmap.map(id)][index]; - data[idmap.map(id)][index] = value; + T ret = (T) data[idmap.mapDBIDToOffset(id)][index]; + data[idmap.mapDBIDToOffset(id)][index] = value; return ret; } 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 a7ce310b..29658818 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 @@ -38,17 +38,20 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; */ public class ArrayStore<T> implements WritableDataStore<T> { /** - * Data array + * Data array. */ private Object[] data; /** - * DBID to index map + * DBID to index map. */ private DataStoreIDMap idmap; /** * Constructor. + * + * @param data Data array + * @param idmap DBID to offset mapping */ public ArrayStore(Object[] data, DataStoreIDMap idmap) { super(); @@ -60,7 +63,7 @@ public class ArrayStore<T> implements WritableDataStore<T> { @Override public T get(DBIDRef id) { try { - return (T) data[idmap.map(id)]; + return (T) data[idmap.mapDBIDToOffset(id)]; } catch(ArrayIndexOutOfBoundsException e) { return null; @@ -76,7 +79,7 @@ public class ArrayStore<T> implements WritableDataStore<T> { @Override public T put(DBIDRef id, T value) { T ret = get(id); - data[idmap.map(id)] = value; + data[idmap.mapDBIDToOffset(id)] = value; return ret; } diff --git a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDDBIDStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDDBIDStore.java new file mode 100644 index 00000000..565d0848 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDDBIDStore.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.TIntIntMap; +import gnu.trove.map.hash.TIntIntHashMap; +import de.lmu.ifi.dbs.elki.database.datastore.WritableDBIDDataStore; +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.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; + +/** + * Writable data store for double values. + * + * @author Erich Schubert + */ +public class MapIntegerDBIDDBIDStore implements WritableDBIDDataStore { + /** + * Data storage. + */ + private TIntIntMap map; + + /** + * Constructor. + * + * @param size Expected size + */ + public MapIntegerDBIDDBIDStore(int size) { + super(); + map = new TIntIntHashMap(size, 0.5f, Integer.MIN_VALUE, DBIDUtil.invalid().internalGetIndex()); + } + + @Override + @Deprecated + public DBID get(DBIDRef id) { + return DBIDUtil.importInteger(map.get(DBIDUtil.asInteger(id))); + } + + @Override + public String getLongName() { + return "raw"; + } + + @Override + public String getShortName() { + return "raw"; + } + + @Override + @Deprecated + public DBID put(DBIDRef id, DBID value) { + return DBIDUtil.importInteger(map.put(id.internalGetIndex(), value.internalGetIndex())); + } + + @Override + public void destroy() { + map.clear(); + map = null; + } + + @Override + public void delete(DBIDRef id) { + map.remove(DBIDUtil.asInteger(id)); + } + + @Override + public void put(DBIDRef id, DBIDRef value) { + map.put(id.internalGetIndex(), value.internalGetIndex()); + } + + @Override + public void putDBID(DBIDRef id, DBIDRef value) { + map.put(id.internalGetIndex(), value.internalGetIndex()); + } + + @Override + public void assignVar(DBIDRef id, DBIDVar var) { + final int val = map.get(id.internalGetIndex()); + DBIDFactory.FACTORY.assignVar(var, val); + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDDoubleDistanceStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDDoubleDistanceStore.java new file mode 100644 index 00000000..82570639 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDDoubleDistanceStore.java @@ -0,0 +1,111 @@ +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.WritableDoubleDistanceDataStore; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; + +/** + * Writable data store for double values. + * + * @author Erich Schubert + */ +public class MapIntegerDBIDDoubleDistanceStore implements WritableDoubleDistanceDataStore { + /** + * Data storage. + */ + private TIntDoubleMap map; + + /** + * Constructor. + * + * @param size Expected size + */ + public MapIntegerDBIDDoubleDistanceStore(int size) { + this(size, Double.NaN); + } + + /** + * Constructor. + * + * @param size Expected size + * @param def Default value + */ + public MapIntegerDBIDDoubleDistanceStore(int size, double def) { + super(); + map = new TIntDoubleHashMap(size, 0.5f, Integer.MIN_VALUE, def); + } + + @Override + @Deprecated + public DoubleDistance get(DBIDRef id) { + return new DoubleDistance(map.get(DBIDUtil.asInteger(id))); + } + + @Override + public double doubleValue(DBIDRef id) { + return map.get(DBIDUtil.asInteger(id)); + } + + @Override + public String getLongName() { + return "raw"; + } + + @Override + public String getShortName() { + return "raw"; + } + + @Override + @Deprecated + public DoubleDistance put(DBIDRef id, DoubleDistance value) { + return new DoubleDistance(map.put(DBIDUtil.asInteger(id), value.doubleValue())); + } + + @Override + public void destroy() { + map.clear(); + map = null; + } + + @Override + public void delete(DBIDRef id) { + map.remove(DBIDUtil.asInteger(id)); + } + + @Override + public double putDouble(DBIDRef id, double value) { + return map.put(DBIDUtil.asInteger(id), value); + } + + @Override + public double put(DBIDRef id, double value) { + return map.put(DBIDUtil.asInteger(id), value); + } +} 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 index f9f8d48a..944f9710 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDDoubleStore.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDDoubleStore.java @@ -27,6 +27,7 @@ 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.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; /** * Writable data store for double values. @@ -35,7 +36,7 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; */ public class MapIntegerDBIDDoubleStore implements WritableDoubleDataStore { /** - * Data storage + * Data storage. */ private TIntDoubleMap map; @@ -62,12 +63,12 @@ public class MapIntegerDBIDDoubleStore implements WritableDoubleDataStore { @Override @Deprecated public Double get(DBIDRef id) { - return map.get(id.getIntegerID()); + return Double.valueOf(map.get(DBIDUtil.asInteger(id))); } @Override public double doubleValue(DBIDRef id) { - return map.get(id.getIntegerID()); + return map.get(DBIDUtil.asInteger(id)); } @Override @@ -83,7 +84,7 @@ public class MapIntegerDBIDDoubleStore implements WritableDoubleDataStore { @Override @Deprecated public Double put(DBIDRef id, Double value) { - return map.put(id.getIntegerID(), value); + return Double.valueOf(map.put(DBIDUtil.asInteger(id), value.doubleValue())); } @Override @@ -94,16 +95,16 @@ public class MapIntegerDBIDDoubleStore implements WritableDoubleDataStore { @Override public void delete(DBIDRef id) { - map.remove(id.getIntegerID()); + map.remove(DBIDUtil.asInteger(id)); } @Override public double putDouble(DBIDRef id, double value) { - return map.put(id.getIntegerID(), value); + return map.put(DBIDUtil.asInteger(id), value); } @Override public double put(DBIDRef id, double value) { - return map.put(id.getIntegerID(), value); + return map.put(DBIDUtil.asInteger(id), value); } } diff --git a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDIntegerStore.java b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDIntegerStore.java index f7aea633..f31c97f9 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDIntegerStore.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDIntegerStore.java @@ -27,6 +27,7 @@ import gnu.trove.map.TIntIntMap; import gnu.trove.map.hash.TIntIntHashMap; import de.lmu.ifi.dbs.elki.database.datastore.WritableIntegerDataStore; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; /** * Writable data store for double values. @@ -35,7 +36,7 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; */ public class MapIntegerDBIDIntegerStore implements WritableIntegerDataStore { /** - * Data storage + * Data storage. */ private TIntIntMap map; @@ -62,12 +63,12 @@ public class MapIntegerDBIDIntegerStore implements WritableIntegerDataStore { @Override @Deprecated public Integer get(DBIDRef id) { - return map.get(id.getIntegerID()); + return Integer.valueOf(map.get(DBIDUtil.asInteger(id))); } @Override public int intValue(DBIDRef id) { - return map.get(id.getIntegerID()); + return map.get(DBIDUtil.asInteger(id)); } @Override @@ -83,7 +84,7 @@ public class MapIntegerDBIDIntegerStore implements WritableIntegerDataStore { @Override @Deprecated public Integer put(DBIDRef id, Integer value) { - return map.put(id.getIntegerID(), value); + return Integer.valueOf(map.put(DBIDUtil.asInteger(id), value.intValue())); } @Override @@ -94,16 +95,16 @@ public class MapIntegerDBIDIntegerStore implements WritableIntegerDataStore { @Override public void delete(DBIDRef id) { - map.remove(id.getIntegerID()); + map.remove(DBIDUtil.asInteger(id)); } @Override public int putInt(DBIDRef id, int value) { - return map.put(id.getIntegerID(), value); + return map.put(DBIDUtil.asInteger(id), value); } @Override public int put(DBIDRef id, int value) { - return map.put(id.getIntegerID(), value); + return map.put(DBIDUtil.asInteger(id), 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 index 805c6de3..2926f14c 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDRecordStore.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDRecordStore.java @@ -28,6 +28,7 @@ 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.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; /** * A class to answer representation queries using a map and an index within the @@ -39,12 +40,12 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; */ public class MapIntegerDBIDRecordStore implements WritableRecordStore { /** - * Record length + * Record length. */ private final int rlen; /** - * Storage Map + * Storage Map. */ private final TIntObjectMap<Object[]> data; @@ -86,15 +87,16 @@ public class MapIntegerDBIDRecordStore implements WritableRecordStore { } /** - * Actual getter + * Actual getter. * * @param id Database ID * @param index column index + * @param <T> type * @return current value */ @SuppressWarnings("unchecked") protected <T> T get(DBIDRef id, int index) { - Object[] d = data.get(id.getIntegerID()); + Object[] d = data.get(DBIDUtil.asInteger(id)); if(d == null) { return null; } @@ -110,19 +112,20 @@ public class MapIntegerDBIDRecordStore implements WritableRecordStore { } /** - * Actual setter + * Actual setter. * * @param id Database ID * @param index column index * @param value new value + * @param <T> type * @return previous value */ @SuppressWarnings("unchecked") protected <T> T set(DBIDRef id, int index, T value) { - Object[] d = data.get(id.getIntegerID()); + Object[] d = data.get(DBIDUtil.asInteger(id)); if(d == null) { d = new Object[rlen]; - data.put(id.getIntegerID(), d); + data.put(DBIDUtil.asInteger(id), d); } T ret = (T) d[index]; d[index] = value; @@ -186,6 +189,6 @@ public class MapIntegerDBIDRecordStore implements WritableRecordStore { @Override public boolean remove(DBIDRef id) { - return data.remove(id.getIntegerID()) != null; + return data.remove(DBIDUtil.asInteger(id)) != 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 index e04027d0..236389e4 100644 --- a/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDStore.java +++ b/src/de/lmu/ifi/dbs/elki/database/datastore/memory/MapIntegerDBIDStore.java @@ -27,6 +27,7 @@ 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.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; /** * A class to answer representation queries using a map. Basically, it is just a @@ -38,7 +39,7 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; */ public class MapIntegerDBIDStore<T> implements WritableDataStore<T> { /** - * Storage Map + * Storage Map. */ private TIntObjectMap<T> data; @@ -71,15 +72,15 @@ public class MapIntegerDBIDStore<T> implements WritableDataStore<T> { @Override public T get(DBIDRef id) { - return data.get(id.getIntegerID()); + return data.get(DBIDUtil.asInteger(id)); } @Override public T put(DBIDRef id, T value) { if(value == null) { - return data.remove(id.getIntegerID()); + return data.remove(DBIDUtil.asInteger(id)); } - return data.put(id.getIntegerID(), value); + return data.put(DBIDUtil.asInteger(id), value); } @Override @@ -89,7 +90,7 @@ public class MapIntegerDBIDStore<T> implements WritableDataStore<T> { @Override public void delete(DBIDRef id) { - data.remove(id.getIntegerID()); + data.remove(DBIDUtil.asInteger(id)); } @Override 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 05cf3697..20778327 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 @@ -30,6 +30,7 @@ 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; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; /** * A class to answer representation queries using a map and an index within the @@ -41,12 +42,12 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; */ public class MapRecordStore implements WritableRecordStore { /** - * Record length + * Record length. */ private final int rlen; /** - * Storage Map + * Storage Map. */ // TODO: Use trove maps? private final Map<DBID, Object[]> data; @@ -79,15 +80,16 @@ public class MapRecordStore implements WritableRecordStore { } /** - * Actual getter + * Actual getter. * * @param id Database ID * @param index column index + * @param <T> type * @return current value */ @SuppressWarnings("unchecked") protected <T> T get(DBIDRef id, int index) { - Object[] d = data.get(id.getDBID()); + Object[] d = data.get(DBIDUtil.deref(id)); if(d == null) { return null; } @@ -103,19 +105,20 @@ public class MapRecordStore implements WritableRecordStore { } /** - * Actual setter + * Actual setter. * * @param id Database ID * @param index column index * @param value new value + * @param <T> type * @return previous value */ @SuppressWarnings("unchecked") protected <T> T set(DBIDRef id, int index, T value) { - Object[] d = data.get(id.getDBID()); + Object[] d = data.get(DBIDUtil.deref(id)); if(d == null) { d = new Object[rlen]; - data.put(id.getDBID(), d); + data.put(DBIDUtil.deref(id), d); } T ret = (T) d[index]; d[index] = value; 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 90742993..9818afd2 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 @@ -29,6 +29,7 @@ import java.util.Map; import de.lmu.ifi.dbs.elki.database.datastore.WritableDataStore; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; /** * A class to answer representation queries using a map. Basically, it is just a @@ -40,9 +41,8 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; */ public class MapStore<T> implements WritableDataStore<T> { /** - * Storage Map + * Storage Map. */ - // TODO: use trove maps? private Map<DBID, T> data; /** @@ -65,15 +65,15 @@ public class MapStore<T> implements WritableDataStore<T> { @Override public T get(DBIDRef id) { - return data.get(id.getDBID()); + return data.get(DBIDUtil.deref(id)); } @Override public T put(DBIDRef id, T value) { if(value == null) { - return data.remove(id.getDBID()); + return data.remove(DBIDUtil.deref(id)); } - return data.put(id.getDBID(), value); + return data.put(DBIDUtil.deref(id), value); } @Override 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 683e4c5d..06a80fd7 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 @@ -24,13 +24,15 @@ 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.WritableDBIDDataStore; 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.WritableDoubleDistanceDataStore; import de.lmu.ifi.dbs.elki.database.datastore.WritableIntegerDataStore; 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; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; /** * Simple factory class that will store all data in memory using object arrays @@ -51,6 +53,9 @@ public class MemoryDataStoreFactory implements DataStoreFactory { @SuppressWarnings("unchecked") @Override public <T> WritableDataStore<T> makeStorage(DBIDs ids, int hints, Class<? super T> dataclass) { + if (DoubleDistance.class.equals(dataclass)) { + return (WritableDataStore<T>) makeDoubleDistanceStorage(ids, hints); + } if (Double.class.equals(dataclass)) { return (WritableDataStore<T>) makeDoubleStorage(ids, hints); } @@ -60,7 +65,7 @@ public class MemoryDataStoreFactory implements DataStoreFactory { if(ids instanceof DBIDRange) { DBIDRange range = (DBIDRange) ids; Object[] data = new Object[range.size()]; - return new ArrayStore<T>(data, new RangeIDMap(range)); + return new ArrayStore<T>(data, range); } else { return new MapIntegerDBIDStore<T>(ids.size()); @@ -68,10 +73,38 @@ public class MemoryDataStoreFactory implements DataStoreFactory { } @Override + public WritableDBIDDataStore makeDBIDStorage(DBIDs ids, int hints) { + if(ids instanceof DBIDRange) { + DBIDRange range = (DBIDRange) ids; + return new ArrayDBIDStore(range.size(), range); + } + else { + return new MapIntegerDBIDDBIDStore(ids.size()); + } + } + + /** + * Make a data storage for double distances. + * + * @param ids IDs to store for + * @param hints Storage hints + * @return double distance storage + */ + public WritableDoubleDistanceDataStore makeDoubleDistanceStorage(DBIDs ids, int hints) { + if(ids instanceof DBIDRange) { + DBIDRange range = (DBIDRange) ids; + return new ArrayDoubleDistanceStore(range.size(), range); + } + else { + return new MapIntegerDBIDDoubleDistanceStore(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)); + return new ArrayDoubleStore(range.size(), range); } else { return new MapIntegerDBIDDoubleStore(ids.size()); @@ -82,7 +115,7 @@ public class MemoryDataStoreFactory implements DataStoreFactory { public WritableDoubleDataStore makeDoubleStorage(DBIDs ids, int hints, double def) { if(ids instanceof DBIDRange) { DBIDRange range = (DBIDRange) ids; - return new ArrayDoubleStore(range.size(), new RangeIDMap(range), def); + return new ArrayDoubleStore(range.size(), range, def); } else { return new MapIntegerDBIDDoubleStore(ids.size(), def); @@ -93,7 +126,7 @@ public class MemoryDataStoreFactory implements DataStoreFactory { public WritableIntegerDataStore makeIntegerStorage(DBIDs ids, int hints) { if(ids instanceof DBIDRange) { DBIDRange range = (DBIDRange) ids; - return new ArrayIntegerStore(range.size(), new RangeIDMap(range)); + return new ArrayIntegerStore(range.size(), range); } else { return new MapIntegerDBIDIntegerStore(ids.size()); @@ -104,7 +137,7 @@ public class MemoryDataStoreFactory implements DataStoreFactory { public WritableIntegerDataStore makeIntegerStorage(DBIDs ids, int hints, int def) { if(ids instanceof DBIDRange) { DBIDRange range = (DBIDRange) ids; - return new ArrayIntegerStore(range.size(), new RangeIDMap(range), def); + return new ArrayIntegerStore(range.size(), range, def); } else { return new MapIntegerDBIDIntegerStore(ids.size(), def); @@ -116,7 +149,7 @@ public class MemoryDataStoreFactory implements DataStoreFactory { if(ids instanceof DBIDRange) { DBIDRange range = (DBIDRange) ids; Object[][] data = new Object[range.size()][dataclasses.length]; - return new ArrayRecordStore(data, new RangeIDMap(range)); + return new ArrayRecordStore(data, range); } else { return new MapIntegerDBIDRecordStore(ids.size(), dataclasses.length); 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 dccd8d4e..e5b4a259 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 @@ -18,6 +18,7 @@ * }</pre> * * @apiviz.exclude datastore.memory + * @apiviz.exclude index.preprocessed */ /* This file is part of ELKI: @@ -41,4 +42,4 @@ 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/>. */ -package de.lmu.ifi.dbs.elki.database.datastore;
\ No newline at end of file +package de.lmu.ifi.dbs.elki.database.datastore; 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 68bbb83d..7e9c55c0 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/ArrayDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/ArrayDBIDs.java @@ -27,23 +27,35 @@ package de.lmu.ifi.dbs.elki.database.ids; * Interface for array based DBIDs. * * @author Erich Schubert + * + * @apiviz.has DBIDArrayIter */ public interface ArrayDBIDs extends DBIDs { /** * Get the i'th entry (starting at 0) * + * If possible, use an {@link DBIDArrayIter} via {@link #iter()} instead! + * * @param i Index * @return DBID of i'th entry. */ public DBID get(int i); /** + * Assign a DBID variable the value of position {@code index}. + * + * @param index Position + * @param var Variable to assign the value to. + */ + public void assign(int index, DBIDVar var); + + /** * Iterable * * @return Iterator */ @Override - public DBIDIter iter(); + public DBIDArrayIter iter(); /** * Size of the DBID "collection". 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 95bcc2f7..ffac393b 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/ArrayModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/ArrayModifiableDBIDs.java @@ -29,6 +29,8 @@ import java.util.Comparator; * Array-oriented implementation of a modifiable DBID collection. * * @author Erich Schubert + * + * @apiviz.has DBIDArrayMIter */ public interface ArrayModifiableDBIDs extends ModifiableDBIDs, ArrayDBIDs { /** @@ -41,7 +43,16 @@ public interface ArrayModifiableDBIDs extends ModifiableDBIDs, ArrayDBIDs { * * @param comparator Comparator to use */ - void sort(Comparator<? super DBID> comparator); + void sort(Comparator<? super DBIDRef> comparator); + + /** + * Sort the DBID set. + * + * @param start Starting index, for partial sorting + * @param end End index, for partial sorting (exclusive) + * @param comparator Comparator to use + */ + void sort(int start, int end, Comparator<? super DBIDRef> comparator); /** * Remove the i'th entry (starting at 0) @@ -58,8 +69,8 @@ public interface ArrayModifiableDBIDs extends ModifiableDBIDs, ArrayDBIDs { * @param newval New value * @return previous value */ - public DBID set(int i, DBID newval); - + public DBID set(int i, DBIDRef newval); + /** * Swap DBIDs add positions a and b. * @@ -67,4 +78,7 @@ public interface ArrayModifiableDBIDs extends ModifiableDBIDs, ArrayDBIDs { * @param b Second position */ public void swap(int a, int b); -}
\ No newline at end of file + + @Override + public DBIDArrayMIter iter(); +} 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 8d98893d..5abf4377 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBID.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBID.java @@ -37,25 +37,7 @@ package de.lmu.ifi.dbs.elki.database.ids; * * @apiviz.landmark */ -public interface DBID extends DBIDRef, Comparable<DBIDRef>, ArrayDBIDs { - /** - * Compare the <em>current</em> value of two referenced DBIDs. - * - * @param other Other DBID reference (or DBID) - * @return {@code true} when the references <em>currently</em> refer to the same. - */ - @Override - public boolean sameDBID(DBIDRef other); - - /** - * Compare two objects by the value of the referenced DBID. - * - * @param other Other DBID or object - * @return -1, 0 or +1 - */ - @Override - public int compareDBID(DBIDRef other); - +public interface DBID extends DBIDRef, Comparable<DBIDRef>, ArrayDBIDs, SetDBIDs { /** * In contrast to {@link DBIDRef}, the DBID interface is supposed to have a * stable hash code. However, it is generally preferred to use optimized @@ -64,40 +46,29 @@ public interface DBID extends DBIDRef, Comparable<DBIDRef>, ArrayDBIDs { * @return hash code */ @Override - public int hashCode(); + int hashCode(); /** * In contrast to {@link DBIDRef}, the DBID interface is supposed to have a * stable equals for other DBIDs. * - * Yet, {@link #sameDBID} is more type safe and explicit. + * Yet, {@link DBIDUtil#equal} is more type safe and explicit. * + * @param obj Other object * @return true when the object is the same DBID. */ @Override - public boolean equals(Object obj); - - /** - * Part of the DBIDRef API, this <em>must</em> return {@code this} for an - * actual DBID. - * - * @return {@code this} - * @deprecated When the object is known to be a DBID, the usage of this method - * is pointless, therefore it is marked as deprecated to cause a - * warning. - */ @Deprecated - @Override - public DBID getDBID(); + boolean equals(Object obj); /** * Compare two DBIDs for ordering. * - * Consider using {@link #compareDBID}, which is more explicit. + * Consider using {@link DBIDUtil#compare}, which is more explicit. * * @param other Other DBID object * @return Comparison result */ @Override - public int compareTo(DBIDRef other); + int compareTo(DBIDRef other); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/DistanceDBIDResult.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDArrayIter.java index ead3eebc..fefe5ad1 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/DistanceDBIDResult.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDArrayIter.java @@ -1,4 +1,4 @@ -package de.lmu.ifi.dbs.elki.database.query; +package de.lmu.ifi.dbs.elki.database.ids; /* This file is part of ELKI: @@ -22,20 +22,13 @@ package de.lmu.ifi.dbs.elki.database.query; 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.List; - -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.utilities.iterator.ArrayIter; /** - * Collection of objects and their distances. + * Array iterators that can also go backwards and seek. * * @author Erich Schubert - * - * @apiviz.composedOf DistanceResultPair - * - * @param <D> Distance type */ -public interface DistanceDBIDResult<D extends Distance<D>> extends List<DistanceResultPair<D>> { - // Empty. TODO: add "sorted" property? +public interface DBIDArrayIter extends DBIDIter, ArrayIter { + // Nothing added - see {@link ArrayIter}! } diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDArrayMIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDArrayMIter.java new file mode 100644 index 00000000..1de202a2 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDArrayMIter.java @@ -0,0 +1,33 @@ +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/>. + */ + +/** + * Modifiable array iterator. + * + * @author Erich Schubert + */ +public interface DBIDArrayMIter extends DBIDArrayIter, DBIDMIter { + // Nothing new, see {@link DBIDArrayIter} and {@link DBIDMIter} +}
\ No newline at end of file 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 6063508b..646e6e4d 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDFactory.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDFactory.java @@ -24,6 +24,7 @@ package de.lmu.ifi.dbs.elki.database.ids; */ import de.lmu.ifi.dbs.elki.database.ids.integer.TrivialDBIDFactory; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; @@ -47,29 +48,49 @@ public interface DBIDFactory { /** * Static DBID factory to use. */ - public static DBIDFactory FACTORY = new TrivialDBIDFactory(); - + final static DBIDFactory FACTORY = new TrivialDBIDFactory(); + /** - * Import an integer ID + * Make a new DBID variable. + * + * @param val Initial value. + * @return Variable + */ + DBIDVar newVar(DBIDRef val); + + /** + * Import and integer as DBID. + * + * Note: this may not be possible for some factories! * * @param id Integer ID to import * @return DBID */ - public DBID importInteger(int id); + DBID importInteger(int id); /** - * Generate a single DBID + * Assign an integer value to a DBID variable. + * + * Note: this may not be possible for some factories! + * + * @param var Variable + * @param val Integer value + */ + void assignVar(DBIDVar var, int val); + + /** + * Generate a single DBID. * * @return A single DBID */ - public DBID generateSingleDBID(); + DBID generateSingleDBID(); /** * Return a single DBID for reuse. * * @param id DBID to deallocate */ - public void deallocateSingleDBID(DBID id); + void deallocateSingleDBID(DBIDRef id); /** * Generate a static DBID range. @@ -77,14 +98,14 @@ public interface DBIDFactory { * @param size Requested size * @return DBID range */ - public DBIDRange generateStaticDBIDRange(int size); + DBIDRange generateStaticDBIDRange(int size); /** * Deallocate a static DBID range. * * @param range Range to deallocate */ - public void deallocateDBIDRange(DBIDRange range); + void deallocateDBIDRange(DBIDRange range); /** * Make a DBID pair from two existing DBIDs. @@ -94,72 +115,133 @@ public interface DBIDFactory { * * @return new pair. */ - public DBIDPair makePair(DBIDRef id1, DBIDRef id2); - + DBIDPair newPair(DBIDRef id1, DBIDRef id2); + + /** + * Make a double-DBID pair. + * + * @param val Double value + * @param id DBID + * @return New pair + */ + DoubleDBIDPair newPair(double val, DBIDRef id); + + /** + * Make a new distance-DBID pair. + * + * @param val Distance value + * @param id Object ID + * @param <D> Distance type + * @return New pair + */ + <D extends Distance<D>> DistanceDBIDPair<D> newDistancePair(D val, DBIDRef id); + + /** + * Make a new distance-DBID pair. + * + * @param val Distance value + * @param id Object ID + * @return New pair + */ + DoubleDistanceDBIDPair newDistancePair(double val, DBIDRef id); + /** * Make a new (modifiable) array of DBIDs. * * @return New array */ - public ArrayModifiableDBIDs newArray(); - + ArrayModifiableDBIDs newArray(); + /** * Make a new (modifiable) hash set of DBIDs. * * @return New hash set */ - public HashSetModifiableDBIDs newHashSet(); - + HashSetModifiableDBIDs newHashSet(); + /** * Make a new (modifiable) array of DBIDs. * * @param size Size hint * @return New array */ - public ArrayModifiableDBIDs newArray(int size); - + ArrayModifiableDBIDs newArray(int size); + /** * Make a new (modifiable) hash set of DBIDs. * * @param size Size hint * @return New hash set */ - public HashSetModifiableDBIDs newHashSet(int size); - + HashSetModifiableDBIDs newHashSet(int size); + /** * Make a new (modifiable) array of DBIDs. * * @param existing existing DBIDs to use * @return New array */ - public ArrayModifiableDBIDs newArray(DBIDs existing); - + ArrayModifiableDBIDs newArray(DBIDs existing); + /** * Make a new (modifiable) hash set of DBIDs. * * @param existing existing DBIDs to use * @return New hash set */ - public HashSetModifiableDBIDs newHashSet(DBIDs existing); - + HashSetModifiableDBIDs newHashSet(DBIDs existing); + /** - * Get a serializer for DBIDs + * Get a serializer for DBIDs. * - * @return DBID serializer + * @return DBID serializer */ - public ByteBufferSerializer<DBID> getDBIDSerializer(); - + ByteBufferSerializer<DBID> getDBIDSerializer(); + /** - * Get a serializer for DBIDs with static size + * Get a serializer for DBIDs with static size. * * @return DBID serializer */ - public FixedSizeByteBufferSerializer<DBID> getDBIDSerializerStatic(); - + FixedSizeByteBufferSerializer<DBID> getDBIDSerializerStatic(); + /** - * Get type restriction + * Get type restriction. * * @return type restriction for DBIDs */ - public Class<? extends DBID> getTypeRestriction(); -}
\ No newline at end of file + Class<? extends DBID> getTypeRestriction(); + + /** + * Compare two DBIDs, for sorting. + * + * @param a First + * @param b Second + * @return Comparison result + */ + int compare(DBIDRef a, DBIDRef b); + + /** + * Compare two DBIDs, for equality testing. + * + * @param a First + * @param b Second + * @return Comparison result + */ + boolean equal(DBIDRef a, DBIDRef b); + + /** + * Print a DBID as string. + * + * @param id DBID reference + * @return Formatted ID + */ + String toString(DBIDRef id); + + /** + * Get the invalid DBID value, usable as "undefined" placeholder. + * + * @return Invalid value + */ + DBIDRef invalid(); +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDIter.java index f2d0ae91..268f4441 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDIter.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDIter.java @@ -38,7 +38,8 @@ import de.lmu.ifi.dbs.elki.utilities.iterator.Iter; * <pre> * {@code * for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - * iter.getDBID(); + * Object o = relation.get(iter); // Many interfaces allow direct use + * DBID id = DBIDUtil.deref(iter); // Materialize only if you need to! * } * } * </pre> @@ -53,16 +54,9 @@ import de.lmu.ifi.dbs.elki.utilities.iterator.Iter; * </ul> * * @author Erich Schubert + * + * @apiviz.landmark */ public interface DBIDIter extends DBIDRef, Iter { - /** - * Get the referenced {@link DBID}. - * - * Efficiency note: this may require materialization of a DBID object - if - * possible, use DBIDRef based APIs instead. - * - * @return referenced DBID - */ - @Override - public DBID getDBID(); + // Empty - use as DBIDRef or Iter }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDMIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDMIter.java index fe3b182c..9f42c5a0 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDMIter.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDMIter.java @@ -1,4 +1,5 @@ package de.lmu.ifi.dbs.elki.database.ids; + /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures @@ -22,17 +23,21 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ +import de.lmu.ifi.dbs.elki.utilities.iterator.MIter; + /** * Modifiable DBID iterator. * * @author Erich Schubert */ -public interface DBIDMIter extends DBIDIter { +public interface DBIDMIter extends DBIDIter, MIter { /** * Remove the object the iterator currently points to. * - * Subsequent calls to {@link #getDBID} may return a different element. - * Call {@link #advance()} to advance the iterator to the next element for further processing. + * Note: Subsequent calls to {@link DBIDUtil#deref} may return a different + * element. Call {@link #advance()} to advance the iterator to the next + * element for further processing. */ + @Override void remove(); } 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 1b9ccc3b..8f7e428d 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDRange.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDRange.java @@ -1,5 +1,7 @@ package de.lmu.ifi.dbs.elki.database.ids; +import de.lmu.ifi.dbs.elki.database.datastore.DataStoreIDMap; + /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures @@ -28,7 +30,7 @@ package de.lmu.ifi.dbs.elki.database.ids; * * @author Erich Schubert */ -public interface DBIDRange extends ArrayStaticDBIDs { +public interface DBIDRange extends ArrayStaticDBIDs, DataStoreIDMap { /** * Get offset in the array for a particular DBID. * @@ -38,5 +40,5 @@ public interface DBIDRange extends ArrayStaticDBIDs { * @param dbid ID to compute index for * @return index */ - public int getOffset(DBIDRef dbid); + int getOffset(DBIDRef dbid); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDRef.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDRef.java index 0934b10b..fce87c31 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDRef.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDRef.java @@ -31,28 +31,27 @@ package de.lmu.ifi.dbs.elki.database.ids; * are a good example how the DBIDRef may change. * * @author Erich Schubert + * + * @apiviz.landmark + * + * @apiviz.has DBID oneway - - «references» */ public interface DBIDRef { /** - * Get the referenced {@link DBID}. + * Get the internal index. * - * Efficiency note: this may require materialization of a DBID object. + * <b>NOT FOR PUBLIC USE - ELKI Optimization engine only</b> * - * @return referenced DBID + * @return Internal index */ - public DBID getDBID(); - - /** - * Return the integer value of the object ID, if possible. - * - * @return integer id - */ - public int getIntegerID(); - + int internalGetIndex(); + /** * WARNING: Hash codes of this interface <b>might not be stable</b> (e.g. for * iterators). * + * Use {@link DBIDUtil#deref} to get an object with a stable hash code! + * * @return current hash code (<b>may change!</b>) * * @deprecated Do not use this hash code. Some implementations will not offer @@ -60,33 +59,19 @@ public interface DBIDRef { */ @Override @Deprecated - public int hashCode(); + int hashCode(); /** * WARNING: calling equality on a reference may be an indicator of incorrect * usage, as it is not clear whether the programmer meant the references to be * the same or the DBIDs. * + * Use {@link DBIDUtil#equal} or {@link DBIDUtil#compare}! + * * @param obj Object to compare with * @return True when they are the same object */ @Override @Deprecated - public boolean equals(Object obj); - - /** - * Compare the <em>current</em> value of two referenced DBIDs. - * - * @param other Other DBID reference (or DBID) - * @return {@code true} when the references <em>currently</em> refer to the same. - */ - public boolean sameDBID(DBIDRef other); - - /** - * Compare two objects by the value of the referenced DBID. - * - * @param other Other DBID or object - * @return -1, 0 or +1 - */ - public int compareDBID(DBIDRef other); + boolean equals(Object obj); }
\ No newline at end of file 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 000659b9..9cb4082a 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDUtil.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDUtil.java @@ -27,7 +27,13 @@ import java.util.Random; import de.lmu.ifi.dbs.elki.database.ids.generic.UnmodifiableArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.generic.UnmodifiableDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.integer.IntegerDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.integer.TroveArrayDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.integer.UnmodifiableIntegerArrayDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.integer.UnmodifiableIntegerDBIDs; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; +import de.lmu.ifi.dbs.elki.utilities.RandomFactory; /** * DBID Utility functions. @@ -35,7 +41,11 @@ import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; * @author Erich Schubert * * @apiviz.landmark - * @apiviz.composedOf de.lmu.ifi.dbs.elki.database.ids.DBIDFactory + * + * @apiviz.has DBID + * @apiviz.has DBIDs + * @apiviz.uses DBIDRef + * @apiviz.composedOf DBIDFactory */ public final class DBIDUtil { /** @@ -51,9 +61,20 @@ public final class DBIDUtil { public static final EmptyDBIDs EMPTYDBIDS = new EmptyDBIDs(); /** - * Import an Integer DBID. + * Get the invalid special ID. + * + * @return invalid ID value + */ + public static DBIDRef invalid() { + return DBIDFactory.FACTORY.invalid(); + } + + /** + * Import and integer as DBID. * - * @param id Integer ID + * Note: this may not be possible for some factories! + * + * @param id Integer ID to import * @return DBID */ public static DBID importInteger(int id) { @@ -61,25 +82,102 @@ public final class DBIDUtil { } /** - * Get a serializer for DBIDs + * Export a DBID as int. + * + * Note: this may not be possible for some factories! + * + * @param id DBID to export + * @return integer value + */ + public static int asInteger(DBIDRef id) { + return id.internalGetIndex(); + } + + /** + * Compare two DBIDs. + * + * @param id1 First ID + * @param id2 Second ID + * @return Comparison result + */ + public static int compare(DBIDRef id1, DBIDRef id2) { + return DBIDFactory.FACTORY.compare(id1, id2); + } + + /** + * Test two DBIDs for equality. + * + * @param id1 First ID + * @param id2 Second ID + * @return Comparison result + */ + public static boolean equal(DBIDRef id1, DBIDRef id2) { + return DBIDFactory.FACTORY.equal(id1, id2); + } + + /** + * Dereference a DBID reference. + * + * @param ref DBID reference + * @return DBID + */ + public static DBID deref(DBIDRef ref) { + if (ref instanceof DBID) { + return (DBID) ref; + } + return importInteger(ref.internalGetIndex()); + } + + /** + * Format a DBID as string. + * + * @param id DBID + * @return String representation + */ + public static String toString(DBIDRef id) { + return DBIDFactory.FACTORY.toString(id); + } + + /** + * Format a DBID as string. + * + * @param ids DBIDs + * @return String representation + */ + public static String toString(DBIDs ids) { + if (ids instanceof DBID) { + return DBIDFactory.FACTORY.toString((DBID) ids); + } + StringBuilder buf = new StringBuilder(); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + if (buf.length() > 0) { + buf.append(", "); + } + buf.append(DBIDFactory.FACTORY.toString(iter)); + } + return buf.toString(); + } + + /** + * Get a serializer for DBIDs. * * @return DBID serializer */ - public ByteBufferSerializer<DBID> getDBIDSerializer() { + public static ByteBufferSerializer<DBID> getDBIDSerializer() { return DBIDFactory.FACTORY.getDBIDSerializer(); } /** - * Get a serializer for DBIDs with static size + * Get a serializer for DBIDs with static size. * * @return DBID serializer */ - public ByteBufferSerializer<DBID> getDBIDSerializerStatic() { + public static ByteBufferSerializer<DBID> getDBIDSerializerStatic() { return DBIDFactory.FACTORY.getDBIDSerializerStatic(); } /** - * Generate a single DBID + * Generate a single DBID. * * @return A single DBID */ @@ -116,6 +214,25 @@ public final class DBIDUtil { } /** + * Make a new DBID variable. + * + * @param val Initial value. + * @return Variable + */ + public static DBIDVar newVar(DBIDRef val) { + return DBIDFactory.FACTORY.newVar(val); + } + + /** + * Make a new DBID variable. + * + * @return Variable + */ + public static DBIDVar newVar() { + return DBIDFactory.FACTORY.newVar(DBIDFactory.FACTORY.invalid()); + } + + /** * Make a new (modifiable) array of DBIDs. * * @return New array @@ -180,14 +297,14 @@ public final class DBIDUtil { * @param second Second set * @return result. */ - // TODO: optimize? + // TODO: optimize better? public static ModifiableDBIDs intersection(DBIDs first, DBIDs second) { - if(first.size() > second.size()) { + if (first.size() > second.size()) { return intersection(second, first); } ModifiableDBIDs inter = newHashSet(first.size()); - for(DBIDIter it = first.iter(); it.valid(); it.advance()) { - if(second.contains(it)) { + for (DBIDIter it = first.iter(); it.valid(); it.advance()) { + if (second.contains(it)) { inter.add(it); } } @@ -195,6 +312,26 @@ public final class DBIDUtil { } /** + * Compute the set intersection size of two sets. + * + * @param first First set + * @param second Second set + * @return size + */ + public static int intersectionSize(DBIDs first, DBIDs second) { + if (first.size() > second.size()) { + return intersectionSize(second, first); + } + int c = 0; + for (DBIDIter it = first.iter(); it.valid(); it.advance()) { + if (second.contains(it)) { + c++; + } + } + return c; + } + + /** * Compute the set symmetric intersection of two sets. * * @param first First set @@ -205,18 +342,18 @@ public final class DBIDUtil { */ // TODO: optimize? public static void symmetricIntersection(DBIDs first, DBIDs second, HashSetModifiableDBIDs firstonly, HashSetModifiableDBIDs intersection, HashSetModifiableDBIDs secondonly) { - if(first.size() > second.size()) { + if (first.size() > second.size()) { symmetricIntersection(second, first, secondonly, intersection, firstonly); return; } - assert(firstonly.size() == 0) : "OUTPUT set should be empty!"; - assert(intersection.size() == 0) : "OUTPUT set should be empty!"; - assert(secondonly.size() == 0) : "OUTPUT set should be empty!"; + assert (firstonly.size() == 0) : "OUTPUT set should be empty!"; + assert (intersection.size() == 0) : "OUTPUT set should be empty!"; + assert (secondonly.size() == 0) : "OUTPUT set should be empty!"; // Initialize with second secondonly.addDBIDs(second); - for(DBIDIter it = first.iter(); it.valid(); it.advance()) { + for (DBIDIter it = first.iter(); it.valid(); it.advance()) { // Try to remove - if(secondonly.remove(it)) { + if (secondonly.remove(it)) { intersection.add(it); } else { firstonly.add(it); @@ -258,27 +395,31 @@ public final class DBIDUtil { * @return Unmodifiable collection */ public static StaticDBIDs makeUnmodifiable(DBIDs existing) { - if(existing instanceof StaticDBIDs) { + if (existing instanceof StaticDBIDs) { return (StaticDBIDs) existing; } + if (existing instanceof TroveArrayDBIDs) { + return new UnmodifiableIntegerArrayDBIDs((TroveArrayDBIDs) existing); + } + if (existing instanceof IntegerDBIDs) { + return new UnmodifiableIntegerDBIDs((IntegerDBIDs) existing); + } if (existing instanceof ArrayDBIDs) { - return new UnmodifiableArrayDBIDs((ArrayDBIDs)existing); - } else { - return new UnmodifiableDBIDs(existing); + return new UnmodifiableArrayDBIDs((ArrayDBIDs) existing); } + return new UnmodifiableDBIDs(existing); } /** * Ensure that the given DBIDs are array-indexable. * - * @param ids + * @param ids IDs * @return Array DBIDs. */ public static ArrayDBIDs ensureArray(DBIDs ids) { - if(ids instanceof ArrayDBIDs) { + if (ids instanceof ArrayDBIDs) { return (ArrayDBIDs) ids; - } - else { + } else { return newArray(ids); } } @@ -286,33 +427,31 @@ public final class DBIDUtil { /** * Ensure that the given DBIDs support fast "contains" operations. * - * @param ids - * @return Array DBIDs. + * @param ids IDs + * @return Set DBIDs. */ public static SetDBIDs ensureSet(DBIDs ids) { - if(ids instanceof SetDBIDs) { + if (ids instanceof SetDBIDs) { return (SetDBIDs) ids; - } - else { + } else { return newHashSet(ids); } } /** - * Ensure modifiable + * Ensure modifiable. * - * @param ids - * @return Array DBIDs. + * @param ids IDs + * @return Modifiable DBIDs. */ public static ModifiableDBIDs ensureModifiable(DBIDs ids) { - if(ids instanceof ModifiableDBIDs) { + if (ids instanceof ModifiableDBIDs) { return (ModifiableDBIDs) ids; - } - else { - if(ids instanceof ArrayDBIDs) { + } else { + if (ids instanceof ArrayDBIDs) { return newArray(ids); } - if(ids instanceof HashSetDBIDs) { + if (ids instanceof HashSetDBIDs) { return newHashSet(ids); } return newArray(ids); @@ -328,11 +467,91 @@ public final class DBIDUtil { * @return DBID pair */ public static DBIDPair newPair(DBIDRef id1, DBIDRef id2) { - return DBIDFactory.FACTORY.makePair(id1, id2); + return DBIDFactory.FACTORY.newPair(id1, id2); + } + + /** + * Make a DoubleDBIDPair. + * + * @param val double value + * @param id ID + * @return new pair + */ + public static DoubleDBIDPair newPair(double val, DBIDRef id) { + return DBIDFactory.FACTORY.newPair(val, id); + } + + /** + * Make a DistanceDBIDPair. + * + * @param dist Distance value + * @param id ID + * @return new pair + */ + public static <D extends Distance<D>> DistanceDBIDPair<D> newDistancePair(D dist, DBIDRef id) { + return DBIDFactory.FACTORY.newDistancePair(dist, id); + } + + /** + * Make a DoubleDistanceDBIDPair. + * + * @param dist Distance value + * @param id ID + * @return new pair + */ + public static DoubleDistanceDBIDPair newDistancePair(double dist, DBIDRef id) { + return DBIDFactory.FACTORY.newDistancePair(dist, id); } /** - * Produce a random sample of the given DBIDs + * Produce a random sample of the given DBIDs. + * + * @param source Original DBIDs + * @param k k Parameter + * @param rnd Random generator + * @return new DBIDs + */ + public static ModifiableDBIDs randomSample(DBIDs source, int k, RandomFactory rnd) { + return randomSample(source, k, rnd.getRandom()); + } + + /** + * Produce a random shuffling of the given DBID array. + * + * @param ids Original DBIDs + * @param rnd Random generator + */ + public static void randomShuffle(ArrayModifiableDBIDs ids, RandomFactory rnd) { + randomShuffle(ids, rnd.getRandom(), ids.size()); + } + + /** + * Produce a random shuffling of the given DBID array. + * + * @param ids Original DBIDs + * @param random Random generator + */ + public static void randomShuffle(ArrayModifiableDBIDs ids, Random random) { + randomShuffle(ids, random, ids.size()); + } + + /** + * Produce a random shuffling of the given DBID array. + * + * Only the first {@code limit} elements will be randomized. + * + * @param ids Original DBIDs + * @param random Random generator + * @param limit Shuffling limit. + */ + public static void randomShuffle(ArrayModifiableDBIDs ids, Random random, final int limit) { + for (int i = 1; i < limit; i++) { + ids.swap(i - 1, i + random.nextInt(limit - i)); + } + } + + /** + * Produce a random sample of the given DBIDs. * * @param source Original DBIDs * @param k k Parameter @@ -340,11 +559,11 @@ public final class DBIDUtil { * @return new DBIDs */ public static ModifiableDBIDs randomSample(DBIDs source, int k, int seed) { - return randomSample(source, k, (long) seed); + return randomSample(source, k, new Random(seed)); } /** - * Produce a random sample of the given DBIDs + * Produce a random sample of the given DBIDs. * * @param source Original DBIDs * @param k k Parameter @@ -352,39 +571,47 @@ public final class DBIDUtil { * @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+ " > "+source.size()+" or < 0"); + if (seed != null) { + return randomSample(source, k, new Random(seed.longValue())); + } else { + return randomSample(source, k, new Random()); } - final Random random; - if(seed != null) { - random = new Random(seed); + } + + /** + * Produce a random sample of the given DBIDs. + * + * @param source Original DBIDs + * @param k k Parameter + * @param random Random generator + * @return new DBIDs + */ + public static ModifiableDBIDs randomSample(DBIDs source, int k, Random random) { + if (k <= 0 || k > source.size()) { + throw new IllegalArgumentException("Illegal value for size of random sample: " + k + " > " + source.size() + " or < 0"); } - else { + if (random == null) { random = new Random(); } // TODO: better balancing for different sizes // Two methods: constructive vs. destructive - if(k < source.size() / 2) { + if (k < source.size() >> 1) { ArrayDBIDs aids = DBIDUtil.ensureArray(source); + DBIDArrayIter iter = aids.iter(); HashSetModifiableDBIDs sample = DBIDUtil.newHashSet(k); - while(sample.size() < k) { - sample.add(aids.get(random.nextInt(aids.size()))); + while (sample.size() < k) { + iter.seek(random.nextInt(aids.size())); + sample.add(iter); } return sample; - } - else { + } else { ArrayModifiableDBIDs sample = DBIDUtil.newArray(source); - while(sample.size() > k) { - // Element to remove - int idx = random.nextInt(sample.size()); - // Remove last element - DBID last = sample.remove(sample.size() - 1); - // Replace target element: - if(idx < sample.size()) { - sample.set(idx, last); - } + randomShuffle(sample, random, k); + // Delete trailing elements + for (int i = sample.size() - 1; i > k; i--) { + sample.remove(i); } return sample; } } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDVar.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDVar.java new file mode 100644 index 00000000..b66ae5f5 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDVar.java @@ -0,0 +1,42 @@ +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/>. + */ + +/** + * (Persistent) variable storing a DBID reference. + * + * In contrast to the {@link DBIDRef} API, which are read-only references, this + * variable can be updated to point to a different DBID, e.g. the current best + * candidate. + * + * @author Erich Schubert + */ +public interface DBIDVar extends DBIDRef, ArrayDBIDs, SetDBIDs { + /** + * Assign a new value for the reference. + * + * @param ref Reference + */ + void set(DBIDRef ref); +} 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 e9a3e0ab..0b9db136 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDs.java @@ -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.Iterator; /** * Interface for a collection of database references (IDs). @@ -34,7 +33,7 @@ import java.util.Iterator; * @apiviz.composedOf DBID * @apiviz.has DBIDIter */ -public interface DBIDs extends Iterable<DBID> { +public interface DBIDs { /** * Get a DBID iterator (a more efficient API). * @@ -73,13 +72,4 @@ public interface DBIDs extends Iterable<DBID> { * @return true when empty. */ public boolean isEmpty(); - - /** - * Classic iterator. - * - * @deprecated Use {@link DBIDIter} API instead. - */ - @Override - @Deprecated - public Iterator<DBID> iterator(); -} +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceDBIDList.java b/src/de/lmu/ifi/dbs/elki/database/ids/DistanceDBIDPair.java index 2283c401..01a1f407 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceDBIDList.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DistanceDBIDPair.java @@ -1,4 +1,4 @@ -package de.lmu.ifi.dbs.elki.database.query; +package de.lmu.ifi.dbs.elki.database.ids; /* This file is part of ELKI: @@ -23,46 +23,30 @@ package de.lmu.ifi.dbs.elki.database.query; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.ArrayList; -import java.util.Collection; - import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** - * Default class to keep a list of distance-object pairs. + * Pair containing a distance an an object ID * - * @author Erich Schubert + * Note: there is no getter for the object, as this is a {@link DBIDRef}. * - * @param <D> Distance type + * @author Erich Schubert + * + * @param <D> Distance */ -public class GenericDistanceDBIDList<D extends Distance<D>> extends ArrayList<DistanceResultPair<D>> implements DistanceDBIDResult<D> { - /** - * Serialization Version - */ - private static final long serialVersionUID = 1L; - +public interface DistanceDBIDPair<D extends Distance<D>> extends DBIDRef { /** - * Constructor. - */ - public GenericDistanceDBIDList() { - super(); - } - - /** - * Constructor. + * Get the distance. * - * @param c existing collection + * @return Distance */ - public GenericDistanceDBIDList(Collection<? extends DistanceResultPair<D>> c) { - super(c); - } - + public D getDistance(); + /** - * Constructor. + * Compare to another result, by distance, smaller first. * - * @param initialCapacity Capacity + * @param other Other result + * @return Comparison result */ - public GenericDistanceDBIDList(int initialCapacity) { - super(initialCapacity); - } -}
\ No newline at end of file + public int compareByDistance(DistanceDBIDPair<D> other); +} diff --git a/src/de/lmu/ifi/dbs/elki/database/query/DistanceResultPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/DoubleDBIDPair.java index b6cc129b..06210076 100644 --- a/src/de/lmu/ifi/dbs/elki/database/query/DistanceResultPair.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DoubleDBIDPair.java @@ -1,4 +1,4 @@ -package de.lmu.ifi.dbs.elki.database.query; +package de.lmu.ifi.dbs.elki.database.ids; /* This file is part of ELKI: @@ -23,46 +23,42 @@ package de.lmu.ifi.dbs.elki.database.query; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.utilities.pairs.PairInterface; /** - * Class that consists of a pair (distance, object ID) commonly returned for kNN - * and range queries. + * Pair of a double value and a DBID * * @author Erich Schubert - * - * @param <D> Distance type */ -public interface DistanceResultPair<D extends Distance<?>> extends PairInterface<D, DBID>, Comparable<DistanceResultPair<D>>, DBIDRef { +public interface DoubleDBIDPair extends PairInterface<Double, DBID>, DBIDRef, Comparable<DoubleDBIDPair> { /** - * Getter for first + * Get the double value of the pair. * - * @return first element in pair + * @return Double */ - public D getDistance(); + public double doubleValue(); /** - * Setter for first + * Get the first object - note: this may cause autoboxing, use pair.first for + * native pairs! * - * @param first new value for first element - */ - public void setDistance(D first); - - /** - * Setter for second + * @deprecated Avoid autoboxing. Use {@link #doubleValue}! * - * @param second new value for second element + * @return First object */ - public void setID(DBID second); + @Override + @Deprecated + public Double getFirst(); /** - * Compare value, but by distance only. + * Get the second object - note: this may cause autoboxing, use pair.second + * for native pairs! + * + * @deprecated Avoid autoboxing! Use {@link DBIDRef} interface! * - * @param o Other object - * @return comparison result, as by Double.compare(this, other) + * @return Second object */ - public int compareByDistance(DistanceResultPair<D> o); -}
\ No newline at end of file + @Override + @Deprecated + public DBID getSecond(); +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DoubleDistanceDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/DoubleDistanceDBIDPair.java new file mode 100644 index 00000000..72a9cfef --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DoubleDistanceDBIDPair.java @@ -0,0 +1,53 @@ +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/>. + */ + +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; + +/** + * Pair containing a double distance a DBID. + * + * There is no getter for the DBID, as this is a {@link DBIDRef} already. + * + * @author Erich Schubert + */ +public interface DoubleDistanceDBIDPair extends DistanceDBIDPair<DoubleDistance> { + /** + * Get the distance. + * + * @deprecated Would produce a DoubleDistance object. Use {@link #doubleDistance} instead! + * + * @return Distance + */ + @Override + @Deprecated + public DoubleDistance getDistance(); + + /** + * Get the distance. + * + * @return Distance + */ + public double doubleDistance(); +}
\ No newline at end of file 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 a85b8954..995f917c 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/EmptyDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/EmptyDBIDs.java @@ -23,11 +23,9 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Iterator; import java.util.NoSuchElementException; import de.lmu.ifi.dbs.elki.logging.LoggingUtil; -import de.lmu.ifi.dbs.elki.utilities.iterator.EmptyIterator; /** * Empty DBID collection. @@ -38,7 +36,7 @@ import de.lmu.ifi.dbs.elki.utilities.iterator.EmptyIterator; */ public class EmptyDBIDs implements ArrayStaticDBIDs, SetDBIDs { /** - * Empty DBID iterator + * Empty DBID iterator. */ public static final EmptyDBIDIterator EMPTY_ITERATOR = new EmptyDBIDIterator(); @@ -55,11 +53,6 @@ public class EmptyDBIDs implements ArrayStaticDBIDs, SetDBIDs { } @Override - public Iterator<DBID> iterator() { - return EmptyIterator.STATIC(); - } - - @Override public int size() { return 0; } @@ -75,7 +68,12 @@ public class EmptyDBIDs implements ArrayStaticDBIDs, SetDBIDs { } @Override - public DBIDIter iter() { + public void assign(int index, DBIDVar var) { + throw new ArrayIndexOutOfBoundsException(); + } + + @Override + public DBIDArrayMIter iter() { return EMPTY_ITERATOR; } @@ -85,11 +83,11 @@ public class EmptyDBIDs implements ArrayStaticDBIDs, SetDBIDs { } /** - * Iterator for empty DBIDs + * Iterator for empty DBIDs- * * @author Erich Schubert */ - protected static class EmptyDBIDIterator implements DBIDIter { + protected static class EmptyDBIDIterator implements DBIDArrayMIter { @Override public boolean valid() { return false; @@ -101,12 +99,7 @@ public class EmptyDBIDs implements ArrayStaticDBIDs, SetDBIDs { } @Override - public int getIntegerID() { - throw new NoSuchElementException(); - } - - @Override - public DBID getDBID() { + public int internalGetIndex() { throw new NoSuchElementException(); } @@ -119,13 +112,28 @@ public class EmptyDBIDs implements ArrayStaticDBIDs, SetDBIDs { } @Override - public boolean sameDBID(DBIDRef other) { - return false; + public void remove() { + throw new NoSuchElementException(); + } + + @Override + public void advance(int count) { + assert (count != 0) : "Misplaced call to advance()"; + } + + @Override + public void retract() { + assert (false) : "Misplaced call to retract()"; + } + + @Override + public void seek(int off) { + // Ignore } @Override - public int compareDBID(DBIDRef other) { - throw new UnsupportedOperationException("Invalid iterator position. Cannot compare."); + public int getOffset() { + return 0; } } -}
\ No newline at end of file +} 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 f7c8b551..efb39bc8 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/HashSetModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/HashSetModifiableDBIDs.java @@ -36,4 +36,8 @@ public interface HashSetModifiableDBIDs extends HashSetDBIDs, ModifiableDBIDs { * @return true when modified */ public boolean retainAll(DBIDs set); + + // To help the compilers... + @Override + DBIDMIter iter(); } 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 c92caef0..547f3297 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/ModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/ModifiableDBIDs.java @@ -31,6 +31,8 @@ package de.lmu.ifi.dbs.elki.database.ids; * <em>deliberately</em>. * * @author Erich Schubert + * + * @apiviz.has DBIDMIter */ public interface ModifiableDBIDs extends DBIDs { /** 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 index 91e307c2..124d1b28 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/DBIDIterAdapter.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/generic/DBIDIterAdapter.java @@ -27,7 +27,6 @@ import java.util.Iterator; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDMIter; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; /** * Iterator for classic collections. @@ -36,12 +35,12 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; */ public class DBIDIterAdapter implements DBIDMIter { /** - * Current DBID + * Current DBID. */ DBID cur = null; /** - * The real iterator + * The real iterator. */ Iterator<DBID> iter; @@ -72,29 +71,12 @@ public class DBIDIterAdapter implements DBIDMIter { } @Override - public int getIntegerID() { - return cur.getIntegerID(); - } - - @Override - public DBID getDBID() { - return cur; + public int internalGetIndex() { + return cur.internalGetIndex(); } @Override public void remove() { iter.remove(); } - - @Override - public boolean sameDBID(DBIDRef other) { - return cur.getIntegerID() == other.getIntegerID(); - } - - @Override - public int compareDBID(DBIDRef o) { - final int thisVal = cur.getIntegerID(); - final int anotherVal = o.getIntegerID(); - return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1)); - } }
\ 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 deleted file mode 100644 index f02c5064..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericArrayModifiableDBIDs.java +++ /dev/null @@ -1,139 +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) 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.ArrayList; -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.DBIDMIter; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -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}! - * - * Use {@link de.lmu.ifi.dbs.elki.database.ids.DBIDUtil#newArray}! - * - * @author Erich Schubert - * - * @apiviz.uses DBID - */ -public class GenericArrayModifiableDBIDs extends ArrayList<DBID> implements ArrayModifiableDBIDs { - /** - * Serial version - */ - private static final long serialVersionUID = 1L; - - /** - * Constructor with size hint. - * - * @param initialCapacity Size hint - */ - public GenericArrayModifiableDBIDs(int initialCapacity) { - super(initialCapacity); - } - - /** - * Constructor without extra hints - */ - public GenericArrayModifiableDBIDs() { - super(); - } - - /** - * Constructor from existing DBIDs. - * - * @param c Existing DBIDs. - */ - public GenericArrayModifiableDBIDs(DBIDs c) { - super(c.size()); - addDBIDs(c); - } - - @Override - public boolean addDBIDs(DBIDs ids) { - super.ensureCapacity(size() + ids.size()); - boolean changed = false; - for(DBIDIter id = ids.iter(); id.valid(); id.advance()) { - changed |= add(id); - } - return changed; - } - - @Override - public boolean removeDBIDs(DBIDs ids) { - boolean changed = false; - for(DBIDIter id = ids.iter(); id.valid(); id.advance()) { - changed |= super.remove(id); - } - return changed; - } - - @Override - public boolean add(DBIDRef id) { - return add(id.getDBID()); - } - - @Override - public boolean remove(DBIDRef id) { - return super.remove(id.getDBID()); - } - - @Override - public void sort() { - Collections.sort(this); - } - - @Override - public void sort(Comparator<? super DBID> comparator) { - Collections.sort(this, comparator); - } - - @Override - public DBIDMIter iter() { - return new DBIDIterAdapter(iterator()); - } - - @Override - public int binarySearch(DBIDRef key) { - return Collections.binarySearch(this, key.getDBID()); - } - - @Override - public boolean contains(DBIDRef o) { - return super.contains(o); - } - - @Override - public void swap(int a, int b) { - set(a, set(b, get(a))); - } -}
\ 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 deleted file mode 100644 index 6eadf0b1..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericHashSetModifiableDBIDs.java +++ /dev/null @@ -1,130 +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) 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.HashSet; - -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.DBIDMIter; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -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}! - * - * Use {@link de.lmu.ifi.dbs.elki.database.ids.DBIDUtil#newHashSet}! - * - * @author Erich Schubert - * - * @apiviz.uses DBID - */ -public class GenericHashSetModifiableDBIDs extends HashSet<DBID> implements HashSetModifiableDBIDs { - /** - * Serial version - */ - private static final long serialVersionUID = 1L; - - /** - * Constructor with size hint. - * - * @param initialCapacity Size hint - */ - public GenericHashSetModifiableDBIDs(int initialCapacity) { - super(initialCapacity); - } - - /** - * Constructor without extra hints - */ - public GenericHashSetModifiableDBIDs() { - super(); - } - - /** - * Constructor from existing DBIDs. - * - * @param c Existing DBIDs. - */ - public GenericHashSetModifiableDBIDs(DBIDs c) { - super(c.size()); - for(DBIDIter id = c.iter(); id.valid(); id.advance()) { - add(id); - } - } - - @Override - public boolean addDBIDs(DBIDs ids) { - boolean changed = false; - for(DBIDIter id = ids.iter(); id.valid(); id.advance()) { - changed |= add(id); - } - return changed; - } - - @Override - public boolean removeDBIDs(DBIDs ids) { - boolean changed = false; - for(DBIDIter id = ids.iter(); id.valid(); id.advance()) { - changed |= super.remove(id); - } - return changed; - } - - @Override - public boolean add(DBIDRef id) { - return super.add(id.getDBID()); - } - - @Override - public boolean remove(DBIDRef id) { - return super.remove(id.getDBID()); - } - - @Override - public boolean retainAll(DBIDs ids) { - boolean modified = false; - for(DBIDMIter it = iter(); it.valid(); it.advance()) { - if(!ids.contains(it)) { - it.remove(); - modified = true; - } - } - return modified; - } - - @Override - public DBIDMIter iter() { - return new DBIDIterAdapter(iterator()); - } - - @Override - public boolean contains(DBIDRef o) { - return super.contains(o); - } -}
\ No newline at end of file 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 13a6cc21..668ac0d8 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 @@ -24,10 +24,10 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; */ import java.util.BitSet; -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.DBIDArrayIter; +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.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; @@ -41,12 +41,12 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDs; */ public class MaskedDBIDs implements DBIDs { /** - * Data storage + * Data storage. */ protected ArrayDBIDs data; /** - * The bitmask used for masking + * The bitmask used for masking. */ protected BitSet bits; @@ -70,16 +70,6 @@ public class MaskedDBIDs implements DBIDs { } @Override - public Iterator<DBID> iterator() { - if(inverse) { - return new InvItr(); - } - else { - return new Itr(); - } - } - - @Override public DBIDIter iter() { if(inverse) { return new InvDBIDItr(); @@ -102,8 +92,8 @@ public class MaskedDBIDs implements DBIDs { @Override public boolean contains(DBIDRef o) { // TODO: optimize. - for(DBID id : this) { - if(id.sameDBID(o)) { + for(DBIDIter iter = iter(); iter.valid(); iter.advance()) { + if(DBIDFactory.FACTORY.equal(iter, o)) { return true; } } @@ -116,61 +106,29 @@ public class MaskedDBIDs implements DBIDs { } /** - * Iterator over set bits + * Iterator over set bits. * * @author Erich Schubert * * @apiviz.exclude */ - protected class Itr implements Iterator<DBID> { + protected class DBIDItr implements DBIDIter { /** - * Next position. + * Current position. */ private int pos; /** - * Constructor + * Array iterator, for referencing. */ - protected Itr() { - this.pos = bits.nextSetBit(0); - } - - @Override - public boolean hasNext() { - return (pos >= 0) && (pos < data.size()); - } - - @Override - public DBID next() { - DBID cur = data.get(pos); - pos = bits.nextSetBit(pos + 1); - return cur; - } - - @Override - public void remove() { - throw new UnsupportedOperationException(); - } - } - - /** - * Iterator over set bits - * - * @author Erich Schubert - * - * @apiviz.exclude - */ - protected class DBIDItr implements DBIDIter { - /** - * Next position. - */ - private int pos; + private DBIDArrayIter iter; /** - * Constructor + * Constructor. */ protected DBIDItr() { this.pos = bits.nextSetBit(0); + this.iter = data.iter(); } @Override @@ -184,84 +142,36 @@ public class MaskedDBIDs implements DBIDs { } @Override - public int getIntegerID() { - return data.get(pos).getIntegerID(); - } - - @Override - public DBID getDBID() { - return data.get(pos); - } - - @Override - public boolean sameDBID(DBIDRef other) { - return getIntegerID() == other.getIntegerID(); - } - - @Override - public int compareDBID(DBIDRef o) { - final int thisVal = getIntegerID(); - final int anotherVal = o.getIntegerID(); - return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1)); + public int internalGetIndex() { + iter.seek(pos); + return iter.internalGetIndex(); } } /** - * Iterator over unset elements. + * Iterator over set bits. * * @author Erich Schubert * * @apiviz.exclude */ - protected class InvItr implements Iterator<DBID> { + protected class InvDBIDItr implements DBIDIter { /** - * Next unset position. + * Next position. */ private int pos; /** - * Constructor - */ - protected InvItr() { - this.pos = bits.nextClearBit(0); - } - - @Override - public boolean hasNext() { - return (pos >= 0) && (pos < data.size()); - } - - @Override - public DBID next() { - DBID cur = data.get(pos); - pos = bits.nextClearBit(pos + 1); - return cur; - } - - @Override - public void remove() { - throw new UnsupportedOperationException(); - } - } - - /** - * Iterator over set bits - * - * @author Erich Schubert - * - * @apiviz.exclude - */ - protected class InvDBIDItr implements DBIDIter { - /** - * Next position. + * Array iterator, for referencing. */ - private int pos; + private DBIDArrayIter iter; /** - * Constructor + * Constructor. */ protected InvDBIDItr() { this.pos = bits.nextClearBit(0); + this.iter = data.iter(); } @Override @@ -275,25 +185,9 @@ public class MaskedDBIDs implements DBIDs { } @Override - public int getIntegerID() { - return data.get(pos).getIntegerID(); - } - - @Override - public DBID getDBID() { - return data.get(pos); - } - - @Override - public boolean sameDBID(DBIDRef other) { - return getIntegerID() == other.getIntegerID(); - } - - @Override - public int compareDBID(DBIDRef o) { - final int thisVal = getIntegerID(); - final int anotherVal = o.getIntegerID(); - return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1)); + public int internalGetIndex() { + iter.seek(pos); + return iter.internalGetIndex(); } } }
\ No newline at end of file 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 16d83a56..9d2583e3 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 @@ -23,9 +23,6 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -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.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; @@ -56,11 +53,6 @@ public class MergedDBIDs implements DBIDs { } @Override - public Iterator<DBID> iterator() { - throw new AbortException("Merged iterators not completely implemented yet!"); - } - - @Override public DBIDIter iter() { throw new AbortException("Merged iterators not completely implemented yet!"); } diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/UnmodifiableArrayDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/UnmodifiableArrayDBIDs.java index 35b092c2..abcdef54 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/UnmodifiableArrayDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/generic/UnmodifiableArrayDBIDs.java @@ -23,27 +23,27 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -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.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDArrayIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDMIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.utilities.iterator.UnmodifiableIterator; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; /** * Unmodifiable wrapper for DBIDs. * * @author Erich Schubert * - * @apiviz.uses de.lmu.ifi.dbs.elki.database.ids.DBIDs + * @apiviz.uses ArrayDBIDs + * @apiviz.has UnmodifiableDBIDArrayIter */ public class UnmodifiableArrayDBIDs implements ArrayStaticDBIDs { /** * The DBIDs we wrap. */ - final private ArrayDBIDs inner; + private final ArrayDBIDs inner; /** * Constructor. @@ -65,15 +65,13 @@ public class UnmodifiableArrayDBIDs implements ArrayStaticDBIDs { return inner.isEmpty(); } - @SuppressWarnings("deprecation") - @Override - public Iterator<DBID> iterator() { - return new UnmodifiableIterator<DBID>(inner.iterator()); - } - @Override - public DBIDIter iter() { - return inner.iter(); + public DBIDArrayIter iter() { + DBIDArrayIter it = inner.iter(); + if(it instanceof DBIDMIter) { + return new UnmodifiableDBIDArrayIter(it); + } + return it; } @Override @@ -81,9 +79,6 @@ public class UnmodifiableArrayDBIDs implements ArrayStaticDBIDs { return inner.size(); } - /** - * Returns a string representation of the inner DBID collection. - */ @Override public String toString() { return inner.toString(); @@ -95,7 +90,69 @@ public class UnmodifiableArrayDBIDs implements ArrayStaticDBIDs { } @Override + public void assign(int index, DBIDVar var) { + inner.assign(index, var); + } + + @Override public int binarySearch(DBIDRef key) { return inner.binarySearch(key); } + + /** + * Make an existing DBIDMIter unmodifiable. + * + * @author Erich Schubert + */ + class UnmodifiableDBIDArrayIter implements DBIDArrayIter { + /** + * Wrapped iterator. + */ + private DBIDArrayIter it; + + /** + * Constructor. + * + * @param it inner iterator + */ + public UnmodifiableDBIDArrayIter(DBIDArrayIter it) { + super(); + this.it = it; + } + + @Override + public boolean valid() { + return it.valid(); + } + + @Override + public void advance() { + it.advance(); + } + + @Override + public int internalGetIndex() { + return it.internalGetIndex(); + } + + @Override + public void advance(int count) { + it.advance(count); + } + + @Override + public void retract() { + it.retract(); + } + + @Override + public void seek(int off) { + it.seek(off); + } + + @Override + public int getOffset() { + return it.getOffset(); + } + } }
\ 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 682b2e4b..fea35692 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 @@ -23,27 +23,25 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -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.DBIDMIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; 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; /** * Unmodifiable wrapper for DBIDs. * * @author Erich Schubert * - * @apiviz.uses de.lmu.ifi.dbs.elki.database.ids.DBIDs + * @apiviz.uses DBIDs + * @apiviz.has UnmodifiableDBIDIter */ public class UnmodifiableDBIDs implements StaticDBIDs { /** * The DBIDs we wrap. */ - final private DBIDs inner; + private final DBIDs inner; /** * Constructor. @@ -65,15 +63,13 @@ public class UnmodifiableDBIDs implements StaticDBIDs { return inner.isEmpty(); } - @SuppressWarnings("deprecation") - @Override - public Iterator<DBID> iterator() { - return new UnmodifiableIterator<DBID>(inner.iterator()); - } - @Override public DBIDIter iter() { - return inner.iter(); + DBIDIter it = inner.iter(); + if(it instanceof DBIDMIter) { + return new UnmodifiableDBIDIter(it); + } + return it; } @Override @@ -81,11 +77,45 @@ public class UnmodifiableDBIDs implements StaticDBIDs { return inner.size(); } - /** - * Returns a string representation of the inner DBID collection. - */ @Override public String toString() { return inner.toString(); } -} + + /** + * Make an existing DBIDMIter unmodifiable. + * + * @author Erich Schubert + */ + class UnmodifiableDBIDIter implements DBIDIter { + /** + * Wrapped iterator. + */ + private DBIDIter it; + + /** + * Constructor. + * + * @param it inner iterator + */ + public UnmodifiableDBIDIter(DBIDIter it) { + super(); + this.it = it; + } + + @Override + public boolean valid() { + return it.valid(); + } + + @Override + public void advance() { + it.advance(); + } + + @Override + public int internalGetIndex() { + return it.internalGetIndex(); + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DistanceIntegerDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DistanceIntegerDBIDPair.java new file mode 100644 index 00000000..01eec02e --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DistanceIntegerDBIDPair.java @@ -0,0 +1,95 @@ +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 de.lmu.ifi.dbs.elki.database.ids.DistanceDBIDPair; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; + +/** + * Class storing a double distance a DBID. + * + * @author Erich Schubert + * + * @param <D> Distance type + */ +class DistanceIntegerDBIDPair<D extends Distance<D>> implements DistanceDBIDPair<D>, IntegerDBIDRef { + /** + * The distance value. + */ + D distance; + + /** + * The integer DBID. + */ + int id; + + /** + * Constructor. + * + * @param distance Distance + * @param id Object ID + */ + protected DistanceIntegerDBIDPair(D distance, int id) { + super(); + this.distance = distance; + this.id = id; + } + + @Override + public D getDistance() { + return distance; + } + + @Override + public int internalGetIndex() { + return id; + } + + @Override + public int compareByDistance(DistanceDBIDPair<D> o) { + return distance.compareTo(o.getDistance()); + } + + @Override + public String toString() { + return distance.toString() + ":" + id; + } + + @Override + public boolean equals(Object o) { + if (this == o) { + return true; + } + if (o instanceof DistanceIntegerDBIDPair) { + DistanceIntegerDBIDPair<?> p = (DistanceIntegerDBIDPair<?>) o; + return (this.id == p.id) && distance.equals(p.getDistance()); + } + if (o instanceof DoubleDistanceIntegerDBIDPair && distance instanceof DoubleDistance) { + DoubleDistanceIntegerDBIDPair p = (DoubleDistanceIntegerDBIDPair) o; + return (this.id == p.id) && (((DoubleDistance) this.distance).doubleValue() == p.distance); + } + return false; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDPair.java new file mode 100644 index 00000000..8334d2e3 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDPair.java @@ -0,0 +1,103 @@ +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 de.lmu.ifi.dbs.elki.database.ids.DistanceDBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDistanceDBIDPair; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; + +/** + * Class storing a double distance a DBID. + * + * @author Erich Schubert + */ +class DoubleDistanceIntegerDBIDPair implements DoubleDistanceDBIDPair, IntegerDBIDRef { + /** + * The distance value. + */ + final double distance; + + /** + * The integer DBID. + */ + final int id; + + /** + * Constructor. + * + * @param distance Distance value + * @param id integer object ID + */ + protected DoubleDistanceIntegerDBIDPair(double distance, int id) { + super(); + this.distance = distance; + this.id = id; + } + + @Override + public double doubleDistance() { + return distance; + } + + @Override + @Deprecated + public DoubleDistance getDistance() { + return new DoubleDistance(distance); + } + + @Override + public int internalGetIndex() { + return id; + } + + @Override + public int compareByDistance(DistanceDBIDPair<DoubleDistance> o) { + if (o instanceof DoubleDistanceDBIDPair) { + return Double.compare(distance, ((DoubleDistanceDBIDPair) o).doubleDistance()); + } + return Double.compare(distance, o.getDistance().doubleValue()); + } + + @Override + public String toString() { + return distance + ":" + id; + } + + @Override + public boolean equals(Object o) { + if (this == o) { + return true; + } + if (o instanceof DoubleDistanceIntegerDBIDPair) { + DoubleDistanceIntegerDBIDPair p = (DoubleDistanceIntegerDBIDPair) o; + return (this.id == p.id) && (this.distance == p.distance); + } + if (o instanceof DistanceIntegerDBIDPair) { + DistanceIntegerDBIDPair<?> p = (DistanceIntegerDBIDPair<?>) o; + if (p.distance instanceof DoubleDistance) { + return (this.id == p.id) && (this.distance == ((DoubleDistance) p.distance).doubleValue()); + } + } + return false; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntArrayStaticDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntArrayStaticDBIDs.java new file mode 100644 index 00000000..aa3b3cc0 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntArrayStaticDBIDs.java @@ -0,0 +1,165 @@ +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 java.util.Arrays; + +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.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; +import de.lmu.ifi.dbs.elki.logging.LoggingUtil; + +/** + * Static (no modifications allowed) set of Database Object IDs. + * + * @author Erich Schubert + * + * @apiviz.has IntegerDBID + */ +public class IntArrayStaticDBIDs implements IntegerArrayStaticDBIDs { + /** + * The actual storage. + */ + protected int[] ids; + + /** + * Constructor. + * + * @param ids Array of ids. + */ + public IntArrayStaticDBIDs(int... ids) { + super(); + this.ids = ids; + } + + @Override + public IntegerDBIDArrayIter iter() { + return new DBIDItr(); + } + + /** + * DBID iterator in ELKI/C style. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected class DBIDItr implements IntegerDBIDArrayIter { + /** + * Position within array. + */ + int pos = 0; + + @Override + public boolean valid() { + return pos < ids.length && pos >= 0; + } + + @Override + public void advance() { + pos++; + } + + @Override + public void advance(int count) { + pos += 0; + } + + @Override + public void retract() { + pos--; + } + + @Override + public void seek(int off) { + pos = off; + } + + @Override + public int getOffset() { + return pos; + } + + @Override + public int internalGetIndex() { + return ids[pos]; + } + + @Override + public boolean equals(Object other) { + if(other instanceof DBID) { + LoggingUtil.warning("Programming error detected: DBIDItr.equals(DBID). Use sameDBID()!", new Throwable()); + } + return super.equals(other); + } + + @Override + public String toString() { + return Integer.toString(internalGetIndex()); + } + } + + @Override + public int size() { + return ids.length; + } + + @Override + public boolean isEmpty() { + return ids.length == 0; + } + + @Override + public boolean contains(DBIDRef o) { + final int oid = DBIDUtil.asInteger(o); + for(int i = 0; i < ids.length; i++) { + if(ids[i] == oid) { + return true; + } + } + return false; + } + + @Override + public DBID get(int i) { + return DBIDFactory.FACTORY.importInteger(ids[i]); + } + + @Override + public void assign(int i, DBIDVar var) { + if (var instanceof IntegerDBIDVar) { + ((IntegerDBIDVar)var).internalSetIndex(ids[i]); + } else { + // Much less efficient: + var.set(get(i)); + } + } + + @Override + public int binarySearch(DBIDRef key) { + return Arrays.binarySearch(ids, DBIDUtil.asInteger(key)); + } +}
\ No newline at end of file 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 90ab5a6a..4bafd343 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 @@ -23,168 +23,15 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.AbstractList; -import java.util.Arrays; -import java.util.Iterator; - 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; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.logging.LoggingUtil; /** - * Static (no modifications allowed) set of Database Object IDs. + * Combination of {@link ArrayStaticDBIDs} and {@link IntegerDBIDs}. * * @author Erich Schubert - * - * @apiviz.has IntegerDBID + * */ -public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements ArrayStaticDBIDs { - /** - * The actual storage. - */ - protected int[] ids; - - /** - * Constructor - * - * @param ids Array of ids. - */ - public IntegerArrayStaticDBIDs(int... ids) { - super(); - this.ids = ids; - } - - @Override - public Iterator<DBID> iterator() { - return new Itr(); - } - - @Override - public DBIDIter iter() { - return new DBIDItr(); - } - - /** - * Iterator class. - * - * @author Erich Schubert - * - * @apiviz.exclude - */ - protected class Itr implements Iterator<DBID> { - int off = 0; - - @Override - public boolean hasNext() { - return off < ids.length; - } - - @Override - public DBID next() { - DBID ret = new IntegerDBID(ids[off]); - off++; - return ret; - } - - @Override - public void remove() { - throw new UnsupportedOperationException(); - } - } - - /** - * 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 boolean sameDBID(DBIDRef other) { - return ids[pos] == other.getIntegerID(); - } - - @Override - public boolean equals(Object other) { - if (other instanceof DBID) { - LoggingUtil.warning("Programming error detected: DBIDItr.equals(DBID). Use sameDBID()!", new Throwable()); - } - return super.equals(other); - } - - @Override - public int compareDBID(DBIDRef o) { - int anotherVal = o.getIntegerID(); - return (ids[pos] < anotherVal ? -1 : (ids[pos] == anotherVal ? 0 : 1)); - } - } - - @Override - public int size() { - return ids.length; - } - - @Override - public boolean contains(DBIDRef o) { - final int oid = o.getIntegerID(); - for(int i = 0; i < ids.length; i++) { - if(ids[i] == oid) { - return true; - } - } - return false; - } - - @SuppressWarnings("unchecked") - @Override - public <T> T[] toArray(T[] a) { - T[] r = a; - if(a.length < ids.length) { - r = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), ids.length); - } - for(int i = 0; i < ids.length; i++) { - r[i] = (T) DBIDFactory.FACTORY.importInteger(ids[i]); - } - // zero-terminate array - if(r.length > ids.length) { - r[ids.length] = null; - } - return r; - } - - @Override - public DBID get(int i) { - return DBIDFactory.FACTORY.importInteger(ids[i]); - } - +public interface IntegerArrayStaticDBIDs extends ArrayStaticDBIDs, IntegerDBIDs { @Override - public int binarySearch(DBIDRef key) { - return Arrays.binarySearch(ids, key.getIntegerID()); - } + IntegerDBIDArrayIter iter(); }
\ 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 66c1f980..91c00939 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 @@ -24,11 +24,11 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; */ import java.nio.ByteBuffer; -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.DBIDArrayIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; import de.lmu.ifi.dbs.elki.logging.LoggingUtil; import de.lmu.ifi.dbs.elki.persistent.ByteArrayUtil; import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; @@ -51,11 +51,11 @@ import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; * @apiviz.composedOf DynamicSerializer * @apiviz.composedOf StaticSerializer */ -final class IntegerDBID implements DBID { +final class IntegerDBID implements DBID, IntegerDBIDRef { /** * The actual object ID. */ - final protected int id; + protected final int id; /** * Constructor from integer id. @@ -74,12 +74,7 @@ final class IntegerDBID implements DBID { */ protected IntegerDBID(Integer id) { super(); - this.id = id; - } - - @Override - public DBID getDBID() { - return this; + this.id = id.intValue(); } /** @@ -88,7 +83,7 @@ final class IntegerDBID implements DBID { * @return integer id */ @Override - public int getIntegerID() { + public int internalGetIndex() { return this.id; } @@ -103,8 +98,12 @@ final class IntegerDBID implements DBID { } @Override + @Deprecated public boolean equals(Object obj) { - if(!(obj instanceof IntegerDBID)) { + if (this == obj) { + return true; + } + if (!(obj instanceof IntegerDBID)) { if (obj instanceof DBIDRef) { LoggingUtil.warning("Programming error: DBID.equals(DBIDRef) is not well-defined. use sameDBID!", new Throwable()); } @@ -113,47 +112,37 @@ final class IntegerDBID implements DBID { IntegerDBID other = (IntegerDBID) obj; return this.id == other.id; } - - @Override - public boolean sameDBID(DBIDRef other) { - return this.id == other.getIntegerID(); - } @Override public int compareTo(DBIDRef o) { - int thisVal = this.id; - int anotherVal = o.getIntegerID(); - return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1)); + final int anotherVal = o.internalGetIndex(); + return (this.id < anotherVal ? -1 : (this.id == anotherVal ? 0 : 1)); } @Override - public int compareDBID(DBIDRef o) { - int thisVal = this.id; - int anotherVal = o.getIntegerID(); - return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1)); - } - - @Override - public DBIDIter iter() { + public DBIDArrayIter iter() { return new DBIDItr(); } @Override public DBID get(int i) { - if(i != 0) { + if (i != 0) { throw new ArrayIndexOutOfBoundsException(); } return this; } @Override - public Iterator<DBID> iterator() { - return new Itr(); + public void assign(int index, DBIDVar var) { + if (index != 0) { + throw new ArrayIndexOutOfBoundsException(); + } + var.set(this); } @Override public boolean contains(DBIDRef o) { - return o.getIntegerID() == id; + return o.internalGetIndex() == id; } @Override @@ -163,7 +152,8 @@ final class IntegerDBID implements DBID { @Override public int binarySearch(DBIDRef key) { - return (id == key.getIntegerID()) ? 0 : -1; + final int other = key.internalGetIndex(); + return (other == id) ? 0 : (other < id) ? -1 : -2; } /** @@ -173,61 +163,51 @@ final class IntegerDBID implements DBID { * * @apiviz.exclude */ - protected class Itr implements Iterator<DBID> { + protected class DBIDItr implements DBIDArrayIter, IntegerDBIDRef { /** - * Whether we've already returned our object. + * Iterator position: We use an integer so we can support retract(). */ - boolean first = true; + int pos = 0; @Override - public boolean hasNext() { - return first == true; + public void advance() { + pos++; } @Override - public DBID next() { - assert (first); - first = false; - return IntegerDBID.this; + public void advance(int count) { + pos += count; } @Override - public void remove() { - throw new UnsupportedOperationException(); + public void retract() { + pos--; } - } - - /** - * 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 void advance() { - first = false; + public void seek(int off) { + pos = off; } @Override - public int getIntegerID() { - return id; + public int getOffset() { + return pos; } @Override - public DBID getDBID() { - return IntegerDBID.this; + public int internalGetIndex() { + return IntegerDBID.this.id; } @Override public boolean valid() { - return first; + return (pos == 0); + } + + @Override + public int hashCode() { + // Override, because we also are overriding equals. + return super.hashCode(); } @Override @@ -239,14 +219,8 @@ final class IntegerDBID implements DBID { } @Override - public boolean sameDBID(DBIDRef other) { - return id == other.getIntegerID(); - } - - @Override - public int compareDBID(DBIDRef o) { - int anotherVal = o.getIntegerID(); - return (id < anotherVal ? -1 : (id == anotherVal ? 0 : 1)); + public String toString() { + return Integer.toString(internalGetIndex()); } } @@ -321,10 +295,10 @@ final class IntegerDBID implements DBID { /** * The public instance to use for dynamic serialization. */ - public final static DynamicSerializer dynamicSerializer = new DynamicSerializer(); + public static final ByteBufferSerializer<DBID> DYNAMIC_SERIALIZER = new DynamicSerializer(); /** * The public instance to use for static serialization. */ - public final static StaticSerializer staticSerializer = new StaticSerializer(); -}
\ No newline at end of file + public static final FixedSizeByteBufferSerializer<DBID> STATIC_SERIALIZER = new StaticSerializer(); +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayIter.java new file mode 100644 index 00000000..b0e2d339 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayIter.java @@ -0,0 +1,34 @@ +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 de.lmu.ifi.dbs.elki.database.ids.DBIDArrayIter; + +/** + * Modifiable integer array iterator. + * + * @author Erich Schubert + */ +public interface IntegerDBIDArrayIter extends IntegerDBIDIter, DBIDArrayIter { + // Empty +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayMIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayMIter.java new file mode 100644 index 00000000..21616f75 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayMIter.java @@ -0,0 +1,34 @@ +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 de.lmu.ifi.dbs.elki.database.ids.DBIDArrayMIter; + +/** + * Modifiable integer array iterator. + * + * @author Erich Schubert + */ +public interface IntegerDBIDArrayMIter extends IntegerDBIDArrayIter, IntegerDBIDMIter, DBIDArrayMIter { + // Empty +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayQuickSort.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayQuickSort.java new file mode 100644 index 00000000..2c096ab9 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayQuickSort.java @@ -0,0 +1,250 @@ +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 java.util.Comparator; + +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; + +/** + * Class to sort an integer DBID array, using a modified quicksort. + * + * Two array iterators will be used to seek to the elements to compare, while + * the backing storage is a plain integer array. + * + * The implementation is closely based on: + * <p> + * Dual-Pivot Quicksort<br /> + * Vladimir Yaroslavskiy + * </p> + * + * @author Erich Schubert + * + * @apiviz.uses TroveArrayModifiableDBIDs + */ +@Reference(authors = "Vladimir Yaroslavskiy", title = "Dual-Pivot Quicksort", booktitle = "http://iaroslavski.narod.ru/quicksort/", url = "http://iaroslavski.narod.ru/quicksort/") +class IntegerDBIDArrayQuickSort { + /** + * Threshold for using insertion sort. Value taken from Javas QuickSort, + * assuming that it will be similar for DBIDs. + */ + private static final int INSERTION_THRESHOLD = 47; + + /** + * Sort the full array using the given comparator. + * + * @param data Data to sort + * @param comp Comparator + */ + public static void sort(int[] data, Comparator<? super DBIDRef> comp) { + sort(data, 0, data.length, comp); + } + + /** + * Sort the array using the given comparator. + * + * @param data Data to sort + * @param start First index + * @param end Last index (exclusive) + * @param comp Comparator + */ + public static void sort(int[] data, int start, int end, Comparator<? super DBIDRef> comp) { + quickSort(data, start, end - 1, comp, new IntegerDBIDVar(), new IntegerDBIDVar(), new IntegerDBIDVar()); + } + + /** + * Actual recursive sort function. + * + * @param data Data to sort + * @param start First index + * @param end Last index (inclusive!) + * @param comp Comparator + * @param vl First seeking iterator + * @param vk Second seeking iterator + * @param vr Third seeking iterator + */ + private static void quickSort(int[] data, final int start, final int end, Comparator<? super DBIDRef> comp, IntegerDBIDVar vl, IntegerDBIDVar vk, IntegerDBIDVar vr) { + final int len = end - start; + if (len < INSERTION_THRESHOLD) { + // Classic insertion sort. + for (int i = start + 1; i <= end; i++) { + for (int j = i; j > start; j--) { + vl.internalSetIndex(data[j]); + vr.internalSetIndex(data[j - 1]); + if (comp.compare(vl, vr) < 0) { + int tmp = data[j - 1]; + data[j - 1] = data[j]; + data[j] = tmp; + } else { + break; + } + } + } + return; + } + + // Choose pivots by looking at five candidates. + final int seventh = (len >> 3) + (len >> 6) + 1; + final int m3 = (start + end) >> 1; // middle + final int m2 = m3 - seventh; + final int m1 = m2 - seventh; + final int m4 = m3 + seventh; + final int m5 = m4 + seventh; + + // Explicit (and optimal) sorting network for 5 elements + // See Knuth for details. + if (compare(vl, data[m1], vk, data[m2], comp) > 0) { + int tmp = data[m2]; + data[m2] = data[m1]; + data[m1] = tmp; + } + if (compare(vl, data[m1], vk, data[m3], comp) > 0) { + int tmp = data[m3]; + data[m3] = data[m1]; + data[m1] = tmp; + } + if (compare(vl, data[m2], vk, data[m3], comp) > 0) { + int tmp = data[m3]; + data[m3] = data[m2]; + data[m2] = tmp; + } + if (compare(vl, data[m4], vk, data[m5], comp) > 0) { + int tmp = data[m5]; + data[m5] = data[m4]; + data[m4] = tmp; + } + if (compare(vl, data[m1], vk, data[m4], comp) > 0) { + int tmp = data[m4]; + data[m4] = data[m1]; + data[m1] = tmp; + } + if (compare(vl, data[m3], vk, data[m4], comp) > 0) { + int tmp = data[m4]; + data[m4] = data[m3]; + data[m3] = tmp; + } + if (compare(vl, data[m2], vk, data[m5], comp) > 0) { + int tmp = data[m5]; + data[m5] = data[m2]; + data[m2] = tmp; + } + if (compare(vl, data[m2], vk, data[m3], comp) > 0) { + int tmp = data[m3]; + data[m3] = data[m2]; + data[m2] = tmp; + } + if (compare(vl, data[m4], vk, data[m5], comp) > 0) { + int tmp = data[m5]; + data[m5] = data[m4]; + data[m4] = tmp; + } + + // Choose the 2 and 4th as pivots, as we want to get three parts + // Copy to variables v1 and v3, replace them with the start and end + // Note: do not modify v1 or v3 until we put them back! + vl.internalSetIndex(data[m2]); + vr.internalSetIndex(data[m4]); + data[m2] = data[start]; + data[m4] = data[end]; + + // A tie is when the two chosen pivots are the same + final boolean tied = comp.compare(vl, vr) == 0; + + // Insertion points for pivot areas. + int left = start + 1; + int right = end - 1; + + // Note: we merged the ties and no ties cases. + // This likely is marginally slower, but not at a macro level + // And you never know with hotspot. + for (int k = left; k <= right; k++) { + int tmp = data[k]; + vk.internalSetIndex(tmp); + final int c = comp.compare(vk, vl); + if (c == 0) { + continue; + } else if (c < 0) { + // Traditional quicksort + data[k] = data[left]; + data[left] = tmp; + left++; + } else if (tied || comp.compare(vk, vr) > 0) { + // Now look at the right. First skip correct entries there, too + while (true) { + vk.internalSetIndex(data[right]); + if (comp.compare(vk, vr) > 0 && k < right) { + right--; + } else { + break; + } + } + // Now move tmp from k to the right. + data[k] = data[right]; + data[right] = tmp; + right--; + // Test the element we just inserted: left or center? + vk.internalSetIndex(data[k]); + if (comp.compare(vk, vl) < 0) { + tmp = data[k]; + data[k] = data[left]; + data[left] = tmp; + left++; + } // else: center. cannot be on right. + } + } + // Put the pivot elements back in. + // Remember: we must not modify v1 and v3 above. + data[start] = data[left - 1]; + data[left - 1] = vl.internalGetIndex(); + data[end] = data[right + 1]; + data[right + 1] = vr.internalGetIndex(); + // v1 and v3 are now safe to modify again. Perform recursion: + quickSort(data, start, left - 2, comp, vl, vk, vr); + // Handle the middle part - if necessary: + if (!tied) { + // TODO: the original publication had a special tie handling here. + // It shouldn't affect correctness, but probably improves situations + // with a lot of tied elements. + quickSort(data, left, right, comp, vl, vk, vr); + } + quickSort(data, right + 2, end, comp, vl, vk, vr); + } + + /** + * Compare two elements. + * + * @param i1 First scratch variable + * @param p1 Value for first + * @param i2 Second scratch variable + * @param p2 Value for second + * @param comp Comparator + * @return Comparison result + */ + private static int compare(IntegerDBIDVar i1, int p1, IntegerDBIDVar i2, int p2, Comparator<? super DBIDRef> comp) { + i1.internalSetIndex(p1); + i2.internalSetIndex(p2); + return comp.compare(i1, i2); + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDIter.java new file mode 100644 index 00000000..9b50d544 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDIter.java @@ -0,0 +1,34 @@ +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 de.lmu.ifi.dbs.elki.database.ids.DBIDIter; + +/** + * Iterator for integer DBIDs. + * + * @author Erich Schubert + */ +public interface IntegerDBIDIter extends IntegerDBIDRef, DBIDIter { + // Empty +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDMIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDMIter.java new file mode 100644 index 00000000..2e339dbc --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDMIter.java @@ -0,0 +1,34 @@ +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 de.lmu.ifi.dbs.elki.database.ids.DBIDMIter; + +/** + * Modifiable iterator interface for integer DBIDs. + * + * @author Erich Schubert + */ +public interface IntegerDBIDMIter extends DBIDMIter, IntegerDBIDIter { + // Empty. +} 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 cad771d9..85c47f43 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 @@ -23,30 +23,29 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.AbstractList; -import java.util.Iterator; - import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDArrayIter; 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; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; /** - * Representing a DBID range allocation + * Representing a DBID range allocation. * * @author Erich Schubert * * @apiviz.has IntegerDBID */ -class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { +class IntegerDBIDRange implements DBIDRange { /** - * Start value + * Start value. */ protected final int start; /** - * Length value + * Length value. */ protected final int len; @@ -68,71 +67,83 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { } @Override - public Iterator<DBID> iterator() { - return new Itr(); + public boolean isEmpty() { + return len == 0; } @Override - public DBIDIter iter() { - return new DBIDItr(); + public DBIDArrayIter iter() { + return new DBIDItr(start, len); } /** - * Iterator class. + * Iterator in ELKI/C++ style. * * @author Erich Schubert * * @apiviz.exclude */ - protected class Itr implements Iterator<DBID> { + protected static class DBIDItr implements DBIDArrayIter, IntegerDBIDRef { + /** + * Current position. + */ int pos = 0; + + /** + * Interval length. + */ + final int len; + + /** + * Interval start. + */ + final int start; + + /** + * Constructor. + * + * @param start Interval start + * @param len Interval length + */ + DBIDItr(int start, int len) { + super(); + this.start = start; + this.len = len; + } @Override - public boolean hasNext() { - return pos < len; + public boolean valid() { + return pos < len && pos >= 0; } @Override - public DBID next() { - DBID ret = new IntegerDBID(pos + start); + public void advance() { pos++; - return ret; } @Override - public void remove() { - throw new UnsupportedOperationException("CompactStaticDBIDs is read-only."); + public void advance(int count) { + pos += count; } - } - - /** - * 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; + public void retract() { + pos--; } @Override - public void advance() { - pos++; + public void seek(int off) { + pos = off; } @Override - public int getIntegerID() { - return start + pos; + public int getOffset() { + return pos; } @Override - public DBID getDBID() { - return new IntegerDBID(start + pos); + public int internalGetIndex() { + return start + pos; } @Override @@ -141,20 +152,14 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { } @Override - public boolean sameDBID(DBIDRef other) { - return start + pos == other.getIntegerID(); - } - - @Override - public int compareDBID(DBIDRef o) { - int anotherVal = o.getIntegerID(); - return (start + pos < anotherVal ? -1 : (start + pos == anotherVal ? 0 : 1)); + public String toString() { + return Integer.toString(internalGetIndex()); } } @Override public boolean contains(DBIDRef o) { - int oid = o.getIntegerID(); + int oid = DBIDUtil.asInteger(o); if(oid < start) { return false; } @@ -164,23 +169,6 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { return true; } - @SuppressWarnings("unchecked") - @Override - public <T> T[] toArray(T[] a) { - T[] r = a; - if(a.length < start) { - r = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), len); - } - for(int i = 0; i < start; i++) { - r[i] = (T) DBIDFactory.FACTORY.importInteger(len + i); - } - // zero-terminate array - if(r.length > len) { - r[len] = null; - } - return r; - } - @Override public DBID get(int i) { if(i > len || i < 0) { @@ -192,17 +180,27 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { /** * For storage array offsets. * - * @param dbid + * @param dbid ID reference * @return array offset */ @Override public int getOffset(DBIDRef dbid) { - return dbid.getIntegerID() - start; + return dbid.internalGetIndex() - start; + } + + @Override + public void assign(int index, DBIDVar var) { + if (var instanceof IntegerDBIDVar) { + ((IntegerDBIDVar)var).internalSetIndex(start + index); + } else { + // Much less efficient: + var.set(get(index)); + } } @Override public int binarySearch(DBIDRef key) { - int keyid = key.getIntegerID(); + int keyid = DBIDUtil.asInteger(key); if(keyid < start) { return -1; } @@ -212,4 +210,14 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { } return -(len + 1); } + + @Override + public String toString() { + return "[" + start + " to " + (start + len - 1) + "]"; + } + + @Override + public int mapDBIDToOffset(DBIDRef dbid) { + return dbid.internalGetIndex() - start; + } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRef.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRef.java new file mode 100644 index 00000000..45854440 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRef.java @@ -0,0 +1,41 @@ +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 de.lmu.ifi.dbs.elki.database.ids.DBIDRef; + +/** + * DBID reference that references an integer value. + * + * @author Erich Schubert + */ +interface IntegerDBIDRef extends DBIDRef { + /** + * Return the integer value of the object ID. + * + * @return integer id + */ + @Override + int internalGetIndex(); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDVar.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDVar.java new file mode 100644 index 00000000..73d164e0 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDVar.java @@ -0,0 +1,198 @@ +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 de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDArrayIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; +import de.lmu.ifi.dbs.elki.logging.LoggingUtil; + +/** + * Variable for storing a single DBID reference. + * + * TODO: what is the actual memory cost for adding a flag to indicate "null" + * values, to allow the variable to be unset? Given 8-byte alignment of Java, it + * should come for free! + * + * @author Erich Schubert + */ +class IntegerDBIDVar implements DBIDVar { + /** + * The actual value. + */ + int id; + + /** + * Constructor. + */ + protected IntegerDBIDVar() { + this.id = -1; + } + + /** + * Constructor. + * + * @param val + */ + protected IntegerDBIDVar(DBIDRef val) { + this.id = val.internalGetIndex(); + } + + @Override + public int internalGetIndex() { + return id; + } + + /** + * Internal set to integer. + * + * @param i integer value + */ + protected void internalSetIndex(int i) { + id = i; + } + + @Override + public void set(DBIDRef ref) { + id = ref.internalGetIndex(); + } + + @Override + public DBID get(int i) { + if (i != 0) { + throw new ArrayIndexOutOfBoundsException(); + } + return new IntegerDBID(i); + } + + @Override + public DBIDArrayIter iter() { + return new DBIDItr(); + } + + @Override + public int size() { + return 1; + } + + @Override + public int binarySearch(DBIDRef key) { + final int other = key.internalGetIndex(); + return (other == id) ? 0 : (other < id) ? -1 : -2; + } + + @Override + public boolean contains(DBIDRef o) { + return id == o.internalGetIndex(); + } + + /** + * Pseudo iterator for DBIDs interface. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected class DBIDItr implements DBIDArrayIter, IntegerDBIDRef { + /** + * Iterator position: We use an integer so we can support retract(). + */ + int pos = 0; + + @Override + public void advance() { + pos++; + } + + @Override + public void advance(int count) { + pos += count; + } + + @Override + public void retract() { + pos--; + } + + @Override + public void seek(int off) { + pos = off; + } + + @Override + public int getOffset() { + return pos; + } + + @Override + public int internalGetIndex() { + return IntegerDBIDVar.this.id; + } + + @Override + public boolean valid() { + return (pos == 0); + } + + @Override + public int hashCode() { + // Override, because we also are overriding equals. + return super.hashCode(); + } + + @Override + public boolean equals(Object other) { + if (other instanceof DBID) { + LoggingUtil.warning("Programming error detected: DBIDItr.equals(DBID). Use sameDBID()!", new Throwable()); + } + return super.equals(other); + } + + @Override + public String toString() { + return Integer.toString(internalGetIndex()); + } + } + + @Override + public boolean isEmpty() { + return false; + } + + @Override + public void assign(int i, DBIDVar var) { + if (var instanceof IntegerDBIDVar) { + ((IntegerDBIDVar)var).internalSetIndex(i); + } else { + // Much less efficient: + var.set(get(i)); + } + } + + @Override + public String toString() { + return Integer.toString(id); + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDs.java new file mode 100644 index 00000000..8ffb9c6b --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDs.java @@ -0,0 +1,35 @@ +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 de.lmu.ifi.dbs.elki.database.ids.DBIDs; + +/** + * Integer DBID collection. + * + * @author Erich Schubert + */ +public interface IntegerDBIDs extends DBIDs { + @Override + IntegerDBIDIter iter(); +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDoubleDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDoubleDBIDPair.java new file mode 100644 index 00000000..fe8c6a60 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDoubleDBIDPair.java @@ -0,0 +1,83 @@ +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 de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDPair; + +/** + * Pair containing a double value and an integer DBID. + * + * @author Erich Schubert + */ +class IntegerDoubleDBIDPair implements DoubleDBIDPair, IntegerDBIDRef { + /** + * The double value. + */ + double value; + + /** + * The DB id. + */ + int id; + + /** + * Constructor. + * + * @param value Double value + * @param id DBID + */ + protected IntegerDoubleDBIDPair(double value, int id) { + super(); + this.value = value; + this.id = id; + } + + @Override + public int internalGetIndex() { + return id; + } + + @Override + public int compareTo(DoubleDBIDPair o) { + return Double.compare(value, o.doubleValue()); + } + + @Override + public double doubleValue() { + return value; + } + + @Override + @Deprecated + public Double getFirst() { + return new Double(value); + } + + @Override + @Deprecated + public DBID getSecond() { + return new IntegerDBID(id); + } +} 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 01e42fe9..f6df2e0d 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 @@ -29,6 +29,7 @@ import java.util.BitSet; 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.DBIDRange; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.logging.Logging; /** @@ -45,19 +46,20 @@ public class ReusingDBIDFactory extends SimpleDBIDFactory { /** * Logging for error messages. */ - private static final Logging logger = Logging.getLogger(ReusingDBIDFactory.class); - + private static final Logging LOG = Logging.getLogger(ReusingDBIDFactory.class); + /** * Bit set to keep track of dynamic DBIDs */ BitSet dynamicUsed = new BitSet(); - + /** * Keep track of the lowest unused dynamic DBID */ int dynamicStart = 0; - // TODO: add an offset, to save keeping long bit sets of 1s for heavy dynamic use? + // TODO: add an offset, to save keeping long bit sets of 1s for heavy dynamic + // use? /** * Returned range allocations @@ -79,12 +81,13 @@ public class ReusingDBIDFactory extends SimpleDBIDFactory { } @Override - public synchronized void deallocateSingleDBID(DBID id) { - if (id.getIntegerID() >= 0) { - logger.warning("Single DBID returned is from a range allocation!"); + public synchronized void deallocateSingleDBID(DBIDRef id) { + final int intid = id.internalGetIndex(); + if (intid >= 0) { + LOG.warning("Single DBID returned is from a range allocation!"); return; } - int pos = - id.getIntegerID() - 1; + final int pos = -intid - 1; dynamicUsed.clear(pos); dynamicStart = Math.min(dynamicStart, pos); } @@ -113,6 +116,6 @@ public class ReusingDBIDFactory extends SimpleDBIDFactory { @Override public synchronized void deallocateDBIDRange(DBIDRange range) { // TODO: catch an eventual cast exception? - returnedAllocations.add((IntegerDBIDRange)range); + returnedAllocations.add((IntegerDBIDRange) range); } -}
\ No newline at end of file +} 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 8003e4ae..77c1a91b 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 @@ -29,8 +29,14 @@ 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.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DistanceDBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDistanceDBIDPair; import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; 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,7 +58,7 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; */ public class SimpleDBIDFactory implements DBIDFactory { /** - * Keep track of the smallest dynamic DBID offset not used + * Keep track of the smallest dynamic DBID offset not used. */ int dynamicids = 0; @@ -60,9 +66,14 @@ public class SimpleDBIDFactory implements DBIDFactory { * The starting point for static DBID range allocations. */ int rangestart = 0; + + /** + * Invalid ID. + */ + DBID invalid = new IntegerDBID(Integer.MIN_VALUE); /** - * Constructor + * Constructor. */ public SimpleDBIDFactory() { super(); @@ -78,8 +89,8 @@ public class SimpleDBIDFactory implements DBIDFactory { } @Override - public void deallocateSingleDBID(DBID id) { - // ignore. + public void deallocateSingleDBID(DBIDRef id) { + // ignore for now. } @Override @@ -103,6 +114,37 @@ public class SimpleDBIDFactory implements DBIDFactory { } @Override + public void assignVar(DBIDVar var, int val) { + if (var instanceof IntegerDBIDVar) { + ((IntegerDBIDVar)var).internalSetIndex(val); + } else { + var.set(new IntegerDBID(val)); + } + } + + @Override + public int compare(DBIDRef a, DBIDRef b) { + final int inta = a.internalGetIndex(); + final int intb = b.internalGetIndex(); + return (inta < intb ? -1 : (inta == intb ? 0 : 1)); + } + + @Override + public boolean equal(DBIDRef a, DBIDRef b) { + return a.internalGetIndex() == b.internalGetIndex(); + } + + @Override + public String toString(DBIDRef id) { + return Integer.toString(id.internalGetIndex()); + } + + @Override + public DBIDVar newVar(DBIDRef val) { + return new IntegerDBIDVar(val); + } + + @Override public ArrayModifiableDBIDs newArray() { return new TroveArrayModifiableDBIDs(); } @@ -133,22 +175,46 @@ public class SimpleDBIDFactory implements DBIDFactory { } @Override - public DBIDPair makePair(DBIDRef first, DBIDRef second) { - return new IntegerDBIDPair(first.getIntegerID(), second.getIntegerID()); + public DBIDPair newPair(DBIDRef first, DBIDRef second) { + return new IntegerDBIDPair(first.internalGetIndex(), second.internalGetIndex()); + } + + @Override + public DoubleDBIDPair newPair(double val, DBIDRef id) { + return new IntegerDoubleDBIDPair(val, id.internalGetIndex()); + } + + @SuppressWarnings("unchecked") + @Override + public <D extends Distance<D>> DistanceDBIDPair<D> newDistancePair(D val, DBIDRef id) { + if (val instanceof DoubleDistance) { + return (DistanceDBIDPair<D>) new DoubleDistanceIntegerDBIDPair(((DoubleDistance) val).doubleValue(), id.internalGetIndex()); + } + return new DistanceIntegerDBIDPair<D>(val, id.internalGetIndex()); + } + + @Override + public DoubleDistanceDBIDPair newDistancePair(double val, DBIDRef id) { + return new DoubleDistanceIntegerDBIDPair(val, id.internalGetIndex()); } @Override public ByteBufferSerializer<DBID> getDBIDSerializer() { - return IntegerDBID.dynamicSerializer; + return IntegerDBID.DYNAMIC_SERIALIZER; } @Override public FixedSizeByteBufferSerializer<DBID> getDBIDSerializerStatic() { - return IntegerDBID.staticSerializer; + return IntegerDBID.STATIC_SERIALIZER; } @Override public Class<? extends DBID> getTypeRestriction() { return IntegerDBID.class; } + + @Override + public DBIDRef invalid() { + return invalid; + } }
\ No newline at end of file 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 80f65f29..a9d8aa90 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 @@ -31,15 +31,21 @@ 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.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DistanceDBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDistanceDBIDPair; import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; 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; /** - * Trivial DBID management, that never reuses IDs and just gives them out in sequence. - * Statically allocated DBID ranges are given positive values, + * Trivial DBID management, that never reuses IDs and just gives them out in + * sequence. Statically allocated DBID ranges are given positive values, * Dynamically allocated DBIDs are given negative values. * * @author Erich Schubert @@ -52,21 +58,26 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; * @apiviz.uses TroveArrayModifiableDBIDs oneway - - «create» * @apiviz.uses TroveHashSetModifiableDBIDs oneway - - «create» */ -public class TrivialDBIDFactory implements DBIDFactory { +final public class TrivialDBIDFactory implements DBIDFactory { /** - * Keep track of the smallest dynamic DBID offset not used + * Keep track of the smallest dynamic DBID offset not used. */ AtomicInteger next = new AtomicInteger(1); - + /** - * Constructor + * Invalid ID. + */ + DBID invalid = new IntegerDBID(Integer.MIN_VALUE); + + /** + * Constructor. */ public TrivialDBIDFactory() { super(); } @Override - public DBID generateSingleDBID() { + final public DBID generateSingleDBID() { final int id = next.getAndIncrement(); if (id == Integer.MAX_VALUE) { throw new AbortException("DBID allocation error - too many objects allocated!"); @@ -76,12 +87,12 @@ public class TrivialDBIDFactory implements DBIDFactory { } @Override - public void deallocateSingleDBID(DBID id) { - // ignore. + final public void deallocateSingleDBID(DBIDRef id) { + // ignore for now } @Override - public DBIDRange generateStaticDBIDRange(int size) { + final public DBIDRange generateStaticDBIDRange(int size) { final int start = next.getAndAdd(size); if (start > next.get()) { throw new AbortException("DBID range allocation error - too many objects allocated!"); @@ -101,6 +112,37 @@ public class TrivialDBIDFactory implements DBIDFactory { } @Override + public void assignVar(DBIDVar var, int val) { + if (var instanceof IntegerDBIDVar) { + ((IntegerDBIDVar)var).internalSetIndex(val); + } else { + var.set(new IntegerDBID(val)); + } + } + + @Override + public int compare(DBIDRef a, DBIDRef b) { + final int inta = a.internalGetIndex(); + final int intb = b.internalGetIndex(); + return (inta < intb ? -1 : (inta == intb ? 0 : 1)); + } + + @Override + public boolean equal(DBIDRef a, DBIDRef b) { + return a.internalGetIndex() == b.internalGetIndex(); + } + + @Override + public String toString(DBIDRef id) { + return Integer.toString(id.internalGetIndex()); + } + + @Override + public DBIDVar newVar(DBIDRef val) { + return new IntegerDBIDVar(val); + } + + @Override public ArrayModifiableDBIDs newArray() { return new TroveArrayModifiableDBIDs(); } @@ -131,22 +173,46 @@ public class TrivialDBIDFactory implements DBIDFactory { } @Override - public DBIDPair makePair(DBIDRef first, DBIDRef second) { - return new IntegerDBIDPair(first.getIntegerID(), second.getIntegerID()); + public DBIDPair newPair(DBIDRef first, DBIDRef second) { + return new IntegerDBIDPair(first.internalGetIndex(), second.internalGetIndex()); + } + + @Override + public DoubleDBIDPair newPair(double val, DBIDRef id) { + return new IntegerDoubleDBIDPair(val, id.internalGetIndex()); + } + + @SuppressWarnings("unchecked") + @Override + public <D extends Distance<D>> DistanceDBIDPair<D> newDistancePair(D val, DBIDRef id) { + if (val instanceof DoubleDistance) { + return (DistanceDBIDPair<D>) new DoubleDistanceIntegerDBIDPair(((DoubleDistance) val).doubleValue(), id.internalGetIndex()); + } + return new DistanceIntegerDBIDPair<D>(val, id.internalGetIndex()); + } + + @Override + public DoubleDistanceDBIDPair newDistancePair(double val, DBIDRef id) { + return new DoubleDistanceIntegerDBIDPair(val, id.internalGetIndex()); } @Override public ByteBufferSerializer<DBID> getDBIDSerializer() { - return IntegerDBID.dynamicSerializer; + return IntegerDBID.DYNAMIC_SERIALIZER; } @Override public FixedSizeByteBufferSerializer<DBID> getDBIDSerializerStatic() { - return IntegerDBID.staticSerializer; + return IntegerDBID.STATIC_SERIALIZER; } @Override public Class<? extends DBID> getTypeRestriction() { return IntegerDBID.class; } -}
\ No newline at end of file + + @Override + public DBIDRef invalid() { + return invalid; + } +} 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 index e2bfbcd5..313a0f3b 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java @@ -24,13 +24,12 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; */ 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.DBIDMIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; import de.lmu.ifi.dbs.elki.logging.LoggingUtil; /** @@ -39,23 +38,18 @@ import de.lmu.ifi.dbs.elki.logging.LoggingUtil; * @author Erich Schubert * * @apiviz.has IntegerDBID - * @apiviz.has TroveIteratorAdapter + * @apiviz.has DBIDItr */ -public abstract class TroveArrayDBIDs implements ArrayDBIDs { +public abstract class TroveArrayDBIDs implements ArrayDBIDs, IntegerDBIDs { /** - * Get the array store + * Get the array store. * * @return the store */ - abstract protected TIntList getStore(); + protected abstract TIntList getStore(); @Override - public Iterator<DBID> iterator() { - return new TroveIteratorAdapter(getStore().iterator()); - } - - @Override - public DBIDMIter iter() { + public IntegerDBIDArrayMIter iter() { return new DBIDItr(getStore()); } @@ -65,10 +59,20 @@ public abstract class TroveArrayDBIDs implements ArrayDBIDs { } @Override + public void assign(int index, DBIDVar var) { + if (var instanceof IntegerDBIDVar) { + ((IntegerDBIDVar)var).internalSetIndex(getStore().get(index)); + } else { + // Much less efficient: + var.set(get(index)); + } + } + + @Override public int size() { return getStore().size(); } - + @Override public boolean isEmpty() { return getStore().isEmpty(); @@ -76,29 +80,43 @@ public abstract class TroveArrayDBIDs implements ArrayDBIDs { @Override public boolean contains(DBIDRef o) { - return getStore().contains(o.getIntegerID()); + return getStore().contains(DBIDUtil.asInteger(o)); } @Override public int binarySearch(DBIDRef key) { - return getStore().binarySearch(key.getIntegerID()); + return getStore().binarySearch(DBIDUtil.asInteger(key)); + } + + @Override + public String toString() { + StringBuilder buf = new StringBuilder(); + buf.append('['); + for(DBIDIter iter = iter(); iter.valid(); iter.advance()) { + if(buf.length() > 1) { + buf.append(", "); + } + buf.append(((IntegerDBIDRef) iter).internalGetIndex()); + } + buf.append(']'); + return buf.toString(); } /** - * Iterate over a Trove IntList, ELKI/C-style + * Iterate over a Trove IntList, ELKI/C-style. * * @author Erich Schubert * * @apiviz.exclude */ - protected static class DBIDItr implements DBIDMIter { + protected static class DBIDItr implements IntegerDBIDArrayMIter { /** - * Current position + * Current position. */ int pos = 0; /** - * The actual store we use + * The actual store we use. */ TIntList store; @@ -114,7 +132,7 @@ public abstract class TroveArrayDBIDs implements ArrayDBIDs { @Override public boolean valid() { - return pos < store.size(); + return pos < store.size() && pos >= 0; } @Override @@ -123,13 +141,28 @@ public abstract class TroveArrayDBIDs implements ArrayDBIDs { } @Override - public int getIntegerID() { - return store.get(pos); + public void advance(int count) { + pos += count; } @Override - public DBID getDBID() { - return new IntegerDBID(store.get(pos)); + public void retract() { + pos--; + } + + @Override + public void seek(int off) { + pos = off; + } + + @Override + public int getOffset() { + return pos; + } + + @Override + public int internalGetIndex() { + return store.get(pos); } @Override @@ -139,23 +172,22 @@ public abstract class TroveArrayDBIDs implements ArrayDBIDs { } @Override - public boolean sameDBID(DBIDRef other) { - return store.get(pos) == other.getIntegerID(); + public int hashCode() { + // Since we add a warning to 'equals', we also override hashCode. + return super.hashCode(); } @Override public boolean equals(Object other) { - if (other instanceof DBID) { - LoggingUtil.warning("Programming error detected: DBIDItr.equals(DBID). Use sameDBID()!", new Throwable()); + if(other instanceof DBID) { + LoggingUtil.warning("Programming error detected: DBIDItr.equals(DBID). Use DBIDUtil.equal(iter, id)!", new Throwable()); } return super.equals(other); } @Override - public int compareDBID(DBIDRef o) { - final int thisVal = store.get(pos); - final int anotherVal = o.getIntegerID(); - return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1)); + public String toString() { + return Integer.toString(internalGetIndex()); } } }
\ 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 index 379ea8a6..7e84eb56 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java @@ -25,13 +25,13 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; 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.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; /** @@ -81,8 +81,8 @@ class TroveArrayModifiableDBIDs extends TroveArrayDBIDs implements ArrayModifiab @Override public boolean addDBIDs(DBIDs ids) { boolean success = false; - for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - success |= store.add(iter.getIntegerID()); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + success |= store.add(DBIDUtil.asInteger(iter)); } return success; } @@ -90,25 +90,25 @@ class TroveArrayModifiableDBIDs extends TroveArrayDBIDs implements ArrayModifiab @Override public boolean removeDBIDs(DBIDs ids) { boolean success = false; - for(DBID id : ids) { - success |= store.remove(id.getIntegerID()); + for (DBIDIter id = ids.iter(); id.valid(); id.advance()) { + success |= store.remove(DBIDUtil.asInteger(id)); } return success; } @Override public boolean add(DBIDRef e) { - return store.add(e.getIntegerID()); + return store.add(DBIDUtil.asInteger(e)); } @Override public boolean remove(DBIDRef o) { - return store.remove(o.getIntegerID()); + return store.remove(DBIDUtil.asInteger(o)); } @Override - public DBID set(int index, DBID element) { - int prev = store.set(index, element.getIntegerID()); + public DBID set(int index, DBIDRef element) { + int prev = store.set(index, DBIDUtil.asInteger(element)); return new IntegerDBID(prev); } @@ -128,23 +128,27 @@ class TroveArrayModifiableDBIDs extends TroveArrayDBIDs implements ArrayModifiab } @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()); - } + public void sort(Comparator<? super DBIDRef> comparator) { + // TODO: we no longer produce a lot of DBIDs anymore, but it would be even + // cooler if we could access store._data directly... + int[] data = store.toArray(); + IntegerDBIDArrayQuickSort.sort(data, comparator); + store.clear(); + store.add(data); + } + + @Override + public void sort(int start, int end, Comparator<? super DBIDRef> comparator) { + // TODO: we no longer produce a lot of DBIDs anymore, but it would be even + // cooler if we could access store._data directly... + int[] data = store.toArray(); + IntegerDBIDArrayQuickSort.sort(data, start, end, comparator); + store.clear(); + store.add(data); } @Override public void swap(int a, int b) { store.set(a, store.set(b, store.get(a))); } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayStaticDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayStaticDBIDs.java index 53ab34d4..60dd50eb 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayStaticDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayStaticDBIDs.java @@ -23,16 +23,15 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; */ import gnu.trove.list.TIntList; -import de.lmu.ifi.dbs.elki.database.ids.ArrayStaticDBIDs; /** * Class accessing a trove int array. * * @author Erich Schubert */ -class TroveArrayStaticDBIDs extends TroveArrayDBIDs implements ArrayStaticDBIDs { +class TroveArrayStaticDBIDs extends TroveArrayDBIDs implements IntegerArrayStaticDBIDs { /** - * Actual trove store + * Actual trove store. */ private final TIntList 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 index 12656f7b..9e65b3ae 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java @@ -1,16 +1,15 @@ 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.DBIDMIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +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.HashSetModifiableDBIDs; +import de.lmu.ifi.dbs.elki.utilities.iterator.Iter; /* This file is part of ELKI: @@ -41,9 +40,9 @@ import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; * @author Erich Schubert * * @apiviz.has IntegerDBID - * @apiviz.has TroveIteratorAdapter + * @apiviz.has DBIDItr */ -class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs { +class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs, IntegerDBIDs { /** * The actual store. */ @@ -78,15 +77,15 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs { } @Override - public DBIDMIter iter() { + public IntegerDBIDMIter 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()); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + success |= store.add(DBIDUtil.asInteger(iter)); } return success; } @@ -94,28 +93,27 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs { @Override public boolean removeDBIDs(DBIDs ids) { boolean success = false; - for(DBID id : ids) { - success |= store.remove(id.getIntegerID()); + for (DBIDIter id = ids.iter(); id.valid(); id.advance()) { + success |= store.remove(DBIDUtil.asInteger(id)); } return success; } @Override public boolean add(DBIDRef e) { - return store.add(e.getIntegerID()); + return store.add(DBIDUtil.asInteger(e)); } @Override public boolean remove(DBIDRef o) { - return store.remove(o.getIntegerID()); + return store.remove(DBIDUtil.asInteger(o)); } @Override public boolean retainAll(DBIDs set) { boolean modified = false; - Iterator<DBID> it = iterator(); - while(it.hasNext()) { - if(!set.contains(it.next())) { + for (DBIDMIter it = iter(); it.valid(); it.advance()) { + if (!set.contains(it)) { it.remove(); modified = true; } @@ -124,11 +122,6 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs { } @Override - public Iterator<DBID> iterator() { - return new TroveIteratorAdapter(store.iterator()); - } - - @Override public int size() { return store.size(); } @@ -145,7 +138,21 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs { @Override public boolean contains(DBIDRef o) { - return store.contains(o.getIntegerID()); + return store.contains(DBIDUtil.asInteger(o)); + } + + @Override + public String toString() { + StringBuilder buf = new StringBuilder(); + buf.append('['); + for (DBIDIter iter = iter(); iter.valid(); iter.advance()) { + if (buf.length() > 1) { + buf.append(", "); + } + buf.append(iter.toString()); + } + buf.append(']'); + return buf.toString(); } /** @@ -155,11 +162,11 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs { * * @apiviz.exclude */ - protected static class DBIDItr extends THashPrimitiveIterator implements DBIDMIter { + protected static class DBIDItr implements IntegerDBIDMIter { /** - * The has we access + * The actual iterator. We don't have multi inheritance. */ - private TIntHash hash; + TIntHashItr it; /** * Constructor. @@ -167,41 +174,77 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs { * @param hash Trove hash */ public DBIDItr(TIntHash hash) { - super(hash); - this.hash = hash; - this._index = nextIndex(); // Find first element + super(); + this.it = new TIntHashItr(hash); } @Override public boolean valid() { - return _index >= 0; + return it.valid(); } @Override public void advance() { - this._index = nextIndex(); + it.advance(); } @Override - public int getIntegerID() { - return hash._set[_index]; + public int internalGetIndex() { + return it.getInt(); } @Override - public DBID getDBID() { - return new IntegerDBID(hash._set[_index]); + public String toString() { + return Integer.toString(internalGetIndex()); } @Override - public boolean sameDBID(DBIDRef other) { - return getIntegerID() == other.getIntegerID(); + public void remove() { + it.remove(); } - @Override - public int compareDBID(DBIDRef o) { - final int thisVal = hash._set[_index]; - final int anotherVal = o.getIntegerID(); - return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1)); + /** + * Custom iterator over TIntHash. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + private static class TIntHashItr extends THashPrimitiveIterator implements Iter { + /** + * The hash we access. + */ + private TIntHash hash; + + /** + * Constructor. + * + * @param hash Hash to iterate over. + */ + public TIntHashItr(TIntHash hash) { + super(hash); + this.hash = hash; + this._index = nextIndex(); // Find first element + } + + /** + * Get the current value. + * + * @return Current value + */ + public int getInt() { + return hash._set[_index]; + } + + @Override + public void advance() { + this._index = nextIndex(); + } + + @Override + public boolean valid() { + return _index >= 0; + } } } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerArrayDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerArrayDBIDs.java new file mode 100644 index 00000000..14e26748 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerArrayDBIDs.java @@ -0,0 +1,160 @@ +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 de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDMIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; + +/** + * Unmodifiable wrapper for DBIDs. + * + * @author Erich Schubert + * + * @apiviz.uses TroveArrayDBIDs + * @apiviz.has UnmodifiableDBIDIter + */ +public class UnmodifiableIntegerArrayDBIDs implements IntegerArrayStaticDBIDs { + /** + * The DBIDs we wrap. + */ + private final TroveArrayDBIDs inner; + + /** + * Constructor. + * + * @param inner Inner DBID collection. + */ + public UnmodifiableIntegerArrayDBIDs(TroveArrayDBIDs inner) { + super(); + this.inner = inner; + } + + @Override + public boolean contains(DBIDRef o) { + return inner.contains(o); + } + + @Override + public boolean isEmpty() { + return inner.isEmpty(); + } + + @Override + public IntegerDBIDArrayIter iter() { + IntegerDBIDArrayIter it = inner.iter(); + if (it instanceof DBIDMIter) { + return new UnmodifiableDBIDIter(it); + } + return it; + } + + @Override + public int size() { + return inner.size(); + } + + @Override + public String toString() { + return inner.toString(); + } + + @Override + public DBID get(int i) { + return inner.get(i); + } + + @Override + public void assign(int index, DBIDVar var) { + inner.assign(index, var); + } + + @Override + public int binarySearch(DBIDRef key) { + return inner.binarySearch(key); + } + + /** + * Make an existing DBIDMIter unmodifiable. + * + * @author Erich Schubert + */ + class UnmodifiableDBIDIter implements IntegerDBIDArrayIter { + /** + * Wrapped iterator. + */ + private IntegerDBIDArrayIter it; + + /** + * Constructor. + * + * @param it inner iterator + */ + public UnmodifiableDBIDIter(IntegerDBIDArrayIter it) { + super(); + this.it = it; + } + + @Override + public boolean valid() { + return it.valid(); + } + + @Override + public void advance() { + it.advance(); + } + + @Override + public void advance(int count) { + it.advance(count); + } + + @Override + public void retract() { + it.retract(); + } + + @Override + public void seek(int off) { + it.seek(off); + } + + @Override + public int getOffset() { + return it.getOffset(); + } + + @Override + public int internalGetIndex() { + return it.internalGetIndex(); + } + + @Override + public String toString() { + return it.toString(); + } + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerDBIDs.java new file mode 100644 index 00000000..1d27f530 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerDBIDs.java @@ -0,0 +1,119 @@ +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 de.lmu.ifi.dbs.elki.database.ids.DBIDMIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.StaticDBIDs; + +/** + * Unmodifiable wrapper for DBIDs. + * + * @author Erich Schubert + * + * @apiviz.uses IntegerDBIDs + * @apiviz.has UnmodifiableDBIDIter + */ +public class UnmodifiableIntegerDBIDs implements StaticDBIDs, IntegerDBIDs { + /** + * The DBIDs we wrap. + */ + private final IntegerDBIDs inner; + + /** + * Constructor. + * + * @param inner Inner DBID collection. + */ + public UnmodifiableIntegerDBIDs(IntegerDBIDs inner) { + super(); + this.inner = inner; + } + + @Override + public boolean contains(DBIDRef o) { + return inner.contains(o); + } + + @Override + public boolean isEmpty() { + return inner.isEmpty(); + } + + @Override + public IntegerDBIDIter iter() { + IntegerDBIDIter it = inner.iter(); + if (it instanceof DBIDMIter) { + return new UnmodifiableDBIDIter(it); + } + return it; + } + + @Override + public int size() { + return inner.size(); + } + + @Override + public String toString() { + return inner.toString(); + } + + /** + * Make an existing DBIDMIter unmodifiable. + * + * @author Erich Schubert + */ + class UnmodifiableDBIDIter implements IntegerDBIDIter { + /** + * Wrapped iterator. + */ + private IntegerDBIDIter it; + + /** + * Constructor. + * + * @param it inner iterator + */ + public UnmodifiableDBIDIter(IntegerDBIDIter it) { + super(); + this.it = it; + } + + @Override + public boolean valid() { + return it.valid(); + } + + @Override + public void advance() { + it.advance(); + } + + @Override + public int internalGetIndex() { + return it.internalGetIndex(); + } + } +} 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 2c7de1c5..71af955c 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 @@ -50,7 +50,6 @@ * }</pre> * * <h2>Utility functions:</h2> - * The static {@link de.lmu.ifi.dbs.elki.database.ids.DBIDUtil DBIDUtil} class provides various utility functions, including: * <ul> * <li>{@link de.lmu.ifi.dbs.elki.database.ids.DBIDUtil#ensureArray DBIDUtil.ensureArray} to ensure {@link de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs ArrayDBIDs}</li> * <li>{@link de.lmu.ifi.dbs.elki.database.ids.DBIDUtil#ensureModifiable DBIDUtil.ensureModifiable} to ensure {@link de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs ModifiableDBIDS}</li> @@ -64,10 +63,18 @@ * <p>{@link de.lmu.ifi.dbs.elki.database.ids.generic.MaskedDBIDs MaskedDBIDs} * allows masking an ArrayDBIDs with a BitSet.</p> * + * @apiviz.exclude de.lmu.ifi.dbs.elki.database.ids.DBIDFactory * @apiviz.exclude de.lmu.ifi.dbs.elki.database.ids.integer.* - * @apiviz.exclude de.lmu.ifi.dbs.elki.database.ids.generic.Generic* - * @apiviz.exclude de.lmu.ifi.dbs.elki.data.cluster.Cluster - * @apiviz.exclude de.lmu.ifi.dbs.elki.utilities.datastructures.heap.* + * @apiviz.exclude de.lmu.ifi.dbs.elki.database.ids.generic.* + * @apiviz.exclude de.lmu.ifi.dbs.elki.database.ids.EmptyDBIDs.EmptyDBIDIterator + * @apiviz.exclude de.lmu.ifi.dbs.elki.database.*Database + * @apiviz.exclude de.lmu.ifi.dbs.elki.data.Cluster + * @apiviz.exclude de.lmu.ifi.dbs.elki.utilities.* + * @apiviz.exclude de.lmu.ifi.dbs.elki.datasource.filter.* + * @apiviz.exclude de.lmu.ifi.dbs.elki.database.query.* + * @apiviz.exclude de.lmu.ifi.dbs.elki.distance.* + * @apiviz.exclude de.lmu.ifi.dbs.elki.index.* + * @apiviz.exclude de.lmu.ifi.dbs.elki.result.* * @apiviz.exclude de.lmu.ifi.dbs.elki.persistent.* * @apiviz.exclude de.lmu.ifi.dbs.elki.algorithm.* * @apiviz.exclude java.* @@ -94,4 +101,4 @@ 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 +package de.lmu.ifi.dbs.elki.database.ids; 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 c39600f7..73cf0596 100644 --- a/src/de/lmu/ifi/dbs/elki/database/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/package-info.java @@ -1,5 +1,9 @@ /** * <p>ELKI database layer - loading, storing, indexing and accessing data</p> + * + * @apiviz.exclude elki.utilities + * @apiviz.exclude elki.result + * @apiviz.exclude elki.workflow */ /* This file is part of ELKI: @@ -23,4 +27,4 @@ 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/>. */ -package de.lmu.ifi.dbs.elki.database;
\ No newline at end of file +package de.lmu.ifi.dbs.elki.database; diff --git a/src/de/lmu/ifi/dbs/elki/database/query/DoubleDistanceResultPair.java b/src/de/lmu/ifi/dbs/elki/database/query/DoubleDistanceResultPair.java deleted file mode 100644 index 23abc327..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/query/DoubleDistanceResultPair.java +++ /dev/null @@ -1,165 +0,0 @@ -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) 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.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; - -/** - * Optimized DistanceResultPair that avoids/postpones an extra layer of boxing - * for double values. - * - * @author Erich Schubert - */ -public class DoubleDistanceResultPair implements DistanceResultPair<DoubleDistance> { - /** - * Distance value - */ - double distance; - - /** - * Object ID - */ - DBID id; - - /** - * Constructor. - * - * @param distance Distance value - * @param id Object ID - */ - public DoubleDistanceResultPair(double distance, DBID id) { - super(); - this.distance = distance; - this.id = id; - } - - @Override - public DoubleDistance getDistance() { - return new DoubleDistance(distance); - } - - @Override - public void setDistance(DoubleDistance distance) { - this.distance = distance.doubleValue(); - } - - @Override - public DBID getDBID() { - return id; - } - - @Override - public int getIntegerID() { - return id.getIntegerID(); - } - - @Override - public boolean sameDBID(DBIDRef other) { - return id.sameDBID(other); - } - - @Override - public int compareDBID(DBIDRef other) { - return id.compareDBID(other); - } - - @Override - public void setID(DBID id) { - this.id = id; - } - - /** - * @deprecated Use {@link #getDoubleDistance} or {@link #getDistance} for clearness. - */ - @Deprecated - @Override - public DoubleDistance getFirst() { - return getDistance(); - } - - /** - * @deprecated Use {@link #getDBID} for clearness. - */ - @Deprecated - @Override - public DBID getSecond() { - return id; - } - - @Override - public int compareByDistance(DistanceResultPair<DoubleDistance> o) { - if(o instanceof DoubleDistanceResultPair) { - DoubleDistanceResultPair od = (DoubleDistanceResultPair) o; - final int delta = Double.compare(distance, od.distance); - if(delta != 0) { - return delta; - } - } - else { - final int delta = Double.compare(distance, o.getDistance().doubleValue()); - if(delta != 0) { - return delta; - } - } - return 0; - } - - @Override - public int compareTo(DistanceResultPair<DoubleDistance> o) { - final int delta = this.compareByDistance(o); - if(delta != 0) { - return delta; - } - return id.compareTo(o.getDBID()); - } - - @Override - public boolean equals(Object obj) { - if(!(obj instanceof DistanceResultPair)) { - return false; - } - if(obj instanceof DoubleDistanceResultPair) { - DoubleDistanceResultPair ddrp = (DoubleDistanceResultPair) obj; - return distance == ddrp.distance && id.sameDBID(ddrp.id); - } - DistanceResultPair<?> other = (DistanceResultPair<?>) obj; - return other.getDistance().equals(distance) && id.sameDBID(other.getDBID()); - } - - /** - * Get the distance as double value. - * - * @return distance value - */ - public double getDoubleDistance() { - return distance; - } - - @Override - public String toString() { - return "DistanceResultPair(" + distance + ", " + id + ")"; - } -}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceResultPair.java b/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceResultPair.java deleted file mode 100644 index 414f145a..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/query/GenericDistanceResultPair.java +++ /dev/null @@ -1,131 +0,0 @@ -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) 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.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.utilities.pairs.Pair; - -/** - * Trivial implementation using a generic pair. - * - * @author Erich Schubert - * - * @param <D> Distance type - */ -public class GenericDistanceResultPair<D extends Distance<D>> extends Pair<D, DBID> implements DistanceResultPair<D> { - /** - * Canonical constructor - * - * @param first Distance - * @param second Object ID - */ - public GenericDistanceResultPair(D first, DBID second) { - super(first, second); - } - - /** - * Getter for first - * - * @return first element in pair - */ - @Override - public final D getDistance() { - return first; - } - - /** - * Setter for first - * - * @param first new value for first element - */ - @Override - public final void setDistance(D first) { - this.first = first; - } - - /** - * Getter for second element in pair - * - * @return second element in pair - */ - @Override - public final DBID getDBID() { - return second; - } - - @Override - public int getIntegerID() { - return second.getIntegerID(); - } - - @Override - public boolean sameDBID(DBIDRef other) { - return second.sameDBID(other); - } - - @Override - public int compareDBID(DBIDRef other) { - return second.compareDBID(other); - } - - /** - * Setter for second - * - * @param second new value for second element - */ - @Override - public final void setID(DBID second) { - this.second = second; - } - - @Override - public int compareByDistance(DistanceResultPair<D> o) { - return first.compareTo(o.getDistance()); - } - - @Override - public int compareTo(DistanceResultPair<D> o) { - final int ret = compareByDistance(o); - if(ret != 0) { - return ret; - } - return second.compareTo(o.getDBID()); - } - - @Override - public boolean equals(Object obj) { - if(!(obj instanceof DistanceResultPair)) { - return false; - } - DistanceResultPair<?> other = (DistanceResultPair<?>) obj; - return first.equals(other.getDistance()) && second.sameDBID(other.getDBID()); - } - - @Override - public String toString() { - return "DistanceResultPair(" + getFirst() + ", " + getSecond() + ")"; - } -}
\ No newline at end of file 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 2257eb98..fdd116b7 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 @@ -1,6 +1,7 @@ /** * <p>Prepared queries for distances.</p> * + * @apiviz.exclude .*Instance */ /* This file is part of ELKI: 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 e5df1452..0ac2e8ee 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 @@ -26,6 +26,7 @@ package de.lmu.ifi.dbs.elki.database.query.knn; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** 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 13bf58c2..5b517509 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 @@ -24,14 +24,12 @@ package de.lmu.ifi.dbs.elki.database.query.knn; */ import java.util.List; -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.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; /** * The interface of an actual instance. @@ -61,17 +59,7 @@ public interface KNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k Number of neighbors requested * @return neighbors */ - public List<KNNResult<D>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k); - - /** - * Bulk query method configured by a map. - * - * Warning: this API is not optimal, and might be removed soon (in fact, it is - * used in a single place) - * - * @param heaps Map of heaps to fill. - */ - public void getKNNForBulkHeaps(Map<DBID, KNNHeap<D>> heaps); + public List<? extends KNNResult<D>> getKNNForBulkDBIDs(ArrayDBIDs ids, int k); /** * Get the k nearest neighbors for a particular id. 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 deleted file mode 100644 index e7612fcc..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNResult.java +++ /dev/null @@ -1,84 +0,0 @@ -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.List; - -import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; -import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; -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 DistanceDBIDResult<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 - */ - @Override - 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 deleted file mode 100644 index 01deeaa0..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/query/knn/KNNUtil.java +++ /dev/null @@ -1,429 +0,0 @@ -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.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.ids.DBIDRef; -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 AbstractList<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(); - } - - @Override - public boolean sameDBID(DBIDRef other) { - return getIntegerID() == other.getIntegerID(); - } - - @Override - public int compareDBID(DBIDRef o) { - final int thisVal = getIntegerID(); - final int anotherVal = o.getIntegerID(); - return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1)); - } - } - - /** - * 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(DBIDRef o) { - for (DBIDIter iter = iter(); iter.valid(); iter.advance()) { - if(iter.sameDBID(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(DBIDRef 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 b51dad4c..29fa9931 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 @@ -25,20 +25,17 @@ package de.lmu.ifi.dbs.elki.database.query.knn; import java.util.ArrayList; import java.util.List; -import java.util.Map; -import java.util.Map.Entry; 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.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; 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; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNHeap; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNUtil; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; /** * Instance of this query for a particular database. @@ -67,11 +64,10 @@ public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistan private void linearScanBatchKNN(ArrayDBIDs ids, List<KNNHeap<D>> heaps) { // The distance is computed on database IDs for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - DBID candidateID = iter.getDBID(); int index = 0; - for (DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) { + for(DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) { KNNHeap<D> heap = heaps.get(index); - heap.add(distanceQuery.distance(iter2, candidateID), candidateID); + heap.add(distanceQuery.distance(iter2, iter), iter); index++; } } @@ -79,16 +75,29 @@ public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistan @Override public KNNResult<D> getKNNForDBID(DBIDRef id, int k) { - KNNHeap<D> heap = new KNNHeap<D>(k); + KNNHeap<D> heap = KNNUtil.newHeap(distanceQuery.getDistanceFactory(), k); + D max = distanceQuery.getDistanceFactory().infiniteDistance(); if(PrimitiveDistanceQuery.class.isInstance(distanceQuery)) { O obj = relation.get(id); for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - heap.add(distanceQuery.distance(obj, relation.get(iter)), iter); + final D dist = distanceQuery.distance(obj, relation.get(iter)); + if(max.compareTo(dist) > 0) { + heap.add(dist, iter); + if(heap.size() >= k) { + max = heap.getKNNDistance(); + } + } } } else { for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - heap.add(distanceQuery.distance(id, iter), iter); + final D dist = distanceQuery.distance(id, iter); + if(max.compareTo(dist) > 0) { + heap.add(dist, iter); + if(heap.size() >= k) { + max = heap.getKNNDistance(); + } + } } } return heap.toKNNList(); @@ -99,7 +108,7 @@ public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistan final int size = ids.size(); final List<KNNHeap<D>> heaps = new ArrayList<KNNHeap<D>>(size); for(int i = 0; i < size; i++) { - heaps.add(new KNNHeap<D>(k)); + heaps.add(KNNUtil.newHeap(distanceQuery.getDistanceFactory(), k)); } linearScanBatchKNN(ids, heaps); // Serialize heaps @@ -111,20 +120,8 @@ public class LinearScanKNNQuery<O, D extends Distance<D>> extends AbstractDistan } @Override - public void getKNNForBulkHeaps(Map<DBID, KNNHeap<D>> heaps) { - final int size = heaps.size(); - ArrayModifiableDBIDs ids = DBIDUtil.newArray(size); - List<KNNHeap<D>> kheaps = new ArrayList<KNNHeap<D>>(size); - for(Entry<DBID, KNNHeap<D>> ent : heaps.entrySet()) { - ids.add(ent.getKey()); - kheaps.add(ent.getValue()); - } - linearScanBatchKNN(ids, kheaps); - } - - @Override public KNNResult<D> getKNNForObject(O obj, int k) { - KNNHeap<D> heap = new KNNHeap<D>(k); + KNNHeap<D> heap = KNNUtil.newHeap(distanceQuery.getDistanceFactory(), k); for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { heap.add(distanceQuery.distance(obj, iter), iter); } 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 59987282..c4f09744 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 @@ -25,16 +25,15 @@ package de.lmu.ifi.dbs.elki.database.query.knn; import java.util.ArrayList; import java.util.List; -import java.util.Map; -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.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.distance.PrimitiveDistanceQuery; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNHeap; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNUtil; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; /** * Instance of this query for a particular database. @@ -66,12 +65,10 @@ public class LinearScanPrimitiveDistanceKNNQuery<O, D extends Distance<D>> exten final int size = objs.size(); // Linear scan style KNN. for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - DBID candidateID = iter.getDBID(); - O candidate = relation.get(candidateID); + O candidate = relation.get(iter); for(int index = 0; index < size; index++) { O object = objs.get(index); - KNNHeap<D> heap = heaps.get(index); - heap.add(distanceQuery.distance(object, candidate), candidateID); + heaps.get(index).add(distanceQuery.distance(object, candidate), iter); } } } @@ -87,7 +84,7 @@ public class LinearScanPrimitiveDistanceKNNQuery<O, D extends Distance<D>> exten final List<KNNHeap<D>> heaps = new ArrayList<KNNHeap<D>>(size); List<O> objs = new ArrayList<O>(size); for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - heaps.add(new KNNHeap<D>(k)); + heaps.add(KNNUtil.newHeap(distanceQuery.getDistanceFactory(), k)); objs.add(relation.get(iter)); } linearScanBatchKNN(objs, heaps); @@ -98,15 +95,4 @@ public class LinearScanPrimitiveDistanceKNNQuery<O, D extends Distance<D>> exten } return result; } - - @Override - public void getKNNForBulkHeaps(Map<DBID, KNNHeap<D>> heaps) { - List<O> objs = new ArrayList<O>(heaps.size()); - List<KNNHeap<D>> kheaps = new ArrayList<KNNHeap<D>>(heaps.size()); - for(Entry<DBID, KNNHeap<D>> ent : heaps.entrySet()) { - objs.add(relation.get(ent.getKey())); - kheaps.add(ent.getValue()); - } - linearScanBatchKNN(objs, kheaps); - } }
\ No newline at end of file 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 a10aaac5..5e5eae2f 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 @@ -23,16 +23,20 @@ package de.lmu.ifi.dbs.elki.database.query.knn; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Arrays; -import java.util.List; - +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.DBIDRef; -import de.lmu.ifi.dbs.elki.database.query.DoubleDistanceResultPair; +import de.lmu.ifi.dbs.elki.database.ids.DistanceDBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDistanceDBIDPair; import de.lmu.ifi.dbs.elki.database.query.distance.PrimitiveDistanceQuery; import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDoubleDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.AbstractKNNHeap; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DoubleDistanceKNNHeap; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DoubleDistanceKNNList; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.GenericKNNList; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; +import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.TiedTopBoundedHeap; /** * Optimized linear scan query for {@link PrimitiveDoubleDistanceFunction}s. @@ -45,15 +49,22 @@ import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; */ public class LinearScanRawDoubleDistanceKNNQuery<O> extends LinearScanPrimitiveDistanceKNNQuery<O, DoubleDistance> { /** + * Raw distance function. + */ + PrimitiveDoubleDistanceFunction<O> rawdist; + + /** * Constructor. * * @param distanceQuery Distance function to use */ + @SuppressWarnings("unchecked") public LinearScanRawDoubleDistanceKNNQuery(PrimitiveDistanceQuery<O, DoubleDistance> distanceQuery) { super(distanceQuery); - if(!(distanceQuery.getDistanceFunction() instanceof PrimitiveDoubleDistanceFunction)) { + if (!(distanceQuery.getDistanceFunction() instanceof PrimitiveDoubleDistanceFunction)) { throw new UnsupportedOperationException("LinearScanRawDoubleDistance instantiated for non-RawDoubleDistance!"); } + rawdist = (PrimitiveDoubleDistanceFunction<O>) distanceQuery.getDistanceFunction(); } @Override @@ -63,47 +74,70 @@ public class LinearScanRawDoubleDistanceKNNQuery<O> extends LinearScanPrimitiveD @Override public KNNResult<DoubleDistance> getKNNForObject(O obj, int k) { - @SuppressWarnings("unchecked") - final PrimitiveDoubleDistanceFunction<O> rawdist = (PrimitiveDoubleDistanceFunction<O>) distanceQuery.getDistanceFunction(); + return getKNNForObjectBenchmarked(obj, k); + } + + /** + * This is the cleaner, supposedly faster implementation. + * + * @param obj Query object + * @param k Desired number of neighbors + * @return kNN result + */ + KNNResult<DoubleDistance> getKNNForObjectClean(O obj, int k) { // Optimization for double distances. - final KNNHeap<DoubleDistance> heap = new KNNHeap<DoubleDistance>(k); - double max = Double.POSITIVE_INFINITY; - for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { + final TiedTopBoundedHeap<DoubleDistanceDBIDPair> heap = new TiedTopBoundedHeap<DoubleDistanceDBIDPair>(k, DoubleDistanceKNNHeap.COMPARATOR); + final DBIDIter iter = relation.iterDBIDs(); + + // First k elements don't need checking. + double max = 0.; + for (int i = 0; i < k && iter.valid(); i++, iter.advance()) { + final double doubleDistance = rawdist.doubleDistance(obj, relation.get(iter)); + heap.add(DBIDFactory.FACTORY.newDistancePair(doubleDistance, iter)); + max = Math.max(max, doubleDistance); + } + // Remaining elements + for (; iter.valid(); iter.advance()) { final double doubleDistance = rawdist.doubleDistance(obj, relation.get(iter)); - if(doubleDistance <= max) { - heap.add(new DoubleDistanceResultPair(doubleDistance, iter.getDBID())); - // Update cutoff - if(heap.size() >= heap.getK()) { - max = ((DoubleDistanceResultPair) heap.peek()).getDoubleDistance(); - } + if (doubleDistance <= max) { + heap.add(DBIDFactory.FACTORY.newDistancePair(doubleDistance, iter)); + } + if (doubleDistance < max) { + max = heap.peek().doubleDistance(); } } - return heap.toKNNList(); + return new DoubleDistanceKNNList(heap, k); } - @Override - protected void linearScanBatchKNN(List<O> objs, List<KNNHeap<DoubleDistance>> heaps) { - final int size = objs.size(); - @SuppressWarnings("unchecked") - final PrimitiveDoubleDistanceFunction<O> rawdist = (PrimitiveDoubleDistanceFunction<O>) distanceQuery.getDistanceFunction(); - // Track the max ourselves to reduce object access for comparisons. - final double[] max = new double[size]; - Arrays.fill(max, Double.POSITIVE_INFINITY); - - // The distance is computed on arbitrary vectors, we can reduce object - // loading by working on the actual vectors. - for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { - O candidate = relation.get(iter); - for(int index = 0; index < size; index++) { - final KNNHeap<DoubleDistance> heap = heaps.get(index); - double doubleDistance = rawdist.doubleDistance(objs.get(index), candidate); - if(doubleDistance <= max[index]) { - heap.add(new DoubleDistanceResultPair(doubleDistance, iter.getDBID())); - if(heap.size() >= heap.getK()) { - max[index] = ((DoubleDistanceResultPair) heap.peek()).getDoubleDistance(); - } - } + /** + * It does not make sense, but this version is faster in our larger + * benchmarks. Apparently, some JIT optimization kicks in better. + * + * @param obj Query object + * @param k Desired number of neighbors + * @return kNN result + */ + KNNResult<DoubleDistance> getKNNForObjectBenchmarked(O obj, int k) { + // THIS SHOULD BE SLOWER THAN THE VERSION ABOVE, BUT ISN'T! + final TiedTopBoundedHeap<DistanceDBIDPair<DoubleDistance>> heap = new TiedTopBoundedHeap<DistanceDBIDPair<DoubleDistance>>(k, AbstractKNNHeap.COMPARATOR); + final DBIDIter iter = relation.iterDBIDs(); + // First k elements don't need checking. + double max = 0.; + for (int i = 0; i < k && iter.valid(); i++, iter.advance()) { + final double doubleDistance = rawdist.doubleDistance(obj, relation.get(iter)); + heap.add(DBIDFactory.FACTORY.newDistancePair(new DoubleDistance(doubleDistance), iter)); + max = Math.max(max, doubleDistance); + } + // Remaining elements + for (; iter.valid(); iter.advance()) { + final double doubleDistance = rawdist.doubleDistance(obj, relation.get(iter)); + if (doubleDistance <= max) { + heap.add(DBIDFactory.FACTORY.newDistancePair(new DoubleDistance(doubleDistance), iter)); + } + if (doubleDistance < max) { + max = heap.peek().getDistance().doubleValue(); } } + return new GenericKNNList<DoubleDistance>(heap, k); } -}
\ No newline at end of file +} 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 09f93945..a1e12fc3 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 @@ -25,20 +25,17 @@ package de.lmu.ifi.dbs.elki.database.query.knn; import java.util.ArrayList; import java.util.List; -import java.util.Map; -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.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; 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.distanceresultlist.KNNResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNUtil; 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.logging.LoggingUtil; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; /** @@ -145,17 +142,6 @@ public class PreprocessorKNNQuery<O, D extends Distance<D>, T extends KNNResult< } @Override - public void getKNNForBulkHeaps(Map<DBID, KNNHeap<D>> heaps) { - for(Entry<DBID, KNNHeap<D>> ent : heaps.entrySet()) { - DBID id = ent.getKey(); - KNNHeap<D> heap = ent.getValue(); - for(DistanceResultPair<D> dr : preprocessor.get(id)) { - heap.add(dr); - } - } - } - - @Override public KNNResult<D> getKNNForObject(O obj, int k) { throw new AbortException("Preprocessor KNN query only supports ID queries."); } 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 891ed296..63c3aa16 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 @@ -2,6 +2,7 @@ * <p>Prepared queries for k nearest neighbor (kNN) queries.</p> * * @apiviz.exclude de.lmu.ifi.dbs.elki.algorithm.* + * @apiviz.exclude java.util.* */ /* This file is part of ELKI: @@ -25,4 +26,4 @@ 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/>. */ -package de.lmu.ifi.dbs.elki.database.query.knn;
\ No newline at end of file +package de.lmu.ifi.dbs.elki.database.query.knn; 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 05c635a0..386ce6f3 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 @@ -73,6 +73,9 @@ * knnQuery.getKNNForDBID(id, 10); * } * }</pre></blockquote> + * + * @apiviz.exclude java.util.* + * @apiviz.exclude de.lmu.ifi.dbs.elki.utilities.* */ /* This file is part of ELKI: @@ -96,4 +99,4 @@ 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/>. */ -package de.lmu.ifi.dbs.elki.database.query;
\ No newline at end of file +package de.lmu.ifi.dbs.elki.database.query; 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 871c5e9e..9997f3d6 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 @@ -25,8 +25,8 @@ package de.lmu.ifi.dbs.elki.database.query.range; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery; -import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** 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 758d603e..57fa2338 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 @@ -24,8 +24,8 @@ package de.lmu.ifi.dbs.elki.database.query.range; */ import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.database.query.distance.PrimitiveDistanceQuery; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** 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 c8ddb1ec..13e13a5c 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 @@ -23,15 +23,12 @@ package de.lmu.ifi.dbs.elki.database.query.range; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collections; - import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceDBIDList; -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.distance.distanceresultlist.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.GenericDistanceDBIDList; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** @@ -61,10 +58,10 @@ public class LinearScanRangeQuery<O, D extends Distance<D>> extends AbstractDist for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { D currentDistance = distanceQuery.distance(id, iter); if(currentDistance.compareTo(range) <= 0) { - result.add(new GenericDistanceResultPair<D>(currentDistance, iter.getDBID())); + result.add(currentDistance, iter); } } - Collections.sort(result); + result.sort(); return result; } @@ -74,10 +71,10 @@ public class LinearScanRangeQuery<O, D extends Distance<D>> extends AbstractDist for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { D currentDistance = distanceQuery.distance(obj, iter); if(currentDistance.compareTo(range) <= 0) { - result.add(new GenericDistanceResultPair<D>(currentDistance, iter.getDBID())); + result.add(currentDistance, iter); } } - Collections.sort(result); + result.sort(); return result; } }
\ No newline at end of file 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 c5ce2f55..18863b2d 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 @@ -23,17 +23,14 @@ package de.lmu.ifi.dbs.elki.database.query.range; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collections; - import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; -import de.lmu.ifi.dbs.elki.database.query.DoubleDistanceResultPair; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceDBIDList; 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; import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDoubleDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DoubleDistanceDBIDList; import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; /** @@ -63,14 +60,14 @@ public class LinearScanRawDoubleDistanceRangeQuery<O> extends LinearScanRangeQue double epsilon = range.doubleValue(); O qo = relation.get(id); - GenericDistanceDBIDList<DoubleDistance> result = new GenericDistanceDBIDList<DoubleDistance>(); + DoubleDistanceDBIDList result = new DoubleDistanceDBIDList(); for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { double doubleDistance = rawdist.doubleDistance(qo, relation.get(iter)); if(doubleDistance <= epsilon) { - result.add(new DoubleDistanceResultPair(doubleDistance, iter.getDBID())); + result.add(doubleDistance, iter); } } - Collections.sort(result); + result.sort(); return result; } else { @@ -85,14 +82,14 @@ public class LinearScanRawDoubleDistanceRangeQuery<O> extends LinearScanRangeQue PrimitiveDoubleDistanceFunction<O> rawdist = (PrimitiveDoubleDistanceFunction<O>) distanceQuery.getDistanceFunction(); double epsilon = range.doubleValue(); - GenericDistanceDBIDList<DoubleDistance> result = new GenericDistanceDBIDList<DoubleDistance>(); + DoubleDistanceDBIDList result = new DoubleDistanceDBIDList(); for(DBIDIter iter = relation.getDBIDs().iter(); iter.valid(); iter.advance()) { double doubleDistance = rawdist.doubleDistance(obj, relation.get(iter)); if(doubleDistance <= epsilon) { - result.add(new DoubleDistanceResultPair(doubleDistance, iter.getDBID())); + result.add(doubleDistance, iter); } } - Collections.sort(result); + result.sort(); return result; } else { 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 2c6842bf..9574cda7 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 @@ -25,7 +25,7 @@ package de.lmu.ifi.dbs.elki.database.query.range; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; -import de.lmu.ifi.dbs.elki.database.query.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** 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 fe4f49e1..a090b466 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 @@ -23,12 +23,10 @@ package de.lmu.ifi.dbs.elki.database.query.rknn; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.List; - import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; 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.distanceresultlist.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** @@ -53,5 +51,5 @@ public abstract class AbstractRKNNQuery<O, D extends Distance<D>> extends Abstra } @Override - abstract public List<DistanceResultPair<D>> getRKNNForDBID(DBIDRef id, int k); + abstract public DistanceDBIDResult<D> getRKNNForDBID(DBIDRef id, int k); }
\ 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 1f901828..f0e33777 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 @@ -24,20 +24,19 @@ package de.lmu.ifi.dbs.elki.database.query.rknn; */ import java.util.ArrayList; -import java.util.Collections; 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.ids.DBIDRef; 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.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.distanceresultlist.DistanceDBIDResult; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResultIter; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.GenericDistanceDBIDList; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** @@ -71,8 +70,8 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ } @Override - public List<DistanceResultPair<D>> getRKNNForObject(O obj, int k) { - ArrayList<DistanceResultPair<D>> rNNlist = new ArrayList<DistanceResultPair<D>>(); + public DistanceDBIDResult<D> getRKNNForObject(O obj, int k) { + GenericDistanceDBIDList<D> rNNlist = new GenericDistanceDBIDList<D>(); ArrayDBIDs allIDs = DBIDUtil.ensureArray(relation.getDBIDs()); List<? extends KNNResult<D>> kNNLists = knnQuery.getKNNForBulkDBIDs(allIDs, k); @@ -83,17 +82,17 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ int last = Math.min(k - 1, knn.size() - 1); D dist = distanceQuery.distance(obj, iter); if(last < k - 1 || dist.compareTo(knn.get(last).getDistance()) < 1) { - rNNlist.add(new GenericDistanceResultPair<D>(dist, iter.getDBID())); + rNNlist.add(dist, iter); } i++; } - Collections.sort(rNNlist); + rNNlist.sort(); return rNNlist; } @Override - public List<DistanceResultPair<D>> getRKNNForDBID(DBIDRef id, int k) { - ArrayList<DistanceResultPair<D>> rNNList = new ArrayList<DistanceResultPair<D>>(); + public DistanceDBIDResult<D> getRKNNForDBID(DBIDRef id, int k) { + GenericDistanceDBIDList<D> rNNList = new GenericDistanceDBIDList<D>(); ArrayDBIDs allIDs = DBIDUtil.ensureArray(relation.getDBIDs()); List<? extends KNNResult<D>> kNNList = knnQuery.getKNNForBulkDBIDs(allIDs, k); @@ -101,22 +100,22 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ int i = 0; for (DBIDIter iter = allIDs.iter(); iter.valid(); iter.advance()) { KNNResult<D> knn = kNNList.get(i); - for(DistanceResultPair<D> n : knn) { - if(n.sameDBID(id)) { - rNNList.add(new GenericDistanceResultPair<D>(n.getDistance(), iter.getDBID())); + for(DistanceDBIDResultIter<D> n = knn.iter(); n.valid(); n.advance()) { + if(DBIDUtil.equal(n, id)) { + rNNList.add(n.getDistance(), iter); } } i++; } - Collections.sort(rNNList); + rNNList.sort(); return rNNList; } @Override - public List<List<DistanceResultPair<D>>> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k) { - List<List<DistanceResultPair<D>>> rNNList = new ArrayList<List<DistanceResultPair<D>>>(ids.size()); + public List<GenericDistanceDBIDList<D>> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + List<GenericDistanceDBIDList<D>> rNNList = new ArrayList<GenericDistanceDBIDList<D>>(ids.size()); for(int i = 0; i < ids.size(); i++) { - rNNList.add(new ArrayList<DistanceResultPair<D>>()); + rNNList.add(new GenericDistanceDBIDList<D>()); } ArrayDBIDs allIDs = DBIDUtil.ensureArray(relation.getDBIDs()); @@ -124,14 +123,13 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ int i = 0; for (DBIDIter iter = allIDs.iter(); iter.valid(); iter.advance()) { - DBID qid = iter.getDBID(); KNNResult<D> knn = kNNList.get(i); - for(DistanceResultPair<D> n : knn) { + for(DistanceDBIDResultIter<D> n = knn.iter(); n.valid(); n.advance()) { int j = 0; for (DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) { - if(n.getDBID().sameDBID(iter2)) { - List<DistanceResultPair<D>> rNN = rNNList.get(j); - rNN.add(new GenericDistanceResultPair<D>(n.getDistance(), qid)); + if(DBIDUtil.equal(n, iter2)) { + GenericDistanceDBIDList<D> rNN = rNNList.get(j); + rNN.add(n.getDistance(), iter); } j++; } @@ -139,8 +137,7 @@ public class LinearScanRKNNQuery<O, D extends Distance<D>> extends AbstractRKNNQ i++; } for(int j = 0; j < ids.size(); j++) { - List<DistanceResultPair<D>> rNN = rNNList.get(j); - Collections.sort(rNN); + rNNList.get(j).sort(); } return rNNList; } 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 ab8c3b30..8256ffad 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 @@ -30,8 +30,8 @@ import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; 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.distanceresultlist.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.index.preprocessed.knn.MaterializeKNNAndRKNNPreprocessor; import de.lmu.ifi.dbs.elki.logging.LoggingUtil; @@ -75,7 +75,7 @@ public class PreprocessorRKNNQuery<O, D extends Distance<D>> extends AbstractDat } @Override - public List<DistanceResultPair<D>> getRKNNForDBID(DBIDRef id, int k) { + public DistanceDBIDResult<D> getRKNNForDBID(DBIDRef id, int k) { if(!warned && k != preprocessor.getK()) { LoggingUtil.warning("Requested more neighbors than preprocessed!"); } @@ -83,18 +83,18 @@ public class PreprocessorRKNNQuery<O, D extends Distance<D>> extends AbstractDat } @Override - public List<DistanceResultPair<D>> getRKNNForObject(O obj, int k) { + public DistanceDBIDResult<D> getRKNNForObject(O obj, int k) { throw new AbortException("Preprocessor KNN query only supports ID queries."); } @Override - public List<List<DistanceResultPair<D>>> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k) { + public List<? extends DistanceDBIDResult<D>> getRKNNForBulkDBIDs(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<DistanceDBIDResult<D>> result = new ArrayList<DistanceDBIDResult<D>>(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - result.add(preprocessor.getRKNN(iter.getDBID())); + result.add(preprocessor.getRKNN(iter)); } return result; } 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 9ff6f790..dc21948e 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 @@ -28,7 +28,7 @@ import java.util.List; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** @@ -36,7 +36,7 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * * @author Erich Schubert * - * @apiviz.uses DistanceResultPair oneway - - «create» + * @apiviz.uses DistanceDBIDResult oneway - - «create» * * @param <O> Object type * @param <D> Distance type @@ -49,7 +49,7 @@ public interface RKNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k number of neighbors requested * @return reverse k nearest neighbors */ - public List<DistanceResultPair<D>> getRKNNForDBID(DBIDRef id, int k); + public DistanceDBIDResult<D> getRKNNForDBID(DBIDRef id, int k); /** * Get the reverse k nearest neighbors for a particular object. @@ -58,7 +58,7 @@ public interface RKNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k number of neighbors requested * @return reverse k nearest neighbors */ - public List<DistanceResultPair<D>> getRKNNForObject(O obj, int k); + public DistanceDBIDResult<D> getRKNNForObject(O obj, int k); /** * Bulk query method for reverse k nearest neighbors for ids. @@ -67,5 +67,5 @@ public interface RKNNQuery<O, D extends Distance<D>> extends DatabaseQuery { * @param k number of neighbors requested * @return reverse k nearest neighbors */ - public List<List<DistanceResultPair<D>>> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k); + public List<? extends DistanceDBIDResult<D>> getRKNNForBulkDBIDs(ArrayDBIDs ids, int k); }
\ No newline at end of file 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 4898c518..b8974ac2 100644 --- a/src/de/lmu/ifi/dbs/elki/database/relation/DBIDView.java +++ b/src/de/lmu/ifi/dbs/elki/database/relation/DBIDView.java @@ -70,7 +70,7 @@ public class DBIDView extends AbstractHierarchicalResult implements Relation<DBI @Override public DBID get(DBIDRef id) { assert (ids.contains(id)); - return id.getDBID(); + return DBIDUtil.deref(id); } @Override @@ -81,8 +81,7 @@ public class DBIDView extends AbstractHierarchicalResult implements Relation<DBI @Override public void delete(DBIDRef id) { if(database instanceof UpdatableDatabase) { - // TODO: skip getDBID() - ((UpdatableDatabase) database).delete(id.getDBID()); + ((UpdatableDatabase) database).delete(id); } else { throw new UnsupportedOperationException("Deletions are not supported."); diff --git a/src/de/lmu/ifi/dbs/elki/database/relation/RelationUtil.java b/src/de/lmu/ifi/dbs/elki/database/relation/RelationUtil.java new file mode 100644 index 00000000..77f98f60 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/relation/RelationUtil.java @@ -0,0 +1,105 @@ +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) 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.data.FeatureVector; +import de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.data.type.VectorFieldTypeInformation; + +/** + * Utility functions for handling database relation. + * + * @author Erich Schubert + * + * @apiviz.uses Relation oneway + */ +public final class RelationUtil { + /** + * Fake constructor: do not instantiate. + */ + private RelationUtil() { + // Do not instantiate! + } + + /** + * Get the vector field type information from a relation. + * + * @param relation relation + * @param <V> Vector type + * @return Vector field type information + */ + public static <V extends FeatureVector<?>> VectorFieldTypeInformation<V> assumeVectorField(Relation<V> relation) { + try { + return ((VectorFieldTypeInformation<V>) relation.getDataTypeInformation()); + } catch (Exception e) { + throw new UnsupportedOperationException("Expected a vector field, got type information: " + relation.getDataTypeInformation().toString(), e); + } + } + + /** + * Get the number vector factory of a database relation. + * + * @param relation relation + * @param <V> Vector type + * @param <N> Number type + * @return Vector field type information + */ + public static <V extends NumberVector<? extends N>, N extends Number> NumberVector.Factory<V, N> getNumberVectorFactory(Relation<V> relation) { + final VectorFieldTypeInformation<V> type = assumeVectorField(relation); + @SuppressWarnings("unchecked") + final NumberVector.Factory<V, N> factory = (NumberVector.Factory<V, N>) type.getFactory(); + return factory; + } + + /** + * Get the dimensionality of a database relation. + * + * @param relation relation + * @return Database dimensionality + */ + public static int dimensionality(Relation<? extends FeatureVector<?>> relation) { + try { + return ((VectorFieldTypeInformation<? extends FeatureVector<?>>) relation.getDataTypeInformation()).getDimensionality(); + } catch (Exception e) { + return -1; + } + } + + /** + * Get the column name or produce a generic label "Column XY". + * + * @param rel Relation + * @param col Column + * @param <V> Vector type + * @return Label + */ + public static <V extends FeatureVector<?>> String getColumnLabel(Relation<? extends V> rel, int col) { + String lbl = assumeVectorField(rel).getLabel(col); + if (lbl != null) { + return lbl; + } else { + return "Column " + col; + } + } +} |