binning.hpp

/*
 * This file is part of libtcspc
 * Copyright 2019-2026 Board of Regents of the University of Wisconsin System
 * SPDX-License-Identifier: MIT
 */
 
#pragma once
 
#include "arg_wrappers.hpp"
#include "common.hpp"
#include "context.hpp"
#include "histogram_events.hpp"
#include "int_arith.hpp"
#include "int_types.hpp"
#include "introspect.hpp"
#include "numeric_traits.hpp"
#include "processor.hpp"
 
#include <algorithm>
#include <cassert>
#include <concepts>
#include <cstddef>
#include <functional>
#include <iterator>
#include <limits>
#include <optional>
#include <span>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <vector>
 
namespace tcspc {

template <typename T, typename Event, typename Datapoint>
concept data_mapper_for =
    std::move_constructible<T> && requires(T const &m, Event const &e) {
        { m(e) } -> std::same_as<Datapoint>;
    };

template <typename T, typename Datapoint, typename BinIndex>
concept bin_mapper_for =
    std::move_constructible<T> && requires(T &m, Datapoint d) {
        { m(d) } -> std::same_as<std::optional<BinIndex>>;
    };
 
namespace internal {
 
template <typename Event, typename NumericTraits, typename DataMapper,
          typename Downstream>
    requires data_mapper_for<DataMapper, Event,
                             typename NumericTraits::datapoint_type> &&
             processor<Downstream, datapoint_event<NumericTraits>>
class map_to_datapoints {
    DataMapper mapper;
 
    Downstream downstream;
 
  public:
    explicit map_to_datapoints(DataMapper mapper, Downstream downstream)
        : mapper(std::move(mapper)), downstream(std::move(downstream)) {}
 
    [[nodiscard]] auto introspect_node() const -> processor_info {
        return processor_info(this, "map_to_datapoints");
    }
 
    [[nodiscard]] auto introspect_graph() const -> processor_graph {
        return downstream.introspect_graph().push_entry_point(this);
    }
 
    void handle(Event const &event) {
        downstream.handle(
            datapoint_event<NumericTraits>{std::invoke(mapper, event)});
    }
 
    // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved)
    void handle(Event &&event) { handle(static_cast<Event const &>(event)); }
 
    template <typename OtherEvent>
        requires handler_for<Downstream, std::remove_cvref_t<OtherEvent>>
    void handle(OtherEvent &&event) {
        downstream.handle(std::forward<OtherEvent>(event));
    }
 
    void flush() { downstream.flush(); }
};
 
} // namespace internal

template <typename Event, typename NumericTraits = default_numeric_traits,
          typename DataMapper, typename Downstream>
auto map_to_datapoints(DataMapper mapper, Downstream downstream) {
    return internal::map_to_datapoints<Event, NumericTraits, DataMapper,
                                       Downstream>(std::move(mapper),
                                                   std::move(downstream));
}

template <typename NumericTraits = default_numeric_traits>
class difftime_data_mapper {
  public:
    template <typename Event>
    auto operator()(Event const &event) const
        -> NumericTraits::datapoint_type {
        static_assert(
            internal::representable_in<decltype(event.difftime),
                                       typename NumericTraits::datapoint_type>,
            "difftime_data_mapper does not allow narrowing conversion");
        return event.difftime;
    }
};

template <typename NumericTraits = default_numeric_traits>
class count_data_mapper {
  public:
    template <typename Event>
    auto operator()(Event const &event) const
        -> NumericTraits::datapoint_type {
        static_assert(
            internal::representable_in<decltype(event.count),
                                       typename NumericTraits::datapoint_type>,
            "count_data_mapper does not allow narrowing conversion");
        return event.count;
    }
};

template <typename NumericTraits = default_numeric_traits>
class channel_data_mapper {
  public:
    template <typename Event>
    auto operator()(Event const &event) const
        -> NumericTraits::datapoint_type {
        static_assert(
            internal::representable_in<decltype(event.channel),
                                       typename NumericTraits::datapoint_type>,
            "channel_data_mapper does not allow narrowing conversion");
        return event.channel;
    }
};
 
namespace internal {
 
template <typename NumericTraits, typename BinMapper, typename Downstream>
    requires bin_mapper_for<BinMapper, typename NumericTraits::datapoint_type,
                            typename NumericTraits::bin_index_type> &&
             processor<Downstream, bin_increment_event<NumericTraits>>
class map_to_bins {
    static_assert(with_datapoint_type<NumericTraits>);
    static_assert(with_bin_index_type<NumericTraits>);
 
    BinMapper bin_mapper;
    Downstream downstream;
 
  public:
    explicit map_to_bins(BinMapper bin_mapper, Downstream downstream)
        : bin_mapper(std::move(bin_mapper)),
          downstream(std::move(downstream)) {}
 
    [[nodiscard]] auto introspect_node() const -> processor_info {
        return processor_info(this, "map_to_bins");
    }
 
    [[nodiscard]] auto introspect_graph() const -> processor_graph {
        return downstream.introspect_graph().push_entry_point(this);
    }
 
