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