Histogram.java revision 12745:f068a4ffddd2
1/* 2 * Copyright (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26package com.sun.java.util.jar.pack; 27 28import java.io.IOException; 29import java.io.InputStream; 30import java.io.PrintStream; 31import java.util.Arrays; 32 33/** 34 * Histogram derived from an integer array of events (int[]). 35 * @author John Rose 36 */ 37final class Histogram { 38 // Compact histogram representation: 4 bytes per distinct value, 39 // plus 5 words per distinct count. 40 protected final int[][] matrix; // multi-row matrix {{counti,valueij...}} 41 protected final int totalWeight; // sum of all counts 42 43 // These are created eagerly also, since that saves work. 44 // They cost another 8 bytes per distinct value. 45 protected final int[] values; // unique values, sorted by value 46 protected final int[] counts; // counts, same order as values 47 48 private static final long LOW32 = (long)-1 >>> 32; 49 50 /** Build a histogram given a sequence of values. 51 * To save work, the input should be sorted, but need not be. 52 */ 53 public 54 Histogram(int[] valueSequence) { 55 long[] hist2col = computeHistogram2Col(maybeSort(valueSequence)); 56 int[][] table = makeTable(hist2col); 57 values = table[0]; 58 counts = table[1]; 59 this.matrix = makeMatrix(hist2col); 60 this.totalWeight = valueSequence.length; 61 assert(assertWellFormed(valueSequence)); 62 } 63 public 64 Histogram(int[] valueSequence, int start, int end) { 65 this(sortedSlice(valueSequence, start, end)); 66 } 67 68 /** Build a histogram given a compact matrix of counts and values. */ 69 public 70 Histogram(int[][] matrix) { 71 // sort the rows 72 matrix = normalizeMatrix(matrix); // clone and sort 73 this.matrix = matrix; 74 int length = 0; 75 int weight = 0; 76 for (int i = 0; i < matrix.length; i++) { 77 int rowLength = matrix[i].length-1; 78 length += rowLength; 79 weight += matrix[i][0] * rowLength; 80 } 81 this.totalWeight = weight; 82 long[] hist2col = new long[length]; 83 int fillp = 0; 84 for (int i = 0; i < matrix.length; i++) { 85 for (int j = 1; j < matrix[i].length; j++) { 86 // sort key is value, so put it in the high 32! 87 hist2col[fillp++] = ((long) matrix[i][j] << 32) 88 | (LOW32 & matrix[i][0]); 89 } 90 } 91 assert(fillp == hist2col.length); 92 Arrays.sort(hist2col); 93 int[][] table = makeTable(hist2col); 94 values = table[1]; //backwards 95 counts = table[0]; //backwards 96 assert(assertWellFormed(null)); 97 } 98 99 /** Histogram of int values, reported compactly as a ragged matrix, 100 * indexed by descending frequency rank. 101 * <p> 102 * Format of matrix: 103 * Each row in the matrix begins with an occurrence count, 104 * and continues with all int values that occur at that frequency. 105 * <pre> 106 * int[][] matrix = { 107 * { count1, value11, value12, value13, ... }, 108 * { count2, value21, value22, ... }, 109 * ... 110 * } 111 * </pre> 112 * The first column of the matrix { count1, count2, ... } 113 * is sorted in descending order, and contains no duplicates. 114 * Each row of the matrix (apart from its first element) 115 * is sorted in ascending order, and contains no duplicates. 116 * That is, each sequence { valuei1, valuei2, ... } is sorted. 117 */ 118 public 119 int[][] getMatrix() { return matrix; } 120 121 public 122 int getRowCount() { return matrix.length; } 123 124 public 125 int getRowFrequency(int rn) { return matrix[rn][0]; } 126 127 public 128 int getRowLength(int rn) { return matrix[rn].length-1; } 129 130 public 131 int getRowValue(int rn, int vn) { return matrix[rn][vn+1]; } 132 133 public 134 int getRowWeight(int rn) { 135 return getRowFrequency(rn) * getRowLength(rn); 136 } 137 138 public 139 int getTotalWeight() { 140 return totalWeight; 141 } 142 143 public 144 int getTotalLength() { 145 return values.length; 146 } 147 148 /** Returns an array of all values, sorted. */ 149 public 150 int[] getAllValues() { 151 152 return values; 153 } 154 155 /** Returns an array parallel with {@link #getValues}, 156 * with a frequency for each value. 157 */ 158 public 159 int[] getAllFrequencies() { 160 return counts; 161 } 162 163 private static double log2 = Math.log(2); 164 165 public 166 int getFrequency(int value) { 167 int pos = Arrays.binarySearch(values, value); 168 if (pos < 0) return 0; 169 assert(values[pos] == value); 170 return counts[pos]; 171 } 172 173 public 174 double getBitLength(int value) { 175 double prob = (double) getFrequency(value) / getTotalWeight(); 176 return - Math.log(prob) / log2; 177 } 178 179 public 180 double getRowBitLength(int rn) { 181 double prob = (double) getRowFrequency(rn) / getTotalWeight(); 182 return - Math.log(prob) / log2; 183 } 184 185 public 186 interface BitMetric { 187 public double getBitLength(int value); 188 } 189 private final BitMetric bitMetric = new BitMetric() { 190 public double getBitLength(int value) { 191 return Histogram.this.getBitLength(value); 192 } 193 }; 194 public BitMetric getBitMetric() { 195 return bitMetric; 196 } 197 198 /** bit-length is negative entropy: -H(matrix). */ 199 public 200 double getBitLength() { 201 double sum = 0; 202 for (int i = 0; i < matrix.length; i++) { 203 sum += getRowBitLength(i) * getRowWeight(i); 204 } 205 assert(0.1 > Math.abs(sum - getBitLength(bitMetric))); 206 return sum; 207 } 208 209 /** bit-length in to another coding (cross-entropy) */ 210 public 211 double getBitLength(BitMetric len) { 212 double sum = 0; 213 for (int i = 0; i < matrix.length; i++) { 214 for (int j = 1; j < matrix[i].length; j++) { 215 sum += matrix[i][0] * len.getBitLength(matrix[i][j]); 216 } 217 } 218 return sum; 219 } 220 221 private static 222 double round(double x, double scale) { 223 return Math.round(x * scale) / scale; 224 } 225 226 /** Sort rows and columns. 227 * Merge adjacent rows with the same key element [0]. 228 * Make a fresh copy of all of it. 229 */ 230 public int[][] normalizeMatrix(int[][] matrix) { 231 long[] rowMap = new long[matrix.length]; 232 for (int i = 0; i < matrix.length; i++) { 233 if (matrix[i].length <= 1) continue; 234 int count = matrix[i][0]; 235 if (count <= 0) continue; 236 rowMap[i] = (long) count << 32 | i; 237 } 238 Arrays.sort(rowMap); 239 int[][] newMatrix = new int[matrix.length][]; 240 int prevCount = -1; 241 int fillp1 = 0; 242 int fillp2 = 0; 243 for (int i = 0; ; i++) { 244 int[] row; 245 if (i < matrix.length) { 246 long rowMapEntry = rowMap[rowMap.length-i-1]; 247 if (rowMapEntry == 0) continue; 248 row = matrix[(int)rowMapEntry]; 249 assert(rowMapEntry>>>32 == row[0]); 250 } else { 251 row = new int[]{ -1 }; // close it off 252 } 253 if (row[0] != prevCount && fillp2 > fillp1) { 254 // Close off previous run. 255 int length = 0; 256 for (int p = fillp1; p < fillp2; p++) { 257 int[] row0 = newMatrix[p]; // previously visited row 258 assert(row0[0] == prevCount); 259 length += row0.length-1; 260 } 261 int[] row1 = new int[1+length]; // cloned & consolidated row 262 row1[0] = prevCount; 263 int rfillp = 1; 264 for (int p = fillp1; p < fillp2; p++) { 265 int[] row0 = newMatrix[p]; // previously visited row 266 assert(row0[0] == prevCount); 267 System.arraycopy(row0, 1, row1, rfillp, row0.length-1); 268 rfillp += row0.length-1; 269 } 270 if (!isSorted(row1, 1, true)) { 271 Arrays.sort(row1, 1, row1.length); 272 int jfillp = 2; 273 // Detect and squeeze out duplicates. 274 for (int j = 2; j < row1.length; j++) { 275 if (row1[j] != row1[j-1]) 276 row1[jfillp++] = row1[j]; 277 } 278 if (jfillp < row1.length) { 279 // Reallocate because of lost duplicates. 280 int[] newRow1 = new int[jfillp]; 281 System.arraycopy(row1, 0, newRow1, 0, jfillp); 282 row1 = newRow1; 283 } 284 } 285 newMatrix[fillp1++] = row1; 286 fillp2 = fillp1; 287 } 288 if (i == matrix.length) 289 break; 290 prevCount = row[0]; 291 newMatrix[fillp2++] = row; 292 } 293 assert(fillp1 == fillp2); // no unfinished business 294 // Now drop missing rows. 295 matrix = newMatrix; 296 if (fillp1 < matrix.length) { 297 newMatrix = new int[fillp1][]; 298 System.arraycopy(matrix, 0, newMatrix, 0, fillp1); 299 matrix = newMatrix; 300 } 301 return matrix; 302 } 303 304 public 305 String[] getRowTitles(String name) { 306 int totalUnique = getTotalLength(); 307 int ltotalWeight = getTotalWeight(); 308 String[] histTitles = new String[matrix.length]; 309 int cumWeight = 0; 310 int cumUnique = 0; 311 for (int i = 0; i < matrix.length; i++) { 312 int count = getRowFrequency(i); 313 int unique = getRowLength(i); 314 int weight = getRowWeight(i); 315 cumWeight += weight; 316 cumUnique += unique; 317 long wpct = ((long)cumWeight * 100 + ltotalWeight/2) / ltotalWeight; 318 long upct = ((long)cumUnique * 100 + totalUnique/2) / totalUnique; 319 double len = getRowBitLength(i); 320 assert(0.1 > Math.abs(len - getBitLength(matrix[i][1]))); 321 histTitles[i] = name+"["+i+"]" 322 +" len="+round(len,10) 323 +" ("+count+"*["+unique+"])" 324 +" ("+cumWeight+":"+wpct+"%)" 325 +" ["+cumUnique+":"+upct+"%]"; 326 } 327 return histTitles; 328 } 329 330 /** Print a report of this histogram. 331 */ 332 public 333 void print(PrintStream out) { 334 print("hist", out); 335 } 336 337 /** Print a report of this histogram. 338 */ 339 public 340 void print(String name, PrintStream out) { 341 print(name, getRowTitles(name), out); 342 } 343 344 /** Print a report of this histogram. 345 */ 346 public 347 void print(String name, String[] histTitles, PrintStream out) { 348 int totalUnique = getTotalLength(); 349 int ltotalWeight = getTotalWeight(); 350 double tlen = getBitLength(); 351 double avgLen = tlen / ltotalWeight; 352 double avg = (double) ltotalWeight / totalUnique; 353 String title = (name 354 +" len="+round(tlen,10) 355 +" avgLen="+round(avgLen,10) 356 +" weight("+ltotalWeight+")" 357 +" unique["+totalUnique+"]" 358 +" avgWeight("+round(avg,100)+")"); 359 if (histTitles == null) { 360 out.println(title); 361 } else { 362 out.println(title+" {"); 363 StringBuffer buf = new StringBuffer(); 364 for (int i = 0; i < matrix.length; i++) { 365 buf.setLength(0); 366 buf.append(" ").append(histTitles[i]).append(" {"); 367 for (int j = 1; j < matrix[i].length; j++) { 368 buf.append(" ").append(matrix[i][j]); 369 } 370 buf.append(" }"); 371 out.println(buf); 372 } 373 out.println("}"); 374 } 375 } 376 377/* 378 public static 379 int[][] makeHistogramMatrix(int[] values) { 380 // Make sure they are sorted. 381 values = maybeSort(values); 382 long[] hist2col = computeHistogram2Col(values); 383 int[][] matrix = makeMatrix(hist2col); 384 return matrix; 385 } 386*/ 387 388 private static 389 int[][] makeMatrix(long[] hist2col) { 390 // Sort by increasing count, then by increasing value. 391 Arrays.sort(hist2col); 392 int[] counts = new int[hist2col.length]; 393 for (int i = 0; i < counts.length; i++) { 394 counts[i] = (int)( hist2col[i] >>> 32 ); 395 } 396 long[] countHist = computeHistogram2Col(counts); 397 int[][] matrix = new int[countHist.length][]; 398 int histp = 0; // cursor into hist2col (increasing count, value) 399 int countp = 0; // cursor into countHist (increasing count) 400 // Do a join between hist2col (resorted) and countHist. 401 for (int i = matrix.length; --i >= 0; ) { 402 long countAndRep = countHist[countp++]; 403 int count = (int) (countAndRep); // what is the value count? 404 int repeat = (int) (countAndRep >>> 32); // # times repeated? 405 int[] row = new int[1+repeat]; 406 row[0] = count; 407 for (int j = 0; j < repeat; j++) { 408 long countAndValue = hist2col[histp++]; 409 assert(countAndValue >>> 32 == count); 410 row[1+j] = (int) countAndValue; 411 } 412 matrix[i] = row; 413 } 414 assert(histp == hist2col.length); 415 return matrix; 416 } 417 418 private static 419 int[][] makeTable(long[] hist2col) { 420 int[][] table = new int[2][hist2col.length]; 421 // Break apart the entries in hist2col. 422 // table[0] gets values, table[1] gets entries. 423 for (int i = 0; i < hist2col.length; i++) { 424 table[0][i] = (int)( hist2col[i] ); 425 table[1][i] = (int)( hist2col[i] >>> 32 ); 426 } 427 return table; 428 } 429 430 /** Simple two-column histogram. Contains repeated counts. 431 * Assumes input is sorted. Does not sort output columns. 432 * <p> 433 * Format of result: 434 * <pre> 435 * long[] hist = { 436 * (count1 << 32) | (value1), 437 * (count2 << 32) | (value2), 438 * ... 439 * } 440 * </pre> 441 * In addition, the sequence {valuei...} is guaranteed to be sorted. 442 * Note that resorting this using Arrays.sort() will reorder the 443 * entries by increasing count. 444 */ 445 private static 446 long[] computeHistogram2Col(int[] sortedValues) { 447 switch (sortedValues.length) { 448 case 0: 449 return new long[]{ }; 450 case 1: 451 return new long[]{ ((long)1 << 32) | (LOW32 & sortedValues[0]) }; 452 } 453 long[] hist = null; 454 for (boolean sizeOnly = true; ; sizeOnly = false) { 455 int prevIndex = -1; 456 int prevValue = sortedValues[0] ^ -1; // force a difference 457 int prevCount = 0; 458 for (int i = 0; i <= sortedValues.length; i++) { 459 int thisValue; 460 if (i < sortedValues.length) 461 thisValue = sortedValues[i]; 462 else 463 thisValue = prevValue ^ -1; // force a difference at end 464 if (thisValue == prevValue) { 465 prevCount += 1; 466 } else { 467 // Found a new value. 468 if (!sizeOnly && prevCount != 0) { 469 // Save away previous value. 470 hist[prevIndex] = ((long)prevCount << 32) 471 | (LOW32 & prevValue); 472 } 473 prevValue = thisValue; 474 prevCount = 1; 475 prevIndex += 1; 476 } 477 } 478 if (sizeOnly) { 479 // Finished the sizing pass. Allocate the histogram. 480 hist = new long[prevIndex]; 481 } else { 482 break; // done 483 } 484 } 485 return hist; 486 } 487 488 /** Regroup the histogram, so that it becomes an approximate histogram 489 * whose rows are of the given lengths. 490 * If matrix rows must be split, the latter parts (larger values) 491 * are placed earlier in the new matrix. 492 * If matrix rows are joined, they are resorted into ascending order. 493 * In the new histogram, the counts are averaged over row entries. 494 */ 495 private static 496 int[][] regroupHistogram(int[][] matrix, int[] groups) { 497 long oldEntries = 0; 498 for (int i = 0; i < matrix.length; i++) { 499 oldEntries += matrix[i].length-1; 500 } 501 long newEntries = 0; 502 for (int ni = 0; ni < groups.length; ni++) { 503 newEntries += groups[ni]; 504 } 505 if (newEntries > oldEntries) { 506 int newlen = groups.length; 507 long ok = oldEntries; 508 for (int ni = 0; ni < groups.length; ni++) { 509 if (ok < groups[ni]) { 510 int[] newGroups = new int[ni+1]; 511 System.arraycopy(groups, 0, newGroups, 0, ni+1); 512 groups = newGroups; 513 groups[ni] = (int) ok; 514 ok = 0; 515 break; 516 } 517 ok -= groups[ni]; 518 } 519 } else { 520 long excess = oldEntries - newEntries; 521 int[] newGroups = new int[groups.length+1]; 522 System.arraycopy(groups, 0, newGroups, 0, groups.length); 523 newGroups[groups.length] = (int) excess; 524 groups = newGroups; 525 } 526 int[][] newMatrix = new int[groups.length][]; 527 // Fill pointers. 528 int i = 0; // into matrix 529 int jMin = 1; 530 int jMax = matrix[i].length; 531 for (int ni = 0; ni < groups.length; ni++) { 532 int groupLength = groups[ni]; 533 int[] group = new int[1+groupLength]; 534 long groupWeight = 0; // count of all in new group 535 newMatrix[ni] = group; 536 int njFill = 1; 537 while (njFill < group.length) { 538 int len = group.length - njFill; 539 while (jMin == jMax) { 540 jMin = 1; 541 jMax = matrix[++i].length; 542 } 543 if (len > jMax - jMin) len = jMax - jMin; 544 groupWeight += (long) matrix[i][0] * len; 545 System.arraycopy(matrix[i], jMax - len, group, njFill, len); 546 jMax -= len; 547 njFill += len; 548 } 549 Arrays.sort(group, 1, group.length); 550 // compute average count of new group: 551 group[0] = (int) ((groupWeight + groupLength/2) / groupLength); 552 } 553 assert(jMin == jMax); 554 assert(i == matrix.length-1); 555 return newMatrix; 556 } 557 558 public static 559 Histogram makeByteHistogram(InputStream bytes) throws IOException { 560 byte[] buf = new byte[1<<12]; 561 int[] tally = new int[1<<8]; 562 for (int nr; (nr = bytes.read(buf)) > 0; ) { 563 for (int i = 0; i < nr; i++) { 564 tally[buf[i] & 0xFF] += 1; 565 } 566 } 567 // Build a matrix. 568 int[][] matrix = new int[1<<8][2]; 569 for (int i = 0; i < tally.length; i++) { 570 matrix[i][0] = tally[i]; 571 matrix[i][1] = i; 572 } 573 return new Histogram(matrix); 574 } 575 576 /** Slice and sort the given input array. */ 577 private static 578 int[] sortedSlice(int[] valueSequence, int start, int end) { 579 if (start == 0 && end == valueSequence.length && 580 isSorted(valueSequence, 0, false)) { 581 return valueSequence; 582 } else { 583 int[] slice = new int[end-start]; 584 System.arraycopy(valueSequence, start, slice, 0, slice.length); 585 Arrays.sort(slice); 586 return slice; 587 } 588 } 589 590 /** Tell if an array is sorted. */ 591 private static 592 boolean isSorted(int[] values, int from, boolean strict) { 593 for (int i = from+1; i < values.length; i++) { 594 if (strict ? !(values[i-1] < values[i]) 595 : !(values[i-1] <= values[i])) { 596 return false; // found witness to disorder 597 } 598 } 599 return true; // no witness => sorted 600 } 601 602 /** Clone and sort the array, if not already sorted. */ 603 private static 604 int[] maybeSort(int[] values) { 605 if (!isSorted(values, 0, false)) { 606 values = values.clone(); 607 Arrays.sort(values); 608 } 609 return values; 610 } 611 612 613 /// Debug stuff follows. 614 615 private boolean assertWellFormed(int[] valueSequence) { 616/* 617 // Sanity check. 618 int weight = 0; 619 int vlength = 0; 620 for (int i = 0; i < matrix.length; i++) { 621 int vlengthi = (matrix[i].length-1); 622 int count = matrix[i][0]; 623 assert(vlengthi > 0); // no empty rows 624 assert(count > 0); // no impossible rows 625 vlength += vlengthi; 626 weight += count * vlengthi; 627 } 628 assert(isSorted(values, 0, true)); 629 // make sure the counts all add up 630 assert(totalWeight == weight); 631 assert(vlength == values.length); 632 assert(vlength == counts.length); 633 int weight2 = 0; 634 for (int i = 0; i < counts.length; i++) { 635 weight2 += counts[i]; 636 } 637 assert(weight2 == weight); 638 int[] revcol1 = new int[matrix.length]; //1st matrix colunm 639 for (int i = 0; i < matrix.length; i++) { 640 // spot checking: try a random query on each matrix row 641 assert(matrix[i].length > 1); 642 revcol1[matrix.length-i-1] = matrix[i][0]; 643 assert(isSorted(matrix[i], 1, true)); 644 int rand = (matrix[i].length+1) / 2; 645 int val = matrix[i][rand]; 646 int count = matrix[i][0]; 647 int pos = Arrays.binarySearch(values, val); 648 assert(values[pos] == val); 649 assert(counts[pos] == matrix[i][0]); 650 if (valueSequence != null) { 651 int count2 = 0; 652 for (int j = 0; j < valueSequence.length; j++) { 653 if (valueSequence[j] == val) count2++; 654 } 655 assert(count2 == count); 656 } 657 } 658 assert(isSorted(revcol1, 0, true)); 659//*/ 660 return true; 661 } 662 663/* 664 public static 665 int[] readValuesFrom(InputStream instr) { 666 return readValuesFrom(new InputStreamReader(instr)); 667 } 668 public static 669 int[] readValuesFrom(Reader inrdr) { 670 inrdr = new BufferedReader(inrdr); 671 final StreamTokenizer in = new StreamTokenizer(inrdr); 672 final int TT_NOTHING = -99; 673 in.commentChar('#'); 674 return readValuesFrom(new Iterator() { 675 int token = TT_NOTHING; 676 private int getToken() { 677 if (token == TT_NOTHING) { 678 try { 679 token = in.nextToken(); 680 assert(token != TT_NOTHING); 681 } catch (IOException ee) { 682 throw new RuntimeException(ee); 683 } 684 } 685 return token; 686 } 687 public boolean hasNext() { 688 return getToken() != StreamTokenizer.TT_EOF; 689 } 690 public Object next() { 691 int ntok = getToken(); 692 token = TT_NOTHING; 693 switch (ntok) { 694 case StreamTokenizer.TT_EOF: 695 throw new NoSuchElementException(); 696 case StreamTokenizer.TT_NUMBER: 697 return new Integer((int) in.nval); 698 default: 699 assert(false); 700 return null; 701 } 702 } 703 public void remove() { 704 throw new UnsupportedOperationException(); 705 } 706 }); 707 } 708 public static 709 int[] readValuesFrom(Iterator iter) { 710 return readValuesFrom(iter, 0); 711 } 712 public static 713 int[] readValuesFrom(Iterator iter, int initSize) { 714 int[] na = new int[Math.max(10, initSize)]; 715 int np = 0; 716 while (iter.hasNext()) { 717 Integer val = (Integer) iter.next(); 718 if (np == na.length) { 719 int[] na2 = new int[np*2]; 720 System.arraycopy(na, 0, na2, 0, np); 721 na = na2; 722 } 723 na[np++] = val.intValue(); 724 } 725 if (np != na.length) { 726 int[] na2 = new int[np]; 727 System.arraycopy(na, 0, na2, 0, np); 728 na = na2; 729 } 730 return na; 731 } 732 733 public static 734 Histogram makeByteHistogram(byte[] bytes) { 735 try { 736 return makeByteHistogram(new ByteArrayInputStream(bytes)); 737 } catch (IOException ee) { 738 throw new RuntimeException(ee); 739 } 740 } 741 742 public static 743 void main(String[] av) throws IOException { 744 if (av.length > 0 && av[0].equals("-r")) { 745 int[] values = new int[Integer.parseInt(av[1])]; 746 int limit = values.length; 747 if (av.length >= 3) { 748 limit = (int)( limit * Double.parseDouble(av[2]) ); 749 } 750 Random rnd = new Random(); 751 for (int i = 0; i < values.length; i++) { 752 values[i] = rnd.nextInt(limit);; 753 } 754 Histogram rh = new Histogram(values); 755 rh.print("random", System.out); 756 return; 757 } 758 if (av.length > 0 && av[0].equals("-s")) { 759 int[] values = readValuesFrom(System.in); 760 Random rnd = new Random(); 761 for (int i = values.length; --i > 0; ) { 762 int j = rnd.nextInt(i+1); 763 if (j < i) { 764 int tem = values[i]; 765 values[i] = values[j]; 766 values[j] = tem; 767 } 768 } 769 for (int i = 0; i < values.length; i++) 770 System.out.println(values[i]); 771 return; 772 } 773 if (av.length > 0 && av[0].equals("-e")) { 774 // edge cases 775 new Histogram(new int[][] { 776 {1, 11, 111}, 777 {0, 123, 456}, 778 {1, 111, 1111}, 779 {0, 456, 123}, 780 {3}, 781 {}, 782 {3}, 783 {2, 22}, 784 {4} 785 }).print(System.out); 786 return; 787 } 788 if (av.length > 0 && av[0].equals("-b")) { 789 // edge cases 790 Histogram bh = makeByteHistogram(System.in); 791 bh.print("bytes", System.out); 792 return; 793 } 794 boolean regroup = false; 795 if (av.length > 0 && av[0].equals("-g")) { 796 regroup = true; 797 } 798 799 int[] values = readValuesFrom(System.in); 800 Histogram h = new Histogram(values); 801 if (!regroup) 802 h.print(System.out); 803 if (regroup) { 804 int[] groups = new int[12]; 805 for (int i = 0; i < groups.length; i++) { 806 groups[i] = 1<<i; 807 } 808 int[][] gm = regroupHistogram(h.getMatrix(), groups); 809 Histogram g = new Histogram(gm); 810 System.out.println("h.getBitLength(g) = "+ 811 h.getBitLength(g.getBitMetric())); 812 System.out.println("g.getBitLength(h) = "+ 813 g.getBitLength(h.getBitMetric())); 814 g.print("regrouped", System.out); 815 } 816 } 817//*/ 818} 819