    template <typename NT> void handle(datapoint_event<NT> const &event) {
        static_assert(std::is_same_v<typename NT::datapoint_type,
                                     typename NumericTraits::datapoint_type>);
        auto bin = std::invoke(bin_mapper, event.value);
        if (bin)
            downstream.handle(bin_increment_event<NumericTraits>{bin.value()});
    }
 
    // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved)
    template <typename NT> void handle(datapoint_event<NT> &&event) {
        handle(static_cast<datapoint_event<NT> const &>(event));
    }
 
    template <typename OtherEvent>
        requires handler_for<Downstream, std::remove_cvref_t<OtherEvent>>
    void handle(OtherEvent &&event) {
        downstream.handle(std::forward<OtherEvent>(event));
    }
 
    void flush() { downstream.flush(); }
};
 
} // namespace internal

template <typename NumericTraits = default_numeric_traits, typename BinMapper,
          typename Downstream>
auto map_to_bins(BinMapper bin_mapper, Downstream downstream) {
    return internal::map_to_bins<NumericTraits, BinMapper, Downstream>(
        std::move(bin_mapper), std::move(downstream));
}

template <unsigned NDataBits, unsigned NHistoBits, bool Flip = false,
          typename NumericTraits = default_numeric_traits>
struct power_of_2_bin_mapper {
    static_assert(with_datapoint_type<NumericTraits>);
    static_assert(with_bin_index_type<NumericTraits>);
    static_assert(NHistoBits <= 64); // Assumption made below.
    static_assert(NDataBits >= NHistoBits);
    static_assert(NDataBits <=
                  8 * sizeof(typename NumericTraits::datapoint_type));
    static_assert(NHistoBits <=
                  8 * sizeof(typename NumericTraits::bin_index_type));
    // Bin indices are always non-negative.
    static_assert(std::is_unsigned_v<typename NumericTraits::bin_index_type> ||
                  NHistoBits <
                      8 * sizeof(typename NumericTraits::bin_index_type));

    [[nodiscard]] auto n_bins() const -> std::size_t {
        return std::size_t{1} << NHistoBits;
    }

    auto operator()(NumericTraits::datapoint_type datapoint) const
        -> std::optional<typename NumericTraits::bin_index_type> {
        using datapoint_type = NumericTraits::datapoint_type;
        using bin_index_type = NumericTraits::bin_index_type;
 
        static constexpr int shift = NDataBits - NHistoBits;
        static_assert(shift <= 8 * sizeof(datapoint_type)); // Ensured above.
        if constexpr (shift == 8 * sizeof(datapoint_type))
            return bin_index_type{0}; // Shift would be UB.
 
        // Convert to unsigned (if necessary) _after_ the shift so that
        // negative datapoints are mapped to indices above max.
        auto const shifted = internal::ensure_unsigned(datapoint >> shift);
        static constexpr auto max_bin_index = static_cast<bin_index_type>(
            NHistoBits == 64 ? std::numeric_limits<u64>::max()
                             : (u64(1) << NHistoBits) - 1);
        if (shifted > max_bin_index)
            return std::nullopt;
 
        auto const bin_index = static_cast<bin_index_type>(shifted);
        if constexpr (Flip)
            return static_cast<bin_index_type>(max_bin_index - bin_index);
        else
            return bin_index;
    }
};

template <typename NumericTraits = default_numeric_traits>
class linear_bin_mapper {
    NumericTraits::datapoint_type off;
    NumericTraits::datapoint_type bwidth;
    NumericTraits::bin_index_type max_index;
    bool clamp;
 
    static_assert(with_datapoint_type<NumericTraits>);
    static_assert(with_bin_index_type<NumericTraits>);
 
    // Assumptions used by implementation.
    static_assert(sizeof(typename NumericTraits::datapoint_type) <=
                  sizeof(u64));
    static_assert(sizeof(typename NumericTraits::bin_index_type) <=
                  sizeof(u64));
 
  public:
    explicit linear_bin_mapper(
        arg::offset<typename NumericTraits::datapoint_type> offset,
        arg::bin_width<typename NumericTraits::datapoint_type> bin_width,
        arg::max_bin_index<typename NumericTraits::bin_index_type>
            max_bin_index,
        arg::clamp<bool> clamp = arg::clamp{false})
        : off(offset.value), bwidth(bin_width.value),
          max_index(max_bin_index.value), clamp(clamp.value) {
        if (bwidth == 0)
            throw std::invalid_argument(
                "linear_bin_mapper bin_width must not be zero");
        if (max_index < 0)
            throw std::invalid_argument(
                "linear_bin_mapper max_bin_index must not be negative");
    }

    [[nodiscard]] auto n_bins() const -> std::size_t {
        return std::size_t(max_index) + 1;
    }

