diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/database/ids/distance')
14 files changed, 1052 insertions, 0 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/distance/DistanceDBIDList.java b/src/de/lmu/ifi/dbs/elki/database/ids/distance/DistanceDBIDList.java new file mode 100644 index 00000000..360dda12 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/distance/DistanceDBIDList.java @@ -0,0 +1,87 @@ +package de.lmu.ifi.dbs.elki.database.ids.distance; + +/* + 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.DBIDs; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; + +/** + * Collection of objects and their distances. + * + * To iterate over the results, use the following code: + * + * <pre> + * {@code + * for (DistanceDBIDResultIter<D> iter = result.iter(); iter.valid(); iter.advance()) { + * // You can get the distance via: iter.getDistance(); + * // Or use iter just like any other DBIDRef + * } + * } + * </pre> + * + * If you are only interested in the IDs of the objects, the following is also + * sufficient: + * + * <pre> + * {@code + * for (DBIDIter<D> iter = result.iter(); iter.valid(); iter.advance()) { + * // Use iter just like any other DBIDRef + * } + * } + * </pre> + * + * @author Erich Schubert + * + * @apiviz.landmark + * + * @apiviz.composedOf DistanceDBIDPair + * @apiviz.has DistanceDBIDListIter + * + * @param <D> Distance type + */ +public interface DistanceDBIDList<D extends Distance<D>> extends DBIDs { + /** + * Size of list. + * + * @return Size + */ + @Override + int size(); + + /** + * Access a single pair. + * + * @param off Offset + * @return Pair + */ + DistanceDBIDPair<D> get(int off); + + /** + * Get an iterator + * + * @return New iterator + */ + @Override + DistanceDBIDListIter<D> iter(); +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/distance/DistanceDBIDListIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/distance/DistanceDBIDListIter.java new file mode 100644 index 00000000..914f3676 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/distance/DistanceDBIDListIter.java @@ -0,0 +1,55 @@ +package de.lmu.ifi.dbs.elki.database.ids.distance; + +/* + 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.DBIDArrayIter; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; + +/** + * Iterator over distance-based query results. + * + * There is no getter for the DBID, as this implements + * {@link de.lmu.ifi.dbs.elki.database.ids.DBIDRef}. + * + * @author Erich Schubert + * + * @apiviz.landmark + * + * @apiviz.has DistanceDBIDPair - - iterator for + */ +public interface DistanceDBIDListIter<D extends Distance<D>> extends DBIDArrayIter { + /** + * Get the distance + * + * @return distance + */ + public D getDistance(); + + /** + * Get an object pair. + * + * @return object pair + */ + public DistanceDBIDPair<D> getDistancePair(); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/distance/DistanceDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/distance/DistanceDBIDPair.java new file mode 100644 index 00000000..a9d879d9 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/distance/DistanceDBIDPair.java @@ -0,0 +1,53 @@ +package de.lmu.ifi.dbs.elki.database.ids.distance; + +/* + 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.DBIDRef; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; + +/** + * Pair containing a distance an an object ID + * + * Note: there is no getter for the object, as this is a {@link DBIDRef}. + * + * @author Erich Schubert + * + * @param <D> Distance + */ +public interface DistanceDBIDPair<D extends Distance<D>> extends DBIDRef { + /** + * Get the distance. + * + * @return Distance + */ + public D getDistance(); + + /** + * Compare to another result, by distance, smaller first. + * + * @param other Other result + * @return Comparison result + */ + public int compareByDistance(DistanceDBIDPair<D> other); +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/distance/DoubleDistanceDBIDList.java b/src/de/lmu/ifi/dbs/elki/database/ids/distance/DoubleDistanceDBIDList.java new file mode 100644 index 00000000..85182313 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/distance/DoubleDistanceDBIDList.java @@ -0,0 +1,39 @@ +package de.lmu.ifi.dbs.elki.database.ids.distance; + +/* + 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.distance.distancevalue.DoubleDistance; + +/** + * An object containing Double-DBID-Pairs. + * + * @author Erich Schubert + */ +public interface DoubleDistanceDBIDList extends DistanceDBIDList<DoubleDistance> { + @Override + DoubleDistanceDBIDListIter iter(); + + @Override + DoubleDistanceDBIDPair get(int off); +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/distance/DoubleDistanceDBIDListIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/distance/DoubleDistanceDBIDListIter.java new file mode 100644 index 00000000..68b2de1e --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/distance/DoubleDistanceDBIDListIter.java @@ -0,0 +1,60 @@ +package de.lmu.ifi.dbs.elki.database.ids.distance; + +/* + 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.distance.distancevalue.DoubleDistance; + +/** + * Iterator for double valued distance-based query results. + * + * @author Erich Schubert + */ +public interface DoubleDistanceDBIDListIter extends DistanceDBIDListIter<DoubleDistance> { + /** + * Get the distance + * + * @return distance + */ + public double doubleDistance(); + + /** + * Get an object pair. + * + * @return object pair + */ + @Override + public DoubleDistanceDBIDPair getDistancePair(); + + /** + * Get the distance + * + * @deprecated Use {@link #doubleDistance} to avoid creating unnecessary + * objects. + * + * @return distance + */ + @Deprecated + @Override + public DoubleDistance getDistance(); +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/distance/DoubleDistanceDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/distance/DoubleDistanceDBIDPair.java new file mode 100644 index 00000000..5286029b --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/distance/DoubleDistanceDBIDPair.java @@ -0,0 +1,54 @@ +package de.lmu.ifi.dbs.elki.database.ids.distance; + +/* + 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.DBIDRef; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; + +/** + * Pair containing a double distance a DBID. + * + * There is no getter for the DBID, as this is a {@link DBIDRef} already. + * + * @author Erich Schubert + */ +public interface DoubleDistanceDBIDPair extends DistanceDBIDPair<DoubleDistance> { + /** + * Get the distance. + * + * @deprecated Would produce a DoubleDistance object. Use {@link #doubleDistance} instead! + * + * @return Distance + */ + @Override + @Deprecated + public DoubleDistance getDistance(); + + /** + * Get the distance. + * + * @return Distance + */ + public double doubleDistance(); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/distance/DoubleDistanceDBIDPairList.java b/src/de/lmu/ifi/dbs/elki/database/ids/distance/DoubleDistanceDBIDPairList.java new file mode 100644 index 00000000..f9bfc20a --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/distance/DoubleDistanceDBIDPairList.java @@ -0,0 +1,212 @@ +package de.lmu.ifi.dbs.elki.database.ids.distance; + +/* + 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.ArrayList; +import java.util.Collections; + +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.distance.distanceresultlist.DistanceDBIDResultUtil; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; + +/** + * Default class to keep a list of distance-object pairs. + * + * @author Erich Schubert + * + * @apiviz.composedOf DoubleDistanceDBIDPair + * @apiviz.has DoubleDistanceDBIDListIter + */ +public class DoubleDistanceDBIDPairList implements ModifiableDoubleDistanceDBIDList { + /** + * Actual storage. + */ + final ArrayList<DoubleDistanceDBIDPair> storage; + + /** + * Constructor. + */ + public DoubleDistanceDBIDPairList() { + super(); + storage = new ArrayList<>(); + } + + /** + * Constructor. + * + * @param initialCapacity Capacity + */ + public DoubleDistanceDBIDPairList(int initialCapacity) { + super(); + storage = new ArrayList<>(initialCapacity); + } + + /** + * Add an element. + * + * @deprecated Pass a double value instead. + * + * @param dist Distance + * @param id ID + */ + @Override + @Deprecated + public void add(DoubleDistance dist, DBIDRef id) { + storage.add(DBIDFactory.FACTORY.newDistancePair(dist.doubleValue(), id)); + } + + /** + * Add an element. + * + * @param dist Distance + * @param id ID + */ + @Override + public void add(double dist, DBIDRef id) { + storage.add(DBIDFactory.FACTORY.newDistancePair(dist, id)); + } + + /** + * Add an element. + * + * @param pair Pair to add + */ + @Override + public void add(DoubleDistanceDBIDPair pair) { + storage.add(pair); + } + + @Override + public void sort() { + Collections.sort(storage, DistanceDBIDResultUtil.distanceComparator()); + } + + @Override + public int size() { + return storage.size(); + } + + @Override + public DoubleDistanceDBIDPair get(int off) { + return storage.get(off); + } + + @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 String toString() { + return DistanceDBIDResultUtil.toString(this); + } + + /** + * Iterator class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected class Itr implements DoubleDistanceDBIDListIter { + /** + * 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 + @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 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; + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/distance/DoubleDistanceKNNHeap.java b/src/de/lmu/ifi/dbs/elki/database/ids/distance/DoubleDistanceKNNHeap.java new file mode 100644 index 00000000..1e75f120 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/distance/DoubleDistanceKNNHeap.java @@ -0,0 +1,100 @@ +package de.lmu.ifi.dbs.elki.database.ids.distance; + +/* + 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.DBIDRef; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; + +/** + * Interface for kNN heaps storing double distances and DBIDs. + * + * @author Erich Schubert + */ +public interface DoubleDistanceKNNHeap extends KNNHeap<DoubleDistance> { + /** + * 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 + */ + void add(double distance, DBIDRef id); + + /** + * 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 + */ + @Deprecated + void add(Double distance, DBIDRef id); + + /** + * Add a distance-id pair to the heap unless the distance is too large. + * + * Use for existing pairs. + * + * @param e Existing distance pair + */ + void add(DoubleDistanceDBIDPair e); + + /** + * {@inheritDoc} + * + * @deprecated if you know your distances are double-valued, you should be + * using the primitive type. + */ + @Override + @Deprecated + void add(DoubleDistance dist, DBIDRef id); + + /** + * Get the distance to the k nearest neighbor, or maxdist otherwise. + * + * @return Maximum distance + */ + double doubleKNNDistance(); + + /** + * {@inheritDoc} + * + * @deprecated if you know your distances are double-valued, you should be + * using the primitive type. + */ + @Override + @Deprecated + DoubleDistance getKNNDistance(); + + @Override + DoubleDistanceDBIDPair poll(); + + @Override + DoubleDistanceDBIDPair peek(); + + @Override + DoubleDistanceKNNList toKNNList(); +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/distance/DoubleDistanceKNNList.java b/src/de/lmu/ifi/dbs/elki/database/ids/distance/DoubleDistanceKNNList.java new file mode 100644 index 00000000..c54110ab --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/distance/DoubleDistanceKNNList.java @@ -0,0 +1,55 @@ +package de.lmu.ifi.dbs.elki.database.ids.distance; + +/* + 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.distance.distancevalue.DoubleDistance; + +/** + * Double-valued KNN result. + * + * @author Erich Schubert + */ +public interface DoubleDistanceKNNList extends KNNList<DoubleDistance> { + /** + * {@inheritDoc} + * + * @deprecated use doubleKNNDistance()! + */ + @Override + @Deprecated + DoubleDistance getKNNDistance(); + + /** + * Get the kNN distance as double value. + * + * @return Distance + */ + double doubleKNNDistance(); + + @Override + DoubleDistanceDBIDListIter iter(); + + @Override + DoubleDistanceDBIDPair get(int off); +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/distance/KNNHeap.java b/src/de/lmu/ifi/dbs/elki/database/ids/distance/KNNHeap.java new file mode 100644 index 00000000..c02071e7 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/distance/KNNHeap.java @@ -0,0 +1,111 @@ +package de.lmu.ifi.dbs.elki.database.ids.distance; + +/* + 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.DBIDRef; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; + +/** + * Interface for kNN heaps. + * + * To instantiate, use: {@link de.lmu.ifi.dbs.elki.database.ids.DBIDUtil#newHeap}! + * + * @author Erich Schubert + * + * @apiviz.landmark + * + * @apiviz.uses KNNList - - «serializes to» + * @apiviz.composedOf DistanceDBIDPair + * + * @param <D> Distance function + */ +public interface KNNHeap<D extends Distance<D>> { + /** + * Serialize to a {@link KNNList}. This empties the heap! + * + * @return KNNList with the heaps contents. + */ + KNNList<D> toKNNList(); + + /** + * Get the K parameter ("maxsize" internally). + * + * @return K + */ + int getK(); + + /** + * Get the distance to the k nearest neighbor, or maxdist otherwise. + * + * @return Maximum distance + */ + D getKNNDistance(); + + /** + * 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 + */ + void add(D distance, DBIDRef id); + + /** + * Current size of heap. + * + * @return Heap size + */ + int size(); + + /** + * Test if the heap is empty. + * + * @return true when empty. + */ + boolean isEmpty(); + + /** + * Clear the heap. + */ + void clear(); + + /** + * Poll the <em>largest</em> element from the heap. + * + * This is in descending order because of the heap structure. For a convenient + * way to serialize the heap into a list that you can iterate in ascending + * order, see {@link #toKNNList()}. + * + * @return largest element + */ + DistanceDBIDPair<D> poll(); + + /** + * Peek at the <em>largest</em> element in the heap. + * + * @return The current largest element. + */ + DistanceDBIDPair<D> peek(); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/distance/KNNList.java b/src/de/lmu/ifi/dbs/elki/database/ids/distance/KNNList.java new file mode 100644 index 00000000..61b75ba8 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/distance/KNNList.java @@ -0,0 +1,89 @@ +package de.lmu.ifi.dbs.elki.database.ids.distance; + +/* + 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.distance.distancevalue.Distance; + +/** + * Interface for kNN results. + * + * To iterate over the results, use the following code: + * + * <pre> + * {@code + * for (DistanceDBIDResultIter<D> iter = result.iter(); iter.valid(); iter.advance()) { + * // You can get the distance via: iter.getDistance(); + * // Or use iter just like any other DBIDRef + * } + * } + * </pre> + * + * If you are only interested in the IDs of the objects, the following is also + * sufficient: + * + * <pre> + * {@code + * for (DBIDIter<D> iter = result.iter(); iter.valid(); iter.advance()) { + * // Use iter just like any other DBIDRef + * } + * } + * </pre> + * + * @author Erich Schubert + * + * @apiviz.landmark + * + * @apiviz.composedOf DistanceDBIDPair + * + * @param <D> Distance type + */ +public interface KNNList<D extends Distance<D>> extends DistanceDBIDList<D> { + /** + * Size + */ + @Override + public int size(); + + /** + * Get the K parameter (note: this may be less than the size of the list!) + * + * @return K + */ + public int getK(); + + /** + * Direct object access. + * + * @param index + */ + @Override + public DistanceDBIDPair<D> get(int index); + + /** + * Get the distance to the k nearest neighbor, or maxdist otherwise. + * + * @return Maximum distance + */ + public D getKNNDistance(); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/distance/ModifiableDistanceDBIDList.java b/src/de/lmu/ifi/dbs/elki/database/ids/distance/ModifiableDistanceDBIDList.java new file mode 100644 index 00000000..afb15f93 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/distance/ModifiableDistanceDBIDList.java @@ -0,0 +1,48 @@ +package de.lmu.ifi.dbs.elki.database.ids.distance; + +/* + 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.DBIDRef; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +/** + * Modifiable API for Distance-DBID results + * + * @author Erich Schubert + * + * @param <D> Distance type + */ +public interface ModifiableDistanceDBIDList<D extends Distance<D>> extends DistanceDBIDList<D> { + /** + * Add an object to this result. + * + * @param distance Distance to add + * @param id DBID to add + */ + public void add(D distance, DBIDRef id); + + /** + * Sort the result in ascending order + */ + public void sort(); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/distance/ModifiableDoubleDistanceDBIDList.java b/src/de/lmu/ifi/dbs/elki/database/ids/distance/ModifiableDoubleDistanceDBIDList.java new file mode 100644 index 00000000..12cdaf69 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/distance/ModifiableDoubleDistanceDBIDList.java @@ -0,0 +1,63 @@ +package de.lmu.ifi.dbs.elki.database.ids.distance; + +/* + 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.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.distance.ModifiableDistanceDBIDList; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; + +/** + * An object containing Double-DBID-Pairs. + * + * @author Erich Schubert + */ +public interface ModifiableDoubleDistanceDBIDList extends DoubleDistanceDBIDList, ModifiableDistanceDBIDList<DoubleDistance> { + /** + * Add an element. + * + * @deprecated Pass a double value instead. + * + * @param dist Distance + * @param id ID + */ + @Override + @Deprecated + void add(DoubleDistance dist, DBIDRef id); + + /** + * Add an element. + * + * @param dist Distance + * @param id ID + */ + void add(double dist, DBIDRef id); + + /** + * Add an element. + * + * @param pair Pair to add + */ + void add(DoubleDistanceDBIDPair pair); +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/distance/package-info.java b/src/de/lmu/ifi/dbs/elki/database/ids/distance/package-info.java new file mode 100644 index 00000000..7fefbedd --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/distance/package-info.java @@ -0,0 +1,26 @@ +/** + * Distance-DBID pairs, lists and heaps. + */ +/* + 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/>. + */ +package de.lmu.ifi.dbs.elki.database.ids.distance; |