text: package com.aricneto.twistytimer.stats;
  
  import android.util.Log;
  
  import com.aricneto.twistytimer.items.AverageComponent;
  import com.aricneto.twistytimer.utils.PuzzleUtils;
  import com.aricneto.twistytimer.utils.StatUtils;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collections;
  import java.util.List;
  
  /**
   * Calculates the average time of a number of puzzle solves. Running averages are easily calculated
   * as each new solve is added. If the number of solve times is five or greater, the best and worst
   * times are discarded before returning the truncated arithmetic mean (aka "trimmed mean" or
   * "modified mean) of the remaining times. All times and averages are in milliseconds. The mean,
   * minimum (best) and maximum (worst) of all added times, and the best average from all values of
   * the running average are also made available.
   *
   * @author damo
   */
  public final class AverageCalculator {
      // NOTE: This implementation is reasonably efficient, as it can calculate an average without
      // iterating over the array of recorded times. Iteration is only required when the known best
      // or worst values are ejected to make room for new times. Storing times in sorted order would
      // reduce this explicit iteration, but a second data structure would be required to record the
      // insertion order and the insertion operations would be more costly, as the sort order would
      // need to be maintained.
      //
      // Discarding only the single best and single worst values is standard for average-of-5
      // calculations, but for higher values of "n", it might be better to exclude, say, the best 10%
      // and worst 10%. However, that would make the implementation significantly more complicated if
      // arrays of best and worst values (or the limits of the ranges of each set of values and the
      // sums of those sets) were to be maintained. One approach might be to support calculation of
      // the median value instead, which would be relatively simple to do: sort the times, eliminate
      // the allowed DNFs and then find the time value in the middle position of the remaining times
      // in their sorted order (or the mean of the two middle values, if there are an even number of
      // remaining times).
      //
      // There are several alternative "streaming" algorithms that would not require the times to
      // be stored. However, all of those would introduce some amount of error due to rounding or
      // precision errors. As the largest value of "n" is likely to be 1,000, the approach used here
      // should be good enough and not use memory excessively.
  
      /**
       * A special time value that represents a solve that "did-not-finish" (DNF). This is also used
       * to represent the calculated value of an average where too many solves included in the
       * average were DNF solves.
       */
      // Deliberately avoiding using "PuzzleUtils.TIME_DNF" as the canonical flag value, as there is
      // no guarantee that it will remain with its current value of "-1" and this class needs to be
      // sure that the value will be negative and will not clash with "UNKNOWN". If changing these,
      // use values that can also be represented as in "int".
      public static final long DNF = Integer.MAX_VALUE;
  
      /**
       * A value that indicates that a calculated time is unknown. This is usually the case when not
       * enough times have been recorded to satisfy the required number of solves to be included in
       * the calculation of the average, or when all recorded solves are {@link #DNF}s.
       */
      public static final long UNKNOWN = -666L;
  
      /**
       * The minimum number of times to include in the average before a single DNF will not result
       * in disqualification.
       */
      private static final int MIN_N_TO_ALLOW_ONE_DNF = 5;
  
      /**
       * The number of solve times to include in the average.
       */
      private final int mN;
  
      /**
       * Indicates if averages should be reported as {@link #DNF}s if too many solve times are DNFs.
       * The number of DNFs that constitute "too many" varies with the value of {@link #mN}.
       */
      private final boolean mDisqualifyDNFs;
  
      /**
       * The array holding the most recently added solve times. A solve time can also be recorded as
       * a {@link #DNF}. This is managed as a circular queue. Once full, the oldest added time is
       * overwritten when the next new time is added.
       */
      private final long[] mTimes;
  
      // TODO: comment these variables
      public AverageComponent mUpperTrim;
      public AverageComponent mMiddleTrim;
      public AverageComponent mLowerTrim;
      private int mLowerTrimBound;
      private int mUpperTrimBound;
      private int mTrimSize;
  
      /**
       * The index in {@link #mTimes} at which to add the next time. If this is equal to the length
       * of the array, it will be wrapped back to zero.
       */
      private int mNext;
  
      /**
       * The total number of solve times that have been added to the array. This may exceed
       * {@link #mN}, but no more than that number of solve times will be stored at any one time.
       */
      private int mNumSolves;
  
      /**
       * The number of DNF results currently recorded in {@code #mTimes}.
       */
      private int mNumCurrentDNFs;
  
      /**
       * The maximum number of DNFs that can be contained in {@link #mTimes}
       * before the whole average is considered a DNF
       */
      private int mNumAcceptableDNFs;
  
      /**
       * The number of DNF results ever recorded in {@code #mTimes}.
       */
      private int mNumAllTimeDNFs;
  
  
      /**
       * The Welford algorithm for variance is one of the most well-known and used online methods of
       * calculating the variance of a given sample data. The algorithm itself has several
       * variables, which are listed here. I won't pretend to fully understand it myself, but there
       * are a lot of references online for it.
       */
      private double mMean = 0;
      private double mVarianceDelta = 0;
      private double mVarianceDelta2 = 0;
      private double mVarianceM2 = 0;
  
      /**
       * The current variance of all solves ever recorded. A value of {@link #UNKNOWN} indicates
       * the sample size is not enough for it to be calculated yet.
       */
      private long mVariance;
  
      /**
       * The sum of all non-DNF results currently recorded in {@code #mTimes}. The number of such
       * results is given by {@code Math.min(mN, mNumSolves) - mNumCurrentDNFs}. A value of
       * {@link #UNKNOWN} indicates that there are no non-DNF results recorded.
       */
      private long mCurrentSum;
  
      /**
       * The sum of all non-DNF results ever recorded in {@code #mTimes}. The number of such results
       * is given by {@code mNumSolves - mNumAllTimeDNFs}. A value of {@link #UNKNOWN} indicates
       * that there are no non-DNF results recorded.
       */
      private long mAllTimeSum;
  
      /**
       * The best time currently recorded in {@code #mTimes}. A value of {@link #UNKNOWN} indicates
       * that there is no non-DNF result recorded.
       */
      private long mCurrentBestTime;
  
      /**
       * The worst time (not a DNF) currently recorded in {@code #mTimes}. If any DNF is present, a
       * DNF will be taken instead as the worst time, if the calculation needs to exclude one. A
       * value of {@link #UNKNOWN} indicates that there is no non-DNF result recorded.
       */
      private long mCurrentWorstTime;
  
      /**
       * The current average value calculated from all times stored in {@link #mTimes}. A value of
       * {@link #UNKNOWN} indicates insufficient results have been added to calculate the required
       * average, or that the calculation has not been performed. A value of {@link #DNF} indicates
       * that too many DNF results are present and the average is disqualified.
       */
      private long mCurrentAverage;
  
      /**
       * The best time ever added to this calculator. This time may not currently be recorded in
       * {@code #mTimes}, as it may have been overwritten. A value of {@link #UNKNOWN} indicates that
       * there is no non-DNF result recorded.
       */
      private long mAllTimeBestTime;
  
      /**
       * The worst time (not a DNF) ever added to this calculator. This time may not currently be
       * recorded in {@code #mTimes}, as it may have been overwritten. A value of {@link #UNKNOWN}
       * indicates that there is no non-DNF result recorded.
       */
      private long mAllTimeWorstTime;
  
      /**
       * The best average value calculated from all times added to date. A value of {@link #UNKNOWN}
       * indicates that insufficient results have been added to calculate the required average. A
       * value of {@link #DNF} indicates that averages could be calculated, but that every average
       * was disqualified as a DNF average.
       */
      private long mAllTimeBestAverage;
  
      /**
       * Creates a new calculator for the "average of <i>n</i>" solve times.
       *
       * @param n
       *     The number of solve times that will be averaged (e.g., 3, 5, 12, ...). Must be greater
       *     than zero.
       *
       * @throws IllegalArgumentException
       *     If {@code n} is not greater than zero.
       */
      AverageCalculator(int n, int trimPercent) {
          if (n <= 0) {
              throw new IllegalArgumentException("Number of solves must be > 0: " + n);
          }
  
          mN = n;
          mTimes = new long[n];
          mDisqualifyDNFs = true;
  
          mTrimSize = (int) Math.ceil (mN * (trimPercent / 100f));
          mNumAcceptableDNFs = mTrimSize;
          mLowerTrimBound = mTrimSize;
          mUpperTrimBound = mN - mTrimSize;
  
          mUpperTrim = new AverageComponent();
          mMiddleTrim = new AverageComponent();
          mLowerTrim = new AverageComponent();
  
          // As "reset()" needs to be supported to ensure a sane state can be guaranteed before
          // populating statistics from the database, it makes sense to use it to initialise the
          // fields in one place.
          reset();
      }
  
      /**
       * Resets all statistics and averages that have been collected previously.
       */
      public void reset() {
          Arrays.fill(mTimes, 0L);
          mNext = 0;
          mNumSolves = 0;
          mNumCurrentDNFs = 0;
          mNumAllTimeDNFs = 0;
  
          // Variance variables
          mMean = 0;
          mVarianceDelta = 0;
          mVarianceDelta2 = 0;
          mVarianceM2 = 0;
  
          mMiddleTrim = new AverageComponent();
          mLowerTrim = new AverageComponent();
          mUpperTrim = new AverageComponent();
  
          mCurrentSum = UNKNOWN;
          mAllTimeSum = UNKNOWN;
          mCurrentBestTime = UNKNOWN;
          mCurrentWorstTime = UNKNOWN;
          mCurrentAverage = UNKNOWN;
          mAllTimeBestTime = UNKNOWN;
          mAllTimeWorstTime = UNKNOWN;
          mAllTimeBestAverage = UNKNOWN;
          mVariance = UNKNOWN;
      }
  
      /**
       * Gets the number of solve times that are included in the average. This is inclusive of any
       * times, such as the best and worst times, that are excluded when calculating the truncated
       * mean. For example, for an "average of 12", the best time and the worst time are trimmed
       * before getting the truncated arithmetic mean of the remaining 10 times, but this method
       * returns 12. This may be greater than the number of times added so far and given by
       * {@link #getNumSolves()}.
       *
       * @return The number of times that must be considered in the calculation of the average.
       */
      public int getN() {
          return mN;
      }
  
      /**
       * Adds a solve time to be included in the calculation of the average. Solve times should be
       * added in chronological order (i.e., by solve time-stamp, not solve time).
       *
       * @param time
       *     The solve time in milliseconds. The time must be greater than zero. Use {@link #DNF} to
       *     represent a DNF solve.
       *
       * @throws IllegalArgumentException
       *     If the added time is not greater than zero and is not {@code DNF}.
       */
      public void addTime(long time) throws IllegalArgumentException {
          if (time <= 0L && time != DNF) {
              // FIXME: throwing an IllegalArgumentException here is too harsh for the user. If the app
              // incorrectly imports an illegal solve, the app will keep crashing and the only way for
              // the user to fix this is to clear the app data. I'm commenting this off for the time
              // being until the import algorithm gets sorted out.
              // TODO: Should the app automatically remove illegal solves?
  
              Log.e("AverageCalculator", "Time must be > 0 or be 'DNF': " + time);
  
              // throw new IllegalArgumentException("Time must be > 0 or be 'DNF': " + time);
          } else {
  
              mNumSolves++;
  
              final long ejectedTime;
  
              // If the array has just been filled, store a sorted version of it
              // If the array is full, "mNext" points to the oldest result that needs to be ejected first.
              //      We also need to remove the oldest solve from the sorted array and insert the new solve
              // If the array is not full, then "mNext" points to an empty entry, so no special handling
              // is needed.
              if (mNumSolves >= mN) {
                  if (mNext == mN) {
                      // Need to wrap around to the start (index zero).
                      mNext = 0;
                  }
                  ejectedTime = mTimes[mNext]; // May be DNF.
  
                  // Create the sorted list as soon as numSolves reaches N
                  // We only need to sort it once. Subsequent added solves will use
                  // an algorithm to insert the new solves in the correct (sorted) position
                  if (mNumSolves == mN) {
                      mTimes[mNext] = time;
  
                      // Sort mTimes
                      List<Long> sortedTimes = new ArrayList<>(StatUtils.asList(mTimes));
                      Collections.sort(sortedTimes);
  
                      // Distribute the sorted times into the trims
                      int count = 0;
                      for (long solve : sortedTimes) {
                          if (count < mLowerTrimBound)
                              mLowerTrim.put(solve);
                          else if (count >= mUpperTrimBound)
                              mUpperTrim.put(solve);
                          else
                              mMiddleTrim.put(solve);
                          count++;
                      }
                  }
  
              } else {
                  // "mNext" must be less than "mN" if "mNumSolves" is less than "mN".
                  ejectedTime = UNKNOWN; // Nothing ejected.
              }
  
              mTimes[mNext] = time;
              mNext++;
  
              //Log.d("AverageCalculator", "N: " + mN + " | Set: " + mSortedTimes);
  
              // Order is important here, as these methods change fields and some methods depend on the
              // fields being updated by other methods before they are called. All depend on the new
              // time being stored already (see above) and any ejected time being known (also above).
              updateDNFCounts(time, ejectedTime);
              updateCurrentBestAndWorstTimes(time, ejectedTime);
              updateSums(time, ejectedTime);
              updateCurrentTrims(time, ejectedTime);
              updateVariance(time);
              updateCurrentAverage();
  
              updateAllTimeBestAndWorstTimes();
              updateAllTimeBestAverage();
          }
      }
  
      /**
       * Adds solve times to be included in the calculation of the average. Solve times should be
       * added in chronological order (i.e., by solve time-stamp, not solve time). This method can be
       * called repeatedly to add any number of solve times over any number of calls.
       *
       * @param times
       *     Zero or more solve times in milliseconds. Times must be greater than zero. Use
       *     {@link #DNF} to represent each DNF. If this is {@code null} or empty, it will be ignored
       *     and this method will have no effect.
       *
       * @throws IllegalArgumentException
       *     If any added time is not greater than zero and is not {@code DNF}.
       */
      public void addTimes(long... times) throws IllegalArgumentException {
          // The variable arguments list makes it easier to write compact test cases; it does not
          // really make life any easier when adding times via a database cursor. In non-test
          // contexts, it will be more efficient to call "addTime", as each call will not need to
          // create a "long[]" object.
          if (times != null) {
              for (final long time : times) {
                  addTime(time); // May throw IAE.
              }
          }
      }
  
      /**
       * Updates the current and all-time counts of DNF solves.
       *
       * @param addedTime
       *     The newly added time. May be {@link #DNF}.
       * @param ejectedTime
       *     An old time that was ejected to make room for the newly added time. May be {@code DNF}.
       *     Use {@link #UNKNOWN} if no old time was ejected.
       */
      private void updateDNFCounts(long addedTime, long ejectedTime) {
          if (addedTime == DNF) {
              mNumCurrentDNFs++;
              mNumAllTimeDNFs++;
          }
  
          if (ejectedTime == DNF) {
              mNumCurrentDNFs--;
          }
      }
  
      /**
       * Updates the current best and worst times after a new time is added. The count of DNFs must
       * be updated by {@link #updateDNFCounts(long, long)} before calling this method.
       *
       * @param addedTime
       *     The newly added time. May be {@link #DNF}. Must already be stored.
       * @param ejectedTime
       *     An old time that was ejected to make room for the newly added time. May be {@code DNF}.
       *     Use {@link #UNKNOWN} if no old time was ejected.
       */
      private void updateCurrentBestAndWorstTimes(long addedTime, long ejectedTime) {
          // The logic here will set one or both of "mCurrentBestTime" and "mCurrentWorstTime" to
          // "UNKNOWN" if knowledge of the best or worst time has been lost. If either value becomes
          // "UNKNOWN", a new iteration over "mTimes" will recalculate both values.
  
          if (addedTime == DNF) {
              // Newly added time does not change the current best or worst time, but has either of
              // the best or worst times (not a DNF) just been ejected and is recalculation required?
              if (ejectedTime == mCurrentBestTime || ejectedTime == mCurrentWorstTime) {
                  // It does not matter which has been ejected, just recalculate both.
                  mCurrentBestTime = UNKNOWN;
                  mCurrentWorstTime = UNKNOWN;
              }
          } else {
              // Newly added time is not a DNF and may be the new best or worst time (or both).
              // However, if it is not the new (or equal) best or worst time, then check if we are
              // ejecting the old best or worst time. If either is ejected, there may be another best
              // or worst time in "mTimes" (with respect to "addedTime") and it must be found. There
              // if no need to check if "ejectedTime" is DNF or UNKNOWN.
              if (mCurrentBestTime == UNKNOWN || addedTime <= mCurrentBestTime) {
                  mCurrentBestTime = addedTime;
              } else if (ejectedTime == mCurrentBestTime) {
                  mCurrentBestTime = UNKNOWN;
              }
  
              if (mCurrentWorstTime == UNKNOWN || addedTime >= mCurrentWorstTime) {
                  mCurrentWorstTime = addedTime;
              } else if (ejectedTime == mCurrentWorstTime) {
                  mCurrentWorstTime = UNKNOWN;
              }
          }
  
          // Recalculate the best and worst times. We can skip this if every stored time is a DNF.
          // In that case, both "mCurrentBestTime" and "mCurrentWorstTime" will remain UNKNOWN.
          final int numCurrentSolves = Math.min(mNumSolves, mN);
  
          if (mNumCurrentDNFs != numCurrentSolves
                  && (mCurrentBestTime == UNKNOWN || mCurrentWorstTime == UNKNOWN)) {
              // At least one stored time is not a DNF and is > 0, so reset the fields and rescan.
              mCurrentBestTime = Long.MAX_VALUE;
              mCurrentWorstTime = 0L;
  
              // There is no need to follow the chronological insertion order here. The array may
              // not be full yet.
              for (int i = 0; i < numCurrentSolves; i++) {
                  final long time = mTimes[i];
  
                  if (time != DNF) {
                      mCurrentBestTime = Math.min(mCurrentBestTime, time);
                      mCurrentWorstTime = Math.max(mCurrentWorstTime, time);
                  }
              }
          }
      }
  
      private void updateCurrentTrims(long addedTime, long ejectedTime) {
          if (mNumSolves > mN && mLowerTrimBound > 0) {
              // Ejected time belongs to lower trim
              if (ejectedTime <= mLowerTrim.getGreatest()) {
                  // Remove the ejected time
                  mLowerTrim.remove(ejectedTime);
  
                  if (addedTime <= mMiddleTrim.getLeast()) {
                      // Added time belongs to lower trim
                      mLowerTrim.put(addedTime);
                  } else if (addedTime >= mUpperTrim.getLeast()) {
                      // Added time belongs to upper trim
                      // Move least elements to the left
                      mLowerTrim.put(mMiddleTrim.getLeast());
                      mMiddleTrim.remove(mMiddleTrim.getLeast());
                      mMiddleTrim.put(mUpperTrim.getLeast());
                      mUpperTrim.remove(mUpperTrim.getLeast());
                      mUpperTrim.put(addedTime);
                  } else {
                      // Added time belongs to middle trim
                      // Move least elements to the left
                      mLowerTrim.put(mMiddleTrim.getLeast());
                      mMiddleTrim.remove(mMiddleTrim.getLeast());
                      mMiddleTrim.put(addedTime);
                  }
              }
  
              // Ejected time belongs to upper trim
              else if (ejectedTime >= mUpperTrim.getLeast()) {
                  // Remove the ejected time
                  mUpperTrim.remove(ejectedTime);
  
                  if (addedTime >= mMiddleTrim.getGreatest()) {
                      // Added time belongs to upper trim
                      mUpperTrim.put(addedTime);
                  } else if (addedTime <= mLowerTrim.getGreatest()) {
                      // Added time belongs to lower trim
                      // Move greatest elements to right
                      mUpperTrim.put(mMiddleTrim.getGreatest());
                      mMiddleTrim.remove(mMiddleTrim.getGreatest());
                      mMiddleTrim.put(mLowerTrim.getGreatest());
                      mLowerTrim.remove(mLowerTrim.getGreatest());
                      mLowerTrim.put(addedTime);
                  } else {
                      // Added time belongs to middle trim
                      // Move greatest elements to right
                      mUpperTrim.put(mMiddleTrim.getGreatest());
                      mMiddleTrim.remove(mMiddleTrim.getGreatest());
                      mMiddleTrim.put(addedTime);
                  }
              }
  
              // Ejected time belongs to middle trim
              else {
                  // Remove the ejected time
                  mMiddleTrim.remove(ejectedTime);
  
                  if (addedTime >= mUpperTrim.getLeast()) {
                      // Added time belongs to upper trim
                      // Move least elements to left
                      mMiddleTrim.put(mUpperTrim.getLeast());
                      mUpperTrim.remove(mUpperTrim.getLeast());
                      mUpperTrim.put(addedTime);
                  } else if (addedTime <= mLowerTrim.getGreatest()) {
                      // Added time belongs to lower trim
                      // Move greatest elements to right
                      mMiddleTrim.put(mLowerTrim.getGreatest());
                      mLowerTrim.remove(mLowerTrim.getGreatest());
                      mLowerTrim.put(addedTime);
                  } else {
                      // Added time belongs to middle trim
                      mMiddleTrim.put(addedTime);
                  }
              }
          } else if (mNumSolves > mN) {
              // If the bound is 0, mLowerTrim and mUpperTrim will be null
              // All operations will be done on mMiddleTrim
              mMiddleTrim.remove(ejectedTime);
              mMiddleTrim.put(addedTime);
          }
      }
  
      /**
       * Updates the sum of all times currently stored and the sum of all times ever added. Any
       * {@link #DNF} results are ignored. If all recorded times have been DNFs, the sums will set
       * to {@link #UNKNOWN}.
       *
       * @param addedTime
       *     The newly added time. May be {@code DNF}. Must already be stored.
       * @param ejectedTime
       *     An old time that was ejected to make room for the newly added time. May be {@code DNF}.
       *     Use {@code UNKNOWN} if no old time was ejected.
       */
      private void updateSums(long addedTime, long ejectedTime) {
          if (addedTime != DNF) {
              mCurrentSum = addedTime + (mCurrentSum == UNKNOWN ? 0L : mCurrentSum);
              mAllTimeSum = addedTime + (mAllTimeSum == UNKNOWN ? 0L : mAllTimeSum);
          }
          if (ejectedTime != DNF && ejectedTime != UNKNOWN) {
              mCurrentSum -= ejectedTime;
          }
  
          // Returned from a state with at least one non-DNF time to a state where all times are DNFs.
          // Flag the new state properly. ("mAllTimeSum" cannot return to zero.)
          if (mCurrentSum == 0L) {
              mCurrentSum = UNKNOWN;
          }
      }
  
      /**
       * The Welford algorithm for variance is one of the most well-known and used online methods of
       * calculating the variance of a given sample data. I won't pretend to fully understand it
       * myself, but there are a lot of references online for it.
       */
      private void updateVariance(long addedTime) {
          long totalValidSolves = (mNumSolves - mNumAllTimeDNFs);
          if (addedTime != DNF) {
              mVarianceDelta = ((double) addedTime) - mMean;
              mMean += mVarianceDelta / totalValidSolves;
              mVarianceDelta2 = ((double) addedTime) - mMean;
              mVarianceM2 += mVarianceDelta * mVarianceDelta2;
          }
          if (totalValidSolves > 2) {
              mVariance = (long) (mVarianceM2 / (totalValidSolves - 1));
          }
      }
  
      /**
       * Updates the average value of the most recently added times. See {@link #getCurrentAverage()}
       * for details. The sum, best and worst values and other fields must be updated by first calling
       * {@link #updateSums(long, long)} and {@link #updateCurrentBestAndWorstTimes(long, long)} and
       * their dependent methods before calling this method.
       */
      private void updateCurrentAverage() {
          if (mNumSolves < mN) {
              // Not enough times added to calculate the average.
              mCurrentAverage = UNKNOWN;
          } else if (mNumCurrentDNFs == mN) {
              // Enough times have been added, but all of the currently stored ones are DNFs.
              mCurrentAverage = DNF;
          } else if (!mDisqualifyDNFs && mNumCurrentDNFs == mN - 1) {
              // More than one DNF is not an automatic disqualification, but there is only one
              // non-DNF time present. Just use that time as the average.
              mCurrentAverage = mCurrentBestTime;
          } else if (mN >= MIN_N_TO_ALLOW_ONE_DNF) {
              if (mDisqualifyDNFs && mNumCurrentDNFs > mNumAcceptableDNFs) {
                  // Disqualify the average: the number of current DNFs is above the acceptable threshold
                  mCurrentAverage = DNF;
              } else {
                  // There is no more than one DNF, or there is more than one DNF, but that will not
                  // cause automatic disqualification. There are at least two non-DNF times present.
                  // Calculate a truncated arithmetic mean. "mCurrentSum" is the sum of all non-DNF
                  // times. Discard the upper and lower trims, discard all other DNFs, if any.
                  // One DNF may already have been discarded as the worst time; do not discard it twice.
                  mCurrentAverage = mMiddleTrim.getSum() /
                                    (mN - (mTrimSize * 2) -
                                     (mNumCurrentDNFs > 1 ? mNumCurrentDNFs - 1 : 0));
              }
          } else { // mN < MIN_N_TO_ALLOW_ONE_DNF
              // NOTE: "mN" could be as low as 1, but will not be zero (see the constructor).
              if (mDisqualifyDNFs && mNumCurrentDNFs > 0) {
                  // Disqualify the average as *no* DNF (not even one) is allowed for small "n".
                  mCurrentAverage = DNF;
              } else {
                  // There is no DNF, or there are DNFs, but that will not cause automatic
                  // disqualification. There is at least one non-DNF time present. Calculate the
                  // (not truncated) arithmetic mean.
                  mCurrentAverage = mCurrentSum / (mN - mNumCurrentDNFs);
              }
          }
      }
  
      /**
       * Updates the all-time best and worst times after a new time is added. The current best and
       * worst times must be updated by {@link #updateCurrentBestAndWorstTimes(long, long)} before
       * calling this method.
       */
      private void updateAllTimeBestAndWorstTimes() {
          if (mAllTimeBestTime == UNKNOWN) {
              mAllTimeBestTime = mCurrentBestTime; // May still be UNKNOWN.
          } else if (mCurrentBestTime != UNKNOWN) {
              // "mCurrentBestTime" is never set to "DNF".
              mAllTimeBestTime = Math.min(mAllTimeBestTime, mCurrentBestTime);
          }
  
          if (mAllTimeWorstTime == UNKNOWN) {
              mAllTimeWorstTime = mCurrentWorstTime; // May still be UNKNOWN.
          } else if (mCurrentWorstTime != UNKNOWN) {
              mAllTimeWorstTime = Math.max(mAllTimeWorstTime, mCurrentWorstTime);
          }
      }
  
      /**
       * Updates the all-time best average after a new time is added. The current average must be
       * updated by {@link #updateCurrentAverage()} before calling this method.
       */
      private void updateAllTimeBestAverage() {
          if (mAllTimeBestAverage == UNKNOWN || mAllTimeBestAverage == DNF) {
              // "mCurrentAverage" may still be UNKNOWN or DNF, but cannot change back to UNKNOWN once
              // set to a different value, as UNKNOWN is cleared once "mN" solves have been added.
              // Therefore, we never set "mAllTimeBestAverage" to a value worse than it already has.
              mAllTimeBestAverage = mCurrentAverage;
          } else if (mCurrentAverage != DNF) {
              mAllTimeBestAverage = Math.min(mAllTimeBestAverage, mCurrentAverage);
          }
      }
  
      /**
       * <p>
       * Gets the current value of the average. This is calculated from the most recently added
       * times. The number of times considered is given by {@link #getN()} ("n").
       * </p>
       * <p>
       * Where the value of "n" is less than 5, the average is the arithmetic mean of the currently
       * stored values, not a truncated mean. If any currently recorded solve is a {@link #DNF},
       * the average is disqualified as a DNF unless configured so that DNFs do not automatically
       * disqualify averages (by passing {@code false} as the value of the {@code disqualifyDNFs}
       * parameter to {@link #AverageCalculator(int, boolean)}). If DNFs are allowed, then the
       * average is the average time of all non-DNF solves, but will still be a DNF average if all
       * solves are DNFs.
       * </p>
       * <p>
       * Where the value of "n" is 5 or greater, the average is the truncated arithmetic mean of the
       * currently stored values. The single best and single worst solve times are discarded and the
       * average is calculated from the remaining times. If one DNF is present, it is taken as the
       * worst solve time and discarded. If more than one DNF is present, the average is disqualified
       * as a DNF unless configured so that DNFs do not automatically disqualify averages. If more
       * DNFs are allowed, one will be taken as the worst solve time and the other DNFs will be
       * ignored. If only a single non-DNF time remains, it will not be discarded as the best time
       * and will be returned as the average time.
       * </p>
       *
       * @return
       *     The current (truncated( arithmetic mean of the most recently added values. If fewer
       *     times have been added that the number required, the result will be {@link #UNKNOWN}.
       *     If too many DNF solves are included in the recently-added times, the result is
       *     {@code DNF}. The returned integer value of the average is truncated (rounded down).
       */
      public long getCurrentAverage() {
          return mCurrentAverage;
      }
  
      /**
       * Gets the best value of the average. This is calculated across all added times. The number of
       * times considered is given by {@link #getN()}. The average for each consecutive sequence of
       * that number of times (including DNFs) is calculated as each new time is added and the best
       * average of all of those sequences is returned. See {@link #getCurrentAverage()} for more
       * details.
       *
       * @return
       *     The best truncated arithmetic mean across all added values. If fewer times have been
       *     added that the number required, the result will be {@link #UNKNOWN}. If too many DNF
       *     solves are included in <i>all</i> sequences of times, the result is {@link #DNF}.
       */
      public long getBestAverage() {
          return mAllTimeBestAverage;
      }
  
      /**
       * Gets the best time of all those added to this calculator.
       *
       * @return
       *     The best time ever added to this calculator. The result will be {@link #UNKNOWN} if no
       *     times have been added, or if all added times were {@link #DNF}s.
       */
      public long getBestTime() {
          return mAllTimeBestTime;
      }
  
      /**
       * Gets the worst time (not a DNF) of all those added to this calculator.
       *
       * @return
       *     The worst time ever added to this calculator. The result will be {@link #UNKNOWN} if no
       *     times have been added, or if all added times were {@link #DNF}s.
       */
      public long getWorstTime() {
          return mAllTimeWorstTime;
      }
  
      /**
       * Gets the total number of solve times (including DNFs) that were added to this calculator.
       * This may be greater than the number (given by {@link #getN}) that are included in the
       * calculation of the average. Subtract the value from {@link #getNumDNFSolves()} to get the
       * total number of non-DNF solves.
       *
       * @return The number of solve times that were added to this calculator.
       */
      public int getNumSolves() {
          return mNumSolves;
      }
  
      /**
       * Gets the total number of DNF solves that were added to this calculator.
       *
       * @return The number of DNF solves that were added to this calculator.
       */
      public int getNumDNFSolves() {
          return mNumAllTimeDNFs;
      }
  
      /**
       * Gets the total time of all non-DNF solves that were added to this calculator.
       *
       * @return
       *     The total time of all non-DNF solves that were added to this calculator. The result
       *     will be {@link #UNKNOWN} if no times have been added, or if all added times were
       *     {@link #DNF}s.
       */
      public long getTotalTime() {
          return mAllTimeSum;
      }
  
      /**
       * Gets the current Sample Standard Deviation of all non-DNF solves that were added to this
       * calculator
       *
       * @return
       *      The Sample Standard Deviation of all non-DNF solves that were added to this calculator
       *      Will be {@link #UNKNOWN} if no times have been added, or if all added solve times
       *      were {@link #DNF}s.
       */
      public long getStandardDeviation() { return mVariance != UNKNOWN ? (long) Math.sqrt
              (mVariance) : UNKNOWN; }
  
      /**
       * Gets the simple arithmetic mean time of all non-DNF solves that were added to this
       * calculator. The returned millisecond value is truncated to a whole milliseconds value, not
       * rounded.
       *
       * @return
       *     The mean time of all non-DNF solves that were added to this calculator. The result
       *     will be {@link #UNKNOWN} if no times have been added, or if all added times were
       *     {@link #DNF}s.
       */
      public long getMeanTime() {
          return (long) mMean != 0 ? (long) mMean : UNKNOWN;
      }
  
      /**
       * Captures the details of the average-of-N calculation including the most recently added time.
       *
       * @return The details for the average-of-N calculation.
       */
      public AverageOfN getAverageOfN() {
          return new AverageOfN(this);
      }
  
      /**
       * Translates a time value that may be {@link #UNKNOWN} or {@link #DNF} into a time value
       * that is compatible with methods such as the {@code PuzzleUtils.convertTimeToString*}
       * methods.
       *
       * @param time The time value to be translated.
       *
       * @return
       *     The translated time value; {@code UNKNOWN} is translated to zero and {@code DNF} is
       *     translated to {@link PuzzleUtils#TIME_DNF}.
       */
      public static long tr(long time) {
          if (time == UNKNOWN) {
              return 0L;
          }
          if (time == DNF) {
              return PuzzleUtils.TIME_DNF;
          }
          return time;
      }
  
      /**
       * A summary of the average of the mostly recently added times. All times are provided in an
       * array and the calculated average, best time and worst time are identified, if appropriate.
       */
      public static class AverageOfN {
          /**
           * The array of values that contributed to the calculation of the average-of-N. If too few
           * values have been recorded (less than "N"), the array will be {@code null}. The times
           * will be ordered with the oldest recorded time first.
           */
          private final long[] mTimes;
  
          /**
           * The total sum of the upper-trim of the calculated times. May be {@link #DNF} if there are too
          * many DNF solves, or {@link #UNKNOWN} if the are too few times (less than "N").
           */
          private long mUpperTrimSum;
  
          /**
           * The total sum of the middle-trim of the calculated times. May be {@link #DNF} if there are too
           * many DNF solves, or {@link #UNKNOWN} if the are too few times (less than "N").
           */
          private long mMiddleTrimSum;
  
          /**
           * The total sum of the lower-trim of the calculated times. May be {@link #DNF} if there are too
           * many DNF solves, or {@link #UNKNOWN} if the are too few times (less than "N").
           */
          private long mLowerTrimSum;
  
          /**
           * The index within {@link #mTimes} of the best time. The index will be -1 if that array is
           * {@code null}, or if the average calculation for the value of "N" does not eliminate the
           * best time, or if all of the times are DNFs, or if DNFs do not cause disqualification,
           * but there is only one non-DNF time recorded.
           */
          private final int mBestTimeIndex;
  
          /**
           * The index within {@link #mTimes} of the worst time. The index will be -1 if that array is
           * {@code null}, or if the average calculation for the value of "N" does not eliminate the
           * best time, or if all of the times are DNFs. The worst time may be a DNF.
           */
          private final int mWorstTimeIndex;
  
          /**
           * The average-of-N value calculated for the times. May be {@link #DNF} if there are too
           * many DNF solves, or {@link #UNKNOWN} if the are too few times (less than "N").
           */
          private final long mAverage;
  
          /**
           * Creates a new record of the most recent "average-of-N" recorded by an average calculator.
           *
           * @param ac The average calculator from which to capture the information.
           */
          private AverageOfN(AverageCalculator ac) {
              final int n = ac.getN();
  
              mAverage = ac.getCurrentAverage();
              mUpperTrimSum = ac.mUpperTrim.getSum();
              mMiddleTrimSum = ac.mMiddleTrim.getSum();
              mLowerTrimSum = ac.mLowerTrim.getSum();
  
              if (mAverage != UNKNOWN && ac.getNumSolves() >= n) {
                  mTimes = new long[n];
  
                  // The oldest time recorded in "ac.mTimes" is not necessarily the first one, as
                  // that array operates as a circular queue. "ac.mNext" marks one index past the
                  // last added time. However, the array should be full, so this should also be the
                  // index of the first (oldest) time. If "ac.mNext" equals "n", then we wrap around
                  // to start at index zero.
                  final int oldestIndex = ac.mNext == n ? 0 : ac.mNext;
  
                  System.arraycopy(ac.mTimes, oldestIndex, mTimes, 0, n - oldestIndex);
                  System.arraycopy(ac.mTimes, 0, mTimes, n - oldestIndex, oldestIndex);
  
                  // "-1" is the convention for an unknown *index*, so "UNKNOWN" is not used.
                  int bestIdx = -1;
                  int worstIdx = -1;
  
                  // IF the threshold value of "N" for the calculation of a truncated mean is not
                  // reached, no best or worst times will be identified for elimination.
                  //
                  // IF all times are DNFs, no best or worst times will be identified for elimination.
                  //
                  // IF only one time is not a DNF, no best time will be identified for elimination.
                  //
                  // IF DNFs are present, a DNF will be identified as the worst time instead of
                  // "mCurrentWorstTime", as "mCurrentWorstTime" is never set to DNF.
                  if (n >= MIN_N_TO_ALLOW_ONE_DNF && n > ac.mNumCurrentDNFs) { // At least 1 non-DNF.
                      // Do not identify the only non-DNF time as the best time.
                      final long bestTime
                              = (n - ac.mNumCurrentDNFs > 1) ? ac.mCurrentBestTime : UNKNOWN;
                      // Identify a DNF as the worst time if DNFs are present.
                      final long worstTime = ac.mNumCurrentDNFs == 0 ? ac.mCurrentWorstTime : DNF;
  
                      for (int i = 0; i < n && (bestIdx == -1 || worstIdx == -1); i++) {
                          // Use if...else... here to ensure that the best and worst times are not
                          // recorded at the same index (e.g., if all times are DNFs or all equal).
                          if (bestIdx == -1 && mTimes[i] == bestTime) {
                              bestIdx = i;
                          } else if (worstIdx == -1 && mTimes[i] == worstTime) {
                              worstIdx = i;
                          }
                      }
                  }
  
                  mBestTimeIndex = bestIdx;
                  mWorstTimeIndex = worstIdx;
              } else {
                  mTimes = null;
                  mBestTimeIndex = -1;
                  mWorstTimeIndex = -1;
              }
          }
  
          /**
           * Gets the array of values that contributed to the calculation of the average-of-N. If
           * too few values have been recorded (less than "N"), the array will be {@code null}. The
           * times will be ordered with the oldest recorded time first and may include {@link #DNF}
           * values. The best and worst times can be identified with {@link #getBestTimeIndex()} and
           * {@link #getWorstTimeIndex()}.
           *
           * @return
           *     The array of times used to calculate the average. May be {@code null}.
           */
          public long[] getTimes() {
              return mTimes;
          }
  
          /**
           * Gets the calculated average-of-N value. The calculation follows the normal rules for
           * the value of "N" that are applied by the average calculator from which this object was
           * captured.
           *
           * @return
           *     The average-of-N value. May be {@link #DNF} if the average was disqualified, or
           *     {@link #UNKNOWN} if too few times have been recorded (i.e., less than "N").
           */
          public long getAverage() {
              return mAverage;
          }
  
          /**
           * Gets the index within the array returned by {@link #getTimes()} of the best time
           * eliminated for the average-of-N calculation. If there were insufficient times, or if the
           * value of "N" is lower than the threshold where best times are eliminated, or if there
           * are less than two non-DNF times, the result will be -1. When DNFs do not disqualify the
           * average and there is only one non-DNF time, that time is not identified as the "best"
           * time, so it is not eliminated; instead that single time becomes the average time.
           *
           * @return The index of the best time value, or -1 if it is not known.
           */
          public int getBestTimeIndex() {
              return mBestTimeIndex;
          }
  
          /**
           * Gets the index within the array returned by {@link #getTimes()} of the worst time
           * eliminated for the average-of-N calculation. If there were insufficient times, or if the
           * value of "N" is lower than the threshold where worst times are eliminated, or if all of
           * the times are DNF times, the result will be -1. If DNFs are present and at least one
           * time is not a DNF, the first DNF will be marked as the worst time.
           *
           * @return The index of the worst time value, or -1 if it is not known.
           */
          public int getWorstTimeIndex() {
              return mWorstTimeIndex;
          }
  
          /**
           * Gets the calculated upper trim sum. That is, the sum of all times in sorted order
           * from the set trim boundary to the end of the mSortedList array
           *
           * @return
           *     The trim value. May be {@link #UNKNOWN} if too few times have been recorded (i.e., less than "N").
           */
          public long getmUpperTrimSum() {
              return mUpperTrimSum;
          }
  
          /**
           * Gets the calculated middle trim sum. That is, the sum of all times minus
           * {@code mUpperTrimSum} and {@code mLowerTrimSum}
           * @return
           *     The trim value. May be {@link #UNKNOWN} if too few times have been recorded (i.e., less than "N").
           */
          public long getmMiddleTrimSum() {
              return mMiddleTrimSum;
          }
  
          /**
           * Gets the calculated lower trim sum. That is, the sum of all times in sorted order
           * from beginning mSortedList array until the set trim boundary
           *
           * @return
           *     The trim value. May be {@link #UNKNOWN} if too few times have been recorded (i.e., less than "N").
           */
          public long getmLowerTrimSum() {
              return mLowerTrimSum;
          }
      }
  }
  