// Copyright 2017 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#ifndef COBALT_BASE_C_VAL_COLLECTION_ENTRY_STATS_H_
#define COBALT_BASE_C_VAL_COLLECTION_ENTRY_STATS_H_

#include <algorithm>
#include <cmath>
#include <numeric>
#include <sstream>
#include <string>
#include <vector>

#include "base/callback.h"
#include "base/logging.h"
#include "base/stringprintf.h"
#include "base/time.h"
#include "cobalt/base/c_val.h"

namespace base {
namespace CValDetail {

// This class tracks a collection of entries, which it retains in memory. When
// either the max size of the collection is reached or Flush() is manually
// called, the count, average, minimum, maximum, 25th, 50th, 75th and 95th
// percentiles, and standard deviation of the collection are recorded with
// CVals, and the tracking resets in preparation for the next collection of
// entries.
// NOTE1: By default there is no max size and the collection will continue to
//        grow indefinitely until Flush() is called.
// NOTE2: This class keeps all of the entries in memory until flush is called so
//        that percentiles can be determined. In cases where the number of
//        entries is extremely large, |CValTimeIntervalEntryStats| is more
//        appropriate, as it does its tracking without keeping entries in memory
//        (at the cost of not being able to provide percentiles);
// NOTE3: This class provides the ability to record all entries within a single
//        string CVal when |enable_entry_list_c_val| is set to true in the
//        constructor. By default, this CVal is not used.
template <typename EntryType, typename Visibility = CValDebug>
class CValCollectionEntryStatsImpl {
 public:
  static const size_t kNoMaxSize = 0;

  struct FlushResults {
    FlushResults(size_t sample_count, EntryType average, EntryType minimum,
                 EntryType maximum, EntryType standard_deviation,
                 EntryType percentile_25th, EntryType percentile_50th,
                 EntryType percentile_75th, EntryType percentile_95th)
        : sample_count(sample_count),
          average(average),
          minimum(minimum),
          maximum(maximum),
          standard_deviation(standard_deviation),
          percentile_25th(percentile_25th),
          percentile_50th(percentile_50th),
          percentile_75th(percentile_75th),
          percentile_95th(percentile_95th) {}

    size_t sample_count;
    EntryType average;
    EntryType minimum;
    EntryType maximum;
    EntryType standard_deviation;
    EntryType percentile_25th;
    EntryType percentile_50th;
    EntryType percentile_75th;
    EntryType percentile_95th;
  };

  typedef base::Callback<void(const FlushResults&)> OnFlushCallback;

  CValCollectionEntryStatsImpl(
      const std::string& name, size_t max_size = kNoMaxSize,
      bool enable_entry_list_c_val = false,
      const OnFlushCallback& on_flush = OnFlushCallback());

  // Add an entry to the collection. This may trigger a Flush() if adding the
  // entry causes the max size to be reached.
  void AddEntry(const EntryType& value);
  // Manually flush the collection's entries. This updates the stat cvals and
  // clears the entries.
  void Flush();

 private:
  typedef std::vector<EntryType> CollectionType;

  static EntryType CalculatePercentile(const CollectionType& sorted_collection,
                                       int percentile);
  static double CalculateStandardDeviation(const CollectionType& collection,
                                           double mean);

  // Constructs a string representing the entries within the collection and
  // populates |entry_list_| with it if the entry list CVal was enabled during
  // construction.
  void PopulateEntryList();

  // The maximum size of the collection before Flush() is automatically called.
  const size_t max_size_;

  // Callback to call whenever the values are flushed.
  const OnFlushCallback on_flush_;

  // The current collection of entries. These will be used to generate the cval
  // stats during the next call of Flush().
  CollectionType collection_;

