diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/utilities')
69 files changed, 1442 insertions, 3970 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/utilities/BitsUtil.java b/src/de/lmu/ifi/dbs/elki/utilities/BitsUtil.java index d1e0587c..64d5be25 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/BitsUtil.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/BitsUtil.java @@ -42,16 +42,24 @@ public final class BitsUtil { */ private static final int LONG_LOG2_SIZE = 6; - /** - * Masking for long shifts. - */ + /** Masking for long shifts. */ private static final int LONG_LOG2_MASK = 0x3f; // 6 bits - /** - * Long with all bits set - */ + /** Long with all bits set */ private static final long LONG_ALL_BITS = -1L; + /** Long, with 63 bits set */ + private static final long LONG_63_BITS = 0x7FFFFFFFFFFFFFFFL; + + /** Masking 32 bit **/ + private static final long LONG_32_BITS = 0xFFFFFFFFL; + + /** Precomputed powers of 5 for pow5, pow10 on the bit representation. */ + private static final int[] POW5_INT = { // + 1, 5, 25, 125, 625,// + 3125, 15625, 78125, 390625, 1953125,// + 9765625, 48828125, 244140625, 1220703125 }; + /** * Allocate a new long[]. * @@ -1177,4 +1185,161 @@ public final class BitsUtil { } return 0; } + + public static double lpow2(long m, int n) { + if (m == 0) { + return 0.0; + } + if (m == Long.MIN_VALUE) { + return lpow2(Long.MIN_VALUE >> 1, n + 1); + } + if (m < 0) { + return -lpow2(-m, n); + } + assert(m >= 0); + int bitLength = magnitude(m); + int shift = bitLength - 53; + long exp = 1023L + 52 + n + shift; // Use long to avoid overflow. + if (exp >= 0x7FF) { + return Double.POSITIVE_INFINITY; + } + if (exp <= 0) { // Degenerated number (subnormal, assume 0 for bit 52) + if (exp <= -54) { + return 0.0; + } + return lpow2(m, n + 54) / 18014398509481984L; // 2^54 Exact. + } + // Normal number. + long bits = (shift > 0) ? (m >> shift) + ((m >> (shift - 1)) & 1) : // Rounding. + m << -shift; + if (((bits >> 52) != 1) && (++exp >= 0x7FF)) { + return Double.POSITIVE_INFINITY; + } + bits &= 0x000fffffffffffffL; // Clears MSB (bit 52) + bits |= exp << 52; + return Double.longBitsToDouble(bits); + } + + /** + * Compute {@code m * Math.pow(10,e)} on the bit representation, for + * assembling a floating point decimal value. + * + * @param m Mantisse + * @param n Exponent to base 10. + * @return Double value. + */ + public static double lpow10(long m, int n) { + if (m == 0) { + return 0.0; + } + if (m == Long.MIN_VALUE) { + return lpow10(Long.MIN_VALUE / 10, n + 1); + } + if (m < 0) { + return -lpow10(-m, n); + } + if (n >= 0) { // Positive power. + if (n > 308) { + return Double.POSITIVE_INFINITY; + } + // Works with 4 x 32 bits registers (x3:x2:x1:x0) + long x0 = 0; // 32 bits. + long x1 = 0; // 32 bits. + long x2 = m & LONG_32_BITS; // 32 bits. + long x3 = m >>> 32; // 32 bits. + int pow2 = 0; + while (n != 0) { + int i = (n >= POW5_INT.length) ? POW5_INT.length - 1 : n; + int coef = POW5_INT[i]; // 31 bits max. + + if (((int) x0) != 0) { + x0 *= coef; // 63 bits max. + } + if (((int) x1) != 0) { + x1 *= coef; // 63 bits max. + } + x2 *= coef; // 63 bits max. + x3 *= coef; // 63 bits max. + + x1 += x0 >>> 32; + x0 &= LONG_32_BITS; + + x2 += x1 >>> 32; + x1 &= LONG_32_BITS; + + x3 += x2 >>> 32; + x2 &= LONG_32_BITS; + + // Adjusts powers. + pow2 += i; + n -= i; + + // Normalizes (x3 should be 32 bits max). + long carry = x3 >>> 32; + if (carry != 0) { // Shift. + x0 = x1; + x1 = x2; + x2 = x3 & LONG_32_BITS; + x3 = carry; + pow2 += 32; + } + } + + // Merges registers to a 63 bits mantissa. + assert(x3 >= 0); + int shift = 31 - magnitude(x3); // -1..30 + pow2 -= shift; + long mantissa = (shift < 0) ? (x3 << 31) | (x2 >>> 1) : // x3 is 32 bits. + (((x3 << 32) | x2) << shift) | (x1 >>> (32 - shift)); + return lpow2(mantissa, pow2); + } else { // n < 0 + if (n < -324 - 20) { + return 0.; + } + + // Works with x1:x0 126 bits register. + long x1 = m; // 63 bits. + long x0 = 0; // 63 bits. + int pow2 = 0; + while (true) { + // Normalizes x1:x0 + assert(x1 >= 0); + int shift = 63 - magnitude(x1); + x1 <<= shift; + x1 |= x0 >>> (63 - shift); + x0 = (x0 << shift) & LONG_63_BITS; + pow2 -= shift; + + // Checks if division has to be performed. + if (n == 0) { + break; // Done. + } + + // Retrieves power of 5 divisor. + int i = (-n >= POW5_INT.length) ? POW5_INT.length - 1 : -n; + int divisor = POW5_INT[i]; + + // Performs the division (126 bits by 31 bits). + long wh = (x1 >>> 32); + long qh = wh / divisor; + long r = wh - qh * divisor; + long wl = (r << 32) | (x1 & LONG_32_BITS); + long ql = wl / divisor; + r = wl - ql * divisor; + x1 = (qh << 32) | ql; + + wh = (r << 31) | (x0 >>> 32); + qh = wh / divisor; + r = wh - qh * divisor; + wl = (r << 32) | (x0 & LONG_32_BITS); + ql = wl / divisor; + x0 = (qh << 32) | ql; + + // Adjusts powers. + n += i; + pow2 -= i; + } + return lpow2(x1, pow2); + } + } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/FormatUtil.java b/src/de/lmu/ifi/dbs/elki/utilities/FormatUtil.java index 08b7bd0d..4601cce9 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/FormatUtil.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/FormatUtil.java @@ -167,10 +167,11 @@ public final class FormatUtil { */ public static String format(double[] d, String sep) { StringBuilder buffer = new StringBuilder(); - for (int i = 0; i < d.length; i++) { - if (i > 0) { + for(int i = 0; i < d.length; i++) { + if(i > 0) { buffer.append(sep).append(d[i]); - } else { + } + else { buffer.append(d[i]); } } @@ -189,10 +190,11 @@ public final class FormatUtil { */ public static String format(double[] d, String sep, int digits) { StringBuilder buffer = new StringBuilder(); - for (int i = 0; i < d.length; i++) { - if (i < d.length - 1) { + for(int i = 0; i < d.length; i++) { + if(i < d.length - 1) { buffer.append(format(d[i], digits)).append(sep); - } else { + } + else { buffer.append(format(d[i], digits)); } } @@ -221,10 +223,11 @@ public final class FormatUtil { */ public static String format(double[] d, String sep, NumberFormat nf) { StringBuilder buffer = new StringBuilder(); - for (int i = 0; i < d.length; i++) { - if (i < d.length - 1) { + for(int i = 0; i < d.length; i++) { + if(i < d.length - 1) { buffer.append(format(d[i], nf)).append(sep); - } else { + } + else { buffer.append(format(d[i], nf)); } } @@ -261,7 +264,7 @@ public final class FormatUtil { */ public static String format(double[][] d) { StringBuilder buffer = new StringBuilder(); - for (double[] array : d) { + for(double[] array : d) { buffer.append(format(array, ", ", 2)).append('\n'); } return buffer.toString(); @@ -280,10 +283,11 @@ public final class FormatUtil { public static String format(double[][] d, String sep1, String sep2, int digits) { StringBuilder buffer = new StringBuilder(); - for (int i = 0; i < d.length; i++) { - if (i < d.length - 1) { + for(int i = 0; i < d.length; i++) { + if(i < d.length - 1) { buffer.append(format(d[i], sep2, digits)).append(sep1); - } else { + } + else { buffer.append(format(d[i], sep2, digits)); } } @@ -303,10 +307,11 @@ public final class FormatUtil { */ public static String format(Double[] f, String sep, int digits) { StringBuilder buffer = new StringBuilder(); - for (int i = 0; i < f.length; i++) { - if (i < f.length - 1) { + for(int i = 0; i < f.length; i++) { + if(i < f.length - 1) { buffer.append(format(f[i].doubleValue(), digits)).append(sep); - } else { + } + else { buffer.append(format(f[i].doubleValue(), digits)); } } @@ -335,10 +340,11 @@ public final class FormatUtil { */ public static String format(Double[] f, String sep, NumberFormat nf) { StringBuilder buffer = new StringBuilder(); - for (int i = 0; i < f.length; i++) { - if (i < f.length - 1) { + for(int i = 0; i < f.length; i++) { + if(i < f.length - 1) { buffer.append(format(f[i].doubleValue(), nf)).append(sep); - } else { + } + else { buffer.append(format(f[i].doubleValue(), nf)); } } @@ -368,10 +374,11 @@ public final class FormatUtil { */ public static String format(float[] f, String sep, int digits) { StringBuilder buffer = new StringBuilder(); - for (int i = 0; i < f.length; i++) { - if (i < f.length - 1) { + for(int i = 0; i < f.length; i++) { + if(i < f.length - 1) { buffer.append(format(f[i], digits)).append(sep); - } else { + } + else { buffer.append(format(f[i], digits)); } } @@ -398,10 +405,11 @@ public final class FormatUtil { */ public static String format(int[] a, String sep) { StringBuilder buffer = new StringBuilder(); - for (int i = 0; i < a.length; i++) { - if (i < a.length - 1) { + for(int i = 0; i < a.length; i++) { + if(i < a.length - 1) { buffer.append(a[i]).append(sep); - } else { + } + else { buffer.append(a[i]); } } @@ -428,10 +436,11 @@ public final class FormatUtil { */ public static String format(Integer[] a, String sep) { StringBuilder buffer = new StringBuilder(); - for (int i = 0; i < a.length; i++) { - if (i < a.length - 1) { + for(int i = 0; i < a.length; i++) { + if(i < a.length - 1) { buffer.append(a[i]).append(sep); - } else { + } + else { buffer.append(a[i]); } } @@ -456,10 +465,11 @@ public final class FormatUtil { */ public static String format(long[] a) { StringBuilder buffer = new StringBuilder(); - for (int i = 0; i < a.length; i++) { - if (i < a.length - 1) { + for(int i = 0; i < a.length; i++) { + if(i < a.length - 1) { buffer.append(a[i]).append(", "); - } else { + } + else { buffer.append(a[i]); } } @@ -474,10 +484,11 @@ public final class FormatUtil { */ public static String format(byte[] a) { StringBuilder buffer = new StringBuilder(); - for (int i = 0; i < a.length; i++) { - if (i < a.length - 1) { + for(int i = 0; i < a.length; i++) { + if(i < a.length - 1) { buffer.append(a[i]).append(", "); - } else { + } + else { buffer.append(a[i]); } } @@ -494,10 +505,11 @@ public final class FormatUtil { */ public static String format(boolean[] b, final String sep) { StringBuilder buffer = new StringBuilder(); - for (int i = 0; i < b.length; i++) { - if (i < b.length - 1) { + for(int i = 0; i < b.length; i++) { + if(i < b.length - 1) { buffer.append(format(b[i])).append(sep); - } else { + } + else { buffer.append(format(b[i])); } } @@ -511,7 +523,7 @@ public final class FormatUtil { * @return a String representing of the boolean b */ public static String format(final boolean b) { - if (b) { + if(b) { return "1"; } return "0"; @@ -528,13 +540,14 @@ public final class FormatUtil { public static String format(BitSet bitSet, int dim, String sep) { StringBuilder msg = new StringBuilder(); - for (int d = 0; d < dim; d++) { - if (d > 0) { + for(int d = 0; d < dim; d++) { + if(d > 0) { msg.append(sep); } - if (bitSet.get(d)) { + if(bitSet.get(d)) { msg.append('1'); - } else { + } + else { msg.append('0'); } } @@ -563,16 +576,16 @@ public final class FormatUtil { * @return a String representing the String Collection d */ public static String format(Collection<String> d, String sep) { - if (d.size() == 0) { + if(d.size() == 0) { return ""; } - if (d.size() == 1) { + if(d.size() == 1) { return d.iterator().next(); } StringBuilder buffer = new StringBuilder(); boolean first = true; - for (String str : d) { - if (!first) { + for(String str : d) { + if(!first) { buffer.append(sep); } buffer.append(str); @@ -600,12 +613,12 @@ public final class FormatUtil { int width = w + 1; StringBuilder msg = new StringBuilder(); msg.append('\n'); // start on new line. - for (int i = 0; i < m.getRowDimensionality(); i++) { - for (int j = 0; j < m.getColumnDimensionality(); j++) { + for(int i = 0; i < m.getRowDimensionality(); i++) { + for(int j = 0; j < m.getColumnDimensionality(); j++) { String s = format.format(m.get(i, j)); // format the number int padding = Math.max(1, width - s.length()); // At _least_ 1 // space - for (int k = 0; k < padding; k++) { + for(int k = 0; k < padding; k++) { msg.append(' '); } msg.append(s); @@ -636,11 +649,11 @@ public final class FormatUtil { int width = w + 1; StringBuilder msg = new StringBuilder(); msg.append('\n'); // start on new line. - for (int i = 0; i < v.getDimensionality(); i++) { + for(int i = 0; i < v.getDimensionality(); i++) { String s = format.format(v.get(i)); // format the number int padding = Math.max(1, width - s.length()); // At _least_ 1 // space - for (int k = 0; k < padding; k++) { + for(int k = 0; k < padding; k++) { msg.append(' '); } msg.append(s); @@ -660,11 +673,11 @@ public final class FormatUtil { public static String format(Matrix m, String pre) { StringBuilder output = new StringBuilder(); output.append(pre).append("[\n").append(pre); - for (int i = 0; i < m.getRowDimensionality(); i++) { + for(int i = 0; i < m.getRowDimensionality(); i++) { output.append(" ["); - for (int j = 0; j < m.getColumnDimensionality(); j++) { + for(int j = 0; j < m.getColumnDimensionality(); j++) { output.append(' ').append(m.get(i, j)); - if (j < m.getColumnDimensionality() - 1) { + if(j < m.getColumnDimensionality() - 1) { output.append(','); } } @@ -685,26 +698,26 @@ public final class FormatUtil { public static String format(Matrix m, NumberFormat nf) { int[] colMax = new int[m.getColumnDimensionality()]; String[][] entries = new String[m.getRowDimensionality()][m.getColumnDimensionality()]; - for (int i = 0; i < m.getRowDimensionality(); i++) { - for (int j = 0; j < m.getColumnDimensionality(); j++) { + for(int i = 0; i < m.getRowDimensionality(); i++) { + for(int j = 0; j < m.getColumnDimensionality(); j++) { entries[i][j] = nf.format(m.get(i, j)); - if (entries[i][j].length() > colMax[j]) { + if(entries[i][j].length() > colMax[j]) { colMax[j] = entries[i][j].length(); } } } StringBuilder output = new StringBuilder(); output.append("[\n"); - for (int i = 0; i < m.getRowDimensionality(); i++) { + for(int i = 0; i < m.getRowDimensionality(); i++) { output.append(" ["); - for (int j = 0; j < m.getColumnDimensionality(); j++) { + for(int j = 0; j < m.getColumnDimensionality(); j++) { output.append(' '); int space = colMax[j] - entries[i][j].length(); - for (int s = 0; s < space; s++) { + for(int s = 0; s < space; s++) { output.append(' '); } output.append(entries[i][j]); - if (j < m.getColumnDimensionality() - 1) { + if(j < m.getColumnDimensionality() - 1) { output.append(','); } } @@ -754,9 +767,9 @@ public final class FormatUtil { public static String format(Vector v, String pre) { StringBuilder output = new StringBuilder(); output.append(pre).append("[\n").append(pre); - for (int j = 0; j < v.getDimensionality(); j++) { + for(int j = 0; j < v.getDimensionality(); j++) { output.append(' ').append(v.get(j)); - if (j < v.getDimensionality() - 1) { + if(j < v.getDimensionality() - 1) { output.append(','); } } @@ -774,32 +787,32 @@ public final class FormatUtil { * @return a string representation of this matrix */ public static String format(Matrix m, String pre, NumberFormat nf) { - if (nf == null) { + if(nf == null) { return FormatUtil.format(m, pre); } int[] colMax = new int[m.getColumnDimensionality()]; String[][] entries = new String[m.getRowDimensionality()][m.getColumnDimensionality()]; - for (int i = 0; i < m.getRowDimensionality(); i++) { - for (int j = 0; j < m.getColumnDimensionality(); j++) { + for(int i = 0; i < m.getRowDimensionality(); i++) { + for(int j = 0; j < m.getColumnDimensionality(); j++) { entries[i][j] = nf.format(m.get(i, j)); - if (entries[i][j].length() > colMax[j]) { + if(entries[i][j].length() > colMax[j]) { colMax[j] = entries[i][j].length(); } } } StringBuilder output = new StringBuilder(); output.append(pre).append("[\n").append(pre); - for (int i = 0; i < m.getRowDimensionality(); i++) { + for(int i = 0; i < m.getRowDimensionality(); i++) { output.append(" ["); - for (int j = 0; j < m.getColumnDimensionality(); j++) { + for(int j = 0; j < m.getColumnDimensionality(); j++) { output.append(' '); int space = colMax[j] - entries[i][j].length(); - for (int s = 0; s < space; s++) { + for(int s = 0; s < space; s++) { output.append(' '); } output.append(entries[i][j]); - if (j < m.getColumnDimensionality() - 1) { + if(j < m.getColumnDimensionality() - 1) { output.append(','); } } @@ -821,22 +834,22 @@ public final class FormatUtil { public static int findSplitpoint(String s, int width) { // the newline (or EOS) is the fallback split position. int in = s.indexOf(NEWLINE); - if (in < 0) { + if(in < 0) { in = s.length(); } // Good enough? - if (in < width) { + if(in < width) { return in; } // otherwise, search for whitespace int iw = s.lastIndexOf(' ', width); // good whitespace found? - if (iw >= 0 && iw < width) { + if(iw >= 0 && iw < width) { return iw; } // sub-optimal splitpoint - retry AFTER the given position int bp = nextPosition(s.indexOf(' ', width), s.indexOf(NEWLINE, width)); - if (bp >= 0) { + if(bp >= 0) { return bp; } // even worse - can't split! @@ -853,10 +866,10 @@ public final class FormatUtil { * otherwise whichever is positive. */ private static int nextPosition(int a, int b) { - if (a < 0) { + if(a < 0) { return b; } - if (b < 0) { + if(b < 0) { return a; } return Math.min(a, b); @@ -874,19 +887,19 @@ public final class FormatUtil { List<String> chunks = new ArrayList<>(); String tmp = s; - while (tmp.length() > 0) { + while(tmp.length() > 0) { int index = findSplitpoint(tmp, width); // store first part chunks.add(tmp.substring(0, index)); // skip whitespace at beginning of line - while (index < tmp.length() && tmp.charAt(index) == ' ') { + while(index < tmp.length() && tmp.charAt(index) == ' ') { index += 1; } // remove a newline - if (index < tmp.length() && tmp.regionMatches(index, NEWLINE, 0, NEWLINE.length())) { + if(index < tmp.length() && tmp.regionMatches(index, NEWLINE, 0, NEWLINE.length())) { index += NEWLINE.length(); } - if (index >= tmp.length()) { + if(index >= tmp.length()) { break; } tmp = tmp.substring(index); @@ -902,11 +915,11 @@ public final class FormatUtil { * @return a string with the specified number of blanks */ public static String whitespace(int n) { - if (n < WHITESPACE_BUFFER.length()) { + if(n < WHITESPACE_BUFFER.length()) { return WHITESPACE_BUFFER.substring(0, n); } char[] buf = new char[n]; - for (int i = 0; i < n; i++) { + for(int i = 0; i < n; i++) { buf[i] = WHITESPACE_BUFFER.charAt(0); } return new String(buf); @@ -920,7 +933,7 @@ public final class FormatUtil { * @return padded string of at least length len (and o otherwise) */ public static String pad(String o, int len) { - if (o.length() >= len) { + if(o.length() >= len) { return o; } return o + whitespace(len - o.length()); @@ -934,7 +947,7 @@ public final class FormatUtil { * @return padded string of at least length len (and o otherwise) */ public static String padRightAligned(String o, int len) { - if (o.length() >= len) { + if(o.length() >= len) { return o; } return whitespace(len - o.length()) + o; @@ -950,9 +963,11 @@ public final class FormatUtil { final int default_termwidth = 78; try { return Integer.parseInt(System.getenv("COLUMNS")) - 1; - } catch (SecurityException e) { + } + catch(SecurityException e) { return default_termwidth; - } catch (NumberFormatException e) { + } + catch(NumberFormatException e) { return default_termwidth; } } @@ -967,18 +982,18 @@ public final class FormatUtil { final StringBuilder sb = new StringBuilder(); final Formatter fmt = new Formatter(sb); - for (int i = TIME_UNIT_SIZES.length - 1; i >= 0; --i) { + for(int i = TIME_UNIT_SIZES.length - 1; i >= 0; --i) { // We do not include ms if we are in the order of minutes. - if (i == 0 && sb.length() > 4) { + if(i == 0 && sb.length() > 4) { continue; } // Separator - if (sb.length() > 0) { + if(sb.length() > 0) { sb.append(sep); } final long acValue = time / TIME_UNIT_SIZES[i]; time = time % TIME_UNIT_SIZES[i]; - if (!(acValue == 0 && sb.length() == 0)) { + if(!(acValue == 0 && sb.length() == 0)) { fmt.format("%0" + TIME_UNIT_DIGITS[i] + "d%s", Long.valueOf(acValue), TIME_UNIT_NAMES[i]); } } @@ -996,13 +1011,341 @@ public final class FormatUtil { */ public static String format(String[] d, String sep) { StringBuilder buffer = new StringBuilder(); - for (int i = 0; i < d.length; i++) { - if (i > 0) { + for(int i = 0; i < d.length; i++) { + if(i > 0) { buffer.append(sep).append(d[i]); - } else { + } + else { buffer.append(d[i]); } } return buffer.toString(); } + + /** + * Preallocated exceptions. + */ + private static final NumberFormatException EXPONENT_OVERFLOW = new NumberFormatException("Precision overflow for double exponent.") { + private static final long serialVersionUID = 1L; + + @Override + public synchronized Throwable fillInStackTrace() { + return this; + } + }; + + /** + * Preallocated exceptions. + */ + private static final NumberFormatException INVALID_EXPONENT = new NumberFormatException("Invalid exponent") { + private static final long serialVersionUID = 1L; + + @Override + public synchronized Throwable fillInStackTrace() { + return this; + } + }; + + /** + * Preallocated exceptions. + */ + private static final NumberFormatException TRAILING_CHARACTERS = new NumberFormatException("String sequence was not completely consumed.") { + private static final long serialVersionUID = 1L; + + @Override + public synchronized Throwable fillInStackTrace() { + return this; + } + }; + + /** + * Preallocated exceptions. + */ + private static final NumberFormatException PRECISION_OVERFLOW = new NumberFormatException("Precision overflow for long values.") { + private static final long serialVersionUID = 1L; + + @Override + public synchronized Throwable fillInStackTrace() { + return this; + } + }; + + /** + * Preallocated exceptions. + */ + private static final NumberFormatException NOT_A_NUMBER = new NumberFormatException("Number must start with a digit or dot.") { + private static final long serialVersionUID = 1L; + + @Override + public synchronized Throwable fillInStackTrace() { + return this; + } + }; + + /** + * Parse a double from a character sequence. + * + * In contrast to Javas {@link Double#parseDouble}, this will <em>not</em> + * create an object and thus is expected to put less load on the garbage + * collector. It will accept some more spellings of NaN and infinity, thus + * removing the need for checking for these independently. + * + * @param str String + * @return Double value + */ + public static double parseDouble(final CharSequence str) { + return parseDouble(str, 0, str.length()); + } + + /** + * Parse a double from a character sequence. + * + * In contrast to Javas {@link Double#parseDouble}, this will <em>not</em> + * create an object and thus is expected to put less load on the garbage + * collector. It will accept some more spellings of NaN and infinity, thus + * removing the need for checking for these independently. + * + * @param str String + * @param start Begin + * @param end End + * @return Double value + */ + public static double parseDouble(final CharSequence str, final int start, final int end) { + // Current position and character. + int pos = start; + char cur = str.charAt(pos); + + // Match for NaN spellings + if(matchNaN(str, cur, pos, end)) { + return Double.NaN; + } + // Match sign + boolean isNegative = (cur == '-'); + // Carefully consume the - character, update c and i: + if((isNegative || (cur == '+')) && (++pos < end)) { + cur = str.charAt(pos); + } + if(matchInf(str, cur, pos, end)) { + return isNegative ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY; + } + + // Begin parsing real numbers! + if(((cur < '0') || (cur > '9')) && (cur != '.')) { + throw NOT_A_NUMBER; + } + + // Parse digits into a long, remember offset of decimal point. + long decimal = 0; + int decimalPoint = -1; + while(true) { + final int digit = cur - '0'; + if((digit >= 0) && (digit <= 9)) { + final long tmp = (decimal << 3) + (decimal << 1) + digit; + if((decimal > MAX_LONG_OVERFLOW) || (tmp < decimal)) { + throw PRECISION_OVERFLOW; + } + decimal = tmp; + } + else if((cur == '.') && (decimalPoint < 0)) { + decimalPoint = pos; + } + else { // No more digits, or a second dot. + break; + } + if(++pos < end) { + cur = str.charAt(pos); + } + else { + break; + } + } + // We need the offset from the back for adjusting the exponent: + // Note that we need the current value of i! + decimalPoint = (decimalPoint >= 0) ? pos - decimalPoint - 1 : 0; + + // Reads exponent. + int exp = 0; + if((pos < end) && ((cur == 'E') || (cur == 'e'))) { + cur = str.charAt(++pos); + final boolean isNegativeExp = (cur == '-'); + if((isNegativeExp || (cur == '+')) && (++pos < end)) { + cur = str.charAt(pos); + } + if((cur < '0') || (cur > '9')) { // At least one digit required. + throw INVALID_EXPONENT; + } + while(true) { + final int digit = cur - '0'; + if((digit >= 0) && (digit < 10)) { + final int tmp = (exp << 3) + (exp << 1) + digit; + // Actually, double can only handle Double.MAX_EXPONENT? How about + // subnormal? + if((exp > MAX_INT_OVERFLOW) || (tmp < exp)) { + throw EXPONENT_OVERFLOW; + } + exp = tmp; + } + else { + break; + } + if(++pos < end) { + cur = str.charAt(pos); + } + else { + break; + } + } + if(isNegativeExp) { + exp = -exp; + } + } + // Adjust exponent by the offset of the dot in our long. + if(decimalPoint >= 0) { + exp = exp - decimalPoint; + } + if(pos != end) { + throw TRAILING_CHARACTERS; + } + + return BitsUtil.lpow10(isNegative ? -decimal : decimal, exp); + } + + /** + * Match "NaN" in a number of different capitalizations. + * + * @param str String to match + * @param firstchar First character + * @param start Interval begin + * @param end Interval end + * @return {@code true} when NaN was recognized. + */ + private static boolean matchNaN(CharSequence str, char firstchar, int start, int end) { + final int len = end - start; + if(len < 2 || len > 3) { + return false; + } + if(firstchar != 'N' && firstchar != 'n') { + return false; + } + final char c1 = str.charAt(start + 1); + if(c1 != 'a' && c1 != 'A') { + return false; + } + // Accept just "NA", too: + if(len == 2) { + return true; + } + final char c2 = str.charAt(start + 2); + if(c2 != 'N' && c2 != 'n') { + return false; + } + return true; + } + + /** + * Maximum long that we can process without overflowing. + */ + private static final long MAX_LONG_OVERFLOW = Long.MAX_VALUE / 10; + + /** + * Maximum integer that we can process without overflowing. + */ + private static final int MAX_INT_OVERFLOW = Integer.MAX_VALUE / 10; + + /** + * Infinity pattern, with any capitalization + */ + private static final char[] INFINITY_PATTERN = { // + 'I', 'n', 'f', 'i', 'n', 'i', 't', 'y', // + 'i', 'N', 'F', 'I', 'N', 'I', 'T', 'Y' }; + + /** Length of pattern */ + private static final int INFINITY_LENGTH = INFINITY_PATTERN.length >> 1; + + /** + * Match "inf", "infinity" in a number of different capitalizations. + * + * @param str String to match + * @param firstchar First character + * @param start Interval begin + * @param end Interval end + * @return {@code true} when infinity was recognized. + */ + private static boolean matchInf(CharSequence str, char firstchar, int start, int end) { + final int len = end - start; + // The wonders of unicode. This is more than one byte on UTF-8 + if(len == 1 && firstchar == '∞') { + return true; + } + if(len != 3 && len != INFINITY_LENGTH) { + return false; + } + // Test beginning: "inf" + if(firstchar != 'I' && firstchar != 'i') { + return false; + } + for(int i = 1, j = INFINITY_LENGTH + 1; i < INFINITY_LENGTH; i++, j++) { + final char c = str.charAt(start + i); + if(c != INFINITY_PATTERN[i] && c != INFINITY_PATTERN[j]) { + return false; + } + if(i == 2 && len == 3) { + return true; + } + } + return true; + } + + /** + * Parse a long integer from a character sequence. + * + * @param str String + * @param start Begin + * @param end End + * @return Double value + */ + public static long parseLongBase10(final CharSequence str, final int start, final int end) { + // Current position and character. + int pos = start; + char cur = str.charAt(pos); + + // Match sign + boolean isNegative = (cur == '-'); + // Carefully consume the - character, update c and i: + if((isNegative || (cur == '+')) && (++pos < end)) { + cur = str.charAt(pos); + } + + // Begin parsing real numbers! + if((cur < '0') || (cur > '9')) { + throw NOT_A_NUMBER; + } + + // Parse digits into a long, remember offset of decimal point. + long decimal = 0; + while(true) { + final int digit = cur - '0'; + if((digit >= 0) && (digit <= 9)) { + final long tmp = (decimal << 3) + (decimal << 1) + digit; + if(tmp < decimal) { + throw PRECISION_OVERFLOW; + } + decimal = tmp; + } + else { // No more digits, or a second dot. + break; + } + if(++pos < end) { + cur = str.charAt(pos); + } + else { + break; + } + } + if(pos != end) { + throw TRAILING_CHARACTERS; + } + + return isNegative ? -decimal : decimal; + } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/InspectionUtil.java b/src/de/lmu/ifi/dbs/elki/utilities/InspectionUtil.java index 0d147420..29745335 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/InspectionUtil.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/InspectionUtil.java @@ -45,8 +45,6 @@ import de.lmu.ifi.dbs.elki.utilities.pairs.Pair; * A collection of inspection-related utility functions. * * @author Erich Schubert - * - * @apiviz.uses InspectionUtilFrequentlyScanned */ public class InspectionUtil { /** diff --git a/src/de/lmu/ifi/dbs/elki/utilities/RandomFactory.java b/src/de/lmu/ifi/dbs/elki/utilities/RandomFactory.java index 9b870acb..229afe5f 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/RandomFactory.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/RandomFactory.java @@ -86,4 +86,18 @@ public class RandomFactory { return new Random(); } } + + /** + * Get a <em>non-threadsafe</em> random generator. + * + * @return Random generator + */ + public Random getSingleThreadedRandom() { + if(seed != null) { + return new UnsafeRandom(seed.longValue()); + } + else { + return new UnsafeRandom(); + } + } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/utilities/UnsafeRandom.java b/src/de/lmu/ifi/dbs/elki/utilities/UnsafeRandom.java new file mode 100644 index 00000000..898b685a --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/UnsafeRandom.java @@ -0,0 +1,81 @@ +package de.lmu.ifi.dbs.elki.utilities; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2013 + 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.Random; + +/** + * Drop-in replacement for {@link java.util.Random}, but not using atomic long + * seeds. This implementation is <em>no longer thread-safe</em> (but faster)! + * + * @author Erich Schubert + */ +public class UnsafeRandom extends Random { + /** + * Serial version number. + */ + private static final long serialVersionUID = 1L; + + // These are the same constants as in {@link java.util.Random} + // since we want to leave the random sequence unchanged. + private static final long multiplier = 0x5DEECE66DL, addend = 0xBL, + mask = (1L << 48) - 1; + + /** + * The random seed. We can't use super.seed. + */ + private long seed; + + /** + * Constructor called only by localRandom.initialValue. + */ + public UnsafeRandom() { + super(); + } + + /** + * Constructor. + * + * @param seed Random generator seed. + */ + public UnsafeRandom(long seed) { + this.seed = (seed ^ multiplier) & mask; + } + + /** + * Throws {@code UnsupportedOperationException}. Setting seeds in this + * generator is not supported. + * + * @throws UnsupportedOperationException always + */ + @Override + public void setSeed(long seed) { + this.seed = (seed ^ multiplier) & mask; + } + + @Override + protected int next(int bits) { + seed = (seed * multiplier + addend) & mask; + return (int) (seed >>> (48 - bits)); + } +} diff --git a/src/de/lmu/ifi/dbs/elki/utilities/Util.java b/src/de/lmu/ifi/dbs/elki/utilities/Util.java index 439ef171..ffac6573 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/Util.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/Util.java @@ -42,6 +42,16 @@ public final class Util { private static final long HASHPRIME = 2654435761L; /** + * Detect Java 7. + */ + public static final boolean IS_JAVA7 = System.getProperty("java.version").startsWith("1.7."); + + /** + * Detect Oracle Java. + */ + public static final boolean IS_ORACLE_JAVA = System.getProperty("java.vm.vendor").startsWith("Oracle"); + + /** * Fake constructor: do not instantiate. */ private Util() { @@ -64,13 +74,14 @@ public final class Util { assert (cardinality >= 0) : "Cannot set a negative number of bits!"; assert (cardinality < capacity) : "Cannot set " + cardinality + " of " + capacity + " bits!"; BitSet bitset = new BitSet(capacity); - if (cardinality < capacity >>> 1) { - while (bitset.cardinality() < cardinality) { + if(cardinality < capacity >>> 1) { + while(bitset.cardinality() < cardinality) { bitset.set(random.nextInt(capacity)); } - } else { + } + else { bitset.flip(0, capacity); - while (bitset.cardinality() > cardinality) { + while(bitset.cardinality() > cardinality) { bitset.clear(random.nextInt(capacity)); } } @@ -119,11 +130,11 @@ public final class Util { * @return Mixed hash code */ public static int mixHashCodes(int... hash) { - if (hash.length == 0) { + if(hash.length == 0) { return 0; } long result = hash[0]; - for (int i = 1; i < hash.length; i++) { + for(int i = 1; i < hash.length; i++) { result = result * HASHPRIME + hash[i]; } return (int) result; diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/QuickSelect.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/QuickSelect.java index 3746ff87..d0a2cd20 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/QuickSelect.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/QuickSelect.java @@ -1347,7 +1347,7 @@ public class QuickSelect { pivot.seek(end - 1); // Begin partitioning - int i = start, j = end - 3; + int i = start, j = end - 2; refi.seek(i); refj.seek(j); // This is classic quicksort stuff 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 index 8fab6f2b..f03d39e9 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/ArrayLikeUtil.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/ArrayLikeUtil.java @@ -66,6 +66,11 @@ public final class ArrayLikeUtil { public static final NumberVectorAdapter<?> NUMBERVECTORADAPTER = new NumberVectorAdapter<Double>(); /** + * Adapter for matrixes, reinterpreted as flat arrays. + */ + public static final FlatMatrixAdapter FLATMATRIXADAPTER = new FlatMatrixAdapter(); + + /** * Use a double array in the array API. */ public static final NumberArrayAdapter<Double, double[]> DOUBLEARRAYADAPTER = new DoubleArrayAdapter(); diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/FlatMatrixAdapter.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/FlatMatrixAdapter.java new file mode 100644 index 00000000..18fbae5d --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/arraylike/FlatMatrixAdapter.java @@ -0,0 +1,85 @@ +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) 2013 + 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.math.linearalgebra.Matrix; + +/** + * Use a matrix as array, by flattening it into a sequence. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ +class FlatMatrixAdapter implements NumberArrayAdapter<Double, Matrix> { + /** + * Constructor. + * + * Use the static instance from {@link ArrayLikeUtil}! + */ + protected FlatMatrixAdapter() { + super(); + } + + @Override + public int size(Matrix array) { + return array.getColumnDimensionality() * array.getRowDimensionality(); + } + + @Override + @Deprecated + public Double get(Matrix array, int off) throws IndexOutOfBoundsException { + return Double.valueOf(getDouble(array, off)); + } + + @Override + public double getDouble(Matrix array, int off) throws IndexOutOfBoundsException { + return array.get(off / array.getColumnDimensionality(), off % array.getColumnDimensionality()); + } + + @Override + public float getFloat(Matrix array, int off) throws IndexOutOfBoundsException { + return (float) getDouble(array, off); + } + + @Override + public int getInteger(Matrix array, int off) throws IndexOutOfBoundsException { + return (int) getDouble(array, off); + } + + @Override + public short getShort(Matrix array, int off) throws IndexOutOfBoundsException { + return (short) getDouble(array, off); + } + + @Override + public long getLong(Matrix array, int off) throws IndexOutOfBoundsException { + return (long) getDouble(array, off); + } + + @Override + public byte getByte(Matrix array, int off) throws IndexOutOfBoundsException { + return (byte) getDouble(array, off); + } +} diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparableMaxHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparableMaxHeap.java index 222fe83a..d6937b4d 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparableMaxHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparableMaxHeap.java @@ -24,32 +24,11 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; */ import java.util.Arrays; -import java.util.ConcurrentModificationException; import de.lmu.ifi.dbs.elki.math.MathUtil; /** - * Advanced priority queue class, based on a binary heap (for small sizes), - * which will for larger heaps be accompanied by a 4-ary heap (attached below - * the root of the two-ary heap, making the root actually 3-ary). - * - * This code was automatically instantiated for the type: Comparable - * - * This combination was found to work quite well in benchmarks, but YMMV. - * - * Some other observations from benchmarking: - * <ul> - * <li>Bulk loading did not improve things</li> - * <li>Primitive heaps are substantially faster.</li> - * <li>Since an array in Java has an overhead of 12 bytes, odd-sized object and - * integer arrays are actually well aligned both for 2-ary and 4-ary heaps.</li> - * <li>Workload makes a huge difference. A load-once, poll-until-empty priority - * queue is something different than e.g. a top-k heap, which will see a lot of - * top element replacements.</li> - * <li>Random vs. increasing vs. decreasing vs. sawtooth insertion patterns for - * top-k make a difference.</li> - * <li>Different day, different benchmark results ...</li> - * </ul> + * Binary heap for primitive types. * * @author Erich Schubert * @@ -63,44 +42,16 @@ public class ComparableMaxHeap<K extends Comparable<? super K>> implements Objec protected Comparable<Object>[] twoheap; /** - * Extension heap. - */ - protected Comparable<Object>[] fourheap; - - /** * Current size of heap. */ protected int size; /** - * (Structural) modification counter. Used to invalidate iterators. - */ - protected int modCount = 0; - - /** - * Maximum size of the 2-ary heap. A complete 2-ary heap has (2^k-1) elements. - */ - private final static int TWO_HEAP_MAX_SIZE = (1 << 9) - 1; - - /** * Initial size of the 2-ary heap. */ private final static int TWO_HEAP_INITIAL_SIZE = (1 << 5) - 1; /** - * Initial size of 4-ary heap when initialized. - * - * 21 = 4-ary heap of height 2: 1 + 4 + 4*4 - * - * 85 = 4-ary heap of height 3: 21 + 4*4*4 - * - * 341 = 4-ary heap of height 4: 85 + 4*4*4*4 - * - * Since we last grew by 255 (to 511), let's use 341. - */ - private final static int FOUR_HEAP_INITIAL_SIZE = 341; - - /** * Constructor, with default size. */ @SuppressWarnings("unchecked") @@ -109,9 +60,6 @@ public class ComparableMaxHeap<K extends Comparable<? super K>> implements Objec Comparable<Object>[] twoheap = (Comparable<Object>[]) java.lang.reflect.Array.newInstance(Comparable.class, TWO_HEAP_INITIAL_SIZE); this.twoheap = twoheap; - this.fourheap = null; - this.size = 0; - this.modCount = 0; } /** @@ -122,27 +70,15 @@ public class ComparableMaxHeap<K extends Comparable<? super K>> implements Objec @SuppressWarnings("unchecked") public ComparableMaxHeap(int minsize) { super(); - if (minsize < TWO_HEAP_MAX_SIZE) { - final int size = MathUtil.nextPow2Int(minsize + 1) - 1; - Comparable<Object>[] twoheap = (Comparable<Object>[]) java.lang.reflect.Array.newInstance(Comparable.class, size); + final int size = MathUtil.nextPow2Int(minsize + 1) - 1; + Comparable<Object>[] twoheap = (Comparable<Object>[]) java.lang.reflect.Array.newInstance(Comparable.class, size); - this.twoheap = twoheap; - this.fourheap = null; - } else { - Comparable<Object>[] twoheap = (Comparable<Object>[]) java.lang.reflect.Array.newInstance(Comparable.class, TWO_HEAP_INITIAL_SIZE); - Comparable<Object>[] fourheap = (Comparable<Object>[]) java.lang.reflect.Array.newInstance(Comparable.class, minsize - TWO_HEAP_MAX_SIZE); - this.twoheap = twoheap; - this.fourheap = fourheap; - } - this.size = 0; - this.modCount = 0; + this.twoheap = twoheap; } @Override public void clear() { size = 0; - ++modCount; - fourheap = null; Arrays.fill(twoheap, null); } @@ -161,29 +97,14 @@ public class ComparableMaxHeap<K extends Comparable<? super K>> implements Objec public void add(K o) { final Comparable<Object> co = (Comparable<Object>)o; // System.err.println("Add: " + o); - if (size < TWO_HEAP_MAX_SIZE) { - if (size >= twoheap.length) { - // Grow by one layer. - twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); - } - final int twopos = size; - twoheap[twopos] = co; - ++size; - heapifyUp2(twopos, co); - ++modCount; - } else { - final int fourpos = size - TWO_HEAP_MAX_SIZE; - if (fourheap == null) { - fourheap = (Comparable<Object>[]) java.lang.reflect.Array.newInstance(Comparable.class, FOUR_HEAP_INITIAL_SIZE); - } else if (fourpos >= fourheap.length) { - // Grow extension heap by half. - fourheap = Arrays.copyOf(fourheap, fourheap.length + (fourheap.length >> 1)); - } - fourheap[fourpos] = co; - ++size; - heapifyUp4(fourpos, co); - ++modCount; + if (size >= twoheap.length) { + // Grow by one layer. + twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); } + final int twopos = size; + twoheap[twopos] = co; + ++size; + heapifyUp(twopos, co); } @Override @@ -200,7 +121,6 @@ public class ComparableMaxHeap<K extends Comparable<? super K>> implements Objec public K replaceTopElement(K reinsert) { final Comparable<Object> ret = twoheap[0]; heapifyDown((Comparable<Object>) reinsert); - ++modCount; return (K)ret; } @@ -210,7 +130,7 @@ public class ComparableMaxHeap<K extends Comparable<? super K>> implements Objec * @param twopos Position in 2-ary heap. * @param cur Current object */ - private void heapifyUp2(int twopos, Comparable<Object> cur) { + private void heapifyUp(int twopos, Comparable<Object> cur) { while (twopos > 0) { final int parent = (twopos - 1) >>> 1; Comparable<Object> par = twoheap[parent]; @@ -223,81 +143,30 @@ public class ComparableMaxHeap<K extends Comparable<? super K>> implements Objec twoheap[twopos] = cur; } - /** - * Heapify-Up method for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - */ - private void heapifyUp4(int fourpos, Comparable<Object> cur) { - while (fourpos > 0) { - final int parent = (fourpos - 1) >> 2; - Comparable<Object> par = fourheap[parent]; - if (cur.compareTo(par) <= 0) { - break; - } - fourheap[fourpos] = par; - fourpos = parent; - } - if (fourpos == 0 && twoheap[0].compareTo(cur) < 0) { - fourheap[0] = twoheap[0]; - twoheap[0] = cur; - } else { - fourheap[fourpos] = cur; - } - } - @Override @SuppressWarnings("unchecked") public K poll() { final Comparable<Object> ret = twoheap[0]; --size; // Replacement object: - if (size >= TWO_HEAP_MAX_SIZE) { - final int last = size - TWO_HEAP_MAX_SIZE; - final Comparable<Object> reinsert = fourheap[last]; - fourheap[last] = null; - heapifyDown(reinsert); - } else if (size > 0) { + if (size > 0) { final Comparable<Object> reinsert = twoheap[size]; twoheap[size] = null; heapifyDown(reinsert); } else { twoheap[0] = null; } - ++modCount; return (K)ret; } /** * Invoke heapify-down for the root object. * - * @param reinsert Object to insert. - */ - private void heapifyDown(Comparable<Object> reinsert) { - if (size > TWO_HEAP_MAX_SIZE) { - // Special case: 3-ary situation. - final int best = (twoheap[1].compareTo(twoheap[2]) >= 0) ? 1 : 2; - if (fourheap[0].compareTo(twoheap[best]) > 0) { - twoheap[0] = fourheap[0]; - heapifyDown4(0, reinsert); - } else { - twoheap[0] = twoheap[best]; - heapifyDown2(best, reinsert); - } - return; - } - heapifyDown2(0, reinsert); - } - - /** - * Heapify-Down for 2-ary heap. - * - * @param twopos Position in 2-ary heap. - * @param cur Current object + * @param cur Object to insert. */ - private void heapifyDown2(int twopos, Comparable<Object> cur) { - final int stop = Math.min(size, TWO_HEAP_MAX_SIZE) >>> 1; + private void heapifyDown(Comparable<Object> cur) { + final int stop = size >>> 1; + int twopos = 0; while (twopos < stop) { int bestchild = (twopos << 1) + 1; Comparable<Object> best = twoheap[bestchild]; @@ -315,51 +184,6 @@ public class ComparableMaxHeap<K extends Comparable<? super K>> implements Objec twoheap[twopos] = cur; } - /** - * Heapify-Down for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - */ - private void heapifyDown4(int fourpos, Comparable<Object> cur) { - final int stop = (size - TWO_HEAP_MAX_SIZE + 2) >>> 2; - while (fourpos < stop) { - final int child = (fourpos << 2) + 1; - Comparable<Object> best = fourheap[child]; - int bestchild = child, candidate = child + 1, minsize = candidate + TWO_HEAP_MAX_SIZE; - if (size > minsize) { - Comparable<Object> nextchild = fourheap[candidate]; - if (best.compareTo(nextchild) < 0) { - bestchild = candidate; - best = nextchild; - } - - minsize += 2; - if (size >= minsize) { - nextchild = fourheap[++candidate]; - if (best.compareTo(nextchild) < 0) { - bestchild = candidate; - best = nextchild; - } - - if (size > minsize) { - nextchild = fourheap[++candidate]; - if (best.compareTo(nextchild) < 0) { - bestchild = candidate; - best = nextchild; - } - } - } - } - if (cur.compareTo(best) >= 0) { - break; - } - fourheap[fourpos] = best; - fourpos = bestchild; - } - fourheap[fourpos] = cur; - } - @Override @SuppressWarnings("unchecked") public K peek() { @@ -403,16 +227,8 @@ public class ComparableMaxHeap<K extends Comparable<? super K>> implements Objec */ protected int pos = 0; - /** - * Modification counter we were initialized at. - */ - protected final int myModCount = modCount; - @Override public boolean valid() { - if (modCount != myModCount) { - throw new ConcurrentModificationException(); - } return pos < size; } @@ -425,7 +241,7 @@ public class ComparableMaxHeap<K extends Comparable<? super K>> implements Objec @Override public K get() { - return (K)((pos < TWO_HEAP_MAX_SIZE) ? twoheap[pos] : fourheap[pos - TWO_HEAP_MAX_SIZE]); + return (K)twoheap[pos]; } } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparableMinHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparableMinHeap.java index 3cc5a02f..167c6bc7 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparableMinHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparableMinHeap.java @@ -24,32 +24,11 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; */ import java.util.Arrays; -import java.util.ConcurrentModificationException; import de.lmu.ifi.dbs.elki.math.MathUtil; /** - * Advanced priority queue class, based on a binary heap (for small sizes), - * which will for larger heaps be accompanied by a 4-ary heap (attached below - * the root of the two-ary heap, making the root actually 3-ary). - * - * This code was automatically instantiated for the type: Comparable - * - * This combination was found to work quite well in benchmarks, but YMMV. - * - * Some other observations from benchmarking: - * <ul> - * <li>Bulk loading did not improve things</li> - * <li>Primitive heaps are substantially faster.</li> - * <li>Since an array in Java has an overhead of 12 bytes, odd-sized object and - * integer arrays are actually well aligned both for 2-ary and 4-ary heaps.</li> - * <li>Workload makes a huge difference. A load-once, poll-until-empty priority - * queue is something different than e.g. a top-k heap, which will see a lot of - * top element replacements.</li> - * <li>Random vs. increasing vs. decreasing vs. sawtooth insertion patterns for - * top-k make a difference.</li> - * <li>Different day, different benchmark results ...</li> - * </ul> + * Binary heap for primitive types. * * @author Erich Schubert * @@ -63,44 +42,16 @@ public class ComparableMinHeap<K extends Comparable<? super K>> implements Objec protected Comparable<Object>[] twoheap; /** - * Extension heap. - */ - protected Comparable<Object>[] fourheap; - - /** * Current size of heap. */ protected int size; /** - * (Structural) modification counter. Used to invalidate iterators. - */ - protected int modCount = 0; - - /** - * Maximum size of the 2-ary heap. A complete 2-ary heap has (2^k-1) elements. - */ - private final static int TWO_HEAP_MAX_SIZE = (1 << 9) - 1; - - /** * Initial size of the 2-ary heap. */ private final static int TWO_HEAP_INITIAL_SIZE = (1 << 5) - 1; /** - * Initial size of 4-ary heap when initialized. - * - * 21 = 4-ary heap of height 2: 1 + 4 + 4*4 - * - * 85 = 4-ary heap of height 3: 21 + 4*4*4 - * - * 341 = 4-ary heap of height 4: 85 + 4*4*4*4 - * - * Since we last grew by 255 (to 511), let's use 341. - */ - private final static int FOUR_HEAP_INITIAL_SIZE = 341; - - /** * Constructor, with default size. */ @SuppressWarnings("unchecked") @@ -109,9 +60,6 @@ public class ComparableMinHeap<K extends Comparable<? super K>> implements Objec Comparable<Object>[] twoheap = (Comparable<Object>[]) java.lang.reflect.Array.newInstance(Comparable.class, TWO_HEAP_INITIAL_SIZE); this.twoheap = twoheap; - this.fourheap = null; - this.size = 0; - this.modCount = 0; } /** @@ -122,27 +70,15 @@ public class ComparableMinHeap<K extends Comparable<? super K>> implements Objec @SuppressWarnings("unchecked") public ComparableMinHeap(int minsize) { super(); - if (minsize < TWO_HEAP_MAX_SIZE) { - final int size = MathUtil.nextPow2Int(minsize + 1) - 1; - Comparable<Object>[] twoheap = (Comparable<Object>[]) java.lang.reflect.Array.newInstance(Comparable.class, size); + final int size = MathUtil.nextPow2Int(minsize + 1) - 1; + Comparable<Object>[] twoheap = (Comparable<Object>[]) java.lang.reflect.Array.newInstance(Comparable.class, size); - this.twoheap = twoheap; - this.fourheap = null; - } else { - Comparable<Object>[] twoheap = (Comparable<Object>[]) java.lang.reflect.Array.newInstance(Comparable.class, TWO_HEAP_INITIAL_SIZE); - Comparable<Object>[] fourheap = (Comparable<Object>[]) java.lang.reflect.Array.newInstance(Comparable.class, minsize - TWO_HEAP_MAX_SIZE); - this.twoheap = twoheap; - this.fourheap = fourheap; - } - this.size = 0; - this.modCount = 0; + this.twoheap = twoheap; } @Override public void clear() { size = 0; - ++modCount; - fourheap = null; Arrays.fill(twoheap, null); } @@ -161,29 +97,14 @@ public class ComparableMinHeap<K extends Comparable<? super K>> implements Objec public void add(K o) { final Comparable<Object> co = (Comparable<Object>)o; // System.err.println("Add: " + o); - if (size < TWO_HEAP_MAX_SIZE) { - if (size >= twoheap.length) { - // Grow by one layer. - twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); - } - final int twopos = size; - twoheap[twopos] = co; - ++size; - heapifyUp2(twopos, co); - ++modCount; - } else { - final int fourpos = size - TWO_HEAP_MAX_SIZE; - if (fourheap == null) { - fourheap = (Comparable<Object>[]) java.lang.reflect.Array.newInstance(Comparable.class, FOUR_HEAP_INITIAL_SIZE); - } else if (fourpos >= fourheap.length) { - // Grow extension heap by half. - fourheap = Arrays.copyOf(fourheap, fourheap.length + (fourheap.length >> 1)); - } - fourheap[fourpos] = co; - ++size; - heapifyUp4(fourpos, co); - ++modCount; + if (size >= twoheap.length) { + // Grow by one layer. + twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); } + final int twopos = size; + twoheap[twopos] = co; + ++size; + heapifyUp(twopos, co); } @Override @@ -200,7 +121,6 @@ public class ComparableMinHeap<K extends Comparable<? super K>> implements Objec public K replaceTopElement(K reinsert) { final Comparable<Object> ret = twoheap[0]; heapifyDown((Comparable<Object>) reinsert); - ++modCount; return (K)ret; } @@ -210,7 +130,7 @@ public class ComparableMinHeap<K extends Comparable<? super K>> implements Objec * @param twopos Position in 2-ary heap. * @param cur Current object */ - private void heapifyUp2(int twopos, Comparable<Object> cur) { + private void heapifyUp(int twopos, Comparable<Object> cur) { while (twopos > 0) { final int parent = (twopos - 1) >>> 1; Comparable<Object> par = twoheap[parent]; @@ -223,81 +143,30 @@ public class ComparableMinHeap<K extends Comparable<? super K>> implements Objec twoheap[twopos] = cur; } - /** - * Heapify-Up method for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - */ - private void heapifyUp4(int fourpos, Comparable<Object> cur) { - while (fourpos > 0) { - final int parent = (fourpos - 1) >> 2; - Comparable<Object> par = fourheap[parent]; - if (cur.compareTo(par) >= 0) { - break; - } - fourheap[fourpos] = par; - fourpos = parent; - } - if (fourpos == 0 && twoheap[0].compareTo(cur) > 0) { - fourheap[0] = twoheap[0]; - twoheap[0] = cur; - } else { - fourheap[fourpos] = cur; - } - } - @Override @SuppressWarnings("unchecked") public K poll() { final Comparable<Object> ret = twoheap[0]; --size; // Replacement object: - if (size >= TWO_HEAP_MAX_SIZE) { - final int last = size - TWO_HEAP_MAX_SIZE; - final Comparable<Object> reinsert = fourheap[last]; - fourheap[last] = null; - heapifyDown(reinsert); - } else if (size > 0) { + if (size > 0) { final Comparable<Object> reinsert = twoheap[size]; twoheap[size] = null; heapifyDown(reinsert); } else { twoheap[0] = null; } - ++modCount; return (K)ret; } /** * Invoke heapify-down for the root object. * - * @param reinsert Object to insert. - */ - private void heapifyDown(Comparable<Object> reinsert) { - if (size > TWO_HEAP_MAX_SIZE) { - // Special case: 3-ary situation. - final int best = (twoheap[1].compareTo(twoheap[2]) <= 0) ? 1 : 2; - if (fourheap[0].compareTo(twoheap[best]) < 0) { - twoheap[0] = fourheap[0]; - heapifyDown4(0, reinsert); - } else { - twoheap[0] = twoheap[best]; - heapifyDown2(best, reinsert); - } - return; - } - heapifyDown2(0, reinsert); - } - - /** - * Heapify-Down for 2-ary heap. - * - * @param twopos Position in 2-ary heap. - * @param cur Current object + * @param cur Object to insert. */ - private void heapifyDown2(int twopos, Comparable<Object> cur) { - final int stop = Math.min(size, TWO_HEAP_MAX_SIZE) >>> 1; + private void heapifyDown(Comparable<Object> cur) { + final int stop = size >>> 1; + int twopos = 0; while (twopos < stop) { int bestchild = (twopos << 1) + 1; Comparable<Object> best = twoheap[bestchild]; @@ -315,51 +184,6 @@ public class ComparableMinHeap<K extends Comparable<? super K>> implements Objec twoheap[twopos] = cur; } - /** - * Heapify-Down for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - */ - private void heapifyDown4(int fourpos, Comparable<Object> cur) { - final int stop = (size - TWO_HEAP_MAX_SIZE + 2) >>> 2; - while (fourpos < stop) { - final int child = (fourpos << 2) + 1; - Comparable<Object> best = fourheap[child]; - int bestchild = child, candidate = child + 1, minsize = candidate + TWO_HEAP_MAX_SIZE; - if (size > minsize) { - Comparable<Object> nextchild = fourheap[candidate]; - if (best.compareTo(nextchild) > 0) { - bestchild = candidate; - best = nextchild; - } - - minsize += 2; - if (size >= minsize) { - nextchild = fourheap[++candidate]; - if (best.compareTo(nextchild) > 0) { - bestchild = candidate; - best = nextchild; - } - - if (size > minsize) { - nextchild = fourheap[++candidate]; - if (best.compareTo(nextchild) > 0) { - bestchild = candidate; - best = nextchild; - } - } - } - } - if (cur.compareTo(best) <= 0) { - break; - } - fourheap[fourpos] = best; - fourpos = bestchild; - } - fourheap[fourpos] = cur; - } - @Override @SuppressWarnings("unchecked") public K peek() { @@ -403,16 +227,8 @@ public class ComparableMinHeap<K extends Comparable<? super K>> implements Objec */ protected int pos = 0; - /** - * Modification counter we were initialized at. - */ - protected final int myModCount = modCount; - @Override public boolean valid() { - if (modCount != myModCount) { - throw new ConcurrentModificationException(); - } return pos < size; } @@ -425,7 +241,7 @@ public class ComparableMinHeap<K extends Comparable<? super K>> implements Objec @Override public K get() { - return (K)((pos < TWO_HEAP_MAX_SIZE) ? twoheap[pos] : fourheap[pos - TWO_HEAP_MAX_SIZE]); + return (K)twoheap[pos]; } } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparatorMaxHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparatorMaxHeap.java index 7b660d31..e5887c73 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparatorMaxHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparatorMaxHeap.java @@ -24,32 +24,11 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; */ import java.util.Arrays; -import java.util.ConcurrentModificationException; import de.lmu.ifi.dbs.elki.math.MathUtil; /** - * Advanced priority queue class, based on a binary heap (for small sizes), - * which will for larger heaps be accompanied by a 4-ary heap (attached below - * the root of the two-ary heap, making the root actually 3-ary). - * - * This code was automatically instantiated for the type: Comparator - * - * This combination was found to work quite well in benchmarks, but YMMV. - * - * Some other observations from benchmarking: - * <ul> - * <li>Bulk loading did not improve things</li> - * <li>Primitive heaps are substantially faster.</li> - * <li>Since an array in Java has an overhead of 12 bytes, odd-sized object and - * integer arrays are actually well aligned both for 2-ary and 4-ary heaps.</li> - * <li>Workload makes a huge difference. A load-once, poll-until-empty priority - * queue is something different than e.g. a top-k heap, which will see a lot of - * top element replacements.</li> - * <li>Random vs. increasing vs. decreasing vs. sawtooth insertion patterns for - * top-k make a difference.</li> - * <li>Different day, different benchmark results ...</li> - * </ul> + * Binary heap for primitive types. * * @author Erich Schubert * @@ -63,43 +42,15 @@ public class ComparatorMaxHeap<K> implements ObjectHeap<K> { protected Object[] twoheap; /** - * Extension heap. - */ - protected Object[] fourheap; - - /** * Current size of heap. */ protected int size; /** - * (Structural) modification counter. Used to invalidate iterators. - */ - protected int modCount = 0; - - /** - * Maximum size of the 2-ary heap. A complete 2-ary heap has (2^k-1) elements. - */ - private final static int TWO_HEAP_MAX_SIZE = (1 << 9) - 1; - - /** * Initial size of the 2-ary heap. */ private final static int TWO_HEAP_INITIAL_SIZE = (1 << 5) - 1; - /** - * Initial size of 4-ary heap when initialized. - * - * 21 = 4-ary heap of height 2: 1 + 4 + 4*4 - * - * 85 = 4-ary heap of height 3: 21 + 4*4*4 - * - * 341 = 4-ary heap of height 4: 85 + 4*4*4*4 - * - * Since we last grew by 255 (to 511), let's use 341. - */ - private final static int FOUR_HEAP_INITIAL_SIZE = 341; - /** * Comparator @@ -117,9 +68,6 @@ public class ComparatorMaxHeap<K> implements ObjectHeap<K> { Object[] twoheap = new Object[TWO_HEAP_INITIAL_SIZE]; this.twoheap = twoheap; - this.fourheap = null; - this.size = 0; - this.modCount = 0; } /** @@ -132,27 +80,15 @@ public class ComparatorMaxHeap<K> implements ObjectHeap<K> { public ComparatorMaxHeap(int minsize, java.util.Comparator<? super K> comparator) { super(); this.comparator = (java.util.Comparator<Object>) java.util.Comparator.class.cast(comparator); - if (minsize < TWO_HEAP_MAX_SIZE) { - final int size = MathUtil.nextPow2Int(minsize + 1) - 1; - Object[] twoheap = new Object[size]; + final int size = MathUtil.nextPow2Int(minsize + 1) - 1; + Object[] twoheap = new Object[size]; - this.twoheap = twoheap; - this.fourheap = null; - } else { - Object[] twoheap = new Object[TWO_HEAP_INITIAL_SIZE]; - Object[] fourheap = new Object[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - this.twoheap = twoheap; - this.fourheap = fourheap; - } - this.size = 0; - this.modCount = 0; + this.twoheap = twoheap; } @Override public void clear() { size = 0; - ++modCount; - fourheap = null; Arrays.fill(twoheap, null); } @@ -170,29 +106,14 @@ public class ComparatorMaxHeap<K> implements ObjectHeap<K> { public void add(K o) { final Object co = o; // System.err.println("Add: " + o); - if (size < TWO_HEAP_MAX_SIZE) { - if (size >= twoheap.length) { - // Grow by one layer. - twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); - } - final int twopos = size; - twoheap[twopos] = co; - ++size; - heapifyUp2(twopos, co); - ++modCount; - } else { - final int fourpos = size - TWO_HEAP_MAX_SIZE; - if (fourheap == null) { - fourheap = new Object[FOUR_HEAP_INITIAL_SIZE]; - } else if (fourpos >= fourheap.length) { - // Grow extension heap by half. - fourheap = Arrays.copyOf(fourheap, fourheap.length + (fourheap.length >> 1)); - } - fourheap[fourpos] = co; - ++size; - heapifyUp4(fourpos, co); - ++modCount; + if (size >= twoheap.length) { + // Grow by one layer. + twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); } + final int twopos = size; + twoheap[twopos] = co; + ++size; + heapifyUp(twopos, co); } @Override @@ -209,7 +130,6 @@ public class ComparatorMaxHeap<K> implements ObjectHeap<K> { public K replaceTopElement(K reinsert) { final Object ret = twoheap[0]; heapifyDown( reinsert); - ++modCount; return (K)ret; } @@ -219,7 +139,7 @@ public class ComparatorMaxHeap<K> implements ObjectHeap<K> { * @param twopos Position in 2-ary heap. * @param cur Current object */ - private void heapifyUp2(int twopos, Object cur) { + private void heapifyUp(int twopos, Object cur) { while (twopos > 0) { final int parent = (twopos - 1) >>> 1; Object par = twoheap[parent]; @@ -232,81 +152,30 @@ public class ComparatorMaxHeap<K> implements ObjectHeap<K> { twoheap[twopos] = cur; } - /** - * Heapify-Up method for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - */ - private void heapifyUp4(int fourpos, Object cur) { - while (fourpos > 0) { - final int parent = (fourpos - 1) >> 2; - Object par = fourheap[parent]; - if (comparator.compare(cur, par) <= 0) { - break; - } - fourheap[fourpos] = par; - fourpos = parent; - } - if (fourpos == 0 && comparator.compare(twoheap[0], cur) < 0) { - fourheap[0] = twoheap[0]; - twoheap[0] = cur; - } else { - fourheap[fourpos] = cur; - } - } - @Override @SuppressWarnings("unchecked") public K poll() { final Object ret = twoheap[0]; --size; // Replacement object: - if (size >= TWO_HEAP_MAX_SIZE) { - final int last = size - TWO_HEAP_MAX_SIZE; - final Object reinsert = fourheap[last]; - fourheap[last] = null; - heapifyDown(reinsert); - } else if (size > 0) { + if (size > 0) { final Object reinsert = twoheap[size]; twoheap[size] = null; heapifyDown(reinsert); } else { twoheap[0] = null; } - ++modCount; return (K)ret; } /** * Invoke heapify-down for the root object. * - * @param reinsert Object to insert. - */ - private void heapifyDown(Object reinsert) { - if (size > TWO_HEAP_MAX_SIZE) { - // Special case: 3-ary situation. - final int best = (comparator.compare(twoheap[1], twoheap[2]) >= 0) ? 1 : 2; - if (comparator.compare(fourheap[0], twoheap[best]) > 0) { - twoheap[0] = fourheap[0]; - heapifyDown4(0, reinsert); - } else { - twoheap[0] = twoheap[best]; - heapifyDown2(best, reinsert); - } - return; - } - heapifyDown2(0, reinsert); - } - - /** - * Heapify-Down for 2-ary heap. - * - * @param twopos Position in 2-ary heap. - * @param cur Current object + * @param cur Object to insert. */ - private void heapifyDown2(int twopos, Object cur) { - final int stop = Math.min(size, TWO_HEAP_MAX_SIZE) >>> 1; + private void heapifyDown(Object cur) { + final int stop = size >>> 1; + int twopos = 0; while (twopos < stop) { int bestchild = (twopos << 1) + 1; Object best = twoheap[bestchild]; @@ -324,51 +193,6 @@ public class ComparatorMaxHeap<K> implements ObjectHeap<K> { twoheap[twopos] = cur; } - /** - * Heapify-Down for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - */ - private void heapifyDown4(int fourpos, Object cur) { - final int stop = (size - TWO_HEAP_MAX_SIZE + 2) >>> 2; - while (fourpos < stop) { - final int child = (fourpos << 2) + 1; - Object best = fourheap[child]; - int bestchild = child, candidate = child + 1, minsize = candidate + TWO_HEAP_MAX_SIZE; - if (size > minsize) { - Object nextchild = fourheap[candidate]; - if (comparator.compare(best, nextchild) < 0) { - bestchild = candidate; - best = nextchild; - } - - minsize += 2; - if (size >= minsize) { - nextchild = fourheap[++candidate]; - if (comparator.compare(best, nextchild) < 0) { - bestchild = candidate; - best = nextchild; - } - - if (size > minsize) { - nextchild = fourheap[++candidate]; - if (comparator.compare(best, nextchild) < 0) { - bestchild = candidate; - best = nextchild; - } - } - } - } - if (comparator.compare(cur, best) >= 0) { - break; - } - fourheap[fourpos] = best; - fourpos = bestchild; - } - fourheap[fourpos] = cur; - } - @Override @SuppressWarnings("unchecked") public K peek() { @@ -412,16 +236,8 @@ public class ComparatorMaxHeap<K> implements ObjectHeap<K> { */ protected int pos = 0; - /** - * Modification counter we were initialized at. - */ - protected final int myModCount = modCount; - @Override public boolean valid() { - if (modCount != myModCount) { - throw new ConcurrentModificationException(); - } return pos < size; } @@ -434,7 +250,7 @@ public class ComparatorMaxHeap<K> implements ObjectHeap<K> { @Override public K get() { - return (K)((pos < TWO_HEAP_MAX_SIZE) ? twoheap[pos] : fourheap[pos - TWO_HEAP_MAX_SIZE]); + return (K)twoheap[pos]; } } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparatorMinHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparatorMinHeap.java index e12c5f64..215a78b6 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparatorMinHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ComparatorMinHeap.java @@ -24,32 +24,11 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; */ import java.util.Arrays; -import java.util.ConcurrentModificationException; import de.lmu.ifi.dbs.elki.math.MathUtil; /** - * Advanced priority queue class, based on a binary heap (for small sizes), - * which will for larger heaps be accompanied by a 4-ary heap (attached below - * the root of the two-ary heap, making the root actually 3-ary). - * - * This code was automatically instantiated for the type: Comparator - * - * This combination was found to work quite well in benchmarks, but YMMV. - * - * Some other observations from benchmarking: - * <ul> - * <li>Bulk loading did not improve things</li> - * <li>Primitive heaps are substantially faster.</li> - * <li>Since an array in Java has an overhead of 12 bytes, odd-sized object and - * integer arrays are actually well aligned both for 2-ary and 4-ary heaps.</li> - * <li>Workload makes a huge difference. A load-once, poll-until-empty priority - * queue is something different than e.g. a top-k heap, which will see a lot of - * top element replacements.</li> - * <li>Random vs. increasing vs. decreasing vs. sawtooth insertion patterns for - * top-k make a difference.</li> - * <li>Different day, different benchmark results ...</li> - * </ul> + * Binary heap for primitive types. * * @author Erich Schubert * @@ -63,43 +42,15 @@ public class ComparatorMinHeap<K> implements ObjectHeap<K> { protected Object[] twoheap; /** - * Extension heap. - */ - protected Object[] fourheap; - - /** * Current size of heap. */ protected int size; /** - * (Structural) modification counter. Used to invalidate iterators. - */ - protected int modCount = 0; - - /** - * Maximum size of the 2-ary heap. A complete 2-ary heap has (2^k-1) elements. - */ - private final static int TWO_HEAP_MAX_SIZE = (1 << 9) - 1; - - /** * Initial size of the 2-ary heap. */ private final static int TWO_HEAP_INITIAL_SIZE = (1 << 5) - 1; - /** - * Initial size of 4-ary heap when initialized. - * - * 21 = 4-ary heap of height 2: 1 + 4 + 4*4 - * - * 85 = 4-ary heap of height 3: 21 + 4*4*4 - * - * 341 = 4-ary heap of height 4: 85 + 4*4*4*4 - * - * Since we last grew by 255 (to 511), let's use 341. - */ - private final static int FOUR_HEAP_INITIAL_SIZE = 341; - /** * Comparator @@ -117,9 +68,6 @@ public class ComparatorMinHeap<K> implements ObjectHeap<K> { Object[] twoheap = new Object[TWO_HEAP_INITIAL_SIZE]; this.twoheap = twoheap; - this.fourheap = null; - this.size = 0; - this.modCount = 0; } /** @@ -132,27 +80,15 @@ public class ComparatorMinHeap<K> implements ObjectHeap<K> { public ComparatorMinHeap(int minsize, java.util.Comparator<? super K> comparator) { super(); this.comparator = (java.util.Comparator<Object>) java.util.Comparator.class.cast(comparator); - if (minsize < TWO_HEAP_MAX_SIZE) { - final int size = MathUtil.nextPow2Int(minsize + 1) - 1; - Object[] twoheap = new Object[size]; + final int size = MathUtil.nextPow2Int(minsize + 1) - 1; + Object[] twoheap = new Object[size]; - this.twoheap = twoheap; - this.fourheap = null; - } else { - Object[] twoheap = new Object[TWO_HEAP_INITIAL_SIZE]; - Object[] fourheap = new Object[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - this.twoheap = twoheap; - this.fourheap = fourheap; - } - this.size = 0; - this.modCount = 0; + this.twoheap = twoheap; } @Override public void clear() { size = 0; - ++modCount; - fourheap = null; Arrays.fill(twoheap, null); } @@ -170,29 +106,14 @@ public class ComparatorMinHeap<K> implements ObjectHeap<K> { public void add(K o) { final Object co = o; // System.err.println("Add: " + o); - if (size < TWO_HEAP_MAX_SIZE) { - if (size >= twoheap.length) { - // Grow by one layer. - twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); - } - final int twopos = size; - twoheap[twopos] = co; - ++size; - heapifyUp2(twopos, co); - ++modCount; - } else { - final int fourpos = size - TWO_HEAP_MAX_SIZE; - if (fourheap == null) { - fourheap = new Object[FOUR_HEAP_INITIAL_SIZE]; - } else if (fourpos >= fourheap.length) { - // Grow extension heap by half. - fourheap = Arrays.copyOf(fourheap, fourheap.length + (fourheap.length >> 1)); - } - fourheap[fourpos] = co; - ++size; - heapifyUp4(fourpos, co); - ++modCount; + if (size >= twoheap.length) { + // Grow by one layer. + twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); } + final int twopos = size; + twoheap[twopos] = co; + ++size; + heapifyUp(twopos, co); } @Override @@ -209,7 +130,6 @@ public class ComparatorMinHeap<K> implements ObjectHeap<K> { public K replaceTopElement(K reinsert) { final Object ret = twoheap[0]; heapifyDown( reinsert); - ++modCount; return (K)ret; } @@ -219,7 +139,7 @@ public class ComparatorMinHeap<K> implements ObjectHeap<K> { * @param twopos Position in 2-ary heap. * @param cur Current object */ - private void heapifyUp2(int twopos, Object cur) { + private void heapifyUp(int twopos, Object cur) { while (twopos > 0) { final int parent = (twopos - 1) >>> 1; Object par = twoheap[parent]; @@ -232,81 +152,30 @@ public class ComparatorMinHeap<K> implements ObjectHeap<K> { twoheap[twopos] = cur; } - /** - * Heapify-Up method for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - */ - private void heapifyUp4(int fourpos, Object cur) { - while (fourpos > 0) { - final int parent = (fourpos - 1) >> 2; - Object par = fourheap[parent]; - if (comparator.compare(cur, par) >= 0) { - break; - } - fourheap[fourpos] = par; - fourpos = parent; - } - if (fourpos == 0 && comparator.compare(twoheap[0], cur) > 0) { - fourheap[0] = twoheap[0]; - twoheap[0] = cur; - } else { - fourheap[fourpos] = cur; - } - } - @Override @SuppressWarnings("unchecked") public K poll() { final Object ret = twoheap[0]; --size; // Replacement object: - if (size >= TWO_HEAP_MAX_SIZE) { - final int last = size - TWO_HEAP_MAX_SIZE; - final Object reinsert = fourheap[last]; - fourheap[last] = null; - heapifyDown(reinsert); - } else if (size > 0) { + if (size > 0) { final Object reinsert = twoheap[size]; twoheap[size] = null; heapifyDown(reinsert); } else { twoheap[0] = null; } - ++modCount; return (K)ret; } /** * Invoke heapify-down for the root object. * - * @param reinsert Object to insert. - */ - private void heapifyDown(Object reinsert) { - if (size > TWO_HEAP_MAX_SIZE) { - // Special case: 3-ary situation. - final int best = (comparator.compare(twoheap[1], twoheap[2]) <= 0) ? 1 : 2; - if (comparator.compare(fourheap[0], twoheap[best]) < 0) { - twoheap[0] = fourheap[0]; - heapifyDown4(0, reinsert); - } else { - twoheap[0] = twoheap[best]; - heapifyDown2(best, reinsert); - } - return; - } - heapifyDown2(0, reinsert); - } - - /** - * Heapify-Down for 2-ary heap. - * - * @param twopos Position in 2-ary heap. - * @param cur Current object + * @param cur Object to insert. */ - private void heapifyDown2(int twopos, Object cur) { - final int stop = Math.min(size, TWO_HEAP_MAX_SIZE) >>> 1; + private void heapifyDown(Object cur) { + final int stop = size >>> 1; + int twopos = 0; while (twopos < stop) { int bestchild = (twopos << 1) + 1; Object best = twoheap[bestchild]; @@ -324,51 +193,6 @@ public class ComparatorMinHeap<K> implements ObjectHeap<K> { twoheap[twopos] = cur; } - /** - * Heapify-Down for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - */ - private void heapifyDown4(int fourpos, Object cur) { - final int stop = (size - TWO_HEAP_MAX_SIZE + 2) >>> 2; - while (fourpos < stop) { - final int child = (fourpos << 2) + 1; - Object best = fourheap[child]; - int bestchild = child, candidate = child + 1, minsize = candidate + TWO_HEAP_MAX_SIZE; - if (size > minsize) { - Object nextchild = fourheap[candidate]; - if (comparator.compare(best, nextchild) > 0) { - bestchild = candidate; - best = nextchild; - } - - minsize += 2; - if (size >= minsize) { - nextchild = fourheap[++candidate]; - if (comparator.compare(best, nextchild) > 0) { - bestchild = candidate; - best = nextchild; - } - - if (size > minsize) { - nextchild = fourheap[++candidate]; - if (comparator.compare(best, nextchild) > 0) { - bestchild = candidate; - best = nextchild; - } - } - } - } - if (comparator.compare(cur, best) <= 0) { - break; - } - fourheap[fourpos] = best; - fourpos = bestchild; - } - fourheap[fourpos] = cur; - } - @Override @SuppressWarnings("unchecked") public K peek() { @@ -412,16 +236,8 @@ public class ComparatorMinHeap<K> implements ObjectHeap<K> { */ protected int pos = 0; - /** - * Modification counter we were initialized at. - */ - protected final int myModCount = modCount; - @Override public boolean valid() { - if (modCount != myModCount) { - throw new ConcurrentModificationException(); - } return pos < size; } @@ -434,7 +250,7 @@ public class ComparatorMinHeap<K> implements ObjectHeap<K> { @Override public K get() { - return (K)((pos < TWO_HEAP_MAX_SIZE) ? twoheap[pos] : fourheap[pos - TWO_HEAP_MAX_SIZE]); + return (K)twoheap[pos]; } } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleHeap.java index acf77d86..c82f2a4a 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleHeap.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) 2013 + 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/heap/DoubleIntegerHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleIntegerHeap.java index c3bf85f4..5d8d31f7 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleIntegerHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleIntegerHeap.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) 2013 + 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/heap/DoubleIntegerMaxHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleIntegerMaxHeap.java index 34f1e889..e903c23d 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleIntegerMaxHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleIntegerMaxHeap.java @@ -24,32 +24,11 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; */ import java.util.Arrays; -import java.util.ConcurrentModificationException; import de.lmu.ifi.dbs.elki.math.MathUtil; /** - * Advanced priority queue class, based on a binary heap (for small sizes), - * which will for larger heaps be accompanied by a 4-ary heap (attached below - * the root of the two-ary heap, making the root actually 3-ary). - * - * This code was automatically instantiated for the types: Double and Integer - * - * This combination was found to work quite well in benchmarks, but YMMV. - * - * Some other observations from benchmarking: - * <ul> - * <li>Bulk loading did not improve things</li> - * <li>Primitive heaps are substantially faster.</li> - * <li>Since an array in Java has an overhead of 12 bytes, odd-sized object and - * integer arrays are actually well aligned both for 2-ary and 4-ary heaps.</li> - * <li>Workload makes a huge difference. A load-once, poll-until-empty priority - * queue is something different than e.g. a top-k heap, which will see a lot of - * top element replacements.</li> - * <li>Random vs. increasing vs. decreasing vs. sawtooth insertion patterns for - * top-k make a difference.</li> - * <li>Different day, different benchmark results ...</li> - * </ul> + * Binary heap for primitive types. * * @author Erich Schubert * @@ -67,49 +46,16 @@ public class DoubleIntegerMaxHeap implements DoubleIntegerHeap { protected int[] twovals; /** - * Extension heap. - */ - protected double[] fourheap; - - /** - * Extension heapvalues. - */ - protected int[] fourvals; - - /** * Current size of heap. */ protected int size; /** - * (Structural) modification counter. Used to invalidate iterators. - */ - protected int modCount = 0; - - /** - * Maximum size of the 2-ary heap. A complete 2-ary heap has (2^k-1) elements. - */ - private final static int TWO_HEAP_MAX_SIZE = (1 << 9) - 1; - - /** * Initial size of the 2-ary heap. */ private final static int TWO_HEAP_INITIAL_SIZE = (1 << 5) - 1; /** - * Initial size of 4-ary heap when initialized. - * - * 21 = 4-ary heap of height 2: 1 + 4 + 4*4 - * - * 85 = 4-ary heap of height 3: 21 + 4*4*4 - * - * 341 = 4-ary heap of height 4: 85 + 4*4*4*4 - * - * Since we last grew by 255 (to 511), let's use 341. - */ - private final static int FOUR_HEAP_INITIAL_SIZE = 341; - - /** * Constructor, with default size. */ public DoubleIntegerMaxHeap() { @@ -119,10 +65,6 @@ public class DoubleIntegerMaxHeap implements DoubleIntegerHeap { this.twoheap = twoheap; this.twovals = twovals; - this.fourheap = null; - this.fourvals = null; - this.size = 0; - this.modCount = 0; } /** @@ -132,35 +74,17 @@ public class DoubleIntegerMaxHeap implements DoubleIntegerHeap { */ public DoubleIntegerMaxHeap(int minsize) { super(); - if (minsize < TWO_HEAP_MAX_SIZE) { - final int size = MathUtil.nextPow2Int(minsize + 1) - 1; - double[] twoheap = new double[size]; - int[] twovals = new int[size]; + final int size = MathUtil.nextPow2Int(minsize + 1) - 1; + double[] twoheap = new double[size]; + int[] twovals = new int[size]; - this.twoheap = twoheap; - this.twovals = twovals; - this.fourheap = null; - this.fourvals = null; - } else { - double[] twoheap = new double[TWO_HEAP_INITIAL_SIZE]; - int[] twovals = new int[TWO_HEAP_INITIAL_SIZE]; - double[] fourheap = new double[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - int[] fourvals = new int[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - this.twoheap = twoheap; - this.twovals = twovals; - this.fourheap = fourheap; - this.fourvals = fourvals; - } - this.size = 0; - this.modCount = 0; + this.twoheap = twoheap; + this.twovals = twovals; } @Override public void clear() { size = 0; - ++modCount; - fourheap = null; - fourvals = null; Arrays.fill(twoheap, 0.0); Arrays.fill(twovals, 0); } @@ -180,34 +104,16 @@ public class DoubleIntegerMaxHeap implements DoubleIntegerHeap { final double co = o; final int cv = v; // System.err.println("Add: " + o); - if (size < TWO_HEAP_MAX_SIZE) { - if (size >= twoheap.length) { - // Grow by one layer. - twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); - twovals = Arrays.copyOf(twovals, twovals.length + twovals.length + 1); - } - final int twopos = size; - twoheap[twopos] = co; - twovals[twopos] = cv; - ++size; - heapifyUp2(twopos, co, cv); - ++modCount; - } else { - final int fourpos = size - TWO_HEAP_MAX_SIZE; - if (fourheap == null) { - fourheap = new double[FOUR_HEAP_INITIAL_SIZE]; - fourvals = new int[FOUR_HEAP_INITIAL_SIZE]; - } else if (fourpos >= fourheap.length) { - // Grow extension heap by half. - fourheap = Arrays.copyOf(fourheap, fourheap.length + (fourheap.length >> 1)); - fourvals = Arrays.copyOf(fourvals, fourvals.length + (fourvals.length >> 1)); - } - fourheap[fourpos] = co; - fourvals[fourpos] = cv; - ++size; - heapifyUp4(fourpos, co, cv); - ++modCount; + if (size >= twoheap.length) { + // Grow by one layer. + twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); + twovals = Arrays.copyOf(twovals, twovals.length + twovals.length + 1); } + final int twopos = size; + twoheap[twopos] = co; + twovals[twopos] = cv; + ++size; + heapifyUp(twopos, co, cv); } @Override @@ -222,7 +128,6 @@ public class DoubleIntegerMaxHeap implements DoubleIntegerHeap { @Override public void replaceTopElement(double reinsert, int val) { heapifyDown(reinsert, val); - ++modCount; } /** @@ -232,7 +137,7 @@ public class DoubleIntegerMaxHeap implements DoubleIntegerHeap { * @param cur Current object * @param val Current value */ - private void heapifyUp2(int twopos, double cur, int val) { + private void heapifyUp(int twopos, double cur, int val) { while (twopos > 0) { final int parent = (twopos - 1) >>> 1; double par = twoheap[parent]; @@ -247,47 +152,11 @@ public class DoubleIntegerMaxHeap implements DoubleIntegerHeap { twovals[twopos] = val; } - /** - * Heapify-Up method for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - * @param val Current value - */ - private void heapifyUp4(int fourpos, double cur, int val) { - while (fourpos > 0) { - final int parent = (fourpos - 1) >> 2; - double par = fourheap[parent]; - if (cur <= par) { - break; - } - fourheap[fourpos] = par; - fourvals[fourpos] = fourvals[parent]; - fourpos = parent; - } - if (fourpos == 0 && twoheap[0] < cur) { - fourheap[0] = twoheap[0]; - fourvals[0] = twovals[0]; - twoheap[0] = cur; - twovals[0] = val; - } else { - fourheap[fourpos] = cur; - fourvals[fourpos] = val; - } - } - @Override public void poll() { --size; // Replacement object: - if (size >= TWO_HEAP_MAX_SIZE) { - final int last = size - TWO_HEAP_MAX_SIZE; - final double reinsert = fourheap[last]; - final int reinsertv = fourvals[last]; - fourheap[last] = 0.0; - fourvals[last] = 0; - heapifyDown(reinsert, reinsertv); - } else if (size > 0) { + if (size > 0) { final double reinsert = twoheap[size]; final int reinsertv = twovals[size]; twoheap[size] = 0.0; @@ -297,42 +166,17 @@ public class DoubleIntegerMaxHeap implements DoubleIntegerHeap { twoheap[0] = 0.0; twovals[0] = 0; } - ++modCount; } /** * Invoke heapify-down for the root object. * - * @param reinsert Object to insert. - * @param val Value to reinsert. - */ - private void heapifyDown(double reinsert, int val) { - if (size > TWO_HEAP_MAX_SIZE) { - // Special case: 3-ary situation. - final int best = (twoheap[1] >= twoheap[2]) ? 1 : 2; - if (fourheap[0] > twoheap[best]) { - twoheap[0] = fourheap[0]; - twovals[0] = fourvals[0]; - heapifyDown4(0, reinsert, val); - } else { - twoheap[0] = twoheap[best]; - twovals[0] = twovals[best]; - heapifyDown2(best, reinsert, val); - } - return; - } - heapifyDown2(0, reinsert, val); - } - - /** - * Heapify-Down for 2-ary heap. - * - * @param twopos Position in 2-ary heap. - * @param cur Current object + * @param cur Object to insert. * @param val Value to reinsert. */ - private void heapifyDown2(int twopos, double cur, int val) { - final int stop = Math.min(size, TWO_HEAP_MAX_SIZE) >>> 1; + private void heapifyDown(double cur, int val) { + final int stop = size >>> 1; + int twopos = 0; while (twopos < stop) { int bestchild = (twopos << 1) + 1; double best = twoheap[bestchild]; @@ -352,54 +196,6 @@ public class DoubleIntegerMaxHeap implements DoubleIntegerHeap { twovals[twopos] = val; } - /** - * Heapify-Down for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - * @param val Value to reinsert. - */ - private void heapifyDown4(int fourpos, double cur, int val) { - final int stop = (size - TWO_HEAP_MAX_SIZE + 2) >>> 2; - while (fourpos < stop) { - final int child = (fourpos << 2) + 1; - double best = fourheap[child]; - int bestchild = child, candidate = child + 1, minsize = candidate + TWO_HEAP_MAX_SIZE; - if (size > minsize) { - double nextchild = fourheap[candidate]; - if (best < nextchild) { - bestchild = candidate; - best = nextchild; - } - - minsize += 2; - if (size >= minsize) { - nextchild = fourheap[++candidate]; - if (best < nextchild) { - bestchild = candidate; - best = nextchild; - } - - if (size > minsize) { - nextchild = fourheap[++candidate]; - if (best < nextchild) { - bestchild = candidate; - best = nextchild; - } - } - } - } - if (cur >= best) { - break; - } - fourheap[fourpos] = best; - fourvals[fourpos] = fourvals[bestchild]; - fourpos = bestchild; - } - fourheap[fourpos] = cur; - fourvals[fourpos] = val; - } - @Override public double peekKey() { return twoheap[0]; @@ -447,16 +243,8 @@ public class DoubleIntegerMaxHeap implements DoubleIntegerHeap { */ protected int pos = 0; - /** - * Modification counter we were initialized at. - */ - protected final int myModCount = modCount; - @Override public boolean valid() { - if (modCount != myModCount) { - throw new ConcurrentModificationException(); - } return pos < size; } @@ -467,12 +255,12 @@ public class DoubleIntegerMaxHeap implements DoubleIntegerHeap { @Override public double getKey() { - return ((pos < TWO_HEAP_MAX_SIZE) ? twoheap[pos] : fourheap[pos - TWO_HEAP_MAX_SIZE]); + return twoheap[pos]; } @Override public int getValue() { - return ((pos < TWO_HEAP_MAX_SIZE) ? twovals[pos] : fourvals[pos - TWO_HEAP_MAX_SIZE]); + return twovals[pos]; } } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleIntegerMinHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleIntegerMinHeap.java index ca6192ad..0e4e2204 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleIntegerMinHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleIntegerMinHeap.java @@ -24,32 +24,11 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; */ import java.util.Arrays; -import java.util.ConcurrentModificationException; import de.lmu.ifi.dbs.elki.math.MathUtil; /** - * Advanced priority queue class, based on a binary heap (for small sizes), - * which will for larger heaps be accompanied by a 4-ary heap (attached below - * the root of the two-ary heap, making the root actually 3-ary). - * - * This code was automatically instantiated for the types: Double and Integer - * - * This combination was found to work quite well in benchmarks, but YMMV. - * - * Some other observations from benchmarking: - * <ul> - * <li>Bulk loading did not improve things</li> - * <li>Primitive heaps are substantially faster.</li> - * <li>Since an array in Java has an overhead of 12 bytes, odd-sized object and - * integer arrays are actually well aligned both for 2-ary and 4-ary heaps.</li> - * <li>Workload makes a huge difference. A load-once, poll-until-empty priority - * queue is something different than e.g. a top-k heap, which will see a lot of - * top element replacements.</li> - * <li>Random vs. increasing vs. decreasing vs. sawtooth insertion patterns for - * top-k make a difference.</li> - * <li>Different day, different benchmark results ...</li> - * </ul> + * Binary heap for primitive types. * * @author Erich Schubert * @@ -67,49 +46,16 @@ public class DoubleIntegerMinHeap implements DoubleIntegerHeap { protected int[] twovals; /** - * Extension heap. - */ - protected double[] fourheap; - - /** - * Extension heapvalues. - */ - protected int[] fourvals; - - /** * Current size of heap. */ protected int size; /** - * (Structural) modification counter. Used to invalidate iterators. - */ - protected int modCount = 0; - - /** - * Maximum size of the 2-ary heap. A complete 2-ary heap has (2^k-1) elements. - */ - private final static int TWO_HEAP_MAX_SIZE = (1 << 9) - 1; - - /** * Initial size of the 2-ary heap. */ private final static int TWO_HEAP_INITIAL_SIZE = (1 << 5) - 1; /** - * Initial size of 4-ary heap when initialized. - * - * 21 = 4-ary heap of height 2: 1 + 4 + 4*4 - * - * 85 = 4-ary heap of height 3: 21 + 4*4*4 - * - * 341 = 4-ary heap of height 4: 85 + 4*4*4*4 - * - * Since we last grew by 255 (to 511), let's use 341. - */ - private final static int FOUR_HEAP_INITIAL_SIZE = 341; - - /** * Constructor, with default size. */ public DoubleIntegerMinHeap() { @@ -119,10 +65,6 @@ public class DoubleIntegerMinHeap implements DoubleIntegerHeap { this.twoheap = twoheap; this.twovals = twovals; - this.fourheap = null; - this.fourvals = null; - this.size = 0; - this.modCount = 0; } /** @@ -132,35 +74,17 @@ public class DoubleIntegerMinHeap implements DoubleIntegerHeap { */ public DoubleIntegerMinHeap(int minsize) { super(); - if (minsize < TWO_HEAP_MAX_SIZE) { - final int size = MathUtil.nextPow2Int(minsize + 1) - 1; - double[] twoheap = new double[size]; - int[] twovals = new int[size]; + final int size = MathUtil.nextPow2Int(minsize + 1) - 1; + double[] twoheap = new double[size]; + int[] twovals = new int[size]; - this.twoheap = twoheap; - this.twovals = twovals; - this.fourheap = null; - this.fourvals = null; - } else { - double[] twoheap = new double[TWO_HEAP_INITIAL_SIZE]; - int[] twovals = new int[TWO_HEAP_INITIAL_SIZE]; - double[] fourheap = new double[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - int[] fourvals = new int[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - this.twoheap = twoheap; - this.twovals = twovals; - this.fourheap = fourheap; - this.fourvals = fourvals; - } - this.size = 0; - this.modCount = 0; + this.twoheap = twoheap; + this.twovals = twovals; } @Override public void clear() { size = 0; - ++modCount; - fourheap = null; - fourvals = null; Arrays.fill(twoheap, 0.0); Arrays.fill(twovals, 0); } @@ -180,34 +104,16 @@ public class DoubleIntegerMinHeap implements DoubleIntegerHeap { final double co = o; final int cv = v; // System.err.println("Add: " + o); - if (size < TWO_HEAP_MAX_SIZE) { - if (size >= twoheap.length) { - // Grow by one layer. - twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); - twovals = Arrays.copyOf(twovals, twovals.length + twovals.length + 1); - } - final int twopos = size; - twoheap[twopos] = co; - twovals[twopos] = cv; - ++size; - heapifyUp2(twopos, co, cv); - ++modCount; - } else { - final int fourpos = size - TWO_HEAP_MAX_SIZE; - if (fourheap == null) { - fourheap = new double[FOUR_HEAP_INITIAL_SIZE]; - fourvals = new int[FOUR_HEAP_INITIAL_SIZE]; - } else if (fourpos >= fourheap.length) { - // Grow extension heap by half. - fourheap = Arrays.copyOf(fourheap, fourheap.length + (fourheap.length >> 1)); - fourvals = Arrays.copyOf(fourvals, fourvals.length + (fourvals.length >> 1)); - } - fourheap[fourpos] = co; - fourvals[fourpos] = cv; - ++size; - heapifyUp4(fourpos, co, cv); - ++modCount; + if (size >= twoheap.length) { + // Grow by one layer. + twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); + twovals = Arrays.copyOf(twovals, twovals.length + twovals.length + 1); } + final int twopos = size; + twoheap[twopos] = co; + twovals[twopos] = cv; + ++size; + heapifyUp(twopos, co, cv); } @Override @@ -222,7 +128,6 @@ public class DoubleIntegerMinHeap implements DoubleIntegerHeap { @Override public void replaceTopElement(double reinsert, int val) { heapifyDown(reinsert, val); - ++modCount; } /** @@ -232,7 +137,7 @@ public class DoubleIntegerMinHeap implements DoubleIntegerHeap { * @param cur Current object * @param val Current value */ - private void heapifyUp2(int twopos, double cur, int val) { + private void heapifyUp(int twopos, double cur, int val) { while (twopos > 0) { final int parent = (twopos - 1) >>> 1; double par = twoheap[parent]; @@ -247,47 +152,11 @@ public class DoubleIntegerMinHeap implements DoubleIntegerHeap { twovals[twopos] = val; } - /** - * Heapify-Up method for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - * @param val Current value - */ - private void heapifyUp4(int fourpos, double cur, int val) { - while (fourpos > 0) { - final int parent = (fourpos - 1) >> 2; - double par = fourheap[parent]; - if (cur >= par) { - break; - } - fourheap[fourpos] = par; - fourvals[fourpos] = fourvals[parent]; - fourpos = parent; - } - if (fourpos == 0 && twoheap[0] > cur) { - fourheap[0] = twoheap[0]; - fourvals[0] = twovals[0]; - twoheap[0] = cur; - twovals[0] = val; - } else { - fourheap[fourpos] = cur; - fourvals[fourpos] = val; - } - } - @Override public void poll() { --size; // Replacement object: - if (size >= TWO_HEAP_MAX_SIZE) { - final int last = size - TWO_HEAP_MAX_SIZE; - final double reinsert = fourheap[last]; - final int reinsertv = fourvals[last]; - fourheap[last] = 0.0; - fourvals[last] = 0; - heapifyDown(reinsert, reinsertv); - } else if (size > 0) { + if (size > 0) { final double reinsert = twoheap[size]; final int reinsertv = twovals[size]; twoheap[size] = 0.0; @@ -297,42 +166,17 @@ public class DoubleIntegerMinHeap implements DoubleIntegerHeap { twoheap[0] = 0.0; twovals[0] = 0; } - ++modCount; } /** * Invoke heapify-down for the root object. * - * @param reinsert Object to insert. - * @param val Value to reinsert. - */ - private void heapifyDown(double reinsert, int val) { - if (size > TWO_HEAP_MAX_SIZE) { - // Special case: 3-ary situation. - final int best = (twoheap[1] <= twoheap[2]) ? 1 : 2; - if (fourheap[0] < twoheap[best]) { - twoheap[0] = fourheap[0]; - twovals[0] = fourvals[0]; - heapifyDown4(0, reinsert, val); - } else { - twoheap[0] = twoheap[best]; - twovals[0] = twovals[best]; - heapifyDown2(best, reinsert, val); - } - return; - } - heapifyDown2(0, reinsert, val); - } - - /** - * Heapify-Down for 2-ary heap. - * - * @param twopos Position in 2-ary heap. - * @param cur Current object + * @param cur Object to insert. * @param val Value to reinsert. */ - private void heapifyDown2(int twopos, double cur, int val) { - final int stop = Math.min(size, TWO_HEAP_MAX_SIZE) >>> 1; + private void heapifyDown(double cur, int val) { + final int stop = size >>> 1; + int twopos = 0; while (twopos < stop) { int bestchild = (twopos << 1) + 1; double best = twoheap[bestchild]; @@ -352,54 +196,6 @@ public class DoubleIntegerMinHeap implements DoubleIntegerHeap { twovals[twopos] = val; } - /** - * Heapify-Down for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - * @param val Value to reinsert. - */ - private void heapifyDown4(int fourpos, double cur, int val) { - final int stop = (size - TWO_HEAP_MAX_SIZE + 2) >>> 2; - while (fourpos < stop) { - final int child = (fourpos << 2) + 1; - double best = fourheap[child]; - int bestchild = child, candidate = child + 1, minsize = candidate + TWO_HEAP_MAX_SIZE; - if (size > minsize) { - double nextchild = fourheap[candidate]; - if (best > nextchild) { - bestchild = candidate; - best = nextchild; - } - - minsize += 2; - if (size >= minsize) { - nextchild = fourheap[++candidate]; - if (best > nextchild) { - bestchild = candidate; - best = nextchild; - } - - if (size > minsize) { - nextchild = fourheap[++candidate]; - if (best > nextchild) { - bestchild = candidate; - best = nextchild; - } - } - } - } - if (cur <= best) { - break; - } - fourheap[fourpos] = best; - fourvals[fourpos] = fourvals[bestchild]; - fourpos = bestchild; - } - fourheap[fourpos] = cur; - fourvals[fourpos] = val; - } - @Override public double peekKey() { return twoheap[0]; @@ -447,16 +243,8 @@ public class DoubleIntegerMinHeap implements DoubleIntegerHeap { */ protected int pos = 0; - /** - * Modification counter we were initialized at. - */ - protected final int myModCount = modCount; - @Override public boolean valid() { - if (modCount != myModCount) { - throw new ConcurrentModificationException(); - } return pos < size; } @@ -467,12 +255,12 @@ public class DoubleIntegerMinHeap implements DoubleIntegerHeap { @Override public double getKey() { - return ((pos < TWO_HEAP_MAX_SIZE) ? twoheap[pos] : fourheap[pos - TWO_HEAP_MAX_SIZE]); + return twoheap[pos]; } @Override public int getValue() { - return ((pos < TWO_HEAP_MAX_SIZE) ? twovals[pos] : fourvals[pos - TWO_HEAP_MAX_SIZE]); + return twovals[pos]; } } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleLongMaxHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleLongMaxHeap.java index 6d15656c..b7508a61 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleLongMaxHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleLongMaxHeap.java @@ -24,32 +24,11 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; */ import java.util.Arrays; -import java.util.ConcurrentModificationException; import de.lmu.ifi.dbs.elki.math.MathUtil; /** - * Advanced priority queue class, based on a binary heap (for small sizes), - * which will for larger heaps be accompanied by a 4-ary heap (attached below - * the root of the two-ary heap, making the root actually 3-ary). - * - * This code was automatically instantiated for the types: Double and Long - * - * This combination was found to work quite well in benchmarks, but YMMV. - * - * Some other observations from benchmarking: - * <ul> - * <li>Bulk loading did not improve things</li> - * <li>Primitive heaps are substantially faster.</li> - * <li>Since an array in Java has an overhead of 12 bytes, odd-sized object and - * integer arrays are actually well aligned both for 2-ary and 4-ary heaps.</li> - * <li>Workload makes a huge difference. A load-once, poll-until-empty priority - * queue is something different than e.g. a top-k heap, which will see a lot of - * top element replacements.</li> - * <li>Random vs. increasing vs. decreasing vs. sawtooth insertion patterns for - * top-k make a difference.</li> - * <li>Different day, different benchmark results ...</li> - * </ul> + * Binary heap for primitive types. * * @author Erich Schubert * @@ -67,49 +46,16 @@ public class DoubleLongMaxHeap implements DoubleLongHeap { protected long[] twovals; /** - * Extension heap. - */ - protected double[] fourheap; - - /** - * Extension heapvalues. - */ - protected long[] fourvals; - - /** * Current size of heap. */ protected int size; /** - * (Structural) modification counter. Used to invalidate iterators. - */ - protected int modCount = 0; - - /** - * Maximum size of the 2-ary heap. A complete 2-ary heap has (2^k-1) elements. - */ - private final static int TWO_HEAP_MAX_SIZE = (1 << 9) - 1; - - /** * Initial size of the 2-ary heap. */ private final static int TWO_HEAP_INITIAL_SIZE = (1 << 5) - 1; /** - * Initial size of 4-ary heap when initialized. - * - * 21 = 4-ary heap of height 2: 1 + 4 + 4*4 - * - * 85 = 4-ary heap of height 3: 21 + 4*4*4 - * - * 341 = 4-ary heap of height 4: 85 + 4*4*4*4 - * - * Since we last grew by 255 (to 511), let's use 341. - */ - private final static int FOUR_HEAP_INITIAL_SIZE = 341; - - /** * Constructor, with default size. */ public DoubleLongMaxHeap() { @@ -119,10 +65,6 @@ public class DoubleLongMaxHeap implements DoubleLongHeap { this.twoheap = twoheap; this.twovals = twovals; - this.fourheap = null; - this.fourvals = null; - this.size = 0; - this.modCount = 0; } /** @@ -132,35 +74,17 @@ public class DoubleLongMaxHeap implements DoubleLongHeap { */ public DoubleLongMaxHeap(int minsize) { super(); - if (minsize < TWO_HEAP_MAX_SIZE) { - final int size = MathUtil.nextPow2Int(minsize + 1) - 1; - double[] twoheap = new double[size]; - long[] twovals = new long[size]; + final int size = MathUtil.nextPow2Int(minsize + 1) - 1; + double[] twoheap = new double[size]; + long[] twovals = new long[size]; - this.twoheap = twoheap; - this.twovals = twovals; - this.fourheap = null; - this.fourvals = null; - } else { - double[] twoheap = new double[TWO_HEAP_INITIAL_SIZE]; - long[] twovals = new long[TWO_HEAP_INITIAL_SIZE]; - double[] fourheap = new double[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - long[] fourvals = new long[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - this.twoheap = twoheap; - this.twovals = twovals; - this.fourheap = fourheap; - this.fourvals = fourvals; - } - this.size = 0; - this.modCount = 0; + this.twoheap = twoheap; + this.twovals = twovals; } @Override public void clear() { size = 0; - ++modCount; - fourheap = null; - fourvals = null; Arrays.fill(twoheap, 0.0); Arrays.fill(twovals, 0); } @@ -180,34 +104,16 @@ public class DoubleLongMaxHeap implements DoubleLongHeap { final double co = o; final long cv = v; // System.err.println("Add: " + o); - if (size < TWO_HEAP_MAX_SIZE) { - if (size >= twoheap.length) { - // Grow by one layer. - twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); - twovals = Arrays.copyOf(twovals, twovals.length + twovals.length + 1); - } - final int twopos = size; - twoheap[twopos] = co; - twovals[twopos] = cv; - ++size; - heapifyUp2(twopos, co, cv); - ++modCount; - } else { - final int fourpos = size - TWO_HEAP_MAX_SIZE; - if (fourheap == null) { - fourheap = new double[FOUR_HEAP_INITIAL_SIZE]; - fourvals = new long[FOUR_HEAP_INITIAL_SIZE]; - } else if (fourpos >= fourheap.length) { - // Grow extension heap by half. - fourheap = Arrays.copyOf(fourheap, fourheap.length + (fourheap.length >> 1)); - fourvals = Arrays.copyOf(fourvals, fourvals.length + (fourvals.length >> 1)); - } - fourheap[fourpos] = co; - fourvals[fourpos] = cv; - ++size; - heapifyUp4(fourpos, co, cv); - ++modCount; + if (size >= twoheap.length) { + // Grow by one layer. + twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); + twovals = Arrays.copyOf(twovals, twovals.length + twovals.length + 1); } + final int twopos = size; + twoheap[twopos] = co; + twovals[twopos] = cv; + ++size; + heapifyUp(twopos, co, cv); } @Override @@ -222,7 +128,6 @@ public class DoubleLongMaxHeap implements DoubleLongHeap { @Override public void replaceTopElement(double reinsert, long val) { heapifyDown(reinsert, val); - ++modCount; } /** @@ -232,7 +137,7 @@ public class DoubleLongMaxHeap implements DoubleLongHeap { * @param cur Current object * @param val Current value */ - private void heapifyUp2(int twopos, double cur, long val) { + private void heapifyUp(int twopos, double cur, long val) { while (twopos > 0) { final int parent = (twopos - 1) >>> 1; double par = twoheap[parent]; @@ -247,47 +152,11 @@ public class DoubleLongMaxHeap implements DoubleLongHeap { twovals[twopos] = val; } - /** - * Heapify-Up method for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - * @param val Current value - */ - private void heapifyUp4(int fourpos, double cur, long val) { - while (fourpos > 0) { - final int parent = (fourpos - 1) >> 2; - double par = fourheap[parent]; - if (cur <= par) { - break; - } - fourheap[fourpos] = par; - fourvals[fourpos] = fourvals[parent]; - fourpos = parent; - } - if (fourpos == 0 && twoheap[0] < cur) { - fourheap[0] = twoheap[0]; - fourvals[0] = twovals[0]; - twoheap[0] = cur; - twovals[0] = val; - } else { - fourheap[fourpos] = cur; - fourvals[fourpos] = val; - } - } - @Override public void poll() { --size; // Replacement object: - if (size >= TWO_HEAP_MAX_SIZE) { - final int last = size - TWO_HEAP_MAX_SIZE; - final double reinsert = fourheap[last]; - final long reinsertv = fourvals[last]; - fourheap[last] = 0.0; - fourvals[last] = 0; - heapifyDown(reinsert, reinsertv); - } else if (size > 0) { + if (size > 0) { final double reinsert = twoheap[size]; final long reinsertv = twovals[size]; twoheap[size] = 0.0; @@ -297,42 +166,17 @@ public class DoubleLongMaxHeap implements DoubleLongHeap { twoheap[0] = 0.0; twovals[0] = 0; } - ++modCount; } /** * Invoke heapify-down for the root object. * - * @param reinsert Object to insert. - * @param val Value to reinsert. - */ - private void heapifyDown(double reinsert, long val) { - if (size > TWO_HEAP_MAX_SIZE) { - // Special case: 3-ary situation. - final int best = (twoheap[1] >= twoheap[2]) ? 1 : 2; - if (fourheap[0] > twoheap[best]) { - twoheap[0] = fourheap[0]; - twovals[0] = fourvals[0]; - heapifyDown4(0, reinsert, val); - } else { - twoheap[0] = twoheap[best]; - twovals[0] = twovals[best]; - heapifyDown2(best, reinsert, val); - } - return; - } - heapifyDown2(0, reinsert, val); - } - - /** - * Heapify-Down for 2-ary heap. - * - * @param twopos Position in 2-ary heap. - * @param cur Current object + * @param cur Object to insert. * @param val Value to reinsert. */ - private void heapifyDown2(int twopos, double cur, long val) { - final int stop = Math.min(size, TWO_HEAP_MAX_SIZE) >>> 1; + private void heapifyDown(double cur, long val) { + final int stop = size >>> 1; + int twopos = 0; while (twopos < stop) { int bestchild = (twopos << 1) + 1; double best = twoheap[bestchild]; @@ -352,54 +196,6 @@ public class DoubleLongMaxHeap implements DoubleLongHeap { twovals[twopos] = val; } - /** - * Heapify-Down for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - * @param val Value to reinsert. - */ - private void heapifyDown4(int fourpos, double cur, long val) { - final int stop = (size - TWO_HEAP_MAX_SIZE + 2) >>> 2; - while (fourpos < stop) { - final int child = (fourpos << 2) + 1; - double best = fourheap[child]; - int bestchild = child, candidate = child + 1, minsize = candidate + TWO_HEAP_MAX_SIZE; - if (size > minsize) { - double nextchild = fourheap[candidate]; - if (best < nextchild) { - bestchild = candidate; - best = nextchild; - } - - minsize += 2; - if (size >= minsize) { - nextchild = fourheap[++candidate]; - if (best < nextchild) { - bestchild = candidate; - best = nextchild; - } - - if (size > minsize) { - nextchild = fourheap[++candidate]; - if (best < nextchild) { - bestchild = candidate; - best = nextchild; - } - } - } - } - if (cur >= best) { - break; - } - fourheap[fourpos] = best; - fourvals[fourpos] = fourvals[bestchild]; - fourpos = bestchild; - } - fourheap[fourpos] = cur; - fourvals[fourpos] = val; - } - @Override public double peekKey() { return twoheap[0]; @@ -447,16 +243,8 @@ public class DoubleLongMaxHeap implements DoubleLongHeap { */ protected int pos = 0; - /** - * Modification counter we were initialized at. - */ - protected final int myModCount = modCount; - @Override public boolean valid() { - if (modCount != myModCount) { - throw new ConcurrentModificationException(); - } return pos < size; } @@ -467,12 +255,12 @@ public class DoubleLongMaxHeap implements DoubleLongHeap { @Override public double getKey() { - return ((pos < TWO_HEAP_MAX_SIZE) ? twoheap[pos] : fourheap[pos - TWO_HEAP_MAX_SIZE]); + return twoheap[pos]; } @Override public long getValue() { - return ((pos < TWO_HEAP_MAX_SIZE) ? twovals[pos] : fourvals[pos - TWO_HEAP_MAX_SIZE]); + return twovals[pos]; } } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleLongMinHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleLongMinHeap.java index d38eb6e3..9fbe0300 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleLongMinHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleLongMinHeap.java @@ -24,32 +24,11 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; */ import java.util.Arrays; -import java.util.ConcurrentModificationException; import de.lmu.ifi.dbs.elki.math.MathUtil; /** - * Advanced priority queue class, based on a binary heap (for small sizes), - * which will for larger heaps be accompanied by a 4-ary heap (attached below - * the root of the two-ary heap, making the root actually 3-ary). - * - * This code was automatically instantiated for the types: Double and Long - * - * This combination was found to work quite well in benchmarks, but YMMV. - * - * Some other observations from benchmarking: - * <ul> - * <li>Bulk loading did not improve things</li> - * <li>Primitive heaps are substantially faster.</li> - * <li>Since an array in Java has an overhead of 12 bytes, odd-sized object and - * integer arrays are actually well aligned both for 2-ary and 4-ary heaps.</li> - * <li>Workload makes a huge difference. A load-once, poll-until-empty priority - * queue is something different than e.g. a top-k heap, which will see a lot of - * top element replacements.</li> - * <li>Random vs. increasing vs. decreasing vs. sawtooth insertion patterns for - * top-k make a difference.</li> - * <li>Different day, different benchmark results ...</li> - * </ul> + * Binary heap for primitive types. * * @author Erich Schubert * @@ -67,49 +46,16 @@ public class DoubleLongMinHeap implements DoubleLongHeap { protected long[] twovals; /** - * Extension heap. - */ - protected double[] fourheap; - - /** - * Extension heapvalues. - */ - protected long[] fourvals; - - /** * Current size of heap. */ protected int size; /** - * (Structural) modification counter. Used to invalidate iterators. - */ - protected int modCount = 0; - - /** - * Maximum size of the 2-ary heap. A complete 2-ary heap has (2^k-1) elements. - */ - private final static int TWO_HEAP_MAX_SIZE = (1 << 9) - 1; - - /** * Initial size of the 2-ary heap. */ private final static int TWO_HEAP_INITIAL_SIZE = (1 << 5) - 1; /** - * Initial size of 4-ary heap when initialized. - * - * 21 = 4-ary heap of height 2: 1 + 4 + 4*4 - * - * 85 = 4-ary heap of height 3: 21 + 4*4*4 - * - * 341 = 4-ary heap of height 4: 85 + 4*4*4*4 - * - * Since we last grew by 255 (to 511), let's use 341. - */ - private final static int FOUR_HEAP_INITIAL_SIZE = 341; - - /** * Constructor, with default size. */ public DoubleLongMinHeap() { @@ -119,10 +65,6 @@ public class DoubleLongMinHeap implements DoubleLongHeap { this.twoheap = twoheap; this.twovals = twovals; - this.fourheap = null; - this.fourvals = null; - this.size = 0; - this.modCount = 0; } /** @@ -132,35 +74,17 @@ public class DoubleLongMinHeap implements DoubleLongHeap { */ public DoubleLongMinHeap(int minsize) { super(); - if (minsize < TWO_HEAP_MAX_SIZE) { - final int size = MathUtil.nextPow2Int(minsize + 1) - 1; - double[] twoheap = new double[size]; - long[] twovals = new long[size]; + final int size = MathUtil.nextPow2Int(minsize + 1) - 1; + double[] twoheap = new double[size]; + long[] twovals = new long[size]; - this.twoheap = twoheap; - this.twovals = twovals; - this.fourheap = null; - this.fourvals = null; - } else { - double[] twoheap = new double[TWO_HEAP_INITIAL_SIZE]; - long[] twovals = new long[TWO_HEAP_INITIAL_SIZE]; - double[] fourheap = new double[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - long[] fourvals = new long[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - this.twoheap = twoheap; - this.twovals = twovals; - this.fourheap = fourheap; - this.fourvals = fourvals; - } - this.size = 0; - this.modCount = 0; + this.twoheap = twoheap; + this.twovals = twovals; } @Override public void clear() { size = 0; - ++modCount; - fourheap = null; - fourvals = null; Arrays.fill(twoheap, 0.0); Arrays.fill(twovals, 0); } @@ -180,34 +104,16 @@ public class DoubleLongMinHeap implements DoubleLongHeap { final double co = o; final long cv = v; // System.err.println("Add: " + o); - if (size < TWO_HEAP_MAX_SIZE) { - if (size >= twoheap.length) { - // Grow by one layer. - twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); - twovals = Arrays.copyOf(twovals, twovals.length + twovals.length + 1); - } - final int twopos = size; - twoheap[twopos] = co; - twovals[twopos] = cv; - ++size; - heapifyUp2(twopos, co, cv); - ++modCount; - } else { - final int fourpos = size - TWO_HEAP_MAX_SIZE; - if (fourheap == null) { - fourheap = new double[FOUR_HEAP_INITIAL_SIZE]; - fourvals = new long[FOUR_HEAP_INITIAL_SIZE]; - } else if (fourpos >= fourheap.length) { - // Grow extension heap by half. - fourheap = Arrays.copyOf(fourheap, fourheap.length + (fourheap.length >> 1)); - fourvals = Arrays.copyOf(fourvals, fourvals.length + (fourvals.length >> 1)); - } - fourheap[fourpos] = co; - fourvals[fourpos] = cv; - ++size; - heapifyUp4(fourpos, co, cv); - ++modCount; + if (size >= twoheap.length) { + // Grow by one layer. + twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); + twovals = Arrays.copyOf(twovals, twovals.length + twovals.length + 1); } + final int twopos = size; + twoheap[twopos] = co; + twovals[twopos] = cv; + ++size; + heapifyUp(twopos, co, cv); } @Override @@ -222,7 +128,6 @@ public class DoubleLongMinHeap implements DoubleLongHeap { @Override public void replaceTopElement(double reinsert, long val) { heapifyDown(reinsert, val); - ++modCount; } /** @@ -232,7 +137,7 @@ public class DoubleLongMinHeap implements DoubleLongHeap { * @param cur Current object * @param val Current value */ - private void heapifyUp2(int twopos, double cur, long val) { + private void heapifyUp(int twopos, double cur, long val) { while (twopos > 0) { final int parent = (twopos - 1) >>> 1; double par = twoheap[parent]; @@ -247,47 +152,11 @@ public class DoubleLongMinHeap implements DoubleLongHeap { twovals[twopos] = val; } - /** - * Heapify-Up method for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - * @param val Current value - */ - private void heapifyUp4(int fourpos, double cur, long val) { - while (fourpos > 0) { - final int parent = (fourpos - 1) >> 2; - double par = fourheap[parent]; - if (cur >= par) { - break; - } - fourheap[fourpos] = par; - fourvals[fourpos] = fourvals[parent]; - fourpos = parent; - } - if (fourpos == 0 && twoheap[0] > cur) { - fourheap[0] = twoheap[0]; - fourvals[0] = twovals[0]; - twoheap[0] = cur; - twovals[0] = val; - } else { - fourheap[fourpos] = cur; - fourvals[fourpos] = val; - } - } - @Override public void poll() { --size; // Replacement object: - if (size >= TWO_HEAP_MAX_SIZE) { - final int last = size - TWO_HEAP_MAX_SIZE; - final double reinsert = fourheap[last]; - final long reinsertv = fourvals[last]; - fourheap[last] = 0.0; - fourvals[last] = 0; - heapifyDown(reinsert, reinsertv); - } else if (size > 0) { + if (size > 0) { final double reinsert = twoheap[size]; final long reinsertv = twovals[size]; twoheap[size] = 0.0; @@ -297,42 +166,17 @@ public class DoubleLongMinHeap implements DoubleLongHeap { twoheap[0] = 0.0; twovals[0] = 0; } - ++modCount; } /** * Invoke heapify-down for the root object. * - * @param reinsert Object to insert. - * @param val Value to reinsert. - */ - private void heapifyDown(double reinsert, long val) { - if (size > TWO_HEAP_MAX_SIZE) { - // Special case: 3-ary situation. - final int best = (twoheap[1] <= twoheap[2]) ? 1 : 2; - if (fourheap[0] < twoheap[best]) { - twoheap[0] = fourheap[0]; - twovals[0] = fourvals[0]; - heapifyDown4(0, reinsert, val); - } else { - twoheap[0] = twoheap[best]; - twovals[0] = twovals[best]; - heapifyDown2(best, reinsert, val); - } - return; - } - heapifyDown2(0, reinsert, val); - } - - /** - * Heapify-Down for 2-ary heap. - * - * @param twopos Position in 2-ary heap. - * @param cur Current object + * @param cur Object to insert. * @param val Value to reinsert. */ - private void heapifyDown2(int twopos, double cur, long val) { - final int stop = Math.min(size, TWO_HEAP_MAX_SIZE) >>> 1; + private void heapifyDown(double cur, long val) { + final int stop = size >>> 1; + int twopos = 0; while (twopos < stop) { int bestchild = (twopos << 1) + 1; double best = twoheap[bestchild]; @@ -352,54 +196,6 @@ public class DoubleLongMinHeap implements DoubleLongHeap { twovals[twopos] = val; } - /** - * Heapify-Down for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - * @param val Value to reinsert. - */ - private void heapifyDown4(int fourpos, double cur, long val) { - final int stop = (size - TWO_HEAP_MAX_SIZE + 2) >>> 2; - while (fourpos < stop) { - final int child = (fourpos << 2) + 1; - double best = fourheap[child]; - int bestchild = child, candidate = child + 1, minsize = candidate + TWO_HEAP_MAX_SIZE; - if (size > minsize) { - double nextchild = fourheap[candidate]; - if (best > nextchild) { - bestchild = candidate; - best = nextchild; - } - - minsize += 2; - if (size >= minsize) { - nextchild = fourheap[++candidate]; - if (best > nextchild) { - bestchild = candidate; - best = nextchild; - } - - if (size > minsize) { - nextchild = fourheap[++candidate]; - if (best > nextchild) { - bestchild = candidate; - best = nextchild; - } - } - } - } - if (cur <= best) { - break; - } - fourheap[fourpos] = best; - fourvals[fourpos] = fourvals[bestchild]; - fourpos = bestchild; - } - fourheap[fourpos] = cur; - fourvals[fourpos] = val; - } - @Override public double peekKey() { return twoheap[0]; @@ -447,16 +243,8 @@ public class DoubleLongMinHeap implements DoubleLongHeap { */ protected int pos = 0; - /** - * Modification counter we were initialized at. - */ - protected final int myModCount = modCount; - @Override public boolean valid() { - if (modCount != myModCount) { - throw new ConcurrentModificationException(); - } return pos < size; } @@ -467,12 +255,12 @@ public class DoubleLongMinHeap implements DoubleLongHeap { @Override public double getKey() { - return ((pos < TWO_HEAP_MAX_SIZE) ? twoheap[pos] : fourheap[pos - TWO_HEAP_MAX_SIZE]); + return twoheap[pos]; } @Override public long getValue() { - return ((pos < TWO_HEAP_MAX_SIZE) ? twovals[pos] : fourvals[pos - TWO_HEAP_MAX_SIZE]); + return twovals[pos]; } } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleMaxHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleMaxHeap.java index 7ea28f14..2c74b34b 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleMaxHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleMaxHeap.java @@ -24,32 +24,11 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; */ import java.util.Arrays; -import java.util.ConcurrentModificationException; import de.lmu.ifi.dbs.elki.math.MathUtil; /** - * Advanced priority queue class, based on a binary heap (for small sizes), - * which will for larger heaps be accompanied by a 4-ary heap (attached below - * the root of the two-ary heap, making the root actually 3-ary). - * - * This code was automatically instantiated for the type: Double - * - * This combination was found to work quite well in benchmarks, but YMMV. - * - * Some other observations from benchmarking: - * <ul> - * <li>Bulk loading did not improve things</li> - * <li>Primitive heaps are substantially faster.</li> - * <li>Since an array in Java has an overhead of 12 bytes, odd-sized object and - * integer arrays are actually well aligned both for 2-ary and 4-ary heaps.</li> - * <li>Workload makes a huge difference. A load-once, poll-until-empty priority - * queue is something different than e.g. a top-k heap, which will see a lot of - * top element replacements.</li> - * <li>Random vs. increasing vs. decreasing vs. sawtooth insertion patterns for - * top-k make a difference.</li> - * <li>Different day, different benchmark results ...</li> - * </ul> + * Binary heap for primitive types. * * @author Erich Schubert * @@ -62,44 +41,16 @@ public class DoubleMaxHeap implements DoubleHeap { protected double[] twoheap; /** - * Extension heap. - */ - protected double[] fourheap; - - /** * Current size of heap. */ protected int size; /** - * (Structural) modification counter. Used to invalidate iterators. - */ - protected int modCount = 0; - - /** - * Maximum size of the 2-ary heap. A complete 2-ary heap has (2^k-1) elements. - */ - private final static int TWO_HEAP_MAX_SIZE = (1 << 9) - 1; - - /** * Initial size of the 2-ary heap. */ private final static int TWO_HEAP_INITIAL_SIZE = (1 << 5) - 1; /** - * Initial size of 4-ary heap when initialized. - * - * 21 = 4-ary heap of height 2: 1 + 4 + 4*4 - * - * 85 = 4-ary heap of height 3: 21 + 4*4*4 - * - * 341 = 4-ary heap of height 4: 85 + 4*4*4*4 - * - * Since we last grew by 255 (to 511), let's use 341. - */ - private final static int FOUR_HEAP_INITIAL_SIZE = 341; - - /** * Constructor, with default size. */ public DoubleMaxHeap() { @@ -107,9 +58,6 @@ public class DoubleMaxHeap implements DoubleHeap { double[] twoheap = new double[TWO_HEAP_INITIAL_SIZE]; this.twoheap = twoheap; - this.fourheap = null; - this.size = 0; - this.modCount = 0; } /** @@ -119,27 +67,15 @@ public class DoubleMaxHeap implements DoubleHeap { */ public DoubleMaxHeap(int minsize) { super(); - if (minsize < TWO_HEAP_MAX_SIZE) { - final int size = MathUtil.nextPow2Int(minsize + 1) - 1; - double[] twoheap = new double[size]; + final int size = MathUtil.nextPow2Int(minsize + 1) - 1; + double[] twoheap = new double[size]; - this.twoheap = twoheap; - this.fourheap = null; - } else { - double[] twoheap = new double[TWO_HEAP_INITIAL_SIZE]; - double[] fourheap = new double[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - this.twoheap = twoheap; - this.fourheap = fourheap; - } - this.size = 0; - this.modCount = 0; + this.twoheap = twoheap; } @Override public void clear() { size = 0; - ++modCount; - fourheap = null; Arrays.fill(twoheap, 0.0); } @@ -157,29 +93,14 @@ public class DoubleMaxHeap implements DoubleHeap { public void add(double o) { final double co = o; // System.err.println("Add: " + o); - if (size < TWO_HEAP_MAX_SIZE) { - if (size >= twoheap.length) { - // Grow by one layer. - twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); - } - final int twopos = size; - twoheap[twopos] = co; - ++size; - heapifyUp2(twopos, co); - ++modCount; - } else { - final int fourpos = size - TWO_HEAP_MAX_SIZE; - if (fourheap == null) { - fourheap = new double[FOUR_HEAP_INITIAL_SIZE]; - } else if (fourpos >= fourheap.length) { - // Grow extension heap by half. - fourheap = Arrays.copyOf(fourheap, fourheap.length + (fourheap.length >> 1)); - } - fourheap[fourpos] = co; - ++size; - heapifyUp4(fourpos, co); - ++modCount; + if (size >= twoheap.length) { + // Grow by one layer. + twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); } + final int twopos = size; + twoheap[twopos] = co; + ++size; + heapifyUp(twopos, co); } @Override @@ -195,7 +116,6 @@ public class DoubleMaxHeap implements DoubleHeap { public double replaceTopElement(double reinsert) { final double ret = twoheap[0]; heapifyDown( reinsert); - ++modCount; return ret; } @@ -205,7 +125,7 @@ public class DoubleMaxHeap implements DoubleHeap { * @param twopos Position in 2-ary heap. * @param cur Current object */ - private void heapifyUp2(int twopos, double cur) { + private void heapifyUp(int twopos, double cur) { while (twopos > 0) { final int parent = (twopos - 1) >>> 1; double par = twoheap[parent]; @@ -218,80 +138,29 @@ public class DoubleMaxHeap implements DoubleHeap { twoheap[twopos] = cur; } - /** - * Heapify-Up method for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - */ - private void heapifyUp4(int fourpos, double cur) { - while (fourpos > 0) { - final int parent = (fourpos - 1) >> 2; - double par = fourheap[parent]; - if (cur <= par) { - break; - } - fourheap[fourpos] = par; - fourpos = parent; - } - if (fourpos == 0 && twoheap[0] < cur) { - fourheap[0] = twoheap[0]; - twoheap[0] = cur; - } else { - fourheap[fourpos] = cur; - } - } - @Override public double poll() { final double ret = twoheap[0]; --size; // Replacement object: - if (size >= TWO_HEAP_MAX_SIZE) { - final int last = size - TWO_HEAP_MAX_SIZE; - final double reinsert = fourheap[last]; - fourheap[last] = 0.0; - heapifyDown(reinsert); - } else if (size > 0) { + if (size > 0) { final double reinsert = twoheap[size]; twoheap[size] = 0.0; heapifyDown(reinsert); } else { twoheap[0] = 0.0; } - ++modCount; return ret; } /** * Invoke heapify-down for the root object. * - * @param reinsert Object to insert. - */ - private void heapifyDown(double reinsert) { - if (size > TWO_HEAP_MAX_SIZE) { - // Special case: 3-ary situation. - final int best = (twoheap[1] >= twoheap[2]) ? 1 : 2; - if (fourheap[0] > twoheap[best]) { - twoheap[0] = fourheap[0]; - heapifyDown4(0, reinsert); - } else { - twoheap[0] = twoheap[best]; - heapifyDown2(best, reinsert); - } - return; - } - heapifyDown2(0, reinsert); - } - - /** - * Heapify-Down for 2-ary heap. - * - * @param twopos Position in 2-ary heap. - * @param cur Current object + * @param cur Object to insert. */ - private void heapifyDown2(int twopos, double cur) { - final int stop = Math.min(size, TWO_HEAP_MAX_SIZE) >>> 1; + private void heapifyDown(double cur) { + final int stop = size >>> 1; + int twopos = 0; while (twopos < stop) { int bestchild = (twopos << 1) + 1; double best = twoheap[bestchild]; @@ -309,51 +178,6 @@ public class DoubleMaxHeap implements DoubleHeap { twoheap[twopos] = cur; } - /** - * Heapify-Down for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - */ - private void heapifyDown4(int fourpos, double cur) { - final int stop = (size - TWO_HEAP_MAX_SIZE + 2) >>> 2; - while (fourpos < stop) { - final int child = (fourpos << 2) + 1; - double best = fourheap[child]; - int bestchild = child, candidate = child + 1, minsize = candidate + TWO_HEAP_MAX_SIZE; - if (size > minsize) { - double nextchild = fourheap[candidate]; - if (best < nextchild) { - bestchild = candidate; - best = nextchild; - } - - minsize += 2; - if (size >= minsize) { - nextchild = fourheap[++candidate]; - if (best < nextchild) { - bestchild = candidate; - best = nextchild; - } - - if (size > minsize) { - nextchild = fourheap[++candidate]; - if (best < nextchild) { - bestchild = candidate; - best = nextchild; - } - } - } - } - if (cur >= best) { - break; - } - fourheap[fourpos] = best; - fourpos = bestchild; - } - fourheap[fourpos] = cur; - } - @Override public double peek() { return twoheap[0]; @@ -396,16 +220,8 @@ public class DoubleMaxHeap implements DoubleHeap { */ protected int pos = 0; - /** - * Modification counter we were initialized at. - */ - protected final int myModCount = modCount; - @Override public boolean valid() { - if (modCount != myModCount) { - throw new ConcurrentModificationException(); - } return pos < size; } @@ -416,7 +232,7 @@ public class DoubleMaxHeap implements DoubleHeap { @Override public double get() { - return ((pos < TWO_HEAP_MAX_SIZE) ? twoheap[pos] : fourheap[pos - TWO_HEAP_MAX_SIZE]); + return twoheap[pos]; } } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleMinHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleMinHeap.java index e9334153..afc50296 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleMinHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleMinHeap.java @@ -24,32 +24,11 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; */ import java.util.Arrays; -import java.util.ConcurrentModificationException; import de.lmu.ifi.dbs.elki.math.MathUtil; /** - * Advanced priority queue class, based on a binary heap (for small sizes), - * which will for larger heaps be accompanied by a 4-ary heap (attached below - * the root of the two-ary heap, making the root actually 3-ary). - * - * This code was automatically instantiated for the type: Double - * - * This combination was found to work quite well in benchmarks, but YMMV. - * - * Some other observations from benchmarking: - * <ul> - * <li>Bulk loading did not improve things</li> - * <li>Primitive heaps are substantially faster.</li> - * <li>Since an array in Java has an overhead of 12 bytes, odd-sized object and - * integer arrays are actually well aligned both for 2-ary and 4-ary heaps.</li> - * <li>Workload makes a huge difference. A load-once, poll-until-empty priority - * queue is something different than e.g. a top-k heap, which will see a lot of - * top element replacements.</li> - * <li>Random vs. increasing vs. decreasing vs. sawtooth insertion patterns for - * top-k make a difference.</li> - * <li>Different day, different benchmark results ...</li> - * </ul> + * Binary heap for primitive types. * * @author Erich Schubert * @@ -62,44 +41,16 @@ public class DoubleMinHeap implements DoubleHeap { protected double[] twoheap; /** - * Extension heap. - */ - protected double[] fourheap; - - /** * Current size of heap. */ protected int size; /** - * (Structural) modification counter. Used to invalidate iterators. - */ - protected int modCount = 0; - - /** - * Maximum size of the 2-ary heap. A complete 2-ary heap has (2^k-1) elements. - */ - private final static int TWO_HEAP_MAX_SIZE = (1 << 9) - 1; - - /** * Initial size of the 2-ary heap. */ private final static int TWO_HEAP_INITIAL_SIZE = (1 << 5) - 1; /** - * Initial size of 4-ary heap when initialized. - * - * 21 = 4-ary heap of height 2: 1 + 4 + 4*4 - * - * 85 = 4-ary heap of height 3: 21 + 4*4*4 - * - * 341 = 4-ary heap of height 4: 85 + 4*4*4*4 - * - * Since we last grew by 255 (to 511), let's use 341. - */ - private final static int FOUR_HEAP_INITIAL_SIZE = 341; - - /** * Constructor, with default size. */ public DoubleMinHeap() { @@ -107,9 +58,6 @@ public class DoubleMinHeap implements DoubleHeap { double[] twoheap = new double[TWO_HEAP_INITIAL_SIZE]; this.twoheap = twoheap; - this.fourheap = null; - this.size = 0; - this.modCount = 0; } /** @@ -119,27 +67,15 @@ public class DoubleMinHeap implements DoubleHeap { */ public DoubleMinHeap(int minsize) { super(); - if (minsize < TWO_HEAP_MAX_SIZE) { - final int size = MathUtil.nextPow2Int(minsize + 1) - 1; - double[] twoheap = new double[size]; + final int size = MathUtil.nextPow2Int(minsize + 1) - 1; + double[] twoheap = new double[size]; - this.twoheap = twoheap; - this.fourheap = null; - } else { - double[] twoheap = new double[TWO_HEAP_INITIAL_SIZE]; - double[] fourheap = new double[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - this.twoheap = twoheap; - this.fourheap = fourheap; - } - this.size = 0; - this.modCount = 0; + this.twoheap = twoheap; } @Override public void clear() { size = 0; - ++modCount; - fourheap = null; Arrays.fill(twoheap, 0.0); } @@ -157,29 +93,14 @@ public class DoubleMinHeap implements DoubleHeap { public void add(double o) { final double co = o; // System.err.println("Add: " + o); - if (size < TWO_HEAP_MAX_SIZE) { - if (size >= twoheap.length) { - // Grow by one layer. - twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); - } - final int twopos = size; - twoheap[twopos] = co; - ++size; - heapifyUp2(twopos, co); - ++modCount; - } else { - final int fourpos = size - TWO_HEAP_MAX_SIZE; - if (fourheap == null) { - fourheap = new double[FOUR_HEAP_INITIAL_SIZE]; - } else if (fourpos >= fourheap.length) { - // Grow extension heap by half. - fourheap = Arrays.copyOf(fourheap, fourheap.length + (fourheap.length >> 1)); - } - fourheap[fourpos] = co; - ++size; - heapifyUp4(fourpos, co); - ++modCount; + if (size >= twoheap.length) { + // Grow by one layer. + twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); } + final int twopos = size; + twoheap[twopos] = co; + ++size; + heapifyUp(twopos, co); } @Override @@ -195,7 +116,6 @@ public class DoubleMinHeap implements DoubleHeap { public double replaceTopElement(double reinsert) { final double ret = twoheap[0]; heapifyDown( reinsert); - ++modCount; return ret; } @@ -205,7 +125,7 @@ public class DoubleMinHeap implements DoubleHeap { * @param twopos Position in 2-ary heap. * @param cur Current object */ - private void heapifyUp2(int twopos, double cur) { + private void heapifyUp(int twopos, double cur) { while (twopos > 0) { final int parent = (twopos - 1) >>> 1; double par = twoheap[parent]; @@ -218,80 +138,29 @@ public class DoubleMinHeap implements DoubleHeap { twoheap[twopos] = cur; } - /** - * Heapify-Up method for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - */ - private void heapifyUp4(int fourpos, double cur) { - while (fourpos > 0) { - final int parent = (fourpos - 1) >> 2; - double par = fourheap[parent]; - if (cur >= par) { - break; - } - fourheap[fourpos] = par; - fourpos = parent; - } - if (fourpos == 0 && twoheap[0] > cur) { - fourheap[0] = twoheap[0]; - twoheap[0] = cur; - } else { - fourheap[fourpos] = cur; - } - } - @Override public double poll() { final double ret = twoheap[0]; --size; // Replacement object: - if (size >= TWO_HEAP_MAX_SIZE) { - final int last = size - TWO_HEAP_MAX_SIZE; - final double reinsert = fourheap[last]; - fourheap[last] = 0.0; - heapifyDown(reinsert); - } else if (size > 0) { + if (size > 0) { final double reinsert = twoheap[size]; twoheap[size] = 0.0; heapifyDown(reinsert); } else { twoheap[0] = 0.0; } - ++modCount; return ret; } /** * Invoke heapify-down for the root object. * - * @param reinsert Object to insert. - */ - private void heapifyDown(double reinsert) { - if (size > TWO_HEAP_MAX_SIZE) { - // Special case: 3-ary situation. - final int best = (twoheap[1] <= twoheap[2]) ? 1 : 2; - if (fourheap[0] < twoheap[best]) { - twoheap[0] = fourheap[0]; - heapifyDown4(0, reinsert); - } else { - twoheap[0] = twoheap[best]; - heapifyDown2(best, reinsert); - } - return; - } - heapifyDown2(0, reinsert); - } - - /** - * Heapify-Down for 2-ary heap. - * - * @param twopos Position in 2-ary heap. - * @param cur Current object + * @param cur Object to insert. */ - private void heapifyDown2(int twopos, double cur) { - final int stop = Math.min(size, TWO_HEAP_MAX_SIZE) >>> 1; + private void heapifyDown(double cur) { + final int stop = size >>> 1; + int twopos = 0; while (twopos < stop) { int bestchild = (twopos << 1) + 1; double best = twoheap[bestchild]; @@ -309,51 +178,6 @@ public class DoubleMinHeap implements DoubleHeap { twoheap[twopos] = cur; } - /** - * Heapify-Down for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - */ - private void heapifyDown4(int fourpos, double cur) { - final int stop = (size - TWO_HEAP_MAX_SIZE + 2) >>> 2; - while (fourpos < stop) { - final int child = (fourpos << 2) + 1; - double best = fourheap[child]; - int bestchild = child, candidate = child + 1, minsize = candidate + TWO_HEAP_MAX_SIZE; - if (size > minsize) { - double nextchild = fourheap[candidate]; - if (best > nextchild) { - bestchild = candidate; - best = nextchild; - } - - minsize += 2; - if (size >= minsize) { - nextchild = fourheap[++candidate]; - if (best > nextchild) { - bestchild = candidate; - best = nextchild; - } - - if (size > minsize) { - nextchild = fourheap[++candidate]; - if (best > nextchild) { - bestchild = candidate; - best = nextchild; - } - } - } - } - if (cur <= best) { - break; - } - fourheap[fourpos] = best; - fourpos = bestchild; - } - fourheap[fourpos] = cur; - } - @Override public double peek() { return twoheap[0]; @@ -396,16 +220,8 @@ public class DoubleMinHeap implements DoubleHeap { */ protected int pos = 0; - /** - * Modification counter we were initialized at. - */ - protected final int myModCount = modCount; - @Override public boolean valid() { - if (modCount != myModCount) { - throw new ConcurrentModificationException(); - } return pos < size; } @@ -416,7 +232,7 @@ public class DoubleMinHeap implements DoubleHeap { @Override public double get() { - return ((pos < TWO_HEAP_MAX_SIZE) ? twoheap[pos] : fourheap[pos - TWO_HEAP_MAX_SIZE]); + return twoheap[pos]; } } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleObjectHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleObjectHeap.java index db65ce81..7323cd8d 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleObjectHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleObjectHeap.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) 2013 + 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/heap/DoubleObjectMaxHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleObjectMaxHeap.java index dd89573c..939c4d7e 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleObjectMaxHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleObjectMaxHeap.java @@ -24,32 +24,11 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; */ import java.util.Arrays; -import java.util.ConcurrentModificationException; import de.lmu.ifi.dbs.elki.math.MathUtil; /** - * Advanced priority queue class, based on a binary heap (for small sizes), - * which will for larger heaps be accompanied by a 4-ary heap (attached below - * the root of the two-ary heap, making the root actually 3-ary). - * - * This code was automatically instantiated for the types: Double and Object - * - * This combination was found to work quite well in benchmarks, but YMMV. - * - * Some other observations from benchmarking: - * <ul> - * <li>Bulk loading did not improve things</li> - * <li>Primitive heaps are substantially faster.</li> - * <li>Since an array in Java has an overhead of 12 bytes, odd-sized object and - * integer arrays are actually well aligned both for 2-ary and 4-ary heaps.</li> - * <li>Workload makes a huge difference. A load-once, poll-until-empty priority - * queue is something different than e.g. a top-k heap, which will see a lot of - * top element replacements.</li> - * <li>Random vs. increasing vs. decreasing vs. sawtooth insertion patterns for - * top-k make a difference.</li> - * <li>Different day, different benchmark results ...</li> - * </ul> + * Binary heap for primitive types. * * @author Erich Schubert * @@ -68,49 +47,16 @@ public class DoubleObjectMaxHeap<V> implements DoubleObjectHeap<V> { protected Object[] twovals; /** - * Extension heap. - */ - protected double[] fourheap; - - /** - * Extension heapvalues. - */ - protected Object[] fourvals; - - /** * Current size of heap. */ protected int size; /** - * (Structural) modification counter. Used to invalidate iterators. - */ - protected int modCount = 0; - - /** - * Maximum size of the 2-ary heap. A complete 2-ary heap has (2^k-1) elements. - */ - private final static int TWO_HEAP_MAX_SIZE = (1 << 9) - 1; - - /** * Initial size of the 2-ary heap. */ private final static int TWO_HEAP_INITIAL_SIZE = (1 << 5) - 1; /** - * Initial size of 4-ary heap when initialized. - * - * 21 = 4-ary heap of height 2: 1 + 4 + 4*4 - * - * 85 = 4-ary heap of height 3: 21 + 4*4*4 - * - * 341 = 4-ary heap of height 4: 85 + 4*4*4*4 - * - * Since we last grew by 255 (to 511), let's use 341. - */ - private final static int FOUR_HEAP_INITIAL_SIZE = 341; - - /** * Constructor, with default size. */ public DoubleObjectMaxHeap() { @@ -120,10 +66,6 @@ public class DoubleObjectMaxHeap<V> implements DoubleObjectHeap<V> { this.twoheap = twoheap; this.twovals = twovals; - this.fourheap = null; - this.fourvals = null; - this.size = 0; - this.modCount = 0; } /** @@ -133,35 +75,17 @@ public class DoubleObjectMaxHeap<V> implements DoubleObjectHeap<V> { */ public DoubleObjectMaxHeap(int minsize) { super(); - if (minsize < TWO_HEAP_MAX_SIZE) { - final int size = MathUtil.nextPow2Int(minsize + 1) - 1; - double[] twoheap = new double[size]; - Object[] twovals = new Object[size]; + final int size = MathUtil.nextPow2Int(minsize + 1) - 1; + double[] twoheap = new double[size]; + Object[] twovals = new Object[size]; - this.twoheap = twoheap; - this.twovals = twovals; - this.fourheap = null; - this.fourvals = null; - } else { - double[] twoheap = new double[TWO_HEAP_INITIAL_SIZE]; - Object[] twovals = new Object[TWO_HEAP_INITIAL_SIZE]; - double[] fourheap = new double[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - Object[] fourvals = new Object[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - this.twoheap = twoheap; - this.twovals = twovals; - this.fourheap = fourheap; - this.fourvals = fourvals; - } - this.size = 0; - this.modCount = 0; + this.twoheap = twoheap; + this.twovals = twovals; } @Override public void clear() { size = 0; - ++modCount; - fourheap = null; - fourvals = null; Arrays.fill(twoheap, 0.0); Arrays.fill(twovals, null); } @@ -181,34 +105,16 @@ public class DoubleObjectMaxHeap<V> implements DoubleObjectHeap<V> { final double co = o; final Object cv = (Object)v; // System.err.println("Add: " + o); - if (size < TWO_HEAP_MAX_SIZE) { - if (size >= twoheap.length) { - // Grow by one layer. - twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); - twovals = Arrays.copyOf(twovals, twovals.length + twovals.length + 1); - } - final int twopos = size; - twoheap[twopos] = co; - twovals[twopos] = cv; - ++size; - heapifyUp2(twopos, co, cv); - ++modCount; - } else { - final int fourpos = size - TWO_HEAP_MAX_SIZE; - if (fourheap == null) { - fourheap = new double[FOUR_HEAP_INITIAL_SIZE]; - fourvals = new Object[FOUR_HEAP_INITIAL_SIZE]; - } else if (fourpos >= fourheap.length) { - // Grow extension heap by half. - fourheap = Arrays.copyOf(fourheap, fourheap.length + (fourheap.length >> 1)); - fourvals = Arrays.copyOf(fourvals, fourvals.length + (fourvals.length >> 1)); - } - fourheap[fourpos] = co; - fourvals[fourpos] = cv; - ++size; - heapifyUp4(fourpos, co, cv); - ++modCount; + if (size >= twoheap.length) { + // Grow by one layer. + twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); + twovals = Arrays.copyOf(twovals, twovals.length + twovals.length + 1); } + final int twopos = size; + twoheap[twopos] = co; + twovals[twopos] = cv; + ++size; + heapifyUp(twopos, co, cv); } @Override @@ -223,7 +129,6 @@ public class DoubleObjectMaxHeap<V> implements DoubleObjectHeap<V> { @Override public void replaceTopElement(double reinsert, V val) { heapifyDown(reinsert, (Object)val); - ++modCount; } /** @@ -233,7 +138,7 @@ public class DoubleObjectMaxHeap<V> implements DoubleObjectHeap<V> { * @param cur Current object * @param val Current value */ - private void heapifyUp2(int twopos, double cur, Object val) { + private void heapifyUp(int twopos, double cur, Object val) { while (twopos > 0) { final int parent = (twopos - 1) >>> 1; double par = twoheap[parent]; @@ -248,47 +153,11 @@ public class DoubleObjectMaxHeap<V> implements DoubleObjectHeap<V> { twovals[twopos] = val; } - /** - * Heapify-Up method for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - * @param val Current value - */ - private void heapifyUp4(int fourpos, double cur, Object val) { - while (fourpos > 0) { - final int parent = (fourpos - 1) >> 2; - double par = fourheap[parent]; - if (cur <= par) { - break; - } - fourheap[fourpos] = par; - fourvals[fourpos] = fourvals[parent]; - fourpos = parent; - } - if (fourpos == 0 && twoheap[0] < cur) { - fourheap[0] = twoheap[0]; - fourvals[0] = twovals[0]; - twoheap[0] = cur; - twovals[0] = val; - } else { - fourheap[fourpos] = cur; - fourvals[fourpos] = val; - } - } - @Override public void poll() { --size; // Replacement object: - if (size >= TWO_HEAP_MAX_SIZE) { - final int last = size - TWO_HEAP_MAX_SIZE; - final double reinsert = fourheap[last]; - final Object reinsertv = fourvals[last]; - fourheap[last] = 0.0; - fourvals[last] = null; - heapifyDown(reinsert, reinsertv); - } else if (size > 0) { + if (size > 0) { final double reinsert = twoheap[size]; final Object reinsertv = twovals[size]; twoheap[size] = 0.0; @@ -298,42 +167,17 @@ public class DoubleObjectMaxHeap<V> implements DoubleObjectHeap<V> { twoheap[0] = 0.0; twovals[0] = null; } - ++modCount; } /** * Invoke heapify-down for the root object. * - * @param reinsert Object to insert. - * @param val Value to reinsert. - */ - private void heapifyDown(double reinsert, Object val) { - if (size > TWO_HEAP_MAX_SIZE) { - // Special case: 3-ary situation. - final int best = (twoheap[1] >= twoheap[2]) ? 1 : 2; - if (fourheap[0] > twoheap[best]) { - twoheap[0] = fourheap[0]; - twovals[0] = fourvals[0]; - heapifyDown4(0, reinsert, val); - } else { - twoheap[0] = twoheap[best]; - twovals[0] = twovals[best]; - heapifyDown2(best, reinsert, val); - } - return; - } - heapifyDown2(0, reinsert, val); - } - - /** - * Heapify-Down for 2-ary heap. - * - * @param twopos Position in 2-ary heap. - * @param cur Current object + * @param cur Object to insert. * @param val Value to reinsert. */ - private void heapifyDown2(int twopos, double cur, Object val) { - final int stop = Math.min(size, TWO_HEAP_MAX_SIZE) >>> 1; + private void heapifyDown(double cur, Object val) { + final int stop = size >>> 1; + int twopos = 0; while (twopos < stop) { int bestchild = (twopos << 1) + 1; double best = twoheap[bestchild]; @@ -353,54 +197,6 @@ public class DoubleObjectMaxHeap<V> implements DoubleObjectHeap<V> { twovals[twopos] = val; } - /** - * Heapify-Down for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - * @param val Value to reinsert. - */ - private void heapifyDown4(int fourpos, double cur, Object val) { - final int stop = (size - TWO_HEAP_MAX_SIZE + 2) >>> 2; - while (fourpos < stop) { - final int child = (fourpos << 2) + 1; - double best = fourheap[child]; - int bestchild = child, candidate = child + 1, minsize = candidate + TWO_HEAP_MAX_SIZE; - if (size > minsize) { - double nextchild = fourheap[candidate]; - if (best < nextchild) { - bestchild = candidate; - best = nextchild; - } - - minsize += 2; - if (size >= minsize) { - nextchild = fourheap[++candidate]; - if (best < nextchild) { - bestchild = candidate; - best = nextchild; - } - - if (size > minsize) { - nextchild = fourheap[++candidate]; - if (best < nextchild) { - bestchild = candidate; - best = nextchild; - } - } - } - } - if (cur >= best) { - break; - } - fourheap[fourpos] = best; - fourvals[fourpos] = fourvals[bestchild]; - fourpos = bestchild; - } - fourheap[fourpos] = cur; - fourvals[fourpos] = val; - } - @Override public double peekKey() { return twoheap[0]; @@ -449,16 +245,8 @@ public class DoubleObjectMaxHeap<V> implements DoubleObjectHeap<V> { */ protected int pos = 0; - /** - * Modification counter we were initialized at. - */ - protected final int myModCount = modCount; - @Override public boolean valid() { - if (modCount != myModCount) { - throw new ConcurrentModificationException(); - } return pos < size; } @@ -469,14 +257,14 @@ public class DoubleObjectMaxHeap<V> implements DoubleObjectHeap<V> { @Override public double getKey() { - return ((pos < TWO_HEAP_MAX_SIZE) ? twoheap[pos] : fourheap[pos - TWO_HEAP_MAX_SIZE]); + return twoheap[pos]; } @SuppressWarnings("unchecked") @Override public V getValue() { - return (V)((pos < TWO_HEAP_MAX_SIZE) ? twovals[pos] : fourvals[pos - TWO_HEAP_MAX_SIZE]); + return (V)twovals[pos]; } } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleObjectMinHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleObjectMinHeap.java index 905cdedb..01b8e58d 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleObjectMinHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/DoubleObjectMinHeap.java @@ -24,32 +24,11 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; */ import java.util.Arrays; -import java.util.ConcurrentModificationException; import de.lmu.ifi.dbs.elki.math.MathUtil; /** - * Advanced priority queue class, based on a binary heap (for small sizes), - * which will for larger heaps be accompanied by a 4-ary heap (attached below - * the root of the two-ary heap, making the root actually 3-ary). - * - * This code was automatically instantiated for the types: Double and Object - * - * This combination was found to work quite well in benchmarks, but YMMV. - * - * Some other observations from benchmarking: - * <ul> - * <li>Bulk loading did not improve things</li> - * <li>Primitive heaps are substantially faster.</li> - * <li>Since an array in Java has an overhead of 12 bytes, odd-sized object and - * integer arrays are actually well aligned both for 2-ary and 4-ary heaps.</li> - * <li>Workload makes a huge difference. A load-once, poll-until-empty priority - * queue is something different than e.g. a top-k heap, which will see a lot of - * top element replacements.</li> - * <li>Random vs. increasing vs. decreasing vs. sawtooth insertion patterns for - * top-k make a difference.</li> - * <li>Different day, different benchmark results ...</li> - * </ul> + * Binary heap for primitive types. * * @author Erich Schubert * @@ -68,49 +47,16 @@ public class DoubleObjectMinHeap<V> implements DoubleObjectHeap<V> { protected Object[] twovals; /** - * Extension heap. - */ - protected double[] fourheap; - - /** - * Extension heapvalues. - */ - protected Object[] fourvals; - - /** * Current size of heap. */ protected int size; /** - * (Structural) modification counter. Used to invalidate iterators. - */ - protected int modCount = 0; - - /** - * Maximum size of the 2-ary heap. A complete 2-ary heap has (2^k-1) elements. - */ - private final static int TWO_HEAP_MAX_SIZE = (1 << 9) - 1; - - /** * Initial size of the 2-ary heap. */ private final static int TWO_HEAP_INITIAL_SIZE = (1 << 5) - 1; /** - * Initial size of 4-ary heap when initialized. - * - * 21 = 4-ary heap of height 2: 1 + 4 + 4*4 - * - * 85 = 4-ary heap of height 3: 21 + 4*4*4 - * - * 341 = 4-ary heap of height 4: 85 + 4*4*4*4 - * - * Since we last grew by 255 (to 511), let's use 341. - */ - private final static int FOUR_HEAP_INITIAL_SIZE = 341; - - /** * Constructor, with default size. */ public DoubleObjectMinHeap() { @@ -120,10 +66,6 @@ public class DoubleObjectMinHeap<V> implements DoubleObjectHeap<V> { this.twoheap = twoheap; this.twovals = twovals; - this.fourheap = null; - this.fourvals = null; - this.size = 0; - this.modCount = 0; } /** @@ -133,35 +75,17 @@ public class DoubleObjectMinHeap<V> implements DoubleObjectHeap<V> { */ public DoubleObjectMinHeap(int minsize) { super(); - if (minsize < TWO_HEAP_MAX_SIZE) { - final int size = MathUtil.nextPow2Int(minsize + 1) - 1; - double[] twoheap = new double[size]; - Object[] twovals = new Object[size]; + final int size = MathUtil.nextPow2Int(minsize + 1) - 1; + double[] twoheap = new double[size]; + Object[] twovals = new Object[size]; - this.twoheap = twoheap; - this.twovals = twovals; - this.fourheap = null; - this.fourvals = null; - } else { - double[] twoheap = new double[TWO_HEAP_INITIAL_SIZE]; - Object[] twovals = new Object[TWO_HEAP_INITIAL_SIZE]; - double[] fourheap = new double[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - Object[] fourvals = new Object[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - this.twoheap = twoheap; - this.twovals = twovals; - this.fourheap = fourheap; - this.fourvals = fourvals; - } - this.size = 0; - this.modCount = 0; + this.twoheap = twoheap; + this.twovals = twovals; } @Override public void clear() { size = 0; - ++modCount; - fourheap = null; - fourvals = null; Arrays.fill(twoheap, 0.0); Arrays.fill(twovals, null); } @@ -181,34 +105,16 @@ public class DoubleObjectMinHeap<V> implements DoubleObjectHeap<V> { final double co = o; final Object cv = (Object)v; // System.err.println("Add: " + o); - if (size < TWO_HEAP_MAX_SIZE) { - if (size >= twoheap.length) { - // Grow by one layer. - twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); - twovals = Arrays.copyOf(twovals, twovals.length + twovals.length + 1); - } - final int twopos = size; - twoheap[twopos] = co; - twovals[twopos] = cv; - ++size; - heapifyUp2(twopos, co, cv); - ++modCount; - } else { - final int fourpos = size - TWO_HEAP_MAX_SIZE; - if (fourheap == null) { - fourheap = new double[FOUR_HEAP_INITIAL_SIZE]; - fourvals = new Object[FOUR_HEAP_INITIAL_SIZE]; - } else if (fourpos >= fourheap.length) { - // Grow extension heap by half. - fourheap = Arrays.copyOf(fourheap, fourheap.length + (fourheap.length >> 1)); - fourvals = Arrays.copyOf(fourvals, fourvals.length + (fourvals.length >> 1)); - } - fourheap[fourpos] = co; - fourvals[fourpos] = cv; - ++size; - heapifyUp4(fourpos, co, cv); - ++modCount; + if (size >= twoheap.length) { + // Grow by one layer. + twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); + twovals = Arrays.copyOf(twovals, twovals.length + twovals.length + 1); } + final int twopos = size; + twoheap[twopos] = co; + twovals[twopos] = cv; + ++size; + heapifyUp(twopos, co, cv); } @Override @@ -223,7 +129,6 @@ public class DoubleObjectMinHeap<V> implements DoubleObjectHeap<V> { @Override public void replaceTopElement(double reinsert, V val) { heapifyDown(reinsert, (Object)val); - ++modCount; } /** @@ -233,7 +138,7 @@ public class DoubleObjectMinHeap<V> implements DoubleObjectHeap<V> { * @param cur Current object * @param val Current value */ - private void heapifyUp2(int twopos, double cur, Object val) { + private void heapifyUp(int twopos, double cur, Object val) { while (twopos > 0) { final int parent = (twopos - 1) >>> 1; double par = twoheap[parent]; @@ -248,47 +153,11 @@ public class DoubleObjectMinHeap<V> implements DoubleObjectHeap<V> { twovals[twopos] = val; } - /** - * Heapify-Up method for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - * @param val Current value - */ - private void heapifyUp4(int fourpos, double cur, Object val) { - while (fourpos > 0) { - final int parent = (fourpos - 1) >> 2; - double par = fourheap[parent]; - if (cur >= par) { - break; - } - fourheap[fourpos] = par; - fourvals[fourpos] = fourvals[parent]; - fourpos = parent; - } - if (fourpos == 0 && twoheap[0] > cur) { - fourheap[0] = twoheap[0]; - fourvals[0] = twovals[0]; - twoheap[0] = cur; - twovals[0] = val; - } else { - fourheap[fourpos] = cur; - fourvals[fourpos] = val; - } - } - @Override public void poll() { --size; // Replacement object: - if (size >= TWO_HEAP_MAX_SIZE) { - final int last = size - TWO_HEAP_MAX_SIZE; - final double reinsert = fourheap[last]; - final Object reinsertv = fourvals[last]; - fourheap[last] = 0.0; - fourvals[last] = null; - heapifyDown(reinsert, reinsertv); - } else if (size > 0) { + if (size > 0) { final double reinsert = twoheap[size]; final Object reinsertv = twovals[size]; twoheap[size] = 0.0; @@ -298,42 +167,17 @@ public class DoubleObjectMinHeap<V> implements DoubleObjectHeap<V> { twoheap[0] = 0.0; twovals[0] = null; } - ++modCount; } /** * Invoke heapify-down for the root object. * - * @param reinsert Object to insert. - * @param val Value to reinsert. - */ - private void heapifyDown(double reinsert, Object val) { - if (size > TWO_HEAP_MAX_SIZE) { - // Special case: 3-ary situation. - final int best = (twoheap[1] <= twoheap[2]) ? 1 : 2; - if (fourheap[0] < twoheap[best]) { - twoheap[0] = fourheap[0]; - twovals[0] = fourvals[0]; - heapifyDown4(0, reinsert, val); - } else { - twoheap[0] = twoheap[best]; - twovals[0] = twovals[best]; - heapifyDown2(best, reinsert, val); - } - return; - } - heapifyDown2(0, reinsert, val); - } - - /** - * Heapify-Down for 2-ary heap. - * - * @param twopos Position in 2-ary heap. - * @param cur Current object + * @param cur Object to insert. * @param val Value to reinsert. */ - private void heapifyDown2(int twopos, double cur, Object val) { - final int stop = Math.min(size, TWO_HEAP_MAX_SIZE) >>> 1; + private void heapifyDown(double cur, Object val) { + final int stop = size >>> 1; + int twopos = 0; while (twopos < stop) { int bestchild = (twopos << 1) + 1; double best = twoheap[bestchild]; @@ -353,54 +197,6 @@ public class DoubleObjectMinHeap<V> implements DoubleObjectHeap<V> { twovals[twopos] = val; } - /** - * Heapify-Down for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - * @param val Value to reinsert. - */ - private void heapifyDown4(int fourpos, double cur, Object val) { - final int stop = (size - TWO_HEAP_MAX_SIZE + 2) >>> 2; - while (fourpos < stop) { - final int child = (fourpos << 2) + 1; - double best = fourheap[child]; - int bestchild = child, candidate = child + 1, minsize = candidate + TWO_HEAP_MAX_SIZE; - if (size > minsize) { - double nextchild = fourheap[candidate]; - if (best > nextchild) { - bestchild = candidate; - best = nextchild; - } - - minsize += 2; - if (size >= minsize) { - nextchild = fourheap[++candidate]; - if (best > nextchild) { - bestchild = candidate; - best = nextchild; - } - - if (size > minsize) { - nextchild = fourheap[++candidate]; - if (best > nextchild) { - bestchild = candidate; - best = nextchild; - } - } - } - } - if (cur <= best) { - break; - } - fourheap[fourpos] = best; - fourvals[fourpos] = fourvals[bestchild]; - fourpos = bestchild; - } - fourheap[fourpos] = cur; - fourvals[fourpos] = val; - } - @Override public double peekKey() { return twoheap[0]; @@ -449,16 +245,8 @@ public class DoubleObjectMinHeap<V> implements DoubleObjectHeap<V> { */ protected int pos = 0; - /** - * Modification counter we were initialized at. - */ - protected final int myModCount = modCount; - @Override public boolean valid() { - if (modCount != myModCount) { - throw new ConcurrentModificationException(); - } return pos < size; } @@ -469,14 +257,14 @@ public class DoubleObjectMinHeap<V> implements DoubleObjectHeap<V> { @Override public double getKey() { - return ((pos < TWO_HEAP_MAX_SIZE) ? twoheap[pos] : fourheap[pos - TWO_HEAP_MAX_SIZE]); + return twoheap[pos]; } @SuppressWarnings("unchecked") @Override public V getValue() { - return (V)((pos < TWO_HEAP_MAX_SIZE) ? twovals[pos] : fourvals[pos - TWO_HEAP_MAX_SIZE]); + return (V)twovals[pos]; } } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerHeap.java index 3235926b..77e5f3e5 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerHeap.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) 2013 + 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/heap/IntegerMaxHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerMaxHeap.java index 60f61d99..4f3b1495 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerMaxHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerMaxHeap.java @@ -24,32 +24,11 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; */ import java.util.Arrays; -import java.util.ConcurrentModificationException; import de.lmu.ifi.dbs.elki.math.MathUtil; /** - * Advanced priority queue class, based on a binary heap (for small sizes), - * which will for larger heaps be accompanied by a 4-ary heap (attached below - * the root of the two-ary heap, making the root actually 3-ary). - * - * This code was automatically instantiated for the type: Integer - * - * This combination was found to work quite well in benchmarks, but YMMV. - * - * Some other observations from benchmarking: - * <ul> - * <li>Bulk loading did not improve things</li> - * <li>Primitive heaps are substantially faster.</li> - * <li>Since an array in Java has an overhead of 12 bytes, odd-sized object and - * integer arrays are actually well aligned both for 2-ary and 4-ary heaps.</li> - * <li>Workload makes a huge difference. A load-once, poll-until-empty priority - * queue is something different than e.g. a top-k heap, which will see a lot of - * top element replacements.</li> - * <li>Random vs. increasing vs. decreasing vs. sawtooth insertion patterns for - * top-k make a difference.</li> - * <li>Different day, different benchmark results ...</li> - * </ul> + * Binary heap for primitive types. * * @author Erich Schubert * @@ -62,44 +41,16 @@ public class IntegerMaxHeap implements IntegerHeap { protected int[] twoheap; /** - * Extension heap. - */ - protected int[] fourheap; - - /** * Current size of heap. */ protected int size; /** - * (Structural) modification counter. Used to invalidate iterators. - */ - protected int modCount = 0; - - /** - * Maximum size of the 2-ary heap. A complete 2-ary heap has (2^k-1) elements. - */ - private final static int TWO_HEAP_MAX_SIZE = (1 << 9) - 1; - - /** * Initial size of the 2-ary heap. */ private final static int TWO_HEAP_INITIAL_SIZE = (1 << 5) - 1; /** - * Initial size of 4-ary heap when initialized. - * - * 21 = 4-ary heap of height 2: 1 + 4 + 4*4 - * - * 85 = 4-ary heap of height 3: 21 + 4*4*4 - * - * 341 = 4-ary heap of height 4: 85 + 4*4*4*4 - * - * Since we last grew by 255 (to 511), let's use 341. - */ - private final static int FOUR_HEAP_INITIAL_SIZE = 341; - - /** * Constructor, with default size. */ public IntegerMaxHeap() { @@ -107,9 +58,6 @@ public class IntegerMaxHeap implements IntegerHeap { int[] twoheap = new int[TWO_HEAP_INITIAL_SIZE]; this.twoheap = twoheap; - this.fourheap = null; - this.size = 0; - this.modCount = 0; } /** @@ -119,27 +67,15 @@ public class IntegerMaxHeap implements IntegerHeap { */ public IntegerMaxHeap(int minsize) { super(); - if (minsize < TWO_HEAP_MAX_SIZE) { - final int size = MathUtil.nextPow2Int(minsize + 1) - 1; - int[] twoheap = new int[size]; + final int size = MathUtil.nextPow2Int(minsize + 1) - 1; + int[] twoheap = new int[size]; - this.twoheap = twoheap; - this.fourheap = null; - } else { - int[] twoheap = new int[TWO_HEAP_INITIAL_SIZE]; - int[] fourheap = new int[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - this.twoheap = twoheap; - this.fourheap = fourheap; - } - this.size = 0; - this.modCount = 0; + this.twoheap = twoheap; } @Override public void clear() { size = 0; - ++modCount; - fourheap = null; Arrays.fill(twoheap, 0); } @@ -157,29 +93,14 @@ public class IntegerMaxHeap implements IntegerHeap { public void add(int o) { final int co = o; // System.err.println("Add: " + o); - if (size < TWO_HEAP_MAX_SIZE) { - if (size >= twoheap.length) { - // Grow by one layer. - twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); - } - final int twopos = size; - twoheap[twopos] = co; - ++size; - heapifyUp2(twopos, co); - ++modCount; - } else { - final int fourpos = size - TWO_HEAP_MAX_SIZE; - if (fourheap == null) { - fourheap = new int[FOUR_HEAP_INITIAL_SIZE]; - } else if (fourpos >= fourheap.length) { - // Grow extension heap by half. - fourheap = Arrays.copyOf(fourheap, fourheap.length + (fourheap.length >> 1)); - } - fourheap[fourpos] = co; - ++size; - heapifyUp4(fourpos, co); - ++modCount; + if (size >= twoheap.length) { + // Grow by one layer. + twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); } + final int twopos = size; + twoheap[twopos] = co; + ++size; + heapifyUp(twopos, co); } @Override @@ -195,7 +116,6 @@ public class IntegerMaxHeap implements IntegerHeap { public int replaceTopElement(int reinsert) { final int ret = twoheap[0]; heapifyDown( reinsert); - ++modCount; return ret; } @@ -205,7 +125,7 @@ public class IntegerMaxHeap implements IntegerHeap { * @param twopos Position in 2-ary heap. * @param cur Current object */ - private void heapifyUp2(int twopos, int cur) { + private void heapifyUp(int twopos, int cur) { while (twopos > 0) { final int parent = (twopos - 1) >>> 1; int par = twoheap[parent]; @@ -218,80 +138,29 @@ public class IntegerMaxHeap implements IntegerHeap { twoheap[twopos] = cur; } - /** - * Heapify-Up method for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - */ - private void heapifyUp4(int fourpos, int cur) { - while (fourpos > 0) { - final int parent = (fourpos - 1) >> 2; - int par = fourheap[parent]; - if (cur <= par) { - break; - } - fourheap[fourpos] = par; - fourpos = parent; - } - if (fourpos == 0 && twoheap[0] < cur) { - fourheap[0] = twoheap[0]; - twoheap[0] = cur; - } else { - fourheap[fourpos] = cur; - } - } - @Override public int poll() { final int ret = twoheap[0]; --size; // Replacement object: - if (size >= TWO_HEAP_MAX_SIZE) { - final int last = size - TWO_HEAP_MAX_SIZE; - final int reinsert = fourheap[last]; - fourheap[last] = 0; - heapifyDown(reinsert); - } else if (size > 0) { + if (size > 0) { final int reinsert = twoheap[size]; twoheap[size] = 0; heapifyDown(reinsert); } else { twoheap[0] = 0; } - ++modCount; return ret; } /** * Invoke heapify-down for the root object. * - * @param reinsert Object to insert. - */ - private void heapifyDown(int reinsert) { - if (size > TWO_HEAP_MAX_SIZE) { - // Special case: 3-ary situation. - final int best = (twoheap[1] >= twoheap[2]) ? 1 : 2; - if (fourheap[0] > twoheap[best]) { - twoheap[0] = fourheap[0]; - heapifyDown4(0, reinsert); - } else { - twoheap[0] = twoheap[best]; - heapifyDown2(best, reinsert); - } - return; - } - heapifyDown2(0, reinsert); - } - - /** - * Heapify-Down for 2-ary heap. - * - * @param twopos Position in 2-ary heap. - * @param cur Current object + * @param cur Object to insert. */ - private void heapifyDown2(int twopos, int cur) { - final int stop = Math.min(size, TWO_HEAP_MAX_SIZE) >>> 1; + private void heapifyDown(int cur) { + final int stop = size >>> 1; + int twopos = 0; while (twopos < stop) { int bestchild = (twopos << 1) + 1; int best = twoheap[bestchild]; @@ -309,51 +178,6 @@ public class IntegerMaxHeap implements IntegerHeap { twoheap[twopos] = cur; } - /** - * Heapify-Down for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - */ - private void heapifyDown4(int fourpos, int cur) { - final int stop = (size - TWO_HEAP_MAX_SIZE + 2) >>> 2; - while (fourpos < stop) { - final int child = (fourpos << 2) + 1; - int best = fourheap[child]; - int bestchild = child, candidate = child + 1, minsize = candidate + TWO_HEAP_MAX_SIZE; - if (size > minsize) { - int nextchild = fourheap[candidate]; - if (best < nextchild) { - bestchild = candidate; - best = nextchild; - } - - minsize += 2; - if (size >= minsize) { - nextchild = fourheap[++candidate]; - if (best < nextchild) { - bestchild = candidate; - best = nextchild; - } - - if (size > minsize) { - nextchild = fourheap[++candidate]; - if (best < nextchild) { - bestchild = candidate; - best = nextchild; - } - } - } - } - if (cur >= best) { - break; - } - fourheap[fourpos] = best; - fourpos = bestchild; - } - fourheap[fourpos] = cur; - } - @Override public int peek() { return twoheap[0]; @@ -396,16 +220,8 @@ public class IntegerMaxHeap implements IntegerHeap { */ protected int pos = 0; - /** - * Modification counter we were initialized at. - */ - protected final int myModCount = modCount; - @Override public boolean valid() { - if (modCount != myModCount) { - throw new ConcurrentModificationException(); - } return pos < size; } @@ -416,7 +232,7 @@ public class IntegerMaxHeap implements IntegerHeap { @Override public int get() { - return ((pos < TWO_HEAP_MAX_SIZE) ? twoheap[pos] : fourheap[pos - TWO_HEAP_MAX_SIZE]); + return twoheap[pos]; } } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerMinHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerMinHeap.java index c352ece4..b02e04db 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerMinHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerMinHeap.java @@ -24,32 +24,11 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; */ import java.util.Arrays; -import java.util.ConcurrentModificationException; import de.lmu.ifi.dbs.elki.math.MathUtil; /** - * Advanced priority queue class, based on a binary heap (for small sizes), - * which will for larger heaps be accompanied by a 4-ary heap (attached below - * the root of the two-ary heap, making the root actually 3-ary). - * - * This code was automatically instantiated for the type: Integer - * - * This combination was found to work quite well in benchmarks, but YMMV. - * - * Some other observations from benchmarking: - * <ul> - * <li>Bulk loading did not improve things</li> - * <li>Primitive heaps are substantially faster.</li> - * <li>Since an array in Java has an overhead of 12 bytes, odd-sized object and - * integer arrays are actually well aligned both for 2-ary and 4-ary heaps.</li> - * <li>Workload makes a huge difference. A load-once, poll-until-empty priority - * queue is something different than e.g. a top-k heap, which will see a lot of - * top element replacements.</li> - * <li>Random vs. increasing vs. decreasing vs. sawtooth insertion patterns for - * top-k make a difference.</li> - * <li>Different day, different benchmark results ...</li> - * </ul> + * Binary heap for primitive types. * * @author Erich Schubert * @@ -62,44 +41,16 @@ public class IntegerMinHeap implements IntegerHeap { protected int[] twoheap; /** - * Extension heap. - */ - protected int[] fourheap; - - /** * Current size of heap. */ protected int size; /** - * (Structural) modification counter. Used to invalidate iterators. - */ - protected int modCount = 0; - - /** - * Maximum size of the 2-ary heap. A complete 2-ary heap has (2^k-1) elements. - */ - private final static int TWO_HEAP_MAX_SIZE = (1 << 9) - 1; - - /** * Initial size of the 2-ary heap. */ private final static int TWO_HEAP_INITIAL_SIZE = (1 << 5) - 1; /** - * Initial size of 4-ary heap when initialized. - * - * 21 = 4-ary heap of height 2: 1 + 4 + 4*4 - * - * 85 = 4-ary heap of height 3: 21 + 4*4*4 - * - * 341 = 4-ary heap of height 4: 85 + 4*4*4*4 - * - * Since we last grew by 255 (to 511), let's use 341. - */ - private final static int FOUR_HEAP_INITIAL_SIZE = 341; - - /** * Constructor, with default size. */ public IntegerMinHeap() { @@ -107,9 +58,6 @@ public class IntegerMinHeap implements IntegerHeap { int[] twoheap = new int[TWO_HEAP_INITIAL_SIZE]; this.twoheap = twoheap; - this.fourheap = null; - this.size = 0; - this.modCount = 0; } /** @@ -119,27 +67,15 @@ public class IntegerMinHeap implements IntegerHeap { */ public IntegerMinHeap(int minsize) { super(); - if (minsize < TWO_HEAP_MAX_SIZE) { - final int size = MathUtil.nextPow2Int(minsize + 1) - 1; - int[] twoheap = new int[size]; + final int size = MathUtil.nextPow2Int(minsize + 1) - 1; + int[] twoheap = new int[size]; - this.twoheap = twoheap; - this.fourheap = null; - } else { - int[] twoheap = new int[TWO_HEAP_INITIAL_SIZE]; - int[] fourheap = new int[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - this.twoheap = twoheap; - this.fourheap = fourheap; - } - this.size = 0; - this.modCount = 0; + this.twoheap = twoheap; } @Override public void clear() { size = 0; - ++modCount; - fourheap = null; Arrays.fill(twoheap, 0); } @@ -157,29 +93,14 @@ public class IntegerMinHeap implements IntegerHeap { public void add(int o) { final int co = o; // System.err.println("Add: " + o); - if (size < TWO_HEAP_MAX_SIZE) { - if (size >= twoheap.length) { - // Grow by one layer. - twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); - } - final int twopos = size; - twoheap[twopos] = co; - ++size; - heapifyUp2(twopos, co); - ++modCount; - } else { - final int fourpos = size - TWO_HEAP_MAX_SIZE; - if (fourheap == null) { - fourheap = new int[FOUR_HEAP_INITIAL_SIZE]; - } else if (fourpos >= fourheap.length) { - // Grow extension heap by half. - fourheap = Arrays.copyOf(fourheap, fourheap.length + (fourheap.length >> 1)); - } - fourheap[fourpos] = co; - ++size; - heapifyUp4(fourpos, co); - ++modCount; + if (size >= twoheap.length) { + // Grow by one layer. + twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); } + final int twopos = size; + twoheap[twopos] = co; + ++size; + heapifyUp(twopos, co); } @Override @@ -195,7 +116,6 @@ public class IntegerMinHeap implements IntegerHeap { public int replaceTopElement(int reinsert) { final int ret = twoheap[0]; heapifyDown( reinsert); - ++modCount; return ret; } @@ -205,7 +125,7 @@ public class IntegerMinHeap implements IntegerHeap { * @param twopos Position in 2-ary heap. * @param cur Current object */ - private void heapifyUp2(int twopos, int cur) { + private void heapifyUp(int twopos, int cur) { while (twopos > 0) { final int parent = (twopos - 1) >>> 1; int par = twoheap[parent]; @@ -218,80 +138,29 @@ public class IntegerMinHeap implements IntegerHeap { twoheap[twopos] = cur; } - /** - * Heapify-Up method for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - */ - private void heapifyUp4(int fourpos, int cur) { - while (fourpos > 0) { - final int parent = (fourpos - 1) >> 2; - int par = fourheap[parent]; - if (cur >= par) { - break; - } - fourheap[fourpos] = par; - fourpos = parent; - } - if (fourpos == 0 && twoheap[0] > cur) { - fourheap[0] = twoheap[0]; - twoheap[0] = cur; - } else { - fourheap[fourpos] = cur; - } - } - @Override public int poll() { final int ret = twoheap[0]; --size; // Replacement object: - if (size >= TWO_HEAP_MAX_SIZE) { - final int last = size - TWO_HEAP_MAX_SIZE; - final int reinsert = fourheap[last]; - fourheap[last] = 0; - heapifyDown(reinsert); - } else if (size > 0) { + if (size > 0) { final int reinsert = twoheap[size]; twoheap[size] = 0; heapifyDown(reinsert); } else { twoheap[0] = 0; } - ++modCount; return ret; } /** * Invoke heapify-down for the root object. * - * @param reinsert Object to insert. - */ - private void heapifyDown(int reinsert) { - if (size > TWO_HEAP_MAX_SIZE) { - // Special case: 3-ary situation. - final int best = (twoheap[1] <= twoheap[2]) ? 1 : 2; - if (fourheap[0] < twoheap[best]) { - twoheap[0] = fourheap[0]; - heapifyDown4(0, reinsert); - } else { - twoheap[0] = twoheap[best]; - heapifyDown2(best, reinsert); - } - return; - } - heapifyDown2(0, reinsert); - } - - /** - * Heapify-Down for 2-ary heap. - * - * @param twopos Position in 2-ary heap. - * @param cur Current object + * @param cur Object to insert. */ - private void heapifyDown2(int twopos, int cur) { - final int stop = Math.min(size, TWO_HEAP_MAX_SIZE) >>> 1; + private void heapifyDown(int cur) { + final int stop = size >>> 1; + int twopos = 0; while (twopos < stop) { int bestchild = (twopos << 1) + 1; int best = twoheap[bestchild]; @@ -309,51 +178,6 @@ public class IntegerMinHeap implements IntegerHeap { twoheap[twopos] = cur; } - /** - * Heapify-Down for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - */ - private void heapifyDown4(int fourpos, int cur) { - final int stop = (size - TWO_HEAP_MAX_SIZE + 2) >>> 2; - while (fourpos < stop) { - final int child = (fourpos << 2) + 1; - int best = fourheap[child]; - int bestchild = child, candidate = child + 1, minsize = candidate + TWO_HEAP_MAX_SIZE; - if (size > minsize) { - int nextchild = fourheap[candidate]; - if (best > nextchild) { - bestchild = candidate; - best = nextchild; - } - - minsize += 2; - if (size >= minsize) { - nextchild = fourheap[++candidate]; - if (best > nextchild) { - bestchild = candidate; - best = nextchild; - } - - if (size > minsize) { - nextchild = fourheap[++candidate]; - if (best > nextchild) { - bestchild = candidate; - best = nextchild; - } - } - } - } - if (cur <= best) { - break; - } - fourheap[fourpos] = best; - fourpos = bestchild; - } - fourheap[fourpos] = cur; - } - @Override public int peek() { return twoheap[0]; @@ -396,16 +220,8 @@ public class IntegerMinHeap implements IntegerHeap { */ protected int pos = 0; - /** - * Modification counter we were initialized at. - */ - protected final int myModCount = modCount; - @Override public boolean valid() { - if (modCount != myModCount) { - throw new ConcurrentModificationException(); - } return pos < size; } @@ -416,7 +232,7 @@ public class IntegerMinHeap implements IntegerHeap { @Override public int get() { - return ((pos < TWO_HEAP_MAX_SIZE) ? twoheap[pos] : fourheap[pos - TWO_HEAP_MAX_SIZE]); + return twoheap[pos]; } } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerObjectHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerObjectHeap.java index 01f7aea0..e4f577af 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerObjectHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerObjectHeap.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) 2013 + 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/heap/IntegerObjectMaxHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerObjectMaxHeap.java index 93a4e75a..036a9520 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerObjectMaxHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerObjectMaxHeap.java @@ -24,32 +24,11 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; */ import java.util.Arrays; -import java.util.ConcurrentModificationException; import de.lmu.ifi.dbs.elki.math.MathUtil; /** - * Advanced priority queue class, based on a binary heap (for small sizes), - * which will for larger heaps be accompanied by a 4-ary heap (attached below - * the root of the two-ary heap, making the root actually 3-ary). - * - * This code was automatically instantiated for the types: Integer and Object - * - * This combination was found to work quite well in benchmarks, but YMMV. - * - * Some other observations from benchmarking: - * <ul> - * <li>Bulk loading did not improve things</li> - * <li>Primitive heaps are substantially faster.</li> - * <li>Since an array in Java has an overhead of 12 bytes, odd-sized object and - * integer arrays are actually well aligned both for 2-ary and 4-ary heaps.</li> - * <li>Workload makes a huge difference. A load-once, poll-until-empty priority - * queue is something different than e.g. a top-k heap, which will see a lot of - * top element replacements.</li> - * <li>Random vs. increasing vs. decreasing vs. sawtooth insertion patterns for - * top-k make a difference.</li> - * <li>Different day, different benchmark results ...</li> - * </ul> + * Binary heap for primitive types. * * @author Erich Schubert * @@ -68,49 +47,16 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> { protected Object[] twovals; /** - * Extension heap. - */ - protected int[] fourheap; - - /** - * Extension heapvalues. - */ - protected Object[] fourvals; - - /** * Current size of heap. */ protected int size; /** - * (Structural) modification counter. Used to invalidate iterators. - */ - protected int modCount = 0; - - /** - * Maximum size of the 2-ary heap. A complete 2-ary heap has (2^k-1) elements. - */ - private final static int TWO_HEAP_MAX_SIZE = (1 << 9) - 1; - - /** * Initial size of the 2-ary heap. */ private final static int TWO_HEAP_INITIAL_SIZE = (1 << 5) - 1; /** - * Initial size of 4-ary heap when initialized. - * - * 21 = 4-ary heap of height 2: 1 + 4 + 4*4 - * - * 85 = 4-ary heap of height 3: 21 + 4*4*4 - * - * 341 = 4-ary heap of height 4: 85 + 4*4*4*4 - * - * Since we last grew by 255 (to 511), let's use 341. - */ - private final static int FOUR_HEAP_INITIAL_SIZE = 341; - - /** * Constructor, with default size. */ public IntegerObjectMaxHeap() { @@ -120,10 +66,6 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> { this.twoheap = twoheap; this.twovals = twovals; - this.fourheap = null; - this.fourvals = null; - this.size = 0; - this.modCount = 0; } /** @@ -133,35 +75,17 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> { */ public IntegerObjectMaxHeap(int minsize) { super(); - if (minsize < TWO_HEAP_MAX_SIZE) { - final int size = MathUtil.nextPow2Int(minsize + 1) - 1; - int[] twoheap = new int[size]; - Object[] twovals = new Object[size]; + final int size = MathUtil.nextPow2Int(minsize + 1) - 1; + int[] twoheap = new int[size]; + Object[] twovals = new Object[size]; - this.twoheap = twoheap; - this.twovals = twovals; - this.fourheap = null; - this.fourvals = null; - } else { - int[] twoheap = new int[TWO_HEAP_INITIAL_SIZE]; - Object[] twovals = new Object[TWO_HEAP_INITIAL_SIZE]; - int[] fourheap = new int[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - Object[] fourvals = new Object[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - this.twoheap = twoheap; - this.twovals = twovals; - this.fourheap = fourheap; - this.fourvals = fourvals; - } - this.size = 0; - this.modCount = 0; + this.twoheap = twoheap; + this.twovals = twovals; } @Override public void clear() { size = 0; - ++modCount; - fourheap = null; - fourvals = null; Arrays.fill(twoheap, 0); Arrays.fill(twovals, null); } @@ -181,34 +105,16 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> { final int co = o; final Object cv = (Object)v; // System.err.println("Add: " + o); - if (size < TWO_HEAP_MAX_SIZE) { - if (size >= twoheap.length) { - // Grow by one layer. - twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); - twovals = Arrays.copyOf(twovals, twovals.length + twovals.length + 1); - } - final int twopos = size; - twoheap[twopos] = co; - twovals[twopos] = cv; - ++size; - heapifyUp2(twopos, co, cv); - ++modCount; - } else { - final int fourpos = size - TWO_HEAP_MAX_SIZE; - if (fourheap == null) { - fourheap = new int[FOUR_HEAP_INITIAL_SIZE]; - fourvals = new Object[FOUR_HEAP_INITIAL_SIZE]; - } else if (fourpos >= fourheap.length) { - // Grow extension heap by half. - fourheap = Arrays.copyOf(fourheap, fourheap.length + (fourheap.length >> 1)); - fourvals = Arrays.copyOf(fourvals, fourvals.length + (fourvals.length >> 1)); - } - fourheap[fourpos] = co; - fourvals[fourpos] = cv; - ++size; - heapifyUp4(fourpos, co, cv); - ++modCount; + if (size >= twoheap.length) { + // Grow by one layer. + twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); + twovals = Arrays.copyOf(twovals, twovals.length + twovals.length + 1); } + final int twopos = size; + twoheap[twopos] = co; + twovals[twopos] = cv; + ++size; + heapifyUp(twopos, co, cv); } @Override @@ -223,7 +129,6 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> { @Override public void replaceTopElement(int reinsert, V val) { heapifyDown(reinsert, (Object)val); - ++modCount; } /** @@ -233,7 +138,7 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> { * @param cur Current object * @param val Current value */ - private void heapifyUp2(int twopos, int cur, Object val) { + private void heapifyUp(int twopos, int cur, Object val) { while (twopos > 0) { final int parent = (twopos - 1) >>> 1; int par = twoheap[parent]; @@ -248,47 +153,11 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> { twovals[twopos] = val; } - /** - * Heapify-Up method for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - * @param val Current value - */ - private void heapifyUp4(int fourpos, int cur, Object val) { - while (fourpos > 0) { - final int parent = (fourpos - 1) >> 2; - int par = fourheap[parent]; - if (cur <= par) { - break; - } - fourheap[fourpos] = par; - fourvals[fourpos] = fourvals[parent]; - fourpos = parent; - } - if (fourpos == 0 && twoheap[0] < cur) { - fourheap[0] = twoheap[0]; - fourvals[0] = twovals[0]; - twoheap[0] = cur; - twovals[0] = val; - } else { - fourheap[fourpos] = cur; - fourvals[fourpos] = val; - } - } - @Override public void poll() { --size; // Replacement object: - if (size >= TWO_HEAP_MAX_SIZE) { - final int last = size - TWO_HEAP_MAX_SIZE; - final int reinsert = fourheap[last]; - final Object reinsertv = fourvals[last]; - fourheap[last] = 0; - fourvals[last] = null; - heapifyDown(reinsert, reinsertv); - } else if (size > 0) { + if (size > 0) { final int reinsert = twoheap[size]; final Object reinsertv = twovals[size]; twoheap[size] = 0; @@ -298,42 +167,17 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> { twoheap[0] = 0; twovals[0] = null; } - ++modCount; } /** * Invoke heapify-down for the root object. * - * @param reinsert Object to insert. - * @param val Value to reinsert. - */ - private void heapifyDown(int reinsert, Object val) { - if (size > TWO_HEAP_MAX_SIZE) { - // Special case: 3-ary situation. - final int best = (twoheap[1] >= twoheap[2]) ? 1 : 2; - if (fourheap[0] > twoheap[best]) { - twoheap[0] = fourheap[0]; - twovals[0] = fourvals[0]; - heapifyDown4(0, reinsert, val); - } else { - twoheap[0] = twoheap[best]; - twovals[0] = twovals[best]; - heapifyDown2(best, reinsert, val); - } - return; - } - heapifyDown2(0, reinsert, val); - } - - /** - * Heapify-Down for 2-ary heap. - * - * @param twopos Position in 2-ary heap. - * @param cur Current object + * @param cur Object to insert. * @param val Value to reinsert. */ - private void heapifyDown2(int twopos, int cur, Object val) { - final int stop = Math.min(size, TWO_HEAP_MAX_SIZE) >>> 1; + private void heapifyDown(int cur, Object val) { + final int stop = size >>> 1; + int twopos = 0; while (twopos < stop) { int bestchild = (twopos << 1) + 1; int best = twoheap[bestchild]; @@ -353,54 +197,6 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> { twovals[twopos] = val; } - /** - * Heapify-Down for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - * @param val Value to reinsert. - */ - private void heapifyDown4(int fourpos, int cur, Object val) { - final int stop = (size - TWO_HEAP_MAX_SIZE + 2) >>> 2; - while (fourpos < stop) { - final int child = (fourpos << 2) + 1; - int best = fourheap[child]; - int bestchild = child, candidate = child + 1, minsize = candidate + TWO_HEAP_MAX_SIZE; - if (size > minsize) { - int nextchild = fourheap[candidate]; - if (best < nextchild) { - bestchild = candidate; - best = nextchild; - } - - minsize += 2; - if (size >= minsize) { - nextchild = fourheap[++candidate]; - if (best < nextchild) { - bestchild = candidate; - best = nextchild; - } - - if (size > minsize) { - nextchild = fourheap[++candidate]; - if (best < nextchild) { - bestchild = candidate; - best = nextchild; - } - } - } - } - if (cur >= best) { - break; - } - fourheap[fourpos] = best; - fourvals[fourpos] = fourvals[bestchild]; - fourpos = bestchild; - } - fourheap[fourpos] = cur; - fourvals[fourpos] = val; - } - @Override public int peekKey() { return twoheap[0]; @@ -449,16 +245,8 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> { */ protected int pos = 0; - /** - * Modification counter we were initialized at. - */ - protected final int myModCount = modCount; - @Override public boolean valid() { - if (modCount != myModCount) { - throw new ConcurrentModificationException(); - } return pos < size; } @@ -469,14 +257,14 @@ public class IntegerObjectMaxHeap<V> implements IntegerObjectHeap<V> { @Override public int getKey() { - return ((pos < TWO_HEAP_MAX_SIZE) ? twoheap[pos] : fourheap[pos - TWO_HEAP_MAX_SIZE]); + return twoheap[pos]; } @SuppressWarnings("unchecked") @Override public V getValue() { - return (V)((pos < TWO_HEAP_MAX_SIZE) ? twovals[pos] : fourvals[pos - TWO_HEAP_MAX_SIZE]); + return (V)twovals[pos]; } } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerObjectMinHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerObjectMinHeap.java index e54c7d28..cc816a0e 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerObjectMinHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/IntegerObjectMinHeap.java @@ -24,32 +24,11 @@ package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; */ import java.util.Arrays; -import java.util.ConcurrentModificationException; import de.lmu.ifi.dbs.elki.math.MathUtil; /** - * Advanced priority queue class, based on a binary heap (for small sizes), - * which will for larger heaps be accompanied by a 4-ary heap (attached below - * the root of the two-ary heap, making the root actually 3-ary). - * - * This code was automatically instantiated for the types: Integer and Object - * - * This combination was found to work quite well in benchmarks, but YMMV. - * - * Some other observations from benchmarking: - * <ul> - * <li>Bulk loading did not improve things</li> - * <li>Primitive heaps are substantially faster.</li> - * <li>Since an array in Java has an overhead of 12 bytes, odd-sized object and - * integer arrays are actually well aligned both for 2-ary and 4-ary heaps.</li> - * <li>Workload makes a huge difference. A load-once, poll-until-empty priority - * queue is something different than e.g. a top-k heap, which will see a lot of - * top element replacements.</li> - * <li>Random vs. increasing vs. decreasing vs. sawtooth insertion patterns for - * top-k make a difference.</li> - * <li>Different day, different benchmark results ...</li> - * </ul> + * Binary heap for primitive types. * * @author Erich Schubert * @@ -68,49 +47,16 @@ public class IntegerObjectMinHeap<V> implements IntegerObjectHeap<V> { protected Object[] twovals; /** - * Extension heap. - */ - protected int[] fourheap; - - /** - * Extension heapvalues. - */ - protected Object[] fourvals; - - /** * Current size of heap. */ protected int size; /** - * (Structural) modification counter. Used to invalidate iterators. - */ - protected int modCount = 0; - - /** - * Maximum size of the 2-ary heap. A complete 2-ary heap has (2^k-1) elements. - */ - private final static int TWO_HEAP_MAX_SIZE = (1 << 9) - 1; - - /** * Initial size of the 2-ary heap. */ private final static int TWO_HEAP_INITIAL_SIZE = (1 << 5) - 1; /** - * Initial size of 4-ary heap when initialized. - * - * 21 = 4-ary heap of height 2: 1 + 4 + 4*4 - * - * 85 = 4-ary heap of height 3: 21 + 4*4*4 - * - * 341 = 4-ary heap of height 4: 85 + 4*4*4*4 - * - * Since we last grew by 255 (to 511), let's use 341. - */ - private final static int FOUR_HEAP_INITIAL_SIZE = 341; - - /** * Constructor, with default size. */ public IntegerObjectMinHeap() { @@ -120,10 +66,6 @@ public class IntegerObjectMinHeap<V> implements IntegerObjectHeap<V> { this.twoheap = twoheap; this.twovals = twovals; - this.fourheap = null; - this.fourvals = null; - this.size = 0; - this.modCount = 0; } /** @@ -133,35 +75,17 @@ public class IntegerObjectMinHeap<V> implements IntegerObjectHeap<V> { */ public IntegerObjectMinHeap(int minsize) { super(); - if (minsize < TWO_HEAP_MAX_SIZE) { - final int size = MathUtil.nextPow2Int(minsize + 1) - 1; - int[] twoheap = new int[size]; - Object[] twovals = new Object[size]; + final int size = MathUtil.nextPow2Int(minsize + 1) - 1; + int[] twoheap = new int[size]; + Object[] twovals = new Object[size]; - this.twoheap = twoheap; - this.twovals = twovals; - this.fourheap = null; - this.fourvals = null; - } else { - int[] twoheap = new int[TWO_HEAP_INITIAL_SIZE]; - Object[] twovals = new Object[TWO_HEAP_INITIAL_SIZE]; - int[] fourheap = new int[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - Object[] fourvals = new Object[Math.max(21, minsize - TWO_HEAP_MAX_SIZE)]; - this.twoheap = twoheap; - this.twovals = twovals; - this.fourheap = fourheap; - this.fourvals = fourvals; - } - this.size = 0; - this.modCount = 0; + this.twoheap = twoheap; + this.twovals = twovals; } @Override public void clear() { size = 0; - ++modCount; - fourheap = null; - fourvals = null; Arrays.fill(twoheap, 0); Arrays.fill(twovals, null); } @@ -181,34 +105,16 @@ public class IntegerObjectMinHeap<V> implements IntegerObjectHeap<V> { final int co = o; final Object cv = (Object)v; // System.err.println("Add: " + o); - if (size < TWO_HEAP_MAX_SIZE) { - if (size >= twoheap.length) { - // Grow by one layer. - twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); - twovals = Arrays.copyOf(twovals, twovals.length + twovals.length + 1); - } - final int twopos = size; - twoheap[twopos] = co; - twovals[twopos] = cv; - ++size; - heapifyUp2(twopos, co, cv); - ++modCount; - } else { - final int fourpos = size - TWO_HEAP_MAX_SIZE; - if (fourheap == null) { - fourheap = new int[FOUR_HEAP_INITIAL_SIZE]; - fourvals = new Object[FOUR_HEAP_INITIAL_SIZE]; - } else if (fourpos >= fourheap.length) { - // Grow extension heap by half. - fourheap = Arrays.copyOf(fourheap, fourheap.length + (fourheap.length >> 1)); - fourvals = Arrays.copyOf(fourvals, fourvals.length + (fourvals.length >> 1)); - } - fourheap[fourpos] = co; - fourvals[fourpos] = cv; - ++size; - heapifyUp4(fourpos, co, cv); - ++modCount; + if (size >= twoheap.length) { + // Grow by one layer. + twoheap = Arrays.copyOf(twoheap, twoheap.length + twoheap.length + 1); + twovals = Arrays.copyOf(twovals, twovals.length + twovals.length + 1); } + final int twopos = size; + twoheap[twopos] = co; + twovals[twopos] = cv; + ++size; + heapifyUp(twopos, co, cv); } @Override @@ -223,7 +129,6 @@ public class IntegerObjectMinHeap<V> implements IntegerObjectHeap<V> { @Override public void replaceTopElement(int reinsert, V val) { heapifyDown(reinsert, (Object)val); - ++modCount; } /** @@ -233,7 +138,7 @@ public class IntegerObjectMinHeap<V> implements IntegerObjectHeap<V> { * @param cur Current object * @param val Current value */ - private void heapifyUp2(int twopos, int cur, Object val) { + private void heapifyUp(int twopos, int cur, Object val) { while (twopos > 0) { final int parent = (twopos - 1) >>> 1; int par = twoheap[parent]; @@ -248,47 +153,11 @@ public class IntegerObjectMinHeap<V> implements IntegerObjectHeap<V> { twovals[twopos] = val; } - /** - * Heapify-Up method for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - * @param val Current value - */ - private void heapifyUp4(int fourpos, int cur, Object val) { - while (fourpos > 0) { - final int parent = (fourpos - 1) >> 2; - int par = fourheap[parent]; - if (cur >= par) { - break; - } - fourheap[fourpos] = par; - fourvals[fourpos] = fourvals[parent]; - fourpos = parent; - } - if (fourpos == 0 && twoheap[0] > cur) { - fourheap[0] = twoheap[0]; - fourvals[0] = twovals[0]; - twoheap[0] = cur; - twovals[0] = val; - } else { - fourheap[fourpos] = cur; - fourvals[fourpos] = val; - } - } - @Override public void poll() { --size; // Replacement object: - if (size >= TWO_HEAP_MAX_SIZE) { - final int last = size - TWO_HEAP_MAX_SIZE; - final int reinsert = fourheap[last]; - final Object reinsertv = fourvals[last]; - fourheap[last] = 0; - fourvals[last] = null; - heapifyDown(reinsert, reinsertv); - } else if (size > 0) { + if (size > 0) { final int reinsert = twoheap[size]; final Object reinsertv = twovals[size]; twoheap[size] = 0; @@ -298,42 +167,17 @@ public class IntegerObjectMinHeap<V> implements IntegerObjectHeap<V> { twoheap[0] = 0; twovals[0] = null; } - ++modCount; } /** * Invoke heapify-down for the root object. * - * @param reinsert Object to insert. - * @param val Value to reinsert. - */ - private void heapifyDown(int reinsert, Object val) { - if (size > TWO_HEAP_MAX_SIZE) { - // Special case: 3-ary situation. - final int best = (twoheap[1] <= twoheap[2]) ? 1 : 2; - if (fourheap[0] < twoheap[best]) { - twoheap[0] = fourheap[0]; - twovals[0] = fourvals[0]; - heapifyDown4(0, reinsert, val); - } else { - twoheap[0] = twoheap[best]; - twovals[0] = twovals[best]; - heapifyDown2(best, reinsert, val); - } - return; - } - heapifyDown2(0, reinsert, val); - } - - /** - * Heapify-Down for 2-ary heap. - * - * @param twopos Position in 2-ary heap. - * @param cur Current object + * @param cur Object to insert. * @param val Value to reinsert. */ - private void heapifyDown2(int twopos, int cur, Object val) { - final int stop = Math.min(size, TWO_HEAP_MAX_SIZE) >>> 1; + private void heapifyDown(int cur, Object val) { + final int stop = size >>> 1; + int twopos = 0; while (twopos < stop) { int bestchild = (twopos << 1) + 1; int best = twoheap[bestchild]; @@ -353,54 +197,6 @@ public class IntegerObjectMinHeap<V> implements IntegerObjectHeap<V> { twovals[twopos] = val; } - /** - * Heapify-Down for 4-ary heap. - * - * @param fourpos Position in 4-ary heap. - * @param cur Current object - * @param val Value to reinsert. - */ - private void heapifyDown4(int fourpos, int cur, Object val) { - final int stop = (size - TWO_HEAP_MAX_SIZE + 2) >>> 2; - while (fourpos < stop) { - final int child = (fourpos << 2) + 1; - int best = fourheap[child]; - int bestchild = child, candidate = child + 1, minsize = candidate + TWO_HEAP_MAX_SIZE; - if (size > minsize) { - int nextchild = fourheap[candidate]; - if (best > nextchild) { - bestchild = candidate; - best = nextchild; - } - - minsize += 2; - if (size >= minsize) { - nextchild = fourheap[++candidate]; - if (best > nextchild) { - bestchild = candidate; - best = nextchild; - } - - if (size > minsize) { - nextchild = fourheap[++candidate]; - if (best > nextchild) { - bestchild = candidate; - best = nextchild; - } - } - } - } - if (cur <= best) { - break; - } - fourheap[fourpos] = best; - fourvals[fourpos] = fourvals[bestchild]; - fourpos = bestchild; - } - fourheap[fourpos] = cur; - fourvals[fourpos] = val; - } - @Override public int peekKey() { return twoheap[0]; @@ -449,16 +245,8 @@ public class IntegerObjectMinHeap<V> implements IntegerObjectHeap<V> { */ protected int pos = 0; - /** - * Modification counter we were initialized at. - */ - protected final int myModCount = modCount; - @Override public boolean valid() { - if (modCount != myModCount) { - throw new ConcurrentModificationException(); - } return pos < size; } @@ -469,14 +257,14 @@ public class IntegerObjectMinHeap<V> implements IntegerObjectHeap<V> { @Override public int getKey() { - return ((pos < TWO_HEAP_MAX_SIZE) ? twoheap[pos] : fourheap[pos - TWO_HEAP_MAX_SIZE]); + return twoheap[pos]; } @SuppressWarnings("unchecked") @Override public V getValue() { - return (V)((pos < TWO_HEAP_MAX_SIZE) ? twovals[pos] : fourvals[pos - TWO_HEAP_MAX_SIZE]); + return (V)twovals[pos]; } } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ObjectHeap.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ObjectHeap.java index b5dbbb0e..2b03740e 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ObjectHeap.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/ObjectHeap.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) 2013 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -31,7 +31,6 @@ import de.lmu.ifi.dbs.elki.utilities.datastructures.iterator.Iter; * @author Erich Schubert * * @apiviz.has UnsortedIter - * * @param <K> Key type */ public interface ObjectHeap<K> { @@ -85,7 +84,7 @@ public interface ObjectHeap<K> { * @return Size */ public int size(); - + /** * Is the heap empty? * @@ -112,7 +111,6 @@ public interface ObjectHeap<K> { * </pre> * * @author Erich Schubert - * * @param <K> Key type */ public static interface UnsortedIter<K> extends Iter { diff --git a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/histogram/IntStaticHistogram.java b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/histogram/IntStaticHistogram.java index 7b1eed94..84b55cd1 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/datastructures/histogram/IntStaticHistogram.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/datastructures/histogram/IntStaticHistogram.java @@ -73,7 +73,7 @@ public class IntStaticHistogram extends AbstractStaticHistogram implements IntHi } else { // Shift in place and clear head System.arraycopy(data, 0, data, -bin, size); - Arrays.fill(data, 0, -bin, (int) 0); + Arrays.fill(data, 0, -bin, 0); } data[0] = val; // Note that bin is negative, -bin is the shift offset! diff --git a/src/de/lmu/ifi/dbs/elki/utilities/documentation/Description.java b/src/de/lmu/ifi/dbs/elki/utilities/documentation/Description.java index 10fe40f3..3ce24e4e 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/documentation/Description.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/documentation/Description.java @@ -36,7 +36,7 @@ import java.lang.annotation.Target; */ @Documented @Retention(RetentionPolicy.RUNTIME) -@Target( { ElementType.TYPE }) +@Target( { ElementType.TYPE, ElementType.METHOD, ElementType.FIELD }) public @interface Description { /** * Description of the class. diff --git a/src/de/lmu/ifi/dbs/elki/utilities/documentation/Title.java b/src/de/lmu/ifi/dbs/elki/utilities/documentation/Title.java index 9676e8e0..c77ca875 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/documentation/Title.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/documentation/Title.java @@ -36,7 +36,7 @@ import java.lang.annotation.Target; */ @Documented @Retention(RetentionPolicy.RUNTIME) -@Target( { ElementType.TYPE }) +@Target( { ElementType.TYPE, ElementType.METHOD, ElementType.FIELD }) public @interface Title { /** * Title of the Algorithm diff --git a/src/de/lmu/ifi/dbs/elki/utilities/ensemble/EnsembleVotingMedian.java b/src/de/lmu/ifi/dbs/elki/utilities/ensemble/EnsembleVotingMedian.java index de137b40..85e7f6c8 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/ensemble/EnsembleVotingMedian.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/ensemble/EnsembleVotingMedian.java @@ -26,8 +26,7 @@ package de.lmu.ifi.dbs.elki.utilities.ensemble; import de.lmu.ifi.dbs.elki.utilities.datastructures.QuickSelect; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.LessEqualConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; @@ -84,10 +83,10 @@ public class EnsembleVotingMedian implements EnsembleVoting { @Override protected void makeOptions(Parameterization config) { super.makeOptions(config); - DoubleParameter quantileP = new DoubleParameter(QUANTILE_ID, 0.5); - quantileP.addConstraint(new GreaterEqualConstraint(0.0)); - quantileP.addConstraint(new LessEqualConstraint(1.0)); - if (config.grab(quantileP)) { + DoubleParameter quantileP = new DoubleParameter(QUANTILE_ID, .5); + quantileP.addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_DOUBLE); + quantileP.addConstraint(CommonConstraints.LESS_EQUAL_ONE_DOUBLE); + if(config.grab(quantileP)) { quantile = quantileP.getValue(); } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/AllOrNoneMustBeSetGlobalConstraint.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/AllOrNoneMustBeSetGlobalConstraint.java index a06a06c1..a87af1a8 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/AllOrNoneMustBeSetGlobalConstraint.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/AllOrNoneMustBeSetGlobalConstraint.java @@ -24,7 +24,6 @@ package de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints; */ import java.util.ArrayList; -import java.util.List; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionUtil; import de.lmu.ifi.dbs.elki.utilities.optionhandling.ParameterException; @@ -41,7 +40,7 @@ public class AllOrNoneMustBeSetGlobalConstraint implements GlobalParameterConstr /** * List of parameters to be checked */ - private List<Parameter<?>> parameterList; + private Parameter<?>[] parameterList; /** * Constructs a global parameter constraint for testing if either all elements @@ -49,7 +48,7 @@ public class AllOrNoneMustBeSetGlobalConstraint implements GlobalParameterConstr * * @param parameters list of parameters to be checked */ - public AllOrNoneMustBeSetGlobalConstraint(List<Parameter<?>> parameters) { + public AllOrNoneMustBeSetGlobalConstraint(Parameter<?>... parameters) { this.parameterList = parameters; } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/CommonConstraints.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/CommonConstraints.java new file mode 100644 index 00000000..ea1caed9 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/CommonConstraints.java @@ -0,0 +1,98 @@ +package de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2013 + 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; + +/** + * Class storing a number of very common constraints. + * + * @author Erich Schubert + */ +public final class CommonConstraints { + /** + * Integer constraint: >= -1 + */ + public static final ParameterConstraint<? super Integer> GREATER_EQUAL_MINUSONE_INT = new GreaterEqualConstraint(-1); + + /** + * Not negative. + */ + public static final ParameterConstraint<? super Integer> GREATER_EQUAL_ZERO_INT = new GreaterEqualConstraint(0); + + /** + * Larger than zero. + */ + public static final ParameterConstraint<? super Integer> GREATER_EQUAL_ONE_INT = new GreaterEqualConstraint(1); + + /** + * Larger than one. + */ + public static final ParameterConstraint<? super Integer> GREATER_THAN_ONE_INT = new GreaterConstraint(1); + + /** + * Not negative. + */ + public static final ParameterConstraint<? super Double> GREATER_EQUAL_ZERO_DOUBLE = new GreaterEqualConstraint(0.); + + /** + * Larger than zero. + */ + public static final ParameterConstraint<? super Double> GREATER_THAN_ZERO_DOUBLE = new GreaterConstraint(0.); + + /** + * Constraint: less than .5 + */ + public static final ParameterConstraint<? super Double> LESS_THAN_HALF_DOUBLE = new LessConstraint(.5); + + /** + * At least 1. + */ + public static final ParameterConstraint<? super Double> GREATER_EQUAL_ONE_DOUBLE = new GreaterEqualConstraint(1.); + + /** + * Larger than one. + */ + public static final ParameterConstraint<? super Double> GREATER_THAN_ONE_DOUBLE = new GreaterConstraint(1.); + + /** + * Less than one. + */ + public static final ParameterConstraint<? super Double> LESS_THAN_ONE_DOUBLE = new LessConstraint(1.); + + /** + * Less or equal than one. + */ + public static final ParameterConstraint<? super Double> LESS_EQUAL_ONE_DOUBLE = new LessEqualConstraint(1.); + + /** + * Constraint for the whole list. + */ + public static final ParameterConstraint<? super List<Integer>> GREATER_EQUAL_ZERO_INT_LIST = new ListEachConstraint<>(GREATER_EQUAL_ZERO_INT); + + /** + * List constraint: >= 1 + */ + public static final ParameterConstraint<? super List<Integer>> GREATER_EQUAL_ONE_INT_LIST = new ListEachConstraint<>(GREATER_EQUAL_ONE_INT); +} diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/EqualSizeGlobalConstraint.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/EqualSizeGlobalConstraint.java index 2ee7be9c..586b4257 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/EqualSizeGlobalConstraint.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/EqualSizeGlobalConstraint.java @@ -23,8 +23,6 @@ package de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.List; - import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionUtil; import de.lmu.ifi.dbs.elki.utilities.optionhandling.ParameterException; import de.lmu.ifi.dbs.elki.utilities.optionhandling.WrongParameterValueException; @@ -41,7 +39,7 @@ public class EqualSizeGlobalConstraint implements GlobalParameterConstraint { /** * List parameters to be tested */ - private List<ListParameter<?>> parameters; + private ListParameter<?, ?>[] parameters; /** * Creates a global parameter constraint for testing if a number of list @@ -49,7 +47,7 @@ public class EqualSizeGlobalConstraint implements GlobalParameterConstraint { * * @param params list parameters to be tested for equal list sizes */ - public EqualSizeGlobalConstraint(List<ListParameter<?>> params) { + public EqualSizeGlobalConstraint(ListParameter<?, ?>... params) { this.parameters = params; } @@ -63,7 +61,7 @@ public class EqualSizeGlobalConstraint implements GlobalParameterConstraint { boolean first = false; int constraintSize = -1; - for(ListParameter<?> listParam : parameters) { + for(ListParameter<?, ?> listParam : parameters) { if(listParam.isDefined()) { if(!first) { constraintSize = listParam.getListSize(); diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/GlobalListSizeConstraint.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/GlobalListSizeConstraint.java index bcedd342..7c35045e 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/GlobalListSizeConstraint.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/GlobalListSizeConstraint.java @@ -39,7 +39,7 @@ public class GlobalListSizeConstraint implements GlobalParameterConstraint { /** * List parameter to be tested. */ - private ListParameter<?> list; + private ListParameter<?, ?> list; /** * Integer parameter specifying the constraint list size. @@ -55,7 +55,7 @@ public class GlobalListSizeConstraint implements GlobalParameterConstraint { * @param v the list parameter to be tested. * @param i integer parameter specifying the constraint list size. */ - public GlobalListSizeConstraint(ListParameter<?> v, IntParameter i) { + public GlobalListSizeConstraint(ListParameter<?, ?> v, IntParameter i) { this.list = v; this.length = i; } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/LessEqualGlobalConstraint.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/LessEqualGlobalConstraint.java index 1216e03b..9fa0ee99 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/LessEqualGlobalConstraint.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/LessEqualGlobalConstraint.java @@ -39,12 +39,12 @@ public class LessEqualGlobalConstraint<T extends Number> implements GlobalParame /** * First number parameter. */ - private NumberParameter<T> first; + private NumberParameter<?, T> first; /** * Second number parameter. */ - private NumberParameter<T> second; + private NumberParameter<?, T> second; /** * Creates a Less-Equal-Than global parameter constraint. @@ -55,7 +55,7 @@ public class LessEqualGlobalConstraint<T extends Number> implements GlobalParame * @param first first number parameter * @param second second number parameter */ - public LessEqualGlobalConstraint(NumberParameter<T> first, NumberParameter<T> second) { + public LessEqualGlobalConstraint(NumberParameter<?, T> first, NumberParameter<?, T> second) { this.first = first; this.second = second; } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/LessGlobalConstraint.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/LessGlobalConstraint.java index a722edab..989f6e29 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/LessGlobalConstraint.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/LessGlobalConstraint.java @@ -39,12 +39,12 @@ public class LessGlobalConstraint<T extends Number> implements GlobalParameterCo /** * First number parameter. */ - private NumberParameter<T> first; + private NumberParameter<?, T> first; /** * Second number parameter. */ - private NumberParameter<T> second; + private NumberParameter<?, T> second; /** * Creates a Less-Than global parameter constraint. That is the value of the @@ -54,7 +54,7 @@ public class LessGlobalConstraint<T extends Number> implements GlobalParameterCo * @param first first number parameter * @param second second number parameter */ - public LessGlobalConstraint(NumberParameter<T> first, NumberParameter<T> second) { + public LessGlobalConstraint(NumberParameter<?, T> first, NumberParameter<?, T> second) { this.first = first; this.second = second; } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/NoDuplicateValueGlobalConstraint.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/NoDuplicateValueGlobalConstraint.java index 65b427a1..7036ecef 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/NoDuplicateValueGlobalConstraint.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/constraints/NoDuplicateValueGlobalConstraint.java @@ -45,7 +45,7 @@ public class NoDuplicateValueGlobalConstraint implements GlobalParameterConstrai /** * List of number parameters to be checked. */ - private List<? extends AbstractParameter<?>> parameters; + private List<? extends AbstractParameter<?, ?>> parameters; /** * Constructs a Not-Equal-Value global parameter constraint. That is, the @@ -54,7 +54,7 @@ public class NoDuplicateValueGlobalConstraint implements GlobalParameterConstrai * * @param parameters list of number parameters to be tested */ - public NoDuplicateValueGlobalConstraint(List<? extends AbstractParameter<?>> parameters) { + public NoDuplicateValueGlobalConstraint(List<? extends AbstractParameter<?, ?>> parameters) { this.parameters = parameters; } @@ -65,7 +65,7 @@ public class NoDuplicateValueGlobalConstraint implements GlobalParameterConstrai * * @param parameters list of number parameters to be tested */ - public NoDuplicateValueGlobalConstraint(AbstractParameter<?>... parameters) { + public NoDuplicateValueGlobalConstraint(AbstractParameter<?, ?>... parameters) { this.parameters = Arrays.asList(parameters); } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/package-info.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/package-info.java index e4c5489b..d2106865 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/package-info.java @@ -15,7 +15,7 @@ * "Distance function to determine the distance between database objects." * ); * }</pre></blockquote> - * (This example is from {@link de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm DistanceBasedAlgorithm}.) + * (This example is from {@link de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm AbstractDistanceBasedAlgorithm}.) * </li> * * <li><b>Parameter Object</b>: To obtain a value, you <em>must</em> use a diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/AbstractParameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/AbstractParameter.java index 8e1b48c3..cdad8583 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/AbstractParameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/AbstractParameter.java @@ -25,7 +25,6 @@ package de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters; import java.security.InvalidParameterException; import java.util.ArrayList; -import java.util.Collection; import java.util.List; import de.lmu.ifi.dbs.elki.logging.LoggingUtil; @@ -49,9 +48,10 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.ParameterConstra * @apiviz.composedOf OptionID * @apiviz.uses ParameterConstraint * + * @param <THIS> type self-reference * @param <T> the type of a possible value (i.e., the type of the option) */ -public abstract class AbstractParameter<T> implements Parameter<T> { +public abstract class AbstractParameter<THIS extends AbstractParameter<THIS, T>, T> implements Parameter<T> { /** * The default value of the parameter (may be null). */ @@ -152,20 +152,24 @@ public abstract class AbstractParameter<T> implements Parameter<T> { @Override public boolean tryDefaultValue() throws UnspecifiedParameterException { // Assume default value instead. - if (hasDefaultValue()) { + if(hasDefaultValue()) { useDefaultValue(); return true; - } else if (isOptional()) { + } + else if(isOptional()) { // Optional is fine, but not successful return false; - } else { + } + else { throw new UnspecifiedParameterException(this); } } + @SuppressWarnings("unchecked") @Override - public void setOptional(boolean opt) { + public THIS setOptional(boolean opt) { this.optionalParameter = opt; + return (THIS) this; } @Override @@ -204,31 +208,32 @@ public abstract class AbstractParameter<T> implements Parameter<T> { // description.append(getParameterType()).append(" "); description.append(shortDescription); description.append(FormatUtil.NEWLINE); - if (hasValuesDescription()) { + if(hasValuesDescription()) { final String valuesDescription = getValuesDescription(); description.append(valuesDescription); - if (!valuesDescription.endsWith(FormatUtil.NEWLINE)) { + if(!valuesDescription.endsWith(FormatUtil.NEWLINE)) { description.append(FormatUtil.NEWLINE); } } - if (hasDefaultValue()) { + if(hasDefaultValue()) { description.append("Default: "); description.append(getDefaultValueAsString()); description.append(FormatUtil.NEWLINE); } - if (constraints != null && !constraints.isEmpty()) { - if (constraints.size() == 1) { + if(constraints != null && !constraints.isEmpty()) { + if(constraints.size() == 1) { description.append("Constraint: "); - } else if (constraints.size() > 1) { + } + else if(constraints.size() > 1) { description.append("Constraints: "); } - for (int i = 0; i < constraints.size(); i++) { + for(int i = 0; i < constraints.size(); i++) { ParameterConstraint<? super T> constraint = constraints.get(i); - if (i > 0) { + if(i > 0) { description.append(", "); } description.append(constraint.getDescription(getName())); - if (i == constraints.size() - 1) { + if(i == constraints.size() - 1) { description.append('.'); } } @@ -245,8 +250,8 @@ public abstract class AbstractParameter<T> implements Parameter<T> { * @throws ParameterException when the object is not valid. */ protected boolean validate(T obj) throws ParameterException { - if (constraints != null) { - for (ParameterConstraint<? super T> cons : this.constraints) { + if(constraints != null) { + for(ParameterConstraint<? super T> cons : this.constraints) { cons.test(obj); } } @@ -276,9 +281,10 @@ public abstract class AbstractParameter<T> implements Parameter<T> { @Override public void setValue(Object obj) throws ParameterException { T val = parseValue(obj); - if (validate(val)) { + if(validate(val)) { setValueInternal(val); - } else { + } + else { throw new InvalidParameterException("Value for option \"" + getName() + "\" did not validate: " + obj.toString()); } } @@ -294,7 +300,7 @@ public abstract class AbstractParameter<T> implements Parameter<T> { @Override public final T getValue() { - if (this.value == null) { + if(this.value == null) { LoggingUtil.warning("Programming error: Parameter#getValue() called for unset parameter \"" + this.optionid.getName() + "\"", new Throwable()); } return this.value; @@ -331,23 +337,13 @@ public abstract class AbstractParameter<T> implements Parameter<T> { return getDefaultValue().toString(); } + @SuppressWarnings("unchecked") @Override - public void addConstraint(ParameterConstraint<? super T> constraint) { - if (constraints == null) { + public THIS addConstraint(ParameterConstraint<? super T> constraint) { + if(constraints == null) { this.constraints = new ArrayList<>(1); } constraints.add(constraint); - } - - /** - * Add a collection of constraints. - * - * @param cs Constraints to add - */ - public void addConstraints(Collection<? extends ParameterConstraint<? super T>> cs) { - if (constraints == null) { - this.constraints = new ArrayList<>(cs.size()); - } - constraints.addAll(cs); + return (THIS) this; } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/ClassListParameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/ClassListParameter.java index 35cd0573..1cea7fac 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/ClassListParameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/ClassListParameter.java @@ -46,7 +46,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameteriz * @param <C> Class type */ // TODO: Add missing constructors. (ObjectListParameter also!) -public class ClassListParameter<C> extends ListParameter<Class<? extends C>> { +public class ClassListParameter<C> extends ListParameter<ClassListParameter<C>, Class<? extends C>> { /** * The restriction class for the list of class names. */ diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/ClassParameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/ClassParameter.java index a0669fca..42288738 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/ClassParameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/ClassParameter.java @@ -49,7 +49,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameteriz */ // TODO: add additional constructors with parameter constraints. // TODO: turn restrictionClass into a constraint? -public class ClassParameter<C> extends AbstractParameter<Class<? extends C>> { +public class ClassParameter<C> extends AbstractParameter<ClassParameter<C>, Class<? extends C>> { /** * The restriction class for this class parameter. */ @@ -73,7 +73,7 @@ public class ClassParameter<C> extends AbstractParameter<Class<? extends C>> { // * ClassParameter<Foo<Bar>>(optionID, (Class<Foo<Bar>>) Foo.class) is an // invalid cast. this.restrictionClass = (Class<C>) restrictionClass; - if (restrictionClass == null) { + if(restrictionClass == null) { LoggingUtil.warning("Restriction class 'null' for parameter '" + optionID + "'", new Throwable()); } } @@ -96,7 +96,7 @@ public class ClassParameter<C> extends AbstractParameter<Class<? extends C>> { // * ClassParameter<Foo<Bar>>(optionID, (Class<Foo<Bar>>) Foo.class) is an // invalid cast. this.restrictionClass = (Class<C>) restrictionClass; - if (restrictionClass == null) { + if(restrictionClass == null) { LoggingUtil.warning("Restriction class 'null' for parameter '" + optionID + "'", new Throwable()); } } @@ -115,15 +115,15 @@ public class ClassParameter<C> extends AbstractParameter<Class<? extends C>> { @SuppressWarnings("unchecked") @Override protected Class<? extends C> parseValue(Object obj) throws ParameterException { - if (obj == null) { + if(obj == null) { throw new UnspecifiedParameterException(this); } - if (obj instanceof Class<?>) { + if(obj instanceof Class<?>) { return (Class<? extends C>) obj; } - if (obj instanceof String) { + if(obj instanceof String) { Class<? extends C> clz = InspectionUtil.findImplementation(restrictionClass, (String) obj); - if (clz != null) { + if(clz != null) { return clz; } } @@ -136,13 +136,13 @@ public class ClassParameter<C> extends AbstractParameter<Class<? extends C>> { */ @Override public boolean validate(Class<? extends C> obj) throws ParameterException { - if (obj == null) { + if(obj == null) { throw new UnspecifiedParameterException(this); } - if (!restrictionClass.isAssignableFrom(obj)) { + if(!restrictionClass.isAssignableFrom(obj)) { throw new WrongParameterValueException(this, obj.getName(), "Given class not a subclass / implementation of " + restrictionClass.getName()); } - if (!super.validate(obj)) { + if(!super.validate(obj)) { return false; } return true; @@ -175,7 +175,7 @@ public class ClassParameter<C> extends AbstractParameter<Class<? extends C>> { */ @Override public String getValuesDescription() { - if (restrictionClass != null && restrictionClass != Object.class) { + if(restrictionClass != null && restrictionClass != Object.class) { return restrictionString(); } return ""; @@ -199,22 +199,26 @@ public class ClassParameter<C> extends AbstractParameter<Class<? extends C>> { */ public C instantiateClass(Parameterization config) { try { - if (getValue() == null /* && !optionalParameter */) { + if(getValue() == null /* && !optionalParameter */) { throw new UnusedParameterException("Value of parameter " + getName() + " has not been specified."); } C instance; try { config = config.descend(this); instance = ClassGenericsUtil.tryInstantiate(restrictionClass, getValue(), config); - } catch (InvocationTargetException e) { + } + catch(InvocationTargetException e) { throw new WrongParameterValueException(this, getValue().getCanonicalName(), "Error instantiating class.", e); - } catch (NoSuchMethodException e) { + } + catch(NoSuchMethodException e) { throw new WrongParameterValueException(this, getValue().getCanonicalName(), "Error instantiating class - no usable public constructor."); - } catch (Exception e) { + } + catch(Exception e) { throw new WrongParameterValueException(this, getValue().getCanonicalName(), "Error instantiating class.", e); } return instance; - } catch (ParameterException e) { + } + catch(ParameterException e) { config.reportError(e); return null; } @@ -247,19 +251,20 @@ public class ClassParameter<C> extends AbstractParameter<Class<? extends C>> { */ public String restrictionString() { StringBuilder info = new StringBuilder(); - if (restrictionClass.isInterface()) { + if(restrictionClass.isInterface()) { info.append("Implementing "); - } else { + } + else { info.append("Extending "); } info.append(restrictionClass.getName()); info.append(FormatUtil.NEWLINE); List<Class<?>> known = getKnownImplementations(); - if (!known.isEmpty()) { + if(!known.isEmpty()) { info.append("Known classes (default package " + restrictionClass.getPackage().getName() + "):"); info.append(FormatUtil.NEWLINE); - for (Class<?> c : known) { + for(Class<?> c : known) { info.append("->" + FormatUtil.NONBREAKING_SPACE); info.append(canonicalClassName(c, getRestrictionClass())); info.append(FormatUtil.NEWLINE); @@ -279,13 +284,13 @@ public class ClassParameter<C> extends AbstractParameter<Class<? extends C>> { */ public static String canonicalClassName(Class<?> c, Package pkg, String postfix) { String name = c.getName(); - if (pkg != null) { + if(pkg != null) { String prefix = pkg.getName() + "."; - if (name.startsWith(prefix)) { + if(name.startsWith(prefix)) { name = name.substring(prefix.length()); } } - if (postfix != null && name.endsWith(postfix)) { + if(postfix != null && name.endsWith(postfix)) { name = name.substring(0, name.length() - postfix.length()); } return name; @@ -299,7 +304,7 @@ public class ClassParameter<C> extends AbstractParameter<Class<? extends C>> { * @return Simplified class name. */ public static String canonicalClassName(Class<?> c, Class<?> parent) { - if (parent == null) { + if(parent == null) { return canonicalClassName(c, null, InspectionUtil.FACTORY_POSTFIX); } return canonicalClassName(c, parent.getPackage(), InspectionUtil.FACTORY_POSTFIX); diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/DistanceParameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/DistanceParameter.java index e97b6d0e..eda54082 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/DistanceParameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/DistanceParameter.java @@ -36,7 +36,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.WrongParameterValueException * * @param <D> Distance type */ -public class DistanceParameter<D extends Distance<D>> extends AbstractParameter<D> { +public class DistanceParameter<D extends Distance<D>> extends AbstractParameter<DistanceParameter<D>, D> { /** * Distance type */ diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/DoubleListParameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/DoubleListParameter.java index 89cfc345..84f97734 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/DoubleListParameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/DoubleListParameter.java @@ -37,7 +37,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.WrongParameterValueException * @author Steffi Wanka * @author Erich Schubert */ -public class DoubleListParameter extends ListParameter<Double> { +public class DoubleListParameter extends ListParameter<DoubleListParameter, Double> { /** * Constructs a list parameter with the given optionID and optional flag. * @@ -83,7 +83,7 @@ public class DoubleListParameter extends ListParameter<Double> { String[] values = SPLIT.split((String) obj); ArrayList<Double> doubleValue = new ArrayList<>(values.length); for(String val : values) { - doubleValue.add(Double.valueOf(val)); + doubleValue.add(FormatUtil.parseDouble(val)); } return doubleValue; } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/DoubleParameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/DoubleParameter.java index 632e1f8c..efa64370 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/DoubleParameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/DoubleParameter.java @@ -23,9 +23,9 @@ package de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters; along with this program. If not, see <http://www.gnu.org/licenses/>. */ +import de.lmu.ifi.dbs.elki.utilities.FormatUtil; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; import de.lmu.ifi.dbs.elki.utilities.optionhandling.WrongParameterValueException; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.ParameterConstraint; /** * Parameter class for a parameter specifying a double value. @@ -33,36 +33,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.ParameterConstra * @author Steffi Wanka * @author Erich Schubert */ -public class DoubleParameter extends NumberParameter<Double> { - /** - * Constructs a double parameter with the given optionID, parameter - * constraint, and default value. - * - * @param optionID the unique id of this parameter - * @param defaultValue the default value for this parameter - * @param constraint the constraint of this parameter - * @deprecated Use {@link #addConstraint} instead. - */ - @Deprecated - public DoubleParameter(OptionID optionID, double defaultValue, ParameterConstraint<Number> constraint) { - super(optionID, defaultValue); - addConstraint(constraint); - } - - /** - * Constructs a double parameter with the given optionID, and parameter - * constraint. - * - * @param optionID the unique id of this parameter - * @param constraint the constraint of this parameter - * @deprecated Use {@link #addConstraint} instead. - */ - @Deprecated - public DoubleParameter(OptionID optionID, ParameterConstraint<Number> constraint) { - super(optionID); - addConstraint(constraint); - } - +public class DoubleParameter extends NumberParameter<DoubleParameter, Double> { /** * Constructs a double parameter with the given optionID and default value. * @@ -74,20 +45,6 @@ public class DoubleParameter extends NumberParameter<Double> { } /** - * Constructs a double parameter with the given optionID and default value. - * - * @param optionID the unique optionID - * @param optional Flag to indicate that the parameter is optional - * - * @deprecated Use {@link #setOptional} instead. - */ - @Deprecated - public DoubleParameter(OptionID optionID, boolean optional) { - super(optionID); - setOptional(optional); - } - - /** * Constructs a double parameter with the given optionID. * * @param optionID the unique id of this parameter @@ -103,14 +60,16 @@ public class DoubleParameter extends NumberParameter<Double> { @Override protected Double parseValue(Object obj) throws WrongParameterValueException { - if (obj instanceof Double) { + if(obj instanceof Double) { return (Double) obj; } try { - return Double.valueOf(obj.toString()); - } catch (NullPointerException e) { + return FormatUtil.parseDouble(obj.toString()); + } + catch(NullPointerException e) { throw new WrongParameterValueException("Wrong parameter format! Parameter \"" + getName() + "\" requires a double value, read: " + obj + "!\n"); - } catch (NumberFormatException e) { + } + catch(NumberFormatException e) { throw new WrongParameterValueException("Wrong parameter format! Parameter \"" + getName() + "\" requires a double value, read: " + obj + "!\n"); } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/EnumParameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/EnumParameter.java index 4d05753c..22d7dd54 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/EnumParameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/EnumParameter.java @@ -62,7 +62,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.WrongParameterValueException *
* @param <E> Enum type
*/
-public class EnumParameter<E extends Enum<E>> extends AbstractParameter<E> {
+public class EnumParameter<E extends Enum<E>> extends AbstractParameter<EnumParameter<E>, E> {
/**
* Reference to the actual enum type, for T.valueOf().
diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/FileListParameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/FileListParameter.java index eb638298..9e115dc7 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/FileListParameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/FileListParameter.java @@ -38,7 +38,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.WrongParameterValueException * @author Steffi Wanka * @author Erich Schubert */ -public class FileListParameter extends ListParameter<File> { +public class FileListParameter extends ListParameter<FileListParameter, File> { /** * Available types of the files: {@link #INPUT_FILES} denotes input files, * {@link #OUTPUT_FILES} denotes output files. diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/FileParameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/FileParameter.java index ea3fa454..3e9fdc7d 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/FileParameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/FileParameter.java @@ -38,7 +38,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.WrongParameterValueException * @author Erich Schubert */ // TODO: turn FileType into a Constraint? -public class FileParameter extends AbstractParameter<File> { +public class FileParameter extends AbstractParameter<FileParameter, File> { /** * Available file types: {@link #INPUT_FILE} denotes an input file, * {@link #OUTPUT_FILE} denotes an output file. diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/Flag.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/Flag.java index 7587d2a5..f9e1a1f1 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/Flag.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/Flag.java @@ -37,7 +37,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.WrongParameterValueException * @author Steffi Wanka * @author Erich Schubert */ -public class Flag extends AbstractParameter<Boolean> { +public class Flag extends AbstractParameter<Flag, Boolean> { /** * Constant indicating that the flag is set. */ diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/IntListParameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/IntListParameter.java index 93012955..cc8327b4 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/IntListParameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/IntListParameter.java @@ -37,7 +37,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.WrongParameterValueException * @author Elke Achtert * @author Erich Schubert */ -public class IntListParameter extends ListParameter<Integer> { +public class IntListParameter extends ListParameter<IntListParameter, Integer> { /** * Constructs an integer list parameter * diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/IntParameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/IntParameter.java index 30457330..3d867770 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/IntParameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/IntParameter.java @@ -23,10 +23,10 @@ package de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters; along with this program. If not, see <http://www.gnu.org/licenses/>. */ +import de.lmu.ifi.dbs.elki.utilities.FormatUtil; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; import de.lmu.ifi.dbs.elki.utilities.optionhandling.ParameterException; import de.lmu.ifi.dbs.elki.utilities.optionhandling.WrongParameterValueException; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.ParameterConstraint; /** * Parameter class for a parameter specifying an integer value. @@ -34,51 +34,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.ParameterConstra * @author Steffi Wanka * @author Erich Schubert */ -public class IntParameter extends NumberParameter<Integer> { - /** - * Constructs an integer parameter with the given optionID, parameter - * constraint, and default value. - * - * @param optionID optionID the unique id of the option - * @param defaultValue the default value - * @param constraint the constraint for this integer parameter - * @deprecated Use {@link #addConstraint} instead. - */ - @Deprecated - public IntParameter(OptionID optionID, int defaultValue, ParameterConstraint<Number> constraint) { - super(optionID, Integer.valueOf(defaultValue)); - addConstraint(constraint); - } - - /** - * Constructs an integer parameter with the given optionID, parameter - * constraint, and optional flag. - * - * @param optionID optionID the unique id of the option - * @param constraint the constraint for this integer parameter - * @param optional specifies if this parameter is an optional parameter - * @deprecated Use {@link #addConstraint} instead. - */ - @Deprecated - public IntParameter(OptionID optionID, ParameterConstraint<Number> constraint, boolean optional) { - super(optionID, optional); - addConstraint(constraint); - } - - /** - * Constructs an integer parameter with the given optionID, and parameter - * constraint. - * - * @param optionID optionID the unique id of the option - * @param constraint the constraint for this integer parameter - * @deprecated Use {@link #addConstraint} instead. - */ - @Deprecated - public IntParameter(OptionID optionID, ParameterConstraint<Number> constraint) { - super(optionID); - addConstraint(constraint); - } - +public class IntParameter extends NumberParameter<IntParameter, Integer> { /** * Constructs an integer parameter with the given optionID. * @@ -93,18 +49,6 @@ public class IntParameter extends NumberParameter<Integer> { * Constructs an integer parameter with the given optionID. * * @param optionID optionID the unique id of the option - * @param optional specifies if this parameter is an optional parameter - * @deprecated Use {@link #setOptional} instead. - */ - @Deprecated - public IntParameter(OptionID optionID, boolean optional) { - super(optionID, optional); - } - - /** - * Constructs an integer parameter with the given optionID. - * - * @param optionID optionID the unique id of the option */ public IntParameter(OptionID optionID) { super(optionID); @@ -117,14 +61,17 @@ public class IntParameter extends NumberParameter<Integer> { @Override protected Integer parseValue(Object obj) throws ParameterException { - if (obj instanceof Integer) { + if(obj instanceof Integer) { return (Integer) obj; } try { - return Integer.valueOf(obj.toString()); - } catch (NullPointerException e) { + final String s = obj.toString(); + return (int) FormatUtil.parseLongBase10(s, 0, s.length()); + } + catch(NullPointerException e) { throw new WrongParameterValueException("Wrong parameter format! Parameter \"" + getName() + "\" requires an integer value, read: " + obj + "!\n"); - } catch (NumberFormatException e) { + } + catch(NumberFormatException e) { throw new WrongParameterValueException("Wrong parameter format! Parameter \"" + getName() + "\" requires an integer value, read: " + obj + "!\n"); } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/ListParameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/ListParameter.java index 119fb121..df520daa 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/ListParameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/ListParameter.java @@ -34,9 +34,10 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; * @author Steffi Wanka * @author Erich Schubert * + * @param <THIS> Type self-reference * @param <T> List type */ -public abstract class ListParameter<T> extends AbstractParameter<List<T>> { +public abstract class ListParameter<THIS extends ListParameter<THIS, T>, T> extends AbstractParameter<THIS, List<T>> { /** * A pattern defining a ",". */ diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/LongParameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/LongParameter.java index f5d441b5..5ab6b487 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/LongParameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/LongParameter.java @@ -26,7 +26,6 @@ package de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; import de.lmu.ifi.dbs.elki.utilities.optionhandling.ParameterException; import de.lmu.ifi.dbs.elki.utilities.optionhandling.WrongParameterValueException; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.ParameterConstraint; /** * Parameter class for a parameter specifying a long value. @@ -34,22 +33,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.ParameterConstra * @author Steffi Wanka * @author Erich Schubert */ -public class LongParameter extends NumberParameter<Long> { - /** - * Constructs a long parameter with the given optionID, parameter constraint - * and default value. - * - * @param optionID the unique OptionID for this parameter - * @param constraint the parameter constraint for this long parameter - * @param defaultValue the default value - * @deprecated Use {@link #addConstraint} instead! - */ - @Deprecated - public LongParameter(OptionID optionID, ParameterConstraint<Number> constraint, long defaultValue) { - super(optionID, Long.valueOf(defaultValue)); - addConstraint(constraint); - } - +public class LongParameter extends NumberParameter<LongParameter, Long> { /** * Constructs a long parameter with the given optionID and default value. * @@ -68,7 +52,7 @@ public class LongParameter extends NumberParameter<Long> { public LongParameter(OptionID optionID) { super(optionID); } - + @Override public String getValueAsString() { return getValue().toString(); diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/NumberParameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/NumberParameter.java index a4448d30..fabdce53 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/NumberParameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/NumberParameter.java @@ -30,10 +30,11 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; * * @author Steffi Wanka * @author Erich Schubert - * + * + * @param <THIS> type self-reference * @param <T> the type of a possible value (i.e., the type of the option) */ -public abstract class NumberParameter<T extends Number> extends AbstractParameter<T> { +public abstract class NumberParameter<THIS extends NumberParameter<THIS, T>, T extends Number> extends AbstractParameter<THIS, T> { /** * Constructs a number parameter with the given optionID and default Value. * diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/Parameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/Parameter.java index 110633b3..ffacb6d1 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/Parameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/Parameter.java @@ -80,8 +80,9 @@ public interface Parameter<T> { * Specifies if this parameter is an optional parameter. * * @param opt true if this parameter is optional, false otherwise + * @return the parameter itself, for chaining */ - public abstract void setOptional(boolean opt); + public abstract Parameter<T> setOptional(boolean opt); /** * Checks if this parameter is an optional parameter. @@ -232,6 +233,7 @@ public interface Parameter<T> { * Add an additional constraint. * * @param constraint Constraint to add. + * @return the parameter itself, for chaining */ - public abstract void addConstraint(ParameterConstraint<? super T> constraint); + public abstract Parameter<T> addConstraint(ParameterConstraint<? super T> constraint); } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/PatternParameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/PatternParameter.java index b76edbbb..e3cb4bcf 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/PatternParameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/PatternParameter.java @@ -37,7 +37,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.WrongParameterValueException * @author Steffi Wanka * @author Erich Schubert */ -public class PatternParameter extends AbstractParameter<Pattern> { +public class PatternParameter extends AbstractParameter<PatternParameter, Pattern> { /** * Constructs a pattern parameter with the given optionID, and default value. * diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/RandomParameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/RandomParameter.java index 6c0668dd..bf5e0cb0 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/RandomParameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/RandomParameter.java @@ -33,7 +33,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.WrongParameterValueException * * @author Erich Schubert */ -public class RandomParameter extends AbstractParameter<RandomFactory> { +public class RandomParameter extends AbstractParameter<RandomParameter, RandomFactory> { /** * Seed value, if used */ diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/StringParameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/StringParameter.java index 3a9bbf11..dc2a2a32 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/StringParameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/StringParameter.java @@ -27,7 +27,6 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; import de.lmu.ifi.dbs.elki.utilities.optionhandling.ParameterException; import de.lmu.ifi.dbs.elki.utilities.optionhandling.UnspecifiedParameterException; import de.lmu.ifi.dbs.elki.utilities.optionhandling.WrongParameterValueException; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.ParameterConstraint; /** * Parameter class for a parameter specifying a string. @@ -35,38 +34,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.ParameterConstra * @author Steffi Wanka * @author Erich Schubert */ -public class StringParameter extends AbstractParameter<String> { - /** - * Constructs a string parameter with the given optionID, constraints and - * default value. - * - * @param optionID the unique id of the parameter - * @param constraint parameter constraint - * @param defaultValue the default value of the parameter - * - * @deprecated Use {@link #addConstraint} instead! - */ - @Deprecated - public StringParameter(OptionID optionID, ParameterConstraint<String> constraint, String defaultValue) { - super(optionID, defaultValue); - addConstraint(constraint); - } - - /** - * Constructs a string parameter with the given optionID, constraints and - * default value. - * - * @param optionID the unique id of the parameter - * @param constraint parameter constraint - * - * @deprecated Use {@link #addConstraint} instead! - */ - @Deprecated - public StringParameter(OptionID optionID, ParameterConstraint<String> constraint) { - super(optionID); - addConstraint(constraint); - } - +public class StringParameter extends AbstractParameter<StringParameter, String> { /** * Constructs a string parameter with the given optionID, and default value. * diff --git a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/VectorListParameter.java b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/VectorListParameter.java index 906bfbd8..43fa0797 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/VectorListParameter.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/optionhandling/parameters/VectorListParameter.java @@ -27,6 +27,7 @@ import java.util.ArrayList; import java.util.Iterator; import java.util.List; +import de.lmu.ifi.dbs.elki.utilities.FormatUtil; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; import de.lmu.ifi.dbs.elki.utilities.optionhandling.ParameterException; import de.lmu.ifi.dbs.elki.utilities.optionhandling.WrongParameterValueException; @@ -38,31 +39,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.ParameterConstra * @author Steffi Wanka * @author Erich Schubert */ -public class VectorListParameter extends ListParameter<List<Double>> { - /** - * Constructs a vector list parameter with the given name and description. - * - * @param optionID Option ID - * @param constraints Constraint - * @param defaultValue Default value - */ - public VectorListParameter(OptionID optionID, List<ParameterConstraint<List<List<Double>>>> constraints, List<List<Double>> defaultValue) { - super(optionID, defaultValue); - addConstraints(constraints); - } - - /** - * Constructs a vector list parameter with the given name and description. - * - * @param optionID Option ID - * @param constraints Constraints - * @param optional Optional flag - */ - public VectorListParameter(OptionID optionID, List<ParameterConstraint<List<List<Double>>>> constraints, boolean optional) { - super(optionID, optional); - addConstraints(constraints); - } - +public class VectorListParameter extends ListParameter<VectorListParameter, List<Double>> { /** * Constructs a vector list parameter with the given name and description. * @@ -139,12 +116,12 @@ public class VectorListParameter extends ListParameter<List<Double>> { Iterator<Double> veciter = vec.iterator(); while(veciter.hasNext()) { buf.append(veciter.next().toString()); - if (veciter.hasNext()) { + if(veciter.hasNext()) { buf.append(LIST_SEP); } } // Append separation character - if (valiter.hasNext()) { + if(valiter.hasNext()) { buf.append(VECTOR_SEP); } } @@ -184,7 +161,7 @@ public class VectorListParameter extends ListParameter<List<Double>> { ArrayList<Double> vectorCoord = new ArrayList<>(); for(String coordinate : coordinates) { try { - vectorCoord.add(Double.valueOf(coordinate)); + vectorCoord.add(FormatUtil.parseDouble(coordinate)); } catch(NumberFormatException e) { throw new WrongParameterValueException("Wrong parameter format! Coordinates of vector \"" + vector + "\" are not valid!"); diff --git a/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/AxisBasedReferencePoints.java b/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/AxisBasedReferencePoints.java index 24829d98..d8544cd4 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/AxisBasedReferencePoints.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/AxisBasedReferencePoints.java @@ -32,7 +32,7 @@ import de.lmu.ifi.dbs.elki.database.relation.RelationUtil; import de.lmu.ifi.dbs.elki.utilities.DatabaseUtil; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; import de.lmu.ifi.dbs.elki.utilities.pairs.Pair; @@ -83,7 +83,7 @@ public class AxisBasedReferencePoints<V extends NumberVector<?>> implements Refe // Compute mean and extend from minmax. double[] mean = new double[dim]; double[] delta = new double[dim]; - for (int d = 0; d < dim; d++) { + for(int d = 0; d < dim; d++) { mean[d] = (minmax.first.doubleValue(d) + minmax.second.doubleValue(d)) * .5; delta[d] = spacescale * (minmax.second.doubleValue(d) - mean[d]); } @@ -92,21 +92,22 @@ public class AxisBasedReferencePoints<V extends NumberVector<?>> implements Refe double[] vec = new double[dim]; // Use min and max - for (int d = 0; d < dim; d++) { + for(int d = 0; d < dim; d++) { vec[d] = mean[d] - delta[d]; } result.add(factory.newNumberVector(vec)); - for (int d = 0; d < dim; d++) { + for(int d = 0; d < dim; d++) { vec[d] = mean[d] + delta[d]; } result.add(factory.newNumberVector(vec)); // Plus axis end points: - for (int i = 0; i < dim; i++) { - for (int d = 0; d < dim; d++) { - if (d != i) { + for(int i = 0; i < dim; i++) { + for(int d = 0; d < dim; d++) { + if(d != i) { vec[d] = mean[d] - delta[d]; - } else { + } + else { vec[d] = mean[d] + delta[d]; } } @@ -133,8 +134,8 @@ public class AxisBasedReferencePoints<V extends NumberVector<?>> implements Refe protected void makeOptions(Parameterization config) { super.makeOptions(config); DoubleParameter spacescaleP = new DoubleParameter(SPACE_SCALE_ID, 1.0); - spacescaleP.addConstraint(new GreaterEqualConstraint(0.0)); - if (config.grab(spacescaleP)) { + spacescaleP.addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_DOUBLE); + if(config.grab(spacescaleP)) { spacescale = spacescaleP.getValue(); } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/GridBasedReferencePoints.java b/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/GridBasedReferencePoints.java index b94564cf..007efe6f 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/GridBasedReferencePoints.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/GridBasedReferencePoints.java @@ -29,10 +29,11 @@ import java.util.Collection; import de.lmu.ifi.dbs.elki.data.NumberVector; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.database.relation.RelationUtil; +import de.lmu.ifi.dbs.elki.math.MathUtil; import de.lmu.ifi.dbs.elki.utilities.DatabaseUtil; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter; @@ -97,23 +98,23 @@ public class GridBasedReferencePoints<V extends NumberVector<?>> implements Refe // Compute mean from minmax. double[] mean = new double[dim]; - for (int d = 0; d < dim; d++) { + for(int d = 0; d < dim; d++) { mean[d] = (minmax.first.doubleValue(d) + minmax.second.doubleValue(d)) * .5; } - int gridpoints = Math.max(1, (int) Math.pow(gridres + 1, dim)); + int gridpoints = Math.max(1, MathUtil.ipowi(gridres + 1, dim)); ArrayList<V> result = new ArrayList<>(gridpoints); double[] delta = new double[dim]; - if (gridres > 0) { + if(gridres > 0) { double halfgrid = gridres / 2.0; - for (int d = 0; d < dim; d++) { + for(int d = 0; d < dim; d++) { delta[d] = (minmax.second.doubleValue(d) - minmax.first.doubleValue(d)) / gridres; } double[] vec = new double[dim]; - for (int i = 0; i < gridpoints; i++) { + for(int i = 0; i < gridpoints; i++) { int acc = i; - for (int d = 0; d < dim; d++) { + for(int d = 0; d < dim; d++) { int coord = acc % (gridres + 1); acc = acc / (gridres + 1); vec[d] = mean[d] + (coord - halfgrid) * delta[d] * gridscale; @@ -122,7 +123,8 @@ public class GridBasedReferencePoints<V extends NumberVector<?>> implements Refe // logger.debug("New reference point: " + FormatUtil.format(vec)); result.add(newp); } - } else { + } + else { result.add(factory.newNumberVector(mean)); // logger.debug("New reference point: " + FormatUtil.format(mean)); } @@ -152,14 +154,14 @@ public class GridBasedReferencePoints<V extends NumberVector<?>> implements Refe protected void makeOptions(Parameterization config) { super.makeOptions(config); IntParameter gridP = new IntParameter(GRID_ID, 1); - gridP.addConstraint(new GreaterEqualConstraint(0)); - if (config.grab(gridP)) { + gridP.addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_INT); + if(config.grab(gridP)) { gridres = gridP.getValue(); } DoubleParameter gridscaleP = new DoubleParameter(GRID_SCALE_ID, 1.0); - gridscaleP.addConstraint(new GreaterEqualConstraint(0.0)); - if (config.grab(gridscaleP)) { + gridscaleP.addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_DOUBLE); + if(config.grab(gridscaleP)) { gridscale = gridscaleP.getValue(); } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/RandomGeneratedReferencePoints.java b/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/RandomGeneratedReferencePoints.java index 0a59d410..9d866ecc 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/RandomGeneratedReferencePoints.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/RandomGeneratedReferencePoints.java @@ -32,7 +32,7 @@ import de.lmu.ifi.dbs.elki.database.relation.RelationUtil; import de.lmu.ifi.dbs.elki.utilities.DatabaseUtil; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter; @@ -97,15 +97,15 @@ public class RandomGeneratedReferencePoints<V extends NumberVector<?>> implement // Compute mean from minmax. double[] mean = new double[dim]; double[] delta = new double[dim]; - for (int d = 0; d < dim; d++) { + for(int d = 0; d < dim; d++) { mean[d] = (minmax.first.doubleValue(d + 1) + minmax.second.doubleValue(d + 1)) * .5; delta[d] = (minmax.second.doubleValue(d + 1) - minmax.first.doubleValue(d + 1)); } ArrayList<V> result = new ArrayList<>(samplesize); double[] vec = new double[dim]; - for (int i = 0; i < samplesize; i++) { - for (int d = 0; d < dim; d++) { + for(int i = 0; i < samplesize; i++) { + for(int d = 0; d < dim; d++) { vec[d] = mean[d] + (Math.random() - 0.5) * scale * delta[d]; } V newp = factory.newNumberVector(vec); @@ -139,14 +139,14 @@ public class RandomGeneratedReferencePoints<V extends NumberVector<?>> implement super.makeOptions(config); IntParameter samplesizeP = new IntParameter(N_ID); - samplesizeP.addConstraint(new GreaterConstraint(0)); - if (config.grab(samplesizeP)) { + samplesizeP.addConstraint(CommonConstraints.GREATER_EQUAL_ONE_INT); + if(config.grab(samplesizeP)) { samplesize = samplesizeP.getValue(); } DoubleParameter scaleP = new DoubleParameter(SCALE_ID, 1.0); - scaleP.addConstraint(new GreaterConstraint(0.0)); - if (config.grab(scaleP)) { + scaleP.addConstraint(CommonConstraints.GREATER_THAN_ZERO_DOUBLE); + if(config.grab(scaleP)) { scale = scaleP.getValue(); } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/RandomSampleReferencePoints.java b/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/RandomSampleReferencePoints.java index a2a48b30..ea80d9d9 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/RandomSampleReferencePoints.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/RandomSampleReferencePoints.java @@ -36,7 +36,7 @@ import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.logging.LoggingUtil; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter; @@ -151,7 +151,7 @@ public class RandomSampleReferencePoints<V extends NumberVector<?>> implements R protected void makeOptions(Parameterization config) { super.makeOptions(config); IntParameter samplesizeP = new IntParameter(N_ID); - samplesizeP.addConstraint(new GreaterConstraint(0)); + samplesizeP.addConstraint(CommonConstraints.GREATER_EQUAL_ONE_INT); if(config.grab(samplesizeP)) { samplesize = samplesizeP.intValue(); } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/StarBasedReferencePoints.java b/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/StarBasedReferencePoints.java index 611100b4..74cdf92b 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/StarBasedReferencePoints.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/referencepoints/StarBasedReferencePoints.java @@ -33,7 +33,7 @@ import de.lmu.ifi.dbs.elki.database.relation.RelationUtil; import de.lmu.ifi.dbs.elki.utilities.DatabaseUtil; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.Flag; @@ -96,14 +96,14 @@ public class StarBasedReferencePoints<V extends NumberVector<?>> implements Refe double[] centroid = new double[dim]; double[] min = new double[dim]; double[] max = new double[dim]; - for (int d = 0; d < dim; d++) { + for(int d = 0; d < dim; d++) { centroid[d] = 0; min[d] = Double.MAX_VALUE; max[d] = -Double.MAX_VALUE; } - for (DBIDIter iditer = database.iterDBIDs(); iditer.valid(); iditer.advance()) { + for(DBIDIter iditer = database.iterDBIDs(); iditer.valid(); iditer.advance()) { V obj = database.get(iditer); - for (int d = 0; d < dim; d++) { + for(int d = 0; d < dim; d++) { double val = obj.doubleValue(d + 1); centroid[d] += val; min[d] = Math.min(min[d], val); @@ -111,21 +111,21 @@ public class StarBasedReferencePoints<V extends NumberVector<?>> implements Refe } } // finish centroid, scale min, max - for (int d = 0; d < dim; d++) { + for(int d = 0; d < dim; d++) { centroid[d] = centroid[d] / database.size(); min[d] = (min[d] - centroid[d]) * scale + centroid[d]; max[d] = (max[d] - centroid[d]) * scale + centroid[d]; } ArrayList<V> result = new ArrayList<>(2 * dim + 1); - if (!nocenter) { + if(!nocenter) { result.add(factory.newNumberVector(centroid)); } // Plus axis end points through centroid double[] vec = new double[dim]; - for (int i = 0; i < dim; i++) { - for (int d = 0; d < dim; d++) { - if (d != i) { + for(int i = 0; i < dim; i++) { + for(int d = 0; d < dim; d++) { + if(d != i) { vec[d] = centroid[d]; } } @@ -160,13 +160,13 @@ public class StarBasedReferencePoints<V extends NumberVector<?>> implements Refe protected void makeOptions(Parameterization config) { super.makeOptions(config); Flag nocenterF = new Flag(NOCENTER_ID); - if (config.grab(nocenterF)) { + if(config.grab(nocenterF)) { nocenter = nocenterF.getValue(); } DoubleParameter scaleP = new DoubleParameter(SCALE_ID, 1.0); - scaleP.addConstraint(new GreaterEqualConstraint(0.0)); - if (config.grab(scaleP)) { + scaleP.addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_DOUBLE); + if(config.grab(scaleP)) { scale = scaleP.getValue(); } } diff --git a/src/de/lmu/ifi/dbs/elki/utilities/scaling/outlier/TopKOutlierScaling.java b/src/de/lmu/ifi/dbs/elki/utilities/scaling/outlier/TopKOutlierScaling.java index 25103dbc..71a495a6 100644 --- a/src/de/lmu/ifi/dbs/elki/utilities/scaling/outlier/TopKOutlierScaling.java +++ b/src/de/lmu/ifi/dbs/elki/utilities/scaling/outlier/TopKOutlierScaling.java @@ -31,7 +31,7 @@ import de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike.ArrayLikeUtil; import de.lmu.ifi.dbs.elki.utilities.datastructures.arraylike.NumberArrayAdapter; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.Flag; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter; @@ -97,36 +97,36 @@ public class TopKOutlierScaling implements OutlierScalingFunction { @Override public void prepare(OutlierResult or) { - if (k <= 0) { + if(k <= 0) { LoggingUtil.warning("No k configured for Top-k outlier scaling!"); } DBIDIter order = or.getOrdering().iter(or.getOrdering().getDBIDs()).iter(); - for (int i = 0; i < k && order.valid(); i++, order.advance()) { + for(int i = 0; i < k && order.valid(); i++, order.advance()) { cutoff = or.getScores().get(order); } max = or.getOutlierMeta().getActualMaximum(); ground = or.getOutlierMeta().getTheoreticalBaseline(); - if (Double.isInfinite(ground) || Double.isNaN(ground)) { + if(Double.isInfinite(ground) || Double.isNaN(ground)) { ground = or.getOutlierMeta().getTheoreticalMinimum(); } - if (Double.isInfinite(ground) || Double.isNaN(ground)) { + if(Double.isInfinite(ground) || Double.isNaN(ground)) { ground = or.getOutlierMeta().getActualMinimum(); } - if (Double.isInfinite(ground) || Double.isNaN(ground)) { + if(Double.isInfinite(ground) || Double.isNaN(ground)) { ground = Math.min(0.0, cutoff); } } @Override public <A> void prepare(A array, NumberArrayAdapter<?, A> adapter) { - if (k <= 0) { + if(k <= 0) { LoggingUtil.warning("No k configured for Top-k outlier scaling!"); } double[] scores = ArrayLikeUtil.toPrimitiveDoubleArray(array, adapter); QuickSelect.quickSelect(scores, k); cutoff = scores[k - 1]; max = Double.NEGATIVE_INFINITY; - for (double v : scores) { + for(double v : scores) { max = Math.max(max, v); } ground = Math.min(0.0, cutoff); @@ -134,7 +134,7 @@ public class TopKOutlierScaling implements OutlierScalingFunction { @Override public double getMax() { - if (binary) { + if(binary) { return 1.0; } return max; @@ -142,7 +142,7 @@ public class TopKOutlierScaling implements OutlierScalingFunction { @Override public double getMin() { - if (binary) { + if(binary) { return 0.0; } return ground; @@ -150,16 +150,19 @@ public class TopKOutlierScaling implements OutlierScalingFunction { @Override public double getScaled(double value) { - if (binary) { - if (value >= cutoff) { + if(binary) { + if(value >= cutoff) { return 1; - } else { + } + else { return 0; } - } else { - if (value >= cutoff) { + } + else { + if(value >= cutoff) { return (value - ground) / (max - ground); - } else { + } + else { return 0.0; } } @@ -181,13 +184,13 @@ public class TopKOutlierScaling implements OutlierScalingFunction { protected void makeOptions(Parameterization config) { super.makeOptions(config); IntParameter kP = new IntParameter(K_ID); - kP.addConstraint(new GreaterConstraint(1)); - if (config.grab(kP)) { + kP.addConstraint(CommonConstraints.GREATER_THAN_ONE_INT); + if(config.grab(kP)) { k = kP.intValue(); } Flag binaryF = new Flag(BINARY_ID); - if (config.grab(binaryF)) { + if(config.grab(binaryF)) { binary = binaryF.isTrue(); } } |