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