# 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;
          }
       }
    }