    auto operator()(NumericTraits::datapoint_type datapoint) const
        -> std::optional<typename NumericTraits::bin_index_type> {
        using bin_index_type = NumericTraits::bin_index_type;
 
        if (bwidth < 0 ? datapoint > off : datapoint < off)
            return clamp ? std::make_optional(bin_index_type{0})
                         : std::nullopt;
        // Note we always divide non-negative by positive or non-positive by
        // negative, to avoid being affected by truncation toward zero.
        auto const scaled = (datapoint - off) / bwidth;
        assert(scaled >= 0);
        if (u64(scaled) > u64(max_index))
            return clamp ? std::make_optional(max_index) : std::nullopt;
        return static_cast<bin_index_type>(scaled);
    }
};

template <typename T> class unique_bin_mapper_accessor {
    std::function<std::vector<T>()> values_fn;
 
  public:
    template <typename Func>
    explicit unique_bin_mapper_accessor(Func values_func)
        : values_fn(values_func) {}

    auto values() -> std::vector<T> { return values_fn(); }
};

template <typename NumericTraits = default_numeric_traits>
class unique_bin_mapper {
    using datapoint_type = NumericTraits::datapoint_type;
    using bin_index_type = NumericTraits::bin_index_type;
    bin_index_type max_index;
    std::vector<datapoint_type> values;
    access_tracker<unique_bin_mapper_accessor<datapoint_type>> trk;
 
  public:
    explicit unique_bin_mapper(
        access_tracker<
            unique_bin_mapper_accessor<typename NumericTraits::datapoint_type>>
            &&tracker,
        arg::max_bin_index<typename NumericTraits::bin_index_type>
            max_bin_index)
        : max_index(max_bin_index.value), trk(std::move(tracker)) {
        if (max_index < 0)
            throw std::invalid_argument(
                "unique_bin_mapper max_bin_index must not be negative");
        trk.register_accessor_factory([](auto &tracker) {
            auto *self =
                LIBTCSPC_OBJECT_FROM_TRACKER(unique_bin_mapper, trk, tracker);
            return unique_bin_mapper_accessor<datapoint_type>(
                [self] { return self->values; });
        });
    }

    [[nodiscard]] auto n_bins() const -> std::size_t {
        return std::size_t(max_index) + 1;
    }

    auto operator()(NumericTraits::datapoint_type datapoint)
        -> std::optional<typename NumericTraits::bin_index_type> {
        auto it = std::find(values.begin(), values.end(), datapoint);
        if (it == values.end()) {
            values.push_back(datapoint);
            it = std::prev(values.end());
        }
        auto idx = std::distance(values.begin(), it);
        return u64(idx) <= u64(max_index)
                   ? std::make_optional(bin_index_type(idx))
                   : std::nullopt;
    }
};
 
namespace internal {
 
template <typename StartEvent, typename StopEvent, typename NumericTraits,
          typename Downstream>
class cluster_bin_increments {
    static_assert(
        processor<Downstream, bin_increment_cluster_event<NumericTraits>>);
 
    bool in_cluster = false;
    std::vector<typename NumericTraits::bin_index_type> cur_cluster;
 
    Downstream downstream;
 
  public:
    explicit cluster_bin_increments(Downstream downstream)
        : downstream(std::move(downstream)) {}
 
    [[nodiscard]] auto introspect_node() const -> processor_info {
        return processor_info(this, "cluster_bin_increments");
    }
 
    [[nodiscard]] auto introspect_graph() const -> processor_graph {
        return downstream.introspect_graph().push_entry_point(this);
    }
 
    template <typename NT> void handle(bin_increment_event<NT> const &event) {
        static_assert(std::is_same_v<typename NT::bin_index_type,
                                     typename NumericTraits::bin_index_type>);
        if (in_cluster)
            cur_cluster.push_back(event.bin_index);
    }
 
    void handle(StartEvent const & /* event */) {
        cur_cluster.clear();
        in_cluster = true;
    }
 
    void handle(StopEvent const & /* event */) {
        if (in_cluster) {
            auto const e = bin_increment_cluster_event<NumericTraits>{
                ad_hoc_bucket(std::span(cur_cluster))};
            downstream.handle(e);
            in_cluster = false;
        }
    }
 
    // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved)
    template <typename NT> void handle(bin_increment_event<NT> &&event) {
        handle(static_cast<bin_increment_event<NT> const &>(event));
    }
 
    // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved)
    void handle(StartEvent &&event) {
        handle(static_cast<StartEvent const &>(event));
    }
 
    // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved)
    void handle(StopEvent &&event) {
        handle(static_cast<StopEvent const &>(event));
    }
 
    template <typename OtherEvent>
        requires handler_for<Downstream, std::remove_cvref_t<OtherEvent>>
    void handle(OtherEvent &&event) {
        downstream.handle(std::forward<OtherEvent>(event));
    }
 
    void flush() { downstream.flush(); }
};
 
} // namespace internal

template <typename StartEvent, typename StopEvent,
          typename NumericTraits = default_numeric_traits, typename Downstream>
auto cluster_bin_increments(Downstream downstream) {
    return internal::cluster_bin_increments<StartEvent, StopEvent,
                                            NumericTraits, Downstream>(
        std::move(downstream));
}
 
} // namespace tcspc