diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/database/ids/generic')
15 files changed, 57 insertions, 1781 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/AbstractKNNHeap.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/AbstractKNNHeap.java deleted file mode 100644 index c42c728d..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/AbstractKNNHeap.java +++ /dev/null @@ -1,93 +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) 2013 - 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.distance.DistanceDBIDPair; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNHeap; -import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResultUtil; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.TiedTopBoundedHeap; - -/** - * Heap used for KNN management. - * - * @author Erich Schubert - * - * @param <P> pair type - * @param <D> distance type - */ -abstract class AbstractKNNHeap<P extends DistanceDBIDPair<D>, D extends Distance<D>> implements KNNHeap<D> { - /** - * The actual heap. - */ - protected final TiedTopBoundedHeap<P> heap; - - /** - * Constructor. - * - * @param k Maximum heap size (unless tied) - */ - public AbstractKNNHeap(int k) { - super(); - heap = new TiedTopBoundedHeap<>(k, DistanceDBIDResultUtil.BY_REVERSE_DISTANCE); - } - - /** - * Add a pair to the heap. - * - * @param pair Pair to add. - */ - public abstract void insert(P pair); - - @Override - public final int getK() { - return heap.getMaxSize(); - } - - @Override - public int size() { - return heap.size(); - } - - @Override - public P peek() { - return heap.peek(); - } - - @Override - public boolean isEmpty() { - return heap.isEmpty(); - } - - @Override - public void clear() { - heap.clear(); - } - - @Override - public P poll() { - return heap.poll(); - } -}
\ No newline at end of file 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 deleted file mode 100644 index 85fdcffd..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/DBIDIterAdapter.java +++ /dev/null @@ -1,82 +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) 2013 - 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.Iterator; - -import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.DBIDMIter; - -/** - * Iterator for classic collections. - * - * @author Erich Schubert - */ -public class DBIDIterAdapter implements DBIDMIter { - /** - * 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 internalGetIndex() { - return cur.internalGetIndex(); - } - - @Override - public void remove() { - iter.remove(); - } -}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/DistanceDBIDPairKNNHeap.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/DistanceDBIDPairKNNHeap.java deleted file mode 100644 index e102d716..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/DistanceDBIDPairKNNHeap.java +++ /dev/null @@ -1,106 +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) 2013 - 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.DBIDFactory; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDPair; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; - -/** - * Heap for collecting kNN candidates with arbitrary distance types. - * - * For double distances, see {@link DoubleDistanceDBIDPairKNNHeap} - * - * <b>To instantiate, use {@link de.lmu.ifi.dbs.elki.database.ids.DBIDUtil#newHeap} instead!</b> - * - * @author Erich Schubert - * - * @param <D> Distance type - */ -public class DistanceDBIDPairKNNHeap<D extends Distance<D>> extends AbstractKNNHeap<DistanceDBIDPair<D>, D> { - /** - * Cached distance to k nearest neighbor (to avoid going through {@link #peek} - * each time). - */ - protected D knndistance = null; - - /** - * Constructor. - * - * <b>To instantiate, use {@link de.lmu.ifi.dbs.elki.database.ids.DBIDUtil#newHeap} instead!</b> - * - * @param k Heap size - */ - public DistanceDBIDPairKNNHeap(int k) { - super(k); - } - - /** - * Serialize to a {@link DistanceDBIDPairKNNList}. This empties the heap! - * - * @return KNNList with the heaps contents. - */ - @Override - public DistanceDBIDPairKNNList<D> toKNNList() { - return new DistanceDBIDPairKNNList<>(this); - } - - @Override - public void insert(D distance, DBIDRef id) { - if (size() < getK()) { - heap.add(DBIDFactory.FACTORY.newDistancePair(distance, id)); - heapModified(); - return; - } - // size >= maxsize. Insert only when necessary. - if (knndistance.compareTo(distance) >= 0) { - // Replace worst element. - heap.add(DBIDFactory.FACTORY.newDistancePair(distance, id)); - heapModified(); - } - } - - @Override - public void insert(DistanceDBIDPair<D> pair) { - if (size() < getK() || knndistance.compareTo(pair.getDistance()) >= 0) { - heap.add(pair); - heapModified(); - } - } - - // @Override - protected void heapModified() { - // super.heapModified(); - // Update threshold. - if (size() >= getK()) { - knndistance = heap.peek().getDistance(); - } - } - - @Override - public D getKNNDistance() { - return knndistance; - } -} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/DistanceDBIDPairKNNList.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/DistanceDBIDPairKNNList.java deleted file mode 100644 index bc5392d6..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/DistanceDBIDPairKNNList.java +++ /dev/null @@ -1,211 +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) 2013 - 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; -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.distance.DistanceDBIDPair; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDListIter; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNHeap; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap; - -/** - * Finalized KNN List. - * - * @author Erich Schubert - * - * @param <D> Distance type - */ -public class DistanceDBIDPairKNNList<D extends Distance<D>> implements KNNList<D> { - /** - * The value of k this was materialized for. - */ - private final int k; - - /** - * The actual data array. - */ - private final Object[] data; - - /** - * Constructor, to be called from KNNHeap only. Use {@link KNNHeap#toKNNList} - * instead! - * - * @param heap Calling heap - */ - protected DistanceDBIDPairKNNList(KNNHeap<D> heap) { - super(); - this.data = new Object[heap.size()]; - this.k = heap.getK(); - // Get sorted data from heap; but in reverse. - int i = heap.size(); - while (heap.size() > 0) { - i--; - assert (i >= 0); - data[i] = heap.poll(); - } - assert (data.length == 0 || data[0] != null); - assert (heap.size() == 0); - } - - /** - * Constructor. With a KNNHeap, use {@link KNNHeap#toKNNList} instead! - * - * @param heap Calling heap - * @param k K value - */ - public DistanceDBIDPairKNNList(Heap<? extends DistanceDBIDPair<D>> heap, int k) { - super(); - this.data = new Object[heap.size()]; - this.k = k; - assert (heap.size() >= this.k) : "Heap doesn't contain enough objects!"; - // Get sorted data from heap; but in reverse. - int i = heap.size(); - while (!heap.isEmpty()) { - i--; - assert (i >= 0); - data[i] = heap.poll(); - } - assert (data.length == 0 || data[0] != null); - assert (heap.size() == 0); - } - - @Override - public int getK() { - return k; - } - - @Override - public D getKNNDistance() { - return get(getK() - 1).getDistance(); - } - - @Override - public String toString() { - StringBuilder buf = new StringBuilder(); - buf.append("kNNList["); - for (DistanceDBIDListIter<D> iter = this.iter(); iter.valid();) { - buf.append(iter.getDistance()).append(':').append(DBIDUtil.toString(iter)); - iter.advance(); - if (iter.valid()) { - buf.append(','); - } - } - buf.append(']'); - return buf.toString(); - } - - @SuppressWarnings("unchecked") - @Override - public DistanceDBIDPair<D> get(int index) { - return (DistanceDBIDPair<D>) data[index]; - } - - @Override - public DistanceDBIDListIter<D> iter() { - return new Itr(); - } - - @Override - public int size() { - return data.length; - } - - @Override - public boolean contains(DBIDRef o) { - for (DBIDIter iter = iter(); iter.valid(); iter.advance()) { - if (DBIDUtil.equal(iter, o)) { - return true; - } - } - return false; - } - - @Override - public boolean isEmpty() { - return size() == 0; - } - - /** - * Iterator. - * - * @author Erich Schubert - * - * @apiviz.exclude - */ - private class Itr implements DistanceDBIDListIter<D> { - /** - * Cursor position. - */ - private int pos = 0; - - @Override - public int internalGetIndex() { - return get(pos).internalGetIndex(); - } - - @Override - public boolean valid() { - return pos < data.length; - } - - @Override - public void advance() { - pos++; - } - - @Override - public D getDistance() { - return get(pos).getDistance(); - } - - @Override - public DistanceDBIDPair<D> getDistancePair() { - return get(pos); - } - - @Override - public int getOffset() { - return pos; - } - - @Override - public void advance(int count) { - pos += count; - } - - @Override - public void retract() { - --pos; - } - - @Override - public void seek(int off) { - pos += off; - } - } -} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/DoubleDistanceDBIDPairKNNHeap.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/DoubleDistanceDBIDPairKNNHeap.java deleted file mode 100644 index 8e489a79..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/DoubleDistanceDBIDPairKNNHeap.java +++ /dev/null @@ -1,218 +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) 2013 - 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.DBIDFactory; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDPair; -import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNHeap; -import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; - -/** - * Heap for collecting double-valued KNN instances. - * - * See also: {@link de.lmu.ifi.dbs.elki.database.ids.DBIDUtil#newHeap}! - * - * Experiments have shown that it <em>can</em> be much more performant to track - * the knndistance <em>outside</em> of the heap, and do comparisons on the - * stack: <blockquote> - * - * <pre> - * {@code - * double knndist = Double.POSITIVE_INFINITY; - * DoubleDistanceDBIDPairKNNHeap heap = new DoubleDistanceDBIDPairKNNHeap(k); - * for (DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { - * double dist = computeDistance(iditer, ...); - * if (dist < knndist) { - * heap.add(dist, iditer); - * if (heap.size() >= k) { - * max = heap.doubleKNNDistance(); - * } - * } - * } - * } - * </pre> - * - * </blockquote> - * - * The reason probably is that {@code knndist} resides on the stack and can be - * better optimized by the hotspot compiler. - * - * @author Erich Schubert - */ -public class DoubleDistanceDBIDPairKNNHeap extends AbstractKNNHeap<DoubleDistanceDBIDPair, DoubleDistance> implements DoubleDistanceKNNHeap { - /** - * Comparator class. - */ - public static final Comparator<DoubleDistanceDBIDPair> COMPARATOR = new Comp(); - - /** - * Reverse comparator. - */ - public static final Comparator<DoubleDistanceDBIDPair> REVERSE_COMPARATOR = new RComp(); - - /** - * Cached distance to k nearest neighbor (to avoid going through {@link #peek} - * too often). - */ - protected double knndistance = Double.POSITIVE_INFINITY; - - /** - * Constructor. - * - * See also: {@link de.lmu.ifi.dbs.elki.database.ids.DBIDUtil#newHeap}! - * - * @param k Heap size - */ - public DoubleDistanceDBIDPairKNNHeap(int k) { - super(k); - } - - /** - * Serialize to a {@link DoubleDistanceDBIDPairKNNList}. This empties the - * heap! - * - * @return KNNList with the heaps contents. - */ - @Override - public DoubleDistanceDBIDPairKNNList toKNNList() { - return new DoubleDistanceDBIDPairKNNList(this); - } - - /** - * Add a distance-id pair to the heap unless the distance is too large. - * - * Compared to the super.add() method, this often saves the pair construction. - * - * @param distance Distance value - * @param id ID number - * @return knn distance. - */ - @Override - public final double insert(final double distance, final DBIDRef id) { - if (size() < getK() || knndistance >= distance) { - heap.add(DBIDFactory.FACTORY.newDistancePair(distance, id)); - heapModified(); - } - return knndistance; - } - - /** - * Add a distance-id pair to the heap unless the distance is too large. - * - * Compared to the super.add() method, this often saves the pair construction. - * - * @param distance Distance value - * @param id ID number - */ - @Override - @Deprecated - public final void insert(final Double distance, final DBIDRef id) { - if (size() < getK() || knndistance >= distance) { - heap.add(DBIDFactory.FACTORY.newDistancePair(distance, id)); - heapModified(); - } - } - - // @Override - protected void heapModified() { - // super.heapModified(); - if (size() >= getK()) { - knndistance = heap.peek().doubleDistance(); - } - } - - @Override - public void insert(final DoubleDistanceDBIDPair e) { - if (size() < getK() || knndistance >= e.doubleDistance()) { - heap.add(e); - heapModified(); - } - } - - /** - * {@inheritDoc} - * - * @deprecated if you know your distances are double-valued, you should be - * using the primitive type. - * - */ - @Override - @Deprecated - public void insert(DoubleDistance dist, DBIDRef id) { - insert(dist.doubleValue(), id); - } - - /** - * Get the distance to the k nearest neighbor, or maxdist otherwise. - * - * @return Maximum distance - */ - @Override - public double doubleKNNDistance() { - return knndistance; - } - - /** - * {@inheritDoc} - * - * @deprecated if you know your distances are double-valued, you should be - * using the primitive type. - */ - @Override - @Deprecated - public DoubleDistance getKNNDistance() { - return new DoubleDistance(knndistance); - } - - /** - * Comparator to use. - * - * @author Erich Schubert - * - * @apiviz.exclude - */ - protected static class Comp implements Comparator<DoubleDistanceDBIDPair> { - @Override - public int compare(DoubleDistanceDBIDPair o1, DoubleDistanceDBIDPair o2) { - return -Double.compare(o1.doubleDistance(), o2.doubleDistance()); - } - } - - /** - * Comparator to use. - * - * @author Erich Schubert - * - * @apiviz.exclude - */ - protected static class RComp implements Comparator<DoubleDistanceDBIDPair> { - @Override - public int compare(DoubleDistanceDBIDPair o1, DoubleDistanceDBIDPair o2) { - return Double.compare(o1.doubleDistance(), o2.doubleDistance()); - } - } -} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/DoubleDistanceDBIDPairKNNList.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/DoubleDistanceDBIDPairKNNList.java deleted file mode 100644 index c72529ad..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/DoubleDistanceDBIDPairKNNList.java +++ /dev/null @@ -1,257 +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) 2013 - 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.Iterator; - -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.distance.DoubleDistanceDBIDPair; -import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDListIter; -import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNList; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNHeap; -import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; -import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.Heap; - -/** - * Finalized KNN List. - * - * @author Erich Schubert - * - * @apiviz.composedOf DoubleDistanceDBIDPair - * @apiviz.has DoubleDistanceDBIDListIter - */ -public class DoubleDistanceDBIDPairKNNList implements DoubleDistanceKNNList { - /** - * The value of k this was materialized for. - */ - private final int k; - - /** - * The actual data array. - */ - private final DoubleDistanceDBIDPair[] data; - - /** - * Constructor. This will <em>clone</em> the given collection! - * - * @param col Existing collection - * @param k K parameter - */ - public DoubleDistanceDBIDPairKNNList(Collection<DoubleDistanceDBIDPair> col, int k) { - super(); - this.data = new DoubleDistanceDBIDPair[col.size()]; - this.k = k; - assert (col.size() >= this.k) : "Collection doesn't contain enough objects!"; - // Get sorted data from heap; but in reverse. - Iterator<DoubleDistanceDBIDPair> it = col.iterator(); - for (int i = 0; it.hasNext(); i++) { - data[i] = it.next(); - } - assert (data.length == 0 || data[0] != null); - } - - /** - * Constructor, to be called from KNNHeap only. Use {@link KNNHeap#toKNNList} - * instead! - * - * @param heap Calling heap - */ - protected DoubleDistanceDBIDPairKNNList(DoubleDistanceDBIDPairKNNHeap heap) { - super(); - this.data = new DoubleDistanceDBIDPair[heap.size()]; - this.k = heap.getK(); - // Get sorted data from heap; but in reverse. - int i = heap.size(); - while (heap.size() > 0) { - i--; - assert (i >= 0); - data[i] = heap.poll(); - } - assert (data.length == 0 || data[0] != null); - assert (heap.size() == 0); - } - - /** - * Constructor, to be called from KNNHeap only. Use {@link KNNHeap#toKNNList} - * instead! - * - * @param heap Calling heap - * @param k Target number of neighbors (before ties) - */ - public DoubleDistanceDBIDPairKNNList(Heap<DoubleDistanceDBIDPair> heap, int k) { - super(); - this.data = new DoubleDistanceDBIDPair[heap.size()]; - this.k = k; - assert (heap.size() >= this.k) : "Heap doesn't contain enough objects!"; - // Get sorted data from heap; but in reverse. - int i = heap.size(); - while (heap.size() > 0) { - i--; - assert (i >= 0); - data[i] = heap.poll(); - } - assert (data.length == 0 || data[0] != null); - assert (heap.size() == 0); - } - - @Override - public int getK() { - return k; - } - - @Override - @Deprecated - public DoubleDistance getKNNDistance() { - if (size() < k) { - return DoubleDistance.INFINITE_DISTANCE; - } - return get(k - 1).getDistance(); - } - - @Override - public double doubleKNNDistance() { - if (size() < k) { - return Double.POSITIVE_INFINITY; - } - return get(k - 1).doubleDistance(); - } - - @Override - public String toString() { - StringBuilder buf = new StringBuilder(); - buf.append("kNNList["); - for (DoubleDistanceDBIDListIter iter = this.iter(); iter.valid();) { - buf.append(iter.doubleDistance()).append(':').append(DBIDUtil.toString(iter)); - iter.advance(); - if (iter.valid()) { - buf.append(','); - } - } - buf.append(']'); - return buf.toString(); - } - - @Override - public DoubleDistanceDBIDPair get(int index) { - return data[index]; - } - - @Override - public DoubleDistanceDBIDListIter iter() { - return new Itr(); - } - - @Override - public int size() { - return data.length; - } - - @Override - public boolean contains(DBIDRef o) { - for (DBIDIter iter = iter(); iter.valid(); iter.advance()) { - if (DBIDUtil.equal(iter, o)) { - return true; - } - } - return false; - } - - @Override - public boolean isEmpty() { - return size() == 0; - } - - /** - * Iterator. - * - * @author Erich Schubert - * - * @apiviz.exclude - */ - private class Itr implements DoubleDistanceDBIDListIter { - /** - * Cursor position. - */ - private int pos = 0; - - @Override - public int internalGetIndex() { - return get(pos).internalGetIndex(); - } - - @Override - public boolean valid() { - return pos < data.length; - } - - @Override - public void advance() { - pos++; - } - - /** - * {@inheritDoc} - * - * @deprecated use {@link #doubleDistance}! - */ - @Override - @Deprecated - public DoubleDistance getDistance() { - return get(pos).getDistance(); - } - - @Override - public double doubleDistance() { - return get(pos).doubleDistance(); - } - - @Override - public DoubleDistanceDBIDPair getDistancePair() { - return get(pos); - } - - @Override - public int getOffset() { - return pos; - } - - @Override - public void advance(int count) { - pos += count; - } - - @Override - public void retract() { - --pos; - } - - @Override - public void seek(int off) { - pos = off; - } - } -} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/DoubleDistanceDBIDPairKNNListHeap.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/DoubleDistanceDBIDPairKNNListHeap.java deleted file mode 100644 index ca00129b..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/DoubleDistanceDBIDPairKNNListHeap.java +++ /dev/null @@ -1,289 +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) 2013 - 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.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.distance.DoubleDistanceDBIDListIter; -import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDPair; -import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNHeap; -import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNList; -import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; - -/** - * Finalized KNN List. - * - * @author Erich Schubert - * - * @apiviz.composedOf DoubleDistanceDBIDPair - * @apiviz.has DoubleDistanceDBIDListIter - */ -public class DoubleDistanceDBIDPairKNNListHeap implements DoubleDistanceKNNList, DoubleDistanceKNNHeap { - /** - * The value of k this was materialized for. - */ - private final int k; - - /** - * The actual data array. - */ - private DoubleDistanceDBIDPair[] data; - - /** - * Current size - */ - private int size; - - /** - * Constructor. - * - * @param k K parameter - */ - public DoubleDistanceDBIDPairKNNListHeap(int k) { - super(); - this.data = new DoubleDistanceDBIDPair[k + 11]; - this.k = k; - } - - @Override - public void clear() { - size = 0; - Arrays.fill(data, null); - } - - @Override - public double insert(double distance, DBIDRef id) { - if (size < k || distance <= data[k - 1].doubleDistance()) { - insert(DBIDUtil.newDistancePair(distance, id)); - } - return (size < k) ? Double.POSITIVE_INFINITY : get(k - 1).doubleDistance(); - } - - @Override - @Deprecated - public void insert(Double distance, DBIDRef id) { - insert(DBIDUtil.newDistancePair(distance.doubleValue(), id)); - } - - @Override - @Deprecated - public void insert(DoubleDistance dist, DBIDRef id) { - insert(DBIDUtil.newDistancePair(dist.doubleValue(), id)); - } - - @Override - public void insert(DoubleDistanceDBIDPair e) { - if (size >= k) { - if (e.doubleDistance() > data[size - 1].doubleDistance()) { - return; - } - // Ensure we have enough space. - final int len = data.length; - if (size > len) { - final int newlength = len + (len >>> 1); - assert (newlength > size); - data = Arrays.copyOf(data, newlength); - } - } - insertionSort(e); - // Truncate if necessary: - if (size > k && data[k].doubleDistance() > data[k - 1].doubleDistance()) { - size = k; - } - } - - /** - * Perform insertion sort. - * - * @param obj Object to insert - */ - private void insertionSort(DoubleDistanceDBIDPair obj) { - // Insertion sort: - int pos = size; - while (pos > 0) { - DoubleDistanceDBIDPair pobj = data[pos - 1]; - if (pobj.doubleDistance() <= obj.doubleDistance()) { - break; - } - data[pos] = pobj; - --pos; - } - data[pos] = obj; - ++size; - } - - @Override - public DoubleDistanceDBIDPair poll() { - assert (size > 0); - return data[size--]; - } - - @Override - public DoubleDistanceDBIDPair peek() { - assert (size > 0); - return data[size - 1]; - } - - @Override - public DoubleDistanceKNNList toKNNList() { - return this; - } - - @Override - public int getK() { - return k; - } - - @Override - @Deprecated - public DoubleDistance getKNNDistance() { - if (size < k) { - return DoubleDistance.INFINITE_DISTANCE; - } - return get(k - 1).getDistance(); - } - - @Override - public double doubleKNNDistance() { - return (size < k) ? Double.POSITIVE_INFINITY : get(k - 1).doubleDistance(); - } - - @Override - public String toString() { - StringBuilder buf = new StringBuilder(); - buf.append("kNNList["); - for (DoubleDistanceDBIDListIter iter = this.iter(); iter.valid();) { - buf.append(iter.doubleDistance()).append(':').append(DBIDUtil.toString(iter)); - iter.advance(); - if (iter.valid()) { - buf.append(','); - } - } - buf.append(']'); - return buf.toString(); - } - - @Override - public DoubleDistanceDBIDPair get(int index) { - return data[index]; - } - - @Override - public DoubleDistanceDBIDListIter iter() { - return new Itr(); - } - - @Override - public int size() { - return data.length; - } - - @Override - public boolean contains(DBIDRef o) { - for (DBIDIter iter = iter(); iter.valid(); iter.advance()) { - if (DBIDUtil.equal(iter, o)) { - return true; - } - } - return false; - } - - @Override - public boolean isEmpty() { - return size() == 0; - } - - /** - * Iterator. - * - * @author Erich Schubert - * - * @apiviz.exclude - */ - private class Itr implements DoubleDistanceDBIDListIter { - /** - * Cursor position. - */ - private int pos = 0; - - @Override - public int internalGetIndex() { - return get(pos).internalGetIndex(); - } - - @Override - public boolean valid() { - return pos < data.length; - } - - @Override - public void advance() { - pos++; - } - - /** - * {@inheritDoc} - * - * @deprecated use {@link #doubleDistance}! - */ - @Override - @Deprecated - public DoubleDistance getDistance() { - return get(pos).getDistance(); - } - - @Override - public double doubleDistance() { - return get(pos).doubleDistance(); - } - - @Override - public DoubleDistanceDBIDPair getDistancePair() { - return get(pos); - } - - @Override - public int getOffset() { - return pos; - } - - @Override - public void advance(int count) { - pos += count; - } - - @Override - public void retract() { - --pos; - } - - @Override - public void seek(int off) { - pos = off; - } - } -} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/DoubleDistanceKNNSubList.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/DoubleDistanceKNNSubList.java deleted file mode 100644 index c2854a54..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/DoubleDistanceKNNSubList.java +++ /dev/null @@ -1,190 +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) 2013 - 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; -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.distance.DoubleDistanceDBIDPair; -import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDListIter; -import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNList; -import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; - -/** - * Sublist of an existing result to contain only the first k elements. - * - * TOOD: can be optimized slightly better. - * - * @author Erich Schubert - */ -public class DoubleDistanceKNNSubList implements DoubleDistanceKNNList { - /** - * Parameter k. - */ - private final int k; - - /** - * Actual size, including ties. - */ - private final int size; - - /** - * Wrapped inner result. - */ - private final DoubleDistanceKNNList inner; - - /** - * Constructor. - * - * @param inner Inner instance - * @param k k value - */ - public DoubleDistanceKNNSubList(DoubleDistanceKNNList inner, int k) { - this.inner = inner; - this.k = k; - // Compute list size - { - DoubleDistanceDBIDPair dist = inner.get(k); - int i = k; - while (i + 1 < inner.size()) { - if (dist.compareByDistance(inner.get(i + 1)) < 0) { - break; - } - i++; - } - size = i; - } - } - - @Override - public int getK() { - return k; - } - - @Override - public DoubleDistanceDBIDPair get(int index) { - assert (index < size) : "Access beyond design size of list."; - return inner.get(index); - } - - @Override - @Deprecated - public DoubleDistance getKNNDistance() { - return inner.get(k).getDistance(); - } - - @Override - public double doubleKNNDistance() { - return inner.get(k).doubleDistance(); - } - - @Override - public DoubleDistanceDBIDListIter iter() { - return new Itr(); - } - - @Override - public boolean contains(DBIDRef o) { - for (DBIDIter iter = iter(); iter.valid(); iter.advance()) { - if (DBIDUtil.equal(iter, o)) { - return true; - } - } - return false; - } - - @Override - public boolean isEmpty() { - return size == 0; - } - - @Override - public int size() { - return size; - } - - /** - * Iterator for the sublist. - * - * @author Erich Schubert - * - * @apiviz.exclude - */ - private class Itr implements DoubleDistanceDBIDListIter { - /** - * Current position. - */ - private int pos = 0; - - @Override - public boolean valid() { - return pos < size; - } - - @Override - public void advance() { - pos++; - } - - @Override - @Deprecated - public DoubleDistance getDistance() { - return inner.get(pos).getDistance(); - } - - @Override - public double doubleDistance() { - return inner.get(pos).doubleDistance(); - } - - @Override - public DoubleDistanceDBIDPair getDistancePair() { - return inner.get(pos); - } - - @Override - public int internalGetIndex() { - return inner.get(pos).internalGetIndex(); - } - - @Override - public int getOffset() { - return pos; - } - - @Override - public void advance(int count) { - pos += count; - } - - @Override - public void retract() { - --pos; - } - - @Override - public void seek(int off) { - pos = off; - } - } -} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericDistanceDBIDList.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericDistanceDBIDList.java deleted file mode 100644 index 911c58e7..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/GenericDistanceDBIDList.java +++ /dev/null @@ -1,206 +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) 2013 - 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 java.util.Comparator; - -import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; -import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDListIter; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDPair; -import de.lmu.ifi.dbs.elki.database.ids.distance.ModifiableDistanceDBIDList; -import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResultUtil; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; - -/** - * Default class to keep a list of distance-object pairs. - * - * @author Erich Schubert - * - * @param <D> Distance type - */ -public class GenericDistanceDBIDList<D extends Distance<D>> implements ModifiableDistanceDBIDList<D> { - /** - * Actual storage. - */ - Object[] storage; - - /** - * Current size. - */ - int size = 0; - - /** - * Constructor. - */ - public GenericDistanceDBIDList() { - super(); - storage = new Object[21]; - } - - /** - * Constructor. - * - * @param initialCapacity Capacity - */ - public GenericDistanceDBIDList(int initialCapacity) { - super(); - storage = new Object[initialCapacity]; - } - - @Override - public void add(D dist, DBIDRef id) { - ensureSize(size + 1); - storage[size] = DBIDFactory.FACTORY.newDistancePair(dist, id); - ++size; - } - - /** - * Add a prepared pair. - * - * @param pair Pair to add - */ - public void add(DistanceDBIDPair<D> pair) { - ensureSize(size + 1); - storage[size] = pair; - ++size; - } - - private void ensureSize(int size) { - if (size < storage.length) { - storage = Arrays.copyOf(storage, (size << 1) + 1); - } - } - - @Override - public void sort() { - @SuppressWarnings("unchecked") - final Comparator<Object> comp = (Comparator<Object>) DistanceDBIDResultUtil.distanceComparator(); - Arrays.sort(storage, 0, size, comp); - // DistanceDBIDResultUtil.sortByDistance(storage); - } - - @Override - public int size() { - return size; - } - - @SuppressWarnings("unchecked") - @Override - public DistanceDBIDPair<D> get(int off) { - return (DistanceDBIDPair<D>) storage[off]; - } - - @Override - public DistanceDBIDListIter<D> iter() { - return new Itr(); - } - - @Override - public boolean contains(DBIDRef o) { - for (DBIDIter iter = iter(); iter.valid(); iter.advance()) { - if (DBIDUtil.equal(iter, o)) { - return true; - } - } - return false; - } - - @Override - public boolean isEmpty() { - return size() == 0; - } - - @Override - public String toString() { - return DistanceDBIDResultUtil.toString(this); - } - - /** - * Iterator class. - * - * @author Erich Schubert - * - * @apiviz.exclude - */ - protected class Itr implements DistanceDBIDListIter<D> { - /** - * Iterator position. - */ - int pos = 0; - - @Override - public int internalGetIndex() { - return get(pos).internalGetIndex(); - } - - @Override - public boolean valid() { - return pos < size(); - } - - @Override - public void advance() { - pos++; - } - - @Override - public D getDistance() { - return get(pos).getDistance(); - } - - @Override - public DistanceDBIDPair<D> getDistancePair() { - return get(pos); - } - - @Override - public String toString() { - return valid() ? getDistancePair().toString() : "null"; - } - - @Override - public int getOffset() { - return pos; - } - - @Override - public void advance(int count) { - pos += count; - } - - @Override - public void retract() { - --pos; - } - - @Override - public void seek(int off) { - pos = off; - } - } -} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/generic/KNNSubList.java b/src/de/lmu/ifi/dbs/elki/database/ids/generic/KNNSubList.java index 3d7863fd..6bfb05b0 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/KNNSubList.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/generic/KNNSubList.java @@ -1,18 +1,10 @@ package de.lmu.ifi.dbs.elki.database.ids.generic; -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.distance.DistanceDBIDListIter; -import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDPair; -import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; - /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -30,15 +22,19 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; 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; +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.DoubleDBIDListIter; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; /** * Sublist of an existing result to contain only the first k elements. * * @author Erich Schubert - * - * @param <D> Distance */ -public class KNNSubList<D extends Distance<D>> implements KNNList<D> { +public class KNNSubList implements KNNList { /** * Parameter k. */ @@ -52,7 +48,7 @@ public class KNNSubList<D extends Distance<D>> implements KNNList<D> { /** * Wrapped inner result. */ - private final KNNList<D> inner; + private final KNNList inner; /** * Constructor. @@ -60,22 +56,24 @@ public class KNNSubList<D extends Distance<D>> implements KNNList<D> { * @param inner Inner instance * @param k k value */ - public KNNSubList(KNNList<D> inner, int k) { + public KNNSubList(KNNList inner, int k) { this.inner = inner; this.k = k; // Compute list size - // TODO: optimize for double distances. - { - DistanceDBIDPair<D> dist = inner.get(k); + if(k < inner.getK()) { + DoubleDBIDPair dist = inner.get(k); int i = k; - while (i + 1 < inner.size()) { - if (dist.compareByDistance(inner.get(i + 1)) < 0) { + while(i + 1 < inner.size()) { + if(dist.doubleValue() < inner.get(i + 1).doubleValue()) { break; } i++; } size = i; } + else { + size = inner.size(); + } } @Override @@ -84,25 +82,25 @@ public class KNNSubList<D extends Distance<D>> implements KNNList<D> { } @Override - public DistanceDBIDPair<D> get(int index) { + public DoubleDBIDPair get(int index) { assert (index < size) : "Access beyond design size of list."; return inner.get(index); } @Override - public D getKNNDistance() { - return inner.get(k).getDistance(); + public double getKNNDistance() { + return inner.get(k).doubleValue(); } @Override - public DistanceDBIDListIter<D> iter() { + public DoubleDBIDListIter iter() { return new Itr(); } @Override public boolean contains(DBIDRef o) { - for (DBIDIter iter = iter(); iter.valid(); iter.advance()) { - if (DBIDUtil.equal(iter, o)) { + for(DBIDIter iter = iter(); iter.valid(); iter.advance()) { + if(DBIDUtil.equal(iter, o)) { return true; } } @@ -126,7 +124,7 @@ public class KNNSubList<D extends Distance<D>> implements KNNList<D> { * * @apiviz.exclude */ - private class Itr implements DistanceDBIDListIter<D> { + private class Itr implements DoubleDBIDListIter { /** * Current position. */ @@ -134,21 +132,22 @@ public class KNNSubList<D extends Distance<D>> implements KNNList<D> { @Override public boolean valid() { - return pos < size; + return pos < size && pos >= 0; } @Override - public void advance() { + public Itr advance() { pos++; + return this; } @Override - public D getDistance() { - return inner.get(pos).getDistance(); + public double doubleValue() { + return inner.get(pos).doubleValue(); } @Override - public DistanceDBIDPair<D> getDistancePair() { + public DoubleDBIDPair getPair() { return inner.get(pos); } @@ -163,18 +162,21 @@ public class KNNSubList<D extends Distance<D>> implements KNNList<D> { } @Override - public void advance(int count) { - pos -= count; + public Itr advance(int count) { + pos += count; + return this; } @Override - public void retract() { + public Itr retract() { --pos; + return this; } @Override - public void seek(int off) { + public Itr seek(int off) { pos = off; + return this; } } } 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 2b481fca..19162450 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -35,6 +35,8 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDs; /** * View on an ArrayDBIDs masked using a BitMask for efficient mask changing. * + * FIXME: switch to long[] instead of BitSet + * * @author Erich Schubert * * @apiviz.uses DBIDs @@ -137,8 +139,9 @@ public class MaskedDBIDs implements DBIDs { } @Override - public void advance() { + public DBIDIter advance() { pos = bits.nextSetBit(pos + 1); + return this; } @Override @@ -180,8 +183,9 @@ public class MaskedDBIDs implements DBIDs { } @Override - public void advance() { + public DBIDIter advance() { pos = bits.nextClearBit(pos + 1); + return this; } @Override 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 deleted file mode 100644 index 7df6975c..00000000 --- a/src/de/lmu/ifi/dbs/elki/database/ids/generic/MergedDBIDs.java +++ /dev/null @@ -1,83 +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) 2013 - 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; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -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. - * - * @author Erich Schubert - * - * @apiviz.uses de.lmu.ifi.dbs.elki.database.ids.DBIDs - */ -// TODO: include ID mapping? -public class MergedDBIDs implements DBIDs { - /** - * Childs to merge - */ - DBIDs childs[]; - - /** - * Constructor. - * - * @param childs - */ - public MergedDBIDs(DBIDs... childs) { - super(); - this.childs = childs; - } - - @Override - public DBIDIter iter() { - throw new AbortException("Merged iterators not completely implemented yet!"); - } - - @Override - public int size() { - int si = 0; - for(DBIDs child : childs) { - si += child.size(); - } - return si; - } - - @Override - public boolean isEmpty() { - return size() == 0; - } - - @Override - public boolean contains(DBIDRef o) { - for(DBIDs child : childs) { - if(child.contains(o)) { - return true; - } - } - return false; - } -}
\ No newline at end of file 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 49c6b07e..0b5d8ed2 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 @@ -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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -131,8 +131,9 @@ public class UnmodifiableArrayDBIDs implements ArrayStaticDBIDs { } @Override - public void advance() { + public DBIDArrayIter advance() { it.advance(); + return this; } @Override @@ -141,18 +142,21 @@ public class UnmodifiableArrayDBIDs implements ArrayStaticDBIDs { } @Override - public void advance(int count) { + public DBIDArrayIter advance(int count) { it.advance(count); + return this; } @Override - public void retract() { + public DBIDArrayIter retract() { it.retract(); + return this; } @Override - public void seek(int off) { + public DBIDArrayIter seek(int off) { it.seek(off); + return this; } @Override 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 458dab3f..0f4920a5 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) 2013 + Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -109,8 +109,9 @@ public class UnmodifiableDBIDs implements StaticDBIDs { } @Override - public void advance() { + public DBIDIter advance() { it.advance(); + return this; } @Override 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 9920cac7..e2232e18 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) 2013 +Copyright (C) 2014 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team |