// 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/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;

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

  // 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_;
  // 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*/)
    : max_size_(max_size),
      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.
  count_ = collection_.size();
  average_ = CValDetail::FromDouble<EntryType>(mean);
  minimum_ = collection_.front();
  maximum_ = collection_.back();
  percentile_25th_ = CalculatePercentile(collection_, 25);
  percentile_50th_ = CalculatePercentile(collection_, 50);
  percentile_75th_ = CalculatePercentile(collection_, 75);
  percentile_95th_ = CalculatePercentile(collection_, 95);
  standard_deviation_ = CValDetail::FromDouble<EntryType>(
      CalculateStandardDeviation(collection_, mean));

  collection_.clear();
}

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);
  variance = std::max(variance, 0.0);

  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:
  explicit CValCollectionEntryStats(const std::string& name)
      : CValParent(name) {}
  CValCollectionEntryStats(const std::string& name, size_t max_size,
                           bool enable_entry_list_c_val)
      : CValParent(name, max_size, enable_entry_list_c_val) {}
};

// 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:
  explicit CValCollectionEntryStats(const std::string& name)
      : CValParent(name) {}
  CValCollectionEntryStats(const std::string& name, size_t max_size,
                           bool enable_entry_list_c_val)
      : CValParent(name, max_size, enable_entry_list_c_val) {}
};

}  // namespace base

#endif  // COBALT_BASE_C_VAL_COLLECTION_ENTRY_STATS_H_