Algorithm.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright (c) OpenGeoSys Community (opengeosys.org)
// SPDX-License-Identifier: BSD-3-Clause
 
#pragma once
 
#include <algorithm>
#include <cassert>
#include <concepts>
#include <optional>
#include <range/v3/algorithm/find_if.hpp>
#include <range/v3/range/concepts.hpp>
#include <range/v3/range/conversion.hpp>
#include <range/v3/view/concat.hpp>
#include <range/v3/view/partial_sum.hpp>
#include <range/v3/view/single.hpp>
#include <set>
#include <string>
#include <typeindex>
#include <typeinfo>
#include <utility>
 
#include "CompilerWorkarounds.h"
#include "Error.h"
 
namespace BaseLib
{
template <typename T>
std::vector<T> excludeObjectCopy(
    std::vector<T> const& src_vec,
    std::vector<std::size_t> const& exclude_positions)
{
    std::vector<T> dest_vec;
    if (exclude_positions.empty())
    {
        dest_vec = src_vec;
        return dest_vec;
    }
 
    assert(exclude_positions.back() < src_vec.size());
 
    std::copy_n(src_vec.cbegin(), exclude_positions[0],
                std::back_inserter(dest_vec));
    for (std::size_t i = 1; i < exclude_positions.size(); ++i)
    {
        std::copy_n(src_vec.cbegin() + exclude_positions[i - 1] + 1,
                    exclude_positions[i] - (exclude_positions[i - 1] + 1),
                    std::back_inserter(dest_vec));
    }
    std::copy(src_vec.cbegin() + exclude_positions.back() + 1, src_vec.cend(),
              std::back_inserter(dest_vec));
 
    return dest_vec;
}
 
template <typename T>
void excludeObjectCopy(std::vector<T> const& src_vec,
                       std::vector<std::size_t> const& exclude_positions,
                       std::vector<T>& dest_vec)
{
    dest_vec = excludeObjectCopy(src_vec, exclude_positions);
}

template <ranges::input_range Range>
ranges::range_reference_t<Range> findElementOrError(
    Range& range,
    std::predicate<ranges::range_reference_t<Range>> auto&& predicate,
    std::invocable auto error_callback)
{
    auto it =
        ranges::find_if(range, std::forward<decltype(predicate)>(predicate));
    if (it == ranges::end(range))
    {
        error_callback();
        OGS_FATAL(
            "Element not found in the input range. The user provided error "
            "callback is meant not to return. That has not happened.");
    }
    return *it;
}

template <typename Map, typename Key, typename Value>
void insertIfKeyUniqueElseError(Map& map, Key const& key, Value&& value,
                                std::string const& error_message)
{
    auto const inserted = map.emplace(key, std::forward<Value>(value));
    if (!inserted.second)
    {  // insertion failed, i.e., key already exists
        OGS_FATAL("{} Key `{}' already exists.", error_message, key);
    }
}

template <typename Map, typename Key>
OGS_NO_DANGLING typename Map::mapped_type& getOrError(
    Map& map, Key const& key, std::string const& error_message)
{
    auto it = map.find(key);
    if (it == map.end())
    {
        if constexpr (std::is_convertible<Key, std::string>::value)
        {
            OGS_FATAL("{:s} Key `{:s}' does not exist.", error_message, key);
        }
        else
        {
            OGS_FATAL("{:s} Key `{:s}' does not exist.", error_message,
                      std::to_string(key));
        }
    }
 
    return it->second;
}

template <typename Map, typename Key>
OGS_NO_DANGLING typename Map::mapped_type const& getOrError(
    Map const& map, Key const& key, std::string const& error_message)
{
    auto it = map.find(key);
    if (it == map.end())
    {
        if constexpr (std::is_convertible<Key, std::string>::value)
        {
            OGS_FATAL("{:s} Key `{:s}' does not exist.", error_message, key);
        }
        else
        {
            OGS_FATAL("{:s} Key `{:s}' does not exist.", error_message,
                      std::to_string(key));
        }
    }
 
    return it->second;
}

template <typename Container, typename Predicate>
OGS_NO_DANGLING typename Container::value_type const& getIfOrError(
    Container const& container,
    Predicate&& predicate,
    std::string const& error_message)
{
    auto it = std::find_if(begin(container), end(container), predicate);
    if (it == end(container))
    {
        OGS_FATAL("Could not find element matching the predicate: {:s}",
                  error_message);
    }
    return *it;
}

template <ranges::input_range Range>
    requires std::totally_ordered<ranges::range_value_t<Range>> &&
             std::copyable<ranges::range_value_t<Range>>
std::vector<ranges::range_value_t<Range>> getDuplicates(Range&& range)
{
    using Element = ranges::range_value_t<Range>;
 
    std::set<Element> seen;
    std::set<Element> duplicates;
    for (auto const& element : range)
    {
        if (!seen.insert(element).second)
        {
            duplicates.insert(element);
        }
    }
 
    return {duplicates.begin(), duplicates.end()};
}

template <typename T>
void makeVectorUnique(std::vector<T>& v)
{
    std::sort(v.begin(), v.end());
    auto it = std::unique(v.begin(), v.end());
    v.erase(it, v.end());
}

template <typename T, class Compare>
void makeVectorUnique(std::vector<T>& v, Compare comp)
{
    std::sort(v.begin(), v.end(), comp);
    auto it = std::unique(v.begin(), v.end());
    v.erase(it, v.end());
}

template <typename ValueType, typename IndexType>
void reorderVector(std::vector<ValueType>& v,
                   std::vector<IndexType> const& order)
{
    std::vector<ValueType> temp_v(v.size());
    temp_v.swap(v);
 
    for (std::size_t i = 0; i < order.size(); i++)
    {
        std::swap(v[i], temp_v[order[i]]);
    }
}
 
template <typename Container>
void uniquePushBack(Container& container,
                    typename Container::value_type const& element)
{
    if (std::find(container.begin(), container.end(), element) ==
        container.end())
    {
        container.push_back(element);
    }
}
 
template <typename Container>
std::optional<typename Container::value_type> findFirstNotEqualElement(
    Container const& container, typename Container::value_type const& element)
{
    auto const it =
        std::find_if_not(container.begin(), container.end(),
                         [&element](typename Container::value_type const& e)
                         { return e == element; });
    return it == container.end() ? std::nullopt : std::make_optional(*it);
}

template <typename Container>
std::size_t findIndex(Container const& container,
                      typename Container::value_type const& element)
{
    auto const it = std::find(container.begin(), container.end(), element);
    if (it == container.end())
    {
        return std::numeric_limits<std::size_t>::max();
    }
    return std::distance(container.begin(), it);
}

template <typename T>
void cleanupVectorElements(std::vector<T*>& items)
{
    for (auto item : items)
    {
        delete item;
    }
    items.clear();
}

template <typename T1, typename... Args>
void cleanupVectorElements(std::vector<T1*>& dependent_items, Args&&... args)
{
    cleanupVectorElements(dependent_items);
    cleanupVectorElements(std::forward<Args>(args)...);
}

template <ranges::range R>
    requires std::is_integral_v<ranges::range_value_t<R>>
std::vector<ranges::range_value_t<R>> sizesToOffsets(R const& sizes)
{
    return ranges::views::concat(
               ranges::views::single(ranges::range_value_t<R>{0}),
               ranges::views::partial_sum(sizes)) |
           ranges::to<std::vector<ranges::range_value_t<R>>>();
}

template <typename List>
constexpr bool any_of(List const& values)
{
    // std::any_of is not constexpr enough in some STLs
    for (auto& value : values)
    {
        if (static_cast<bool>(value))
        {
            return true;
        }
    }
 
    return false;
}

template <typename List>
constexpr bool all_of(List const& values)
{
    // std::all_of is not constexpr enough in some STLs
    for (auto& value : values)
    {
        if (!static_cast<bool>(value))
        {
            return false;
        }
    }
 
    return true;
}

template <typename List>
constexpr bool none_of(List const& values)
{
    return !any_of(values);
}

template <class... Ts>
struct Overloaded : Ts...
{
    using Ts::operator()...;
};
#if defined(__clang__)
#if (__clang_major__ <= 16)
template <class... Ts>
Overloaded(Ts...) -> Overloaded<Ts...>;
#endif
#endif
 
}  // namespace BaseLib