1 /*
2  * Copyright (C) 2019 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 
17 #ifndef AUDIO_UTILS_HISTOGRAM_H
18 #define AUDIO_UTILS_HISTOGRAM_H
19 
20 #include <memory>
21 #include <sstream>
22 #include <vector>
23 
24 namespace android::audio_utils {
25 
26 class Histogram {
27 public:
Histogram(int32_t numBinsInRange,int32_t binWidth)28     Histogram(int32_t numBinsInRange, int32_t binWidth)
29     : mBinWidth(binWidth)
30     , mBins(numBinsInRange + kExtraBins)
31     , mLastItemNumbers(mBins.size())
32     {
33     }
34 
35     /**
36      * Add another item to the histogram.
37      * The value will be divided by the binWidth to determine the bin index.
38      * @param value
39      */
add(int32_t value)40     void add(int32_t value) {
41         int32_t binIndex = (value + mBinWidth) / mBinWidth;
42         binIndex = std::max(binIndex, 0); // put values below range in bottom bin
43         binIndex = std::min(binIndex, (int32_t)mBins.size() - 1);
44                                           // put values below range in top bin
45         mBins[binIndex]++;
46         mLastItemNumbers[binIndex] = mItemCount++;
47     }
48 
49     /**
50      * Reset all counters to zero.
51      */
clear()52     void clear() {
53         std::fill(mBins.begin(), mBins.end(), 0);
54         std::fill(mLastItemNumbers.begin(), mLastItemNumbers.end(), 0);
55         mItemCount = 0;
56     }
57 
58     /**
59      * @return original number of bins passed to the constructor
60      */
getNumBinsInRange()61     int32_t getNumBinsInRange() const {
62         return mBins.size() - kExtraBins;
63     }
64 
65     /**
66      * @return number of items below the lowest bin
67      */
getCountBelowRange()68     uint64_t getCountBelowRange() const {
69         return mBins[0];
70     }
71 
72     /**
73      * @param binIndex between 0 and numBins-1
74      * @return number of items for the given bin index
75      */
getCount(int32_t binIndex)76     uint64_t getCount(int32_t binIndex) const {
77         if (binIndex < 0 || binIndex >= getNumBinsInRange()) {
78             return 0;
79         }
80         return mBins[binIndex + 1];
81     }
82 
83     /**
84      * @return total number of items added
85      */
getCount()86     uint64_t getCount() const {
87         return mItemCount;
88     }
89 
90     /**
91      * This can be used to determine whether outlying bins were incremented
92      * early or late in the process.
93      * @param binIndex between 0 and numBins-1
94      * @return number of the last item added to this bin
95      */
getLastItemNumber(int32_t binIndex)96     uint64_t getLastItemNumber(int32_t binIndex) const {
97         if (binIndex < 0 || binIndex >= getNumBinsInRange()) {
98             return 0;
99         }
100         return mLastItemNumbers[binIndex + 1];
101     }
102 
103     /**
104      * @return number of items above the highest bin
105      */
getCountAboveRange()106     uint64_t getCountAboveRange() const {
107         return mBins[mBins.size() - 1];
108     }
109 
110     /**
111      * Dump the bins in CSV format, which can be easily imported into a spreadsheet.
112      * @return string bins in CSV format
113      */
dump()114     std::string dump() const {
115         std::stringstream result;
116         uint64_t count = getCountBelowRange();
117         if (count > 0) {
118             result << "below range = " << count << std::endl;
119         }
120         result << "index, start, count, last" << std::endl;
121         for (size_t i = 1; i < mBins.size() - 1; i++) {
122             if (mBins[i] > 0) {
123                 size_t properIndex = i - 1;
124                 result << properIndex;
125                 result << ", "<< (properIndex * mBinWidth);
126                 result << ", " << mBins[i];
127                 result << ", " << mLastItemNumbers[i];
128                 result << std::endl;
129             }
130         }
131         count = getCountAboveRange();
132         if (count > 0) {
133             result << "above range = " << count << std::endl;
134         }
135         return result.str();
136     }
137 
138 private:
139     static constexpr int kExtraBins = 2; // for out of range values
140     const int32_t mBinWidth;
141     int64_t mItemCount = 0;
142     std::vector<uint64_t> mBins;  // count of the number of items in the range of this bin
143     std::vector<uint64_t> mLastItemNumbers; // number of the last item added this bin
144 };
145 
146 } // namespace
147 #endif //AUDIO_UTILS_HISTOGRAM_H
148