diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/database/ids')
51 files changed, 2783 insertions, 1155 deletions
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/ids/DBIDArrayIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDArrayIter.java new file mode 100644 index 00000000..fefe5ad1 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDArrayIter.java @@ -0,0 +1,34 @@ +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.utilities.iterator.ArrayIter; + +/** + * Array iterators that can also go backwards and seek. + * + * @author Erich Schubert + */ +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/ids/DistanceDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/DistanceDBIDPair.java new file mode 100644 index 00000000..01a1f407 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DistanceDBIDPair.java @@ -0,0 +1,52 @@ +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.Distance; + +/** + * Pair containing a distance an an object ID + * + * Note: there is no getter for the object, as this is a {@link DBIDRef}. + * + * @author Erich Schubert + * + * @param <D> Distance + */ +public interface DistanceDBIDPair<D extends Distance<D>> extends DBIDRef { + /** + * Get the distance. + * + * @return Distance + */ + public D getDistance(); + + /** + * Compare to another result, by distance, smaller first. + * + * @param other Other result + * @return Comparison result + */ + public int compareByDistance(DistanceDBIDPair<D> other); +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DoubleDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/DoubleDBIDPair.java new file mode 100644 index 00000000..06210076 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DoubleDBIDPair.java @@ -0,0 +1,64 @@ +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.utilities.pairs.PairInterface; + +/** + * Pair of a double value and a DBID + * + * @author Erich Schubert + */ +public interface DoubleDBIDPair extends PairInterface<Double, DBID>, DBIDRef, Comparable<DoubleDBIDPair> { + /** + * Get the double value of the pair. + * + * @return Double + */ + public double doubleValue(); + + /** + * Get the first object - note: this may cause autoboxing, use pair.first for + * native pairs! + * + * @deprecated Avoid autoboxing. Use {@link #doubleValue}! + * + * @return First object + */ + @Override + @Deprecated + public Double getFirst(); + + /** + * Get the second object - note: this may cause autoboxing, use pair.second + * for native pairs! + * + * @deprecated Avoid autoboxing! Use {@link DBIDRef} interface! + * + * @return Second object + */ + @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/TroveIteratorAdapter.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRef.java index 2f596f47..45854440 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveIteratorAdapter.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRef.java @@ -23,44 +23,19 @@ 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; /** - * Adapter for using GNU Trove iterators. + * DBID reference that references an integer value. * * @author Erich Schubert */ -class TroveIteratorAdapter implements Iterator<DBID> { - /** - * The actual iterator. - */ - private TIntIterator iterator; - +interface IntegerDBIDRef extends DBIDRef { /** - * Constructor. + * Return the integer value of the object ID. * - * @param iterator Trove iterator + * @return integer id */ - 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(); - } + 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; |