diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap')
22 files changed, 2159 insertions, 595 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/AbstractHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/AbstractHeap.java new file mode 100644 index 00000000..b6f098e6 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/AbstractHeap.java @@ -0,0 +1,103 @@ +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/>. + */ + +/** + * Abstract base class for heaps. + * + * @author Erich Schubert + */ +public class AbstractHeap { + /** + * Default initial capacity + */ + public static final int DEFAULT_INITIAL_CAPACITY = 11; + + /** + * Current number of objects + */ + public int size = 0; + + /** + * Indicate up to where the heap is valid + */ + public int validSize = 0; + + /** + * (Structural) modification counter. Used to invalidate iterators. + */ + public int modCount = 0; + + /** + * Constructor. + */ + public AbstractHeap() { + super(); + } + + /** + * Query the size + * + * @return Size + */ + public int size() { + return this.size; + } + + /** + * Delete all elements from the heap. + */ + public void clear() { + this.size = 0; + this.validSize = -1; + heapModified(); + } + + /** + * Test whether we need to resize to have the requested capacity. + * + * @param requiredSize required capacity + * @param capacity Current capacity + * @return new capacity + */ + protected final int desiredSize(int requiredSize, int capacity) { + // Double until 64, then increase by 50% each time. + int newCapacity = ((capacity < 64) ? ((capacity + 1) * 2) : ((capacity / 2) * 3)); + // overflow? + if (newCapacity < 0) { + throw new OutOfMemoryError(); + } + if (requiredSize > newCapacity) { + newCapacity = requiredSize; + } + return newCapacity; + } + + /** + * Called at the end of each heap modification. + */ + protected void heapModified() { + modCount++; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparableMaxHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparableMaxHeap.java new file mode 100644 index 00000000..ab8ef1bb --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparableMaxHeap.java @@ -0,0 +1,63 @@ +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/>. + */ + +/** + * Basic in-memory heap structure. + * + * 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 + */ +public class ComparableMaxHeap<K extends Comparable<K>> extends ObjectHeap<K> { + /** + * Constructor with default capacity. + */ + public ComparableMaxHeap() { + super(DEFAULT_INITIAL_CAPACITY); + } + + /** + * Constructor with initial capacity. + * + * @param size initial capacity + */ + public ComparableMaxHeap(int size) { + super(size); + } + + /** + * Compare two objects + * + * @param o1 First object + * @param o2 Second object + */ + @Override + @SuppressWarnings("unchecked") + protected boolean comp(Object o1, Object o2) { + return ((K) o1).compareTo((K) o2) < 0; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparableMinHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparableMinHeap.java new file mode 100644 index 00000000..06d2cb32 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparableMinHeap.java @@ -0,0 +1,63 @@ +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/>. + */ + +/** + * Basic in-memory heap structure. + * + * 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 + */ +public class ComparableMinHeap<K extends Comparable<K>> extends ObjectHeap<K> { + /** + * Constructor with default capacity. + */ + public ComparableMinHeap() { + super(DEFAULT_INITIAL_CAPACITY); + } + + /** + * Constructor with initial capacity. + * + * @param size initial capacity + */ + public ComparableMinHeap(int size) { + super(size); + } + + /** + * Compare two objects + * + * @param o1 First object + * @param o2 Second object + */ + @Override + @SuppressWarnings("unchecked") + protected boolean comp(Object o1, Object o2) { + return ((K) o1).compareTo((K) o2) > 0; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleHeap.java new file mode 100644 index 00000000..f9f928bd --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleHeap.java @@ -0,0 +1,264 @@ +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.Arrays; + +import de.lmu.ifi.dbs.elki.math.MathUtil; + +/** + * Basic in-memory heap structure. + * + * 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 + */ +public abstract class DoubleHeap extends AbstractHeap { + /** + * Heap storage: queue + */ + protected transient double[] queue; + + /** + * Constructor with initial capacity. + * + * @param size initial capacity + */ + public DoubleHeap(int size) { + super(); + this.size = 0; + this.queue = new double[size]; + } + + /** + * Add a key-value pair to the heap + * + * @param key Key + */ + public void add(double key) { + // resize when needed + if (size + 1 > queue.length) { + resize(size + 1); + } + // final int pos = size; + this.queue[size] = key; + this.size += 1; + heapifyUp(size - 1, key); + validSize += 1; + heapModified(); + } + + /** + * Add a key-value pair to the heap, except if the new element is larger than + * the top, and we are at design size (overflow) + * + * @param key Key + * @param max Maximum size of heap + */ + public void add(double key, int max) { + if (size < max) { + add(key); + } else if (comp(key, peek())) { + replaceTopElement(key); + } + } + + /** + * Combined operation that removes the top element, and inserts a new element + * instead. + * + * @param e New element to insert + * @return Previous top element of the heap + */ + public double replaceTopElement(double e) { + ensureValid(); + double oldroot = queue[0]; + heapifyDown(0, e); + heapModified(); + return oldroot; + } + + /** + * Get the current top key + * + * @return Top key + */ + public double peek() { + if (size == 0) { + throw new ArrayIndexOutOfBoundsException("Peek() on an empty heap!"); + } + ensureValid(); + return queue[0]; + } + + /** + * Remove the first element + * + * @return Top element + */ + public double poll() { + return removeAt(0); + } + + /** + * Repair the heap + */ + protected void ensureValid() { + if (validSize != size) { + if (size > 1) { + // 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 (!heapifyDown(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. + * @return Removed element + */ + protected double removeAt(int pos) { + if (pos < 0 || pos >= size) { + return 0.0; + } + final double top = queue[0]; + // Replacement object: + final double reinkey = queue[size - 1]; + // Keep heap in sync + if (validSize == size) { + size -= 1; + validSize -= 1; + heapifyDown(pos, reinkey); + } else { + size -= 1; + validSize = Math.min(pos >>> 1, validSize); + queue[pos] = reinkey; + } + heapModified(); + return top; + } + + /** + * Execute a "Heapify Upwards" aka "SiftUp". Used in insertions. + * + * @param pos insertion position + * @param curkey Current key + */ + protected void heapifyUp(int pos, double curkey) { + while (pos > 0) { + final int parent = (pos - 1) >>> 1; + double parkey = queue[parent]; + + if (comp(curkey, parkey)) { // Compare + break; + } + queue[pos] = parkey; + pos = parent; + } + queue[pos] = curkey; + } + + /** + * Execute a "Heapify Downwards" aka "SiftDown". Used in deletions. + * + * @param ipos re-insertion position + * @param curkey Current key + * @return true when the order was changed + */ + protected boolean heapifyDown(final int ipos, double curkey) { + int pos = ipos; + final int half = size >>> 1; + while (pos < half) { + // Get left child (must exist!) + int cpos = (pos << 1) + 1; + double chikey = queue[cpos]; + // Test right child, if present + final int rchild = cpos + 1; + if (rchild < size) { + double right = queue[rchild]; + if (comp(chikey, right)) { // Compare + cpos = rchild; + chikey = right; + } + } + + if (comp(chikey, curkey)) { // Compare + break; + } + queue[pos] = chikey; + pos = cpos; + } + queue[pos] = curkey; + return (pos == ipos); + } + + /** + * Test whether we need to resize to have the requested capacity. + * + * @param requiredSize required capacity + */ + protected final void resize(int requiredSize) { + queue = Arrays.copyOf(queue, desiredSize(requiredSize, queue.length)); + } + + /** + * Delete all elements from the heap. + */ + @Override + public void clear() { + super.clear(); + for (int i = 0; i < size; i++) { + queue[i] = 0.0; + } + } + + /** + * Compare two objects + */ + abstract protected boolean comp(double o1, double o2); +} diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleMaxHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleMaxHeap.java new file mode 100644 index 00000000..1b7d6037 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleMaxHeap.java @@ -0,0 +1,62 @@ +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/>. + */ + +/** + * Basic in-memory heap structure. + * + * 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 + */ +public class DoubleMaxHeap extends DoubleHeap { + /** + * Constructor with default capacity. + */ + public DoubleMaxHeap() { + super(DEFAULT_INITIAL_CAPACITY); + } + + /** + * Constructor with initial capacity. + * + * @param size initial capacity + */ + public DoubleMaxHeap(int size) { + super(size); + } + + /** + * Compare two objects + * + * @param o1 First object + * @param o2 Second object + */ + @Override + protected boolean comp(double o1, double o2) { + return o1 < o2; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleMinHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleMinHeap.java new file mode 100644 index 00000000..2ce05ff9 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleMinHeap.java @@ -0,0 +1,62 @@ +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/>. + */ + +/** + * Basic in-memory heap structure. + * + * 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 + */ +public class DoubleMinHeap extends DoubleHeap { + /** + * Constructor with default capacity. + */ + public DoubleMinHeap() { + super(DEFAULT_INITIAL_CAPACITY); + } + + /** + * Constructor with initial capacity. + * + * @param size initial capacity + */ + public DoubleMinHeap(int size) { + super(size); + } + + /** + * Compare two objects + * + * @param o1 First object + * @param o2 Second object + */ + @Override + protected boolean comp(double o1, double o2) { + return o1 > o2; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleObjMaxHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleObjMaxHeap.java new file mode 100644 index 00000000..8417309a --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleObjMaxHeap.java @@ -0,0 +1,328 @@ +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.Arrays; +import java.util.Comparator; + +import de.lmu.ifi.dbs.elki.math.MathUtil; + +/** + * Basic in-memory heap structure. + * + * 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 + * + * @param <V> value type + */ +public class DoubleObjMaxHeap<V> { + /** + * Heap storage: keys + */ + protected double[] keys; + + /** + * Heap storage: values + */ + protected Object[] values; + + /** + * Current number of objects + */ + protected int size = 0; + + /** + * Indicate up to where the heap is valid + */ + protected int validSize = 0; + + /** + * (Structural) modification counter. Used to invalidate iterators. + */ + public transient int modCount = 0; + + /** + * Default initial capacity + */ + private static final int DEFAULT_INITIAL_CAPACITY = 11; + + /** + * Default constructor: default capacity, natural ordering. + */ + public DoubleObjMaxHeap() { + this(DEFAULT_INITIAL_CAPACITY); + } + + /** + * Constructor with initial capacity and {@link Comparator}. + * + * @param size initial capacity + */ + public DoubleObjMaxHeap(int size) { + super(); + this.size = 0; + this.keys = new double[size]; + this.values = new Object[size]; + } + + /** + * Add a key-value pair to the heap + * + * @param key Key + * @param val Value + * @return Success code + */ + public boolean add(double key, V val) { + // resize when needed + if(size + 1 > keys.length) { + resize(size + 1); + } + // final int pos = size; + this.keys[size] = key; + this.values[size] = val; + this.size += 1; + heapifyUp(size - 1, key, val); + validSize += 1; + // We have changed - return true according to {@link Collection#put} + modCount++; + return true; + } + + /** + * Get the current top key + * + * @return Top key + */ + public double peekKey() { + if(size == 0) { + throw new ArrayIndexOutOfBoundsException("Peek() on an empty heap!"); + } + ensureValid(); + return keys[0]; + } + + /** + * Get the current top value + * + * @return Value + */ + @SuppressWarnings("unchecked") + public V peekValue() { + if(size == 0) { + throw new ArrayIndexOutOfBoundsException("Peek() on an empty heap!"); + } + ensureValid(); + return (V) values[0]; + } + + /** + * Remove the first element + */ + public void poll() { + removeAt(0); + } + + /** + * Repair the heap + */ + protected void ensureValid() { + if(validSize != size) { + if(size > 1) { + // 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(!heapifyDown(pos, keys[pos], values[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 void removeAt(int pos) { + if(pos < 0 || pos >= size) { + return; + } + // Replacement object: + final double reinkey = keys[size - 1]; + final Object reinval = values[size - 1]; + values[size - 1] = null; + // Keep heap in sync + if(validSize == size) { + size -= 1; + validSize -= 1; + heapifyDown(pos, reinkey, reinval); + } + else { + size -= 1; + validSize = Math.min(pos >>> 1, validSize); + keys[pos] = reinkey; + values[pos] = reinval; + } + modCount++; + } + + /** + * Execute a "Heapify Upwards" aka "SiftUp". Used in insertions. + * + * @param pos insertion position + * @param curkey Current key + * @param curval Current value + */ + protected void heapifyUp(int pos, double curkey, Object curval) { + while(pos > 0) { + final int parent = (pos - 1) >>> 1; + double parkey = keys[parent]; + + if(curkey <= parkey) { // Compare + break; + } + keys[pos] = parkey; + values[pos] = values[parent]; + pos = parent; + } + keys[pos] = curkey; + values[pos] = curval; + } + + /** + * Execute a "Heapify Downwards" aka "SiftDown". Used in deletions. + * + * @param ipos re-insertion position + * @param curkey Current key + * @param curval Current value + * @return true when the order was changed + */ + protected boolean heapifyDown(final int ipos, double curkey, Object curval) { + int pos = ipos; + final int half = size >>> 1; + while(pos < half) { + // Get left child (must exist!) + int cpos = (pos << 1) + 1; + double chikey = keys[cpos]; + Object chival = values[cpos]; + // Test right child, if present + final int rchild = cpos + 1; + if(rchild < size) { + double right = keys[rchild]; + if(chikey < right) { // Compare + cpos = rchild; + chikey = right; + chival = values[rchild]; + } + } + + if(curkey >= chikey) { // Compare + break; + } + keys[pos] = chikey; + values[pos] = chival; + pos = cpos; + } + keys[pos] = curkey; + values[pos] = curval; + return (pos == ipos); + } + + /** + * Query the size + * + * @return Size + */ + public int size() { + return this.size; + } + + /** + * Test whether we need to resize to have the requested capacity. + * + * @param requiredSize required capacity + */ + protected final void resize(int requiredSize) { + // Double until 64, then increase by 50% each time. + int newCapacity = ((keys.length < 64) ? ((keys.length + 1) << 1) : ((keys.length >> 1) * 3)); + // overflow? + if(newCapacity < 0) { + throw new OutOfMemoryError(); + } + if(requiredSize > newCapacity) { + newCapacity = requiredSize; + } + keys = Arrays.copyOf(keys, newCapacity); + values = Arrays.copyOf(values, newCapacity); + } + + /** + * Delete all elements from the heap. + */ + public void clear() { + // clean up references in the array for memory management + Arrays.fill(values, null); + this.size = 0; + this.validSize = -1; + modCount++; + } + + /** + * Test whether the heap is still valid. + * + * Debug method. + * + * @return {@code null} when the heap is correct + */ + protected String checkHeap() { + ensureValid(); + for(int i = 1; i < size; i++) { + final int parent = (i - 1) >>> 1; + if(keys[parent] < keys[i]) { // Compare + return "@" + parent + ": " + keys[parent] + " < @" + i + ": " + keys[i]; + } + } + return null; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleObjMinHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleObjMinHeap.java new file mode 100644 index 00000000..244277e8 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleObjMinHeap.java @@ -0,0 +1,328 @@ +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.Arrays; +import java.util.Comparator; + +import de.lmu.ifi.dbs.elki.math.MathUtil; + +/** + * Basic in-memory heap structure. + * + * 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 + * + * @param <V> value type + */ +public class DoubleObjMinHeap<V> { + /** + * Heap storage: keys + */ + protected double[] keys; + + /** + * Heap storage: values + */ + protected Object[] values; + + /** + * Current number of objects + */ + protected int size = 0; + + /** + * Indicate up to where the heap is valid + */ + protected int validSize = 0; + + /** + * (Structural) modification counter. Used to invalidate iterators. + */ + public transient int modCount = 0; + + /** + * Default initial capacity + */ + private static final int DEFAULT_INITIAL_CAPACITY = 11; + + /** + * Default constructor: default capacity, natural ordering. + */ + public DoubleObjMinHeap() { + this(DEFAULT_INITIAL_CAPACITY); + } + + /** + * Constructor with initial capacity and {@link Comparator}. + * + * @param size initial capacity + */ + public DoubleObjMinHeap(int size) { + super(); + this.size = 0; + this.keys = new double[size]; + this.values = new Object[size]; + } + + /** + * Add a key-value pair to the heap + * + * @param key Key + * @param val Value + * @return Success code + */ + public boolean add(double key, V val) { + // resize when needed + if(size + 1 > keys.length) { + resize(size + 1); + } + // final int pos = size; + this.keys[size] = key; + this.values[size] = val; + this.size += 1; + heapifyUp(size - 1, key, val); + validSize += 1; + // We have changed - return true according to {@link Collection#put} + modCount++; + return true; + } + + /** + * Get the current top key + * + * @return Top key + */ + public double peekKey() { + if(size == 0) { + throw new ArrayIndexOutOfBoundsException("Peek() on an empty heap!"); + } + ensureValid(); + return keys[0]; + } + + /** + * Get the current top value + * + * @return Value + */ + @SuppressWarnings("unchecked") + public V peekValue() { + if(size == 0) { + throw new ArrayIndexOutOfBoundsException("Peek() on an empty heap!"); + } + ensureValid(); + return (V) values[0]; + } + + /** + * Remove the first element + */ + public void poll() { + removeAt(0); + } + + /** + * Repair the heap + */ + protected void ensureValid() { + if(validSize != size) { + if(size > 1) { + // 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(!heapifyDown(pos, keys[pos], values[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 void removeAt(int pos) { + if(pos < 0 || pos >= size) { + return; + } + // Replacement object: + final double reinkey = keys[size - 1]; + final Object reinval = values[size - 1]; + values[size - 1] = null; + // Keep heap in sync + if(validSize == size) { + size -= 1; + validSize -= 1; + heapifyDown(pos, reinkey, reinval); + } + else { + size -= 1; + validSize = Math.min(pos >>> 1, validSize); + keys[pos] = reinkey; + values[pos] = reinval; + } + modCount++; + } + + /** + * Execute a "Heapify Upwards" aka "SiftUp". Used in insertions. + * + * @param pos insertion position + * @param curkey Current key + * @param curval Current value + */ + protected void heapifyUp(int pos, double curkey, Object curval) { + while(pos > 0) { + final int parent = (pos - 1) >>> 1; + double parkey = keys[parent]; + + if(curkey >= parkey) { // Compare + break; + } + keys[pos] = parkey; + values[pos] = values[parent]; + pos = parent; + } + keys[pos] = curkey; + values[pos] = curval; + } + + /** + * Execute a "Heapify Downwards" aka "SiftDown". Used in deletions. + * + * @param ipos re-insertion position + * @param curkey Current key + * @param curval Current value + * @return true when the order was changed + */ + protected boolean heapifyDown(final int ipos, double curkey, Object curval) { + int pos = ipos; + final int half = size >>> 1; + while(pos < half) { + // Get left child (must exist!) + int cpos = (pos << 1) + 1; + double chikey = keys[cpos]; + Object chival = values[cpos]; + // Test right child, if present + final int rchild = cpos + 1; + if(rchild < size) { + double right = keys[rchild]; + if(chikey > right) { // Compare + cpos = rchild; + chikey = right; + chival = values[rchild]; + } + } + + if(curkey <= chikey) { // Compare + break; + } + keys[pos] = chikey; + values[pos] = chival; + pos = cpos; + } + keys[pos] = curkey; + values[pos] = curval; + return (pos == ipos); + } + + /** + * Query the size + * + * @return Size + */ + public int size() { + return this.size; + } + + /** + * Test whether we need to resize to have the requested capacity. + * + * @param requiredSize required capacity + */ + protected final void resize(int requiredSize) { + // Double until 64, then increase by 50% each time. + int newCapacity = ((keys.length < 64) ? ((keys.length + 1) << 1) : ((keys.length >> 1) * 3)); + // overflow? + if(newCapacity < 0) { + throw new OutOfMemoryError(); + } + if(requiredSize > newCapacity) { + newCapacity = requiredSize; + } + keys = Arrays.copyOf(keys, newCapacity); + values = Arrays.copyOf(values, newCapacity); + } + + /** + * Delete all elements from the heap. + */ + public void clear() { + // clean up references in the array for memory management + Arrays.fill(values, null); + this.size = 0; + this.validSize = -1; + modCount++; + } + + /** + * Test whether the heap is still valid. + * + * Debug method. + * + * @return {@code null} when the heap is correct + */ + protected String checkHeap() { + ensureValid(); + for(int i = 1; i < size; i++) { + final int parent = (i - 1) >>> 1; + if(keys[parent] > keys[i]) { // Compare + return "@" + parent + ": " + keys[parent] + " < @" + i + ": " + keys[i]; + } + } + return null; + } +} 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 index 976a4d0c..92d548cb 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoublePriorityObject.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoublePriorityObject.java @@ -79,8 +79,9 @@ public class DoublePriorityObject<O> implements PairInterface<Double, O>, Compar } @Override + @Deprecated public Double getFirst() { - return priority; + return Double.valueOf(priority); } @Override @@ -120,8 +121,8 @@ public class DoublePriorityObject<O> implements PairInterface<Double, O>, Compar @Override public String toString() { - StringBuffer buf = new StringBuffer(); - buf.append(priority).append(":").append(object.toString()); + StringBuilder buf = new StringBuilder(); + 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 307a0807..86d3ae08 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 @@ -23,11 +23,7 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -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; @@ -49,39 +45,34 @@ import de.lmu.ifi.dbs.elki.math.MathUtil; * @param <E> Element type. Should be {@link java.lang.Comparable} or a * {@link java.util.Comparator} needs to be given. */ -public class Heap<E> extends AbstractQueue<E> implements Serializable { +public class Heap<E> implements Iterable<E> { /** - * Serial version - */ - private static final long serialVersionUID = 1L; - - /** - * Heap storage + * Heap storage. */ protected transient Object[] queue; /** - * Current number of objects + * Current number of objects. */ protected int size = 0; /** - * Indicate up to where the heap is valid + * Indicate up to where the heap is valid. */ protected int validSize = 0; /** - * The comparator or {@code null} + * The comparator or {@code null}. */ protected final Comparator<Object> comparator; /** * (Structural) modification counter. Used to invalidate iterators. */ - public transient int modCount = 0; + private transient int modCount = 0; /** - * Default initial capacity + * Default initial capacity. */ private static final int DEFAULT_INITIAL_CAPACITY = 11; @@ -124,16 +115,14 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { this.comparator = (Comparator<Object>) comparator; } - @Override - public boolean add(E e) { - // Never full - overriding probably slightly faster - return offer(e); - } - - @Override - public boolean offer(E e) { + /** + * Add an element to the heap. + * + * @param e Element to add + */ + public void add(E e) { // resize when needed - if(size + 1 > queue.length) { + if (size + 1 > queue.length) { resize(size + 1); } // final int pos = size; @@ -141,46 +130,69 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { this.size += 1; heapifyUp(size - 1, e); validSize += 1; - // We have changed - return true according to {@link Collection#put} - modCount++; - return true; + heapModified(); } - @Override + /** + * Combined operation that removes the top element, and inserts a new element + * instead. + * + * @param e New element to insert + * @return Previous top element of the heap + */ + @SuppressWarnings("unchecked") + public E replaceTopElement(E e) { + ensureValid(); + E oldroot = (E) queue[0]; + heapifyDown(0, e); + heapModified(); + return oldroot; + } + + /** + * Peek at the top element. + * + * @return Top element. + */ + @SuppressWarnings("unchecked") public E peek() { - if(size == 0) { + if (size == 0) { return null; } ensureValid(); - return castQueueElement(0); + return (E) queue[0]; } - @Override + /** + * Remove the top element. + * + * @return Top element. + */ public E poll() { ensureValid(); return removeAt(0); } /** - * Repair the heap + * Perform pending heap repair operations in a single bulk operation. */ protected void ensureValid() { - if(validSize != size) { - if(size > 1) { + if (validSize != size) { + if (size > 1) { // Bottom up heap update. - if(comparator != null) { + 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) { + while (pos >= nextmin) { // System.err.println(validSize+"<="+size+" iter:"+pos+"->"+curmin); - while(pos >= curmin) { - if(!heapifyDownComparator(pos, queue[pos])) { + while (pos >= curmin) { + if (!heapifyDownComparator(pos, queue[pos])) { final int parent = (pos - 1) >>> 1; - if(parent < curmin) { + if (parent < curmin) { nextmin = Math.min(nextmin, parent); nextmax = Math.max(nextmax, parent); } @@ -191,20 +203,19 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { pos = Math.min(pos, nextmax); nextmax = -1; } - } - else { + } 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) { + while (pos >= nextmin) { // System.err.println(validSize+"<="+size+" iter:"+pos+"->"+curmin); - while(pos >= curmin) { - if(!heapifyDownComparable(pos, queue[pos])) { + while (pos >= curmin) { + if (!heapifyDownComparable(pos, queue[pos])) { final int parent = (pos - 1) >>> 1; - if(parent < curmin) { + if (parent < curmin) { nextmin = Math.min(nextmin, parent); nextmax = Math.max(nextmax, parent); } @@ -225,27 +236,28 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { * Remove the element at the given position. * * @param pos Element position. + * @return Element that was at this position. */ + @SuppressWarnings("unchecked") protected E removeAt(int pos) { - if(pos < 0 || pos >= size) { + if (pos < 0 || pos >= size) { return null; } - final E ret = castQueueElement(pos); + final E ret = (E) queue[pos]; // Replacement object: final Object reinsert = queue[size - 1]; queue[size - 1] = null; // Keep heap in sync - if(validSize == size) { + if (validSize == size) { size -= 1; validSize -= 1; heapifyDown(pos, reinsert); - } - else { + } else { size -= 1; validSize = Math.min(pos >>> 1, validSize); queue[pos] = reinsert; } - modCount++; + heapModified(); return ret; } @@ -257,10 +269,9 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { */ protected void heapifyUp(int pos, E elem) { assert (pos < size && pos >= 0); - if(comparator != null) { + if (comparator != null) { heapifyUpComparator(pos, elem); - } - else { + } else { heapifyUpComparable(pos, elem); } } @@ -274,11 +285,11 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { @SuppressWarnings("unchecked") protected void heapifyUpComparable(int pos, Object elem) { final Comparable<Object> cur = (Comparable<Object>) elem; // queue[pos]; - while(pos > 0) { + while (pos > 0) { final int parent = (pos - 1) >>> 1; Object par = queue[parent]; - if(cur.compareTo(par) >= 0) { + if (cur.compareTo(par) >= 0) { break; } queue[pos] = par; @@ -294,11 +305,11 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { * @param cur Element to insert */ protected void heapifyUpComparator(int pos, Object cur) { - while(pos > 0) { + while (pos > 0) { final int parent = (pos - 1) >>> 1; Object par = queue[parent]; - if(comparator.compare(cur, par) >= 0) { + if (comparator.compare(cur, par) >= 0) { break; } queue[pos] = par; @@ -316,10 +327,9 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { */ protected boolean heapifyDown(int pos, Object reinsert) { assert (pos >= 0); - if(comparator != null) { + if (comparator != null) { return heapifyDownComparator(pos, reinsert); - } - else { + } else { return heapifyDownComparable(pos, reinsert); } } @@ -328,6 +338,7 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { * Execute a "Heapify Downwards" aka "SiftDown". Used in deletions. * * @param ipos re-insertion position + * @param reinsert Object to reinsert * @return true when the order was changed */ @SuppressWarnings("unchecked") @@ -335,21 +346,21 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { Comparable<Object> cur = (Comparable<Object>) reinsert; int pos = ipos; final int half = size >>> 1; - while(pos < half) { + 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) { + if (rchild < size) { Object right = queue[rchild]; - if(((Comparable<Object>) child).compareTo(right) > 0) { + if (((Comparable<Object>) child).compareTo(right) > 0) { cpos = rchild; child = right; } } - if(cur.compareTo(child) <= 0) { + if (cur.compareTo(child) <= 0) { break; } queue[pos] = child; @@ -363,30 +374,31 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { * Execute a "Heapify Downwards" aka "SiftDown". Used in deletions. * * @param ipos re-insertion position + * @param cur Object to reinsert * @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) { + 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) { + if (comparator.compare(best, left) > 0) { min = lchild; best = left; } final int rchild = lchild + 1; - if(rchild < size) { + if (rchild < size) { Object right = queue[rchild]; - if(comparator.compare(best, right) > 0) { + if (comparator.compare(best, right) > 0) { min = rchild; best = right; } } - if(min == pos) { + if (min == pos) { break; } queue[pos] = best; @@ -396,56 +408,53 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { return (pos == ipos); } - @SuppressWarnings("unchecked") - protected final E castQueueElement(int n) { - return (E) queue[n]; - } - - @Override + /** + * Get the heap size. + * + * @return Heap size + */ public int size() { return this.size; } /** + * Test for emptiness. + * + * @return true when the heap is empty + */ + public boolean isEmpty() { + return size == 0; + } + + /** * Test whether we need to resize to have the requested capacity. * * @param requiredSize required capacity */ 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)); + int newCapacity = ((queue.length < 64) ? ((queue.length + 1) << 1) : ((queue.length >> 1) * 3)); // overflow? - if(newCapacity < 0) { + if (newCapacity < 0) { throw new OutOfMemoryError(); } - if(requiredSize > newCapacity) { + if (requiredSize > newCapacity) { newCapacity = requiredSize; } queue = Arrays.copyOf(queue, newCapacity); } - @Override + /** + * Clear the heap. + */ public void clear() { // clean up references in the array for memory management - for(int i = 0; i < size; i++) { + for (int i = 0; i < size; i++) { queue[i] = null; } this.size = 0; this.validSize = -1; - modCount++; - } - - @Override - public boolean contains(Object o) { - if(o != null) { - // TODO: use order to reduce search space? - for(int i = 0; i < size; i++) { - if(o.equals(queue[i])) { - return true; - } - } - } - return false; + heapModified(); } @Override @@ -453,19 +462,11 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { 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; + /** + * Called at the end of each heap modification. + */ + protected void heapModified() { + modCount++; } /** @@ -477,7 +478,7 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { */ protected final class Itr implements Iterator<E> { /** - * Cursor position + * Cursor position. */ private int cursor = 0; @@ -491,26 +492,26 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { return cursor < size; } + @SuppressWarnings("unchecked") @Override public E next() { - if(expectedModCount != modCount) { + if (expectedModCount != modCount) { throw new ConcurrentModificationException(); } - if(cursor < size) { - return castQueueElement(cursor++); + if (cursor < size) { + return (E) queue[cursor++]; } throw new NoSuchElementException(); } @Override public void remove() { - if(expectedModCount != modCount) { + if (expectedModCount != modCount) { throw new ConcurrentModificationException(); } - if(cursor > 0) { + if (cursor > 0) { cursor--; - } - else { + } else { throw new IllegalStateException(); } expectedModCount = modCount; @@ -518,20 +519,6 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { } /** - * Return the heap as a sorted array list, by repeated polling. This will - * empty the heap! - * - * @return new array list - */ - public ArrayList<E> toSortedArrayList() { - ArrayList<E> ret = new ArrayList<E>(size()); - while(!isEmpty()) { - ret.add(poll()); - } - return ret; - } - - /** * Test whether the heap is still valid. * * Debug method. @@ -540,24 +527,23 @@ public class Heap<E> extends AbstractQueue<E> implements Serializable { */ protected String checkHeap() { ensureValid(); - if(comparator == null) { - for(int i = 1; i < size; i++) { + 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) { + if (po.compareTo(queue[i]) > 0) { return "@" + parent + ": " + queue[parent] + " < @" + i + ": " + queue[i]; } } - } - else { - for(int i = 1; i < size; i++) { + } else { + for (int i = 1; i < size; i++) { final int parent = (i - 1) >>> 1; - if(comparator.compare(queue[parent], queue[i]) > 0) { + 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/IntegerHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerHeap.java new file mode 100644 index 00000000..6203ad96 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerHeap.java @@ -0,0 +1,264 @@ +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.Arrays; + +import de.lmu.ifi.dbs.elki.math.MathUtil; + +/** + * Basic in-memory heap structure. + * + * 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 + */ +public abstract class IntegerHeap extends AbstractHeap { + /** + * Heap storage: queue + */ + protected transient int[] queue; + + /** + * Constructor with initial capacity. + * + * @param size initial capacity + */ + public IntegerHeap(int size) { + super(); + this.size = 0; + this.queue = new int[size]; + } + + /** + * Add a key-value pair to the heap + * + * @param key Key + */ + public void add(int key) { + // resize when needed + if (size + 1 > queue.length) { + resize(size + 1); + } + // final int pos = size; + this.queue[size] = key; + this.size += 1; + heapifyUp(size - 1, key); + validSize += 1; + heapModified(); + } + + /** + * Add a key-value pair to the heap, except if the new element is larger than + * the top, and we are at design size (overflow) + * + * @param key Key + * @param max Maximum size of heap + */ + public void add(int key, int max) { + if (size < max) { + add(key); + } else if (comp(key, peek())) { + replaceTopElement(key); + } + } + + /** + * Combined operation that removes the top element, and inserts a new element + * instead. + * + * @param e New element to insert + * @return Previous top element of the heap + */ + public int replaceTopElement(int e) { + ensureValid(); + int oldroot = queue[0]; + heapifyDown(0, e); + heapModified(); + return oldroot; + } + + /** + * Get the current top key + * + * @return Top key + */ + public int peek() { + if (size == 0) { + throw new ArrayIndexOutOfBoundsException("Peek() on an empty heap!"); + } + ensureValid(); + return queue[0]; + } + + /** + * Remove the first element + * + * @return Top element + */ + public int poll() { + return removeAt(0); + } + + /** + * Repair the heap + */ + protected void ensureValid() { + if (validSize != size) { + if (size > 1) { + // 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 (!heapifyDown(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. + * @return Removed element + */ + protected int removeAt(int pos) { + if (pos < 0 || pos >= size) { + return 0; + } + final int top = queue[0]; + // Replacement object: + final int reinkey = queue[size - 1]; + // Keep heap in sync + if (validSize == size) { + size -= 1; + validSize -= 1; + heapifyDown(pos, reinkey); + } else { + size -= 1; + validSize = Math.min(pos >>> 1, validSize); + queue[pos] = reinkey; + } + heapModified(); + return top; + } + + /** + * Execute a "Heapify Upwards" aka "SiftUp". Used in insertions. + * + * @param pos insertion position + * @param curkey Current key + */ + protected void heapifyUp(int pos, int curkey) { + while (pos > 0) { + final int parent = (pos - 1) >>> 1; + int parkey = queue[parent]; + + if (comp(curkey, parkey)) { // Compare + break; + } + queue[pos] = parkey; + pos = parent; + } + queue[pos] = curkey; + } + + /** + * Execute a "Heapify Downwards" aka "SiftDown". Used in deletions. + * + * @param ipos re-insertion position + * @param curkey Current key + * @return true when the order was changed + */ + protected boolean heapifyDown(final int ipos, int curkey) { + int pos = ipos; + final int half = size >>> 1; + while (pos < half) { + // Get left child (must exist!) + int cpos = (pos << 1) + 1; + int chikey = queue[cpos]; + // Test right child, if present + final int rchild = cpos + 1; + if (rchild < size) { + int right = queue[rchild]; + if (comp(chikey, right)) { // Compare + cpos = rchild; + chikey = right; + } + } + + if (comp(chikey, curkey)) { // Compare + break; + } + queue[pos] = chikey; + pos = cpos; + } + queue[pos] = curkey; + return (pos == ipos); + } + + /** + * Test whether we need to resize to have the requested capacity. + * + * @param requiredSize required capacity + */ + protected final void resize(int requiredSize) { + queue = Arrays.copyOf(queue, desiredSize(requiredSize, queue.length)); + } + + /** + * Delete all elements from the heap. + */ + @Override + public void clear() { + super.clear(); + for (int i = 0; i < size; i++) { + queue[i] = 0; + } + } + + /** + * Compare two objects + */ + abstract protected boolean comp(int o1, int o2); +} diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerMaxHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerMaxHeap.java new file mode 100644 index 00000000..383eb727 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerMaxHeap.java @@ -0,0 +1,62 @@ +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/>. + */ + +/** + * Basic in-memory heap structure. + * + * 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 + */ +public class IntegerMaxHeap extends IntegerHeap { + /** + * Constructor with default capacity. + */ + public IntegerMaxHeap() { + super(DEFAULT_INITIAL_CAPACITY); + } + + /** + * Constructor with initial capacity. + * + * @param size initial capacity + */ + public IntegerMaxHeap(int size) { + super(size); + } + + /** + * Compare two objects + * + * @param o1 First object + * @param o2 Second object + */ + @Override + protected boolean comp(int o1, int o2) { + return o1 < o2; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerMinHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerMinHeap.java new file mode 100644 index 00000000..f81fe275 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerMinHeap.java @@ -0,0 +1,62 @@ +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/>. + */ + +/** + * Basic in-memory heap structure. + * + * 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 + */ +public class IntegerMinHeap extends IntegerHeap { + /** + * Constructor with default capacity. + */ + public IntegerMinHeap() { + super(DEFAULT_INITIAL_CAPACITY); + } + + /** + * Constructor with initial capacity. + * + * @param size initial capacity + */ + public IntegerMinHeap(int size) { + super(size); + } + + /** + * Compare two objects + * + * @param o1 First object + * @param o2 Second object + */ + @Override + protected boolean comp(int o1, int o2) { + return o1 > o2; + } +} 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 9dd941ec..2014de65 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 @@ -79,8 +79,9 @@ public class IntegerPriorityObject<O> implements PairInterface<Integer, O>, Comp } @Override + @Deprecated public Integer getFirst() { - return priority; + return Integer.valueOf(priority); } @Override @@ -120,8 +121,8 @@ public class IntegerPriorityObject<O> implements PairInterface<Integer, O>, Comp @Override public String toString() { - StringBuffer buf = new StringBuffer(); - buf.append(priority).append(":").append(object.toString()); + StringBuilder buf = new StringBuilder(); + 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 deleted file mode 100644 index 6c59123b..00000000 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/KNNHeap.java +++ /dev/null @@ -1,153 +0,0 @@ -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.Collections; -import java.util.Comparator; - -import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; -import de.lmu.ifi.dbs.elki.database.query.GenericDistanceResultPair; -import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; - -/** - * Heap used for KNN management. - * - * @author Erich Schubert - * - * @apiviz.has KNNList oneway - - serializes to - * - * @param <D> distance type - */ -public class KNNHeap<D extends Distance<D>> extends TiedTopBoundedHeap<DistanceResultPair<D>> { - /** - * Serial version - */ - private static final long serialVersionUID = 1L; - - /** - * Maximum distance, usually infiniteDistance - */ - private final D maxdist; - - /** - * Constructor. - * - * @param k k Parameter - * @param maxdist k-distance to return for less than k neighbors - usually - * infiniteDistance - */ - public KNNHeap(int k, D maxdist) { - super(k, new Comp<D>()); - this.maxdist = maxdist; - } - - /** - * Simplified constructor. Will return {@code null} as kNN distance with less - * than k entries. - * - * @param k k Parameter - */ - public KNNHeap(int k) { - this(k, null); - } - - @Override - public ArrayList<DistanceResultPair<D>> toSortedArrayList() { - ArrayList<DistanceResultPair<D>> list = super.toSortedArrayList(); - Collections.reverse(list); - return list; - } - - /** - * Serialize to a {@link KNNList}. This empties the heap! - * - * @return KNNList with the heaps contents. - */ - public KNNList<D> toKNNList() { - return new KNNList<D>(this); - } - - /** - * Get the K parameter ("maxsize" internally). - * - * @return K - */ - public int getK() { - return super.getMaxSize(); - } - - /** - * Get the distance to the k nearest neighbor, or maxdist otherwise. - * - * @return Maximum distance - */ - public D getKNNDistance() { - if(size() < getK()) { - return maxdist; - } - return peek().getDistance(); - } - - /** - * Get maximum distance in heap - */ - public D getMaximumDistance() { - if(isEmpty()) { - return maxdist; - } - return peek().getDistance(); - } - - /** - * Add a distance-id pair to the heap unless the distance is too large. - * - * Compared to the super.add() method, this often saves the pair construction. - * - * @param distance Distance value - * @param id ID number - * @return success code - */ - public boolean add(D distance, DBIDRef id) { - if(size() < maxsize || peek().getDistance().compareTo(distance) >= 0) { - return super.add(new GenericDistanceResultPair<D>(distance, id.getDBID())); - } - return true; /* "success" */ - } - - /** - * Comparator to use. - * - * @author Erich Schubert - * - * @apiviz.exclude - */ - public static class Comp<D extends Distance<D>> implements Comparator<DistanceResultPair<D>> { - @Override - public int compare(DistanceResultPair<D> o1, DistanceResultPair<D> o2) { - return -o1.compareByDistance(o2); - } - } -}
\ No newline at end of file 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 deleted file mode 100644 index 3e6ecc9d..00000000 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/KNNList.java +++ /dev/null @@ -1,181 +0,0 @@ -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.AbstractList; -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.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; - -/** - * Finalized KNN List. - * - * @author Erich Schubert - * - * @param <D> Distance type - */ -public class KNNList<D extends Distance<D>> extends AbstractList<DistanceResultPair<D>> implements KNNResult<D> { - /** - * The value of k this was materialized for. - */ - private final int k; - - /** - * The actual data array. - */ - private final Object[] data; - - /** - * Constructor, to be called from KNNHeap only. Use {@link KNNHeap#toKNNList} - * instead! - * - * @param heap Calling heap - */ - protected KNNList(KNNHeap<D> heap) { - super(); - this.data = new Object[heap.size()]; - this.k = heap.getK(); - 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); - 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); - data[i] = heap.poll(); - } - assert (data.length == 0 || data[0] != null); - assert (heap.size() == 0); - } - - @Override - public int getK() { - return k; - } - - @Override - public D getKNNDistance() { - return get(getK() - 1).getDistance(); - } - - @Override - public ArrayDBIDs asDBIDs() { - return KNNUtil.asDBIDs(this); - } - - @Override - public List<D> asDistanceList() { - return KNNUtil.asDistanceList(this); - } - - @Override - 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 DistanceResultPair<D> get(int index) { - return (DistanceResultPair<D>) data[index]; - } - - @Override - public Iterator<DistanceResultPair<D>> iterator() { - return new Itr(); - } - - @Override - public int size() { - return data.length; - } - - /** - * Iterator - * - * @author Erich Schubert - * - * @apiviz.exclude - */ - private class Itr implements Iterator<DistanceResultPair<D>> { - /** - * Cursor position - */ - private int pos = -1; - - @Override - public boolean hasNext() { - return pos + 1 < data.length; - } - - @SuppressWarnings("unchecked") - @Override - public DistanceResultPair<D> next() { - pos++; - return (DistanceResultPair<D>) data[pos]; - } - - @Override - public void remove() { - throw new UnsupportedOperationException("kNN results are unmodifiable."); - } - } -}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ObjectHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ObjectHeap.java new file mode 100644 index 00000000..2e20ed56 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ObjectHeap.java @@ -0,0 +1,267 @@ +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.Arrays; + +import de.lmu.ifi.dbs.elki.math.MathUtil; + +/** + * Basic in-memory heap structure. + * + * 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 + */ +public abstract class ObjectHeap<K> extends AbstractHeap { + /** + * Heap storage: queue + */ + protected transient Object[] queue; + + /** + * Constructor with initial capacity. + * + * @param size initial capacity + */ + public ObjectHeap(int size) { + super(); + this.size = 0; + this.queue = new Object[size]; + } + + /** + * Add a key-value pair to the heap + * + * @param key Key + */ + public void add(Object key) { + // resize when needed + if (size + 1 > queue.length) { + resize(size + 1); + } + // final int pos = size; + this.queue[size] = key; + this.size += 1; + heapifyUp(size - 1, key); + validSize += 1; + heapModified(); + } + + /** + * Add a key-value pair to the heap, except if the new element is larger than + * the top, and we are at design size (overflow) + * + * @param key Key + * @param max Maximum size of heap + */ + public void add(Object key, int max) { + if (size < max) { + add(key); + } else if (comp(key, peek())) { + replaceTopElement(key); + } + } + + /** + * Combined operation that removes the top element, and inserts a new element + * instead. + * + * @param e New element to insert + * @return Previous top element of the heap + */ + @SuppressWarnings("unchecked") + public Object replaceTopElement(Object e) { + ensureValid(); + Object oldroot = (K) queue[0]; + heapifyDown(0, e); + heapModified(); + return oldroot; + } + + /** + * Get the current top key + * + * @return Top key + */ + @SuppressWarnings("unchecked") + public Object peek() { + if (size == 0) { + throw new ArrayIndexOutOfBoundsException("Peek() on an empty heap!"); + } + ensureValid(); + return (K) queue[0]; + } + + /** + * Remove the first element + * + * @return Top element + */ + public Object poll() { + return removeAt(0); + } + + /** + * Repair the heap + */ + protected void ensureValid() { + if (validSize != size) { + if (size > 1) { + // 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 (!heapifyDown(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. + * @return Removed element + */ + @SuppressWarnings("unchecked") + protected Object removeAt(int pos) { + if (pos < 0 || pos >= size) { + return null; + } + final Object top = (K) queue[0]; + // Replacement object: + final Object reinkey = queue[size - 1]; + // Keep heap in sync + if (validSize == size) { + size -= 1; + validSize -= 1; + heapifyDown(pos, reinkey); + } else { + size -= 1; + validSize = Math.min(pos >>> 1, validSize); + queue[pos] = reinkey; + } + heapModified(); + return top; + } + + /** + * Execute a "Heapify Upwards" aka "SiftUp". Used in insertions. + * + * @param pos insertion position + * @param curkey Current key + */ + protected void heapifyUp(int pos, Object curkey) { + while (pos > 0) { + final int parent = (pos - 1) >>> 1; + Object parkey = queue[parent]; + + if (comp(curkey, parkey)) { // Compare + break; + } + queue[pos] = parkey; + pos = parent; + } + queue[pos] = curkey; + } + + /** + * Execute a "Heapify Downwards" aka "SiftDown". Used in deletions. + * + * @param ipos re-insertion position + * @param curkey Current key + * @return true when the order was changed + */ + protected boolean heapifyDown(final int ipos, Object curkey) { + int pos = ipos; + final int half = size >>> 1; + while (pos < half) { + // Get left child (must exist!) + int cpos = (pos << 1) + 1; + Object chikey = queue[cpos]; + // Test right child, if present + final int rchild = cpos + 1; + if (rchild < size) { + Object right = queue[rchild]; + if (comp(chikey, right)) { // Compare + cpos = rchild; + chikey = right; + } + } + + if (comp(chikey, curkey)) { // Compare + break; + } + queue[pos] = chikey; + pos = cpos; + } + queue[pos] = curkey; + return (pos == ipos); + } + + /** + * Test whether we need to resize to have the requested capacity. + * + * @param requiredSize required capacity + */ + protected final void resize(int requiredSize) { + queue = Arrays.copyOf(queue, desiredSize(requiredSize, queue.length)); + } + + /** + * Delete all elements from the heap. + */ + @Override + public void clear() { + super.clear(); + for (int i = 0; i < size; i++) { + queue[i] = null; + } + } + + /** + * Compare two objects + */ + abstract protected boolean comp(Object o1, Object o2); +} 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 c0ce3acf..2daaafa4 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 @@ -41,11 +41,6 @@ import de.lmu.ifi.dbs.elki.utilities.iterator.MergedIterator; */ public class TiedTopBoundedHeap<E> extends TopBoundedHeap<E> { /** - * Serial version - */ - private static final long serialVersionUID = 1L; - - /** * List to keep ties in. */ private List<E> ties = new ArrayList<E>(); @@ -80,11 +75,6 @@ public class TiedTopBoundedHeap<E> extends TopBoundedHeap<E> { ties.clear(); } - @Override - public boolean contains(Object o) { - return ties.contains(o) || super.contains(o); - } - @SuppressWarnings("unchecked") @Override public Iterator<E> iterator() { @@ -93,45 +83,52 @@ public class TiedTopBoundedHeap<E> extends TopBoundedHeap<E> { @Override public E peek() { - if(ties.isEmpty()) { + if (ties.isEmpty()) { return super.peek(); - } - else { + } else { return ties.get(ties.size() - 1); } } @Override public E poll() { - if(ties.isEmpty()) { + if (ties.isEmpty()) { return super.poll(); - } - else { + } else { return ties.remove(ties.size() - 1); } } @Override + public E replaceTopElement(E e) { + if (ties.isEmpty()) { + return super.replaceTopElement(e); + } + // Fall back to classic emulation via poll and offer: + E prev = poll(); + add(e); + return prev; + } + + @Override protected void handleOverflow(E e) { boolean tied = false; - if(comparator == null) { + if (comparator == null) { @SuppressWarnings("unchecked") Comparable<Object> c = (Comparable<Object>) e; - if(c.compareTo(queue[0]) == 0) { + if (c.compareTo(queue[0]) == 0) { tied = true; } - } - else { - if(comparator.compare(e, queue[0]) == 0) { + } else { + if (comparator.compare(e, queue[0]) == 0) { tied = true; } } - if(tied) { + if (tied) { ties.add(e); - } - else { + } else { // Also remove old ties. ties.clear(); } } -}
\ No newline at end of file +} 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 index 4fbc852e..8e39af1d 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TiedTopBoundedUpdatableHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TiedTopBoundedUpdatableHeap.java @@ -42,11 +42,6 @@ import de.lmu.ifi.dbs.elki.utilities.iterator.MergedIterator; */ 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>(); @@ -81,11 +76,6 @@ public class TiedTopBoundedUpdatableHeap<E> extends TopBoundedUpdatableHeap<E> { ties.clear(); } - @Override - public boolean contains(Object o) { - return ties.contains(o) || super.contains(o); - } - @SuppressWarnings("unchecked") @Override public Iterator<E> iterator() { @@ -93,7 +83,7 @@ public class TiedTopBoundedUpdatableHeap<E> extends TopBoundedUpdatableHeap<E> { } @Override - public boolean offerAt(int pos, E e) { + public void offerAt(int pos, E e) { if(pos == IN_TIES) { for(Iterator<E> i = ties.iterator(); i.hasNext();) { E e2 = i.next(); @@ -102,8 +92,7 @@ public class TiedTopBoundedUpdatableHeap<E> extends TopBoundedUpdatableHeap<E> { i.remove(); index.remove(e2); } - // while we did not change, this still was "successful". - return true; + return; } } throw new AbortException("Heap corrupt - should not be reached"); @@ -117,9 +106,9 @@ public class TiedTopBoundedUpdatableHeap<E> extends TopBoundedUpdatableHeap<E> { final E e2 = ties.remove(ties.size() - 1); // index.remove(e2); super.offerAt(NO_VALUE, e2); - return true; + return; } - return super.offerAt(pos, e); + super.offerAt(pos, e); } @Override 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 5b61e6f3..07b595f6 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 @@ -36,12 +36,7 @@ import java.util.Comparator; */ public class TopBoundedHeap<E> extends Heap<E> { /** - * Serial version - */ - private static final long serialVersionUID = 1L; - - /** - * Maximum size + * Maximum size. */ protected int maxsize; @@ -67,31 +62,32 @@ public class TopBoundedHeap<E> extends Heap<E> { } @Override - public boolean offer(E e) { - // don't add if we hit maxsize and are worse - 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; - } - } + public void add(E e) { + if (super.size() < maxsize) { + // Just offer. + super.add(e); + return; } - boolean result = super.offer(e); - // purge unneeded entry(s) - while(super.size() > maxsize) { - handleOverflow(super.poll()); + // Peek at the top element, return if we are worse. + ensureValid(); + final int comp; + if (comparator == null) { + @SuppressWarnings("unchecked") + Comparable<Object> c = (Comparable<Object>) e; + comp = c.compareTo(queue[0]); + } else { + comp = comparator.compare(e, queue[0]); + } + if (comp < 0) { + return; + } + if (comp == 0) { + handleOverflow(e); + } else { + // Otherwise, replace and repair: + E prev = super.replaceTopElement(e); + handleOverflow(prev); } - return result; } /** @@ -105,9 +101,11 @@ public class TopBoundedHeap<E> extends Heap<E> { } /** + * Get the maximum size. + * * @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/TopBoundedUpdatableHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TopBoundedUpdatableHeap.java index 2b22eba2..75f2abcf 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TopBoundedUpdatableHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TopBoundedUpdatableHeap.java @@ -36,12 +36,7 @@ import java.util.Comparator; */ public class TopBoundedUpdatableHeap<E> extends UpdatableHeap<E> { /** - * Serial version - */ - private static final long serialVersionUID = 1L; - - /** - * Maximum size + * Maximum size. */ protected int maxsize; @@ -67,22 +62,19 @@ public class TopBoundedUpdatableHeap<E> extends UpdatableHeap<E> { } @Override - public boolean offerAt(int pos, E e) { + public void 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. + if (pos != NO_VALUE || super.size() < maxsize) { + super.offerAt(pos, e); + return; } - boolean result = super.offerAt(pos, e); - // purge unneeded entry(s) - while(super.size() > maxsize) { - handleOverflow(super.poll()); + ensureValid(); + if (compare(e, queue[0]) < 0) { + // while we did not change, this still was "successful". + return; } - return result; + E prev = super.replaceTopElement(e); + handleOverflow(prev); } /** @@ -93,12 +85,11 @@ public class TopBoundedUpdatableHeap<E> extends UpdatableHeap<E> { * @return True when an update is needed */ protected int compare(Object e, Object object) { - if(comparator == null) { + if (comparator == null) { @SuppressWarnings("unchecked") Comparable<Object> c = (Comparable<Object>) e; return c.compareTo(queue[0]); - } - else { + } else { return comparator.compare(e, queue[0]); } } @@ -114,9 +105,11 @@ public class TopBoundedUpdatableHeap<E> extends UpdatableHeap<E> { } /** + * Get the maximum size. + * * @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 05858981..1ab5f4df 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 @@ -37,7 +37,7 @@ import java.util.Comparator; */ public class UpdatableHeap<O> extends Heap<O> { /** - * Constant for "not in heap" + * Constant for "not in heap". */ protected static final int NO_VALUE = Integer.MIN_VALUE; @@ -47,11 +47,6 @@ public class UpdatableHeap<O> extends Heap<O> { protected static final int IN_TIES = -1; /** - * Serial version - */ - private static final long serialVersionUID = 1L; - - /** * Holds the indices in the heap of each element. */ protected final TObjectIntMap<Object> index = new TObjectIntHashMap<Object>(100, 0.5f, NO_VALUE); @@ -73,7 +68,7 @@ public class UpdatableHeap<O> extends Heap<O> { } /** - * Constructor with comparator + * Constructor with comparator. * * @param comparator Comparator */ @@ -82,7 +77,7 @@ public class UpdatableHeap<O> extends Heap<O> { } /** - * Constructor with predefined size and comparator + * Constructor with predefined size and comparator. * * @param size Size * @param comparator Comparator @@ -98,12 +93,18 @@ public class UpdatableHeap<O> extends Heap<O> { } @Override - public boolean offer(O e) { + public void add(O e) { final int pos = index.get(e); - return offerAt(pos, e); + offerAt(pos, e); } - protected boolean offerAt(final int pos, O e) { + /** + * Offer element at the given position. + * + * @param pos Position + * @param e Element + */ + protected void offerAt(final int pos, O e) { if(pos == NO_VALUE) { // resize when needed if(size + 1 > queue.length) { @@ -114,9 +115,8 @@ public class UpdatableHeap<O> extends Heap<O> { 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; + heapModified(); + return; } else { assert (pos >= 0) : "Unexpected negative position."; @@ -126,14 +126,12 @@ public class UpdatableHeap<O> extends Heap<O> { @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; + return; } } else { if(comparator.compare(e, queue[pos]) >= 0) { - // Ignore, but return true according to {@link Collection#put} - return true; + return; } } if(pos >= validSize) { @@ -144,9 +142,8 @@ public class UpdatableHeap<O> extends Heap<O> { // ensureValid(); heapifyUp(pos, e); } - modCount++; - // We have changed - return true according to {@link Collection#put} - return true; + heapModified(); + return; } } @@ -155,7 +152,8 @@ public class UpdatableHeap<O> extends Heap<O> { if(pos < 0 || pos >= size) { return null; } - final O ret = castQueueElement(pos); + @SuppressWarnings("unchecked") + final O ret = (O) queue[pos]; // Replacement object: final Object reinsert = queue[size - 1]; queue[size - 1] = null; @@ -188,7 +186,7 @@ public class UpdatableHeap<O> extends Heap<O> { queue[pos] = reinsert; index.put(reinsert, pos); } - modCount++; + heapModified(); // Keep index up to date index.remove(ret); return ret; @@ -216,6 +214,13 @@ public class UpdatableHeap<O> extends Heap<O> { index.remove(node); return node; } + + @Override + public O replaceTopElement(O e) { + O node = super.replaceTopElement(e); + index.remove(node); + return node; + } /** * Execute a "Heapify Upwards" aka "SiftUp". Used in insertions. |