Algorithm.h

/*
 * Copyright (C) 2026 Yury Bobylev <bobilev_yury@mail.ru>
 *
 * This program 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, version 3.
 *
 * This program 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
 * this program. If not, see <https://www.gnu.org/licenses/>.
 */
#ifndef ALGORITHM_H
#define ALGORITHM_H
 
#include <algorithm>
#include <omp.h>
#include <vector>

class Algorithm
{
public:
  Algorithm();

  template <class InputIt,
            class T = typename std::iterator_traits<InputIt>::value_type>
  static InputIt
  parallelFind(InputIt start, InputIt end, const T &val)
  {
    InputIt result = end;
#pragma omp parallel
#pragma omp for
    for(InputIt i = start; i < end; i++)
      {
        if(*i == val)
          {
#pragma omp critical
            {
              if(i < result)
                {
                  result = i;
                }
            }
#pragma omp cancel for
          }
      }
 
    return result;
  }

  template <class InputIt, class UnaryPred>
  static InputIt
  parallelFindIf(InputIt start, InputIt end, UnaryPred predicate)
  {
    InputIt res = end;
#pragma omp parallel
#pragma omp for
    for(InputIt i = start; i < end; i++)
      {
        if(predicate(*i))
          {
#pragma omp critical
            {
              if(i < res)
                {
                  res = i;
                }
            }
#pragma omp cancel for
          }
      }
 
    return res;
  }

  template <class InputIt, class UnaryPred>
  static void
  parallelSort(InputIt start, InputIt end, UnaryPred predicate)
  {
    if(end - start < 1)
      {
        return void();
      }
    std::vector<std::tuple<InputIt, InputIt>> parts;
    parts.push_back(std::make_tuple(start, end));
 
    omp_lock_t mtx;
    omp_init_lock(&mtx);
 
    while(parts.size() > 0)
      {
        std::vector<std::tuple<InputIt, InputIt>> l_parts;
#pragma omp parallel
#pragma omp masked
        {
          for(auto it = parts.begin(); it != parts.end(); it++)
            {
#pragma omp task
              {
                InputIt i = std::get<0>(*it);
                InputIt end = std::get<1>(*it);
                std::ptrdiff_t diff = end - i;
                while(diff > 1)
                  {
                    if(predicate(*i, *(end - 1)))
                      {
                        i++;
                      }
                    else
                      {
                        if(diff > 2)
                          {
                            std::swap(*(end - 1), *(end - 2));
                          }
                        std::swap(*i, *(end - 1));
                        end--;
                      }
                    diff = end - i;
                  }
                if(end - 1 - std::get<0>(*it) > 1)
                  {
                    omp_set_lock(&mtx);
                    l_parts.push_back(
                        std::make_tuple(std::get<0>(*it), end - 1));
                    omp_unset_lock(&mtx);
                  }
                if(std::get<1>(*it) - end > 1)
                  {
                    omp_set_lock(&mtx);
                    l_parts.push_back(std::make_tuple(end, std::get<1>(*it)));
                    omp_unset_lock(&mtx);
                  }
              }
            }
        }
        parts = std::move(l_parts);
      }
 
    omp_destroy_lock(&mtx);
  }

  template <class InputIt,
            class T = typename std::iterator_traits<InputIt>::value_type>
  static InputIt
  parallelRemove(InputIt start, InputIt end, const T &val)
  {
#ifndef OMP_REMOVING
    return std::remove(start, end, val);
#else
    start = parallelFind(start, end, val);
    if(start < end)
      {
        T *s = start.base();
        T *e = end.base();
#pragma omp parallel
#pragma omp for ordered
        for(T *i = s + 1; i != e; i++)
          {
            if((*i) != val)
              {
#pragma omp ordered
                {
                  *s = std::move((*i));
                  s++;
                }
              }
          }
        start += s - start.base();
      }
    return start;
#endif
  }

  template <class InputIt, class UnaryPred,
            class T = typename std::iterator_traits<InputIt>::value_type>
  static InputIt
  parallelRemoveIf(InputIt start, InputIt end, UnaryPred predicate)
  {
#ifndef OMP_REMOVING
    return std::remove_if(start, end, predicate);
#else
    start = parallelFindIf(start, end, predicate);
    if(start < end)
      {
        T *s = start.base();
        T *e = end.base();
#pragma omp parallel
#pragma omp for ordered
        for(T *i = s + 1; i != e; i++)
          {
            if(!predicate(*i))
              {
#pragma omp ordered
                {
                  *s = std::move(*i);
                  s++;
                }
              }
          }
        start += s - start.base();
      }
    return start;
#endif
  }
};
 
#endif // ALGORITHM_H