TrackOrderingTSP.hpp

/*
  Copyright 2026 Equinor ASA.

  This file is part of the Open Porous Media project (OPM).

  OPM is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  OPM is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with OPM.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef OPM_TRACK_ORDERING_TSP_HPP
#define OPM_TRACK_ORDERING_TSP_HPP

#include <algorithm>
#include <compare>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <initializer_list>
#include <span>
#include <type_traits>
#include <vector>

namespace Opm {
    class Connection;
} // namespace Opm

namespace Opm {

class TrackOrderingTSP
{
public:
    struct TrackCostWeights
    {
        double w_ij {1.0};

        double w_k {0.5};

        double w_z {0.05};

        double w_dir {0.25};

        double z_to_ij_scale {0.05};

        [[nodiscard]] constexpr bool isValid() const noexcept
        {
            auto&& [ij, k, z, dir, z_scale] = *this;

            []<typename... Ts>(Ts&&...) {
                static_assert((std::same_as<double, std::decay_t<Ts>> && ...),
                              "TrackCostWeights must only contain double members.");
            }(ij, k, z, dir, z_scale);

            const auto all_nonneg = std::ranges::
                all_of(std::initializer_list {ij, k, z, dir, z_scale},
                       [](const auto w) { return w >= 0.0; });

            // Note: z_scale (z_to_ij_scale) is intentionally omitted from
            // the check that at least one weight is positive.  It is not a
            // direct cost weight but rather a scale factor.  If only the
            // z_scale is positive, the edge cost function would be
            // identically zero and thus not well-defined.  The z_scale must
            // still be non-negative, but that requirement is enforced by
            // the all_nonneg check.
            return all_nonneg
                && std::ranges::any_of(std::initializer_list {ij, k, z, dir},
                                       [](const auto w) { return w > 0.0; });
        }
    };

    TrackOrderingTSP(int headI, int headJ);

    TrackOrderingTSP& numberOfStartPoints(std::size_t numStarts);

    std::vector<std::size_t>
    order(std::span<const Connection> connections) const;

    std::vector<std::size_t>
    order(std::span<const Connection> connections,
          const TrackCostWeights&     weights) const;

private:
    struct CandidateStart
    {
        std::int_least64_t ijdist2 {};

        double zdiff {};

        std::size_t index {};

        auto operator<=>(const CandidateStart&) const = default;
    };

    int headI_{};

    int headJ_{};

    std::size_t numStartPoints_{1};

    std::vector<CandidateStart>
    determineStartPoints(std::span<const Connection> connections) const;
};

} // namespace Opm

#endif // OPM_TRACK_ORDERING_TSP_HPP