  // CVals of the stats for the previous collection.
  base::CVal<size_t, Visibility> count_;
  base::CVal<EntryType, Visibility> average_;
  base::CVal<EntryType, Visibility> minimum_;
  base::CVal<EntryType, Visibility> maximum_;
  base::CVal<EntryType, Visibility> percentile_25th_;
  base::CVal<EntryType, Visibility> percentile_50th_;
  base::CVal<EntryType, Visibility> percentile_75th_;
  base::CVal<EntryType, Visibility> percentile_95th_;
  base::CVal<EntryType, Visibility> standard_deviation_;
  // |entry_list_| is only non-NULL when it is enabled.
  scoped_ptr<base::CVal<std::string, Visibility> > entry_list_;
};

template <typename EntryType, typename Visibility>
CValCollectionEntryStatsImpl<EntryType, Visibility>::
    CValCollectionEntryStatsImpl(
        const std::string& name, size_t max_size /*=kNoMaxSize*/,
        bool enable_entry_list_c_val /*=false*/,
        const OnFlushCallback& on_flush /*=OnFlushCallback()*/)
    : max_size_(max_size),
      on_flush_(on_flush),
      count_(StringPrintf("%s.Cnt", name.c_str()), 0, "Total entries."),
      average_(StringPrintf("%s.Avg", name.c_str()), EntryType(),
               "Average value."),
      minimum_(StringPrintf("%s.Min", name.c_str()), EntryType(),
               "Minimum value."),
      maximum_(StringPrintf("%s.Max", name.c_str()), EntryType(),
               "Maximum value."),
      percentile_25th_(StringPrintf("%s.Pct.25th", name.c_str()), EntryType(),
                       "25th percentile value."),
      percentile_50th_(StringPrintf("%s.Pct.50th", name.c_str()), EntryType(),
                       "50th percentile value."),
      percentile_75th_(StringPrintf("%s.Pct.75th", name.c_str()), EntryType(),
                       "75th percentile value."),
      percentile_95th_(StringPrintf("%s.Pct.95th", name.c_str()), EntryType(),
                       "95th percentile value."),
      standard_deviation_(StringPrintf("%s.Std", name.c_str()), EntryType(),
                          "Standard deviation of values.") {
  if (enable_entry_list_c_val) {
    entry_list_.reset(new base::CVal<std::string, Visibility>(
        StringPrintf("%s.EntryList", name.c_str()), "[]",
        "The list of entries in the collection."));
  }
}

template <typename EntryType, typename Visibility>
void CValCollectionEntryStatsImpl<EntryType, Visibility>::AddEntry(
    const EntryType& value) {
  collection_.push_back(value);
  if (collection_.size() == max_size_) {
    Flush();
  }
}

template <typename EntryType, typename Visibility>
void CValCollectionEntryStatsImpl<EntryType, Visibility>::Flush() {
  if (collection_.size() == 0) {
    return;
  }

  // Populate the entry list cval before the collection is sorted.
  PopulateEntryList();

  // Sort the collection. This allows min, max, and percentiles to be easily
  // determined.
  std::sort(collection_.begin(), collection_.end());

  // Calculate the mean of the collection.
  EntryType sum = std::accumulate(collection_.begin(), collection_.end(),
                                  CValDetail::FromDouble<EntryType>(0));
  double mean = CValDetail::ToDouble<EntryType>(sum) / collection_.size();

  // Update the collection stat cvals.
  size_t count = collection_.size();
  EntryType average = CValDetail::FromDouble<EntryType>(mean);
  EntryType minimum = collection_.front();
  EntryType maximum = collection_.back();
  EntryType percentile_25th = CalculatePercentile(collection_, 25);
  EntryType percentile_50th = CalculatePercentile(collection_, 50);
  EntryType percentile_75th = CalculatePercentile(collection_, 75);
  EntryType percentile_95th = CalculatePercentile(collection_, 95);
  EntryType standard_deviation = CValDetail::FromDouble<EntryType>(
      CalculateStandardDeviation(collection_, mean));

  // Flush the computed values out to the CVals.
  count_ = count;
  average_ = average;
  minimum_ = minimum;
  maximum_ = maximum;
  percentile_25th_ = percentile_25th;
  percentile_50th_ = percentile_50th;
  percentile_75th_ = percentile_75th;
  percentile_95th_ = percentile_95th;
  standard_deviation_ = standard_deviation;

  collection_.clear();

  // Callback to any listeners with the flush values.
  if (!on_flush_.is_null()) {
    on_flush_.Run(FlushResults(
        count, average, minimum, maximum, standard_deviation, percentile_25th,
        percentile_50th, percentile_75th, percentile_95th));
  }
}

template <typename EntryType, typename Visibility>
EntryType
CValCollectionEntryStatsImpl<EntryType, Visibility>::CalculatePercentile(
    const CollectionType& sorted_collection, int percentile) {
  DCHECK_GT(sorted_collection.size(), 0);
  DCHECK(percentile >= 0 && percentile <= 100);

  // Determine the position of the percentile within the collection.
  double percentile_position =
      (sorted_collection.size() - 1) * static_cast<double>(percentile) * 0.01;

  // Split out the integral and fractional parts of the percentile position.
  double percentile_integral_position, percentile_fractional_position;
  percentile_fractional_position =
      std::modf(percentile_position, &percentile_integral_position);

  int percentile_first_index = static_cast<int>(percentile_integral_position);

  // If |percentile_first_index| maps to the last entry, then there is no
  // second entry and there's nothing to interpolate; simply use the last entry.
  if (sorted_collection.size() == percentile_first_index + 1) {
    return sorted_collection.back();
  }

  // Interpolate between the two entries that the percentile falls between.
  double first_data_point = CValDetail::ToDouble<EntryType>(
                                sorted_collection[percentile_first_index]) *
                            (1.0 - percentile_fractional_position);
  double second_data_point =
      CValDetail::ToDouble<EntryType>(
          sorted_collection[percentile_first_index + 1]) *
      percentile_fractional_position;

  return CValDetail::FromDouble<EntryType>(first_data_point +
                                           second_data_point);
}

template <typename EntryType, typename Visibility>
double
CValCollectionEntryStatsImpl<EntryType, Visibility>::CalculateStandardDeviation(
    const CollectionType& collection, double mean) {
  if (collection.size() <= 1) {
    return 0;
  }

  double dif_squared_sum = 0;
  for (size_t i = 0; i < collection.size(); ++i) {
    double dif = CValDetail::ToDouble<EntryType>(collection[i]) - mean;
    dif_squared_sum += dif * dif;
  }

  double variance =
      dif_squared_sum / static_cast<double>(collection.size() - 1);

  return std::sqrt(variance);
}

template <typename EntryType, typename Visibility>
void CValCollectionEntryStatsImpl<EntryType, Visibility>::PopulateEntryList() {
  // If the entry list was not enabled, then |entry_list_| will be NULL and
  // there is nothing to do. Simply return.
  if (!entry_list_) {
    return;
  }

  // Construct a string containing a list representation of the collection
  // entries and set the entry list CVal to it.
  std::ostringstream oss;
  oss << "[";
  for (size_t i = 0; i < collection_.size(); ++i) {
    if (i > 0) {
      oss << ", ";
    }
    oss << CValDetail::ValToString<EntryType>(collection_[i]);
  }
  oss << "]";
  *entry_list_ = oss.str();
}

#if !defined(ENABLE_DEBUG_C_VAL)
// This is a stub class that disables CValCollectionEntryStats when
// ENABLE_DEBUG_C_VAL is not defined.
template <typename EntryType>
class CValCollectionEntryStatsStub {
 public:
  explicit CValCollectionEntryStatsStub(const std::string& name) {
    UNREFERENCED_PARAMETER(name);
  }
  CValCollectionEntryStatsStub(const std::string& name, size_t max_size,
                               bool enable_entry_list_c_val) {
    UNREFERENCED_PARAMETER(name);
    UNREFERENCED_PARAMETER(max_size);
    UNREFERENCED_PARAMETER(enable_entry_list_c_val);
  }

