discrepancy.h

Go to the documentation of this file.

#ifndef ION_ANALYTICS_DISCREPANCY_H_
#define ION_ANALYTICS_DISCREPANCY_H_

#include <algorithm>
#include <vector>

#include "ion/base/logging.h"

namespace ion {
namespace analytics {

class SampleMapping {
 public:
  SampleMapping(double time_begin, double time_end, size_t num_samples) {
    CHECK_LT(1, num_samples);
    CHECK_GT(time_end, time_begin);
    time_begin_ = time_begin;
    normalized_begin_ = 0.5 / static_cast<double>(num_samples);
    const double normalized_end = (static_cast<double>(num_samples) - 0.5) /
                                  static_cast<double>(num_samples);
    scale_ = (normalized_end - normalized_begin_) / (time_end - time_begin_);
    inv_scale_ = 1.0 / scale_;
  }

  double NormalizedFromTime(double time_sample) const {
    return normalized_begin_ + scale_ * (time_sample - time_begin_);
  }

  double TimeFromNormalized(double normalized_sample) const {
    return time_begin_ + inv_scale_ * (normalized_sample - normalized_begin_);
  }

  double DurationFromLength(double length) const { return length * inv_scale_; }

 private:
  double time_begin_;
  double normalized_begin_;
  double scale_;
  double inv_scale_;
};

template <class InputIterator>
std::vector<double> NormalizeSamples(InputIterator first, InputIterator last,
                                     const SampleMapping& sample_mapping) {
  size_t num_samples = last - first;
  std::vector<double> result(num_samples);
  std::copy(first, last, result.begin());
  std::sort(result.begin(), result.end());
  for (auto& iter : result) iter = sample_mapping.NormalizedFromTime(iter);
  return result;
}

template <class ContainerType>
std::vector<double> NormalizeSamples(const ContainerType& samples,
                                     const SampleMapping& sample_mapping) {
  return NormalizeSamples(samples.begin(), samples.end(), sample_mapping);
}

struct IntervalDiscrepancy {
  IntervalDiscrepancy()
      : discrepancy(0.0), begin(0.0), end(0.0), num_samples(0) {}
  IntervalDiscrepancy(double discrepancy, double begin, double end,
                      size_t num_samples)
      : discrepancy(discrepancy),
        begin(begin),
        end(end),
        num_samples(num_samples) {}
  double discrepancy;
  double begin;
  double end;
  size_t num_samples;
};

template <class InputIterator>
IntervalDiscrepancy Discrepancy(InputIterator first, InputIterator last) {
  IntervalDiscrepancy largest_interval_discrepancy;
  const size_t num_samples = last - first;
  if (num_samples == 0) return largest_interval_discrepancy;

  const double inv_sample_count = 1.0 / static_cast<double>(num_samples);
  std::vector<double> locations;
  std::vector<size_t> count_less;
  std::vector<size_t> count_less_equal;

  if (*first > 0.0) {
    locations.push_back(0.0);
    count_less.push_back(0);
    count_less_equal.push_back(0);
  }
  size_t i = 0;
  for (auto iter = first; iter != last; ++iter) {
    locations.push_back(*iter);
    count_less.push_back(i);
    count_less_equal.push_back(i + 1);
    ++i;
  }
  if (*(last - 1) < 1.0) {
    locations.push_back(1.0);
    count_less.push_back(num_samples);
    count_less_equal.push_back(num_samples);
  }


  double interval_discrepancy = 0.0;
  size_t interval_begin = 0;
  size_t interval_end = 0;
  for (size_t i = 1; i < locations.size(); ++i) {
    const double length = locations[i] - locations[i - 1];

    const size_t count_open_increment = count_less[i] - count_less[i - 1];
    const double extended_interval_discrepancy =
        interval_discrepancy +
        (length - static_cast<double>(count_open_increment) * inv_sample_count);

    const size_t new_count_open = count_less[i] - count_less_equal[i - 1];
    const double new_interval_discrepancy =
        length - static_cast<double>(new_count_open) * inv_sample_count;

    if (extended_interval_discrepancy >= new_interval_discrepancy) {
      interval_discrepancy = extended_interval_discrepancy;
      interval_end = i;
    } else {
      interval_discrepancy = new_interval_discrepancy;
      interval_begin = i - 1;
      interval_end = i;
    }

    if (interval_discrepancy > largest_interval_discrepancy.discrepancy) {
      largest_interval_discrepancy = IntervalDiscrepancy(
          interval_discrepancy, locations[interval_begin],
          locations[interval_end],
          count_less[interval_end] - count_less_equal[interval_begin]);
    }
  }

  return largest_interval_discrepancy;
}

template <class ContainerType>
IntervalDiscrepancy Discrepancy(const ContainerType& samples) {
  return Discrepancy(samples.begin(), samples.end());
}

template <class RandomIt>
IntervalDiscrepancy AbsoluteTimestampDiscrepancy(RandomIt first,
                                                 RandomIt last) {
  const size_t num_samples = last - first;
  if (num_samples == 0) return IntervalDiscrepancy();
  if (num_samples == 1) return IntervalDiscrepancy(0.5, *first, *first, 0);

  SampleMapping sample_mapping(*std::min_element(first, last),
                               *std::max_element(first, last), num_samples);
  std::vector<double> normalized_timestamps =
      NormalizeSamples(first, last, sample_mapping);
  IntervalDiscrepancy largest_interval_discrepancy =
      Discrepancy(normalized_timestamps.begin(), normalized_timestamps.end());

  largest_interval_discrepancy.discrepancy = sample_mapping.DurationFromLength(
      largest_interval_discrepancy.discrepancy);
  largest_interval_discrepancy.begin =
      sample_mapping.TimeFromNormalized(largest_interval_discrepancy.begin);
  largest_interval_discrepancy.end =
      sample_mapping.TimeFromNormalized(largest_interval_discrepancy.end);

  return largest_interval_discrepancy;
}

template <class ContainerType>
IntervalDiscrepancy AbsoluteTimestampDiscrepancy(
    const ContainerType& timestamps) {
  return AbsoluteTimestampDiscrepancy(timestamps.begin(), timestamps.end());
}

}  // namespace analytics
}  // namespace ion

#endif  // ION_ANALYTICS_DISCREPANCY_H_