1 /*
   2  * Copyright (c) 2003, 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 
  26 package com.sun.java.util.jar.pack;
  27 
  28 import java.io.IOException;
  29 import java.io.InputStream;
  30 import java.io.PrintStream;
  31 import java.util.Arrays;
  32 
  33 /**
  34  * Histogram derived from an integer array of events (int[]).
  35  * @author John Rose
  36  */
  37 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     static private
 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 totalWeight = 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 + totalWeight/2) / totalWeight;
 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 totalWeight = getTotalWeight();
 350         double tlen = getBitLength();
 351         double avgLen = tlen / totalWeight;
 352         double avg = (double) totalWeight / totalUnique;
 353         String title = (name
 354                         +" len="+round(tlen,10)
 355                         +" avgLen="+round(avgLen,10)
 356                         +" weight("+totalWeight+")"
 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("  "+histTitles[i]+" {");
 367                 for (int j = 1; j < matrix[i].length; j++) {
 368                     buf.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 = (int[]) 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 }
--- EOF ---