diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap')
11 files changed, 1072 insertions, 495 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoublePriorityObject.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoublePriorityObject.java new file mode 100644 index 00000000..976a4d0c --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoublePriorityObject.java @@ -0,0 +1,127 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; + +/* + 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.utilities.pairs.PairInterface; + +/** + * Object for a priority queue with integer priority. Can be used in the + * {@link de.lmu.ifi.dbs.elki.utilities.datastructures.heap.UpdatableHeap + * UpdatableHeap}, since hashcode and equality use the stored objects only, not + * the priority. + * + * @author Erich Schubert + * + * @param <O> Stored object type. + */ +public class DoublePriorityObject<O> implements PairInterface<Double, O>, Comparable<DoublePriorityObject<?>> { + /** + * Priority. + */ + double priority; + + /** + * Stored object. Private; since changing this will break an + * {@link de.lmu.ifi.dbs.elki.utilities.datastructures.heap.UpdatableHeap + * UpdatableHeap}s Hash Map! + */ + private O object; + + /** + * Constructor. + * + * @param priority Priority + * @param object Payload + */ + public DoublePriorityObject(double priority, O object) { + super(); + this.priority = priority; + this.object = object; + } + + /** + * Get the priority. + * + * @return Priority + */ + public double getPriority() { + return priority; + } + + /** + * Get the stored object payload + * + * @return object data + */ + public O getObject() { + return object; + } + + @Override + public Double getFirst() { + return priority; + } + + @Override + public O getSecond() { + return object; + } + + @Override + public int hashCode() { + return ((object == null) ? 0 : object.hashCode()); + } + + @Override + public boolean equals(Object obj) { + if(this == obj) { + return true; + } + if(obj == null) { + return false; + } + if(!(obj instanceof DoublePriorityObject)) { + return false; + } + DoublePriorityObject<?> other = (DoublePriorityObject<?>) obj; + if(object == null) { + return (other.object == null); + } + else { + return object.equals(other.object); + } + } + + @Override + public int compareTo(DoublePriorityObject<?> o) { + return Double.compare(o.priority, this.priority); + } + + @Override + public String toString() { + StringBuffer buf = new StringBuffer(); + buf.append(priority).append(":").append(object.toString()); + return buf.toString(); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/Heap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/Heap.java index 307e3ecc..307a0807 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/Heap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/Heap.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; 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,14 +27,22 @@ import java.io.Serializable; import java.util.AbstractQueue; import java.util.ArrayList; import java.util.Arrays; +import java.util.Collection; import java.util.Comparator; import java.util.ConcurrentModificationException; import java.util.Iterator; import java.util.NoSuchElementException; +import de.lmu.ifi.dbs.elki.math.MathUtil; + /** - * Basic in-memory heap structure. Closely related to a {@link java.util.PriorityQueue}, - * but here we can override methods to obtain e.g. a {@link TopBoundedHeap} + * Basic in-memory heap structure. Closely related to a + * {@link java.util.PriorityQueue}, but here we can override methods to obtain + * e.g. a {@link TopBoundedHeap} + * + * Additionally, this heap is built lazily: if you first add many elements, then + * poll the heap, it will be bulk-loaded in O(n) instead of iteratively built in + * O(n log n). This is implemented via a simple validTo counter. * * @author Erich Schubert * @@ -49,11 +57,8 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { /** * Heap storage - * - * Note: keep private; all write access should be done through - * {@link #putInQueue} for subclasses to track! */ - private Object[] queue; + protected transient Object[] queue; /** * Current number of objects @@ -61,9 +66,14 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { protected int size = 0; /** + * Indicate up to where the heap is valid + */ + protected int validSize = 0; + + /** * The comparator or {@code null} */ - private final Comparator<? super E> comparator; + protected final Comparator<Object> comparator; /** * (Structural) modification counter. Used to invalidate iterators. @@ -106,230 +116,288 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { * @param size initial capacity * @param comparator Comparator */ + @SuppressWarnings("unchecked") public Heap(int size, Comparator<? super E> comparator) { super(); this.size = 0; this.queue = new Object[size]; - this.comparator = comparator; + this.comparator = (Comparator<Object>) comparator; + } + + @Override + public boolean add(E e) { + // Never full - overriding probably slightly faster + return offer(e); } @Override - public synchronized boolean offer(E e) { + public boolean offer(E e) { // resize when needed - considerResize(size + 1); - final int parent = parent(size); - // append element - modCount++; - putInQueue(size, e); - this.size = size + 1; - heapifyUp(parent); + if(size + 1 > queue.length) { + resize(size + 1); + } + // final int pos = size; + this.queue[size] = e; + this.size += 1; + heapifyUp(size - 1, e); + validSize += 1; // We have changed - return true according to {@link Collection#put} + modCount++; return true; } @Override - public synchronized E peek() { + public E peek() { if(size == 0) { return null; } + ensureValid(); return castQueueElement(0); } @Override public E poll() { + ensureValid(); return removeAt(0); } /** + * Repair the heap + */ + protected void ensureValid() { + if(validSize != size) { + if(size > 1) { + // Bottom up heap update. + if(comparator != null) { + // Parent of first invalid + int nextmin = validSize > 0 ? ((validSize - 1) >>> 1) : 0; + int curmin = MathUtil.nextAllOnesInt(nextmin); // Next line + int nextmax = curmin - 1; // End of valid line + int pos = (size - 2) >>> 1; // Parent of last element + // System.err.println(validSize+"<="+size+" iter:"+pos+"->"+curmin+", "+nextmin); + while(pos >= nextmin) { + // System.err.println(validSize+"<="+size+" iter:"+pos+"->"+curmin); + while(pos >= curmin) { + if(!heapifyDownComparator(pos, queue[pos])) { + final int parent = (pos - 1) >>> 1; + if(parent < curmin) { + nextmin = Math.min(nextmin, parent); + nextmax = Math.max(nextmax, parent); + } + } + pos--; + } + curmin = nextmin; + pos = Math.min(pos, nextmax); + nextmax = -1; + } + } + else { + // Parent of first invalid + int nextmin = validSize > 0 ? ((validSize - 1) >>> 1) : 0; + int curmin = MathUtil.nextAllOnesInt(nextmin); // Next line + int nextmax = curmin - 1; // End of valid line + int pos = (size - 2) >>> 1; // Parent of last element + // System.err.println(validSize+"<="+size+" iter:"+pos+"->"+curmin+", "+nextmin); + while(pos >= nextmin) { + // System.err.println(validSize+"<="+size+" iter:"+pos+"->"+curmin); + while(pos >= curmin) { + if(!heapifyDownComparable(pos, queue[pos])) { + final int parent = (pos - 1) >>> 1; + if(parent < curmin) { + nextmin = Math.min(nextmin, parent); + nextmax = Math.max(nextmax, parent); + } + } + pos--; + } + curmin = nextmin; + pos = Math.min(pos, nextmax); + nextmax = -1; + } + } + } + validSize = size; + } + } + + /** * Remove the element at the given position. * * @param pos Element position. */ - protected synchronized E removeAt(int pos) { + protected E removeAt(int pos) { if(pos < 0 || pos >= size) { return null; } + final E ret = castQueueElement(pos); + // Replacement object: + final Object reinsert = queue[size - 1]; + queue[size - 1] = null; + // Keep heap in sync + if(validSize == size) { + size -= 1; + validSize -= 1; + heapifyDown(pos, reinsert); + } + else { + size -= 1; + validSize = Math.min(pos >>> 1, validSize); + queue[pos] = reinsert; + } modCount++; - E ret = castQueueElement(0); - // remove! - putInQueue(pos, queue[size - 1]); - size = size - 1; - // avoid dangling references! - putInQueue(size, null); - heapifyDown(pos); return ret; } /** - * Compute parent index in heap array. - * - * @param pos Element index - * @return Parent index - */ - private int parent(int pos) { - return (pos - 1) / 2; - } - - /** - * Compute left child index in heap array. + * Execute a "Heapify Upwards" aka "SiftUp". Used in insertions. * - * @param pos Element index - * @return left child index + * @param pos insertion position + * @param elem Element to insert */ - private int leftChild(int pos) { - return 2 * pos + 1; + protected void heapifyUp(int pos, E elem) { + assert (pos < size && pos >= 0); + if(comparator != null) { + heapifyUpComparator(pos, elem); + } + else { + heapifyUpComparable(pos, elem); + } } /** - * Compute right child index in heap array. + * Execute a "Heapify Upwards" aka "SiftUp". Used in insertions. * - * @param pos Element index - * @return right child index + * @param pos insertion position + * @param elem Element to insert */ - private int rightChild(int pos) { - return 2 * pos + 2; + @SuppressWarnings("unchecked") + protected void heapifyUpComparable(int pos, Object elem) { + final Comparable<Object> cur = (Comparable<Object>) elem; // queue[pos]; + while(pos > 0) { + final int parent = (pos - 1) >>> 1; + Object par = queue[parent]; + + if(cur.compareTo(par) >= 0) { + break; + } + queue[pos] = par; + pos = parent; + } + queue[pos] = cur; } /** * Execute a "Heapify Upwards" aka "SiftUp". Used in insertions. * * @param pos insertion position + * @param cur Element to insert */ - protected void heapifyUp(int pos) { - if(pos < 0 || pos >= size) { - return; - } - // precondition: both child trees are already sorted. - final int parent = parent(pos); - final int lchild = leftChild(pos); - final int rchild = rightChild(pos); - - int min = pos; - if(lchild < size) { - if(compare(min, lchild) > 0) { - min = lchild; - } - } - if(rchild < size) { - if(compare(min, rchild) > 0) { - min = rchild; + protected void heapifyUpComparator(int pos, Object cur) { + while(pos > 0) { + final int parent = (pos - 1) >>> 1; + Object par = queue[parent]; + + if(comparator.compare(cur, par) >= 0) { + break; } + queue[pos] = par; + pos = parent; } - if(min != pos) { - swap(pos, min); - heapifyUp(parent); - } - } - - /** - * Start a heapify up at the parent of this node, since we've changed a child - * - * @param pos Position to start the modification. - */ - protected void heapifyUpParent(int pos) { - heapifyUp(parent(pos)); + queue[pos] = cur; } /** * Execute a "Heapify Downwards" aka "SiftDown". Used in deletions. * * @param pos re-insertion position + * @param reinsert Object to reinsert + * @return true when the order was changed */ - protected void heapifyDown(int pos) { - if(pos < 0 || pos >= size) { - return; - } - final int lchild = leftChild(pos); - final int rchild = rightChild(pos); - - int min = pos; - if(lchild < size) { - if(compare(min, lchild) > 0) { - min = lchild; - } - } - if(rchild < size) { - if(compare(min, rchild) > 0) { - min = rchild; - } + protected boolean heapifyDown(int pos, Object reinsert) { + assert (pos >= 0); + if(comparator != null) { + return heapifyDownComparator(pos, reinsert); } - if(min != pos) { - // swap with minimal element - swap(pos, min); - // recurse down - heapifyDown(min); + else { + return heapifyDownComparable(pos, reinsert); } } /** - * Put an element into the queue at a given position. This allows subclasses - * to index the queue. - * - * @param index Index - * @param e Element - */ - protected void putInQueue(int index, Object e) { - queue[index] = e; - } - - /** - * Swap two elements in the heap. + * Execute a "Heapify Downwards" aka "SiftDown". Used in deletions. * - * @param a Element - * @param b Element + * @param ipos re-insertion position + * @return true when the order was changed */ - protected void swap(int a, int b) { - Object oa = queue[a]; - Object ob = queue[b]; - putInQueue(a, ob); - putInQueue(b, oa); - modCount++; - } - @SuppressWarnings("unchecked") - protected int compare(int pos1, int pos2) { - if(comparator != null) { - return comparator.compare(castQueueElement(pos1), castQueueElement(pos2)); - } - try { - Comparable<E> c = (Comparable<E>) castQueueElement(pos1); - return c.compareTo(castQueueElement(pos2)); - } - catch(ClassCastException e) { - throw e; - } - } + protected boolean heapifyDownComparable(final int ipos, Object reinsert) { + Comparable<Object> cur = (Comparable<Object>) reinsert; + int pos = ipos; + final int half = size >>> 1; + while(pos < half) { + // Get left child (must exist!) + int cpos = (pos << 1) + 1; + Object child = queue[cpos]; + // Test right child, if present + final int rchild = cpos + 1; + if(rchild < size) { + Object right = queue[rchild]; + if(((Comparable<Object>) child).compareTo(right) > 0) { + cpos = rchild; + child = right; + } + } - @SuppressWarnings("unchecked") - protected int compareExternal(E o1, int pos2) { - if(comparator != null) { - return comparator.compare(o1, castQueueElement(pos2)); - } - try { - Comparable<E> c = (Comparable<E>) o1; - return c.compareTo(castQueueElement(pos2)); - } - catch(ClassCastException e) { - throw e; + if(cur.compareTo(child) <= 0) { + break; + } + queue[pos] = child; + pos = cpos; } + queue[pos] = cur; + return (pos == ipos); } - @SuppressWarnings("unchecked") - protected int compareExternalExternal(E o1, E o2) { - if(comparator != null) { - return comparator.compare(o1, o2); - } - try { - Comparable<E> c = (Comparable<E>) o1; - return c.compareTo(o2); - } - catch(ClassCastException e) { - throw e; + /** + * Execute a "Heapify Downwards" aka "SiftDown". Used in deletions. + * + * @param ipos re-insertion position + * @return true when the order was changed + */ + protected boolean heapifyDownComparator(final int ipos, Object cur) { + int pos = ipos; + final int half = size >>> 1; + while(pos < half) { + int min = pos; + Object best = cur; + + final int lchild = (pos << 1) + 1; + Object left = queue[lchild]; + if(comparator.compare(best, left) > 0) { + min = lchild; + best = left; + } + final int rchild = lchild + 1; + if(rchild < size) { + Object right = queue[rchild]; + if(comparator.compare(best, right) > 0) { + min = rchild; + best = right; + } + } + if(min == pos) { + break; + } + queue[pos] = best; + pos = min; } + queue[pos] = cur; + return (pos == ipos); } @SuppressWarnings("unchecked") - protected E castQueueElement(int n) { + protected final E castQueueElement(int n) { return (E) queue[n]; } @@ -343,46 +411,28 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { * * @param requiredSize required capacity */ - private void considerResize(int requiredSize) { - if(requiredSize > queue.length) { - // Double until 64, then increase by 50% each time. - int newCapacity = ((queue.length < 64) ? ((queue.length + 1) * 2) : ((queue.length / 2) * 3)); - // overflow? - if(newCapacity < 0) { - newCapacity = Integer.MAX_VALUE; - } - if(requiredSize > newCapacity) { - newCapacity = requiredSize; - } - grow(newCapacity); - } - } - - /** - * Execute the actual resize operation. - * - * @param newsize New size - */ - private void grow(int newsize) { - // check for overflows - if(newsize < 0) { + protected final void resize(int requiredSize) { + // Double until 64, then increase by 50% each time. + int newCapacity = ((queue.length < 64) ? ((queue.length + 1) * 2) : ((queue.length / 2) * 3)); + // overflow? + if(newCapacity < 0) { throw new OutOfMemoryError(); } - if(newsize == queue.length) { - return; + if(requiredSize > newCapacity) { + newCapacity = requiredSize; } - modCount++; - queue = Arrays.copyOf(queue, newsize); + queue = Arrays.copyOf(queue, newCapacity); } @Override public void clear() { - modCount++; // clean up references in the array for memory management for(int i = 0; i < size; i++) { queue[i] = null; } this.size = 0; + this.validSize = -1; + modCount++; } @Override @@ -398,13 +448,26 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { return false; } - // TODO: bulk add implementation of addAll? - @Override public Iterator<E> iterator() { return new Itr(); } + @Override + public boolean addAll(Collection<? extends E> c) { + final int addsize = c.size(); + if(addsize <= 0) { + return false; + } + if(size + addsize > queue.length) { + resize(size + addsize); + } + for(E elem : c) { + add(elem); + } + return true; + } + /** * Iterator over queue elements. No particular order (i.e. heap order!) * @@ -453,10 +516,10 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { expectedModCount = modCount; } } - + /** - * Return the heap as a sorted array list, by repeated polling. - * This will empty the heap! + * Return the heap as a sorted array list, by repeated polling. This will + * empty the heap! * * @return new array list */ @@ -467,4 +530,34 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { } return ret; } + + /** + * Test whether the heap is still valid. + * + * Debug method. + * + * @return {@code null} when the heap is correct + */ + protected String checkHeap() { + ensureValid(); + if(comparator == null) { + for(int i = 1; i < size; i++) { + final int parent = (i - 1) >>> 1; + @SuppressWarnings("unchecked") + Comparable<Object> po = (Comparable<Object>) queue[parent]; + if(po.compareTo(queue[i]) > 0) { + return "@" + parent + ": " + queue[parent] + " < @" + i + ": " + queue[i]; + } + } + } + else { + for(int i = 1; i < size; i++) { + final int parent = (i - 1) >>> 1; + if(comparator.compare(queue[parent], queue[i]) > 0) { + return "@" + parent + ": " + queue[parent] + " < @" + i + ": " + queue[i]; + } + } + } + return null; + } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerPriorityObject.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerPriorityObject.java index 0bfa8a90..9dd941ec 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerPriorityObject.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerPriorityObject.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; 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,8 +27,9 @@ import de.lmu.ifi.dbs.elki.utilities.pairs.PairInterface; /** * Object for a priority queue with integer priority. Can be used in the - * {@link de.lmu.ifi.dbs.elki.utilities.datastructures.heap.UpdatableHeap UpdatableHeap}, since hashcode and equality use the stored objects - * only, not the priority. + * {@link de.lmu.ifi.dbs.elki.utilities.datastructures.heap.UpdatableHeap + * UpdatableHeap}, since hashcode and equality use the stored objects only, not + * the priority. * * @author Erich Schubert * @@ -42,13 +43,14 @@ public class IntegerPriorityObject<O> implements PairInterface<Integer, O>, Comp /** * Stored object. Private; since changing this will break an - * {@link de.lmu.ifi.dbs.elki.utilities.datastructures.heap.UpdatableHeap UpdatableHeap}s Hash Map! + * {@link de.lmu.ifi.dbs.elki.utilities.datastructures.heap.UpdatableHeap + * UpdatableHeap}s Hash Map! */ private O object; /** * Constructor. - * + * * @param priority Priority * @param object Payload */ @@ -115,4 +117,11 @@ public class IntegerPriorityObject<O> implements PairInterface<Integer, O>, Comp public int compareTo(IntegerPriorityObject<?> o) { return o.priority - this.priority; } + + @Override + public String toString() { + StringBuffer buf = new StringBuffer(); + buf.append(priority).append(":").append(object.toString()); + return buf.toString(); + } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/KNNHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/KNNHeap.java index 9f2d29f3..a1706c84 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/KNNHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/KNNHeap.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; 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 @@ -87,7 +87,7 @@ public class KNNHeap<D extends Distance<D>> extends TiedTopBoundedHeap<DistanceR * @return KNNList with the heaps contents. */ public KNNList<D> toKNNList() { - return new KNNList<D>(this, maxdist); + return new KNNList<D>(this); } /** diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/KNNList.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/KNNList.java index 02a5264c..b19612f2 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/KNNList.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/KNNList.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; 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 @@ -23,15 +23,15 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.AbstractList; -import java.util.ArrayList; -import java.util.Collection; +import java.util.AbstractCollection; import java.util.Iterator; import java.util.List; +import java.util.Queue; 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.query.DistanceResultPair; +import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult; +import de.lmu.ifi.dbs.elki.database.query.knn.KNNUtil; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; /** @@ -39,49 +39,60 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * * @author Erich Schubert * - * @apiviz.composedOf DBIDItr - * @apiviz.composedOf DBIDView - * @apiviz.composedOf DistanceItr - * @apiviz.composedOf DistanceView - * - * @param <D> + * @param <D> Distance type */ -public class KNNList<D extends Distance<D>> extends ArrayList<DistanceResultPair<D>> { - /** - * Serial ID - */ - private static final long serialVersionUID = 1L; - +public class KNNList<D extends Distance<D>> extends AbstractCollection<DistanceResultPair<D>> implements KNNResult<D> { /** * The value of k this was materialized for. */ private final int k; /** - * The maximum distance to return if size() < k + * The actual data array. */ - private final D maxdist; + private final Object[] data; /** - * Constructor, to be called from KNNHeap only! + * Constructor, to be called from KNNHeap only. Use {@link KNNHeap#toKNNList} + * instead! * - * @param heap Calling heap. - * @param maxdist infinite distance to return. + * @param heap Calling heap */ - protected KNNList(KNNHeap<D> heap, D maxdist) { - super(heap.size()); + protected KNNList(KNNHeap<D> heap) { + super(); + this.data = new Object[heap.size()]; this.k = heap.getK(); - this.maxdist = maxdist; + assert(heap.size() >= this.k) : "Heap doesn't contain enough objects!"; // Get sorted data from heap; but in reverse. - int i; - for(i = 0; i < heap.size(); i++) { - super.add(null); + int i = heap.size(); + while(!heap.isEmpty()) { + i--; + assert (i >= 0); + data[i] = heap.poll(); } + assert (data.length == 0 || data[0] != null); + assert (heap.size() == 0); + } + + /** + * Constructor. With a KNNHeap, use {@link KNNHeap#toKNNList} instead! + * + * @param heap Calling heap + * @param k K value + */ + public KNNList(Queue<D> heap, int k) { + super(); + this.data = new Object[heap.size()]; + this.k = k; + assert(heap.size() >= this.k) : "Heap doesn't contain enough objects!"; + // Get sorted data from heap; but in reverse. + int i = heap.size(); while(!heap.isEmpty()) { i--; assert (i >= 0); - super.set(i, heap.poll()); + data[i] = heap.poll(); } + assert (data.length == 0 || data[0] != null); assert (heap.size() == 0); } @@ -99,30 +110,19 @@ public class KNNList<D extends Distance<D>> extends ArrayList<DistanceResultPair * * @return Maximum distance */ + @Override public D getKNNDistance() { - if(size() < getK()) { - return maxdist; - } return get(getK() - 1).getDistance(); } /** - * Get maximum distance in list - */ - public D getMaximumDistance() { - if(isEmpty()) { - return maxdist; - } - return get(size() - 1).getDistance(); - } - - /** * View as ArrayDBIDs * * @return Static DBIDs */ + @Override public ArrayDBIDs asDBIDs() { - return new DBIDView(this); + return KNNUtil.asDBIDs(this); } /** @@ -130,221 +130,73 @@ public class KNNList<D extends Distance<D>> extends ArrayList<DistanceResultPair * * @return List of distances view */ + @Override public List<D> asDistanceList() { - return new DistanceView<D>(this); + return KNNUtil.asDistanceList(this); } /* Make the list unmodifiable! */ @Override - public boolean add(DistanceResultPair<D> e) { - throw new UnsupportedOperationException(); - } - - @Override - public void add(int index, DistanceResultPair<D> element) { - throw new UnsupportedOperationException(); - } - - @Override - public boolean addAll(Collection<? extends DistanceResultPair<D>> c) { - throw new UnsupportedOperationException(); - } - + public String toString() { + StringBuffer buf = new StringBuffer(); + buf.append("kNNList["); + Iterator<DistanceResultPair<D>> iter = this.iterator(); + while(iter.hasNext()) { + DistanceResultPair<D> pair = iter.next(); + buf.append(pair.getDistance()).append(":").append(pair.getDBID()); + if(iter.hasNext()) { + buf.append(","); + } + } + buf.append("]"); + return buf.toString(); + } + + @SuppressWarnings("unchecked") @Override - public boolean addAll(int index, Collection<? extends DistanceResultPair<D>> c) { - throw new UnsupportedOperationException(); + public DistanceResultPair<D> get(int index) { + return (DistanceResultPair<D>) data[index]; } @Override - public void clear() { - throw new UnsupportedOperationException(); + public Iterator<DistanceResultPair<D>> iterator() { + return new Itr(); } @Override - public DistanceResultPair<D> remove(int index) { - throw new UnsupportedOperationException(); - } - - @Override - public boolean remove(Object o) { - throw new UnsupportedOperationException(); - } - - @Override - public DistanceResultPair<D> set(int index, DistanceResultPair<D> element) { - throw new UnsupportedOperationException(); - } - - @Override - public void trimToSize() { - throw new UnsupportedOperationException(); + public int size() { + return data.length; } /** - * Proxy iterator for accessing DBIDs. + * Iterator * * @author Erich Schubert - */ - protected static class DBIDItr implements Iterator<DBID> { - /** - * The real iterator. - */ - Iterator<? extends DistanceResultPair<?>> itr; - - /** - * Constructor. - */ - protected DBIDItr(Iterator<? extends DistanceResultPair<?>> itr) { - super(); - this.itr = itr; - } - - @Override - public boolean hasNext() { - return itr.hasNext(); - } - - @Override - public DBID next() { - return itr.next().getDBID(); - } - - @Override - public void remove() { - itr.remove(); - } - } - - /** - * A view on the DBIDs of the result * - * @author Erich Schubert + * @apiviz.exclude */ - protected static class DBIDView extends AbstractList<DBID> implements ArrayDBIDs { + private class Itr implements Iterator<DistanceResultPair<D>> { /** - * The true list. + * Cursor position */ - final List<? extends DistanceResultPair<?>> parent; - - /** - * Constructor. - * - * @param parent Owner - */ - public DBIDView(List<? extends DistanceResultPair<?>> parent) { - super(); - this.parent = parent; - } - - @Override - public DBID get(int i) { - return parent.get(i).getDBID(); - } - - @Override - public Collection<DBID> asCollection() { - return this; - } - - @Override - public Iterator<DBID> iterator() { - return new DBIDItr(parent.iterator()); - } - - @Override - public int size() { - return parent.size(); - } - } - - /** - * Proxy iterator for accessing DBIDs. - * - * @author Erich Schubert - */ - protected static class DistanceItr<D extends Distance<D>> implements Iterator<D> { - /** - * The real iterator. - */ - Iterator<? extends DistanceResultPair<D>> itr; - - /** - * Constructor. - */ - protected DistanceItr(Iterator<? extends DistanceResultPair<D>> itr) { - super(); - this.itr = itr; - } + private int pos = -1; @Override public boolean hasNext() { - return itr.hasNext(); + return pos + 1 < data.length; } + @SuppressWarnings("unchecked") @Override - public D next() { - return itr.next().getDistance(); + public DistanceResultPair<D> next() { + pos++; + return (DistanceResultPair<D>) data[pos]; } @Override public void remove() { - itr.remove(); - } - } - - /** - * A view on the Distances of the result - * - * @author Erich Schubert - */ - protected static class DistanceView<D extends Distance<D>> extends AbstractList<D> implements List<D> { - /** - * The true list. - */ - final List<? extends DistanceResultPair<D>> parent; - - /** - * Constructor. - * - * @param parent Owner - */ - public DistanceView(List<? extends DistanceResultPair<D>> parent) { - super(); - this.parent = parent; + throw new UnsupportedOperationException("kNN results are unmodifiable."); } - - @Override - public D get(int i) { - return parent.get(i).getDistance(); - } - - @Override - public Iterator<D> iterator() { - return new DistanceItr<D>(parent.iterator()); - } - - @Override - public int size() { - return parent.size(); - } - } - - /** - * View as ArrayDBIDs - * - * @return Static DBIDs - */ - public static ArrayDBIDs asDBIDs(List<? extends DistanceResultPair<?>> list) { - return new DBIDView(list); - } - - /** - * View as list of distances - * - * @return List of distances view - */ - public static <D extends Distance<D>> List<D> asDistanceList(List<? extends DistanceResultPair<D>> list) { - return new DistanceView<D>(list); } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TiedTopBoundedHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TiedTopBoundedHeap.java index ba4307b1..c0ce3acf 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TiedTopBoundedHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TiedTopBoundedHeap.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; 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 @@ -23,15 +23,17 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; along with this program. If not, see <http://www.gnu.org/licenses/>. */ +import java.util.ArrayList; import java.util.Comparator; import java.util.Iterator; -import java.util.LinkedList; +import java.util.List; import de.lmu.ifi.dbs.elki.utilities.iterator.MergedIterator; /** - * A size-limited heap similar to {@link TopBoundedHeap}, discarding elements with - * the highest value. However, this variation keeps a list of tied elements. + * A size-limited heap similar to {@link TopBoundedHeap}, discarding elements + * with the highest value. However, this variation keeps a list of tied + * elements. * * @author Erich Schubert * @@ -46,7 +48,7 @@ public class TiedTopBoundedHeap<E> extends TopBoundedHeap<E> { /** * List to keep ties in. */ - private LinkedList<E> ties = new LinkedList<E>(); + private List<E> ties = new ArrayList<E>(); /** * Constructor with comparator. @@ -90,31 +92,44 @@ public class TiedTopBoundedHeap<E> extends TopBoundedHeap<E> { } @Override - public synchronized E peek() { - if (ties.isEmpty()) { + public E peek() { + if(ties.isEmpty()) { return super.peek(); - } else { - return ties.peek() ; + } + else { + return ties.get(ties.size() - 1); } } @Override public E poll() { - if (ties.isEmpty()) { + if(ties.isEmpty()) { return super.poll(); - } else { - return ties.poll(); + } + else { + return ties.remove(ties.size() - 1); } } @Override protected void handleOverflow(E e) { - if (super.compareExternal(e, 0) == 0) { - if (!ties.isEmpty() && super.compareExternalExternal(e, ties.peek()) < 0) { - ties.clear(); + boolean tied = false; + if(comparator == null) { + @SuppressWarnings("unchecked") + Comparable<Object> c = (Comparable<Object>) e; + if(c.compareTo(queue[0]) == 0) { + tied = true; + } + } + else { + if(comparator.compare(e, queue[0]) == 0) { + tied = true; } + } + if(tied) { ties.add(e); - } else { + } + else { // Also remove old ties. ties.clear(); } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TiedTopBoundedUpdatableHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TiedTopBoundedUpdatableHeap.java new file mode 100644 index 00000000..4fbc852e --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TiedTopBoundedUpdatableHeap.java @@ -0,0 +1,175 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; + +/* + 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.ArrayList; +import java.util.Comparator; +import java.util.Iterator; +import java.util.List; + +import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; +import de.lmu.ifi.dbs.elki.utilities.iterator.MergedIterator; + +/** + * A size-limited heap similar to {@link TopBoundedHeap}, discarding elements + * with the highest value. However, this variation keeps a list of tied + * elements. + * + * @author Erich Schubert + * + * @param <E> Object type + */ +public class TiedTopBoundedUpdatableHeap<E> extends TopBoundedUpdatableHeap<E> { + /** + * Serial version + */ + private static final long serialVersionUID = 1L; + + /** + * List to keep ties in. + */ + private List<E> ties = new ArrayList<E>(); + + /** + * Constructor with comparator. + * + * @param maxsize Maximum size of heap (unless tied) + * @param comparator Comparator + */ + public TiedTopBoundedUpdatableHeap(int maxsize, Comparator<? super E> comparator) { + super(maxsize, comparator); + } + + /** + * Constructor for Comparable objects. + * + * @param maxsize Maximum size of heap (unless tied) + */ + public TiedTopBoundedUpdatableHeap(int maxsize) { + this(maxsize, null); + } + + @Override + public int size() { + return super.size() + ties.size(); + } + + @Override + public void clear() { + super.clear(); + ties.clear(); + } + + @Override + public boolean contains(Object o) { + return ties.contains(o) || super.contains(o); + } + + @SuppressWarnings("unchecked") + @Override + public Iterator<E> iterator() { + return new MergedIterator<E>(ties.iterator(), super.iterator()); + } + + @Override + public boolean offerAt(int pos, E e) { + if(pos == IN_TIES) { + for(Iterator<E> i = ties.iterator(); i.hasNext();) { + E e2 = i.next(); + if(e.equals(e2)) { + if(compare(e, e2) <= 0) { + i.remove(); + index.remove(e2); + } + // while we did not change, this still was "successful". + return true; + } + } + throw new AbortException("Heap corrupt - should not be reached"); + } + // Updated object will be worse than the current ties + if(pos >= 0 && ties.size() > 0 && compare(e, ties.get(0)) < 0) { + removeAt(pos); + index.remove(e); + // assert(checkHeap() == null) : "removeObject broke heap: "+ checkHeap(); + // Move one object back from ties + final E e2 = ties.remove(ties.size() - 1); + // index.remove(e2); + super.offerAt(NO_VALUE, e2); + return true; + } + return super.offerAt(pos, e); + } + + @Override + public E peek() { + if(ties.isEmpty()) { + return super.peek(); + } + else { + return ties.get(ties.size() - 1); + } + } + + @Override + public E poll() { + if(ties.isEmpty()) { + return super.poll(); + } + else { + E e = ties.remove(ties.size() - 1); + index.remove(e); + return e; + } + } + + @Override + protected void handleOverflow(E e) { + boolean tied = false; + if(comparator == null) { + @SuppressWarnings("unchecked") + Comparable<Object> c = (Comparable<Object>) e; + if(c.compareTo(queue[0]) == 0) { + tied = true; + } + } + else { + if(comparator.compare(e, queue[0]) == 0) { + tied = true; + } + } + if(tied) { + ties.add(e); + index.put(e, IN_TIES); + } + else { + index.remove(e); + // Also remove old ties. + for(E e2 : ties) { + index.remove(e2); + } + ties.clear(); + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TopBoundedHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TopBoundedHeap.java index cd7280a5..5b61e6f3 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TopBoundedHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TopBoundedHeap.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; 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 @@ -26,19 +26,20 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; import java.util.Comparator; /** - * Heap class that is bounded in size from the top. - * It will keep the bottom {@code k} Elements only. + * Heap class that is bounded in size from the top. It will keep the bottom + * {@code k} Elements only. * * @author Erich Schubert - * - * @param <E> Element type. Should be {@link Comparable} or a {@link Comparator} needs to be given. + * + * @param <E> Element type. Should be {@link Comparable} or a {@link Comparator} + * needs to be given. */ public class TopBoundedHeap<E> extends Heap<E> { /** * Serial version */ private static final long serialVersionUID = 1L; - + /** * Maximum size */ @@ -62,32 +63,40 @@ public class TopBoundedHeap<E> extends Heap<E> { public TopBoundedHeap(int maxsize, Comparator<? super E> comparator) { super(maxsize + 1, comparator); this.maxsize = maxsize; - assert(maxsize > 0); + assert (maxsize > 0); } @Override public boolean offer(E e) { - // NOTE: we deliberately call super methods here! - // to have the handleOverflow method called consistently. - // don't add if we hit maxsize and are worse - if (super.size() >= maxsize) { - if (super.compareExternal(e, 0) < 0) { - // while we did not change, this still was "successful". - return true; + if(super.size() >= maxsize) { + ensureValid(); + if(comparator == null) { + @SuppressWarnings("unchecked") + Comparable<Object> c = (Comparable<Object>) e; + if(c.compareTo(queue[0]) < 0) { + // while we did not change, this still was "successful". + return true; + } + } + else { + if(comparator.compare(e, queue[0]) < 0) { + // while we did not change, this still was "successful". + return true; + } } } boolean result = super.offer(e); // purge unneeded entry(s) - while (super.size() > maxsize) { + while(super.size() > maxsize) { handleOverflow(super.poll()); } return result; } /** - * Handle an overflow in the structure. - * This function can be overridden to get overflow treatment. + * Handle an overflow in the structure. This function can be overridden to get + * overflow treatment. * * @param e Overflowing element. */ @@ -101,4 +110,4 @@ public class TopBoundedHeap<E> extends Heap<E> { public int getMaxSize() { return maxsize; } -} +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TopBoundedUpdatableHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TopBoundedUpdatableHeap.java new file mode 100644 index 00000000..2b22eba2 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TopBoundedUpdatableHeap.java @@ -0,0 +1,122 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; + +/* + 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; + +/** + * Heap class that is bounded in size from the top. It will keep the bottom + * {@code k} Elements only. + * + * @author Erich Schubert + * + * @param <E> Element type. Should be {@link Comparable} or a {@link Comparator} + * needs to be given. + */ +public class TopBoundedUpdatableHeap<E> extends UpdatableHeap<E> { + /** + * Serial version + */ + private static final long serialVersionUID = 1L; + + /** + * Maximum size + */ + protected int maxsize; + + /** + * Constructor with maximum size only. + * + * @param maxsize Maximum size + */ + public TopBoundedUpdatableHeap(int maxsize) { + this(maxsize, null); + } + + /** + * Constructor with maximum size and {@link Comparator}. + * + * @param maxsize Maximum size + * @param comparator Comparator + */ + public TopBoundedUpdatableHeap(int maxsize, Comparator<? super E> comparator) { + super(maxsize + 1, comparator); + this.maxsize = maxsize; + assert (maxsize > 0); + } + + @Override + public boolean offerAt(int pos, E e) { + // don't add if we hit maxsize and are worse + if(pos == NO_VALUE && super.size() >= maxsize) { + ensureValid(); + if(compare(e, queue[0]) < 0) { + // while we did not change, this still was "successful". + return true; + } + // pos = index.get(e); // Should not be needed. + } + boolean result = super.offerAt(pos, e); + // purge unneeded entry(s) + while(super.size() > maxsize) { + handleOverflow(super.poll()); + } + return result; + } + + /** + * Test if the priority of an object is higher. + * + * @param e New object + * @param object Reference object + * @return True when an update is needed + */ + protected int compare(Object e, Object object) { + if(comparator == null) { + @SuppressWarnings("unchecked") + Comparable<Object> c = (Comparable<Object>) e; + return c.compareTo(queue[0]); + } + else { + return comparator.compare(e, queue[0]); + } + } + + /** + * Handle an overflow in the structure. This function can be overridden to get + * overflow treatment. + * + * @param e Overflowing element. + */ + protected void handleOverflow(E e) { + // index.remove(e); // Should not be needed. + } + + /** + * @return the maximum size + */ + public int getMaxSize() { + return maxsize; + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/UpdatableHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/UpdatableHeap.java index 0ccacadc..745d82cc 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/UpdatableHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/UpdatableHeap.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; 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 @@ -23,8 +23,10 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; along with this program. If not, see <http://www.gnu.org/licenses/>. */ +import gnu.trove.map.TObjectIntMap; +import gnu.trove.map.hash.TObjectIntHashMap; + import java.util.Comparator; -import java.util.HashMap; /** * A heap as used in OPTICS that allows updating entries. @@ -35,6 +37,16 @@ import java.util.HashMap; */ public class UpdatableHeap<O> extends Heap<O> { /** + * Constant for "not in heap" + */ + protected static final int NO_VALUE = Integer.MIN_VALUE; + + /** + * Constant for "in ties list", for tied heaps. + */ + protected static final int IN_TIES = -1; + + /** * Serial version */ private static final long serialVersionUID = 1L; @@ -42,7 +54,7 @@ public class UpdatableHeap<O> extends Heap<O> { /** * Holds the indices in the heap of each element. */ - private HashMap<O, Integer> index = new HashMap<O, Integer>(); + protected final TObjectIntMap<Object> index = new TObjectIntHashMap<Object>(100, 0.5f, NO_VALUE); /** * Simple constructor with default size. @@ -86,60 +98,111 @@ public class UpdatableHeap<O> extends Heap<O> { } @Override - public synchronized boolean offer(O e) { - Integer pos = index.get(e); - if(pos == null) { - // LoggingUtil.logExpensive(Level.INFO, "Inserting: "+e); - // insert - return super.offer(e); + public boolean offer(O e) { + final int pos = index.get(e); + return offerAt(pos, e); + } + + protected boolean offerAt(final int pos, O e) { + if(pos == NO_VALUE) { + // resize when needed + if(size + 1 > queue.length) { + resize(size + 1); + } + // final int pos = size; + this.queue[size] = e; + index.put(e, size); + size += 1; + // We do NOT YET update the heap. This is done lazily. + // We have changed - return true according to {@link Collection#put} + modCount++; + return true; } else { - // update - if(compareExternal(e, pos) < 0) { - // LoggingUtil.logExpensive(Level.INFO, - // "Updating value: "+e+" vs. "+castQueueElement(pos)); - modCount++; - putInQueue(pos, e); - heapifyUpParent(pos); - // We have changed - return true according to {@link Collection#put} - return true; + assert (pos >= 0) : "Unexpected negative position."; + assert (queue[pos].equals(e)); + // Did the value improve? + if(comparator == null) { + @SuppressWarnings("unchecked") + Comparable<Object> c = (Comparable<Object>) e; + if(c.compareTo(queue[pos]) >= 0) { + // Ignore, but return true according to {@link Collection#put} + return true; + } } else { - // LoggingUtil.logExpensive(Level.INFO, - // "Keeping value: "+e+" vs. "+castQueueElement(pos)); - // Ignore, no improvement. Return success anyway. - return true; + if(comparator.compare(e, queue[pos]) >= 0) { + // Ignore, but return true according to {@link Collection#put} + return true; + } } + if(pos >= validSize) { + queue[pos] = e; + // validSize = Math.min(pos, validSize); + } + else { + // ensureValid(); + heapifyUp(pos, e); + } + modCount++; + // We have changed - return true according to {@link Collection#put} + return true; } } @Override - protected void putInQueue(int pos, Object e) { - super.putInQueue(pos, e); - // Keep index up to date - if(e != null) { - O n = castQueueElement(pos); - index.put(n, pos); + protected O removeAt(int pos) { + if(pos < 0 || pos >= size) { + return null; } - } - - @Override - protected synchronized O removeAt(int pos) { - O node = super.removeAt(pos); + final O ret = castQueueElement(pos); + // Replacement object: + final Object reinsert = queue[size - 1]; + queue[size - 1] = null; + // Keep heap in sync? + if(validSize == size) { + size -= 1; + validSize -= 1; + if(comparator != null) { + if(comparator.compare(ret, reinsert) > 0) { + heapifyUpComparator(pos, reinsert); + } + else { + heapifyDownComparator(pos, reinsert); + } + } + else { + @SuppressWarnings("unchecked") + Comparable<Object> comp = (Comparable<Object>) ret; + if(comp.compareTo(reinsert) > 0) { + heapifyUpComparable(pos, reinsert); + } + else { + heapifyDownComparable(pos, reinsert); + } + } + } + else { + size -= 1; + validSize = Math.min(pos >>> 1, validSize); + queue[pos] = reinsert; + index.put(reinsert, pos); + } + modCount++; // Keep index up to date - index.remove(node); - return node; + index.remove(ret); + return ret; } /** * Remove the given object from the queue. * - * @param e Obejct to remove + * @param e Object to remove * @return Existing entry */ public O removeObject(O e) { - Integer pos = index.get(e); - if(pos != null) { + int pos = index.get(e); + if(pos >= 0) { return removeAt(pos); } else { @@ -153,4 +216,116 @@ public class UpdatableHeap<O> extends Heap<O> { index.remove(node); return node; } + + /** + * Execute a "Heapify Upwards" aka "SiftUp". Used in insertions. + * + * @param pos insertion position + * @param elem Element to insert + */ + @SuppressWarnings("unchecked") + protected void heapifyUpComparable(int pos, Object elem) { + final Comparable<Object> cur = (Comparable<Object>) elem; // queue[pos]; + while(pos > 0) { + final int parent = (pos - 1) >>> 1; + Object par = queue[parent]; + + if(cur.compareTo(par) >= 0) { + break; + } + queue[pos] = par; + index.put(par, pos); + pos = parent; + } + queue[pos] = cur; + index.put(cur, pos); + } + + /** + * Execute a "Heapify Upwards" aka "SiftUp". Used in insertions. + * + * @param pos insertion position + * @param cur Element to insert + */ + protected void heapifyUpComparator(int pos, Object cur) { + while(pos > 0) { + final int parent = (pos - 1) >>> 1; + Object par = queue[parent]; + + if(comparator.compare(cur, par) >= 0) { + break; + } + queue[pos] = par; + index.put(par, pos); + pos = parent; + } + queue[pos] = cur; + index.put(cur, pos); + } + + @SuppressWarnings("unchecked") + @Override + protected boolean heapifyDownComparable(final int ipos, Object reinsert) { + Comparable<Object> cur = (Comparable<Object>) reinsert; + int pos = ipos; + final int half = size >>> 1; + while(pos < half) { + // Get left child (must exist!) + int cpos = (pos << 1) + 1; + Object child = queue[cpos]; + // Test right child, if present + final int rchild = cpos + 1; + if(rchild < size) { + Object right = queue[rchild]; + if(((Comparable<Object>) child).compareTo(right) > 0) { + cpos = rchild; + child = right; + } + } + + if(cur.compareTo(child) <= 0) { + break; + } + queue[pos] = child; + index.put(child, pos); + pos = cpos; + } + queue[pos] = cur; + index.put(cur, pos); + return (pos == ipos); + } + + @Override + protected boolean heapifyDownComparator(final int ipos, Object cur) { + int pos = ipos; + final int half = size >>> 1; + while(pos < half) { + int min = pos; + Object best = cur; + + final int lchild = (pos << 1) + 1; + Object left = queue[lchild]; + if(comparator.compare(best, left) > 0) { + min = lchild; + best = left; + } + final int rchild = lchild + 1; + if(rchild < size) { + Object right = queue[rchild]; + if(comparator.compare(best, right) > 0) { + min = rchild; + best = right; + } + } + if(min == pos) { + break; + } + queue[pos] = best; + index.put(best, pos); + pos = min; + } + queue[pos] = cur; + index.put(cur, pos); + return (pos == ipos); + } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/package-info.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/package-info.java index 45259fe7..3f193171 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/package-info.java @@ -5,7 +5,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 |