diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/database/ids/integer')
33 files changed, 1669 insertions, 353 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/AbstractIntegerDBIDFactory.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/AbstractIntegerDBIDFactory.java new file mode 100644 index 00000000..061deb08 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/AbstractIntegerDBIDFactory.java @@ -0,0 +1,201 @@ +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) 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.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.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; +import de.lmu.ifi.dbs.elki.database.ids.DBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDPair; +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.database.ids.distance.KNNHeap; +import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList; +import de.lmu.ifi.dbs.elki.database.ids.generic.DistanceDBIDPairKNNHeap; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; +import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; +import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; + +/** + * Abstract base class for DBID factories. + * + * @author Erich Schubert + * + * @apiviz.uses IntegerDBID oneway - - «create» + * @apiviz.uses IntegerDBIDPair oneway - - «create» + * @apiviz.uses IntegerDBIDRange oneway - - «create» + * @apiviz.uses TroveArrayModifiableDBIDs oneway - - «create» + * @apiviz.uses TroveHashSetModifiableDBIDs oneway - - «create» + */ +abstract class AbstractIntegerDBIDFactory implements DBIDFactory { + /** + * Invalid ID. + */ + DBID invalid = new IntegerDBID(Integer.MIN_VALUE); + + @Override + public DBID importInteger(int id) { + return new IntegerDBID(id); + } + + @Override + public void assignVar(DBIDVar var, int val) { + if (var instanceof IntegerDBIDVar) { + ((IntegerDBIDVar)var).internalSetIndex(val); + } else { + var.set(new IntegerDBID(val)); + } + } + + @Override + public int compare(DBIDRef a, DBIDRef b) { + final int inta = a.internalGetIndex(); + final int intb = b.internalGetIndex(); + return (inta < intb ? -1 : (inta == intb ? 0 : 1)); + } + + @Override + public boolean equal(DBIDRef a, DBIDRef b) { + return a.internalGetIndex() == b.internalGetIndex(); + } + + @Override + public String toString(DBIDRef id) { + return Integer.toString(id.internalGetIndex()); + } + + @Override + public DBIDVar newVar(DBIDRef val) { + return new IntegerDBIDVar(val); + } + + @Override + public ArrayModifiableDBIDs newArray() { + return new ArrayModifiableIntegerDBIDs(); + } + + @Override + public HashSetModifiableDBIDs newHashSet() { + return new TroveHashSetModifiableDBIDs(); + } + + @Override + public ArrayModifiableDBIDs newArray(int size) { + return new ArrayModifiableIntegerDBIDs(size); + } + + @Override + public HashSetModifiableDBIDs newHashSet(int size) { + return new TroveHashSetModifiableDBIDs(size); + } + + @Override + public ArrayModifiableDBIDs newArray(DBIDs existing) { + return new ArrayModifiableIntegerDBIDs(existing); + } + + @Override + public HashSetModifiableDBIDs newHashSet(DBIDs existing) { + return new TroveHashSetModifiableDBIDs(existing); + } + + @Override + public DBIDPair newPair(DBIDRef first, DBIDRef second) { + return new IntegerDBIDPair(first.internalGetIndex(), second.internalGetIndex()); + } + + @Override + public DoubleDBIDPair newPair(double val, DBIDRef id) { + return new IntegerDoubleDBIDPair(val, id.internalGetIndex()); + } + + @SuppressWarnings("unchecked") + @Override + public <D extends Distance<D>> DistanceDBIDPair<D> newDistancePair(D val, DBIDRef id) { + if (val instanceof DoubleDistance) { + return (DistanceDBIDPair<D>) new DoubleDistanceIntegerDBIDPair(((DoubleDistance) val).doubleValue(), id.internalGetIndex()); + } + return new DistanceIntegerDBIDPair<>(val, id.internalGetIndex()); + } + + @Override + public DoubleDistanceDBIDPair newDistancePair(double val, DBIDRef id) { + return new DoubleDistanceIntegerDBIDPair(val, id.internalGetIndex()); + } + + @SuppressWarnings("unchecked") + @Override + public <D extends Distance<D>> KNNHeap<D> newHeap(D factory, int k) { + if (factory instanceof DoubleDistance) { + return (KNNHeap<D>) new DoubleDistanceIntegerDBIDKNNListHeap(k); + } + return new DistanceDBIDPairKNNHeap<>(k); + } + + @SuppressWarnings("unchecked") + @Override + public <D extends Distance<D>> KNNHeap<D> newHeap(KNNList<D> exist) { + if (exist instanceof DoubleDistanceKNNList) { + DoubleDistanceKNNHeap heap = new DoubleDistanceIntegerDBIDKNNListHeap(exist.getK()); + // Insert backwards, as this will produce a proper heap + for (int i = exist.size() - 1; i >= 0; i--) { + heap.add((DoubleDistanceDBIDPair) exist.get(i)); + } + return (KNNHeap<D>) heap; + } else { + DistanceDBIDPairKNNHeap<D> heap = new DistanceDBIDPairKNNHeap<>(exist.getK()); + // Insert backwards, as this will produce a proper heap + for (int i = exist.size() - 1; i >= 0; i--) { + heap.add(exist.get(i)); + } + return heap; + } + } + + @Override + public ByteBufferSerializer<DBID> getDBIDSerializer() { + return IntegerDBID.DYNAMIC_SERIALIZER; + } + + @Override + public FixedSizeByteBufferSerializer<DBID> getDBIDSerializerStatic() { + return IntegerDBID.STATIC_SERIALIZER; + } + + @Override + public Class<? extends DBID> getTypeRestriction() { + return IntegerDBID.class; + } + + @Override + public DBIDRef invalid() { + return invalid; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/ArrayModifiableIntegerDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/ArrayModifiableIntegerDBIDs.java new file mode 100644 index 00000000..dfff45b4 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/ArrayModifiableIntegerDBIDs.java @@ -0,0 +1,306 @@ +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) 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.ArrayModifiableDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; +import de.lmu.ifi.dbs.elki.database.ids.DBIDs; + +/** + * Class using a primitive int[] array as storage. + * + * @author Erich Schubert + */ +public class ArrayModifiableIntegerDBIDs implements ArrayModifiableDBIDs, IntegerArrayDBIDs { + /** + * The actual Trove array list. + */ + private int[] store; + + /** + * Occupied size. + */ + private int size = 0; + + /** + * Initial size. + */ + public static final int INITIAL_SIZE = 21; + + /** + * Constructor. + * + * @param size Initial size + */ + protected ArrayModifiableIntegerDBIDs(int size) { + super(); + this.store = new int[size]; + } + + /** + * Constructor. + */ + protected ArrayModifiableIntegerDBIDs() { + super(); + this.store = new int[INITIAL_SIZE]; + } + + /** + * Constructor. + * + * @param existing Existing ids + */ + protected ArrayModifiableIntegerDBIDs(DBIDs existing) { + this(existing.size()); + this.addDBIDs(existing); + } + + @Override + public int size() { + return size; + } + + @Override + public boolean isEmpty() { + return size == 0; + } + + @Override + public DBID get(int i) { + return new IntegerDBID(store[i]); + } + + @Override + public void assignVar(int index, DBIDVar var) { + if(var instanceof IntegerDBIDVar) { + ((IntegerDBIDVar) var).internalSetIndex(store[index]); + } + else { + // less efficient, involves object creation. + var.set(get(index)); + } + } + + /** + * Resize as desired. + * + * @param minsize Desired size + */ + private void ensureSize(int minsize) { + int asize = store.length; + // Ensure a minimum size, to not run into an infinite loop below! + if (asize < 2) { + asize = 2; + } + while(asize < minsize) { + asize = (asize >> 1) + asize; + } + if(asize > store.length) { + store = Arrays.copyOf(store, asize); + } + } + + @Override + public boolean addDBIDs(DBIDs ids) { + ensureSize(size + ids.size()); + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + store[size] = iter.internalGetIndex(); + ++size; + } + return true; + } + + @Override + public boolean removeDBIDs(DBIDs ids) { + boolean success = false; + for(DBIDIter id = ids.iter(); id.valid(); id.advance()) { + int rm = id.internalGetIndex(); + // TODO: when sorted, use binary search! + for(int i = 0; i < size; i++) { + if(store[i] == rm) { + --size; + store[i] = store[size]; + success = true; + break; + } + } + } + return success; + } + + @Override + public boolean add(DBIDRef e) { + if(size == store.length) { + ensureSize(size + 1); + } + store[size] = e.internalGetIndex(); + ++size; + return true; + } + + @Override + public boolean remove(DBIDRef o) { + int rm = o.internalGetIndex(); + // TODO: when sorted, use binary search! + for(int i = 0; i < size; i++) { + if(store[i] == rm) { + --size; + store[i] = store[size]; + return true; + } + } + return false; + } + + @Override + public DBID set(int index, DBIDRef element) { + int prev = store[index]; + store[index] = element.internalGetIndex(); + return new IntegerDBID(prev); + } + + @Override + public DBID remove(int index) { + DBID ret = new IntegerDBID(store[index]); + --size; + if(size > 0) { + store[index] = store[size]; + } + return ret; + } + + @Override + public void clear() { + size = 0; + } + + @Override + public int binarySearch(DBIDRef key) { + return Arrays.binarySearch(store, 0, size, key.internalGetIndex()); + } + + @Override + public boolean contains(DBIDRef o) { + // TODO: recognize sorted arrays, then use binary search? + int oid = o.internalGetIndex(); + for(int i = 0; i < size; i++) { + if(store[i] == oid) { + return true; + } + } + return false; + } + + @Override + public void sort() { + Arrays.sort(store, 0, size); + } + + @Override + public void sort(Comparator<? super DBIDRef> comparator) { + IntegerDBIDArrayQuickSort.sort(store, 0, size, comparator); + } + + @Override + public void sort(int start, int end, Comparator<? super DBIDRef> comparator) { + IntegerDBIDArrayQuickSort.sort(store, start, end, comparator); + } + + @Override + public void swap(int a, int b) { + int tmp = store[b]; + store[b] = store[a]; + store[a] = tmp; + } + + @Override + public IntegerDBIDArrayMIter iter() { + return new Itr(); + } + + /** + * Iterator class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + private class Itr implements IntegerDBIDArrayMIter { + /** + * Iterator position. + */ + int pos = 0; + + @Override + public int internalGetIndex() { + return store[pos]; + } + + @Override + public boolean valid() { + return pos < size && pos >= 0; + } + + @Override + public void advance() { + ++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; + } + + @Override + public void remove() { + ArrayModifiableIntegerDBIDs.this.remove(pos); + } + + @Override + public String toString() { + return Integer.toString(internalGetIndex()) + "@" + pos; + } + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntArrayStaticDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/ArrayStaticIntegerDBIDs.java index aa3b3cc0..4b4b5a42 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntArrayStaticDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/ArrayStaticIntegerDBIDs.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) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -39,7 +39,7 @@ import de.lmu.ifi.dbs.elki.logging.LoggingUtil; * * @apiviz.has IntegerDBID */ -public class IntArrayStaticDBIDs implements IntegerArrayStaticDBIDs { +public class ArrayStaticIntegerDBIDs implements IntegerArrayStaticDBIDs { /** * The actual storage. */ @@ -50,7 +50,7 @@ public class IntArrayStaticDBIDs implements IntegerArrayStaticDBIDs { * * @param ids Array of ids. */ - public IntArrayStaticDBIDs(int... ids) { + public ArrayStaticIntegerDBIDs(int... ids) { super(); this.ids = ids; } @@ -118,7 +118,7 @@ public class IntArrayStaticDBIDs implements IntegerArrayStaticDBIDs { @Override public String toString() { - return Integer.toString(internalGetIndex()); + return Integer.toString(internalGetIndex()) + "@" + pos; } } @@ -149,7 +149,7 @@ public class IntArrayStaticDBIDs implements IntegerArrayStaticDBIDs { } @Override - public void assign(int i, DBIDVar var) { + public void assignVar(int i, DBIDVar var) { if (var instanceof IntegerDBIDVar) { ((IntegerDBIDVar)var).internalSetIndex(ids[i]); } else { diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DistanceIntegerDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DistanceIntegerDBIDPair.java index 01eec02e..a8930b87 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DistanceIntegerDBIDPair.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DistanceIntegerDBIDPair.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) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,9 +23,10 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.database.ids.DistanceDBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDPair; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; +import de.lmu.ifi.dbs.elki.utilities.Util; /** * Class storing a double distance a DBID. @@ -88,8 +89,13 @@ class DistanceIntegerDBIDPair<D extends Distance<D>> implements DistanceDBIDPair } if (o instanceof DoubleDistanceIntegerDBIDPair && distance instanceof DoubleDistance) { DoubleDistanceIntegerDBIDPair p = (DoubleDistanceIntegerDBIDPair) o; - return (this.id == p.id) && (((DoubleDistance) this.distance).doubleValue() == p.distance); + return (this.id == p.id) && (Double.compare(((DoubleDistance) this.distance).doubleValue(), p.distance) == 0); } return false; } + + @Override + public int hashCode() { + return Util.mixHashCodes(distance.hashCode(), id); + } } diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNHeap.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNHeap.java new file mode 100644 index 00000000..6c88c2d8 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNHeap.java @@ -0,0 +1,252 @@ +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) 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.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; +import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.DoubleIntegerMaxHeap; + +/** + * Class to efficiently manage a kNN heap. + * + * @author Erich Schubert + * + * @apiviz.has DoubleDistanceIntegerDBIDKNNList + * @apiviz.composedOf DoubleIntegerMaxHeap + */ +public class DoubleDistanceIntegerDBIDKNNHeap implements DoubleDistanceKNNHeap { + /** + * k for this heap. + */ + private final int k; + + /** + * The main heap. + */ + private final DoubleIntegerMaxHeap heap; + + /** + * List to track ties. + */ + private int[] ties; + + /** + * Number of element in ties list. + */ + private int numties = 0; + + /** + * Current maximum value. + */ + private double kdist = Double.POSITIVE_INFINITY; + + /** + * Initial size of ties array. + */ + private static final int INITIAL_TIES_SIZE = 11; + + /** + * Constructor. + * + * @param k Size of knn. + */ + public DoubleDistanceIntegerDBIDKNNHeap(int k) { + super(); + this.k = k; + this.heap = new DoubleIntegerMaxHeap(k); + this.ties = new int[INITIAL_TIES_SIZE]; + } + + @Override + public int getK() { + return k; + } + + @Override + @Deprecated + public DoubleDistance getKNNDistance() { + if (heap.size() < k) { + return DoubleDistance.INFINITE_DISTANCE; + } + return new DoubleDistance(kdist); + } + + @Override + public double doubleKNNDistance() { + return kdist; + } + + @Override + @Deprecated + public void add(DoubleDistance distance, DBIDRef id) { + add(distance.doubleValue(), id); + } + + @Override + @Deprecated + public void add(Double distance, DBIDRef id) { + add(distance.doubleValue(), id); + } + + @Override + public final void add(final double distance, final DBIDRef id) { + if (distance > kdist) { + return; + } + final int iid = id.internalGetIndex(); + if (heap.size() < k) { + heap.add(distance, iid); + if (heap.size() >= k) { + kdist = heap.peekKey(); + } + return; + } + // Tied with top: + if (distance >= kdist) { + addToTies(iid); + return; + } + // Old top element: (kdist, previd) + updateHeap(distance, iid); + } + + @Override + public void add(DoubleDistanceDBIDPair e) { + add(e.doubleDistance(), e); + } + + /** + * Do a full update for the heap. + * + * @param distance Distance + * @param iid Object id + */ + private final void updateHeap(final double distance, final int iid) { + final double prevdist = kdist; + final int previd = heap.peekValue(); + heap.replaceTopElement(distance, iid); + kdist = heap.peekKey(); + // If the kdist improved, zap ties. + if (kdist < prevdist) { + numties = 0; + } else { + addToTies(previd); + } + } + + /** + * Ensure the ties array has capacity for at least one more element. + * + * @param id Id to add + */ + private final void addToTies(int id) { + if (ties.length == numties) { + ties = Arrays.copyOf(ties, (ties.length << 1) + 1); // grow. + } + ties[numties] = id; + ++numties; + } + + @Override + public DoubleDistanceIntegerDBIDPair poll() { + final DoubleDistanceIntegerDBIDPair ret; + if (numties > 0) { + ret = new DoubleDistanceIntegerDBIDPair(kdist, ties[numties - 1]); + --numties; + } else { + ret = new DoubleDistanceIntegerDBIDPair(heap.peekKey(), heap.peekValue()); + heap.poll(); + } + return ret; + } + + /** + * Pop the topmost element. + */ + protected void pop() { + if (numties > 0) { + --numties; + } else { + heap.poll(); + } + } + + @Override + public DoubleDistanceIntegerDBIDPair peek() { + if (numties > 0) { + return new DoubleDistanceIntegerDBIDPair(kdist, ties[numties - 1]); + } + return new DoubleDistanceIntegerDBIDPair(heap.peekKey(), heap.peekValue()); + } + + @Override + public int size() { + return heap.size() + numties; + } + + @Override + public boolean isEmpty() { + return heap.size() == 0; + } + + @Override + public void clear() { + heap.clear(); + numties = 0; + } + + @Override + public DoubleDistanceIntegerDBIDKNNList toKNNList() { + return new DoubleDistanceIntegerDBIDKNNList(this); + } + + /** + * Peek the topmost distance. + * + * @return distance + */ + protected double peekDistance() { + if (numties > 0) { + return kdist; + } else { + return heap.peekKey(); + } + } + + /** + * Peek the topmost internal ID. + * + * @return internal id + */ + protected int peekInternalDBID() { + if (numties > 0) { + return ties[numties - 1]; + } + return heap.peekValue(); + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNList.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNList.java new file mode 100644 index 00000000..a74497e8 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNList.java @@ -0,0 +1,298 @@ +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) 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.DBIDRef; +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.ModifiableDoubleDistanceDBIDList; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; + +/** + * Class to store double distance, integer DBID results. + * + * @author Erich Schubert + * + * @apiviz.uses DoubleIntegerArrayQuickSort + */ +public class DoubleDistanceIntegerDBIDKNNList implements ModifiableDoubleDistanceDBIDList, DoubleDistanceKNNList, IntegerDBIDs { + /** + * Initial size allocation. + */ + private static final int INITIAL_SIZE = 21; + + /** + * The k value this list was generated for. + */ + int k; + + /** + * The size + */ + int size; + + /** + * Distance values + */ + double[] dists; + + /** + * DBIDs + */ + int[] ids; + + /** + * Constructor. + */ + public DoubleDistanceIntegerDBIDKNNList() { + super(); + this.k = -1; + this.dists = new double[INITIAL_SIZE]; + this.ids = new int[INITIAL_SIZE]; + } + + /** + * Constructor. + * + * @param k K parameter + * @param size Actual size + */ + public DoubleDistanceIntegerDBIDKNNList(int k, int size) { + super(); + this.k = k; + if (size > 0) { + this.dists = new double[size]; + this.ids = new int[size]; + } else { + this.dists = new double[INITIAL_SIZE]; + this.ids = new int[INITIAL_SIZE]; + } + } + + /** + * Constructor from heap. + * + * @param heap KNN heap. + */ + public DoubleDistanceIntegerDBIDKNNList(DoubleDistanceIntegerDBIDKNNHeap heap) { + super(); + this.k = heap.getK(); + this.size = heap.size(); + this.dists = new double[size]; + this.ids = new int[size]; + for (int i = size - 1; i >= 0; i--) { + dists[i] = heap.peekDistance(); + ids[i] = heap.peekInternalDBID(); + heap.pop(); + } + } + + @Override + public DoubleDistanceIntegerDBIDListIter iter() { + return new Itr(); + } + + @Override + public boolean contains(DBIDRef o) { + final int q = o.internalGetIndex(); + for (int i = 0; i < size; i++) { + if (q == ids[i]) { + return true; + } + } + return false; + } + + @Override + public boolean isEmpty() { + return size == 0; + } + + @Override + public int size() { + return size; + } + + @Override + public int getK() { + if (k <= 0) { + return size - 1; + } + return k; + } + + @Override + public DoubleDistanceIntegerDBIDPair get(int index) { + return new DoubleDistanceIntegerDBIDPair(dists[index], ids[index]); + } + + @Override + @Deprecated + public DoubleDistance getKNNDistance() { + return new DoubleDistance(doubleKNNDistance()); + } + + @Override + public double doubleKNNDistance() { + if (k <= 0) { + return dists[size - 1]; + } + if (size < k) { + return Double.POSITIVE_INFINITY; + } + return dists[k - 1]; + } + + /** + * Add an entry, consisting of distance and internal index. + * + * @param dist Distance + * @param id Internal index + */ + protected void add(double dist, int id) { + if (size == dists.length) { + final int newlength = (dists.length << 1) + 1; + dists = Arrays.copyOf(dists, newlength); + ids = Arrays.copyOf(ids, newlength); + } + dists[size] = dist; + ids[size] = id; + ++size; + } + + @Override + @Deprecated + public void add(DoubleDistance dist, DBIDRef id) { + add(dist.doubleValue(), id); + } + + @Override + public void add(double dist, DBIDRef id) { + add(dist, id.internalGetIndex()); + } + + @Override + public void add(DoubleDistanceDBIDPair pair) { + add(pair.doubleDistance(), pair.internalGetIndex()); + } + + @Override + public void sort() { + DoubleIntegerArrayQuickSort.sort(dists, ids, 0, size); + } + + /** + * Reverse the list. + */ + protected void reverse() { + for (int i = 0, j = size - 1; i < j; i++, j--) { + double tmpd = dists[j]; + dists[j] = dists[i]; + dists[i] = tmpd; + int tmpi = ids[j]; + ids[j] = ids[i]; + ids[i] = tmpi; + } + } + + @Override + public String toString() { + StringBuilder buf = new StringBuilder(); + buf.append("kNNList["); + for (DoubleDistanceDBIDListIter iter = this.iter(); iter.valid();) { + buf.append(iter.doubleDistance()).append(':').append(iter.internalGetIndex()); + iter.advance(); + if (iter.valid()) { + buf.append(','); + } + } + buf.append(']'); + return buf.toString(); + } + + /** + * List iterator. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + private class Itr implements DoubleDistanceIntegerDBIDListIter { + int offset = 0; + + @Override + public boolean valid() { + return offset < size; + } + + @Override + public void advance() { + ++offset; + } + + @Override + public int getOffset() { + return offset; + } + + @Override + public void advance(int count) { + offset += count; + } + + @Override + public void retract() { + offset--; + } + + @Override + public void seek(int off) { + offset = off; + } + + @Override + public int internalGetIndex() { + return ids[offset]; + } + + @Override + public double doubleDistance() { + return dists[offset]; + } + + @Override + public DoubleDistanceDBIDPair getDistancePair() { + return new DoubleDistanceIntegerDBIDPair(dists[offset], ids[offset]); + } + + @Override + @Deprecated + public DoubleDistance getDistance() { + return new DoubleDistance(dists[offset]); + } + + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNListHeap.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNListHeap.java new file mode 100644 index 00000000..ffc2266e --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDKNNListHeap.java @@ -0,0 +1,315 @@ +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) 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.DBIDRef; +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; + +/** + * Class to store double distance, integer DBID results. + * + * @author Erich Schubert + * + * @apiviz.uses DoubleIntegerArrayQuickSort + */ +public class DoubleDistanceIntegerDBIDKNNListHeap implements DoubleDistanceKNNHeap, DoubleDistanceKNNList, IntegerDBIDs { + /** + * The k value this list was generated for. + */ + int k; + + /** + * The size + */ + int size; + + /** + * Distance values + */ + double[] dists; + + /** + * DBIDs + */ + int[] ids; + + /** + * Constructor. + * + * @param k K parameter + */ + public DoubleDistanceIntegerDBIDKNNListHeap(int k) { + super(); + this.k = k; + this.size = 0; + this.dists = new double[k + 1]; + this.ids = new int[k + 1]; + } + + @Override + public DoubleDistanceIntegerDBIDListIter iter() { + return new Itr(); + } + + @Override + public boolean contains(DBIDRef o) { + final int q = o.internalGetIndex(); + for(int i = 0; i < size; i++) { + if(q == ids[i]) { + return true; + } + } + return false; + } + + @Override + public boolean isEmpty() { + return size == 0; + } + + @Override + public int size() { + return size; + } + + @Override + public int getK() { + return k; + } + + @Override + public DoubleDistanceIntegerDBIDPair get(int index) { + return new DoubleDistanceIntegerDBIDPair(dists[index], ids[index]); + } + + @Override + @Deprecated + public DoubleDistance getKNNDistance() { + return new DoubleDistance(doubleKNNDistance()); + } + + @Override + public double doubleKNNDistance() { + if(size < k) { + return Double.POSITIVE_INFINITY; + } + return dists[k - 1]; + } + + /** + * Add an entry, consisting of distance and internal index. + * + * @param dist Distance + * @param id Internal index + */ + protected void append(double dist, int id) { + ensureSize(size + 1); + dists[size] = dist; + ids[size] = id; + ++size; + } + + /** + * Add a new element to the heap/list. + * + * @param dist Distance + * @param id Object ID + */ + protected void add(double dist, int id) { + if(size < k) { + dists[size] = dist; + ids[size] = id; + ++size; + if(size == k) { + sort(); + } + return; + } + if (dist > dists[size - 1]) { + return; + } + // Ensure we have enough space. + ensureSize(size + 1); + // Insertion sort: + int pos = size; + while(pos > 0 && dists[pos - 1] > dist) { + dists[pos] = dists[pos - 1]; + ids[pos] = ids[pos - 1]; + --pos; + } + dists[pos] = dist; + ids[pos] = id; + ++size; + // Truncate if necessary: + if(dists[k] > dists[k - 1]) { + size = k; + } + } + + /** + * Ensure we have enough space. + * + * @param size Desired size + */ + private void ensureSize(int size) { + if(size > dists.length) { + final int newlength = Math.max(size, (dists.length << 1) + 1); + dists = Arrays.copyOf(dists, newlength); + ids = Arrays.copyOf(ids, newlength); + } + } + + @Override + @Deprecated + public void add(DoubleDistance dist, DBIDRef id) { + add(dist.doubleValue(), id); + } + + @Override + @Deprecated + public void add(Double dist, DBIDRef id) { + add(dist.doubleValue(), id); + } + + @Override + public void add(double dist, DBIDRef id) { + add(dist, id.internalGetIndex()); + } + + @Override + public void add(DoubleDistanceDBIDPair pair) { + add(pair.doubleDistance(), pair.internalGetIndex()); + } + + /** + * Sort the current contents of the list. + */ + protected void sort() { + DoubleIntegerArrayQuickSort.sort(dists, ids, 0, size); + } + + @Override + public void clear() { + size = 0; + Arrays.fill(dists, Double.NaN); + Arrays.fill(ids, -1); + } + + @Override + public DoubleDistanceIntegerDBIDPair poll() { + return new DoubleDistanceIntegerDBIDPair(dists[k], ids[k]); + } + + @Override + public DoubleDistanceIntegerDBIDPair peek() { + return new DoubleDistanceIntegerDBIDPair(dists[k], ids[k]); + } + + @Override + public DoubleDistanceKNNList toKNNList() { + return this; + } + + @Override + public String toString() { + StringBuilder buf = new StringBuilder(); + buf.append("kNNListHeap["); + for(DoubleDistanceDBIDListIter iter = this.iter(); iter.valid();) { + buf.append(iter.doubleDistance()).append(':').append(iter.internalGetIndex()); + iter.advance(); + if(iter.valid()) { + buf.append(','); + } + } + buf.append(']'); + return buf.toString(); + } + + /** + * List iterator. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + private class Itr implements DoubleDistanceIntegerDBIDListIter { + int offset = 0; + + @Override + public boolean valid() { + return offset < size; + } + + @Override + public void advance() { + ++offset; + } + + @Override + public int getOffset() { + return offset; + } + + @Override + public void advance(int count) { + offset += count; + } + + @Override + public void retract() { + offset--; + } + + @Override + public void seek(int off) { + offset = off; + } + + @Override + public int internalGetIndex() { + return ids[offset]; + } + + @Override + public double doubleDistance() { + return dists[offset]; + } + + @Override + public DoubleDistanceDBIDPair getDistancePair() { + return new DoubleDistanceIntegerDBIDPair(dists[offset], ids[offset]); + } + + @Override + @Deprecated + public DoubleDistance getDistance() { + return new DoubleDistance(dists[offset]); + } + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDListIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDListIter.java new file mode 100644 index 00000000..0df81929 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDListIter.java @@ -0,0 +1,34 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 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.DoubleDistanceDBIDListIter; + +/** + * Combination interface. + * + * @author Erich Schubert + */ +public interface DoubleDistanceIntegerDBIDListIter extends DoubleDistanceDBIDListIter, IntegerDBIDArrayIter { + // Yet another painful combination interface. +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDPair.java index 8334d2e3..1f3b2a45 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDPair.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDPair.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) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -22,9 +22,10 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; You should have received a copy of the GNU Affero General Public License along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import de.lmu.ifi.dbs.elki.database.ids.DistanceDBIDPair; -import de.lmu.ifi.dbs.elki.database.ids.DoubleDistanceDBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDPair; import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; +import de.lmu.ifi.dbs.elki.utilities.Util; /** * Class storing a double distance a DBID. @@ -90,14 +91,20 @@ class DoubleDistanceIntegerDBIDPair implements DoubleDistanceDBIDPair, IntegerDB } if (o instanceof DoubleDistanceIntegerDBIDPair) { DoubleDistanceIntegerDBIDPair p = (DoubleDistanceIntegerDBIDPair) o; - return (this.id == p.id) && (this.distance == p.distance); + return (this.id == p.id) && (Double.compare(this.distance, p.distance) == 0); } if (o instanceof DistanceIntegerDBIDPair) { DistanceIntegerDBIDPair<?> p = (DistanceIntegerDBIDPair<?>) o; if (p.distance instanceof DoubleDistance) { - return (this.id == p.id) && (this.distance == ((DoubleDistance) p.distance).doubleValue()); + return (this.id == p.id) && (Double.compare(this.distance, ((DoubleDistance) p.distance).doubleValue()) == 0); } } return false; } + + @Override + public int hashCode() { + long bits = Double.doubleToLongBits(distance); + return Util.mixHashCodes((int) (bits ^ (bits >>> 32)), id); + } } diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleIntegerArrayQuickSort.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleIntegerArrayQuickSort.java new file mode 100644 index 00000000..8f1c58d6 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleIntegerArrayQuickSort.java @@ -0,0 +1,181 @@ +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) 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/>. + */ + +/** + * Class to sort a double and an integer DBID array, using a quicksort with a + * best of 5 heuristic. + * + * @author Erich Schubert + */ +class DoubleIntegerArrayQuickSort { + /** + * Threshold for using insertion sort. + */ + private static final int INSERTION_THRESHOLD = 22; + + /** + * Sort the full array using the given comparator. + * + * @param keys Keys for sorting + * @param values Values for sorting + * @param len Length to sort. + */ + public static void sort(double[] keys, int[] values, int len) { + sort(keys, values, 0, len); + } + + /** + * Sort the array using the given comparator. + * + * @param keys Keys for sorting + * @param values Values for sorting + * @param start First index + * @param end Last index (exclusive) + */ + public static void sort(double[] keys, int[] values, int start, int end) { + quickSort(keys, values, start, end); + } + + /** + * Actual recursive sort function. + * + * @param keys Keys for sorting + * @param vals Values for sorting + * @param start First index + * @param end Last index (exclusive!) + */ + private static void quickSort(double[] keys, int[] vals, final int start, final int end) { + final int len = end - start; + if (len < INSERTION_THRESHOLD) { + // Classic insertion sort. + for (int i = start + 1; i < end; i++) { + for (int j = i; j > start; j--) { + if (keys[j] < keys[j - 1]) { + swap(keys, vals, j, j - 1); + } else { + break; + } + } + } + return; + } + + // Choose pivots by looking at five candidates. + final int seventh = (len >> 3) + (len >> 6) + 1; + final int m3 = (start + end) >> 1; // middle + final int m2 = m3 - seventh; + final int m1 = m2 - seventh; + final int m4 = m3 + seventh; + final int m5 = m4 + seventh; + + // Mixture of insertion and merge sort: + if (keys[m1] > keys[m2]) { + swap(keys, vals, m1, m2); + } + if (keys[m3] > keys[m4]) { + swap(keys, vals, m3, m4); + } + // Merge 1+2 and 3+4 + if (keys[m2] > keys[m4]) { + swap(keys, vals, m2, m4); + } + if (keys[m1] > keys[m3]) { + swap(keys, vals, m1, m3); + } + if (keys[m2] > keys[m3]) { + swap(keys, vals, m2, m3); + } + // Insertion sort m5: + if (keys[m4] > keys[m5]) { + swap(keys, vals, m4, m5); + if (keys[m3] > keys[m4]) { + swap(keys, vals, m3, m4); + if (keys[m2] > keys[m3]) { + swap(keys, vals, m2, m3); + if (keys[m1] > keys[m1]) { + swap(keys, vals, m1, m2); + } + } + } + } + + // Move pivot to the front. + double pivotkey = keys[m3]; + int pivotval = vals[m3]; + keys[m3] = keys[start]; + vals[m3] = vals[start]; + + // The interval to pivotize + int left = start + 1; + int right = end - 1; + + // This is the classic QuickSort loop: + while (true) { + while (left <= right && keys[left] <= pivotkey) { + left++; + } + while (left <= right && pivotkey <= keys[right]) { + right--; + } + if (right <= left) { + break; + } + swap(keys, vals, left, right); + left++; + right--; + } + + // Move pivot back into the appropriate place + keys[start] = keys[right]; + vals[start] = vals[right]; + keys[right] = pivotkey; + vals[right] = pivotval; + + // Recursion: + if (start + 1 < right) { + quickSort(keys, vals, start, right); + } + if (right + 2 < end) { + quickSort(keys, vals, right + 1, end); + } + } + + /** + * Swap two entries. + * + * @param keys Keys + * @param vals Values + * @param j First index + * @param i Second index + */ + private static void swap(double[] keys, int[] vals, int j, int i) { + double td = keys[j]; + keys[j] = keys[i]; + keys[i] = td; + int ti = vals[j]; + vals[j] = vals[i]; + vals[i] = ti; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayStaticDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayDBIDs.java index 60dd50eb..61a12b3f 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayStaticDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayDBIDs.java @@ -1,9 +1,10 @@ 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 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -22,31 +23,14 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; 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.ArrayDBIDs; /** - * Class accessing a trove int array. + * Trivial combination interface. * * @author Erich Schubert */ -class TroveArrayStaticDBIDs extends TroveArrayDBIDs implements IntegerArrayStaticDBIDs { - /** - * Actual trove store. - */ - private final TIntList store; - - /** - * Constructor. - * - * @param store Actual trove store. - */ - protected TroveArrayStaticDBIDs(TIntList store) { - super(); - this.store = store; - } - +public interface IntegerArrayDBIDs extends IntegerDBIDs, ArrayDBIDs { @Override - protected TIntList getStore() { - return store; - } + IntegerDBIDArrayIter iter(); } 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 4bafd343..9e18631b 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) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -29,9 +29,8 @@ import de.lmu.ifi.dbs.elki.database.ids.ArrayStaticDBIDs; * Combination of {@link ArrayStaticDBIDs} and {@link IntegerDBIDs}. * * @author Erich Schubert - * */ -public interface IntegerArrayStaticDBIDs extends ArrayStaticDBIDs, IntegerDBIDs { +public interface IntegerArrayStaticDBIDs extends ArrayStaticDBIDs, IntegerArrayDBIDs { @Override IntegerDBIDArrayIter iter(); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java index 91c00939..40243695 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) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -133,7 +133,7 @@ final class IntegerDBID implements DBID, IntegerDBIDRef { } @Override - public void assign(int index, DBIDVar var) { + public void assignVar(int index, DBIDVar var) { if (index != 0) { throw new ArrayIndexOutOfBoundsException(); } diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayIter.java index b0e2d339..c604ac71 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayIter.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayIter.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) 2012 + Copyright (C) 2013 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/IntegerDBIDArrayMIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayMIter.java index 21616f75..dcead6bd 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayMIter.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayMIter.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) 2012 + Copyright (C) 2013 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/IntegerDBIDArrayQuickSort.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayQuickSort.java index 2c096ab9..90a97609 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayQuickSort.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayQuickSort.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) 2012 + Copyright (C) 2013 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/IntegerDBIDIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDIter.java index 9b50d544..cc241475 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDIter.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDIter.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) 2012 + Copyright (C) 2013 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/IntegerDBIDMIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDMIter.java index 2e339dbc..c0291d5b 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDMIter.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDMIter.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) 2012 + Copyright (C) 2013 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/IntegerDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDPair.java index e716f5b5..1b1ab154 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) 2012 + Copyright (C) 2013 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/IntegerDBIDRange.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java index 85c47f43..3ceb163d 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) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -189,7 +189,7 @@ class IntegerDBIDRange implements DBIDRange { } @Override - public void assign(int index, DBIDVar var) { + public void assignVar(int index, DBIDVar var) { if (var instanceof IntegerDBIDVar) { ((IntegerDBIDVar)var).internalSetIndex(start + index); } else { diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRef.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRef.java index 45854440..dc63b117 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRef.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRef.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) 2012 + Copyright (C) 2013 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/IntegerDBIDVar.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDVar.java index 73d164e0..57d400df 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDVar.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDVar.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) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -24,7 +24,6 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; */ import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.DBIDArrayIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; import de.lmu.ifi.dbs.elki.logging.LoggingUtil; @@ -38,7 +37,7 @@ import de.lmu.ifi.dbs.elki.logging.LoggingUtil; * * @author Erich Schubert */ -class IntegerDBIDVar implements DBIDVar { +class IntegerDBIDVar implements DBIDVar, IntegerDBIDs { /** * The actual value. */ @@ -88,7 +87,7 @@ class IntegerDBIDVar implements DBIDVar { } @Override - public DBIDArrayIter iter() { + public IntegerDBIDArrayIter iter() { return new DBIDItr(); } @@ -115,7 +114,7 @@ class IntegerDBIDVar implements DBIDVar { * * @apiviz.exclude */ - protected class DBIDItr implements DBIDArrayIter, IntegerDBIDRef { + protected class DBIDItr implements IntegerDBIDArrayIter, IntegerDBIDRef { /** * Iterator position: We use an integer so we can support retract(). */ @@ -182,15 +181,15 @@ class IntegerDBIDVar implements DBIDVar { } @Override - public void assign(int i, DBIDVar var) { + public void assignVar(int i, DBIDVar var) { if (var instanceof IntegerDBIDVar) { - ((IntegerDBIDVar)var).internalSetIndex(i); + ((IntegerDBIDVar) var).internalSetIndex(i); } else { // Much less efficient: var.set(get(i)); } } - + @Override public String toString() { return Integer.toString(id); diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDs.java index 8ffb9c6b..4acf91e6 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDs.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) 2012 + Copyright (C) 2013 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/IntegerDoubleDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDoubleDBIDPair.java index fe8c6a60..b522ffb2 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDoubleDBIDPair.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDoubleDBIDPair.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) 2012 + Copyright (C) 2013 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/ReusingDBIDFactory.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/ReusingDBIDFactory.java index f6df2e0d..ebb36f22 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) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -33,14 +33,15 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.logging.Logging; /** - * Slightly more advanced DBID management, that allows reuse of DBIDs. + * Slightly more complex DBID management, that allows reuse of DBIDs. + * + * NOT tested a lot yet. Not reusing is much simpler! + * + * TODO: manage fragmentation of ranges? * * @author Erich Schubert * * @apiviz.stereotype factory - * @apiviz.uses IntegerDBID oneway - - «create» - * @apiviz.uses IntegerDBIDPair oneway - - «create» - * @apiviz.uses IntegerDBIDRange oneway - - «create» */ public class ReusingDBIDFactory extends SimpleDBIDFactory { /** @@ -64,7 +65,7 @@ public class ReusingDBIDFactory extends SimpleDBIDFactory { /** * Returned range allocations */ - ArrayList<IntegerDBIDRange> returnedAllocations = new ArrayList<IntegerDBIDRange>(); + ArrayList<IntegerDBIDRange> returnedAllocations = new ArrayList<>(); /** * Constructor @@ -115,7 +116,6 @@ public class ReusingDBIDFactory extends SimpleDBIDFactory { @Override public synchronized void deallocateDBIDRange(DBIDRange range) { - // TODO: catch an eventual cast exception? returnedAllocations.add((IntegerDBIDRange) range); } } 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 77c1a91b..c3abd43a 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) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -23,22 +23,9 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -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.DBIDRef; -import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; -import de.lmu.ifi.dbs.elki.database.ids.DBIDs; -import de.lmu.ifi.dbs.elki.database.ids.DistanceDBIDPair; -import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDPair; -import de.lmu.ifi.dbs.elki.database.ids.DoubleDistanceDBIDPair; -import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; -import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; -import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; /** @@ -50,13 +37,8 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; * * @apiviz.landmark * @apiviz.stereotype factory - * @apiviz.uses IntegerDBID oneway - - «create» - * @apiviz.uses IntegerDBIDPair oneway - - «create» - * @apiviz.uses IntegerDBIDRange oneway - - «create» - * @apiviz.uses TroveArrayModifiableDBIDs oneway - - «create» - * @apiviz.uses TroveHashSetModifiableDBIDs oneway - - «create» */ -public class SimpleDBIDFactory implements DBIDFactory { +public class SimpleDBIDFactory extends AbstractIntegerDBIDFactory { /** * Keep track of the smallest dynamic DBID offset not used. */ @@ -68,11 +50,6 @@ public class SimpleDBIDFactory implements DBIDFactory { int rangestart = 0; /** - * Invalid ID. - */ - DBID invalid = new IntegerDBID(Integer.MIN_VALUE); - - /** * Constructor. */ public SimpleDBIDFactory() { @@ -81,10 +58,10 @@ public class SimpleDBIDFactory implements DBIDFactory { @Override public synchronized DBID generateSingleDBID() { + dynamicids--; if(dynamicids == Integer.MIN_VALUE) { throw new AbortException("DBID range allocation error - too many objects allocated!"); } - dynamicids--; return new IntegerDBID(dynamicids); } @@ -107,114 +84,4 @@ public class SimpleDBIDFactory implements DBIDFactory { public void deallocateDBIDRange(DBIDRange range) { // ignore. } - - @Override - public DBID importInteger(int id) { - return new IntegerDBID(id); - } - - @Override - public void assignVar(DBIDVar var, int val) { - if (var instanceof IntegerDBIDVar) { - ((IntegerDBIDVar)var).internalSetIndex(val); - } else { - var.set(new IntegerDBID(val)); - } - } - - @Override - public int compare(DBIDRef a, DBIDRef b) { - final int inta = a.internalGetIndex(); - final int intb = b.internalGetIndex(); - return (inta < intb ? -1 : (inta == intb ? 0 : 1)); - } - - @Override - public boolean equal(DBIDRef a, DBIDRef b) { - return a.internalGetIndex() == b.internalGetIndex(); - } - - @Override - public String toString(DBIDRef id) { - return Integer.toString(id.internalGetIndex()); - } - - @Override - public DBIDVar newVar(DBIDRef val) { - return new IntegerDBIDVar(val); - } - - @Override - public ArrayModifiableDBIDs newArray() { - return new TroveArrayModifiableDBIDs(); - } - - @Override - public HashSetModifiableDBIDs newHashSet() { - return new TroveHashSetModifiableDBIDs(); - } - - @Override - public ArrayModifiableDBIDs newArray(int size) { - return new TroveArrayModifiableDBIDs(size); - } - - @Override - public HashSetModifiableDBIDs newHashSet(int size) { - return new TroveHashSetModifiableDBIDs(size); - } - - @Override - public ArrayModifiableDBIDs newArray(DBIDs existing) { - return new TroveArrayModifiableDBIDs(existing); - } - - @Override - public HashSetModifiableDBIDs newHashSet(DBIDs existing) { - return new TroveHashSetModifiableDBIDs(existing); - } - - @Override - public DBIDPair newPair(DBIDRef first, DBIDRef second) { - return new IntegerDBIDPair(first.internalGetIndex(), second.internalGetIndex()); - } - - @Override - public DoubleDBIDPair newPair(double val, DBIDRef id) { - return new IntegerDoubleDBIDPair(val, id.internalGetIndex()); - } - - @SuppressWarnings("unchecked") - @Override - public <D extends Distance<D>> DistanceDBIDPair<D> newDistancePair(D val, DBIDRef id) { - if (val instanceof DoubleDistance) { - return (DistanceDBIDPair<D>) new DoubleDistanceIntegerDBIDPair(((DoubleDistance) val).doubleValue(), id.internalGetIndex()); - } - return new DistanceIntegerDBIDPair<D>(val, id.internalGetIndex()); - } - - @Override - public DoubleDistanceDBIDPair newDistancePair(double val, DBIDRef id) { - return new DoubleDistanceIntegerDBIDPair(val, id.internalGetIndex()); - } - - @Override - public ByteBufferSerializer<DBID> getDBIDSerializer() { - return IntegerDBID.DYNAMIC_SERIALIZER; - } - - @Override - public FixedSizeByteBufferSerializer<DBID> getDBIDSerializerStatic() { - return IntegerDBID.STATIC_SERIALIZER; - } - - @Override - public Class<? extends DBID> getTypeRestriction() { - return IntegerDBID.class; - } - - @Override - public DBIDRef invalid() { - return invalid; - } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TrivialDBIDFactory.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TrivialDBIDFactory.java index a9d8aa90..577c29ac 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) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -25,51 +25,27 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; import java.util.concurrent.atomic.AtomicInteger; -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.DBIDRef; -import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; -import de.lmu.ifi.dbs.elki.database.ids.DBIDs; -import de.lmu.ifi.dbs.elki.database.ids.DistanceDBIDPair; -import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDPair; -import de.lmu.ifi.dbs.elki.database.ids.DoubleDistanceDBIDPair; -import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; -import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; -import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; -import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; /** * Trivial DBID management, that never reuses IDs and just gives them out in - * sequence. Statically allocated DBID ranges are given positive values, - * Dynamically allocated DBIDs are given negative values. + * sequence. All IDs will be positive. * * @author Erich Schubert * * @apiviz.landmark * @apiviz.stereotype factory - * @apiviz.uses IntegerDBID oneway - - «create» - * @apiviz.uses IntegerDBIDPair oneway - - «create» - * @apiviz.uses IntegerDBIDRange oneway - - «create» - * @apiviz.uses TroveArrayModifiableDBIDs oneway - - «create» - * @apiviz.uses TroveHashSetModifiableDBIDs oneway - - «create» */ -final public class TrivialDBIDFactory implements DBIDFactory { +final public class TrivialDBIDFactory extends AbstractIntegerDBIDFactory { /** * Keep track of the smallest dynamic DBID offset not used. */ AtomicInteger next = new AtomicInteger(1); /** - * Invalid ID. - */ - DBID invalid = new IntegerDBID(Integer.MIN_VALUE); - - /** * Constructor. */ public TrivialDBIDFactory() { @@ -105,114 +81,4 @@ final public class TrivialDBIDFactory implements DBIDFactory { public void deallocateDBIDRange(DBIDRange range) { // ignore. } - - @Override - public DBID importInteger(int id) { - return new IntegerDBID(id); - } - - @Override - public void assignVar(DBIDVar var, int val) { - if (var instanceof IntegerDBIDVar) { - ((IntegerDBIDVar)var).internalSetIndex(val); - } else { - var.set(new IntegerDBID(val)); - } - } - - @Override - public int compare(DBIDRef a, DBIDRef b) { - final int inta = a.internalGetIndex(); - final int intb = b.internalGetIndex(); - return (inta < intb ? -1 : (inta == intb ? 0 : 1)); - } - - @Override - public boolean equal(DBIDRef a, DBIDRef b) { - return a.internalGetIndex() == b.internalGetIndex(); - } - - @Override - public String toString(DBIDRef id) { - return Integer.toString(id.internalGetIndex()); - } - - @Override - public DBIDVar newVar(DBIDRef val) { - return new IntegerDBIDVar(val); - } - - @Override - public ArrayModifiableDBIDs newArray() { - return new TroveArrayModifiableDBIDs(); - } - - @Override - public HashSetModifiableDBIDs newHashSet() { - return new TroveHashSetModifiableDBIDs(); - } - - @Override - public ArrayModifiableDBIDs newArray(int size) { - return new TroveArrayModifiableDBIDs(size); - } - - @Override - public HashSetModifiableDBIDs newHashSet(int size) { - return new TroveHashSetModifiableDBIDs(size); - } - - @Override - public ArrayModifiableDBIDs newArray(DBIDs existing) { - return new TroveArrayModifiableDBIDs(existing); - } - - @Override - public HashSetModifiableDBIDs newHashSet(DBIDs existing) { - return new TroveHashSetModifiableDBIDs(existing); - } - - @Override - public DBIDPair newPair(DBIDRef first, DBIDRef second) { - return new IntegerDBIDPair(first.internalGetIndex(), second.internalGetIndex()); - } - - @Override - public DoubleDBIDPair newPair(double val, DBIDRef id) { - return new IntegerDoubleDBIDPair(val, id.internalGetIndex()); - } - - @SuppressWarnings("unchecked") - @Override - public <D extends Distance<D>> DistanceDBIDPair<D> newDistancePair(D val, DBIDRef id) { - if (val instanceof DoubleDistance) { - return (DistanceDBIDPair<D>) new DoubleDistanceIntegerDBIDPair(((DoubleDistance) val).doubleValue(), id.internalGetIndex()); - } - return new DistanceIntegerDBIDPair<D>(val, id.internalGetIndex()); - } - - @Override - public DoubleDistanceDBIDPair newDistancePair(double val, DBIDRef id) { - return new DoubleDistanceIntegerDBIDPair(val, id.internalGetIndex()); - } - - @Override - public ByteBufferSerializer<DBID> getDBIDSerializer() { - return IntegerDBID.DYNAMIC_SERIALIZER; - } - - @Override - public FixedSizeByteBufferSerializer<DBID> getDBIDSerializerStatic() { - return IntegerDBID.STATIC_SERIALIZER; - } - - @Override - public Class<? extends DBID> getTypeRestriction() { - return IntegerDBID.class; - } - - @Override - public DBIDRef invalid() { - return invalid; - } } diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java index 313a0f3b..6980176a 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java @@ -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) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -24,7 +24,6 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; */ import gnu.trove.list.TIntList; -import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; @@ -40,7 +39,7 @@ import de.lmu.ifi.dbs.elki.logging.LoggingUtil; * @apiviz.has IntegerDBID * @apiviz.has DBIDItr */ -public abstract class TroveArrayDBIDs implements ArrayDBIDs, IntegerDBIDs { +public abstract class TroveArrayDBIDs implements IntegerArrayDBIDs { /** * Get the array store. * @@ -59,7 +58,7 @@ public abstract class TroveArrayDBIDs implements ArrayDBIDs, IntegerDBIDs { } @Override - public void assign(int index, DBIDVar var) { + public void assignVar(int index, DBIDVar var) { if (var instanceof IntegerDBIDVar) { ((IntegerDBIDVar)var).internalSetIndex(getStore().get(index)); } else { diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java index 7e84eb56..41191b10 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java @@ -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) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -81,6 +81,7 @@ class TroveArrayModifiableDBIDs extends TroveArrayDBIDs implements ArrayModifiab @Override public boolean addDBIDs(DBIDs ids) { boolean success = false; + store.ensureCapacity(ids.size()); for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { success |= store.add(DBIDUtil.asInteger(iter)); } diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java index 9e65b3ae..9ebdccea 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java @@ -9,13 +9,13 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.utilities.iterator.Iter; +import de.lmu.ifi.dbs.elki.utilities.datastructures.iterator.Iter; /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -83,6 +83,7 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs, IntegerDBID @Override public boolean addDBIDs(DBIDs ids) { + store.ensureCapacity(ids.size()); boolean success = false; for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { success |= store.add(DBIDUtil.asInteger(iter)); diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerArrayDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerArrayDBIDs.java index 14e26748..ba30f54f 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerArrayDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerArrayDBIDs.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) 2012 + Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -40,14 +40,14 @@ public class UnmodifiableIntegerArrayDBIDs implements IntegerArrayStaticDBIDs { /** * The DBIDs we wrap. */ - private final TroveArrayDBIDs inner; + private final IntegerArrayDBIDs inner; /** * Constructor. * * @param inner Inner DBID collection. */ - public UnmodifiableIntegerArrayDBIDs(TroveArrayDBIDs inner) { + public UnmodifiableIntegerArrayDBIDs(IntegerArrayDBIDs inner) { super(); this.inner = inner; } @@ -87,8 +87,8 @@ public class UnmodifiableIntegerArrayDBIDs implements IntegerArrayStaticDBIDs { } @Override - public void assign(int index, DBIDVar var) { - inner.assign(index, var); + public void assignVar(int index, DBIDVar var) { + inner.assignVar(index, var); } @Override diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerDBIDs.java index 1d27f530..a3f03bd9 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerDBIDs.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) 2012 + Copyright (C) 2013 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/package-info.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/package-info.java index 2508c930..74a39fb9 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) 2012 +Copyright (C) 2013 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team |