1 /*
2  * Copyright (C) 2018 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package com.android.game.qualification.metric;
17 
18 import com.android.annotations.VisibleForTesting;
19 
20 import com.google.common.collect.ImmutableSet;
21 
22 import java.io.IOException;
23 import java.io.OutputStream;
24 import java.nio.charset.StandardCharsets;
25 import java.util.Collection;
26 import java.util.Collections;
27 import java.util.Map;
28 import java.util.Set;
29 import java.util.SortedMap;
30 import java.util.TreeMap;
31 
32 import javax.annotation.Nullable;
33 
34 /**
35  * Create a histogram from a set of data.
36  */
37 public class Histogram {
38     private Long mBucketSize;
39     private SortedMap<Long, Integer> mCounts = new TreeMap<>(); // need sorted keys for plotting.
40     @Nullable private Long mMinCutoff;
41     @Nullable private Long mMaxCutoff;
42 
43     /**
44      * Create a Histogram
45      *
46      * @param data data to be graphed.
47      * @param bucketSize Size of each bucket.  The first bucket will have a range of
48      *                  [-bucketSize / 2, bucketSize/2).
49      * @param minCutoff All data value < minCutoff will be categorize into the same bucket.
50      * @param maxCutoff All data value > maxCutoff will be categorize into the same bucket.
51      */
Histogram( Collection<Long> data, Long bucketSize, @Nullable Long minCutoff, @Nullable Long maxCutoff)52     public Histogram(
53             Collection<Long> data,
54             Long bucketSize,
55             @Nullable Long minCutoff,
56             @Nullable Long maxCutoff) {
57         mBucketSize = bucketSize;
58         mMinCutoff = minCutoff;
59         mMaxCutoff = maxCutoff;
60 
61         for (Long value : data) {
62             long bucket = findBucket(value);
63             mCounts.put(bucket, mCounts.getOrDefault(bucket, 0) + 1);
64         }
65 
66         // Add some buckets for padding to clarify the range of value represented by each bar of the
67         // histogram.
68         Set<Long> keys = ImmutableSet.copyOf(mCounts.keySet());
69         for (long bucket : keys) {
70             if (bucket == Long.MIN_VALUE) {
71                 mCounts.putIfAbsent(mMinCutoff, 0);
72             } else if (mMaxCutoff != null && bucket > mMaxCutoff - bucketSize){
73                 mCounts.putIfAbsent(Long.MAX_VALUE, 0);
74             } else {
75                 mCounts.putIfAbsent(bucket + bucketSize, 0);
76             }
77         }
78     }
79 
80     @VisibleForTesting
getCounts()81     SortedMap<Long, Integer> getCounts() {
82         return mCounts;
83     }
84 
85     /**
86      * Plot the histogram as text.
87      *
88      * Use '=' to represent the count of each bucket.
89      *
90      * @param output OutputStream to print the histogram to.
91      * @param maxBarLength Maximum number of '=' to be printed for each bar.  If a bucket contains
92      *                     a larger count than maxBarLength, all the other bars are scaled
93      *                     accordingly.
94      */
plotAscii(OutputStream output, int maxBarLength)95     public void plotAscii(OutputStream output, int maxBarLength) throws IOException {
96         if (mCounts.isEmpty()) {
97             return;
98         }
99         int maxCount = 0;
100         int total = 0;
101         for (int count : mCounts.values()) {
102             if (count > maxCount) {
103                 maxCount = count;
104             }
105             total += count;
106         }
107         int cumulative = 0;
108         int maxKeyLength =
109                 (int) Math.log10(
110                         mCounts.lastKey() == Long.MAX_VALUE ? mMaxCutoff : mCounts.lastKey()) + 1;
111         for (Map.Entry<Long, Integer> entry : mCounts.entrySet()) {
112             cumulative += entry.getValue();
113             long key = entry.getKey();
114             if (mMinCutoff != null && Long.MIN_VALUE == key) {
115                 output.write("<".getBytes(StandardCharsets.UTF_8));
116                 key = mMinCutoff;
117             } else if (mMaxCutoff != null && Long.MAX_VALUE == key) {
118                 output.write(">".getBytes(StandardCharsets.UTF_8));
119                 key = mMaxCutoff;
120             } else {
121                 output.write(" ".getBytes(StandardCharsets.UTF_8));
122             }
123             float percentage = entry.getValue() * 100f / total;
124             int barLength =
125                     (maxCount > maxBarLength)
126                             ? (entry.getValue() * maxBarLength + maxCount - 1) / maxCount
127                             : entry.getValue();
128             String bar = String.join("", Collections.nCopies(barLength, "="));
129             output.write(
130                     String.format(
131                             "%" + maxKeyLength + "d| %-" + maxBarLength + "s (%d = %.1f%%) {%.1f%%}\n",
132                             key,
133                             bar,
134                             entry.getValue(),
135                             percentage,
136                             cumulative * 100f / total) .getBytes());
137         }
138     }
139 
140     // Returns the lowest value of the bucket for the specified value.
findBucket(Long value)141     private Long findBucket(Long value) {
142         if (mMinCutoff != null && value < mMinCutoff) {
143             return Long.MIN_VALUE;
144         }
145         if (mMaxCutoff != null && value > mMaxCutoff) {
146             return Long.MAX_VALUE;
147         }
148         long index = (value + mBucketSize / 2) / mBucketSize;
149         return mBucketSize * index - mBucketSize / 2;
150     }
151 }
152