diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/utilities/datastructures')
38 files changed, 3331 insertions, 506 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/AnyMap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/AnyMap.java index 9e1307be..763ce105 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/AnyMap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/AnyMap.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/HashMapList.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/HashMapList.java index 7c5c950b..26fa4d19 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/HashMapList.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/HashMapList.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/MaskedArrayList.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/MaskedArrayList.java new file mode 100644 index 00000000..c24519d1 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/MaskedArrayList.java @@ -0,0 +1,174 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures; + +/* + 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.AbstractCollection; +import java.util.ArrayList; +import java.util.BitSet; +import java.util.Collection; +import java.util.Iterator; + +/** + * This class is a virtual collection based on masking an array list using a bit + * mask. + * + * @author Erich Schubert + * + * @apiviz.stereotype decorator + * @apiviz.composedOf java.util.ArrayList + * @apiviz.composedOf java.util.BitSet + * + * @param <T> Object type + */ +public class MaskedArrayList<T> extends AbstractCollection<T> implements Collection<T> { + /** + * Data storage + */ + protected ArrayList<T> data; + + /** + * The bitmask used for masking + */ + protected BitSet bits; + + /** + * Flag whether to iterator over set or unset values. + */ + protected boolean inverse = false; + + /** + * Constructor. + * + * @param data Data + * @param bits Bitset to use as mask + * @param inverse Flag to inverse the masking rule + */ + public MaskedArrayList(ArrayList<T> data, BitSet bits, boolean inverse) { + super(); + this.data = data; + this.bits = bits; + this.inverse = inverse; + } + + @Override + public boolean add(T e) { + throw new UnsupportedOperationException(); + } + + @Override + public Iterator<T> iterator() { + if(inverse) { + return new InvItr(); + } + else { + return new Itr(); + } + } + + @Override + public int size() { + if(inverse) { + return data.size() - bits.cardinality(); + } + else { + return bits.cardinality(); + } + } + + /** + * Iterator over set bits + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected class Itr implements Iterator<T> { + /** + * Next position. + */ + private int pos; + + /** + * Constructor + */ + protected Itr() { + this.pos = bits.nextSetBit(0); + } + + @Override + public boolean hasNext() { + return (pos >= 0) && (pos < data.size()); + } + + @Override + public T next() { + T cur = data.get(pos); + pos = bits.nextSetBit(pos + 1); + return cur; + } + + @Override + public void remove() { + throw new UnsupportedOperationException(); + } + } + + /** + * Iterator over unset elements. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + protected class InvItr implements Iterator<T> { + /** + * Next unset position. + */ + private int pos; + + /** + * Constructor + */ + protected InvItr() { + this.pos = bits.nextClearBit(0); + } + + @Override + public boolean hasNext() { + return (pos >= 0) && (pos < data.size()); + } + + @Override + public T next() { + T cur = data.get(pos); + pos = bits.nextClearBit(pos + 1); + return cur; + } + + @Override + public void remove() { + throw new UnsupportedOperationException(); + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/QuickSelect.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/QuickSelect.java new file mode 100644 index 00000000..4498cf07 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/QuickSelect.java @@ -0,0 +1,780 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures; + +import java.util.Comparator; +import java.util.List; + +/* + 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/>. + */ + +/** + * QuickSelect computes ("selects") the element at a given rank and can be used + * to compute Medians and arbitrary quantiles by computing the appropriate rank. + * + * This algorithm is essentially an incomplete QuickSort that only descends into + * that part of the data that we are interested in, and also attributed to + * Charles Antony Richard Hoare + * + * @author Erich Schubert + */ +public class QuickSelect { + /** + * For small arrays, use a simpler method: + */ + private static final int SMALL = 10; + + /** + * QuickSelect is essentially quicksort, except that we only "sort" that half + * of the array that we are interested in. + * + * Note: the array is <b>modified</b> by this. + * + * @param data Data to process + * @param rank Rank position that we are interested in (integer!) + * @return Value at the given rank + */ + public static double quickSelect(double[] data, int rank) { + quickSelect(data, 0, data.length, rank); + return data[rank]; + } + + /** + * Compute the median of an array efficiently using the QuickSelect method. + * + * Note: the array is <b>modified</b> by this. + * + * @param data Data to process + * @return Median value + */ + public static double median(double[] data) { + return median(data, 0, data.length); + } + + /** + * Compute the median of an array efficiently using the QuickSelect method. + * + * Note: the array is <b>modified</b> by this. + * + * @param data Data to process + * @param begin Begin of valid values + * @param end End of valid values (exclusive!) + * @return Median value + */ + public static double median(double[] data, int begin, int end) { + final int length = end - begin; + assert (length > 0); + // Integer division is "floor" since we are non-negative. + final int left = begin + (length - 1) / 2; + quickSelect(data, begin, end, left); + if(length % 2 == 1) { + return data[left]; + } + else { + quickSelect(data, begin, end, left + 1); + return data[left] + (data[left + 1] - data[left]) / 2; + } + } + + /** + * Compute the median of an array efficiently using the QuickSelect method. + * + * Note: the array is <b>modified</b> by this. + * + * @param data Data to process + * @param quant Quantile to compute + * @return Value at quantile + */ + public static double quantile(double[] data, double quant) { + return quantile(data, 0, data.length, quant); + } + + /** + * Compute the median of an array efficiently using the QuickSelect method. + * + * Note: the array is <b>modified</b> by this. + * + * @param data Data to process + * @param begin Begin of valid values + * @param end End of valid values (exclusive!) + * @param quant Quantile to compute + * @return Value at quantile + */ + public static double quantile(double[] data, int begin, int end, double quant) { + final int length = end - begin; + assert (length > 0) : "Quantile on empty set?"; + // Integer division is "floor" since we are non-negative. + final double dleft = begin + (length - 1) * quant; + final int ileft = (int) Math.floor(dleft); + final double err = dleft - ileft; + + quickSelect(data, begin, end, ileft); + if(err <= Double.MIN_NORMAL) { + return data[ileft]; + } + else { + quickSelect(data, begin, end, ileft + 1); + // Mix: + double mix = data[ileft] + (data[ileft + 1] - data[ileft]) * err; + return mix; + } + } + + /** + * QuickSelect is essentially quicksort, except that we only "sort" that half + * of the array that we are interested in. + * + * @param data Data to process + * @param start Interval start + * @param end Interval end (exclusive) + * @param rank rank position we are interested in (starting at 0) + */ + public static void quickSelect(double[] data, int start, int end, int rank) { + // Optimization for small arrays + // This also ensures a minimum size below + if(start + SMALL > end) { + insertionSort(data, start, end); + return; + } + + // Pick pivot from three candidates: start, middle, end + // Since we compare them, we can also just "bubble sort" them. + final int middle = (start + end) / 2; + if(data[start] > data[middle]) { + swap(data, start, middle); + } + if(data[start] > data[end - 1]) { + swap(data, start, end - 1); + } + if(data[middle] > data[end - 1]) { + swap(data, middle, end - 1); + } + // TODO: use more candidates for larger arrays? + + final double pivot = data[middle]; + // Move middle element out of the way, just before end + // (Since we already know that "end" is bigger) + swap(data, middle, end - 2); + + // Begin partitioning + int i = start + 1, j = end - 3; + // This is classic quicksort stuff + while(true) { + while(data[i] <= pivot && i <= j) { + i++; + } + while(data[j] >= pivot && j >= i) { + j--; + } + if(i >= j) { + break; + } + swap(data, i, j); + } + + // Move pivot (former middle element) back into the appropriate place + swap(data, i, end - 2); + + // In contrast to quicksort, we only need to recurse into the half we are + // interested in. + if(rank < i) { + quickSelect(data, start, i, rank); + } + else if(rank > i) { + quickSelect(data, i + 1, end, rank); + } + } + + /** + * Sort a small array using repetitive insertion sort. + * + * @param data Data to sort + * @param start Interval start + * @param end Interval end + */ + private static void insertionSort(double[] data, int start, int end) { + for(int i = start + 1; i < end; i++) { + for(int j = i; j > start && data[j - 1] > data[j]; j--) { + swap(data, j, j - 1); + } + } + } + + /** + * The usual swap method. + * + * @param data Array + * @param a First index + * @param b Second index + */ + private static final void swap(double[] data, int a, int b) { + double tmp = data[a]; + data[a] = data[b]; + data[b] = tmp; + } + + /** + * QuickSelect is essentially quicksort, except that we only "sort" that half + * of the array that we are interested in. + * + * Note: the array is <b>modified</b> by this. + * + * @param <T> object type + * @param data Data to process + * @param rank Rank position that we are interested in (integer!) + * @return Value at the given rank + */ + public static <T extends Comparable<? super T>> T quickSelect(T[] data, int rank) { + quickSelect(data, 0, data.length, rank); + return data[rank]; + } + + /** + * Compute the median of an array efficiently using the QuickSelect method. + * + * Note: the array is <b>modified</b> by this. + * + * @param data Data to process + * @return Median value + */ + public static <T extends Comparable<? super T>> T median(T[] data) { + return median(data, 0, data.length); + } + + /** + * Compute the median of an array efficiently using the QuickSelect method. + * + * On an odd length, it will return the lower element. + * + * Note: the array is <b>modified</b> by this. + * + * @param <T> object type + * @param data Data to process + * @param begin Begin of valid values + * @param end End of valid values (exclusive!) + * @return Median value + */ + public static <T extends Comparable<? super T>> T median(T[] data, int begin, int end) { + final int length = end - begin; + assert (length > 0); + // Integer division is "floor" since we are non-negative. + final int left = begin + (length - 1) / 2; + quickSelect(data, begin, end, left); + return data[left]; + } + + /** + * Compute the median of an array efficiently using the QuickSelect method. + * + * Note: the array is <b>modified</b> by this. + * + * @param <T> object type + * @param data Data to process + * @param quant Quantile to compute + * @return Value at quantile + */ + public static <T extends Comparable<? super T>> T quantile(T[] data, double quant) { + return quantile(data, 0, data.length, quant); + } + + /** + * Compute the median of an array efficiently using the QuickSelect method. + * + * It will prefer the lower element. + * + * Note: the array is <b>modified</b> by this. + * + * @param <T> object type + * @param data Data to process + * @param begin Begin of valid values + * @param end End of valid values (exclusive!) + * @param quant Quantile to compute + * @return Value at quantile + */ + public static <T extends Comparable<? super T>> T quantile(T[] data, int begin, int end, double quant) { + final int length = end - begin; + assert (length > 0) : "Quantile on empty set?"; + // Integer division is "floor" since we are non-negative. + final double dleft = begin + (length - 1) * quant; + final int ileft = (int) Math.floor(dleft); + + quickSelect(data, begin, end, ileft); + return data[ileft]; + } + + /** + * QuickSelect is essentially quicksort, except that we only "sort" that half + * of the array that we are interested in. + * + * @param <T> object type + * @param data Data to process + * @param start Interval start + * @param end Interval end (exclusive) + * @param rank rank position we are interested in (starting at 0) + */ + public static <T extends Comparable<? super T>> void quickSelect(T[] data, int start, int end, int rank) { + // Optimization for small arrays + // This also ensures a minimum size below + if(start + SMALL > end) { + insertionSort(data, start, end); + return; + } + + // Pick pivot from three candidates: start, middle, end + // Since we compare them, we can also just "bubble sort" them. + final int middle = (start + end) / 2; + if(data[start].compareTo(data[middle]) > 0) { + swap(data, start, middle); + } + if(data[start].compareTo(data[end - 1]) > 0) { + swap(data, start, end - 1); + } + if(data[middle].compareTo(data[end - 1]) > 0) { + swap(data, middle, end - 1); + } + // TODO: use more candidates for larger arrays? + + final T pivot = data[middle]; + // Move middle element out of the way, just before end + // (Since we already know that "end" is bigger) + swap(data, middle, end - 2); + + // Begin partitioning + int i = start + 1, j = end - 3; + // This is classic quicksort stuff + while(true) { + while(data[i].compareTo(pivot) <= 0 && i <= j) { + i++; + } + while(data[j].compareTo(pivot) >= 0 && j >= i) { + j--; + } + if(i >= j) { + break; + } + swap(data, i, j); + } + + // Move pivot (former middle element) back into the appropriate place + swap(data, i, end - 2); + + // In contrast to quicksort, we only need to recurse into the half we are + // interested in. + if(rank < i) { + quickSelect(data, start, i, rank); + } + else if(rank > i) { + quickSelect(data, i + 1, end, rank); + } + } + + /** + * Sort a small array using repetitive insertion sort. + * + * @param <T> object type + * @param data Data to sort + * @param start Interval start + * @param end Interval end + */ + private static <T extends Comparable<? super T>> void insertionSort(T[] data, int start, int end) { + for(int i = start + 1; i < end; i++) { + for(int j = i; j > start && data[j - 1].compareTo(data[j]) > 0; j--) { + swap(data, j, j - 1); + } + } + } + + /** + * The usual swap method. + * + * @param <T> object type + * @param data Array + * @param a First index + * @param b Second index + */ + private static final <T extends Comparable<? super T>> void swap(T[] data, int a, int b) { + T tmp = data[a]; + data[a] = data[b]; + data[b] = tmp; + } + + /** + * QuickSelect is essentially quicksort, except that we only "sort" that half + * of the array that we are interested in. + * + * Note: the array is <b>modified</b> by this. + * + * @param <T> object type + * @param data Data to process + * @param rank Rank position that we are interested in (integer!) + * @return Value at the given rank + */ + public static <T extends Comparable<? super T>> T quickSelect(List<? extends T> data, int rank) { + quickSelect(data, 0, data.size(), rank); + return data.get(rank); + } + + /** + * Compute the median of an array efficiently using the QuickSelect method. + * + * Note: the array is <b>modified</b> by this. + * + * @param <T> object type + * @param data Data to process + * @return Median value + */ + public static <T extends Comparable<? super T>> T median(List<? extends T> data) { + return median(data, 0, data.size()); + } + + /** + * Compute the median of an array efficiently using the QuickSelect method. + * + * On an odd length, it will return the lower element. + * + * Note: the array is <b>modified</b> by this. + * + * @param <T> object type + * @param data Data to process + * @param begin Begin of valid values + * @param end End of valid values (exclusive!) + * @return Median value + */ + public static <T extends Comparable<? super T>> T median(List<? extends T> data, int begin, int end) { + final int length = end - begin; + assert (length > 0); + // Integer division is "floor" since we are non-negative. + final int left = begin + (length - 1) / 2; + quickSelect(data, begin, end, left); + return data.get(left); + } + + /** + * Compute the median of an array efficiently using the QuickSelect method. + * + * Note: the array is <b>modified</b> by this. + * + * @param <T> object type + * @param data Data to process + * @param quant Quantile to compute + * @return Value at quantile + */ + public static <T extends Comparable<? super T>> T quantile(List<? extends T> data, double quant) { + return quantile(data, 0, data.size(), quant); + } + + /** + * Compute the median of an array efficiently using the QuickSelect method. + * + * It will prefer the lower element. + * + * Note: the array is <b>modified</b> by this. + * + * @param <T> object type + * @param data Data to process + * @param begin Begin of valid values + * @param end End of valid values (exclusive!) + * @param quant Quantile to compute + * @return Value at quantile + */ + public static <T extends Comparable<? super T>> T quantile(List<? extends T> data, int begin, int end, double quant) { + final int length = end - begin; + assert (length > 0) : "Quantile on empty set?"; + // Integer division is "floor" since we are non-negative. + final double dleft = begin + (length - 1) * quant; + final int ileft = (int) Math.floor(dleft); + + quickSelect(data, begin, end, ileft); + return data.get(ileft); + } + + /** + * QuickSelect is essentially quicksort, except that we only "sort" that half + * of the array that we are interested in. + * + * @param <T> object type + * @param data Data to process + * @param start Interval start + * @param end Interval end (exclusive) + * @param rank rank position we are interested in (starting at 0) + */ + public static <T extends Comparable<? super T>> void quickSelect(List<? extends T> data, int start, int end, int rank) { + // Optimization for small arrays + // This also ensures a minimum size below + if(start + SMALL > end) { + insertionSort(data, start, end); + return; + } + + // Pick pivot from three candidates: start, middle, end + // Since we compare them, we can also just "bubble sort" them. + final int middle = (start + end) / 2; + if(data.get(start).compareTo(data.get(middle)) > 0) { + swap(data, start, middle); + } + if(data.get(start).compareTo(data.get(end - 1)) > 0) { + swap(data, start, end - 1); + } + if(data.get(middle).compareTo(data.get(end - 1)) > 0) { + swap(data, middle, end - 1); + } + // TODO: use more candidates for larger arrays? + + final T pivot = data.get(middle); + // Move middle element out of the way, just before end + // (Since we already know that "end" is bigger) + swap(data, middle, end - 2); + + // Begin partitioning + int i = start + 1, j = end - 3; + // This is classic quicksort stuff + while(true) { + while(data.get(i).compareTo(pivot) <= 0 && i <= j) { + i++; + } + while(data.get(j).compareTo(pivot) >= 0 && j >= i) { + j--; + } + if(i >= j) { + break; + } + swap(data, i, j); + } + + // Move pivot (former middle element) back into the appropriate place + swap(data, i, end - 2); + + // In contrast to quicksort, we only need to recurse into the half we are + // interested in. + if(rank < i) { + quickSelect(data, start, i, rank); + } + else if(rank > i) { + quickSelect(data, i + 1, end, rank); + } + } + + /** + * Sort a small array using repetitive insertion sort. + * + * @param <T> object type + * @param data Data to sort + * @param start Interval start + * @param end Interval end + */ + private static <T extends Comparable<? super T>> void insertionSort(List<T> data, int start, int end) { + for(int i = start + 1; i < end; i++) { + for(int j = i; j > start && data.get(j - 1).compareTo(data.get(j)) > 0; j--) { + swap(data, j, j - 1); + } + } + } + + /** + * The usual swap method. + * + * @param <T> object type + * @param data Array + * @param a First index + * @param b Second index + */ + private static final <T> void swap(List<T> data, int a, int b) { + data.set(b, data.set(a, data.get(b))); + } + + /** + * QuickSelect is essentially quicksort, except that we only "sort" that half + * of the array that we are interested in. + * + * Note: the array is <b>modified</b> by this. + * + * @param <T> object type + * @param data Data to process + * @param comparator Comparator to use + * @param rank Rank position that we are interested in (integer!) + * @return Value at the given rank + */ + public static <T> T quickSelect(List<? extends T> data, Comparator<? super T> comparator, int rank) { + quickSelect(data, comparator, 0, data.size(), rank); + return data.get(rank); + } + + /** + * Compute the median of an array efficiently using the QuickSelect method. + * + * Note: the array is <b>modified</b> by this. + * + * @param <T> object type + * @param data Data to process + * @param comparator Comparator to use + * @return Median value + */ + public static <T> T median(List<? extends T> data, Comparator<? super T> comparator) { + return median(data, comparator, 0, data.size()); + } + + /** + * Compute the median of an array efficiently using the QuickSelect method. + * + * On an odd length, it will return the lower element. + * + * Note: the array is <b>modified</b> by this. + * + * @param <T> object type + * @param data Data to process + * @param comparator Comparator to use + * @param begin Begin of valid values + * @param end End of valid values (exclusive!) + * @return Median value + */ + public static <T> T median(List<? extends T> data, Comparator<? super T> comparator, int begin, int end) { + final int length = end - begin; + assert (length > 0); + // Integer division is "floor" since we are non-negative. + final int left = begin + (length - 1) / 2; + quickSelect(data, comparator, begin, end, left); + return data.get(left); + } + + /** + * Compute the median of an array efficiently using the QuickSelect method. + * + * Note: the array is <b>modified</b> by this. + * + * @param <T> object type + * @param data Data to process + * @param comparator Comparator to use + * @param quant Quantile to compute + * @return Value at quantile + */ + public static <T> T quantile(List<? extends T> data, Comparator<? super T> comparator, double quant) { + return quantile(data, comparator, 0, data.size(), quant); + } + + /** + * Compute the median of an array efficiently using the QuickSelect method. + * + * It will prefer the lower element. + * + * Note: the array is <b>modified</b> by this. + * + * @param <T> object type + * @param data Data to process + * @param comparator Comparator to use + * @param begin Begin of valid values + * @param end End of valid values (inclusive!) + * @param quant Quantile to compute + * @return Value at quantile + */ + public static <T> T quantile(List<? extends T> data, Comparator<? super T> comparator, int begin, int end, double quant) { + final int length = end - begin; + assert (length > 0) : "Quantile on empty set?"; + // Integer division is "floor" since we are non-negative. + final double dleft = begin + (length - 1) * quant; + final int ileft = (int) Math.floor(dleft); + + quickSelect(data, comparator, begin, end, ileft); + return data.get(ileft); + } + + /** + * QuickSelect is essentially quicksort, except that we only "sort" that half + * of the array that we are interested in. + * + * @param <T> object type + * @param data Data to process + * @param comparator Comparator to use + * @param start Interval start + * @param end Interval end (inclusive) + * @param rank rank position we are interested in (starting at 0) + */ + public static <T> void quickSelect(List<? extends T> data, Comparator<? super T> comparator, int start, int end, int rank) { + // Optimization for small arrays + // This also ensures a minimum size below + if(start + SMALL > end) { + insertionSort(data, comparator, start, end); + return; + } + + // Pick pivot from three candidates: start, middle, end + // Since we compare them, we can also just "bubble sort" them. + final int middle = (start + end) / 2; + if(comparator.compare(data.get(start), data.get(middle)) > 0) { + swap(data, start, middle); + } + if(comparator.compare(data.get(start), data.get(end - 1)) > 0) { + swap(data, start, end - 1); + } + if(comparator.compare(data.get(middle), data.get(end - 1)) > 0) { + swap(data, middle, end - 1); + } + // TODO: use more candidates for larger arrays? + + final T pivot = data.get(middle); + // Move middle element out of the way, just before end + // (Since we already know that "end" is bigger) + swap(data, middle, end - 2); + + // Begin partitioning + int i = start + 1, j = end - 3; + // This is classic quicksort stuff + while(true) { + while(comparator.compare(data.get(i), pivot) <= 0 && i <= j) { + i++; + } + while(comparator.compare(data.get(j), pivot) >= 0 && j >= i) { + j--; + } + if(i >= j) { + break; + } + swap(data, i, j); + } + + // Move pivot (former middle element) back into the appropriate place + swap(data, i, end - 2); + + // In contrast to quicksort, we only need to recurse into the half we are + // interested in. + if(rank < i) { + quickSelect(data, comparator, start, i, rank); + } + else if(rank > i) { + quickSelect(data, comparator, i + 1, end, rank); + } + } + + /** + * Sort a small array using repetitive insertion sort. + * + * @param <T> object type + * @param data Data to sort + * @param start Interval start + * @param end Interval end + */ + private static <T> void insertionSort(List<T> data, Comparator<? super T> comparator, int start, int end) { + for(int i = start + 1; i < end; i++) { + for(int j = i; j > start && comparator.compare(data.get(j - 1), data.get(j)) > 0; j--) { + swap(data, j, j - 1); + } + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/ArrayAdapter.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/ArrayAdapter.java new file mode 100644 index 00000000..969d068d --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/ArrayAdapter.java @@ -0,0 +1,52 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike; + +/* + 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/>. + */ + +/** + * Adapter for array-like things. For example, arrays and lists. + * + * @author Erich Schubert + * + * @param <T> Item type + * @param <A> Array object type + */ +public interface ArrayAdapter<T, A> { + /** + * Get the size of the array. + * + * @param array Array-like thing + * @return Size + */ + public int size(A array); + + /** + * Get the off'th item from the array. + * + * @param array Array to get from + * @param off Offset + * @return Item at offset off + * @throws IndexOutOfBoundsException for an invalid index. + */ + public T get(A array, int off) throws IndexOutOfBoundsException; +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/ArrayDBIDsAdapter.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/ArrayDBIDsAdapter.java new file mode 100644 index 00000000..6e6e8122 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/ArrayDBIDsAdapter.java @@ -0,0 +1,53 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2012 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DBID; + +/** + * Use a DBID array in a generic array-like context. + * + * @author Erich Schubert + */ +public class ArrayDBIDsAdapter implements ArrayAdapter<DBID, ArrayDBIDs> { + /** + * Constructor. + * + * Protected - use the static instance from {@link ArrayLikeUtil}! + */ + protected ArrayDBIDsAdapter() { + super(); + } + + @Override + public int size(ArrayDBIDs array) { + return array.size(); + } + + @Override + public DBID get(ArrayDBIDs array, int off) throws IndexOutOfBoundsException { + return array.get(off); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/ArrayLikeUtil.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/ArrayLikeUtil.java new file mode 100644 index 00000000..2d29f40c --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/ArrayLikeUtil.java @@ -0,0 +1,253 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike; + +/* + 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.List; + +import de.lmu.ifi.dbs.elki.data.FeatureVector; +import de.lmu.ifi.dbs.elki.data.NumberVector; + +/** + * Utility class that allows plug-in use of various "array-like" types such as + * lists in APIs that can take any kind of array to safe the cost of + * reorganizing the objects into a real array. + * + * @author Erich Schubert + */ +public final class ArrayLikeUtil { + /** + * Static instance for lists + */ + private static final ListArrayAdapter<Object> LISTADAPTER = new ListArrayAdapter<Object>(); + + /** + * Static instance for lists of numbers + */ + private static final NumberListArrayAdapter<Number> NUMBERLISTADAPTER = new NumberListArrayAdapter<Number>(); + + /** + * Static instance + */ + private final static IdentityArrayAdapter<?> IDENTITYADAPTER = new IdentityArrayAdapter<Object>(); + + /** + * Static instance + */ + private static final FeatureVectorAdapter<?> FEATUREVECTORADAPTER = new FeatureVectorAdapter<Number>(); + + /** + * Use a number vector in the array API. + */ + private static final NumberVectorAdapter<?> NUMBERVECTORADAPTER = new NumberVectorAdapter<Double>(); + + /** + * Use a double array in the array API. + */ + public static final NumberArrayAdapter<Double, double[]> DOUBLEARRAYADAPTER = new DoubleArrayAdapter(); + + /** + * Use a float array in the array API. + */ + public static final NumberArrayAdapter<Float, float[]> FLOATARRAYADAPTER = new FloatArrayAdapter(); + + /** + * Use a Trove double list as array. + */ + public static final TDoubleListAdapter TDOUBLELISTADAPTER = new TDoubleListAdapter(); + + /** + * Use ArrayDBIDs as array. + */ + public static final ArrayDBIDsAdapter ARRAYDBIDADAPTER = new ArrayDBIDsAdapter(); + + /** + * Cast the static instance. + * + * @param dummy Dummy variable, for type inference + * @return Static instance + */ + @SuppressWarnings("unchecked") + public static <T> ArrayAdapter<T, List<? extends T>> listAdapter(List<? extends T> dummy) { + return (ListArrayAdapter<T>) LISTADAPTER; + } + + /** + * Cast the static instance. + * + * @param dummy Dummy variable, for type inference + * @return Static instance + */ + @SuppressWarnings("unchecked") + public static <T extends Number> NumberArrayAdapter<T, List<? extends T>> numberListAdapter(List<? extends T> dummy) { + return (NumberListArrayAdapter<T>) NUMBERLISTADAPTER; + } + + /** + * Get the static instance. + * + * @param dummy Dummy object for type inference + * @return Static instance + */ + @SuppressWarnings("unchecked") + public static <T> IdentityArrayAdapter<T> identityAdapter(T dummy) { + return (IdentityArrayAdapter<T>) IDENTITYADAPTER; + } + + /** + * Get the static instance. + * + * @param prototype Prototype value, for type inference + * @return Instance + */ + @SuppressWarnings("unchecked") + public static <F> FeatureVectorAdapter<F> featureVectorAdapter(FeatureVector<?, F> prototype) { + return (FeatureVectorAdapter<F>) FEATUREVECTORADAPTER; + } + + /** + * Get the static instance. + * + * @param prototype Prototype value, for type inference + * @return Instance + */ + @SuppressWarnings("unchecked") + public static <N extends Number> NumberVectorAdapter<N> numberVectorAdapter(NumberVector<?, N> prototype) { + return (NumberVectorAdapter<N>) NUMBERVECTORADAPTER; + } + + /** + * Get the adapter for double arrays. + * + * @return double array adapter + */ + public static NumberArrayAdapter<Double, double[]> doubleArrayAdapter() { + return DOUBLEARRAYADAPTER; + } + + /** + * Returns the index of the maximum of the given values. If no value is bigger + * than the first, the index of the first entry is returned. + * + * @param <A> array type + * @param array Array to inspect + * @param adapter API adapter class + * @return the index of the maximum in the given values + * @throws IndexOutOfBoundsException if the length of the array is 0. + */ + public static <A> int getIndexOfMaximum(A array, NumberArrayAdapter<?, A> adapter) throws IndexOutOfBoundsException { + final int size = adapter.size(array); + int index = 0; + double max = adapter.getDouble(array, 0); + for(int i = 1; i < size; i++) { + double val = adapter.getDouble(array, i); + if(val > max) { + max = val; + index = i; + } + } + return index; + } + + /** + * Returns the index of the maximum of the given values. If no value is bigger + * than the first, the index of the first entry is returned. + * + * @param array Array to inspect + * @return the index of the maximum in the given values + * @throws IndexOutOfBoundsException if the length of the array is 0. + */ + public static int getIndexOfMaximum(double[] array) throws IndexOutOfBoundsException { + return getIndexOfMaximum(array, DOUBLEARRAYADAPTER); + } + + /** + * Convert a numeric array-like to a <code>double[]</code> + * + * @param array Array-like + * @param adapter Adapter + * @return primitive double array + */ + public static <A> double[] toPrimitiveDoubleArray(A array, NumberArrayAdapter<?, ? super A> adapter) { + double[] ret = new double[adapter.size(array)]; + for(int i = 0; i < ret.length; i++) { + ret[i] = adapter.getDouble(array, i); + } + return ret; + } + + /** + * Convert a list of numbers to <code>double[]</code>. + * + * @param array List of numbers + * @return double array + */ + public static double[] toPrimitiveDoubleArray(List<? extends Number> array) { + return toPrimitiveDoubleArray(array, NUMBERLISTADAPTER); + } + + /** + * Convert a number vector to <code>double[]</code>. + * + * @param obj Object to convert + * @return primitive double array + */ + public static <N extends Number> double[] toPrimitiveDoubleArray(NumberVector<?, N> obj) { + return toPrimitiveDoubleArray(obj, numberVectorAdapter(obj)); + } + + /** + * Convert a numeric array-like to a <code>float[]</code> + * + * @param array Array-like + * @param adapter Adapter + * @return primitive float array + */ + public static <A> float[] toPrimitiveFloatArray(A array, NumberArrayAdapter<?, ? super A> adapter) { + float[] ret = new float[adapter.size(array)]; + for(int i = 0; i < ret.length; i++) { + ret[i] = adapter.getFloat(array, i); + } + return ret; + } + + /** + * Convert a list of numbers to <code>float[]</code>. + * + * @param array List of numbers + * @return float array + */ + public static float[] toPrimitiveFloatArray(List<? extends Number> array) { + return toPrimitiveFloatArray(array, NUMBERLISTADAPTER); + } + + /** + * Convert a number vector to <code>float[]</code>. + * + * @param obj Object to convert + * @return primitive float array + */ + public static <N extends Number> float[] toPrimitiveFloatArray(NumberVector<?, N> obj) { + return toPrimitiveFloatArray(obj, numberVectorAdapter(obj)); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/DoubleArrayAdapter.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/DoubleArrayAdapter.java new file mode 100644 index 00000000..43419103 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/DoubleArrayAdapter.java @@ -0,0 +1,81 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike; +/* + 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/>. + */ + +/** + * Use a double array as, well, double array in the ArrayAdapter API. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ +class DoubleArrayAdapter implements NumberArrayAdapter<Double, double[]> { + /** + * Constructor. + * + * Use the static instance from {@link ArrayLikeUtil}! + */ + protected DoubleArrayAdapter() { + super(); + } + + @Override + public int size(double[] array) { + return array.length; + } + + @Override + public Double get(double[] array, int off) throws IndexOutOfBoundsException { + return array[off]; + } + + @Override + public double getDouble(double[] array, int off) throws IndexOutOfBoundsException { + return array[off]; + } + + @Override + public float getFloat(double[] array, int off) throws IndexOutOfBoundsException { + return (float) array[off]; + } + + @Override + public int getInteger(double[] array, int off) throws IndexOutOfBoundsException { + return (int) array[off]; + } + + @Override + public short getShort(double[] array, int off) throws IndexOutOfBoundsException { + return (short) array[off]; + } + + @Override + public long getLong(double[] array, int off) throws IndexOutOfBoundsException { + return (long) array[off]; + } + + @Override + public byte getByte(double[] array, int off) throws IndexOutOfBoundsException { + return (byte) array[off]; + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/ExtendedArray.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/ExtendedArray.java new file mode 100644 index 00000000..a195360b --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/ExtendedArray.java @@ -0,0 +1,96 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike; + +/* + 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/>. + */ + +/** + * Class to extend an array with a single element virtually. + * + * @author Erich Schubert + * + * @param <T> Object type + */ +public class ExtendedArray<T> implements ArrayAdapter<T, ExtendedArray<T>> { + /** + * The array + */ + final Object array; + + /** + * The array adapter + */ + final ArrayAdapter<T, Object> getter; + + /** + * The extra element + */ + final T extra; + + /** + * Our size + */ + final int size; + + /** + * Constructor. + * + * @param array Original array + * @param getter Adapter for array + * @param extra Extra element + */ + protected ExtendedArray(Object array, ArrayAdapter<T, Object> getter, T extra) { + super(); + this.array = array; + this.getter = getter; + this.extra = extra; + this.size = getter.size(array) + 1; + } + + @Override + public int size(ExtendedArray<T> array) { + assert (array == this); + return size; + } + + @Override + public T get(ExtendedArray<T> array, int off) throws IndexOutOfBoundsException { + assert (array == this); + if(off == size - 1) { + return extra; + } + return getter.get(this.array, off); + } + + /** + * Static wrapper that has a nicer generics signature. + * + * @param array Array to extend + * @param getter Getter for array + * @param extra Extra element + * @return Extended array + */ + @SuppressWarnings("unchecked") + public static <T, A> ExtendedArray<T> extend(A array, ArrayAdapter<T, A> getter, T extra) { + return new ExtendedArray<T>(array, (ArrayAdapter<T, Object>) getter, extra); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/FeatureVectorAdapter.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/FeatureVectorAdapter.java new file mode 100644 index 00000000..19c2ec19 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/FeatureVectorAdapter.java @@ -0,0 +1,56 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike; + +import de.lmu.ifi.dbs.elki.data.FeatureVector; + +/* + 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/>. + */ + +/** + * Adapter to use a feature vector as an array of features. + * + * Use the static instance from {@link ArrayLikeUtil}! + * + * @author Erich Schubert + * + * @param <F> Feature type + */ +public class FeatureVectorAdapter<F> implements ArrayAdapter<F, FeatureVector<?, F>> { + /** + * Constructor. + * + * Use the static instance from {@link ArrayLikeUtil}! + */ + protected FeatureVectorAdapter() { + super(); + } + + @Override + public int size(FeatureVector<?, F> array) { + return array.getDimensionality(); + } + + @Override + public F get(FeatureVector<?, F> array, int off) throws IndexOutOfBoundsException { + return array.getValue(off); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/FloatArrayAdapter.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/FloatArrayAdapter.java new file mode 100644 index 00000000..14d42dc5 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/FloatArrayAdapter.java @@ -0,0 +1,82 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike; + +/* + 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/>. + */ + +/** + * Use a double array as, well, double array in the ArrayAdapter API. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ +class FloatArrayAdapter implements NumberArrayAdapter<Float, float[]> { + /** + * Constructor. + * + * Use the static instance from {@link ArrayLikeUtil}! + */ + protected FloatArrayAdapter() { + super(); + } + + @Override + public int size(float[] array) { + return array.length; + } + + @Override + public Float get(float[] array, int off) throws IndexOutOfBoundsException { + return array[off]; + } + + @Override + public double getDouble(float[] array, int off) throws IndexOutOfBoundsException { + return (double) array[off]; + } + + @Override + public float getFloat(float[] array, int off) throws IndexOutOfBoundsException { + return array[off]; + } + + @Override + public int getInteger(float[] array, int off) throws IndexOutOfBoundsException { + return (int) array[off]; + } + + @Override + public short getShort(float[] array, int off) throws IndexOutOfBoundsException { + return (short) array[off]; + } + + @Override + public long getLong(float[] array, int off) throws IndexOutOfBoundsException { + return (long) array[off]; + } + + @Override + public byte getByte(float[] array, int off) throws IndexOutOfBoundsException { + return (byte) array[off]; + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/IdentityArrayAdapter.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/IdentityArrayAdapter.java new file mode 100644 index 00000000..0c6e03dd --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/IdentityArrayAdapter.java @@ -0,0 +1,55 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike; + +/* + 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/>. + */ + +/** + * Single-item subset adapter + * + * Use the static instance from {@link ArrayLikeUtil}! + * + * @author Erich Schubert + * + * @param <T> Item type + */ +public class IdentityArrayAdapter<T> implements ArrayAdapter<T, T> { + /** + * Constructor. + * + * Use the static instance from {@link ArrayLikeUtil}! + */ + protected IdentityArrayAdapter() { + super(); + } + + @Override + public int size(T array) { + return 1; + } + + @Override + public T get(T array, int off) throws IndexOutOfBoundsException { + assert (off == 0) : "Invalid get()"; + return array; + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/ListArrayAdapter.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/ListArrayAdapter.java new file mode 100644 index 00000000..37875ab7 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/ListArrayAdapter.java @@ -0,0 +1,55 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike; + +import java.util.List; +/* + 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/>. + */ + +/** + * Static adapter class to use a {@link java.util.List} in an array API. + * + * Use the static instance from {@link ArrayLikeUtil}! + * + * @author Erich Schubert + * + * @param <T> Data object type. + */ +public class ListArrayAdapter<T> implements ArrayAdapter<T, List<? extends T>> { + /** + * Constructor. + * + * Use the static instance from {@link ArrayLikeUtil}! + */ + protected ListArrayAdapter() { + super(); + } + + @Override + public int size(List<? extends T> array) { + return array.size(); + } + + @Override + public T get(List<? extends T> array, int off) throws IndexOutOfBoundsException { + return array.get(off); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/NumberArrayAdapter.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/NumberArrayAdapter.java new file mode 100644 index 00000000..1dc823b1 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/NumberArrayAdapter.java @@ -0,0 +1,99 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike; +/* + 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/>. + */ + +/** + * Adapter for arrays of numbers, to avoid boxing. + * + * @author Erich Schubert + * + * @param <N> Number type + * @param <A> Array type + */ +public interface NumberArrayAdapter<N extends Number, A> extends ArrayAdapter<N, A> { + @Override + public int size(A array); + + @Override + public N get(A array, int off) throws IndexOutOfBoundsException; + + /** + * Get the off'th item from the array as double. + * + * @param array Array to get from + * @param off Offset + * @return Item at offset off + * @throws IndexOutOfBoundsException for an invalid index. + */ + public double getDouble(A array, int off) throws IndexOutOfBoundsException; + + /** + * Get the off'th item from the array as float. + * + * @param array Array to get from + * @param off Offset + * @return Item at offset off + * @throws IndexOutOfBoundsException for an invalid index. + */ + public float getFloat(A array, int off) throws IndexOutOfBoundsException; + + /** + * Get the off'th item from the array as integer. + * + * @param array Array to get from + * @param off Offset + * @return Item at offset off + * @throws IndexOutOfBoundsException for an invalid index. + */ + public int getInteger(A array, int off) throws IndexOutOfBoundsException; + + /** + * Get the off'th item from the array as short. + * + * @param array Array to get from + * @param off Offset + * @return Item at offset off + * @throws IndexOutOfBoundsException for an invalid index. + */ + public short getShort(A array, int off) throws IndexOutOfBoundsException; + + /** + * Get the off'th item from the array as long. + * + * @param array Array to get from + * @param off Offset + * @return Item at offset off + * @throws IndexOutOfBoundsException for an invalid index. + */ + public long getLong(A array, int off) throws IndexOutOfBoundsException; + + /** + * Get the off'th item from the array as byte. + * + * @param array Array to get from + * @param off Offset + * @return Item at offset off + * @throws IndexOutOfBoundsException for an invalid index. + */ + public byte getByte(A array, int off) throws IndexOutOfBoundsException; +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/NumberListArrayAdapter.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/NumberListArrayAdapter.java new file mode 100644 index 00000000..89a4e3d6 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/NumberListArrayAdapter.java @@ -0,0 +1,87 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike; + +import java.util.List; + +/* + 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/>. + */ + +/** + * Static adapter class to use a {@link java.util.List} in an array of number + * API. + * + * Use the static instance from {@link ArrayLikeUtil}! + * + * @author Erich Schubert + * + * @param <T> Data object type. + */ +public class NumberListArrayAdapter<T extends Number> implements NumberArrayAdapter<T, List<? extends T>> { + /** + * Constructor. + * + * Use the static instance from {@link ArrayLikeUtil}! + */ + protected NumberListArrayAdapter() { + super(); + } + + @Override + public int size(List<? extends T> array) { + return array.size(); + } + + @Override + public T get(List<? extends T> array, int off) throws IndexOutOfBoundsException { + return array.get(off); + } + + @Override + public double getDouble(List<? extends T> array, int off) throws IndexOutOfBoundsException { + return array.get(off).doubleValue(); + } + + @Override + public float getFloat(List<? extends T> array, int off) throws IndexOutOfBoundsException { + return array.get(off).floatValue(); + } + + @Override + public int getInteger(List<? extends T> array, int off) throws IndexOutOfBoundsException { + return array.get(off).intValue(); + } + + @Override + public short getShort(List<? extends T> array, int off) throws IndexOutOfBoundsException { + return array.get(off).shortValue(); + } + + @Override + public long getLong(List<? extends T> array, int off) throws IndexOutOfBoundsException { + return array.get(off).longValue(); + } + + @Override + public byte getByte(List<? extends T> array, int off) throws IndexOutOfBoundsException { + return array.get(off).byteValue(); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/NumberVectorAdapter.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/NumberVectorAdapter.java new file mode 100644 index 00000000..c75acd64 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/NumberVectorAdapter.java @@ -0,0 +1,86 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike; + +import de.lmu.ifi.dbs.elki.data.NumberVector; + +/* + 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/>. + */ + +/** + * Adapter to use a feature vector as an array of features. + * + * Use the static instance from {@link ArrayLikeUtil}! + * + * @author Erich Schubert + * + * @param <N> Number type + */ +public class NumberVectorAdapter<N extends Number> implements NumberArrayAdapter<N, NumberVector<?, N>> { + /** + * Constructor. + * + * Use the static instance from {@link ArrayLikeUtil}! + */ + protected NumberVectorAdapter() { + super(); + } + + @Override + public int size(NumberVector<?, N> array) { + return array.getDimensionality(); + } + + @Override + public N get(NumberVector<?, N> array, int off) throws IndexOutOfBoundsException { + return array.getValue(off + 1); + } + + @Override + public double getDouble(NumberVector<?, N> array, int off) throws IndexOutOfBoundsException { + return array.doubleValue(off + 1); + } + + @Override + public float getFloat(NumberVector<?, N> array, int off) throws IndexOutOfBoundsException { + return array.floatValue(off + 1); + } + + @Override + public int getInteger(NumberVector<?, N> array, int off) throws IndexOutOfBoundsException { + return array.intValue(off + 1); + } + + @Override + public short getShort(NumberVector<?, N> array, int off) throws IndexOutOfBoundsException { + return array.shortValue(off + 1); + } + + @Override + public long getLong(NumberVector<?, N> array, int off) throws IndexOutOfBoundsException { + return array.longValue(off + 1); + } + + @Override + public byte getByte(NumberVector<?, N> array, int off) throws IndexOutOfBoundsException { + return array.byteValue(off + 1); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/SingleSubsetArrayAdapter.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/SingleSubsetArrayAdapter.java new file mode 100644 index 00000000..d7483e4d --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/SingleSubsetArrayAdapter.java @@ -0,0 +1,67 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike; + +/* + 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/>. + */ + +/** + * Single-item subset adapter + * + * @author Erich Schubert + * + * @param <T> Entry type + * @param <A> Array type + */ +public class SingleSubsetArrayAdapter<T, A> implements ArrayAdapter<T, A> { + /** + * Wrapped adapter + */ + ArrayAdapter<T, ? super A> wrapped; + + /** + * Offset to return + */ + int off; + + /** + * Constructor. + * + * @param wrapped Wrapped adapter + * @param off Offset + */ + public SingleSubsetArrayAdapter(ArrayAdapter<T, ? super A> wrapped, int off) { + super(); + this.wrapped = wrapped; + this.off = off; + } + + @Override + public int size(A array) { + return 1; + } + + @Override + public T get(A array, int off) throws IndexOutOfBoundsException { + assert (off == 0) : "Invalid get()"; + return wrapped.get(array, off); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/SubsetArrayAdapter.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/SubsetArrayAdapter.java new file mode 100644 index 00000000..b2958358 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/SubsetArrayAdapter.java @@ -0,0 +1,65 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike; +/* + 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/>. + */ + +/** + * Subset array adapter (allows reordering and projection) + * + * @author Erich Schubert + * + * @param <T> Entry type + * @param <A> Array type + */ +public class SubsetArrayAdapter<T, A> implements ArrayAdapter<T, A> { + /** + * Wrapped adapter + */ + ArrayAdapter<T, ? super A> wrapped; + + /** + * Offsets to return + */ + int[] offs; + + /** + * Constructor. + * + * @param wrapped Wrapped adapter + * @param offs Offsets + */ + public SubsetArrayAdapter(ArrayAdapter<T, ? super A> wrapped, int[] offs) { + super(); + this.wrapped = wrapped; + this.offs = offs; + } + + @Override + public int size(A array) { + return offs.length; + } + + @Override + public T get(A array, int off) throws IndexOutOfBoundsException { + return wrapped.get(array, offs[off]); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/TDoubleListAdapter.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/TDoubleListAdapter.java new file mode 100644 index 00000000..889c64e8 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/TDoubleListAdapter.java @@ -0,0 +1,81 @@ +package de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike; + +import gnu.trove.list.TDoubleList; + +/* + 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/>. + */ +/** + * Adapter for using Trove TDoubleLists as array-like. + * + * @author Erich Schubert + * + * @apiviz.uses TDoubleList + */ +public class TDoubleListAdapter implements NumberArrayAdapter<Double, TDoubleList> { + /** + * Constructor. + */ + protected TDoubleListAdapter() { + super(); + } + + @Override + public int size(TDoubleList array) { + return array.size(); + } + + @Override + public Double get(TDoubleList array, int off) throws IndexOutOfBoundsException { + return array.get(off); + } + + @Override + public double getDouble(TDoubleList array, int off) throws IndexOutOfBoundsException { + return array.get(off); + } + + @Override + public float getFloat(TDoubleList array, int off) throws IndexOutOfBoundsException { + return (float) array.get(off); + } + + @Override + public int getInteger(TDoubleList array, int off) throws IndexOutOfBoundsException { + return (int) array.get(off); + } + + @Override + public short getShort(TDoubleList array, int off) throws IndexOutOfBoundsException { + return (short) array.get(off); + } + + @Override + public long getLong(TDoubleList array, int off) throws IndexOutOfBoundsException { + return (long) array.get(off); + } + + @Override + public byte getByte(TDoubleList array, int off) throws IndexOutOfBoundsException { + return (byte) array.get(off); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/package-info.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/package-info.java new file mode 100644 index 00000000..55627df4 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/package-info.java @@ -0,0 +1,26 @@ +/** + * <p>Common API for accessing objects that are "array-like", including lists, numerical vectors, database vectors and arrays.</p> + */ +/* + 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/>. + */ +package de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike;
\ No newline at end of file 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 diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/Hierarchical.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/Hierarchical.java index 1bd9b430..697ac640 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/Hierarchical.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/Hierarchical.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.hierarchy; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/Hierarchy.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/Hierarchy.java index 94a6c708..3a3c4d45 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/Hierarchy.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/Hierarchy.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.hierarchy; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/HierarchyHashmapList.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/HierarchyHashmapList.java index 1b2dd0fa..d09e6d94 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/HierarchyHashmapList.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/HierarchyHashmapList.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.hierarchy; 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 @@ -92,7 +92,7 @@ public class HierarchyHashmapList<O> implements ModifiableHierarchy<O> { @Override public void remove(O parent, O child) { - // Add child to parent. + // Remove child from parent. { List<O> pchi = this.cmap.get(parent); if(pchi != null) { @@ -104,7 +104,7 @@ public class HierarchyHashmapList<O> implements ModifiableHierarchy<O> { } } } - // Add child to parent + // Remove parent from child { List<O> cpar = this.pmap.get(child); if(cpar != null) { diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/HierarchyReferenceLists.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/HierarchyReferenceLists.java index c2185dc9..f6c527ab 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/HierarchyReferenceLists.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/HierarchyReferenceLists.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.hierarchy; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/ModifiableHierarchy.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/ModifiableHierarchy.java index 9faaf189..dadc6f66 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/ModifiableHierarchy.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/ModifiableHierarchy.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.hierarchy; This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures - Copyright (C) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/package-info.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/package-info.java index 259ab46b..0aba31be 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/hierarchy/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 diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/package-info.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/package-info.java index 31a0f5b4..ae8308af 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/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 |