Coverage details for edu.uci.ics.jung.statistics.Histogram

LineHitsSource
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      */
414    private boolean growthAllowed = false;
42     /**
43      * Flag to enforce integer bin width.
44      */
454    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      */
634    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() {
780        this(100);
790    }
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) {
890        this(from, to, 50);
900    }
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      */
992    public Histogram(double from, double to, int bins) {
1002        defineParameters(from, to, bins);
1012    }
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) {
1110        this(n, 50);
1120    }
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)
1242            throws IllegalArgumentException {
1252        if (width <= 0)
1260            throw new IllegalArgumentException(
127                     "Non-positive bin width: " + width);
1282        contents = new int[n];
1292        minimum = min;
1302        binWidth = width;
1312        reset();
1322    }
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      */
1410    public Histogram(int n, int m) {
1420        cached = true;
1430        cache = new double[n];
1440        underflow = 0;
1450        overflow = m;
1460    }
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) {
1530        for (int i=0; i<list.size(); i++) {
1540            fill(list.get(i));
155         }
1560    }
157  
158     /**
159      * Fills with a random variable.
160      * @param x value of the random variable.
161      */
162     public void fill(double x) {
1631012        if (cached) {
1640            cache[underflow++] = x;
1650            if (underflow == cache.length)
1660                flushCache();
1671012        } else if (x < minimum) {
1680            if (growthAllowed) {
1690                expandDown(x);
1700                moments.accumulate(x);
171             } else
1720                underflow++;
173         } else {
1741012            int index = binIndex(x);
1751012            if (index < contents.length) {
1761010                contents[index]++;
1771010                moments.accumulate(x);
1782            } else if (growthAllowed) {
1790                expandUp(x);
1800                moments.accumulate(x);
181             } else
1822                overflow++;
183         }
184         //values.add(x);
1851012    }
186  
187     /**
188      * Returns the average of the values accumulated in the histogram bins.
189      * @return average.
190      */
191     public double average() {
1922        if (cached)
1930            flushCache();
1942        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) {
2021026        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() {
2100        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 {
2242        if (from >= to)
2250            throw new IllegalArgumentException(
226                     "Inverted range: minimum = " + from + ", maximum = " + to);
2272        if (bins < 1)
2280            throw new IllegalArgumentException(
229                     "Non-positive number of bins: " + bins);
2302        binWidth = NumericalPrecision.roundToScale((to - from) / bins,
231                 integerBinWidth);
2322        minimum = binWidth * Math.floor(from / binWidth);
2332        int numberOfBins = (int) Math.ceil((to - minimum) / binWidth);
2342        if (minimum + numberOfBins * binWidth <= to)
2351            numberOfBins++;
2362        contents = new int[numberOfBins];
237         //values = new DoubleArrayList();
2382        cached = false;
2392        cache = null;
2402        reset();
2412    }
242  
243     /**
244      * Returns the error on average. May throw divide by zero exception.
245      * @return error on average.
246      */
247     public double errorOnAverage() {
2480        if (cached)
2490            flushCache();
2500        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) {
2590        int addSize = (int) Math.ceil((minimum - x) / binWidth);
2600        int newContents[] = new int[addSize + contents.length];
2610        minimum -= addSize * binWidth;
262         int n;
2630        newContents[0] = 1;
2640        for (n = 1; n < addSize; n++)
2650            newContents[n] = 0;
2660        for (n = 0; n < contents.length; n++)
2670            newContents[n + addSize] = contents[n];
2680        contents = newContents;
2690    }
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) {
2770        int newSize = (int) Math.ceil((x - minimum) / binWidth);
2780        int newContents[] = new int[newSize];
279         int n;
2800        for (n = 0; n < contents.length; n++)
2810            newContents[n] = contents[n];
2820        for (n = contents.length; n < newSize - 1; n++)
2830            newContents[n] = 0;
2840        newContents[n] = 1;
2850        contents = newContents;
2860    }
287  
288     /**
289      * Flush the values from the cache.
290      */
291     private void flushCache() {
2920        double min = cache[0];
2930        double max = min;
2940        int cacheSize = underflow;
2950        double[] cachedValues = cache;
296         int n;
2970        for (n = 1; n < cacheSize; n++) {
2980            if (cache[n] < min)
2990                min = cache[n];
3000            else if (cache[n] > max)
3010                max = cache[n];
302         }
3030        defineParameters(min, max, overflow);
3040        for (n = 0; n < cacheSize; n++)
3050            fill(cachedValues[n]);
3060    }
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) {
31414        if (x < minimum)
3150            return Double.NaN;
31614        int n = binIndex(x);
31714        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) {
3280        if (x >= minimum) {
3290            int index = (int) Math.floor((x - minimum) / binWidth);
3300            if (index < contents.length) {
3310                double[] answer = new double[3];
3320                answer[0] = minimum + index * binWidth;
3330                answer[1] = answer[0] + binWidth;
3340                answer[2] = contents[index];
3350                return answer;
336             }
337         }
3380        return null;
339     }
340  
341     /**
342      * Returns the bin width.
343      * @return bin width.
344      */
345     public double getBinWidth() {
3460        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) {
3550        int n = binIndex(x);
3560        int m = binIndex(y);
3570        double sum = contents[n] * ((minimum - x) / binWidth - (n + 1))
358                 + contents[m] * ((y - minimum) / binWidth - m);
3590        while (++n < m)
3600            sum += contents[n];
3610        return sum;
362     }
363  
364     /**
365      * @return double integrated count up to x
366      * @param x double
367      */
368     public double getCountsUpTo(double x) {
3690        int n = binIndex(x);
3700        double sum = contents[n] * ((x - minimum) / binWidth - n)
371                 + underflow;
3720        for (int i = 0; i < n; i++)
3730            sum += contents[i];
3740        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() {
3830        if (cached)
3840            flushCache();
3850        return contents.length;
386     }
387  
388     public int getNumBins() {
3890        if (cached)
3900            flushCache();
3910        return contents.length;
392     }
393  
394     /**
395      * @return double
396      */
397     public double getMaximum() {
3980        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() {
4060        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() {
4180        if (cached)
4190            flushCache();
4200        double[] range = new double[4];
4210        range[0] = minimum;
4220        range[1] = getMaximum();
4230        range[2] = 0;
4240        range[3] = 0;
4250        for (int n = 0; n < contents.length; n++)
4260            range[3] = Math.max(range[3], contents[n]);
4270        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() {
4370        if (cached)
4380            flushCache();
4390        return moments.kurtosis();
440     }
441  
442     /**
443      * @return FixedStatisticalMoments
444      */
445     protected StatisticalMoments moments() {
4460        return moments;
447     }
448  
449     /**
450      * Returns the number of counts accumulated below the lowest bin.
451      * @return overflow.
452      */
453     public long overflow() {
4540        return cached ? 0 : overflow;
455     }
456  
457     /**
458      * Reset histogram.
459      */
460     public void reset() {
4614        if (moments == null)
4624            moments = new StatisticalMoments();
463         else
4640            moments.reset();
4654        underflow = 0;
4664        overflow = 0;
46751        for (int n = 0; n < contents.length; n++)
46847            contents[n] = 0;
4694    }
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 {
4800        if (underflow != 0 || overflow != 0) {
4810            if (!cached)
4820                throw new RuntimeException(
483                         "Cannot allow growth to a non-empty histogram");
484         }
4850        growthAllowed = true;
4860    }
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 {
4950        if (!cached)
4960            throw new RuntimeException(
497                     "Cannot change bin width of a non-empty histogram");
4980        integerBinWidth = true;
4990    }
500  
501     /**
502      * Returns the number of points in the series.
503      */
504     public int size() {
5051        if (cached)
5060            flushCache();
5071        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() {
5150        if (cached)
5160            flushCache();
5170        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() {
5250        if (cached)
5260            flushCache();
5270        return moments.standardDeviation();
528     }
529  
530     /**
531      * @return long
532      */
533     public long totalCount() {
5340        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() {
5430        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() {
5510        if (cached)
5520            flushCache();
5530        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) {
5620        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) {
57114        if (cached)
5720            flushCache();
57314        return (index >= 0 && index < contents.length) ? (double) contents[index] : 0;
574     }
575 }

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.