StatisticsHelper.java
/*
** Module : StatisticsHelper.java
** Abstract : provides a set of useful helper methods to calculate statistics
**
** Copyright (c) 2005-2022, Golden Code Development Corporation.
**
** -#- -I- --Date-- --JPRM-- ----------------Description-----------------
** 001 ECF 20050722 @21819 Created initial version. Analyzes data
** distributions to calculate max, min, median,
** mean, and standard deviation.
** 002 ECF 20050727 @21892 Added loadDistributions and population
** methods. The former loads a map of
** distribution data from an XML document. The
** latter accumulates the total population of a
** distribution.
** 003 GES 20090515 @42236 Import change.
** 004 GES 20130206 Moved to pattern package and turned into a worker.
** 005 TJD 20220504 Java 11 compatibility minor changes
*/
/*
** This program is free software: you can redistribute it and/or modify
** it under the terms of the GNU Affero General Public License as
** published by the Free Software Foundation, either version 3 of the
** License, or (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU Affero General Public License for more details.
**
** You may find a copy of the GNU Affero GPL version 3 at the following
** location: https://www.gnu.org/licenses/agpl-3.0.en.html
**
** Additional terms under GNU Affero GPL version 3 section 7:
**
** Under Section 7 of the GNU Affero GPL version 3, the following additional
** terms apply to the works covered under the License. These additional terms
** are non-permissive additional terms allowed under Section 7 of the GNU
** Affero GPL version 3 and may not be removed by you.
**
** 0. Attribution Requirement.
**
** You must preserve all legal notices or author attributions in the covered
** work or Appropriate Legal Notices displayed by works containing the covered
** work. You may not remove from the covered work any author or developer
** credit already included within the covered work.
**
** 1. No License To Use Trademarks.
**
** This license does not grant any license or rights to use the trademarks
** Golden Code, FWD, any Golden Code or FWD logo, or any other trademarks
** of Golden Code Development Corporation. You are not authorized to use the
** name Golden Code, FWD, or the names of any author or contributor, for
** publicity purposes without written authorization.
**
** 2. No Misrepresentation of Affiliation.
**
** You may not represent yourself as Golden Code Development Corporation or FWD.
**
** You may not represent yourself for publicity purposes as associated with
** Golden Code Development Corporation, FWD, or any author or contributor to
** the covered work, without written authorization.
**
** 3. No Misrepresentation of Source or Origin.
**
** You may not represent the covered work as solely your work. All modified
** versions of the covered work must be marked in a reasonable way to make it
** clear that the modified work is not originating from Golden Code Development
** Corporation or FWD. All modified versions must contain the notices of
** attribution required in this license.
*/
package com.goldencode.p2j.pattern;
import java.lang.reflect.*;
import java.util.*;
import org.w3c.dom.*;
import com.goldencode.ast.*;
import com.goldencode.util.*;
/**
* Provides a set of methods to calculate statistical values based upon the data provided.
*/
public class StatisticsHelper
extends AbstractPatternWorker
{
/** XML tag name for distribution element */
private static final String ELEM_DISTRIBUTION = "distribution";
/** XML tag name for bucket element */
private static final String ELEM_BUCKET = "bucket";
/** XML name for name attribute */
private static final String ATTR_NAME = "name";
/** XML name for type attribute */
private static final String ATTR_TYPE = "type";
/** XML name for class attribute */
private static final String ATTR_CLASS = "class";
/** XML name for value attribute */
private static final String ATTR_VALUE = "value";
/** XML name for count attribute */
private static final String ATTR_COUNT = "count";
/**
* Default constructor which calls the super-class constructor, registers
* its libraries and initializes its instance members.
*/
public StatisticsHelper()
throws AstException
{
super();
setLibrary(new Library());
}
/**
* Provides a service for calculating statistics. This class is a <code>PatternEngine</code>
* worker library.
*/
public class Library
{
/**
* Locate the maximum value of a distribution, where the map's keys are
* the data values and the map's values are the corresponding numbers of
* occurrences of these data values in the distribution. The map's keys
* must implement <code>Comparable</code>.
*
* @param distrib
* Map of data values to numbers of occurrences. For purposes of
* this algorithm, the map's values are ignored; only the keys
* are of interest.
*
* @return The distribution's maximum value, as determined by the
* natural order of the keys.
*/
public Object maximum(Map distrib)
{
return Collections.max(distrib.keySet());
}
/**
* Locate the minimum value of a distribution, where the map's keys are
* the data values and the map's values are the corresponding numbers of
* occurrences of these data values in the distribution. The map's keys
* must implement <code>Comparable</code>.
*
* @param distrib
* Map of data values to numbers of occurrences. For purposes of
* this algorithm, the map's values are ignored; only the keys
* are of interest.
*
* @return The distribution's minimum value, as determined by the
* natural order of the keys.
*/
public Object minimum(Map distrib)
{
return Collections.min(distrib.keySet());
}
/**
* Calculate the total population size of a distribution.
*
* @param distrib
* Map of data values to numbers of occurrences (i.e., population
* for each data value). For purposes of this algorithm, the
* map's keys are ignored; only the values are of interest.
*
* @return Cumulative population of all distribution buckets.
*/
public long population(Map distrib)
{
long pop = 0L;
Iterator iter = distrib.values().iterator();
while (iter.hasNext())
{
pop += ((Number) iter.next()).longValue();
}
return pop;
}
/**
* Calculate the median value of a distribution, where the map's keys are
* the data values and the map's values are the corresponding numbers of
* occurrences of these data values in the distribution. The map's keys
* must be instances of <code>Number</code>, since a numeric result is
* generated.
* <p>
* To locate the median, we sort the values in the distribution in
* ascending order, then determine which bucket in the distribution
* contains the middle-ranked value. For distributions with an odd total
* population, this number represents the median. For an even total
* population, the two middle-ranked values are averaged to produce the
* median.
*
* @param distrib
* Map of data values to numbers of occurrences.
*
* @return The median numeric value.
*
* @throws ClassCastException
* if a non-numeric key is encountered in <code>distrib</code>.
*/
public double median(Map distrib)
{
long n = 0L;
SortedSet sorted = new TreeSet(distrib.keySet());
SortedMap cumulative = new TreeMap();
Iterator iter = sorted.iterator();
while (iter.hasNext())
{
Number value = (Number) iter.next();
Number weight = (Number) distrib.get(value);
n += weight.longValue();
cumulative.put(Long.valueOf(n), value);
}
// If an odd number of occurrences, take the middle value; if an even
// number, take the average of the two middle values.
double median = getValueAtRank(cumulative, n / 2).doubleValue();
if (n % 2 == 1)
{
double median2 = getValueAtRank(cumulative, n / 2 + 1).doubleValue();
median = (median + median2) / 2;
}
return median;
}
/**
* Calculate the <i>weighted</i> average value of the <code>Number</code>s
* represented by the keys of the specified map. The average is weighted
* by the number of occurrences contained in the value of each bucket of
* the distribution.
*
* @param distrib
* Distribution buckets; mapping of numeric values to the number
* of occurrences for each. The keys of this map must each be an
* instance of <code>Number</code>
*
* @return Weighted average of <code>distrib</code>'s numeric keys.
*
* @throws ClassCastException
* if a non-numeric key is encountered in <code>distrib</code>.
*/
public double mean(Map distrib)
{
double total = 0.0;
long n = 0L;
Iterator iter = distrib.keySet().iterator();
while (iter.hasNext())
{
Number value = (Number) iter.next();
int weight = ((Number) distrib.get(value)).intValue();
total += value.doubleValue() * weight;
n += weight;
}
return (n == 0L ? 0L : (total / n));
}
/**
* Calculate the standard deviation of the given distribution using the
* "sum of the squares" algorithm.
*
* @param distrib
* Distribution buckets; mapping of numeric values to the number
* of occurrences for each. The keys of this map must each be an
* instance of <code>Number</code>
*
* @return Standard deviation of the distribution.
*
* @throws ClassCastException
* if a non-numeric key is encountered in <code>distrib</code>.
*/
public double standardDeviation(Map distrib)
{
double mean = mean(distrib);
double total = 0.0;
long n = 0L;
Iterator iter = distrib.keySet().iterator();
while (iter.hasNext())
{
Number value = (Number) iter.next();
int weight = ((Number) distrib.get(value)).intValue();
n += weight;
total += (Math.pow(value.doubleValue() - mean, 2) * weight);
}
return (n == 0L ? 1.0 : Math.sqrt(total / n));
}
/**
* Given an XML filename and a distribution type, load statistics from
* an XML document and produce a map of all distributions of that type.
* The map's keys are the distribution names; its values are the
* distributions themselves.
* <p>
* Each distribution is represented as a <code>SortedMap</code>, where
* each map key represents a "bucket" value, and each map value
* represents the the number of occurrences of that value in the
* distribution.
*
* @param filename
* Name of the file containing the XML document to be read.
* @param type
* Type of distribution to collect; this corresponds with the
* "type" attribute of the "distribution" element within the
* XML document.
*
* @return An unmodifiable map of unmodifiable distribution maps.
*
* @throws RuntimeException
* if any error occurs loading the distribution data from the
* specified XML file.
*/
public Map loadDistributions(String filename, String type)
{
Map distMap = new HashMap();
try
{
Element root = XmlHelper.parse(filename).getDocumentElement();
NodeList dists = root.getElementsByTagName(ELEM_DISTRIBUTION);
// Loop through all distribution elements; ignore those that do not
// match our type.
int len = dists.getLength();
for (int i = 0; i < len; i++)
{
// Get next element and reject if not required type.
Element dist = (Element) dists.item(i);
if (!type.equals(dist.getAttribute(ATTR_TYPE)))
{
continue;
}
// Get constructor which will be used to instantiate our values;
// must accept a single string argument.
Class cls = Class.forName(dist.getAttribute(ATTR_CLASS));
Class[] parmTypes = { String.class };
Constructor ctor = cls.getConstructor(parmTypes);
// Create bucket map.
SortedMap bucketMap = new TreeMap();
// Retrieve all the buckets for this distribution; insert each
// into our distribution map.
NodeList buckets = dist.getElementsByTagName(ELEM_BUCKET);
int size = buckets.getLength();
for (int j = 0; j < size; j++)
{
Element bucket = (Element) buckets.item(j);
String value = bucket.getAttribute(ATTR_VALUE);
String count = bucket.getAttribute(ATTR_COUNT);
// Populate bucket map.
Object[] parms = { value };
bucketMap.put(ctor.newInstance(parms), Long.valueOf(count));
}
// Add unmodifiable view of bucket map to distribution.
distMap.put(dist.getAttribute(ATTR_NAME),
Collections.unmodifiableMap(bucketMap));
}
}
catch (Exception exc)
{
throw new RuntimeException(
"Error loading distribution map from " + filename, exc);
}
return Collections.unmodifiableMap(distMap);
}
/**
* Given a sorted map of cumulative numbers of occurrences (ranks) to
* numeric data values, return the number associated with a specific rank.
* The map's structure defines ranges of ranks, where one key defines the
* low end of the range, and the next key in an iteration defines the high
* end of the range.
*
* @param rankMap
* A sorted map whose keys represent the highest rank for a given
* data value, when a distribution is sorted in ascending order
* by data value. The map's values represent the data values at
* each rank.
* @param rank
* Target rank.
*
* @return The numeric value associated with the target rank.
*/
private Number getValueAtRank(SortedMap rankMap, long rank)
{
Iterator iter = rankMap.keySet().iterator();
while (iter.hasNext())
{
Number rankCap = (Number) iter.next();
if (rankCap.longValue() >= rank)
{
return (Number) rankMap.get(rankCap);
}
}
return null;
}
}
}