Line | Hits | Source |
---|---|---|
1 | /* | |
2 | * Copyright (c) 2003, the JUNG Project and the Regents of the University | |
3 | * of California | |
4 | * All rights reserved. | |
5 | * | |
6 | * This software is open-source under the BSD license; see either | |
7 | * "license.txt" or | |
8 | * http://jung.sourceforge.net/license.txt for a description. | |
9 | */ | |
10 | package edu.uci.ics.jung.statistics; | |
11 | ||
12 | import cern.colt.list.DoubleArrayList; | |
13 | import edu.uci.ics.jung.utils.NumericalPrecision; | |
14 | ||
15 | /** | |
16 | * General-purpose class for representing experimental distributions via a histogram. | |
17 | * A histogram is primarily characterized by three things: <br> | |
18 | * 1) the minimum value in the data, minX <br> | |
19 | * 2) the bin width, w<br> | |
20 | * 3) the number of bins, n <br> * | |
21 | * The ith bin represents the interval [minX + (i-1)w, minX + i*w]. Each bin contains the | |
22 | * number of times a value in the original data set falls within its corresponding interval | |
23 | * @author Didier H. Besset (modified by Scott White) | |
24 | */ | |
25 | public class Histogram { | |
26 | /** | |
27 | * Lower limit of first histogram bin. | |
28 | */ | |
29 | private double minimum; | |
30 | /** | |
31 | * Width of a bin. | |
32 | */ | |
33 | private double binWidth; | |
34 | /** | |
35 | * Histogram contents. | |
36 | */ | |
37 | private int[] contents; | |
38 | /** | |
39 | * Flag to allow automatical growth. | |
40 | */ | |
41 | 4 | private boolean growthAllowed = false; |
42 | /** | |
43 | * Flag to enforce integer bin width. | |
44 | */ | |
45 | 4 | private boolean integerBinWidth = false; |
46 | /** | |
47 | * Counts of values located below first bin. | |
48 | * Note: also used to count cached values when caching is in effect. | |
49 | */ | |
50 | private int underflow; | |
51 | /** | |
52 | * Counts of values located above last bin. | |
53 | * Note: also used to hold desired number of bins when caching is in effect. | |
54 | */ | |
55 | private int overflow; | |
56 | /** | |
57 | * Statistical moments of values accumulated within the histogram limits. | |
58 | */ | |
59 | private StatisticalMoments moments; | |
60 | /** | |
61 | * Flag indicating the histogram is caching values to compute adequate range. | |
62 | */ | |
63 | 4 | private boolean cached = false; |
64 | /** | |
65 | * Cache for accumulated values. | |
66 | */ | |
67 | private double cache[]; | |
68 | ||
69 | //private DoubleArrayList values; | |
70 | ||
71 | ||
72 | /** | |
73 | * Constructor method with unknown limits and a desired number | |
74 | * of 50 bins. The first 100 accumulated values are cached. | |
75 | * Then, a suitable range is computed. | |
76 | */ | |
77 | public Histogram() { | |
78 | 0 | this(100); |
79 | 0 | } |
80 | ||
81 | /** | |
82 | * Constructor method for approximate range for a desired number | |
83 | * of 50 bins. | |
84 | * All parameters are adjusted so that the bin width is a round number. | |
85 | * @param from approximate lower limit of first histogram bin. | |
86 | * @param to approximate upper limit of last histogram bin. | |
87 | */ | |
88 | public Histogram(double from, double to) { | |
89 | 0 | this(from, to, 50); |
90 | 0 | } |
91 | ||
92 | /** | |
93 | * Constructor method for approximate range and desired number of bins. | |
94 | * All parameters are adjusted so that the bin width is a round number. | |
95 | * @param from approximate lower limit of first histogram bin. | |
96 | * @param to approximate upper limit of last histogram bin. | |
97 | * @param bins desired number of bins. | |
98 | */ | |
99 | 2 | public Histogram(double from, double to, int bins) { |
100 | 2 | defineParameters(from, to, bins); |
101 | 2 | } |
102 | ||
103 | /** | |
104 | * Constructor method with unknown limits and a desired number of | |
105 | * 50 bins. | |
106 | * Accumulated values are first cached. When the cache is full, | |
107 | * a suitable range is computed. | |
108 | * @param n size of cache. | |
109 | */ | |
110 | public Histogram(int n) { | |
111 | 0 | this(n, 50); |
112 | 0 | } |
113 | ||
114 | /** | |
115 | * General constructor method. | |
116 | * @param n number of bins. | |
117 | * @param min lower limit of first histogram bin. | |
118 | * @param width bin width (must be positive). | |
119 | * @exception java.lang.IllegalArgumentException | |
120 | * if the number of bins is non-positive, | |
121 | * if the limits are inversed. | |
122 | */ | |
123 | public Histogram(int n, double min, double width) | |
124 | 2 | throws IllegalArgumentException { |
125 | 2 | if (width <= 0) |
126 | 0 | throw new IllegalArgumentException( |
127 | "Non-positive bin width: " + width); | |
128 | 2 | contents = new int[n]; |
129 | 2 | minimum = min; |
130 | 2 | binWidth = width; |
131 | 2 | reset(); |
132 | 2 | } |
133 | ||
134 | /** | |
135 | * Constructor method with unknown limits. | |
136 | * Accumulated values are first cached. When the cache is full, | |
137 | * a suitable range is computed. | |
138 | * @param n size of cache. | |
139 | * @param m desired number of bins | |
140 | */ | |
141 | 0 | public Histogram(int n, int m) { |
142 | 0 | cached = true; |
143 | 0 | cache = new double[n]; |
144 | 0 | underflow = 0; |
145 | 0 | overflow = m; |
146 | 0 | } |
147 | ||
148 | /** | |
149 | * Fills the histogram with the list of random values | |
150 | * @param list a list of double values | |
151 | */ | |
152 | public void fill(DoubleArrayList list) { | |
153 | 0 | for (int i=0; i<list.size(); i++) { |
154 | 0 | fill(list.get(i)); |
155 | } | |
156 | 0 | } |
157 | ||
158 | /** | |
159 | * Fills with a random variable. | |
160 | * @param x value of the random variable. | |
161 | */ | |
162 | public void fill(double x) { | |
163 | 1012 | if (cached) { |
164 | 0 | cache[underflow++] = x; |
165 | 0 | if (underflow == cache.length) |
166 | 0 | flushCache(); |
167 | 1012 | } else if (x < minimum) { |
168 | 0 | if (growthAllowed) { |
169 | 0 | expandDown(x); |
170 | 0 | moments.accumulate(x); |
171 | } else | |
172 | 0 | underflow++; |
173 | } else { | |
174 | 1012 | int index = binIndex(x); |
175 | 1012 | if (index < contents.length) { |
176 | 1010 | contents[index]++; |
177 | 1010 | moments.accumulate(x); |
178 | 2 | } else if (growthAllowed) { |
179 | 0 | expandUp(x); |
180 | 0 | moments.accumulate(x); |
181 | } else | |
182 | 2 | overflow++; |
183 | } | |
184 | //values.add(x); | |
185 | 1012 | } |
186 | ||
187 | /** | |
188 | * Returns the average of the values accumulated in the histogram bins. | |
189 | * @return average. | |
190 | */ | |
191 | public double average() { | |
192 | 2 | if (cached) |
193 | 0 | flushCache(); |
194 | 2 | return moments.average(); |
195 | } | |
196 | ||
197 | /** | |
198 | * @return int index of the bin where x is located | |
199 | * @param x double | |
200 | */ | |
201 | public int binIndex(double x) { | |
202 | 1026 | return (int) Math.floor((x - minimum) / binWidth); |
203 | } | |
204 | ||
205 | /** | |
206 | * Returns the number of accumulated counts. | |
207 | * @return number of counts. | |
208 | */ | |
209 | public long count() { | |
210 | 0 | return cached ? underflow : moments.count(); |
211 | } | |
212 | ||
213 | /** | |
214 | * Compute suitable limits and bin width. | |
215 | * @param from approximate lower limit of first histogram bin. | |
216 | * @param to approximate upper limit of last histogram bin. | |
217 | * @param bins desired number of bins. | |
218 | * @exception java.lang.IllegalArgumentException | |
219 | * if the number of bins is non-positive, | |
220 | * if the limits are inversed. | |
221 | */ | |
222 | private void defineParameters(double from, double to, int bins) | |
223 | throws IllegalArgumentException { | |
224 | 2 | if (from >= to) |
225 | 0 | throw new IllegalArgumentException( |
226 | "Inverted range: minimum = " + from + ", maximum = " + to); | |
227 | 2 | if (bins < 1) |
228 | 0 | throw new IllegalArgumentException( |
229 | "Non-positive number of bins: " + bins); | |
230 | 2 | binWidth = NumericalPrecision.roundToScale((to - from) / bins, |
231 | integerBinWidth); | |
232 | 2 | minimum = binWidth * Math.floor(from / binWidth); |
233 | 2 | int numberOfBins = (int) Math.ceil((to - minimum) / binWidth); |
234 | 2 | if (minimum + numberOfBins * binWidth <= to) |
235 | 1 | numberOfBins++; |
236 | 2 | contents = new int[numberOfBins]; |
237 | //values = new DoubleArrayList(); | |
238 | 2 | cached = false; |
239 | 2 | cache = null; |
240 | 2 | reset(); |
241 | 2 | } |
242 | ||
243 | /** | |
244 | * Returns the error on average. May throw divide by zero exception. | |
245 | * @return error on average. | |
246 | */ | |
247 | public double errorOnAverage() { | |
248 | 0 | if (cached) |
249 | 0 | flushCache(); |
250 | 0 | return moments.errorOnAverage(); |
251 | } | |
252 | ||
253 | /** | |
254 | * Expand the contents so that the lowest bin include the specified | |
255 | * value. | |
256 | * @param x value to be included. | |
257 | */ | |
258 | private void expandDown(double x) { | |
259 | 0 | int addSize = (int) Math.ceil((minimum - x) / binWidth); |
260 | 0 | int newContents[] = new int[addSize + contents.length]; |
261 | 0 | minimum -= addSize * binWidth; |
262 | int n; | |
263 | 0 | newContents[0] = 1; |
264 | 0 | for (n = 1; n < addSize; n++) |
265 | 0 | newContents[n] = 0; |
266 | 0 | for (n = 0; n < contents.length; n++) |
267 | 0 | newContents[n + addSize] = contents[n]; |
268 | 0 | contents = newContents; |
269 | 0 | } |
270 | ||
271 | /** | |
272 | * Expand the contents so that the highest bin include the specified | |
273 | * value. | |
274 | * @param x value to be included. | |
275 | */ | |
276 | private void expandUp(double x) { | |
277 | 0 | int newSize = (int) Math.ceil((x - minimum) / binWidth); |
278 | 0 | int newContents[] = new int[newSize]; |
279 | int n; | |
280 | 0 | for (n = 0; n < contents.length; n++) |
281 | 0 | newContents[n] = contents[n]; |
282 | 0 | for (n = contents.length; n < newSize - 1; n++) |
283 | 0 | newContents[n] = 0; |
284 | 0 | newContents[n] = 1; |
285 | 0 | contents = newContents; |
286 | 0 | } |
287 | ||
288 | /** | |
289 | * Flush the values from the cache. | |
290 | */ | |
291 | private void flushCache() { | |
292 | 0 | double min = cache[0]; |
293 | 0 | double max = min; |
294 | 0 | int cacheSize = underflow; |
295 | 0 | double[] cachedValues = cache; |
296 | int n; | |
297 | 0 | for (n = 1; n < cacheSize; n++) { |
298 | 0 | if (cache[n] < min) |
299 | 0 | min = cache[n]; |
300 | 0 | else if (cache[n] > max) |
301 | 0 | max = cache[n]; |
302 | } | |
303 | 0 | defineParameters(min, max, overflow); |
304 | 0 | for (n = 0; n < cacheSize; n++) |
305 | 0 | fill(cachedValues[n]); |
306 | 0 | } |
307 | ||
308 | /** | |
309 | * retrieves the bin given a random value and returns the corresponding height of the bin | |
310 | * @param x the random value | |
311 | * @return total height of the corresponding bin | |
312 | */ | |
313 | public double binHeight(double x) { | |
314 | 14 | if (x < minimum) |
315 | 0 | return Double.NaN; |
316 | 14 | int n = binIndex(x); |
317 | 14 | return n < contents.length ? yValueAt(n) : Double.NaN; |
318 | } | |
319 | ||
320 | /** | |
321 | * Returns the low and high limits and the content of the bin | |
322 | * containing the specified number or nul if the specified number | |
323 | * lies outside of the histogram limits. | |
324 | * @return a 3-dimensional array containing the bin limits and | |
325 | * the bin content. | |
326 | */ | |
327 | public double[] getBinParameters(double x) { | |
328 | 0 | if (x >= minimum) { |
329 | 0 | int index = (int) Math.floor((x - minimum) / binWidth); |
330 | 0 | if (index < contents.length) { |
331 | 0 | double[] answer = new double[3]; |
332 | 0 | answer[0] = minimum + index * binWidth; |
333 | 0 | answer[1] = answer[0] + binWidth; |
334 | 0 | answer[2] = contents[index]; |
335 | 0 | return answer; |
336 | } | |
337 | } | |
338 | 0 | return null; |
339 | } | |
340 | ||
341 | /** | |
342 | * Returns the bin width. | |
343 | * @return bin width. | |
344 | */ | |
345 | public double getBinWidth() { | |
346 | 0 | return binWidth; |
347 | } | |
348 | ||
349 | /** | |
350 | * @return double | |
351 | * @param x double | |
352 | * @param y double | |
353 | */ | |
354 | public double getCountsBetween(double x, double y) { | |
355 | 0 | int n = binIndex(x); |
356 | 0 | int m = binIndex(y); |
357 | 0 | double sum = contents[n] * ((minimum - x) / binWidth - (n + 1)) |
358 | + contents[m] * ((y - minimum) / binWidth - m); | |
359 | 0 | while (++n < m) |
360 | 0 | sum += contents[n]; |
361 | 0 | return sum; |
362 | } | |
363 | ||
364 | /** | |
365 | * @return double integrated count up to x | |
366 | * @param x double | |
367 | */ | |
368 | public double getCountsUpTo(double x) { | |
369 | 0 | int n = binIndex(x); |
370 | 0 | double sum = contents[n] * ((x - minimum) / binWidth - n) |
371 | + underflow; | |
372 | 0 | for (int i = 0; i < n; i++) |
373 | 0 | sum += contents[i]; |
374 | 0 | return sum; |
375 | } | |
376 | ||
377 | /** | |
378 | * Returns the number of bins of the histogram. | |
379 | * @return number of bins. | |
380 | * @deprecated use getNumBins | |
381 | */ | |
382 | public double getDimension() { | |
383 | 0 | if (cached) |
384 | 0 | flushCache(); |
385 | 0 | return contents.length; |
386 | } | |
387 | ||
388 | public int getNumBins() { | |
389 | 0 | if (cached) |
390 | 0 | flushCache(); |
391 | 0 | return contents.length; |
392 | } | |
393 | ||
394 | /** | |
395 | * @return double | |
396 | */ | |
397 | public double getMaximum() { | |
398 | 0 | return minimum + (contents.length - 1) * binWidth; |
399 | } | |
400 | ||
401 | /** | |
402 | * Returns the lower bin limit of the first bin. | |
403 | * @return minimum histogram range. | |
404 | */ | |
405 | public double getMinimum() { | |
406 | 0 | return minimum; |
407 | } | |
408 | ||
409 | /** | |
410 | * Returns the range of values to be plotted. | |
411 | * @return An array of 4 double values as follows | |
412 | * index 0: minimum of X range | |
413 | * 1: maximum of X range | |
414 | * 2: minimum of Y range | |
415 | * 3: maximum of Y range | |
416 | */ | |
417 | public double[] getRange() { | |
418 | 0 | if (cached) |
419 | 0 | flushCache(); |
420 | 0 | double[] range = new double[4]; |
421 | 0 | range[0] = minimum; |
422 | 0 | range[1] = getMaximum(); |
423 | 0 | range[2] = 0; |
424 | 0 | range[3] = 0; |
425 | 0 | for (int n = 0; n < contents.length; n++) |
426 | 0 | range[3] = Math.max(range[3], contents[n]); |
427 | 0 | return range; |
428 | } | |
429 | ||
430 | /** | |
431 | * Returns the kurtosis of the values accumulated in the histogram bins. | |
432 | * The kurtosis measures the sharpness of the distribution near the maximum. | |
433 | * Note: The kurtosis of the Normal distribution is 0 by definition. | |
434 | * @return double kurtosis. | |
435 | */ | |
436 | public double kurtosis() { | |
437 | 0 | if (cached) |
438 | 0 | flushCache(); |
439 | 0 | return moments.kurtosis(); |
440 | } | |
441 | ||
442 | /** | |
443 | * @return FixedStatisticalMoments | |
444 | */ | |
445 | protected StatisticalMoments moments() { | |
446 | 0 | return moments; |
447 | } | |
448 | ||
449 | /** | |
450 | * Returns the number of counts accumulated below the lowest bin. | |
451 | * @return overflow. | |
452 | */ | |
453 | public long overflow() { | |
454 | 0 | return cached ? 0 : overflow; |
455 | } | |
456 | ||
457 | /** | |
458 | * Reset histogram. | |
459 | */ | |
460 | public void reset() { | |
461 | 4 | if (moments == null) |
462 | 4 | moments = new StatisticalMoments(); |
463 | else | |
464 | 0 | moments.reset(); |
465 | 4 | underflow = 0; |
466 | 4 | overflow = 0; |
467 | 51 | for (int n = 0; n < contents.length; n++) |
468 | 47 | contents[n] = 0; |
469 | 4 | } |
470 | ||
471 | /** | |
472 | * Allows histogram contents to grow in order to contain all | |
473 | * accumulated values. | |
474 | * Note: Should not be called after counts have been accumulated in | |
475 | * the underflow and/or overflow of the histogram. | |
476 | * @exception java.lang.RuntimeException | |
477 | * if the histogram has some contents. | |
478 | */ | |
479 | public void setGrowthAllowed() throws RuntimeException { | |
480 | 0 | if (underflow != 0 || overflow != 0) { |
481 | 0 | if (!cached) |
482 | 0 | throw new RuntimeException( |
483 | "Cannot allow growth to a non-empty histogram"); | |
484 | } | |
485 | 0 | growthAllowed = true; |
486 | 0 | } |
487 | ||
488 | /** | |
489 | * Forces the bin width of the histogram to be integer. | |
490 | * Note: Can only be called when the histogram is cached. | |
491 | * @exception java.lang.RuntimeException | |
492 | * if the histogram has some contents. | |
493 | */ | |
494 | public void setIntegerBinWidth() throws RuntimeException { | |
495 | 0 | if (!cached) |
496 | 0 | throw new RuntimeException( |
497 | "Cannot change bin width of a non-empty histogram"); | |
498 | 0 | integerBinWidth = true; |
499 | 0 | } |
500 | ||
501 | /** | |
502 | * Returns the number of points in the series. | |
503 | */ | |
504 | public int size() { | |
505 | 1 | if (cached) |
506 | 0 | flushCache(); |
507 | 1 | return contents.length; |
508 | } | |
509 | ||
510 | /** | |
511 | * Returns the skewness of the values accumulated in the histogram bins. | |
512 | * @return double skewness. | |
513 | */ | |
514 | public double skewness() { | |
515 | 0 | if (cached) |
516 | 0 | flushCache(); |
517 | 0 | return moments.skewness(); |
518 | } | |
519 | ||
520 | /** | |
521 | * Returns the standard deviation of the values accumulated in the histogram bins. | |
522 | * @return double standard deviation. | |
523 | */ | |
524 | public double standardDeviation() { | |
525 | 0 | if (cached) |
526 | 0 | flushCache(); |
527 | 0 | return moments.standardDeviation(); |
528 | } | |
529 | ||
530 | /** | |
531 | * @return long | |
532 | */ | |
533 | public long totalCount() { | |
534 | 0 | return cached ? underflow |
535 | : moments.count() + overflow + underflow; | |
536 | } | |
537 | ||
538 | /** | |
539 | * Returns the number of counts accumulated below the lowest bin. | |
540 | * @return underflow. | |
541 | */ | |
542 | public long underflow() { | |
543 | 0 | return cached ? 0 : underflow; |
544 | } | |
545 | ||
546 | /** | |
547 | * Returns the variance of the values accumulated in the histogram bins. | |
548 | * @return double variance. | |
549 | */ | |
550 | public double variance() { | |
551 | 0 | if (cached) |
552 | 0 | flushCache(); |
553 | 0 | return moments.variance(); |
554 | } | |
555 | ||
556 | /** | |
557 | * Returns the end of the bin at the specified index. | |
558 | * @param index the index of the bin. | |
559 | * @return middle of bin | |
560 | */ | |
561 | public double xValueAt(int index) { | |
562 | 0 | return (index) * binWidth + minimum; |
563 | } | |
564 | ||
565 | /** | |
566 | * Returns the content of the bin at the given index. | |
567 | * @param index the index of the bin. | |
568 | * @return bin content | |
569 | */ | |
570 | public double yValueAt(int index) { | |
571 | 14 | if (cached) |
572 | 0 | flushCache(); |
573 | 14 | return (index >= 0 && index < contents.length) ? (double) contents[index] : 0; |
574 | } | |
575 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |