diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/database/ids')
38 files changed, 1312 insertions, 509 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 015d881a..13d6ea58 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/ArrayDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/ArrayDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,20 +23,43 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.List; - /** * Interface for array based DBIDs. * * @author Erich Schubert */ -public interface ArrayDBIDs extends DBIDs, List<DBID> { +public interface ArrayDBIDs extends DBIDs { /** * Get the i'th entry (starting at 0) * * @param i Index * @return DBID of i'th entry. */ - // In List<DBID> which confuses the java compiler - /* public DBID get(int i); */ + public DBID get(int i); + + /** + * Iterable + * + * @return Iterator + */ + public DBIDIter iter(); + + /** + * Size of the DBID "collection". + * + * @return size + */ + public int size(); + + /** + * Search for the position of the given key, assuming that the data set is + * sorted. + * + * For keys not found, <code>-(1+insertion position)</code> is returned, as + * for Java {@link java.util.Collections#binarySearch} + * + * @param key Key to search for + * @return Offset of key + */ + public int binarySearch(DBID key); } diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/ArrayModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/ArrayModifiableDBIDs.java index 1320ba4e..e9a6c8e0 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/ArrayModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/ArrayModifiableDBIDs.java @@ -1,10 +1,12 @@ package de.lmu.ifi.dbs.elki.database.ids; +import java.util.Comparator; + /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,13 +25,38 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.List; - /** * Array-oriented implementation of a modifiable DBID collection. * * @author Erich Schubert */ -public interface ArrayModifiableDBIDs extends ModifiableDBIDs, ArrayDBIDs, List<DBID> { - // Empty interface +public interface ArrayModifiableDBIDs extends ModifiableDBIDs, ArrayDBIDs { + /** + * Sort the DBID set. + */ + void sort(); + + /** + * Sort the DBID set. + * + * @param comparator Comparator to use + */ + void sort(Comparator<? super DBID> comparator); + + /** + * Remove the i'th entry (starting at 0) + * + * @param i Index + * @return value removed + */ + public DBID remove(int i); + + /** + * Replace the i'th entry (starting at 0) + * + * @param i Index + * @param newval New value + * @return previous value + */ + public DBID set(int i, DBID newval); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/ArrayStaticDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/ArrayStaticDBIDs.java index 2cf0f030..a14eac0c 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/ArrayStaticDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/ArrayStaticDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DBID.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBID.java index 41e67c4e..1391b75b 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBID.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBID.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,8 +23,6 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ - - /** * Database ID object. * @@ -39,7 +37,7 @@ package de.lmu.ifi.dbs.elki.database.ids; * * @apiviz.landmark */ -public interface DBID extends Comparable<DBID>, ArrayStaticDBIDs { +public interface DBID extends Comparable<DBID>, ArrayDBIDs { /** * Return the integer value of the object ID, if possible. * diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDFactory.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDFactory.java index cc5be115..f35f390b 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDFactory.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -111,13 +111,6 @@ public interface DBIDFactory { public HashSetModifiableDBIDs newHashSet(); /** - * Make a new (modifiable) tree set of DBIDs. - * - * @return New tree set - */ - public TreeSetModifiableDBIDs newTreeSet(); - - /** * Make a new (modifiable) array of DBIDs. * * @param size Size hint @@ -134,14 +127,6 @@ public interface DBIDFactory { public HashSetModifiableDBIDs newHashSet(int size); /** - * Make a new (modifiable) tree set of DBIDs. - * - * @param size Size hint - * @return New tree set - */ - public TreeSetModifiableDBIDs newTreeSet(int size); - - /** * Make a new (modifiable) array of DBIDs. * * @param existing existing DBIDs to use @@ -158,14 +143,6 @@ public interface DBIDFactory { public HashSetModifiableDBIDs newHashSet(DBIDs existing); /** - * Make a new (modifiable) tree set of DBIDs. - * - * @param existing existing DBIDs to use - * @return New tree set - */ - public TreeSetModifiableDBIDs newTreeSet(DBIDs existing); - - /** * Get a serializer for DBIDs * * @return DBID serializer diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDIter.java new file mode 100644 index 00000000..a41284f4 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDIter.java @@ -0,0 +1,79 @@ +package de.lmu.ifi.dbs.elki.database.ids; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +/** + * Iterator for DBIDs. + * + * Important note: this iterator has a <em>significantly</em> different syntax + * and semantics than the Java iterators. It is much more aligned with C than + * with Java, but at the same time, the syntax is much more compatible with for + * loops. + * + * Usage example: <blockquote><code>{@code + * for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + * iter.getDBID(); + * } + * }</code></blockquote> + * + * We list some fundamental differences. + * <ul> + * <li>{@link DBIDIter#valid() iter.valid()} refers to the current element, + * {@code Iterator.next()} to the next.</li> + * <li>{@link DBIDIter#advance() iter.advance()} does not return an element. Use + * {@code get...} to access it.</li> + * <li>{@code DBIDIter.get...} do not advance the iterator.</li> + * </ul> + * + * @author Erich Schubert + */ +public interface DBIDIter { + /** + * Returns true if the iterator currently points to a valid object. + * + * @return a <code>boolean</code> value + */ + public boolean valid(); + + /** + * Moves the iterator forward to the next entry. + * + * @throws java.util.NoSuchElementException if the iterator is already + * exhausted + */ + public void advance(); + + /** + * Return the integer value of the object ID, if possible. + * + * @return integer id + */ + public int getIntegerID(); + + /** + * Get the current DBID. + * + * @return current DBID + */ + public DBID getDBID(); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDPair.java index fdaff560..8f03e279 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDPair.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDPair.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDRange.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDRange.java index 4143c570..48a1f0ba 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDRange.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDRange.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDUtil.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDUtil.java index 3a62c222..cd2bd4e0 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDUtil.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDUtil.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -133,15 +133,6 @@ public final class DBIDUtil { } /** - * Make a new (modifiable) tree set of DBIDs. - * - * @return New tree set - */ - public static TreeSetModifiableDBIDs newTreeSet() { - return DBIDFactory.FACTORY.newTreeSet(); - } - - /** * Make a new (modifiable) array of DBIDs. * * @param size Size hint @@ -162,16 +153,6 @@ public final class DBIDUtil { } /** - * Make a new (modifiable) tree set of DBIDs. - * - * @param size Size hint - * @return New tree set - */ - public static TreeSetModifiableDBIDs newTreeSet(int size) { - return DBIDFactory.FACTORY.newTreeSet(size); - } - - /** * Make a new (modifiable) array of DBIDs. * * @param existing Existing DBIDs @@ -192,16 +173,6 @@ public final class DBIDUtil { } /** - * Make a new (modifiable) tree set of DBIDs. - * - * @param existing Existing DBIDs - * @return New tree set - */ - public static TreeSetModifiableDBIDs newTreeSet(DBIDs existing) { - return DBIDFactory.FACTORY.newTreeSet(existing); - } - - /** * Compute the set intersection of two sets. * * @param first First set @@ -285,11 +256,8 @@ public final class DBIDUtil { * @return Array DBIDs. */ public static SetDBIDs ensureSet(DBIDs ids) { - if(ids instanceof HashSetDBIDs) { - return (HashSetDBIDs) ids; - } - else if(ids instanceof TreeSetDBIDs) { - return (TreeSetDBIDs) ids; + if(ids instanceof SetDBIDs) { + return (SetDBIDs) ids; } else { return newHashSet(ids); @@ -313,9 +281,6 @@ public final class DBIDUtil { if(ids instanceof HashSetDBIDs) { return newHashSet(ids); } - if(ids instanceof TreeSetDBIDs) { - return newTreeSet(ids); - } return newArray(ids); } } @@ -340,11 +305,29 @@ public final class DBIDUtil { * @param seed Random generator seed * @return new DBIDs */ - public static ModifiableDBIDs randomSample(DBIDs source, int k, long seed) { + public static ModifiableDBIDs randomSample(DBIDs source, int k, int seed) { + return randomSample(source, k, (long) seed); + } + + /** + * Produce a random sample of the given DBIDs + * + * @param source Original DBIDs + * @param k k Parameter + * @param seed Random generator seed + * @return new DBIDs + */ + public static ModifiableDBIDs randomSample(DBIDs source, int k, Long seed) { if(k <= 0 || k > source.size()) { throw new IllegalArgumentException("Illegal value for size of random sample: " + k); } - Random random = new Random(seed); + final Random random; + if(seed != null) { + random = new Random(seed); + } + else { + random = new Random(); + } // TODO: better balancing for different sizes // Two methods: constructive vs. destructive if(k < source.size() / 2) { diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDs.java index c1a52d6a..ef83ba69 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/DBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/DBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,7 +23,6 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collection; import java.util.Iterator; /** @@ -36,13 +35,6 @@ import java.util.Iterator; */ public interface DBIDs extends Iterable<DBID> { /** - * Retrieve collection access to the IDs - * - * @return a collection of IDs - */ - public Collection<DBID> asCollection(); - - /** * Retrieve Iterator access to the IDs. * * @return an iterator for the IDs @@ -51,20 +43,26 @@ public interface DBIDs extends Iterable<DBID> { public Iterator<DBID> iterator(); /** + * Get a DBIDIterator (a more efficient API). + * + * @return iterator + */ + public DBIDIter iter(); + + /** * Retrieve the collection / data size. * * @return collection size */ public int size(); - + /** * Test whether an ID is contained. - * Signature compatible with {@link Collection}. * * @param o object to test * @return true when contained */ - public boolean contains(Object o); + public boolean contains(DBID o); /** * Test for an empty DBID collection. diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/EmptyDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/EmptyDBIDs.java index bee2faab..5a7d6991 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/EmptyDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/EmptyDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,10 +23,8 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.AbstractList; -import java.util.ArrayList; -import java.util.Collection; import java.util.Iterator; +import java.util.NoSuchElementException; import de.lmu.ifi.dbs.elki.utilities.iterator.EmptyIterator; @@ -35,14 +33,21 @@ import de.lmu.ifi.dbs.elki.utilities.iterator.EmptyIterator; * * @author Erich Schubert */ -class EmptyDBIDs extends AbstractList<DBID> implements ArrayStaticDBIDs { - @Override - public Collection<DBID> asCollection() { - return new ArrayList<DBID>(0); +public class EmptyDBIDs implements ArrayStaticDBIDs, SetDBIDs { + /** + * Empty DBID iterator + */ + public static final EmptyDBIDIterator EMPTY_ITERATOR = new EmptyDBIDIterator(); + + /** + * Constructor. + */ + protected EmptyDBIDs() { + super(); } @Override - public boolean contains(Object o) { + public boolean contains(DBID o) { return false; } @@ -65,4 +70,41 @@ class EmptyDBIDs extends AbstractList<DBID> implements ArrayStaticDBIDs { public DBID get(int i) { throw new ArrayIndexOutOfBoundsException(); } + + @Override + public DBIDIter iter() { + return EMPTY_ITERATOR; + } + + @Override + public int binarySearch(DBID key) { + return -1; // Not found + } + + /** + * Iterator for empty DBIDs + * + * @author Erich Schubert + */ + protected static class EmptyDBIDIterator implements DBIDIter { + @Override + public boolean valid() { + return false; + } + + @Override + public void advance() { + assert (false) : "Misplaced call to advance()"; + } + + @Override + public int getIntegerID() { + throw new NoSuchElementException(); + } + + @Override + public DBID getDBID() { + throw new NoSuchElementException(); + } + } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/HashSetDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/HashSetDBIDs.java index f449180f..5ff0bc97 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/HashSetDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/HashSetDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/HashSetModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/HashSetModifiableDBIDs.java index 03805590..f7c8b551 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/HashSetModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/HashSetModifiableDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,14 +23,12 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Set; - /** * Set-oriented implementation of a modifiable DBID collection. * * @author Erich Schubert */ -public interface HashSetModifiableDBIDs extends Set<DBID>, HashSetDBIDs, ModifiableDBIDs { +public interface HashSetModifiableDBIDs extends HashSetDBIDs, ModifiableDBIDs { /** * Retain all elements that also are in the second set. * diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/ModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/ModifiableDBIDs.java index 57d8c578..97646902 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/ModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/ModifiableDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,14 +23,16 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collection; - /** * Interface for a generic modifiable DBID collection. * + * Note: we had this use the Java Collections API for a long time, however this + * prevented certain optimizations. So it now only mimics the Collections API + * <em>deliberately</em>. + * * @author Erich Schubert */ -public interface ModifiableDBIDs extends DBIDs, Collection<DBID> { +public interface ModifiableDBIDs extends DBIDs { /** * Add DBIDs to collection. * @@ -38,7 +40,7 @@ public interface ModifiableDBIDs extends DBIDs, Collection<DBID> { * @return {@code true} when modified */ boolean addDBIDs(DBIDs ids); - + /** * Remove DBIDs from collection. * @@ -46,4 +48,23 @@ public interface ModifiableDBIDs extends DBIDs, Collection<DBID> { * @return {@code true} when modified */ boolean removeDBIDs(DBIDs ids); -} + + /** + * Add a single DBID to the collection. + * + * @param id ID to add + */ + boolean add(DBID id); + + /** + * Remove a single DBID from the collection. + * + * @param id ID to remove + */ + boolean remove(DBID id); + + /** + * Clear this collection. + */ + void clear(); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/SetDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/SetDBIDs.java index 6509a57f..7fd28326 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/SetDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/SetDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,7 +23,6 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Set; /** * Interface for DBIDs that support fast "set" operations, in particular @@ -31,6 +30,6 @@ import java.util.Set; * * @author Erich Schubert */ -public interface SetDBIDs extends DBIDs, Set<DBID> { +public interface SetDBIDs extends DBIDs { // empty marker interface }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/StaticDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/StaticDBIDs.java index 08676215..ce616da3 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/StaticDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/StaticDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/DBIDIterAdapter.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/DBIDIterAdapter.java new file mode 100644 index 00000000..c517ea9f --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/generic/DBIDIterAdapter.java @@ -0,0 +1,82 @@ +package de.lmu.ifi.dbs.elki.database.ids.generic; + +import java.util.Iterator; + +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +/** + * Iterator for classic collections. + * + * @author Erich Schubert + */ +public class DBIDIterAdapter implements DBIDIter { + /** + * Current DBID + */ + DBID cur = null; + + /** + * The real iterator + */ + Iterator<DBID> iter; + + /** + * Constructor. + * + * @param iter Iterator + */ + public DBIDIterAdapter(Iterator<DBID> iter) { + super(); + this.iter = iter; + advance(); + } + + @Override + public boolean valid() { + return cur != null; + } + + @Override + public void advance() { + if(iter.hasNext()) { + cur = iter.next(); + } + else { + cur = null; + } + } + + @Override + public int getIntegerID() { + return cur.getIntegerID(); + } + + @Override + public DBID getDBID() { + return cur; + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericArrayModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericArrayModifiableDBIDs.java index 0316f82d..f271180d 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericArrayModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericArrayModifiableDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -24,26 +24,27 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; */ import java.util.ArrayList; -import java.util.Collection; +import java.util.Collections; +import java.util.Comparator; import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; - /** * Array-oriented implementation of a modifiable DBID collection. * - * This should only be instantiated by a {@link de.lmu.ifi.dbs.elki.database.ids.DBIDFactory}! + * This should only be instantiated by a + * {@link de.lmu.ifi.dbs.elki.database.ids.DBIDFactory}! * * Use {@link de.lmu.ifi.dbs.elki.database.ids.DBIDUtil#newArray}! * * @author Erich Schubert * - * @apiviz.uses de.lmu.ifi.dbs.elki.database.ids.DBID + * @apiviz.uses DBID */ -// TODO: implement this optimized for integers? -public class GenericArrayModifiableDBIDs extends ArrayList<DBID> implements ArrayModifiableDBIDs { +public class GenericArrayModifiableDBIDs extends ArrayList<DBID> implements ArrayModifiableDBIDs { /** * Serial version */ @@ -71,21 +72,56 @@ public class GenericArrayModifiableDBIDs extends ArrayList<DBID> implements Arra * @param c Existing DBIDs. */ public GenericArrayModifiableDBIDs(DBIDs c) { - super(c.asCollection()); + super(c.size()); + addDBIDs(c); } @Override - public Collection<DBID> asCollection() { - return this; + public boolean addDBIDs(DBIDs ids) { + super.ensureCapacity(size() + ids.size()); + boolean changed = false; + for(DBID id : ids) { + changed |= add(id); + } + return changed; } @Override - public boolean addDBIDs(DBIDs ids) { - return super.addAll(ids.asCollection()); + public boolean removeDBIDs(DBIDs ids) { + boolean changed = false; + for(DBID id : ids) { + changed |= super.remove(id); + } + return changed; } @Override - public boolean removeDBIDs(DBIDs ids) { - return super.removeAll(ids.asCollection()); + public boolean remove(DBID id) { + return super.remove(id); + } + + @Override + public void sort() { + Collections.sort(this); + } + + @Override + public void sort(Comparator<? super DBID> comparator) { + Collections.sort(this, comparator); + } + + @Override + public DBIDIter iter() { + return new DBIDIterAdapter(iterator()); + } + + @Override + public int binarySearch(DBID key) { + return Collections.binarySearch(this, key); + } + + @Override + public boolean contains(DBID o) { + return super.contains(o); } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericHashSetModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericHashSetModifiableDBIDs.java index 6d251cd8..31a8602c 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericHashSetModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericHashSetModifiableDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,25 +23,26 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collection; import java.util.HashSet; +import java.util.Iterator; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; /** * Set-oriented implementation of a modifiable DBID collection. * - * This should only be instantiated by a {@link de.lmu.ifi.dbs.elki.database.ids.DBIDFactory}! + * This should only be instantiated by a + * {@link de.lmu.ifi.dbs.elki.database.ids.DBIDFactory}! * * Use {@link de.lmu.ifi.dbs.elki.database.ids.DBIDUtil#newHashSet}! * * @author Erich Schubert * - * @apiviz.uses de.lmu.ifi.dbs.elki.database.ids.DBID + * @apiviz.uses DBID */ -// TODO: implement this optimized for integers? public class GenericHashSetModifiableDBIDs extends HashSet<DBID> implements HashSetModifiableDBIDs { /** * Serial version @@ -70,26 +71,55 @@ public class GenericHashSetModifiableDBIDs extends HashSet<DBID> implements Hash * @param c Existing DBIDs. */ public GenericHashSetModifiableDBIDs(DBIDs c) { - super(c.asCollection()); + super(c.size()); + for(DBID id : c) { + add(id); + } } @Override - public Collection<DBID> asCollection() { - return this; + public boolean addDBIDs(DBIDs ids) { + boolean changed = false; + for(DBID id : ids) { + changed |= add(id); + } + return changed; } @Override - public boolean addDBIDs(DBIDs ids) { - return super.addAll(ids.asCollection()); + public boolean removeDBIDs(DBIDs ids) { + boolean changed = false; + for(DBID id : ids) { + changed |= super.remove(id); + } + return changed; } @Override - public boolean removeDBIDs(DBIDs ids) { - return super.removeAll(ids.asCollection()); + public boolean remove(DBID id) { + return super.remove(id); } @Override public boolean retainAll(DBIDs ids) { - return super.retainAll(ids.asCollection()); + boolean modified = false; + Iterator<DBID> it = iterator(); + while(it.hasNext()) { + if(!ids.contains(it.next())) { + it.remove(); + modified = true; + } + } + return modified; + } + + @Override + public DBIDIter iter() { + return new DBIDIterAdapter(iterator()); + } + + @Override + public boolean contains(DBID o) { + return super.contains(o); } -} +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericTreeSetModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericTreeSetModifiableDBIDs.java deleted file mode 100644 index afd56730..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericTreeSetModifiableDBIDs.java +++ /dev/null @@ -1,90 +0,0 @@ -package de.lmu.ifi.dbs.elki.database.ids.generic; - -/* - This file is part of ELKI: - Environment for Developing KDD-Applications Supported by Index-Structures - - Copyright (C) 2011 - Ludwig-Maximilians-Universität München - Lehr- und Forschungseinheit für Datenbanksysteme - ELKI Development Team - - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU Affero General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU Affero General Public License for more details. - - You should have received a copy of the GNU Affero General Public License - along with this program. If not, see <http://www.gnu.org/licenses/>. - */ - -import java.util.Collection; -import java.util.TreeSet; - -import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.DBIDs; -import de.lmu.ifi.dbs.elki.database.ids.TreeSetModifiableDBIDs; - -/** - * Set-oriented implementation of a modifiable DBID collection. - * - * This should only be instantiated by a {@link de.lmu.ifi.dbs.elki.database.ids.DBIDFactory}! - * - * Use {@link de.lmu.ifi.dbs.elki.database.ids.DBIDUtil#newTreeSet}! - * - * @author Erich Schubert - * - * @apiviz.uses de.lmu.ifi.dbs.elki.database.ids.DBID - */ -// TODO: implement this optimized for integers? -public class GenericTreeSetModifiableDBIDs extends TreeSet<DBID> implements TreeSetModifiableDBIDs { - /** - * Serial version - */ - private static final long serialVersionUID = 1L; - - /** - * Constructor with size hint. - * - * @param initialCapacity Size hint - */ - public GenericTreeSetModifiableDBIDs(int initialCapacity) { - super(); - } - - /** - * Constructor without extra hints - */ - public GenericTreeSetModifiableDBIDs() { - super(); - } - - /** - * Constructor from existing DBIDs. - * - * @param c Existing DBIDs. - */ - public GenericTreeSetModifiableDBIDs(DBIDs c) { - super(c.asCollection()); - } - - @Override - public Collection<DBID> asCollection() { - return this; - } - - @Override - public boolean addDBIDs(DBIDs ids) { - return super.addAll(ids.asCollection()); - } - - @Override - public boolean removeDBIDs(DBIDs ids) { - return super.removeAll(ids.asCollection()); - } -} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/MaskedDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/MaskedDBIDs.java index 77d5c063..67c84290 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/MaskedDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/generic/MaskedDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,13 +23,12 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.AbstractCollection; import java.util.BitSet; -import java.util.Collection; import java.util.Iterator; import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; /** @@ -39,7 +38,7 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDs; * * @apiviz.uses de.lmu.ifi.dbs.elki.database.ids.DBIDs */ -public class MaskedDBIDs extends AbstractCollection<DBID> implements DBIDs, Collection<DBID> { +public class MaskedDBIDs implements DBIDs { /** * Data storage */ @@ -80,8 +79,13 @@ public class MaskedDBIDs extends AbstractCollection<DBID> implements DBIDs, Coll } @Override - public Collection<DBID> asCollection() { - return this; + public DBIDIter iter() { + if(inverse) { + return new InvDBIDItr(); + } + else { + return new DBIDItr(); + } } @Override @@ -94,6 +98,22 @@ public class MaskedDBIDs extends AbstractCollection<DBID> implements DBIDs, Coll } } + @Override + public boolean contains(DBID o) { + // TODO: optimize. + for(DBID id : this) { + if(id.equals(o)) { + return true; + } + } + return false; + } + + @Override + public boolean isEmpty() { + return size() == 0; + } + /** * Iterator over set bits * @@ -133,6 +153,47 @@ public class MaskedDBIDs extends AbstractCollection<DBID> implements DBIDs, Coll } /** + * Iterator over set bits + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected class DBIDItr implements DBIDIter { + /** + * Next position. + */ + private int pos; + + /** + * Constructor + */ + protected DBIDItr() { + this.pos = bits.nextSetBit(0); + } + + @Override + public boolean valid() { + return pos >= 0; + } + + @Override + public void advance() { + pos = bits.nextSetBit(pos + 1); + } + + @Override + public int getIntegerID() { + return data.get(pos).getIntegerID(); + } + + @Override + public DBID getDBID() { + return data.get(pos); + } + } + + /** * Iterator over unset elements. * * @author Erich Schubert @@ -170,18 +231,44 @@ public class MaskedDBIDs extends AbstractCollection<DBID> implements DBIDs, Coll } } - @Override - public boolean add(DBID e) { - throw new UnsupportedOperationException(); - } + /** + * Iterator over set bits + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected class InvDBIDItr implements DBIDIter { + /** + * Next position. + */ + private int pos; - @Override - public boolean remove(Object o) { - throw new UnsupportedOperationException(); - } + /** + * Constructor + */ + protected InvDBIDItr() { + this.pos = bits.nextClearBit(0); + } - @Override - public void clear() { - throw new UnsupportedOperationException(); + @Override + public boolean valid() { + return pos >= 0; + } + + @Override + public void advance() { + pos = bits.nextClearBit(pos + 1); + } + + @Override + public int getIntegerID() { + return data.get(pos).getIntegerID(); + } + + @Override + public DBID getDBID() { + return data.get(pos); + } } } diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/MergedDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/MergedDBIDs.java index ce28ac38..97743867 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/MergedDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/generic/MergedDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,12 +23,12 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collection; import java.util.Iterator; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; - +import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; /** * Merge the IDs of multiple layers into one. @@ -38,12 +38,12 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDs; * @apiviz.uses de.lmu.ifi.dbs.elki.database.ids.DBIDs */ // TODO: include ID mapping? -public class MergedDBIDs implements DBIDs, Collection<DBID> { +public class MergedDBIDs implements DBIDs { /** * Childs to merge */ DBIDs childs[]; - + /** * Constructor. * @@ -55,14 +55,13 @@ public class MergedDBIDs implements DBIDs, Collection<DBID> { } @Override - public Collection<DBID> asCollection() { - return this; + public Iterator<DBID> iterator() { + throw new AbortException("Merged iterators not completely implemented yet!"); } @Override - public Iterator<DBID> iterator() { - // TODO Auto-generated method stub - return null; + public DBIDIter iter() { + throw new AbortException("Merged iterators not completely implemented yet!"); } @Override @@ -80,32 +79,7 @@ public class MergedDBIDs implements DBIDs, Collection<DBID> { } @Override - public Object[] toArray() { - return toArray(new Object[size()]); - } - - @SuppressWarnings("unchecked") - @Override - public <T> T[] toArray(T[] a) { - final int si = size(); - T[] r = a; - if(a.length < si) { - r = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), si); - } - int i = 0; - for (Iterator<DBID> iter = iterator(); iter.hasNext(); i++) { - DBID id = iter.next(); - r[i] = (T) id; - } - // zero-terminate array - if(r.length > si) { - r[si] = null; - } - return r; - } - - @Override - public boolean contains(Object o) { + public boolean contains(DBID o) { for(DBIDs child : childs) { if(child.contains(o)) { return true; @@ -113,45 +87,4 @@ public class MergedDBIDs implements DBIDs, Collection<DBID> { } return false; } - - @Override - public boolean containsAll(Collection<?> c) { - Iterator<?> e = c.iterator(); - while(e.hasNext()) { - if(!contains(e.next())) { - return false; - } - } - return true; - } - - @Override - public void clear() { - throw new UnsupportedOperationException(MergedDBIDs.class.getName() + " are unmodifiable!"); - } - - @Override - public boolean add(DBID e) { - throw new UnsupportedOperationException(MergedDBIDs.class.getName() + " are unmodifiable!"); - } - - @Override - public boolean addAll(Collection<? extends DBID> c) { - throw new UnsupportedOperationException(MergedDBIDs.class.getName() + " are unmodifiable!"); - } - - @Override - public boolean remove(Object o) { - throw new UnsupportedOperationException(MergedDBIDs.class.getName() + " are unmodifiable!"); - } - - @Override - public boolean removeAll(Collection<?> c) { - throw new UnsupportedOperationException(MergedDBIDs.class.getName() + " are unmodifiable!"); - } - - @Override - public boolean retainAll(Collection<?> c) { - throw new UnsupportedOperationException(MergedDBIDs.class.getName() + " are unmodifiable!"); - } -} +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/UnmodifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/UnmodifiableDBIDs.java index 908dabd3..bd68e2fb 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/UnmodifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/generic/UnmodifiableDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,11 +23,10 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.Collection; -import java.util.Collections; import java.util.Iterator; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.StaticDBIDs; import de.lmu.ifi.dbs.elki.utilities.iterator.UnmodifiableIterator; @@ -56,12 +55,7 @@ public class UnmodifiableDBIDs implements StaticDBIDs { } @Override - public Collection<DBID> asCollection() { - return Collections.unmodifiableCollection(inner.asCollection()); - } - - @Override - public boolean contains(Object o) { + public boolean contains(DBID o) { return inner.contains(o); } @@ -74,6 +68,11 @@ public class UnmodifiableDBIDs implements StaticDBIDs { public Iterator<DBID> iterator() { return new UnmodifiableIterator<DBID>(inner.iterator()); } + + @Override + public DBIDIter iter() { + return inner.iter(); + } @Override public int size() { diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/package-info.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/package-info.java index cdf4c487..890b9c0a 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/generic/package-info.java @@ -7,7 +7,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2011 +Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayStaticDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayStaticDBIDs.java index b617b4c4..ef4aee94 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayStaticDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayStaticDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -24,22 +24,22 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; */ import java.util.AbstractList; -import java.util.Collection; +import java.util.Arrays; import java.util.Iterator; -import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.ArrayStaticDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; - +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; /** * Static (no modifications allowed) set of Database Object IDs. * * @author Erich Schubert * - * @apiviz.composedOf IntegerDBID + * @apiviz.has IntegerDBID */ -public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements ArrayDBIDs { +public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements ArrayStaticDBIDs { /** * The actual storage. */ @@ -59,7 +59,12 @@ public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements Array public Iterator<DBID> iterator() { return new Itr(); } - + + @Override + public DBIDIter iter() { + return new DBIDItr(); + } + /** * Iterator class. * @@ -77,7 +82,7 @@ public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements Array @Override public DBID next() { - DBID ret = DBIDFactory.FACTORY.importInteger(ids[off]); + DBID ret = new IntegerDBID(ids[off]); off++; return ret; } @@ -88,22 +93,49 @@ public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements Array } } + /** + * DBID iterator in ELKI/C style. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected class DBIDItr implements DBIDIter { + int pos = 0; + + @Override + public boolean valid() { + return pos < ids.length; + } + + @Override + public void advance() { + pos++; + } + + @Override + public int getIntegerID() { + return ids[pos]; + } + + @Override + public DBID getDBID() { + return new IntegerDBID(ids[pos]); + } + + } + @Override public int size() { return ids.length; } - - /* - * "Contains" operations - */ + @Override - public boolean contains(Object o) { - if(o instanceof DBID) { - int oid = ((DBID) o).getIntegerID(); - for(int i = 0; i < ids.length; i++) { - if(ids[i] == oid) { - return true; - } + public boolean contains(DBID o) { + final int oid = o.getIntegerID(); + for(int i = 0; i < ids.length; i++) { + if(ids[i] == oid) { + return true; } } return false; @@ -132,7 +164,7 @@ public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements Array } @Override - public Collection<DBID> asCollection() { - return this; + public int binarySearch(DBID key) { + return Arrays.binarySearch(ids, key.getIntegerID()); } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java index 2842ca75..f9e83294 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -24,11 +24,10 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; */ import java.nio.ByteBuffer; -import java.util.AbstractList; -import java.util.Collection; import java.util.Iterator; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.persistent.ByteArrayUtil; import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; @@ -50,7 +49,7 @@ import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; * @apiviz.composedOf DynamicSerializer * @apiviz.composedOf StaticSerializer */ -class IntegerDBID extends AbstractList<DBID> implements DBID { +class IntegerDBID implements DBID { /** * The actual object ID. */ @@ -113,13 +112,16 @@ class IntegerDBID extends AbstractList<DBID> implements DBID { } @Override - public Collection<DBID> asCollection() { - return this; + public DBIDIter iter() { + return new DBIDItr(); } @Override - public boolean contains(Object o) { - return this.equals(o); + public DBID get(int i) { + if(i != 0) { + throw new ArrayIndexOutOfBoundsException(); + } + return this; } @Override @@ -128,10 +130,20 @@ class IntegerDBID extends AbstractList<DBID> implements DBID { } @Override + public boolean contains(DBID o) { + return o.getIntegerID() == id; + } + + @Override public int size() { return 1; } + @Override + public int binarySearch(DBID key) { + return equals(key) ? 0 : -1; + } + /** * Pseudo iterator for DBIDs interface. * @@ -163,21 +175,45 @@ class IntegerDBID extends AbstractList<DBID> implements DBID { } } - @Override - public boolean isEmpty() { - return false; - } + /** + * Pseudo iterator for DBIDs interface. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected class DBIDItr implements DBIDIter { + /** + * Whether we've already returned our object. + */ + boolean first = true; - @Override - public DBID get(int i) { - if(i == 0) { - return this; + @Override + public void advance() { + first = false; } - else { - throw new ArrayIndexOutOfBoundsException(); + + @Override + public int getIntegerID() { + return id; + } + + @Override + public DBID getDBID() { + return IntegerDBID.this; + } + + @Override + public boolean valid() { + return first; } } + @Override + public boolean isEmpty() { + return false; + } + /** * Dynamic sized serializer, using varint. * diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDPair.java index 742bab57..e716f5b5 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDPair.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDPair.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -30,7 +30,7 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDPair; * * @author Erich Schubert * - * @apiviz.composedOf IntegerDBID + * @apiviz.has IntegerDBID */ public class IntegerDBIDPair implements DBIDPair { /** diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java index 1142f1a6..debe39a4 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -24,32 +24,31 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; */ import java.util.AbstractList; -import java.util.Collection; import java.util.Iterator; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; - /** * Representing a DBID range allocation * * @author Erich Schubert * - * @apiviz.composedOf IntegerDBID + * @apiviz.has IntegerDBID */ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { /** * Start value */ protected final int start; - + /** * Length value */ protected final int len; - + /** * Constructor. * @@ -72,6 +71,11 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { return new Itr(); } + @Override + public DBIDIter iter() { + return new DBIDItr(); + } + /** * Iterator class. * @@ -89,7 +93,7 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { @Override public DBID next() { - DBID ret = DBIDFactory.FACTORY.importInteger(pos + start); + DBID ret = new IntegerDBID(pos + start); pos++; return ret; } @@ -100,22 +104,48 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { } } - /* - * "Contains" operations + /** + * Iterator in ELKI/C++ style. + * + * @author Erich Schubert + * + * @apiviz.exclude */ + protected class DBIDItr implements DBIDIter { + int pos = 0; + + @Override + public boolean valid() { + return pos < len; + } + + @Override + public void advance() { + pos++; + } + + @Override + public int getIntegerID() { + return start + pos; + } + + @Override + public DBID getDBID() { + return new IntegerDBID(start + pos); + } + + } + @Override - public boolean contains(Object o) { - if(o instanceof DBID) { - int oid = ((DBID) o).getIntegerID(); - if(oid < start) { - return false; - } - if(oid >= start + len) { - return false; - } - return true; + public boolean contains(DBID o) { + int oid = o.getIntegerID(); + if(oid < start) { + return false; } - return false; + if(oid >= start + len) { + return false; + } + return true; } @SuppressWarnings("unchecked") @@ -137,11 +167,11 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { @Override public DBID get(int i) { - if (i > len || i < 0) { + if(i > len || i < 0) { throw new ArrayIndexOutOfBoundsException(); } return DBIDFactory.FACTORY.importInteger(start + i); - } + } /** * For storage array offsets. @@ -155,7 +185,15 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { } @Override - public Collection<DBID> asCollection() { - return this; + public int binarySearch(DBID key) { + int keyid = key.getIntegerID(); + if(keyid < start) { + return -1; + } + final int off = keyid - start; + if(off < len) { + return off; + } + return -(len + 1); } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/ReusingDBIDFactory.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/ReusingDBIDFactory.java index 8e4600db..01e42fe9 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/ReusingDBIDFactory.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/ReusingDBIDFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/SimpleDBIDFactory.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/SimpleDBIDFactory.java index 3348701e..59fa34b5 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/SimpleDBIDFactory.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/SimpleDBIDFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -27,21 +27,17 @@ import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; import de.lmu.ifi.dbs.elki.database.ids.DBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; -import de.lmu.ifi.dbs.elki.database.ids.TreeSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericArrayModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericHashSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericTreeSetModifiableDBIDs; import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; /** - * Simple DBID management, that never reuses IDs. - * Statically allocated DBID ranges are given positive values, - * Dynamically allocated DBIDs are given negative values. + * Simple DBID management, that never reuses IDs. Statically allocated DBID + * ranges are given positive values, Dynamically allocated DBIDs are given + * negative values. * * @author Erich Schubert * @@ -50,21 +46,20 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; * @apiviz.uses IntegerDBID oneway - - «create» * @apiviz.uses IntegerDBIDPair oneway - - «create» * @apiviz.uses IntegerDBIDRange oneway - - «create» - * @apiviz.uses GenericArrayModifiableDBIDs oneway - - «create» - * @apiviz.uses GenericHashSetModifiableDBIDs oneway - - «create» - * @apiviz.uses GenericTreeSetModifiableDBIDs oneway - - «create» + * @apiviz.uses TroveArrayModifiableDBIDs oneway - - «create» + * @apiviz.uses TroveHashSetModifiableDBIDs oneway - - «create» */ public class SimpleDBIDFactory implements DBIDFactory { /** * Keep track of the smallest dynamic DBID offset not used */ int dynamicids = 0; - + /** * The starting point for static DBID range allocations. */ int rangestart = 0; - + /** * Constructor */ @@ -74,7 +69,7 @@ public class SimpleDBIDFactory implements DBIDFactory { @Override public synchronized DBID generateSingleDBID() { - if (dynamicids == Integer.MIN_VALUE) { + if(dynamicids == Integer.MIN_VALUE) { throw new AbortException("DBID range allocation error - too many objects allocated!"); } dynamicids--; @@ -88,7 +83,7 @@ public class SimpleDBIDFactory implements DBIDFactory { @Override public synchronized DBIDRange generateStaticDBIDRange(int size) { - if (rangestart >= Integer.MAX_VALUE - size) { + if(rangestart >= Integer.MAX_VALUE - size) { throw new AbortException("DBID range allocation error - too many objects allocated!"); } DBIDRange alloc = new IntegerDBIDRange(rangestart, size); @@ -108,47 +103,32 @@ public class SimpleDBIDFactory implements DBIDFactory { @Override public ArrayModifiableDBIDs newArray() { - return new GenericArrayModifiableDBIDs(); + return new TroveArrayModifiableDBIDs(); } @Override public HashSetModifiableDBIDs newHashSet() { - return new GenericHashSetModifiableDBIDs(); - } - - @Override - public TreeSetModifiableDBIDs newTreeSet() { - return new GenericTreeSetModifiableDBIDs(); + return new TroveHashSetModifiableDBIDs(); } @Override public ArrayModifiableDBIDs newArray(int size) { - return new GenericArrayModifiableDBIDs(size); + return new TroveArrayModifiableDBIDs(size); } @Override public HashSetModifiableDBIDs newHashSet(int size) { - return new GenericHashSetModifiableDBIDs(size); - } - - @Override - public TreeSetModifiableDBIDs newTreeSet(int size) { - return new GenericTreeSetModifiableDBIDs(size); + return new TroveHashSetModifiableDBIDs(size); } @Override public ArrayModifiableDBIDs newArray(DBIDs existing) { - return new GenericArrayModifiableDBIDs(existing); + return new TroveArrayModifiableDBIDs(existing); } @Override public HashSetModifiableDBIDs newHashSet(DBIDs existing) { - return new GenericHashSetModifiableDBIDs(existing); - } - - @Override - public TreeSetModifiableDBIDs newTreeSet(DBIDs existing) { - return new GenericTreeSetModifiableDBIDs(existing); + return new TroveHashSetModifiableDBIDs(existing); } @Override diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TrivialDBIDFactory.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TrivialDBIDFactory.java index ee49e2f1..b38286fe 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TrivialDBIDFactory.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TrivialDBIDFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -29,13 +29,9 @@ import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; import de.lmu.ifi.dbs.elki.database.ids.DBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; -import de.lmu.ifi.dbs.elki.database.ids.TreeSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericArrayModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericHashSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericTreeSetModifiableDBIDs; import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; @@ -52,9 +48,8 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; * @apiviz.uses IntegerDBID oneway - - «create» * @apiviz.uses IntegerDBIDPair oneway - - «create» * @apiviz.uses IntegerDBIDRange oneway - - «create» - * @apiviz.uses GenericArrayModifiableDBIDs oneway - - «create» - * @apiviz.uses GenericHashSetModifiableDBIDs oneway - - «create» - * @apiviz.uses GenericTreeSetModifiableDBIDs oneway - - «create» + * @apiviz.uses TroveArrayModifiableDBIDs oneway - - «create» + * @apiviz.uses TroveHashSetModifiableDBIDs oneway - - «create» */ public class TrivialDBIDFactory implements DBIDFactory { /** @@ -106,47 +101,32 @@ public class TrivialDBIDFactory implements DBIDFactory { @Override public ArrayModifiableDBIDs newArray() { - return new GenericArrayModifiableDBIDs(); + return new TroveArrayModifiableDBIDs(); } @Override public HashSetModifiableDBIDs newHashSet() { - return new GenericHashSetModifiableDBIDs(); - } - - @Override - public TreeSetModifiableDBIDs newTreeSet() { - return new GenericTreeSetModifiableDBIDs(); + return new TroveHashSetModifiableDBIDs(); } @Override public ArrayModifiableDBIDs newArray(int size) { - return new GenericArrayModifiableDBIDs(size); + return new TroveArrayModifiableDBIDs(size); } @Override public HashSetModifiableDBIDs newHashSet(int size) { - return new GenericHashSetModifiableDBIDs(size); - } - - @Override - public TreeSetModifiableDBIDs newTreeSet(int size) { - return new GenericTreeSetModifiableDBIDs(size); + return new TroveHashSetModifiableDBIDs(size); } @Override public ArrayModifiableDBIDs newArray(DBIDs existing) { - return new GenericArrayModifiableDBIDs(existing); + return new TroveArrayModifiableDBIDs(existing); } @Override public HashSetModifiableDBIDs newHashSet(DBIDs existing) { - return new GenericHashSetModifiableDBIDs(existing); - } - - @Override - public TreeSetModifiableDBIDs newTreeSet(DBIDs existing) { - return new GenericTreeSetModifiableDBIDs(existing); + return new TroveHashSetModifiableDBIDs(existing); } @Override diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java new file mode 100644 index 00000000..a060c6b8 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java @@ -0,0 +1,133 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import gnu.trove.list.TIntList; + +import java.util.Iterator; + +import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; + +/** + * Abstract base class for GNU Trove array based lists. + * + * @author Erich Schubert + * + * @apiviz.has IntegerDBID + * @apiviz.has TroveIteratorAdapter + */ +public abstract class TroveArrayDBIDs implements ArrayDBIDs { + /** + * Get the array store + * + * @return the store + */ + abstract protected TIntList getStore(); + + @Override + public Iterator<DBID> iterator() { + return new TroveIteratorAdapter(getStore().iterator()); + } + + @Override + public DBIDIter iter() { + return new DBIDItr(getStore()); + } + + @Override + public DBID get(int index) { + return new IntegerDBID(getStore().get(index)); + } + + @Override + public int size() { + return getStore().size(); + } + + @Override + public boolean isEmpty() { + return getStore().isEmpty(); + } + + @Override + public boolean contains(DBID o) { + return getStore().contains(o.getIntegerID()); + } + + @Override + public int binarySearch(DBID key) { + return getStore().binarySearch(key.getIntegerID()); + } + + /** + * Iterate over a Trove IntList, ELKI/C-style + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected static class DBIDItr implements DBIDIter { + /** + * Current position + */ + int pos = 0; + + /** + * The actual store we use + */ + TIntList store; + + /** + * Constructor. + * + * @param store The actual trove store + */ + public DBIDItr(TIntList store) { + super(); + this.store = store; + } + + @Override + public boolean valid() { + return pos < store.size(); + } + + @Override + public void advance() { + pos++; + } + + @Override + public int getIntegerID() { + return store.get(pos); + } + + @Override + public DBID getDBID() { + return new IntegerDBID(store.get(pos)); + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java new file mode 100644 index 00000000..abcbba14 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java @@ -0,0 +1,144 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import gnu.trove.list.array.TIntArrayList; + +import java.util.Arrays; +import java.util.Comparator; + +import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDs; + +/** + * Class using a GNU Trove int array list as storage. + * + * @author Erich Schubert + */ +class TroveArrayModifiableDBIDs extends TroveArrayDBIDs implements ArrayModifiableDBIDs { + /** + * The actual trove array list + */ + private TIntArrayList store; + + /** + * Constructor. + * + * @param size Initial size + */ + protected TroveArrayModifiableDBIDs(int size) { + super(); + this.store = new TIntArrayList(size); + } + + /** + * Constructor. + */ + protected TroveArrayModifiableDBIDs() { + super(); + this.store = new TIntArrayList(); + } + + /** + * Constructor. + * + * @param existing Existing ids + */ + protected TroveArrayModifiableDBIDs(DBIDs existing) { + this(existing.size()); + this.addDBIDs(existing); + } + + @Override + protected TIntArrayList getStore() { + return store; + } + + @Override + public boolean addDBIDs(DBIDs ids) { + boolean success = false; + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + success |= store.add(iter.getIntegerID()); + } + return success; + } + + @Override + public boolean removeDBIDs(DBIDs ids) { + boolean success = false; + for(DBID id : ids) { + success |= store.remove(id.getIntegerID()); + } + return success; + } + + @Override + public boolean add(DBID e) { + return store.add(e.getIntegerID()); + } + + @Override + public boolean remove(DBID o) { + return store.remove(o.getIntegerID()); + } + + @Override + public DBID set(int index, DBID element) { + int prev = store.set(index, element.getIntegerID()); + return new IntegerDBID(prev); + } + + @Override + public DBID remove(int index) { + return new IntegerDBID(store.removeAt(index)); + } + + @Override + public void clear() { + store.clear(); + } + + @Override + public void sort() { + store.sort(); + } + + @Override + public void sort(Comparator<? super DBID> comparator) { + // FIXME: optimize, avoid the extra copy. + // Clone data + DBID[] data = new DBID[store.size()]; + for(int i = 0; i < store.size(); i++) { + data[i] = new IntegerDBID(store.get(i)); + } + // Sort + Arrays.sort(data, comparator); + // Copy back + for(int i = 0; i < store.size(); i++) { + store.set(i, data[i].getIntegerID()); + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/TreeSetDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayStaticDBIDs.java index 43fff9ef..53ab34d4 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/TreeSetDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayStaticDBIDs.java @@ -1,10 +1,9 @@ -package de.lmu.ifi.dbs.elki.database.ids; - +package de.lmu.ifi.dbs.elki.database.ids.integer; /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,12 +22,32 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ +import gnu.trove.list.TIntList; +import de.lmu.ifi.dbs.elki.database.ids.ArrayStaticDBIDs; /** - * Marker for sorted, tree-organized DBIDs + * Class accessing a trove int array. * * @author Erich Schubert */ -public interface TreeSetDBIDs extends SetDBIDs { - // Empty +class TroveArrayStaticDBIDs extends TroveArrayDBIDs implements ArrayStaticDBIDs { + /** + * Actual trove store + */ + private final TIntList store; + + /** + * Constructor. + * + * @param store Actual trove store. + */ + protected TroveArrayStaticDBIDs(TIntList store) { + super(); + this.store = store; + } + + @Override + protected TIntList getStore() { + return store; + } } diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java new file mode 100644 index 00000000..11fe669c --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java @@ -0,0 +1,193 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +import java.util.Iterator; + +import gnu.trove.impl.hash.THashPrimitiveIterator; +import gnu.trove.impl.hash.TIntHash; +import gnu.trove.set.hash.TIntHashSet; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDs; +import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +/** + * Implementation using GNU Trove Int Hash Sets. + * + * @author Erich Schubert + * + * @apiviz.has IntegerDBID + * @apiviz.has TroveIteratorAdapter + */ +class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs { + /** + * The actual store. + */ + TIntHashSet store; + + /** + * Constructor. + * + * @param size Initial size + */ + protected TroveHashSetModifiableDBIDs(int size) { + super(); + this.store = new TIntHashSet(size); + } + + /** + * Constructor. + */ + protected TroveHashSetModifiableDBIDs() { + super(); + this.store = new TIntHashSet(); + } + + /** + * Constructor. + * + * @param existing Existing IDs + */ + protected TroveHashSetModifiableDBIDs(DBIDs existing) { + this(existing.size()); + this.addDBIDs(existing); + } + + @Override + public DBIDIter iter() { + return new DBIDItr(store); + } + + @Override + public boolean addDBIDs(DBIDs ids) { + boolean success = false; + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + success |= store.add(iter.getIntegerID()); + } + return success; + } + + @Override + public boolean removeDBIDs(DBIDs ids) { + boolean success = false; + for(DBID id : ids) { + success |= store.remove(id.getIntegerID()); + } + return success; + } + + @Override + public boolean add(DBID e) { + return store.add(e.getIntegerID()); + } + + @Override + public boolean remove(DBID o) { + return store.remove(o.getIntegerID()); + } + + @Override + public boolean retainAll(DBIDs set) { + boolean modified = false; + Iterator<DBID> it = iterator(); + while(it.hasNext()) { + if(!set.contains(it.next())) { + it.remove(); + modified = true; + } + } + return modified; + } + + @Override + public Iterator<DBID> iterator() { + return new TroveIteratorAdapter(store.iterator()); + } + + @Override + public int size() { + return store.size(); + } + + @Override + public boolean isEmpty() { + return store.isEmpty(); + } + + @Override + public void clear() { + store.clear(); + } + + @Override + public boolean contains(DBID o) { + return store.contains(o.getIntegerID()); + } + + /** + * Iterator over trove hashs. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected static class DBIDItr extends THashPrimitiveIterator implements DBIDIter { + /** + * The has we access + */ + private TIntHash hash; + + /** + * Constructor. + * + * @param hash Trove hash + */ + public DBIDItr(TIntHash hash) { + super(hash); + this.hash = hash; + this._index = nextIndex(); // Find first element + } + + @Override + public boolean valid() { + return _index >= 0; + } + + @Override + public void advance() { + this._index = nextIndex(); + } + + @Override + public int getIntegerID() { + return hash._set[_index]; + } + + @Override + public DBID getDBID() { + return new IntegerDBID(hash._set[_index]); + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/TreeSetModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveIteratorAdapter.java index 4212f847..2f596f47 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/TreeSetModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveIteratorAdapter.java @@ -1,10 +1,10 @@ -package de.lmu.ifi.dbs.elki.database.ids; +package de.lmu.ifi.dbs.elki.database.ids.integer; /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,13 +23,44 @@ package de.lmu.ifi.dbs.elki.database.ids; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.NavigableSet; +import gnu.trove.iterator.TIntIterator; + +import java.util.Iterator; + +import de.lmu.ifi.dbs.elki.database.ids.DBID; /** - * Set-oriented implementation of a modifiable DBID collection. + * Adapter for using GNU Trove iterators. * * @author Erich Schubert */ -public interface TreeSetModifiableDBIDs extends ModifiableDBIDs, TreeSetDBIDs, NavigableSet<DBID> { - // empty +class TroveIteratorAdapter implements Iterator<DBID> { + /** + * The actual iterator. + */ + private TIntIterator iterator; + + /** + * Constructor. + * + * @param iterator Trove iterator + */ + protected TroveIteratorAdapter(TIntIterator iterator) { + this.iterator = iterator; + } + + @Override + public boolean hasNext() { + return iterator.hasNext(); + } + + @Override + public DBID next() { + return new IntegerDBID(iterator.next()); + } + + @Override + public void remove() { + iterator.remove(); + } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/package-info.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/package-info.java index d7ab7304..2508c930 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/package-info.java @@ -10,7 +10,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2011 +Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/package-info.java b/src/de/lmu/ifi/dbs/elki/database/ids/package-info.java index ce8d1f39..2c7de1c5 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/package-info.java @@ -17,19 +17,16 @@ * <th></th> * <th style="border-bottom: 2px">{@link de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs ArrayDBIDs}</th> * <th style="border-bottom: 2px">{@link de.lmu.ifi.dbs.elki.database.ids.HashSetDBIDs HashSetDBIDs}</th> - * <th style="border-bottom: 2px">{@link de.lmu.ifi.dbs.elki.database.ids.TreeSetDBIDs TreeSetDBIDs}</th> * </tr> * <tr> * <th style="border-right: 2px">{@link de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs ModifiableDBIDs}</th> * <td>{@link de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs ArrayModifiableDBIDs}</td> * <td>{@link de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs HashSetModifiableDBIDs}</td> - * <td>{@link de.lmu.ifi.dbs.elki.database.ids.TreeSetModifiableDBIDs TreeSetModifiableDBIDs}</td> * </tr> * <tr> * <th style="border-right: 2px">{@link de.lmu.ifi.dbs.elki.database.ids.StaticDBIDs StaticDBIDs}</th> * <td>{@link de.lmu.ifi.dbs.elki.database.ids.ArrayStaticDBIDs ArrayStaticDBIDs}</td> * <td>n/a</td> - * <td>n/a</td> * </tr> * </table> * @@ -47,8 +44,6 @@ * ArrayModifiableDBIDs array = DBIDUtil.newArraySet(123); * // new DBID hash set with minimum initial capacity * ModifiableDBIDs hash = DBIDUtil.newHashSet(); - * // initialize a tree set with the IDs of the database. - * ModifiableDBIDs tree = DBIDUtil.newTreeSet(database.getIDs()); * * // add all DBIDs from the hash * tree.addDBIDs(hash) @@ -78,25 +73,25 @@ * @apiviz.exclude java.* */ /* -This file is part of ELKI: -Environment for Developing KDD-Applications Supported by Index-Structures + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2011 -Ludwig-Maximilians-Universität München -Lehr- und Forschungseinheit für Datenbanksysteme -ELKI Development Team + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team -This program is free software: you can redistribute it and/or modify -it under the terms of the GNU Affero General Public License as published by -the Free Software Foundation, either version 3 of the License, or -(at your option) any later version. + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. -This program is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU Affero General Public License for more details. + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. -You should have received a copy of the GNU Affero General Public License -along with this program. If not, see <http://www.gnu.org/licenses/>. -*/ + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ package de.lmu.ifi.dbs.elki.database.ids;
\ No newline at end of file |