diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/database/ids/integer')
13 files changed, 789 insertions, 134 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayStaticDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayStaticDBIDs.java index b617b4c4..ef4aee94 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayStaticDBIDs.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerArrayStaticDBIDs.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -24,22 +24,22 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; */ import java.util.AbstractList; -import java.util.Collection; +import java.util.Arrays; import java.util.Iterator; -import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.ArrayStaticDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; - +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; /** * Static (no modifications allowed) set of Database Object IDs. * * @author Erich Schubert * - * @apiviz.composedOf IntegerDBID + * @apiviz.has IntegerDBID */ -public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements ArrayDBIDs { +public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements ArrayStaticDBIDs { /** * The actual storage. */ @@ -59,7 +59,12 @@ public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements Array public Iterator<DBID> iterator() { return new Itr(); } - + + @Override + public DBIDIter iter() { + return new DBIDItr(); + } + /** * Iterator class. * @@ -77,7 +82,7 @@ public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements Array @Override public DBID next() { - DBID ret = DBIDFactory.FACTORY.importInteger(ids[off]); + DBID ret = new IntegerDBID(ids[off]); off++; return ret; } @@ -88,22 +93,49 @@ public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements Array } } + /** + * DBID iterator in ELKI/C style. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected class DBIDItr implements DBIDIter { + int pos = 0; + + @Override + public boolean valid() { + return pos < ids.length; + } + + @Override + public void advance() { + pos++; + } + + @Override + public int getIntegerID() { + return ids[pos]; + } + + @Override + public DBID getDBID() { + return new IntegerDBID(ids[pos]); + } + + } + @Override public int size() { return ids.length; } - - /* - * "Contains" operations - */ + @Override - public boolean contains(Object o) { - if(o instanceof DBID) { - int oid = ((DBID) o).getIntegerID(); - for(int i = 0; i < ids.length; i++) { - if(ids[i] == oid) { - return true; - } + public boolean contains(DBID o) { + final int oid = o.getIntegerID(); + for(int i = 0; i < ids.length; i++) { + if(ids[i] == oid) { + return true; } } return false; @@ -132,7 +164,7 @@ public class IntegerArrayStaticDBIDs extends AbstractList<DBID> implements Array } @Override - public Collection<DBID> asCollection() { - return this; + public int binarySearch(DBID key) { + return Arrays.binarySearch(ids, key.getIntegerID()); } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java index 2842ca75..f9e83294 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBID.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -24,11 +24,10 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; */ import java.nio.ByteBuffer; -import java.util.AbstractList; -import java.util.Collection; import java.util.Iterator; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.persistent.ByteArrayUtil; import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; @@ -50,7 +49,7 @@ import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; * @apiviz.composedOf DynamicSerializer * @apiviz.composedOf StaticSerializer */ -class IntegerDBID extends AbstractList<DBID> implements DBID { +class IntegerDBID implements DBID { /** * The actual object ID. */ @@ -113,13 +112,16 @@ class IntegerDBID extends AbstractList<DBID> implements DBID { } @Override - public Collection<DBID> asCollection() { - return this; + public DBIDIter iter() { + return new DBIDItr(); } @Override - public boolean contains(Object o) { - return this.equals(o); + public DBID get(int i) { + if(i != 0) { + throw new ArrayIndexOutOfBoundsException(); + } + return this; } @Override @@ -128,10 +130,20 @@ class IntegerDBID extends AbstractList<DBID> implements DBID { } @Override + public boolean contains(DBID o) { + return o.getIntegerID() == id; + } + + @Override public int size() { return 1; } + @Override + public int binarySearch(DBID key) { + return equals(key) ? 0 : -1; + } + /** * Pseudo iterator for DBIDs interface. * @@ -163,21 +175,45 @@ class IntegerDBID extends AbstractList<DBID> implements DBID { } } - @Override - public boolean isEmpty() { - return false; - } + /** + * Pseudo iterator for DBIDs interface. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected class DBIDItr implements DBIDIter { + /** + * Whether we've already returned our object. + */ + boolean first = true; - @Override - public DBID get(int i) { - if(i == 0) { - return this; + @Override + public void advance() { + first = false; } - else { - throw new ArrayIndexOutOfBoundsException(); + + @Override + public int getIntegerID() { + return id; + } + + @Override + public DBID getDBID() { + return IntegerDBID.this; + } + + @Override + public boolean valid() { + return first; } } + @Override + public boolean isEmpty() { + return false; + } + /** * Dynamic sized serializer, using varint. * diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDPair.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDPair.java index 742bab57..e716f5b5 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDPair.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDPair.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -30,7 +30,7 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDPair; * * @author Erich Schubert * - * @apiviz.composedOf IntegerDBID + * @apiviz.has IntegerDBID */ public class IntegerDBIDPair implements DBIDPair { /** diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java index 1142f1a6..debe39a4 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/IntegerDBIDRange.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -24,32 +24,31 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; */ import java.util.AbstractList; -import java.util.Collection; import java.util.Iterator; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; - /** * Representing a DBID range allocation * * @author Erich Schubert * - * @apiviz.composedOf IntegerDBID + * @apiviz.has IntegerDBID */ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { /** * Start value */ protected final int start; - + /** * Length value */ protected final int len; - + /** * Constructor. * @@ -72,6 +71,11 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { return new Itr(); } + @Override + public DBIDIter iter() { + return new DBIDItr(); + } + /** * Iterator class. * @@ -89,7 +93,7 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { @Override public DBID next() { - DBID ret = DBIDFactory.FACTORY.importInteger(pos + start); + DBID ret = new IntegerDBID(pos + start); pos++; return ret; } @@ -100,22 +104,48 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { } } - /* - * "Contains" operations + /** + * Iterator in ELKI/C++ style. + * + * @author Erich Schubert + * + * @apiviz.exclude */ + protected class DBIDItr implements DBIDIter { + int pos = 0; + + @Override + public boolean valid() { + return pos < len; + } + + @Override + public void advance() { + pos++; + } + + @Override + public int getIntegerID() { + return start + pos; + } + + @Override + public DBID getDBID() { + return new IntegerDBID(start + pos); + } + + } + @Override - public boolean contains(Object o) { - if(o instanceof DBID) { - int oid = ((DBID) o).getIntegerID(); - if(oid < start) { - return false; - } - if(oid >= start + len) { - return false; - } - return true; + public boolean contains(DBID o) { + int oid = o.getIntegerID(); + if(oid < start) { + return false; } - return false; + if(oid >= start + len) { + return false; + } + return true; } @SuppressWarnings("unchecked") @@ -137,11 +167,11 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { @Override public DBID get(int i) { - if (i > len || i < 0) { + if(i > len || i < 0) { throw new ArrayIndexOutOfBoundsException(); } return DBIDFactory.FACTORY.importInteger(start + i); - } + } /** * For storage array offsets. @@ -155,7 +185,15 @@ class IntegerDBIDRange extends AbstractList<DBID> implements DBIDRange { } @Override - public Collection<DBID> asCollection() { - return this; + public int binarySearch(DBID key) { + int keyid = key.getIntegerID(); + if(keyid < start) { + return -1; + } + final int off = keyid - start; + if(off < len) { + return off; + } + return -(len + 1); } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/ReusingDBIDFactory.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/ReusingDBIDFactory.java index 8e4600db..01e42fe9 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/ReusingDBIDFactory.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/ReusingDBIDFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/SimpleDBIDFactory.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/SimpleDBIDFactory.java index 3348701e..59fa34b5 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/SimpleDBIDFactory.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/SimpleDBIDFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -27,21 +27,17 @@ import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; import de.lmu.ifi.dbs.elki.database.ids.DBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; -import de.lmu.ifi.dbs.elki.database.ids.TreeSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericArrayModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericHashSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericTreeSetModifiableDBIDs; import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; /** - * Simple DBID management, that never reuses IDs. - * Statically allocated DBID ranges are given positive values, - * Dynamically allocated DBIDs are given negative values. + * Simple DBID management, that never reuses IDs. Statically allocated DBID + * ranges are given positive values, Dynamically allocated DBIDs are given + * negative values. * * @author Erich Schubert * @@ -50,21 +46,20 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; * @apiviz.uses IntegerDBID oneway - - «create» * @apiviz.uses IntegerDBIDPair oneway - - «create» * @apiviz.uses IntegerDBIDRange oneway - - «create» - * @apiviz.uses GenericArrayModifiableDBIDs oneway - - «create» - * @apiviz.uses GenericHashSetModifiableDBIDs oneway - - «create» - * @apiviz.uses GenericTreeSetModifiableDBIDs oneway - - «create» + * @apiviz.uses TroveArrayModifiableDBIDs oneway - - «create» + * @apiviz.uses TroveHashSetModifiableDBIDs oneway - - «create» */ public class SimpleDBIDFactory implements DBIDFactory { /** * Keep track of the smallest dynamic DBID offset not used */ int dynamicids = 0; - + /** * The starting point for static DBID range allocations. */ int rangestart = 0; - + /** * Constructor */ @@ -74,7 +69,7 @@ public class SimpleDBIDFactory implements DBIDFactory { @Override public synchronized DBID generateSingleDBID() { - if (dynamicids == Integer.MIN_VALUE) { + if(dynamicids == Integer.MIN_VALUE) { throw new AbortException("DBID range allocation error - too many objects allocated!"); } dynamicids--; @@ -88,7 +83,7 @@ public class SimpleDBIDFactory implements DBIDFactory { @Override public synchronized DBIDRange generateStaticDBIDRange(int size) { - if (rangestart >= Integer.MAX_VALUE - size) { + if(rangestart >= Integer.MAX_VALUE - size) { throw new AbortException("DBID range allocation error - too many objects allocated!"); } DBIDRange alloc = new IntegerDBIDRange(rangestart, size); @@ -108,47 +103,32 @@ public class SimpleDBIDFactory implements DBIDFactory { @Override public ArrayModifiableDBIDs newArray() { - return new GenericArrayModifiableDBIDs(); + return new TroveArrayModifiableDBIDs(); } @Override public HashSetModifiableDBIDs newHashSet() { - return new GenericHashSetModifiableDBIDs(); - } - - @Override - public TreeSetModifiableDBIDs newTreeSet() { - return new GenericTreeSetModifiableDBIDs(); + return new TroveHashSetModifiableDBIDs(); } @Override public ArrayModifiableDBIDs newArray(int size) { - return new GenericArrayModifiableDBIDs(size); + return new TroveArrayModifiableDBIDs(size); } @Override public HashSetModifiableDBIDs newHashSet(int size) { - return new GenericHashSetModifiableDBIDs(size); - } - - @Override - public TreeSetModifiableDBIDs newTreeSet(int size) { - return new GenericTreeSetModifiableDBIDs(size); + return new TroveHashSetModifiableDBIDs(size); } @Override public ArrayModifiableDBIDs newArray(DBIDs existing) { - return new GenericArrayModifiableDBIDs(existing); + return new TroveArrayModifiableDBIDs(existing); } @Override public HashSetModifiableDBIDs newHashSet(DBIDs existing) { - return new GenericHashSetModifiableDBIDs(existing); - } - - @Override - public TreeSetModifiableDBIDs newTreeSet(DBIDs existing) { - return new GenericTreeSetModifiableDBIDs(existing); + return new TroveHashSetModifiableDBIDs(existing); } @Override diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TrivialDBIDFactory.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TrivialDBIDFactory.java index ee49e2f1..b38286fe 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TrivialDBIDFactory.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TrivialDBIDFactory.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.database.ids.integer; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -29,13 +29,9 @@ import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDFactory; import de.lmu.ifi.dbs.elki.database.ids.DBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.DBIDRange; -import de.lmu.ifi.dbs.elki.database.ids.TreeSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericArrayModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericHashSetModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.ids.generic.GenericTreeSetModifiableDBIDs; import de.lmu.ifi.dbs.elki.persistent.ByteBufferSerializer; import de.lmu.ifi.dbs.elki.persistent.FixedSizeByteBufferSerializer; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; @@ -52,9 +48,8 @@ import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; * @apiviz.uses IntegerDBID oneway - - «create» * @apiviz.uses IntegerDBIDPair oneway - - «create» * @apiviz.uses IntegerDBIDRange oneway - - «create» - * @apiviz.uses GenericArrayModifiableDBIDs oneway - - «create» - * @apiviz.uses GenericHashSetModifiableDBIDs oneway - - «create» - * @apiviz.uses GenericTreeSetModifiableDBIDs oneway - - «create» + * @apiviz.uses TroveArrayModifiableDBIDs oneway - - «create» + * @apiviz.uses TroveHashSetModifiableDBIDs oneway - - «create» */ public class TrivialDBIDFactory implements DBIDFactory { /** @@ -106,47 +101,32 @@ public class TrivialDBIDFactory implements DBIDFactory { @Override public ArrayModifiableDBIDs newArray() { - return new GenericArrayModifiableDBIDs(); + return new TroveArrayModifiableDBIDs(); } @Override public HashSetModifiableDBIDs newHashSet() { - return new GenericHashSetModifiableDBIDs(); - } - - @Override - public TreeSetModifiableDBIDs newTreeSet() { - return new GenericTreeSetModifiableDBIDs(); + return new TroveHashSetModifiableDBIDs(); } @Override public ArrayModifiableDBIDs newArray(int size) { - return new GenericArrayModifiableDBIDs(size); + return new TroveArrayModifiableDBIDs(size); } @Override public HashSetModifiableDBIDs newHashSet(int size) { - return new GenericHashSetModifiableDBIDs(size); - } - - @Override - public TreeSetModifiableDBIDs newTreeSet(int size) { - return new GenericTreeSetModifiableDBIDs(size); + return new TroveHashSetModifiableDBIDs(size); } @Override public ArrayModifiableDBIDs newArray(DBIDs existing) { - return new GenericArrayModifiableDBIDs(existing); + return new TroveArrayModifiableDBIDs(existing); } @Override public HashSetModifiableDBIDs newHashSet(DBIDs existing) { - return new GenericHashSetModifiableDBIDs(existing); - } - - @Override - public TreeSetModifiableDBIDs newTreeSet(DBIDs existing) { - return new GenericTreeSetModifiableDBIDs(existing); + return new TroveHashSetModifiableDBIDs(existing); } @Override diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java new file mode 100644 index 00000000..a060c6b8 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayDBIDs.java @@ -0,0 +1,133 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import gnu.trove.list.TIntList; + +import java.util.Iterator; + +import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; + +/** + * Abstract base class for GNU Trove array based lists. + * + * @author Erich Schubert + * + * @apiviz.has IntegerDBID + * @apiviz.has TroveIteratorAdapter + */ +public abstract class TroveArrayDBIDs implements ArrayDBIDs { + /** + * Get the array store + * + * @return the store + */ + abstract protected TIntList getStore(); + + @Override + public Iterator<DBID> iterator() { + return new TroveIteratorAdapter(getStore().iterator()); + } + + @Override + public DBIDIter iter() { + return new DBIDItr(getStore()); + } + + @Override + public DBID get(int index) { + return new IntegerDBID(getStore().get(index)); + } + + @Override + public int size() { + return getStore().size(); + } + + @Override + public boolean isEmpty() { + return getStore().isEmpty(); + } + + @Override + public boolean contains(DBID o) { + return getStore().contains(o.getIntegerID()); + } + + @Override + public int binarySearch(DBID key) { + return getStore().binarySearch(key.getIntegerID()); + } + + /** + * Iterate over a Trove IntList, ELKI/C-style + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected static class DBIDItr implements DBIDIter { + /** + * Current position + */ + int pos = 0; + + /** + * The actual store we use + */ + TIntList store; + + /** + * Constructor. + * + * @param store The actual trove store + */ + public DBIDItr(TIntList store) { + super(); + this.store = store; + } + + @Override + public boolean valid() { + return pos < store.size(); + } + + @Override + public void advance() { + pos++; + } + + @Override + public int getIntegerID() { + return store.get(pos); + } + + @Override + public DBID getDBID() { + return new IntegerDBID(store.get(pos)); + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java new file mode 100644 index 00000000..abcbba14 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayModifiableDBIDs.java @@ -0,0 +1,144 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import gnu.trove.list.array.TIntArrayList; + +import java.util.Arrays; +import java.util.Comparator; + +import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDs; + +/** + * Class using a GNU Trove int array list as storage. + * + * @author Erich Schubert + */ +class TroveArrayModifiableDBIDs extends TroveArrayDBIDs implements ArrayModifiableDBIDs { + /** + * The actual trove array list + */ + private TIntArrayList store; + + /** + * Constructor. + * + * @param size Initial size + */ + protected TroveArrayModifiableDBIDs(int size) { + super(); + this.store = new TIntArrayList(size); + } + + /** + * Constructor. + */ + protected TroveArrayModifiableDBIDs() { + super(); + this.store = new TIntArrayList(); + } + + /** + * Constructor. + * + * @param existing Existing ids + */ + protected TroveArrayModifiableDBIDs(DBIDs existing) { + this(existing.size()); + this.addDBIDs(existing); + } + + @Override + protected TIntArrayList getStore() { + return store; + } + + @Override + public boolean addDBIDs(DBIDs ids) { + boolean success = false; + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + success |= store.add(iter.getIntegerID()); + } + return success; + } + + @Override + public boolean removeDBIDs(DBIDs ids) { + boolean success = false; + for(DBID id : ids) { + success |= store.remove(id.getIntegerID()); + } + return success; + } + + @Override + public boolean add(DBID e) { + return store.add(e.getIntegerID()); + } + + @Override + public boolean remove(DBID o) { + return store.remove(o.getIntegerID()); + } + + @Override + public DBID set(int index, DBID element) { + int prev = store.set(index, element.getIntegerID()); + return new IntegerDBID(prev); + } + + @Override + public DBID remove(int index) { + return new IntegerDBID(store.removeAt(index)); + } + + @Override + public void clear() { + store.clear(); + } + + @Override + public void sort() { + store.sort(); + } + + @Override + public void sort(Comparator<? super DBID> comparator) { + // FIXME: optimize, avoid the extra copy. + // Clone data + DBID[] data = new DBID[store.size()]; + for(int i = 0; i < store.size(); i++) { + data[i] = new IntegerDBID(store.get(i)); + } + // Sort + Arrays.sort(data, comparator); + // Copy back + for(int i = 0; i < store.size(); i++) { + store.set(i, data[i].getIntegerID()); + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayStaticDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayStaticDBIDs.java new file mode 100644 index 00000000..53ab34d4 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveArrayStaticDBIDs.java @@ -0,0 +1,53 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import gnu.trove.list.TIntList; +import de.lmu.ifi.dbs.elki.database.ids.ArrayStaticDBIDs; + +/** + * Class accessing a trove int array. + * + * @author Erich Schubert + */ +class TroveArrayStaticDBIDs extends TroveArrayDBIDs implements ArrayStaticDBIDs { + /** + * Actual trove store + */ + private final TIntList store; + + /** + * Constructor. + * + * @param store Actual trove store. + */ + protected TroveArrayStaticDBIDs(TIntList store) { + super(); + this.store = store; + } + + @Override + protected TIntList getStore() { + return store; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java new file mode 100644 index 00000000..11fe669c --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveHashSetModifiableDBIDs.java @@ -0,0 +1,193 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +import java.util.Iterator; + +import gnu.trove.impl.hash.THashPrimitiveIterator; +import gnu.trove.impl.hash.TIntHash; +import gnu.trove.set.hash.TIntHashSet; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDs; +import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +/** + * Implementation using GNU Trove Int Hash Sets. + * + * @author Erich Schubert + * + * @apiviz.has IntegerDBID + * @apiviz.has TroveIteratorAdapter + */ +class TroveHashSetModifiableDBIDs implements HashSetModifiableDBIDs { + /** + * The actual store. + */ + TIntHashSet store; + + /** + * Constructor. + * + * @param size Initial size + */ + protected TroveHashSetModifiableDBIDs(int size) { + super(); + this.store = new TIntHashSet(size); + } + + /** + * Constructor. + */ + protected TroveHashSetModifiableDBIDs() { + super(); + this.store = new TIntHashSet(); + } + + /** + * Constructor. + * + * @param existing Existing IDs + */ + protected TroveHashSetModifiableDBIDs(DBIDs existing) { + this(existing.size()); + this.addDBIDs(existing); + } + + @Override + public DBIDIter iter() { + return new DBIDItr(store); + } + + @Override + public boolean addDBIDs(DBIDs ids) { + boolean success = false; + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + success |= store.add(iter.getIntegerID()); + } + return success; + } + + @Override + public boolean removeDBIDs(DBIDs ids) { + boolean success = false; + for(DBID id : ids) { + success |= store.remove(id.getIntegerID()); + } + return success; + } + + @Override + public boolean add(DBID e) { + return store.add(e.getIntegerID()); + } + + @Override + public boolean remove(DBID o) { + return store.remove(o.getIntegerID()); + } + + @Override + public boolean retainAll(DBIDs set) { + boolean modified = false; + Iterator<DBID> it = iterator(); + while(it.hasNext()) { + if(!set.contains(it.next())) { + it.remove(); + modified = true; + } + } + return modified; + } + + @Override + public Iterator<DBID> iterator() { + return new TroveIteratorAdapter(store.iterator()); + } + + @Override + public int size() { + return store.size(); + } + + @Override + public boolean isEmpty() { + return store.isEmpty(); + } + + @Override + public void clear() { + store.clear(); + } + + @Override + public boolean contains(DBID o) { + return store.contains(o.getIntegerID()); + } + + /** + * Iterator over trove hashs. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected static class DBIDItr extends THashPrimitiveIterator implements DBIDIter { + /** + * The has we access + */ + private TIntHash hash; + + /** + * Constructor. + * + * @param hash Trove hash + */ + public DBIDItr(TIntHash hash) { + super(hash); + this.hash = hash; + this._index = nextIndex(); // Find first element + } + + @Override + public boolean valid() { + return _index >= 0; + } + + @Override + public void advance() { + this._index = nextIndex(); + } + + @Override + public int getIntegerID() { + return hash._set[_index]; + } + + @Override + public DBID getDBID() { + return new IntegerDBID(hash._set[_index]); + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveIteratorAdapter.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveIteratorAdapter.java new file mode 100644 index 00000000..2f596f47 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/TroveIteratorAdapter.java @@ -0,0 +1,66 @@ +package de.lmu.ifi.dbs.elki.database.ids.integer; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import gnu.trove.iterator.TIntIterator; + +import java.util.Iterator; + +import de.lmu.ifi.dbs.elki.database.ids.DBID; + +/** + * Adapter for using GNU Trove iterators. + * + * @author Erich Schubert + */ +class TroveIteratorAdapter implements Iterator<DBID> { + /** + * The actual iterator. + */ + private TIntIterator iterator; + + /** + * Constructor. + * + * @param iterator Trove iterator + */ + protected TroveIteratorAdapter(TIntIterator iterator) { + this.iterator = iterator; + } + + @Override + public boolean hasNext() { + return iterator.hasNext(); + } + + @Override + public DBID next() { + return new IntegerDBID(iterator.next()); + } + + @Override + public void remove() { + iterator.remove(); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/database/ids/integer/package-info.java b/src/de/lmu/ifi/dbs/elki/database/ids/integer/package-info.java index d7ab7304..2508c930 100644 --- a/src/de/lmu/ifi/dbs/elki/database/ids/integer/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/database/ids/integer/package-info.java @@ -10,7 +10,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2011 +Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team |