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
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 }