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 
17 #ifndef LOG_PLOT_H
18 #define LOG_PLOT_H
19 
20 #include <algorithm>
21 #include <cmath>
22 #include <iomanip>      // setw
23 #include <iostream>
24 #include <map>
25 #include <sstream>
26 #include <string>
27 
28 // TODO Make a class called LogPlot and put this functionality in it.
29 // Actually maybe this file can be called AsciiPlot or something...
30 /**
31  * \brief Creates a std::string graph representation of equally-spaced time-series data points.
32  *
33  * \param first     RandomAccessIterator iterator to initial position of sequence.
34  *                  Iterator shall point to a pair<float, bool>, where the float is the data value
35  *                  and the bool is whether the data value is the start of a new data point in time
36  *                  (i.e. a break in time continuity).
37  * \param last      RandomAccessIterator iterator to final position of sequence.
38  * \return the std::string of the graph.
39  *
40  */
41 template <class RandomAccessIterator>
audio_utils_log_plot(RandomAccessIterator first,RandomAccessIterator last)42 std::string audio_utils_log_plot(RandomAccessIterator first, RandomAccessIterator last)
43 {
44     using T = decltype((*first).first);
45 
46     constexpr int HEIGHT = 14;                    // Character height of the plot
47     // Leave 20% display space before min and after max data points
48     constexpr float RANGE_BUFFER_ROOM = 0.2f;
49     // Minimum range of lowest and highest y-axis value to display
50     constexpr int RANGE_MIN = 14;
51     constexpr unsigned int WIDTH_MAX = 200U;      // Max character width of plot
52     const size_t size = last - first;
53 
54     if (size <= 0) {
55         return "";
56     }
57 
58     // Find min and max element in the vector.
59     const auto result = std::minmax_element(first, last);
60     const T minVal = (*result.first).first;
61     const T maxVal = (*result.second).first;
62 
63     const T range = maxVal - minVal;
64     T graphMin, graphMax;
65     if (range < RANGE_MIN) {
66         T avg = (maxVal + minVal) / 2;
67         graphMin = avg - RANGE_MIN / 2;
68         graphMax = avg + RANGE_MIN / 2;
69     } else {
70         graphMin = minVal - range * RANGE_BUFFER_ROOM;
71         graphMax = maxVal + range * RANGE_BUFFER_ROOM;
72     }
73 
74     // Value of one character height increase on the graph
75     const T increment = (graphMax - graphMin) / HEIGHT;
76     // Something went wrong if we reached this statement..
77     if (increment <= 0.0f) {
78         return "";
79     }
80 
81     std::stringstream ss;
82     ss << std::fixed << std::setprecision(1);
83 
84     // Start storing the graph into string.
85     // TODO store everything into a preallocated string rather than use stringstream.
86     // This may make the code easier to maintain.
87     ss << "\n";
88     for (int height = HEIGHT - 1; height >= 0; height--) {
89         int spaces = 1;     // Amount of spaces before the data point
90         ss << std::setw(9) << graphMin + increment * height;
91         ss << std::setw(3) << "-|";
92         auto it = size <= WIDTH_MAX ? first : first + size - WIDTH_MAX;
93         for (; it < last; ++it) {
94             const T power = it->first;
95             const bool start = it->second;
96             // TODO explicitly do type conversion for parameter passed to round()?
97             int px = (int)round((power - graphMin) / increment);
98             // The it != last - 1 is a temporary workaround to prevent vertical bar
99             // separators after the last data point entry.
100             if ((start || px == height) && it != last - 1) {
101                 ss << std::setw(spaces) << (start ? "|" : "*");
102                 spaces = 1;
103             } else {
104                 spaces++;
105             }
106         }
107         ss << "\n";
108     }
109     ss << std::setw(12) << "|";
110     ss << std::string(std::min(size - (size_t)1, (size_t)WIDTH_MAX), '_') << "\n\n";
111 
112     return ss.str();
113 }
114 
115 // determines how many character spaces an integer takes up.
widthOf(int x)116 inline int widthOf(int x) {
117     int width = 0;
118     if (x < 0) {
119         ++width;
120         x = x == INT_MIN ? INT_MAX : -x;
121     }
122     // assert (x >= 0)
123     do {
124         ++width;
125         x /= 10;
126     } while (x > 0);
127     return width;
128 }
129 
130 // computes the column width required for a specific histogram value
numberWidth(double number,int leftPadding)131 inline int numberWidth(double number, int leftPadding) {
132     // Added values account for whitespaces needed around numbers, and for the
133     // dot and decimal digit not accounted for by widthOf
134     return std::max(std::max(widthOf(static_cast<int>(number)) + 3, 2), leftPadding + 1);
135 }
136 
137 // TODO Make this templated and add comments.
138 inline std::string audio_utils_plot_histogram(const std::map<double, int> &buckets,
139         const char *title = "", const char *label = "", int maxHeight = 10)
140 {
141     if (buckets.empty()) {
142         return "";
143     }
144 
145     auto it = buckets.begin();
146     double maxDelta = it->first;
147     int maxCount = it->second;
148     // Compute maximum values
149     while (++it != buckets.end()) {
150         if (it->first > maxDelta) {
151             maxDelta = it->first;
152         }
153         if (it->second > maxCount) {
154             maxCount = it->second;
155         }
156     }
157     int height = log2(maxCount) + 1; // maxCount > 0, safe to call log2
158     const int leftPadding = widthOf(1 << height);
159     const int bucketWidth = numberWidth(maxDelta, leftPadding);
160     int scalingFactor = 1;
161     // scale data if it exceeds maximum height
162     if (height > maxHeight) {
163         scalingFactor = (height + maxHeight) / maxHeight;
164         height /= scalingFactor;
165     }
166     std::stringstream ss;
167     ss << title << "\n " << std::setw(leftPadding) << " ";
168     // write histogram label line with bucket values
169     for (auto const &x : buckets) {
170         const int colWidth = numberWidth(x.first, leftPadding);
171         ss << std::setw(colWidth) << x.second;
172     }
173     // write histogram ascii art
174     // underscores and spaces length corresponds to maximum width of histogram
175     constexpr int kLen = 200;
176     static const std::string underscores(kLen, '_');
177     static const std::string spaces(kLen, ' ');
178     auto getTail = [](const size_t n, const std::string &s) {
179         return s.c_str() + s.size() - std::min(n, s.size());
180     };
181 
182     ss << "\n ";
183     for (int row = height * scalingFactor; row >= 0; row -= scalingFactor) {
184         // TODO explain how value is derived from log2 and why it doesn't overflow.
185         const int value = 1 << row;
186         ss << getTail(leftPadding, spaces);
187         for (auto const &x : buckets) {
188             const int colWidth = numberWidth(x.first, leftPadding);
189             ss << getTail(colWidth - 1, spaces) <<
190                 (x.second < value ? " " : "|");
191         }
192         ss << "\n ";
193     }
194     // print x-axis
195     const int columns = static_cast<int>(buckets.size());
196     ss << std::setw(leftPadding) << " "
197         << getTail((columns + 1) * bucketWidth, underscores) << "\n ";
198 
199     // write footer with bucket labels
200     ss << std::setw(leftPadding) << " ";
201     for (auto const &x : buckets) {
202         const int colWidth = numberWidth(x.first, leftPadding);
203         ss << std::setw(colWidth) << std::fixed << std::setprecision(1) << x.first;
204     }
205     ss << getTail(bucketWidth, spaces) << label << "\n";
206 
207     return ss.str();
208 }
209 
210 #endif // !LOG_PLOT_H
211