diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/database/ids/integer')
24 files changed, 1828 insertions, 467 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DistanceIntegerDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DistanceIntegerDBIDPair.java new file mode 100644 index 00000000..01eec02e --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DistanceIntegerDBIDPair.java @@ -0,0 +1,95 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import de.lmu.ifi.dbs.elki.database.ids.DistanceDBIDPair; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; + +/** + * Class storing a double distance a DBID. + * + * @author Erich Schubert + * + * @param <D> Distance type + */ +class DistanceIntegerDBIDPair<D extends Distance<D>> implements DistanceDBIDPair<D>, IntegerDBIDRef { + /** + * The distance value. + */ + D distance; + + /** + * The integer DBID. + */ + int id; + + /** + * Constructor. + * + * @param distance Distance + * @param id Object ID + */ + protected DistanceIntegerDBIDPair(D distance, int id) { + super(); + this.distance = distance; + this.id = id; + } + + @Override + public D getDistance() { + return distance; + } + + @Override + public int internalGetIndex() { + return id; + } + + @Override + public int compareByDistance(DistanceDBIDPair<D> o) { + return distance.compareTo(o.getDistance()); + } + + @Override + public String toString() { + return distance.toString() + ":" + id; + } + + @Override + public boolean equals(Object o) { + if (this == o) { + return true; + } + if (o instanceof DistanceIntegerDBIDPair) { + DistanceIntegerDBIDPair<?> p = (DistanceIntegerDBIDPair<?>) o; + return (this.id == p.id) && distance.equals(p.getDistance()); + } + if (o instanceof DoubleDistanceIntegerDBIDPair && distance instanceof DoubleDistance) { + DoubleDistanceIntegerDBIDPair p = (DoubleDistanceIntegerDBIDPair) o; + return (this.id == p.id) && (((DoubleDistance) this.distance).doubleValue() == p.distance); + } + return false; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDPair.java new file mode 100644 index 00000000..8334d2e3 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/DoubleDistanceIntegerDBIDPair.java @@ -0,0 +1,103 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +import de.lmu.ifi.dbs.elki.database.ids.DistanceDBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDistanceDBIDPair; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; + +/** + * Class storing a double distance a DBID. + * + * @author Erich Schubert + */ +class DoubleDistanceIntegerDBIDPair implements DoubleDistanceDBIDPair, IntegerDBIDRef { + /** + * The distance value. + */ + final double distance; + + /** + * The integer DBID. + */ + final int id; + + /** + * Constructor. + * + * @param distance Distance value + * @param id integer object ID + */ + protected DoubleDistanceIntegerDBIDPair(double distance, int id) { + super(); + this.distance = distance; + this.id = id; + } + + @Override + public double doubleDistance() { + return distance; + } + + @Override + @Deprecated + public DoubleDistance getDistance() { + return new DoubleDistance(distance); + } + + @Override + public int internalGetIndex() { + return id; + } + + @Override + public int compareByDistance(DistanceDBIDPair<DoubleDistance> o) { + if (o instanceof DoubleDistanceDBIDPair) { + return Double.compare(distance, ((DoubleDistanceDBIDPair) o).doubleDistance()); + } + return Double.compare(distance, o.getDistance().doubleValue()); + } + + @Override + public String toString() { + return distance + ":" + id; + } + + @Override + public boolean equals(Object o) { + if (this == o) { + return true; + } + if (o instanceof DoubleDistanceIntegerDBIDPair) { + DoubleDistanceIntegerDBIDPair p = (DoubleDistanceIntegerDBIDPair) o; + return (this.id == p.id) && (this.distance == p.distance); + } + if (o instanceof DistanceIntegerDBIDPair) { + DistanceIntegerDBIDPair<?> p = (DistanceIntegerDBIDPair<?>) o; + if (p.distance instanceof DoubleDistance) { + return (this.id == p.id) && (this.distance == ((DoubleDistance) p.distance).doubleValue()); + } + } + return false; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntArrayStaticDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntArrayStaticDBIDs.java new file mode 100644 index 00000000..aa3b3cc0 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntArrayStaticDBIDs.java @@ -0,0 +1,165 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import java.util.Arrays; + +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; +import de.lmu.ifi.dbs.elki.logging.LoggingUtil; + +/** + * Static (no modifications allowed) set of Database Object IDs. + * + * @author Erich Schubert + * + * @apiviz.has IntegerDBID + */ +public class IntArrayStaticDBIDs implements IntegerArrayStaticDBIDs { + /** + * The actual storage. + */ + protected int[] ids; + + /** + * Constructor. + * + * @param ids Array of ids. + */ + public IntArrayStaticDBIDs(int... ids) { + super(); + this.ids = ids; + } + + @Override + public IntegerDBIDArrayIter iter() { + return new DBIDItr(); + } + + /** + * DBID iterator in ELKI/C style. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected class DBIDItr implements IntegerDBIDArrayIter { + /** + * Position within array. + */ + int pos = 0; + + @Override + public boolean valid() { + return pos < ids.length && pos >= 0; + } + + @Override + public void advance() { + pos++; + } + + @Override + public void advance(int count) { + pos += 0; + } + + @Override + public void retract() { + pos--; + } + + @Override + public void seek(int off) { + pos = off; + } + + @Override + public int getOffset() { + return pos; + } + + @Override + public int internalGetIndex() { + return ids[pos]; + } + + @Override + public boolean equals(Object other) { + if(other instanceof DBID) { + LoggingUtil.warning("Programming error detected: DBIDItr.equals(DBID). Use sameDBID()!", new Throwable()); + } + return super.equals(other); + } + + @Override + public String toString() { + return Integer.toString(internalGetIndex()); + } + } + + @Override + public int size() { + return ids.length; + } + + @Override + public boolean isEmpty() { + return ids.length == 0; + } + + @Override + public boolean contains(DBIDRef o) { + final int oid = DBIDUtil.asInteger(o); + for(int i = 0; i < ids.length; i++) { + if(ids[i] == oid) { + return true; + } + } + return false; + } + + @Override + public DBID get(int i) { + return DBIDFactory.FACTORY.importInteger(ids[i]); + } + + @Override + public void assign(int i, DBIDVar var) { + if (var instanceof IntegerDBIDVar) { + ((IntegerDBIDVar)var).internalSetIndex(ids[i]); + } else { + // Much less efficient: + var.set(get(i)); + } + } + + @Override + public int binarySearch(DBIDRef key) { + return Arrays.binarySearch(ids, DBIDUtil.asInteger(key)); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayStaticDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayStaticDBIDs.java index 90ab5a6a..4bafd343 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayStaticDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayStaticDBIDs.java @@ -23,168 +23,15 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.AbstractList; -import java.util.Arrays; -import java.util.Iterator; - import de.lmu.ifi.dbs.elki.database.ids.ArrayStaticDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; -import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.logging.LoggingUtil; /** - * Static (no modifications allowed) set of Database Object IDs. + * Combination of {@link ArrayStaticDBIDs} and {@link IntegerDBIDs}. * * @author Erich Schubert - * - * @apiviz.has IntegerDBID + * */ -public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements ArrayStaticDBIDs { - /** - * The actual storage. - */ - protected int[] ids; - - /** - * Constructor - * - * @param ids Array of ids. - */ - public IntegerArrayStaticDBIDs(int... ids) { - super(); - this.ids = ids; - } - - @Override - public Iterator<DBID> iterator() { - return new Itr(); - } - - @Override - public DBIDIter iter() { - return new DBIDItr(); - } - - /** - * Iterator class. - * - * @author Erich Schubert - * - * @apiviz.exclude - */ - protected class Itr implements Iterator<DBID> { - int off = 0; - - @Override - public boolean hasNext() { - return off < ids.length; - } - - @Override - public DBID next() { - DBID ret = new IntegerDBID(ids[off]); - off++; - return ret; - } - - @Override - public void remove() { - throw new UnsupportedOperationException(); - } - } - - /** - * DBID iterator in ELKI/C style. - * - * @author Erich Schubert - * - * @apiviz.exclude - */ - protected class DBIDItr implements DBIDIter { - int pos = 0; - - @Override - public boolean valid() { - return pos < ids.length; - } - - @Override - public void advance() { - pos++; - } - - @Override - public int getIntegerID() { - return ids[pos]; - } - - @Override - public DBID getDBID() { - return new IntegerDBID(ids[pos]); - } - - @Override - public boolean sameDBID(DBIDRef other) { - return ids[pos] == other.getIntegerID(); - } - - @Override - public boolean equals(Object other) { - if (other instanceof DBID) { - LoggingUtil.warning("Programming error detected: DBIDItr.equals(DBID). Use sameDBID()!", new Throwable()); - } - return super.equals(other); - } - - @Override - public int compareDBID(DBIDRef o) { - int anotherVal = o.getIntegerID(); - return (ids[pos] < anotherVal ? -1 : (ids[pos] == anotherVal ? 0 : 1)); - } - } - - @Override - public int size() { - return ids.length; - } - - @Override - public boolean contains(DBIDRef o) { - final int oid = o.getIntegerID(); - for(int i = 0; i < ids.length; i++) { - if(ids[i] == oid) { - return true; - } - } - return false; - } - - @SuppressWarnings("unchecked") - @Override - public <T> T[] toArray(T[] a) { - T[] r = a; - if(a.length < ids.length) { - r = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), ids.length); - } - for(int i = 0; i < ids.length; i++) { - r[i] = (T) DBIDFactory.FACTORY.importInteger(ids[i]); - } - // zero-terminate array - if(r.length > ids.length) { - r[ids.length] = null; - } - return r; - } - - @Override - public DBID get(int i) { - return DBIDFactory.FACTORY.importInteger(ids[i]); - } - +public interface IntegerArrayStaticDBIDs extends ArrayStaticDBIDs, IntegerDBIDs { @Override - public int binarySearch(DBIDRef key) { - return Arrays.binarySearch(ids, key.getIntegerID()); - } + IntegerDBIDArrayIter iter(); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java index 66c1f980..91c00939 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java @@ -24,11 +24,11 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; */ import java.nio.ByteBuffer; -import java.util.Iterator; import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDArrayIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; import de.lmu.ifi.dbs.elki.logging.LoggingUtil; import de.lmu.ifi.dbs.elki.persistent.ByteArrayUtil; import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; @@ -51,11 +51,11 @@ import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; * @apiviz.composedOf DynamicSerializer * @apiviz.composedOf StaticSerializer */ -final class IntegerDBID implements DBID { +final class IntegerDBID implements DBID, IntegerDBIDRef { /** * The actual object ID. */ - final protected int id; + protected final int id; /** * Constructor from integer id. @@ -74,12 +74,7 @@ final class IntegerDBID implements DBID { */ protected IntegerDBID(Integer id) { super(); - this.id = id; - } - - @Override - public DBID getDBID() { - return this; + this.id = id.intValue(); } /** @@ -88,7 +83,7 @@ final class IntegerDBID implements DBID { * @return integer id */ @Override - public int getIntegerID() { + public int internalGetIndex() { return this.id; } @@ -103,8 +98,12 @@ final class IntegerDBID implements DBID { } @Override + @Deprecated public boolean equals(Object obj) { - if(!(obj instanceof IntegerDBID)) { + if (this == obj) { + return true; + } + if (!(obj instanceof IntegerDBID)) { if (obj instanceof DBIDRef) { LoggingUtil.warning("Programming error: DBID.equals(DBIDRef) is not well-defined. use sameDBID!", new Throwable()); } @@ -113,47 +112,37 @@ final class IntegerDBID implements DBID { IntegerDBID other = (IntegerDBID) obj; return this.id == other.id; } - - @Override - public boolean sameDBID(DBIDRef other) { - return this.id == other.getIntegerID(); - } @Override public int compareTo(DBIDRef o) { - int thisVal = this.id; - int anotherVal = o.getIntegerID(); - return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1)); + final int anotherVal = o.internalGetIndex(); + return (this.id < anotherVal ? -1 : (this.id == anotherVal ? 0 : 1)); } @Override - public int compareDBID(DBIDRef o) { - int thisVal = this.id; - int anotherVal = o.getIntegerID(); - return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1)); - } - - @Override - public DBIDIter iter() { + public DBIDArrayIter iter() { return new DBIDItr(); } @Override public DBID get(int i) { - if(i != 0) { + if (i != 0) { throw new ArrayIndexOutOfBoundsException(); } return this; } @Override - public Iterator<DBID> iterator() { - return new Itr(); + public void assign(int index, DBIDVar var) { + if (index != 0) { + throw new ArrayIndexOutOfBoundsException(); + } + var.set(this); } @Override public boolean contains(DBIDRef o) { - return o.getIntegerID() == id; + return o.internalGetIndex() == id; } @Override @@ -163,7 +152,8 @@ final class IntegerDBID implements DBID { @Override public int binarySearch(DBIDRef key) { - return (id == key.getIntegerID()) ? 0 : -1; + final int other = key.internalGetIndex(); + return (other == id) ? 0 : (other < id) ? -1 : -2; } /** @@ -173,61 +163,51 @@ final class IntegerDBID implements DBID { * * @apiviz.exclude */ - protected class Itr implements Iterator<DBID> { + protected class DBIDItr implements DBIDArrayIter, IntegerDBIDRef { /** - * Whether we've already returned our object. + * Iterator position: We use an integer so we can support retract(). */ - boolean first = true; + int pos = 0; @Override - public boolean hasNext() { - return first == true; + public void advance() { + pos++; } @Override - public DBID next() { - assert (first); - first = false; - return IntegerDBID.this; + public void advance(int count) { + pos += count; } @Override - public void remove() { - throw new UnsupportedOperationException(); + public void retract() { + pos--; } - } - - /** - * Pseudo iterator for DBIDs interface. - * - * @author Erich Schubert - * - * @apiviz.exclude - */ - protected class DBIDItr implements DBIDIter { - /** - * Whether we've already returned our object. - */ - boolean first = true; @Override - public void advance() { - first = false; + public void seek(int off) { + pos = off; } @Override - public int getIntegerID() { - return id; + public int getOffset() { + return pos; } @Override - public DBID getDBID() { - return IntegerDBID.this; + public int internalGetIndex() { + return IntegerDBID.this.id; } @Override public boolean valid() { - return first; + return (pos == 0); + } + + @Override + public int hashCode() { + // Override, because we also are overriding equals. + return super.hashCode(); } @Override @@ -239,14 +219,8 @@ final class IntegerDBID implements DBID { } @Override - public boolean sameDBID(DBIDRef other) { - return id == other.getIntegerID(); - } - - @Override - public int compareDBID(DBIDRef o) { - int anotherVal = o.getIntegerID(); - return (id < anotherVal ? -1 : (id == anotherVal ? 0 : 1)); + public String toString() { + return Integer.toString(internalGetIndex()); } } @@ -321,10 +295,10 @@ final class IntegerDBID implements DBID { /** * The public instance to use for dynamic serialization. */ - public final static DynamicSerializer dynamicSerializer = new DynamicSerializer(); + public static final ByteBufferSerializer<DBID> DYNAMIC_SERIALIZER = new DynamicSerializer(); /** * The public instance to use for static serialization. */ - public final static StaticSerializer staticSerializer = new StaticSerializer(); -}
\ No newline at end of file + public static final FixedSizeByteBufferSerializer<DBID> STATIC_SERIALIZER = new StaticSerializer(); +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayIter.java new file mode 100644 index 00000000..b0e2d339 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayIter.java @@ -0,0 +1,34 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +import de.lmu.ifi.dbs.elki.database.ids.DBIDArrayIter; + +/** + * Modifiable integer array iterator. + * + * @author Erich Schubert + */ +public interface IntegerDBIDArrayIter extends IntegerDBIDIter, DBIDArrayIter { + // Empty +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayMIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayMIter.java new file mode 100644 index 00000000..21616f75 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayMIter.java @@ -0,0 +1,34 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +import de.lmu.ifi.dbs.elki.database.ids.DBIDArrayMIter; + +/** + * Modifiable integer array iterator. + * + * @author Erich Schubert + */ +public interface IntegerDBIDArrayMIter extends IntegerDBIDArrayIter, IntegerDBIDMIter, DBIDArrayMIter { + // Empty +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayQuickSort.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayQuickSort.java new file mode 100644 index 00000000..2c096ab9 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDArrayQuickSort.java @@ -0,0 +1,250 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import java.util.Comparator; + +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; + +/** + * Class to sort an integer DBID array, using a modified quicksort. + * + * Two array iterators will be used to seek to the elements to compare, while + * the backing storage is a plain integer array. + * + * The implementation is closely based on: + * <p> + * Dual-Pivot Quicksort<br /> + * Vladimir Yaroslavskiy + * </p> + * + * @author Erich Schubert + * + * @apiviz.uses TroveArrayModifiableDBIDs + */ +@Reference(authors = "Vladimir Yaroslavskiy", title = "Dual-Pivot Quicksort", booktitle = "http://iaroslavski.narod.ru/quicksort/", url = "http://iaroslavski.narod.ru/quicksort/") +class IntegerDBIDArrayQuickSort { + /** + * Threshold for using insertion sort. Value taken from Javas QuickSort, + * assuming that it will be similar for DBIDs. + */ + private static final int INSERTION_THRESHOLD = 47; + + /** + * Sort the full array using the given comparator. + * + * @param data Data to sort + * @param comp Comparator + */ + public static void sort(int[] data, Comparator<? super DBIDRef> comp) { + sort(data, 0, data.length, comp); + } + + /** + * Sort the array using the given comparator. + * + * @param data Data to sort + * @param start First index + * @param end Last index (exclusive) + * @param comp Comparator + */ + public static void sort(int[] data, int start, int end, Comparator<? super DBIDRef> comp) { + quickSort(data, start, end - 1, comp, new IntegerDBIDVar(), new IntegerDBIDVar(), new IntegerDBIDVar()); + } + + /** + * Actual recursive sort function. + * + * @param data Data to sort + * @param start First index + * @param end Last index (inclusive!) + * @param comp Comparator + * @param vl First seeking iterator + * @param vk Second seeking iterator + * @param vr Third seeking iterator + */ + private static void quickSort(int[] data, final int start, final int end, Comparator<? super DBIDRef> comp, IntegerDBIDVar vl, IntegerDBIDVar vk, IntegerDBIDVar vr) { + final int len = end - start; + if (len < INSERTION_THRESHOLD) { + // Classic insertion sort. + for (int i = start + 1; i <= end; i++) { + for (int j = i; j > start; j--) { + vl.internalSetIndex(data[j]); + vr.internalSetIndex(data[j - 1]); + if (comp.compare(vl, vr) < 0) { + int tmp = data[j - 1]; + data[j - 1] = data[j]; + data[j] = tmp; + } else { + break; + } + } + } + return; + } + + // Choose pivots by looking at five candidates. + final int seventh = (len >> 3) + (len >> 6) + 1; + final int m3 = (start + end) >> 1; // middle + final int m2 = m3 - seventh; + final int m1 = m2 - seventh; + final int m4 = m3 + seventh; + final int m5 = m4 + seventh; + + // Explicit (and optimal) sorting network for 5 elements + // See Knuth for details. + if (compare(vl, data[m1], vk, data[m2], comp) > 0) { + int tmp = data[m2]; + data[m2] = data[m1]; + data[m1] = tmp; + } + if (compare(vl, data[m1], vk, data[m3], comp) > 0) { + int tmp = data[m3]; + data[m3] = data[m1]; + data[m1] = tmp; + } + if (compare(vl, data[m2], vk, data[m3], comp) > 0) { + int tmp = data[m3]; + data[m3] = data[m2]; + data[m2] = tmp; + } + if (compare(vl, data[m4], vk, data[m5], comp) > 0) { + int tmp = data[m5]; + data[m5] = data[m4]; + data[m4] = tmp; + } + if (compare(vl, data[m1], vk, data[m4], comp) > 0) { + int tmp = data[m4]; + data[m4] = data[m1]; + data[m1] = tmp; + } + if (compare(vl, data[m3], vk, data[m4], comp) > 0) { + int tmp = data[m4]; + data[m4] = data[m3]; + data[m3] = tmp; + } + if (compare(vl, data[m2], vk, data[m5], comp) > 0) { + int tmp = data[m5]; + data[m5] = data[m2]; + data[m2] = tmp; + } + if (compare(vl, data[m2], vk, data[m3], comp) > 0) { + int tmp = data[m3]; + data[m3] = data[m2]; + data[m2] = tmp; + } + if (compare(vl, data[m4], vk, data[m5], comp) > 0) { + int tmp = data[m5]; + data[m5] = data[m4]; + data[m4] = tmp; + } + + // Choose the 2 and 4th as pivots, as we want to get three parts + // Copy to variables v1 and v3, replace them with the start and end + // Note: do not modify v1 or v3 until we put them back! + vl.internalSetIndex(data[m2]); + vr.internalSetIndex(data[m4]); + data[m2] = data[start]; + data[m4] = data[end]; + + // A tie is when the two chosen pivots are the same + final boolean tied = comp.compare(vl, vr) == 0; + + // Insertion points for pivot areas. + int left = start + 1; + int right = end - 1; + + // Note: we merged the ties and no ties cases. + // This likely is marginally slower, but not at a macro level + // And you never know with hotspot. + for (int k = left; k <= right; k++) { + int tmp = data[k]; + vk.internalSetIndex(tmp); + final int c = comp.compare(vk, vl); + if (c == 0) { + continue; + } else if (c < 0) { + // Traditional quicksort + data[k] = data[left]; + data[left] = tmp; + left++; + } else if (tied || comp.compare(vk, vr) > 0) { + // Now look at the right. First skip correct entries there, too + while (true) { + vk.internalSetIndex(data[right]); + if (comp.compare(vk, vr) > 0 && k < right) { + right--; + } else { + break; + } + } + // Now move tmp from k to the right. + data[k] = data[right]; + data[right] = tmp; + right--; + // Test the element we just inserted: left or center? + vk.internalSetIndex(data[k]); + if (comp.compare(vk, vl) < 0) { + tmp = data[k]; + data[k] = data[left]; + data[left] = tmp; + left++; + } // else: center. cannot be on right. + } + } + // Put the pivot elements back in. + // Remember: we must not modify v1 and v3 above. + data[start] = data[left - 1]; + data[left - 1] = vl.internalGetIndex(); + data[end] = data[right + 1]; + data[right + 1] = vr.internalGetIndex(); + // v1 and v3 are now safe to modify again. Perform recursion: + quickSort(data, start, left - 2, comp, vl, vk, vr); + // Handle the middle part - if necessary: + if (!tied) { + // TODO: the original publication had a special tie handling here. + // It shouldn't affect correctness, but probably improves situations + // with a lot of tied elements. + quickSort(data, left, right, comp, vl, vk, vr); + } + quickSort(data, right + 2, end, comp, vl, vk, vr); + } + + /** + * Compare two elements. + * + * @param i1 First scratch variable + * @param p1 Value for first + * @param i2 Second scratch variable + * @param p2 Value for second + * @param comp Comparator + * @return Comparison result + */ + private static int compare(IntegerDBIDVar i1, int p1, IntegerDBIDVar i2, int p2, Comparator<? super DBIDRef> comp) { + i1.internalSetIndex(p1); + i2.internalSetIndex(p2); + return comp.compare(i1, i2); + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDIter.java new file mode 100644 index 00000000..9b50d544 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDIter.java @@ -0,0 +1,34 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; + +/** + * Iterator for integer DBIDs. + * + * @author Erich Schubert + */ +public interface IntegerDBIDIter extends IntegerDBIDRef, DBIDIter { + // Empty +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDMIter.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDMIter.java new file mode 100644 index 00000000..2e339dbc --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDMIter.java @@ -0,0 +1,34 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +import de.lmu.ifi.dbs.elki.database.ids.DBIDMIter; + +/** + * Modifiable iterator interface for integer DBIDs. + * + * @author Erich Schubert + */ +public interface IntegerDBIDMIter extends DBIDMIter, IntegerDBIDIter { + // Empty. +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java index cad771d9..85c47f43 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java @@ -23,30 +23,29 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.AbstractList; -import java.util.Iterator; - import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDArrayIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; -import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; /** - * Representing a DBID range allocation + * Representing a DBID range allocation. * * @author Erich Schubert * * @apiviz.has IntegerDBID */ -class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { +class IntegerDBIDRange implements DBIDRange { /** - * Start value + * Start value. */ protected final int start; /** - * Length value + * Length value. */ protected final int len; @@ -68,71 +67,83 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { } @Override - public Iterator<DBID> iterator() { - return new Itr(); + public boolean isEmpty() { + return len == 0; } @Override - public DBIDIter iter() { - return new DBIDItr(); + public DBIDArrayIter iter() { + return new DBIDItr(start, len); } /** - * Iterator class. + * Iterator in ELKI/C++ style. * * @author Erich Schubert * * @apiviz.exclude */ - protected class Itr implements Iterator<DBID> { + protected static class DBIDItr implements DBIDArrayIter, IntegerDBIDRef { + /** + * Current position. + */ int pos = 0; + + /** + * Interval length. + */ + final int len; + + /** + * Interval start. + */ + final int start; + + /** + * Constructor. + * + * @param start Interval start + * @param len Interval length + */ + DBIDItr(int start, int len) { + super(); + this.start = start; + this.len = len; + } @Override - public boolean hasNext() { - return pos < len; + public boolean valid() { + return pos < len && pos >= 0; } @Override - public DBID next() { - DBID ret = new IntegerDBID(pos + start); + public void advance() { pos++; - return ret; } @Override - public void remove() { - throw new UnsupportedOperationException("CompactStaticDBIDs is read-only."); + public void advance(int count) { + pos += count; } - } - - /** - * Iterator in ELKI/C++ style. - * - * @author Erich Schubert - * - * @apiviz.exclude - */ - protected class DBIDItr implements DBIDIter { - int pos = 0; @Override - public boolean valid() { - return pos < len; + public void retract() { + pos--; } @Override - public void advance() { - pos++; + public void seek(int off) { + pos = off; } @Override - public int getIntegerID() { - return start + pos; + public int getOffset() { + return pos; } @Override - public DBID getDBID() { - return new IntegerDBID(start + pos); + public int internalGetIndex() { + return start + pos; } @Override @@ -141,20 +152,14 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { } @Override - public boolean sameDBID(DBIDRef other) { - return start + pos == other.getIntegerID(); - } - - @Override - public int compareDBID(DBIDRef o) { - int anotherVal = o.getIntegerID(); - return (start + pos < anotherVal ? -1 : (start + pos == anotherVal ? 0 : 1)); + public String toString() { + return Integer.toString(internalGetIndex()); } } @Override public boolean contains(DBIDRef o) { - int oid = o.getIntegerID(); + int oid = DBIDUtil.asInteger(o); if(oid < start) { return false; } @@ -164,23 +169,6 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { return true; } - @SuppressWarnings("unchecked") - @Override - public <T> T[] toArray(T[] a) { - T[] r = a; - if(a.length < start) { - r = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), len); - } - for(int i = 0; i < start; i++) { - r[i] = (T) DBIDFactory.FACTORY.importInteger(len + i); - } - // zero-terminate array - if(r.length > len) { - r[len] = null; - } - return r; - } - @Override public DBID get(int i) { if(i > len || i < 0) { @@ -192,17 +180,27 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { /** * For storage array offsets. * - * @param dbid + * @param dbid ID reference * @return array offset */ @Override public int getOffset(DBIDRef dbid) { - return dbid.getIntegerID() - start; + return dbid.internalGetIndex() - start; + } + + @Override + public void assign(int index, DBIDVar var) { + if (var instanceof IntegerDBIDVar) { + ((IntegerDBIDVar)var).internalSetIndex(start + index); + } else { + // Much less efficient: + var.set(get(index)); + } } @Override public int binarySearch(DBIDRef key) { - int keyid = key.getIntegerID(); + int keyid = DBIDUtil.asInteger(key); if(keyid < start) { return -1; } @@ -212,4 +210,14 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { } return -(len + 1); } + + @Override + public String toString() { + return "[" + start + " to " + (start + len - 1) + "]"; + } + + @Override + public int mapDBIDToOffset(DBIDRef dbid) { + return dbid.internalGetIndex() - start; + } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveIteratorAdapter.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRef.java index 2f596f47..45854440 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveIteratorAdapter.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRef.java @@ -23,44 +23,19 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import gnu.trove.iterator.TIntIterator; - -import java.util.Iterator; - -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; /** - * Adapter for using GNU Trove iterators. + * DBID reference that references an integer value. * * @author Erich Schubert */ -class TroveIteratorAdapter implements Iterator<DBID> { - /** - * The actual iterator. - */ - private TIntIterator iterator; - +interface IntegerDBIDRef extends DBIDRef { /** - * Constructor. + * Return the integer value of the object ID. * - * @param iterator Trove iterator + * @return integer id */ - protected TroveIteratorAdapter(TIntIterator iterator) { - this.iterator = iterator; - } - - @Override - public boolean hasNext() { - return iterator.hasNext(); - } - - @Override - public DBID next() { - return new IntegerDBID(iterator.next()); - } - @Override - public void remove() { - iterator.remove(); - } + int internalGetIndex(); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDVar.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDVar.java new file mode 100644 index 00000000..73d164e0 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDVar.java @@ -0,0 +1,198 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDArrayIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; +import de.lmu.ifi.dbs.elki.logging.LoggingUtil; + +/** + * Variable for storing a single DBID reference. + * + * TODO: what is the actual memory cost for adding a flag to indicate "null" + * values, to allow the variable to be unset? Given 8-byte alignment of Java, it + * should come for free! + * + * @author Erich Schubert + */ +class IntegerDBIDVar implements DBIDVar { + /** + * The actual value. + */ + int id; + + /** + * Constructor. + */ + protected IntegerDBIDVar() { + this.id = -1; + } + + /** + * Constructor. + * + * @param val + */ + protected IntegerDBIDVar(DBIDRef val) { + this.id = val.internalGetIndex(); + } + + @Override + public int internalGetIndex() { + return id; + } + + /** + * Internal set to integer. + * + * @param i integer value + */ + protected void internalSetIndex(int i) { + id = i; + } + + @Override + public void set(DBIDRef ref) { + id = ref.internalGetIndex(); + } + + @Override + public DBID get(int i) { + if (i != 0) { + throw new ArrayIndexOutOfBoundsException(); + } + return new IntegerDBID(i); + } + + @Override + public DBIDArrayIter iter() { + return new DBIDItr(); + } + + @Override + public int size() { + return 1; + } + + @Override + public int binarySearch(DBIDRef key) { + final int other = key.internalGetIndex(); + return (other == id) ? 0 : (other < id) ? -1 : -2; + } + + @Override + public boolean contains(DBIDRef o) { + return id == o.internalGetIndex(); + } + + /** + * Pseudo iterator for DBIDs interface. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected class DBIDItr implements DBIDArrayIter, IntegerDBIDRef { + /** + * Iterator position: We use an integer so we can support retract(). + */ + int pos = 0; + + @Override + public void advance() { + pos++; + } + + @Override + public void advance(int count) { + pos += count; + } + + @Override + public void retract() { + pos--; + } + + @Override + public void seek(int off) { + pos = off; + } + + @Override + public int getOffset() { + return pos; + } + + @Override + public int internalGetIndex() { + return IntegerDBIDVar.this.id; + } + + @Override + public boolean valid() { + return (pos == 0); + } + + @Override + public int hashCode() { + // Override, because we also are overriding equals. + return super.hashCode(); + } + + @Override + public boolean equals(Object other) { + if (other instanceof DBID) { + LoggingUtil.warning("Programming error detected: DBIDItr.equals(DBID). Use sameDBID()!", new Throwable()); + } + return super.equals(other); + } + + @Override + public String toString() { + return Integer.toString(internalGetIndex()); + } + } + + @Override + public boolean isEmpty() { + return false; + } + + @Override + public void assign(int i, DBIDVar var) { + if (var instanceof IntegerDBIDVar) { + ((IntegerDBIDVar)var).internalSetIndex(i); + } else { + // Much less efficient: + var.set(get(i)); + } + } + + @Override + public String toString() { + return Integer.toString(id); + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDs.java new file mode 100644 index 00000000..8ffb9c6b --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDs.java @@ -0,0 +1,35 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +import de.lmu.ifi.dbs.elki.database.ids.DBIDs; + +/** + * Integer DBID collection. + * + * @author Erich Schubert + */ +public interface IntegerDBIDs extends DBIDs { + @Override + IntegerDBIDIter iter(); +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDoubleDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDoubleDBIDPair.java new file mode 100644 index 00000000..fe8c6a60 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDoubleDBIDPair.java @@ -0,0 +1,83 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDPair; + +/** + * Pair containing a double value and an integer DBID. + * + * @author Erich Schubert + */ +class IntegerDoubleDBIDPair implements DoubleDBIDPair, IntegerDBIDRef { + /** + * The double value. + */ + double value; + + /** + * The DB id. + */ + int id; + + /** + * Constructor. + * + * @param value Double value + * @param id DBID + */ + protected IntegerDoubleDBIDPair(double value, int id) { + super(); + this.value = value; + this.id = id; + } + + @Override + public int internalGetIndex() { + return id; + } + + @Override + public int compareTo(DoubleDBIDPair o) { + return Double.compare(value, o.doubleValue()); + } + + @Override + public double doubleValue() { + return value; + } + + @Override + @Deprecated + public Double getFirst() { + return new Double(value); + } + + @Override + @Deprecated + public DBID getSecond() { + return new IntegerDBID(id); + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/ReusingDBIDFactory.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/ReusingDBIDFactory.java index 01e42fe9..f6df2e0d 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/ReusingDBIDFactory.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/ReusingDBIDFactory.java @@ -29,6 +29,7 @@ import java.util.BitSet; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.logging.Logging; /** @@ -45,19 +46,20 @@ public class ReusingDBIDFactory extends SimpleDBIDFactory { /** * Logging for error messages. */ - private static final Logging logger = Logging.getLogger(ReusingDBIDFactory.class); - + private static final Logging LOG = Logging.getLogger(ReusingDBIDFactory.class); + /** * Bit set to keep track of dynamic DBIDs */ BitSet dynamicUsed = new BitSet(); - + /** * Keep track of the lowest unused dynamic DBID */ int dynamicStart = 0; - // TODO: add an offset, to save keeping long bit sets of 1s for heavy dynamic use? + // TODO: add an offset, to save keeping long bit sets of 1s for heavy dynamic + // use? /** * Returned range allocations @@ -79,12 +81,13 @@ public class ReusingDBIDFactory extends SimpleDBIDFactory { } @Override - public synchronized void deallocateSingleDBID(DBID id) { - if (id.getIntegerID() >= 0) { - logger.warning("Single DBID returned is from a range allocation!"); + public synchronized void deallocateSingleDBID(DBIDRef id) { + final int intid = id.internalGetIndex(); + if (intid >= 0) { + LOG.warning("Single DBID returned is from a range allocation!"); return; } - int pos = - id.getIntegerID() - 1; + final int pos = -intid - 1; dynamicUsed.clear(pos); dynamicStart = Math.min(dynamicStart, pos); } @@ -113,6 +116,6 @@ public class ReusingDBIDFactory extends SimpleDBIDFactory { @Override public synchronized void deallocateDBIDRange(DBIDRange range) { // TODO: catch an eventual cast exception? - returnedAllocations.add((IntegerDBIDRange)range); + returnedAllocations.add((IntegerDBIDRange) range); } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/SimpleDBIDFactory.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/SimpleDBIDFactory.java index 8003e4ae..77c1a91b 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/SimpleDBIDFactory.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/SimpleDBIDFactory.java @@ -29,8 +29,14 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; import de.lmu.ifi.dbs.elki.database.ids.DBIDPair; import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DistanceDBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDistanceDBIDPair; import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; @@ -52,7 +58,7 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; */ public class SimpleDBIDFactory implements DBIDFactory { /** - * Keep track of the smallest dynamic DBID offset not used + * Keep track of the smallest dynamic DBID offset not used. */ int dynamicids = 0; @@ -60,9 +66,14 @@ public class SimpleDBIDFactory implements DBIDFactory { * The starting point for static DBID range allocations. */ int rangestart = 0; + + /** + * Invalid ID. + */ + DBID invalid = new IntegerDBID(Integer.MIN_VALUE); /** - * Constructor + * Constructor. */ public SimpleDBIDFactory() { super(); @@ -78,8 +89,8 @@ public class SimpleDBIDFactory implements DBIDFactory { } @Override - public void deallocateSingleDBID(DBID id) { - // ignore. + public void deallocateSingleDBID(DBIDRef id) { + // ignore for now. } @Override @@ -103,6 +114,37 @@ public class SimpleDBIDFactory implements DBIDFactory { } @Override + public void assignVar(DBIDVar var, int val) { + if (var instanceof IntegerDBIDVar) { + ((IntegerDBIDVar)var).internalSetIndex(val); + } else { + var.set(new IntegerDBID(val)); + } + } + + @Override + public int compare(DBIDRef a, DBIDRef b) { + final int inta = a.internalGetIndex(); + final int intb = b.internalGetIndex(); + return (inta < intb ? -1 : (inta == intb ? 0 : 1)); + } + + @Override + public boolean equal(DBIDRef a, DBIDRef b) { + return a.internalGetIndex() == b.internalGetIndex(); + } + + @Override + public String toString(DBIDRef id) { + return Integer.toString(id.internalGetIndex()); + } + + @Override + public DBIDVar newVar(DBIDRef val) { + return new IntegerDBIDVar(val); + } + + @Override public ArrayModifiableDBIDs newArray() { return new TroveArrayModifiableDBIDs(); } @@ -133,22 +175,46 @@ public class SimpleDBIDFactory implements DBIDFactory { } @Override - public DBIDPair makePair(DBIDRef first, DBIDRef second) { - return new IntegerDBIDPair(first.getIntegerID(), second.getIntegerID()); + public DBIDPair newPair(DBIDRef first, DBIDRef second) { + return new IntegerDBIDPair(first.internalGetIndex(), second.internalGetIndex()); + } + + @Override + public DoubleDBIDPair newPair(double val, DBIDRef id) { + return new IntegerDoubleDBIDPair(val, id.internalGetIndex()); + } + + @SuppressWarnings("unchecked") + @Override + public <D extends Distance<D>> DistanceDBIDPair<D> newDistancePair(D val, DBIDRef id) { + if (val instanceof DoubleDistance) { + return (DistanceDBIDPair<D>) new DoubleDistanceIntegerDBIDPair(((DoubleDistance) val).doubleValue(), id.internalGetIndex()); + } + return new DistanceIntegerDBIDPair<D>(val, id.internalGetIndex()); + } + + @Override + public DoubleDistanceDBIDPair newDistancePair(double val, DBIDRef id) { + return new DoubleDistanceIntegerDBIDPair(val, id.internalGetIndex()); } @Override public ByteBufferSerializer<DBID> getDBIDSerializer() { - return IntegerDBID.dynamicSerializer; + return IntegerDBID.DYNAMIC_SERIALIZER; } @Override public FixedSizeByteBufferSerializer<DBID> getDBIDSerializerStatic() { - return IntegerDBID.staticSerializer; + return IntegerDBID.STATIC_SERIALIZER; } @Override public Class<? extends DBID> getTypeRestriction() { return IntegerDBID.class; } + + @Override + public DBIDRef invalid() { + return invalid; + } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TrivialDBIDFactory.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TrivialDBIDFactory.java index 80f65f29..a9d8aa90 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TrivialDBIDFactory.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TrivialDBIDFactory.java @@ -31,15 +31,21 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; import de.lmu.ifi.dbs.elki.database.ids.DBIDPair; import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DistanceDBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDistanceDBIDPair; import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; /** - * Trivial DBID management, that never reuses IDs and just gives them out in sequence. - * Statically allocated DBID ranges are given positive values, + * Trivial DBID management, that never reuses IDs and just gives them out in + * sequence. Statically allocated DBID ranges are given positive values, * Dynamically allocated DBIDs are given negative values. * * @author Erich Schubert @@ -52,21 +58,26 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; * @apiviz.uses TroveArrayModifiableDBIDs oneway - - «create» * @apiviz.uses TroveHashSetModifiableDBIDs oneway - - «create» */ -public class TrivialDBIDFactory implements DBIDFactory { +final public class TrivialDBIDFactory implements DBIDFactory { /** - * Keep track of the smallest dynamic DBID offset not used + * Keep track of the smallest dynamic DBID offset not used. */ AtomicInteger next = new AtomicInteger(1); - + /** - * Constructor + * Invalid ID. + */ + DBID invalid = new IntegerDBID(Integer.MIN_VALUE); + + /** + * Constructor. */ public TrivialDBIDFactory() { super(); } @Override - public DBID generateSingleDBID() { + final public DBID generateSingleDBID() { final int id = next.getAndIncrement(); if (id == Integer.MAX_VALUE) { throw new AbortException("DBID allocation error - too many objects allocated!"); @@ -76,12 +87,12 @@ public class TrivialDBIDFactory implements DBIDFactory { } @Override - public void deallocateSingleDBID(DBID id) { - // ignore. + final public void deallocateSingleDBID(DBIDRef id) { + // ignore for now } @Override - public DBIDRange generateStaticDBIDRange(int size) { + final public DBIDRange generateStaticDBIDRange(int size) { final int start = next.getAndAdd(size); if (start > next.get()) { throw new AbortException("DBID range allocation error - too many objects allocated!"); @@ -101,6 +112,37 @@ public class TrivialDBIDFactory implements DBIDFactory { } @Override + public void assignVar(DBIDVar var, int val) { + if (var instanceof IntegerDBIDVar) { + ((IntegerDBIDVar)var).internalSetIndex(val); + } else { + var.set(new IntegerDBID(val)); + } + } + + @Override + public int compare(DBIDRef a, DBIDRef b) { + final int inta = a.internalGetIndex(); + final int intb = b.internalGetIndex(); + return (inta < intb ? -1 : (inta == intb ? 0 : 1)); + } + + @Override + public boolean equal(DBIDRef a, DBIDRef b) { + return a.internalGetIndex() == b.internalGetIndex(); + } + + @Override + public String toString(DBIDRef id) { + return Integer.toString(id.internalGetIndex()); + } + + @Override + public DBIDVar newVar(DBIDRef val) { + return new IntegerDBIDVar(val); + } + + @Override public ArrayModifiableDBIDs newArray() { return new TroveArrayModifiableDBIDs(); } @@ -131,22 +173,46 @@ public class TrivialDBIDFactory implements DBIDFactory { } @Override - public DBIDPair makePair(DBIDRef first, DBIDRef second) { - return new IntegerDBIDPair(first.getIntegerID(), second.getIntegerID()); + public DBIDPair newPair(DBIDRef first, DBIDRef second) { + return new IntegerDBIDPair(first.internalGetIndex(), second.internalGetIndex()); + } + + @Override + public DoubleDBIDPair newPair(double val, DBIDRef id) { + return new IntegerDoubleDBIDPair(val, id.internalGetIndex()); + } + + @SuppressWarnings("unchecked") + @Override + public <D extends Distance<D>> DistanceDBIDPair<D> newDistancePair(D val, DBIDRef id) { + if (val instanceof DoubleDistance) { + return (DistanceDBIDPair<D>) new DoubleDistanceIntegerDBIDPair(((DoubleDistance) val).doubleValue(), id.internalGetIndex()); + } + return new DistanceIntegerDBIDPair<D>(val, id.internalGetIndex()); + } + + @Override + public DoubleDistanceDBIDPair newDistancePair(double val, DBIDRef id) { + return new DoubleDistanceIntegerDBIDPair(val, id.internalGetIndex()); } @Override public ByteBufferSerializer<DBID> getDBIDSerializer() { - return IntegerDBID.dynamicSerializer; + return IntegerDBID.DYNAMIC_SERIALIZER; } @Override public FixedSizeByteBufferSerializer<DBID> getDBIDSerializerStatic() { - return IntegerDBID.staticSerializer; + return IntegerDBID.STATIC_SERIALIZER; } @Override public Class<? extends DBID> getTypeRestriction() { return IntegerDBID.class; } -}
\ No newline at end of file + + @Override + public DBIDRef invalid() { + return invalid; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java index e2bfbcd5..313a0f3b 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java @@ -24,13 +24,12 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; */ import gnu.trove.list.TIntList; - -import java.util.Iterator; - import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.DBIDMIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; import de.lmu.ifi.dbs.elki.logging.LoggingUtil; /** @@ -39,23 +38,18 @@ import de.lmu.ifi.dbs.elki.logging.LoggingUtil; * @author Erich Schubert * * @apiviz.has IntegerDBID - * @apiviz.has TroveIteratorAdapter + * @apiviz.has DBIDItr */ -public abstract class TroveArrayDBIDs implements ArrayDBIDs { +public abstract class TroveArrayDBIDs implements ArrayDBIDs, IntegerDBIDs { /** - * Get the array store + * Get the array store. * * @return the store */ - abstract protected TIntList getStore(); + protected abstract TIntList getStore(); @Override - public Iterator<DBID> iterator() { - return new TroveIteratorAdapter(getStore().iterator()); - } - - @Override - public DBIDMIter iter() { + public IntegerDBIDArrayMIter iter() { return new DBIDItr(getStore()); } @@ -65,10 +59,20 @@ public abstract class TroveArrayDBIDs implements ArrayDBIDs { } @Override + public void assign(int index, DBIDVar var) { + if (var instanceof IntegerDBIDVar) { + ((IntegerDBIDVar)var).internalSetIndex(getStore().get(index)); + } else { + // Much less efficient: + var.set(get(index)); + } + } + + @Override public int size() { return getStore().size(); } - + @Override public boolean isEmpty() { return getStore().isEmpty(); @@ -76,29 +80,43 @@ public abstract class TroveArrayDBIDs implements ArrayDBIDs { @Override public boolean contains(DBIDRef o) { - return getStore().contains(o.getIntegerID()); + return getStore().contains(DBIDUtil.asInteger(o)); } @Override public int binarySearch(DBIDRef key) { - return getStore().binarySearch(key.getIntegerID()); + return getStore().binarySearch(DBIDUtil.asInteger(key)); + } + + @Override + public String toString() { + StringBuilder buf = new StringBuilder(); + buf.append('['); + for(DBIDIter iter = iter(); iter.valid(); iter.advance()) { + if(buf.length() > 1) { + buf.append(", "); + } + buf.append(((IntegerDBIDRef) iter).internalGetIndex()); + } + buf.append(']'); + return buf.toString(); } /** - * Iterate over a Trove IntList, ELKI/C-style + * Iterate over a Trove IntList, ELKI/C-style. * * @author Erich Schubert * * @apiviz.exclude */ - protected static class DBIDItr implements DBIDMIter { + protected static class DBIDItr implements IntegerDBIDArrayMIter { /** - * Current position + * Current position. */ int pos = 0; /** - * The actual store we use + * The actual store we use. */ TIntList store; @@ -114,7 +132,7 @@ public abstract class TroveArrayDBIDs implements ArrayDBIDs { @Override public boolean valid() { - return pos < store.size(); + return pos < store.size() && pos >= 0; } @Override @@ -123,13 +141,28 @@ public abstract class TroveArrayDBIDs implements ArrayDBIDs { } @Override - public int getIntegerID() { - return store.get(pos); + public void advance(int count) { + pos += count; } @Override - public DBID getDBID() { - return new IntegerDBID(store.get(pos)); + public void retract() { + pos--; + } + + @Override + public void seek(int off) { + pos = off; + } + + @Override + public int getOffset() { + return pos; + } + + @Override + public int internalGetIndex() { + return store.get(pos); } @Override @@ -139,23 +172,22 @@ public abstract class TroveArrayDBIDs implements ArrayDBIDs { } @Override - public boolean sameDBID(DBIDRef other) { - return store.get(pos) == other.getIntegerID(); + public int hashCode() { + // Since we add a warning to 'equals', we also override hashCode. + return super.hashCode(); } @Override public boolean equals(Object other) { - if (other instanceof DBID) { - LoggingUtil.warning("Programming error detected: DBIDItr.equals(DBID). Use sameDBID()!", new Throwable()); + if(other instanceof DBID) { + LoggingUtil.warning("Programming error detected: DBIDItr.equals(DBID). Use DBIDUtil.equal(iter, id)!", new Throwable()); } return super.equals(other); } @Override - public int compareDBID(DBIDRef o) { - final int thisVal = store.get(pos); - final int anotherVal = o.getIntegerID(); - return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1)); + public String toString() { + return Integer.toString(internalGetIndex()); } } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java index 379ea8a6..7e84eb56 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java @@ -25,13 +25,13 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; import gnu.trove.list.array.TIntArrayList; -import java.util.Arrays; import java.util.Comparator; import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; /** @@ -81,8 +81,8 @@ class TroveArrayModifiableDBIDs extends TroveArrayDBIDs implements ArrayModifiab @Override public boolean addDBIDs(DBIDs ids) { boolean success = false; - for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - success |= store.add(iter.getIntegerID()); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + success |= store.add(DBIDUtil.asInteger(iter)); } return success; } @@ -90,25 +90,25 @@ class TroveArrayModifiableDBIDs extends TroveArrayDBIDs implements ArrayModifiab @Override public boolean removeDBIDs(DBIDs ids) { boolean success = false; - for(DBID id : ids) { - success |= store.remove(id.getIntegerID()); + for (DBIDIter id = ids.iter(); id.valid(); id.advance()) { + success |= store.remove(DBIDUtil.asInteger(id)); } return success; } @Override public boolean add(DBIDRef e) { - return store.add(e.getIntegerID()); + return store.add(DBIDUtil.asInteger(e)); } @Override public boolean remove(DBIDRef o) { - return store.remove(o.getIntegerID()); + return store.remove(DBIDUtil.asInteger(o)); } @Override - public DBID set(int index, DBID element) { - int prev = store.set(index, element.getIntegerID()); + public DBID set(int index, DBIDRef element) { + int prev = store.set(index, DBIDUtil.asInteger(element)); return new IntegerDBID(prev); } @@ -128,23 +128,27 @@ class TroveArrayModifiableDBIDs extends TroveArrayDBIDs implements ArrayModifiab } @Override - public void sort(Comparator<? super DBID> comparator) { - // FIXME: optimize, avoid the extra copy. - // Clone data - DBID[] data = new DBID[store.size()]; - for(int i = 0; i < store.size(); i++) { - data[i] = new IntegerDBID(store.get(i)); - } - // Sort - Arrays.sort(data, comparator); - // Copy back - for(int i = 0; i < store.size(); i++) { - store.set(i, data[i].getIntegerID()); - } + public void sort(Comparator<? super DBIDRef> comparator) { + // TODO: we no longer produce a lot of DBIDs anymore, but it would be even + // cooler if we could access store._data directly... + int[] data = store.toArray(); + IntegerDBIDArrayQuickSort.sort(data, comparator); + store.clear(); + store.add(data); + } + + @Override + public void sort(int start, int end, Comparator<? super DBIDRef> comparator) { + // TODO: we no longer produce a lot of DBIDs anymore, but it would be even + // cooler if we could access store._data directly... + int[] data = store.toArray(); + IntegerDBIDArrayQuickSort.sort(data, start, end, comparator); + store.clear(); + store.add(data); } @Override public void swap(int a, int b) { store.set(a, store.set(b, store.get(a))); } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayStaticDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayStaticDBIDs.java index 53ab34d4..60dd50eb 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayStaticDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayStaticDBIDs.java @@ -23,16 +23,15 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; */ import gnu.trove.list.TIntList; -import de.lmu.ifi.dbs.elki.database.ids.ArrayStaticDBIDs; /** * Class accessing a trove int array. * * @author Erich Schubert */ -class TroveArrayStaticDBIDs extends TroveArrayDBIDs implements ArrayStaticDBIDs { +class TroveArrayStaticDBIDs extends TroveArrayDBIDs implements IntegerArrayStaticDBIDs { /** - * Actual trove store + * Actual trove store. */ private final TIntList store; diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java index 12656f7b..9e65b3ae 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java @@ -1,16 +1,15 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; -import java.util.Iterator; - import gnu.trove.impl.hash.THashPrimitiveIterator; import gnu.trove.impl.hash.TIntHash; import gnu.trove.set.hash.TIntHashSet; -import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDMIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; +import de.lmu.ifi.dbs.elki.utilities.iterator.Iter; /* This file is part of ELKI: @@ -41,9 +40,9 @@ import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; * @author Erich Schubert * * @apiviz.has IntegerDBID - * @apiviz.has TroveIteratorAdapter + * @apiviz.has DBIDItr */ -class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs { +class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs, IntegerDBIDs { /** * The actual store. */ @@ -78,15 +77,15 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs { } @Override - public DBIDMIter iter() { + public IntegerDBIDMIter iter() { return new DBIDItr(store); } @Override public boolean addDBIDs(DBIDs ids) { boolean success = false; - for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - success |= store.add(iter.getIntegerID()); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + success |= store.add(DBIDUtil.asInteger(iter)); } return success; } @@ -94,28 +93,27 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs { @Override public boolean removeDBIDs(DBIDs ids) { boolean success = false; - for(DBID id : ids) { - success |= store.remove(id.getIntegerID()); + for (DBIDIter id = ids.iter(); id.valid(); id.advance()) { + success |= store.remove(DBIDUtil.asInteger(id)); } return success; } @Override public boolean add(DBIDRef e) { - return store.add(e.getIntegerID()); + return store.add(DBIDUtil.asInteger(e)); } @Override public boolean remove(DBIDRef o) { - return store.remove(o.getIntegerID()); + return store.remove(DBIDUtil.asInteger(o)); } @Override public boolean retainAll(DBIDs set) { boolean modified = false; - Iterator<DBID> it = iterator(); - while(it.hasNext()) { - if(!set.contains(it.next())) { + for (DBIDMIter it = iter(); it.valid(); it.advance()) { + if (!set.contains(it)) { it.remove(); modified = true; } @@ -124,11 +122,6 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs { } @Override - public Iterator<DBID> iterator() { - return new TroveIteratorAdapter(store.iterator()); - } - - @Override public int size() { return store.size(); } @@ -145,7 +138,21 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs { @Override public boolean contains(DBIDRef o) { - return store.contains(o.getIntegerID()); + return store.contains(DBIDUtil.asInteger(o)); + } + + @Override + public String toString() { + StringBuilder buf = new StringBuilder(); + buf.append('['); + for (DBIDIter iter = iter(); iter.valid(); iter.advance()) { + if (buf.length() > 1) { + buf.append(", "); + } + buf.append(iter.toString()); + } + buf.append(']'); + return buf.toString(); } /** @@ -155,11 +162,11 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs { * * @apiviz.exclude */ - protected static class DBIDItr extends THashPrimitiveIterator implements DBIDMIter { + protected static class DBIDItr implements IntegerDBIDMIter { /** - * The has we access + * The actual iterator. We don't have multi inheritance. */ - private TIntHash hash; + TIntHashItr it; /** * Constructor. @@ -167,41 +174,77 @@ class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs { * @param hash Trove hash */ public DBIDItr(TIntHash hash) { - super(hash); - this.hash = hash; - this._index = nextIndex(); // Find first element + super(); + this.it = new TIntHashItr(hash); } @Override public boolean valid() { - return _index >= 0; + return it.valid(); } @Override public void advance() { - this._index = nextIndex(); + it.advance(); } @Override - public int getIntegerID() { - return hash._set[_index]; + public int internalGetIndex() { + return it.getInt(); } @Override - public DBID getDBID() { - return new IntegerDBID(hash._set[_index]); + public String toString() { + return Integer.toString(internalGetIndex()); } @Override - public boolean sameDBID(DBIDRef other) { - return getIntegerID() == other.getIntegerID(); + public void remove() { + it.remove(); } - @Override - public int compareDBID(DBIDRef o) { - final int thisVal = hash._set[_index]; - final int anotherVal = o.getIntegerID(); - return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1)); + /** + * Custom iterator over TIntHash. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + private static class TIntHashItr extends THashPrimitiveIterator implements Iter { + /** + * The hash we access. + */ + private TIntHash hash; + + /** + * Constructor. + * + * @param hash Hash to iterate over. + */ + public TIntHashItr(TIntHash hash) { + super(hash); + this.hash = hash; + this._index = nextIndex(); // Find first element + } + + /** + * Get the current value. + * + * @return Current value + */ + public int getInt() { + return hash._set[_index]; + } + + @Override + public void advance() { + this._index = nextIndex(); + } + + @Override + public boolean valid() { + return _index >= 0; + } } } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerArrayDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerArrayDBIDs.java new file mode 100644 index 00000000..14e26748 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerArrayDBIDs.java @@ -0,0 +1,160 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDMIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDVar; + +/** + * Unmodifiable wrapper for DBIDs. + * + * @author Erich Schubert + * + * @apiviz.uses TroveArrayDBIDs + * @apiviz.has UnmodifiableDBIDIter + */ +public class UnmodifiableIntegerArrayDBIDs implements IntegerArrayStaticDBIDs { + /** + * The DBIDs we wrap. + */ + private final TroveArrayDBIDs inner; + + /** + * Constructor. + * + * @param inner Inner DBID collection. + */ + public UnmodifiableIntegerArrayDBIDs(TroveArrayDBIDs inner) { + super(); + this.inner = inner; + } + + @Override + public boolean contains(DBIDRef o) { + return inner.contains(o); + } + + @Override + public boolean isEmpty() { + return inner.isEmpty(); + } + + @Override + public IntegerDBIDArrayIter iter() { + IntegerDBIDArrayIter it = inner.iter(); + if (it instanceof DBIDMIter) { + return new UnmodifiableDBIDIter(it); + } + return it; + } + + @Override + public int size() { + return inner.size(); + } + + @Override + public String toString() { + return inner.toString(); + } + + @Override + public DBID get(int i) { + return inner.get(i); + } + + @Override + public void assign(int index, DBIDVar var) { + inner.assign(index, var); + } + + @Override + public int binarySearch(DBIDRef key) { + return inner.binarySearch(key); + } + + /** + * Make an existing DBIDMIter unmodifiable. + * + * @author Erich Schubert + */ + class UnmodifiableDBIDIter implements IntegerDBIDArrayIter { + /** + * Wrapped iterator. + */ + private IntegerDBIDArrayIter it; + + /** + * Constructor. + * + * @param it inner iterator + */ + public UnmodifiableDBIDIter(IntegerDBIDArrayIter it) { + super(); + this.it = it; + } + + @Override + public boolean valid() { + return it.valid(); + } + + @Override + public void advance() { + it.advance(); + } + + @Override + public void advance(int count) { + it.advance(count); + } + + @Override + public void retract() { + it.retract(); + } + + @Override + public void seek(int off) { + it.seek(off); + } + + @Override + public int getOffset() { + return it.getOffset(); + } + + @Override + public int internalGetIndex() { + return it.internalGetIndex(); + } + + @Override + public String toString() { + return it.toString(); + } + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerDBIDs.java new file mode 100644 index 00000000..1d27f530 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/UnmodifiableIntegerDBIDs.java @@ -0,0 +1,119 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import de.lmu.ifi.dbs.elki.database.ids.DBIDMIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.StaticDBIDs; + +/** + * Unmodifiable wrapper for DBIDs. + * + * @author Erich Schubert + * + * @apiviz.uses IntegerDBIDs + * @apiviz.has UnmodifiableDBIDIter + */ +public class UnmodifiableIntegerDBIDs implements StaticDBIDs, IntegerDBIDs { + /** + * The DBIDs we wrap. + */ + private final IntegerDBIDs inner; + + /** + * Constructor. + * + * @param inner Inner DBID collection. + */ + public UnmodifiableIntegerDBIDs(IntegerDBIDs inner) { + super(); + this.inner = inner; + } + + @Override + public boolean contains(DBIDRef o) { + return inner.contains(o); + } + + @Override + public boolean isEmpty() { + return inner.isEmpty(); + } + + @Override + public IntegerDBIDIter iter() { + IntegerDBIDIter it = inner.iter(); + if (it instanceof DBIDMIter) { + return new UnmodifiableDBIDIter(it); + } + return it; + } + + @Override + public int size() { + return inner.size(); + } + + @Override + public String toString() { + return inner.toString(); + } + + /** + * Make an existing DBIDMIter unmodifiable. + * + * @author Erich Schubert + */ + class UnmodifiableDBIDIter implements IntegerDBIDIter { + /** + * Wrapped iterator. + */ + private IntegerDBIDIter it; + + /** + * Constructor. + * + * @param it inner iterator + */ + public UnmodifiableDBIDIter(IntegerDBIDIter it) { + super(); + this.it = it; + } + + @Override + public boolean valid() { + return it.valid(); + } + + @Override + public void advance() { + it.advance(); + } + + @Override + public int internalGetIndex() { + return it.internalGetIndex(); + } + } +} |