  void AddEntry(const EntryType& value) { UNREFERENCED_PARAMETER(value); }
  void Flush() {}
};
#endif  // ENABLE_DEBUG_C_VAL

}  // namespace CValDetail

template <typename EntryType, typename Visibility = CValDebug>
class CValCollectionEntryStats {};

template <typename EntryType>
#if defined(ENABLE_DEBUG_C_VAL)
// When ENABLE_DEBUG_C_VAL is defined, CVals with Visibility set to CValDebug
// are tracked through the CVal system.
class CValCollectionEntryStats<EntryType, CValDebug>
    : public CValDetail::CValCollectionEntryStatsImpl<EntryType, CValDebug> {
  typedef CValDetail::CValCollectionEntryStatsImpl<EntryType, CValDebug>
      CValParent;
#else   // ENABLE_DEBUG_C_VAL
// When ENABLE_DEBUG_C_VAL is not defined, CVals with Visibility set to
// CValDebug are not tracked though the CVal system and
// CValCollectionEntryStats can be stubbed out.
class CValCollectionEntryStats<EntryType, CValDebug>
    : public CValDetail::CValCollectionEntryStatsStub<EntryType> {
  typedef CValDetail::CValCollectionEntryStatsStub<EntryType> CValParent;
#endif  // ENABLE_DEBUG_C_VAL

 public:
  typedef typename CValParent::OnFlushCallback OnFlushCallback;
  typedef typename CValParent::FlushResults FlushResults;

  explicit CValCollectionEntryStats(const std::string& name)
      : CValParent(name) {}
  CValCollectionEntryStats(const std::string& name, size_t max_size,
                           bool enable_entry_list_c_val,
                           const OnFlushCallback& on_flush = OnFlushCallback())
      : CValParent(name, max_size, enable_entry_list_c_val, on_flush) {}
};

// CVals with visibility set to CValPublic are always tracked though the CVal
// system, regardless of the ENABLE_DEBUG_C_VAL state.
template <typename EntryType>
class CValCollectionEntryStats<EntryType, CValPublic>
    : public CValDetail::CValCollectionEntryStatsImpl<EntryType, CValPublic> {
  typedef CValDetail::CValCollectionEntryStatsImpl<EntryType, CValPublic>
      CValParent;

 public:
  typedef typename CValParent::OnFlushCallback OnFlushCallback;
  typedef typename CValParent::FlushResults FlushResults;

  explicit CValCollectionEntryStats(const std::string& name)
      : CValParent(name) {}
  CValCollectionEntryStats(const std::string& name, size_t max_size,
                           bool enable_entry_list_c_val,
                           const OnFlushCallback& on_flush = OnFlushCallback())
      : CValParent(name, max_size, enable_entry_list_c_val, on_flush) {}
};

}  // namespace base

#endif  // COBALT_BASE_C_VAL_COLLECTION_ENTRY_STATS_H_