ahAlgo.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
 
// Aleph implementation of C++ standard algorithms
// Based on code from GNU ISO C++ Library, Hewlett-Packard and Silicon Graphics
 
#ifndef AHALGO_H
#define AHALGO_H
 
#include <ahAssert.H>
#include <ahUtils.H>
 
namespace Aleph
{
 
using size_type = size_t;
 
// ============================================================================
// Non-Modifying Algorithms
// ============================================================================
 
template <class Itor, class Operation>
inline Operation for_each(Itor beg, const Itor & end, Operation op)
{
  while (beg != end)
    op(*beg++);
  
  return op;
}
 
template<class Itor, class Operation>
[[nodiscard]] inline typename Itor::difference_type
count_if(Itor beg, const Itor & end, Operation op)
{
  typename Itor::difference_type n = 0;
 
  while (beg != end)
    if (op(*beg++))
      ++n;
  
  return n;
}
 
template <class Itor, class T>
[[nodiscard]] inline typename Itor::difference_type
count(const Itor & beg, const Itor & end, const T & value)
{
  return Aleph::count_if(beg, end, Aleph::bind2nd(equal_to<T>(), value));
}
 
template<class Itor, 
         class CompFunc = Aleph::less<typename Itor::value_type>>
[[nodiscard]] inline Itor min_element(Itor beg, const Itor & end, 
                                       CompFunc op = CompFunc())
{
  if (beg == end)
    return end;
 
  Itor min = beg;
  ++beg;
 
  while (beg != end)
    {
      if (op(*beg, *min))
        min = beg;
 
      ++beg;
    }
 
  return min;
}
 
template<class Itor, 
         class CompFunc = Aleph::greater<typename Itor::value_type>>
[[nodiscard]] inline Itor max_element(const Itor& beg, const Itor& end, 
                                       CompFunc op = CompFunc())
{
  return Aleph::min_element(beg, end, op);
}
 
template<class Itor, class UnaryPredicate>
[[nodiscard]] inline Itor find_if(Itor beg, const Itor & end, UnaryPredicate op)
{
  while (beg != end and not op(*beg))
    ++beg;
 
  assert(beg == end or op(*beg));
 
  return beg;
} 
 
template<class Itor, class T>
[[nodiscard]] inline Itor find(const Itor & beg, const Itor & end, const T & value)
{
  return Aleph::find_if(beg, end, Aleph::bind2nd(Aleph::equal_to<T>(), value));
}
 
template<class Itor, class Size, class T, 
         class BinaryPredicate = Aleph::equal_to<T>>
[[nodiscard]] inline Itor search_n(Itor            beg, 
                                    const Itor &    end, 
                                    Size            count, 
                                    const T &       value, 
                                    BinaryPredicate op = BinaryPredicate())
{
  if (count <= 0 or beg == end)
    return end;
 
  Size i = 0;
  Itor first;
 
  while (beg != end and i < count)
    {
      if (op(*beg, value))
        {
          if (i == 0)
            first = beg;
          ++i;
        }
      else
        i = 0;
    
      ++beg;
    }
 
  if (i == count)
    return first;
 
  return end;
}
 
template<class Itor1, class Itor2, 
         class BinaryPredicate = Aleph::equal_to<typename Itor1::value_type>>
[[nodiscard]] inline Itor1 search(Itor1 beg, const Itor1 & end, 
                                   Itor2 searchBeg, const Itor2 & searchEnd, 
                                   BinaryPredicate op = BinaryPredicate())
{
  if (beg == end or searchBeg == searchEnd)
    return end;
 
  Itor1 first;
  Itor2 pivot = searchBeg;
  int count = 0;
 
  while (beg != end and pivot != searchEnd)
    { 
      if (op(*beg, *pivot))
        {
          if (count == 0)
            first = beg;
    
          ++pivot;
          ++count;
        }
      else
        {
          pivot = searchBeg;
          count = 0;
        }
 
      ++beg;
    }
  
  if (pivot == searchEnd)
    return first;
 
  return end;
}
 
template<class Itor1, class Itor2, 
         class BinaryPredicate = Aleph::equal_to<typename Itor1::value_type>>
[[nodiscard]] inline Itor1 find_end(Itor1 beg, Itor1 end, 
                                     Itor2 searchBeg, Itor2 searchEnd, 
                                     BinaryPredicate op = BinaryPredicate())
{
  if (beg == end or searchBeg == searchEnd)
    return end;
 
  Itor1 ret_val = end;
  while (true)
    {
      Itor1 new_ret = search(beg, end, searchBeg, searchEnd, op);
      if (new_ret == end)
        return ret_val;
      else
        {
          ret_val = new_ret;
          beg = new_ret;
          ++beg;
        }
    }
}
 
template<class Itor1, class Itor2, 
         class BinaryPredicate = Aleph::equal_to<typename Itor1::value_type>>
[[nodiscard]] inline Itor1 find_first_of(const Itor1& beg, const Itor1& end, 
                                          Itor2 searchBeg, const Itor2& searchEnd, 
                                          BinaryPredicate op = BinaryPredicate())
{
  while (searchBeg != searchEnd)
    {
      Itor1 current = beg;
 
      while (current != end)
        {
          if (op(*current, *searchBeg))
            return current;
 
          ++current;
        }
 
      ++searchBeg;
    }
  
  return end;
}
 
template<class Itor, 
         class BinaryPredicate = Aleph::equal_to<typename Itor::value_type>>
[[nodiscard]] inline Itor adjacent_find(Itor beg, const Itor & end, 
                                         BinaryPredicate op = BinaryPredicate())
{
  if (beg == end)
    return end;
 
  Itor next(beg);
  ++next;
 
  while (next != end)
    {
      if (op(*beg, *next))
        return beg;
 
      ++beg;
      ++next;
    }
 
  return end;
}
 
template <class Itor1, class Itor2, 
          class BinaryPredicate = Aleph::equal_to<typename Itor1::value_type>>
[[nodiscard]] inline bool equal(Itor1 beg, const Itor1 & end,
                                 Itor2 cmpBeg, BinaryPredicate op = BinaryPredicate())
{
  while (beg != end)
    {
      if (not op(*beg, *cmpBeg))
        return false;
 
      ++beg;
      ++cmpBeg;
    }
 
  return true;
}
 
template <class Itor1, class Itor2, 
          class BinaryPredicate = Aleph::equal_to<typename Itor1::value_type>>
[[nodiscard]] inline std::pair<Itor1, Itor2>
mismatch(Itor1 beg, const Itor1& end, 
         Itor2 cmpBeg, 
         BinaryPredicate op = BinaryPredicate())
{
  while (beg != end and op(*beg, *cmpBeg))
    {
      ++beg;
      ++cmpBeg;
    }
  
  return std::make_pair(beg, cmpBeg);
}
 
template <class Itor1, class Itor2, 
          class Comp = Aleph::less<typename Itor1::value_type>>
[[nodiscard]] inline bool lexicographical_compare(Itor1 beg1, const Itor1 & end1, 
                                                   Itor2 beg2, const Itor2 & end2, 
                                                   Comp op = Comp())
{
  while (beg1 != end1 and beg2 != end2) 
    {
      if (op(*beg1, *beg2))
        return true;
      else if (op(*beg2, *beg1))
        return false;
  
      ++beg1;
      ++beg2;
    }
 
  return beg1 == end1 and beg2 != end2;
}
 
 
// ============================================================================
// Modifying Algorithms
// ============================================================================
 
template <class Itor1, class Itor2>
inline Itor2 copy(Itor1 sourceBeg, const Itor1& sourceEnd, Itor2 destBeg)
{
  while (sourceBeg != sourceEnd)
    *destBeg++ = *sourceBeg++;
 
  return destBeg;
}
 
template <class Itor1, class Itor2>
inline Itor2 copy_backward(const Itor1 & sourceBeg, Itor1 sourceEnd, Itor2 destEnd)
{
  while (sourceBeg != sourceEnd)
    *--destEnd = *--sourceEnd;
 
  return destEnd;
}
 
template <class Itor1, class Itor2, class UnaryFunc>
inline Itor2 transform(Itor1 sourceBeg, Itor1 sourceEnd, 
                       Itor2 destBeg, UnaryFunc op)
{
  while (sourceBeg != sourceEnd)
    *destBeg++ = op(*sourceBeg++);
  
  return destBeg;
}
 
template <class Itor1, class Itor2, class Itor3, class BinaryFunc>
inline Itor3 transform(Itor1 source1Beg, Itor1 source1End, 
                       Itor2 source2Beg, 
                       Itor3 destBeg, 
                       BinaryFunc op)
{
  while (source1Beg != source1End)
    *destBeg++ = op(*source1Beg++, *source2Beg++);
 
  return destBeg;
}
 
template <class Itor1, class Itor2>
inline Itor2 swap_ranges(Itor1 beg1, const Itor1& end1, Itor2 beg2)
{
  while (beg1 != end1)
    std::swap(*beg1++, *beg2++);
 
  return beg2;
}
 
template <class Itor, class T>
inline void fill(Itor beg, const Itor& end, const T & value)
{
  while (beg != end)
    *beg++ = value;
}
 
template <class Itor, class T, class Size>
inline void fill_n(Itor beg, Size num, const T & value)
{
  while (num-- > 0)
    *beg++ = value;
} 
 
template <class Itor, class Func>
inline void generate(Itor beg, const Itor& end, Func op)
{
  while (beg != end)
    *beg++ = op();
}
 
template <class Itor, class Size, class Func>
inline void generate_n(Itor beg, Size num, Func op)
{
  while (num-- > 0)
    *beg++ = op();
}
 
template <class Itor, class UnaryPredicate, class T>
inline void replace_if(Itor beg, const Itor& end, 
                       UnaryPredicate op, 
                       const T & value)
{
  while (beg != end)
    {
      if (op(*beg))
        *beg = value;
 
      ++beg;
    }
}
 
template <class Itor, class T>
inline void replace(Itor beg, const Itor& end, 
                    const T & old_value, 
                    const T & new_value)
{
  Aleph::replace_if(beg, end, 
                    Aleph::bind2nd(equal_to<T>(), old_value), new_value);
}
 
template <class Itor1, class Itor2, class UnaryPredicate, class T>
inline Itor2 replace_copy_if(Itor1 sourceBeg, const Itor1& sourceEnd, 
                             Itor2 destBeg, 
                             UnaryPredicate op, 
                             const T & value)
{
  while (sourceBeg != sourceEnd)
    {
      if (op(*sourceBeg))
        *destBeg++ = value;
      else
        *destBeg++ = *sourceBeg;
 
      ++sourceBeg;
    }
 
  return destBeg;
}
 
template <class Itor1, class Itor2, class T>
inline Itor2 replace_copy(const Itor1& sourceBeg, const Itor1& sourceEnd, 
                          Itor2 destBeg, 
                          const T & old_value, 
                          const T & new_value)
{
  return Aleph::replace_copy_if(sourceBeg, sourceEnd, destBeg, 
                                 Aleph::bind2nd(equal_to<T>(), old_value), 
                                 new_value);
}
 
template <class In_Itor, class Out_Itor, class Predicate>
inline Out_Itor remove_copy_if(In_Itor __first, const In_Itor & __last,
                               Out_Itor __result, 
                               Predicate __pred)
{
  for ( ; __first != __last; ++__first)
    if (not __pred(*__first))
      {
        *__result = *__first;
        ++__result;
      }
 
  return __result;
}
 
template<class Fw_Itor, class Predicate>
inline Fw_Itor remove_if(Fw_Itor __first, const Fw_Itor & __last,
                         Predicate __pred)
{
  __first = Aleph::find_if(__first, __last, __pred);
 
  Fw_Itor __i = __first;
 
  if (__first == __last) 
    return __first;
  else
    return Aleph::remove_copy_if(++__i, __last, __first, __pred);
}
 
template<class Fw_Itor, class T>
inline Fw_Itor remove(Fw_Itor __first, const Fw_Itor & __last, 
                      const T & __value)
{
  return Aleph::remove_if(__first, __last, 
                          Aleph::bind2nd(Aleph::equal_to<T>(), __value));
}
 
template<class In_Itor, class Out_Itor, 
         class BinaryPredicate = Aleph::equal_to<typename In_Itor::value_type>>
static inline Out_Itor __unique_copy(In_Itor __first, In_Itor __last,
                                     Out_Itor __result,
                                     BinaryPredicate __binary_pred = BinaryPredicate())
{
  typename In_Itor::value_type __value = *__first;
 
  *__result = __value;
  
  while (++__first != __last)
    if (not __binary_pred(__value, *__first))
      {
        __value = *__first;
        *++__result = __value;
      }
 
  return ++__result;
}
 
template<class In_Itor, class Out_Itor>
inline Out_Itor unique_copy(In_Itor __first, In_Itor __last,
                            Out_Itor __result)
{
  if (__first == __last) 
    return __result;
   
  return Aleph::__unique_copy(__first, __last, __result);
}
 
template <class In_Itor, class Out_Itor, class BinaryPredicate>
inline Out_Itor unique_copy(In_Itor __first, In_Itor __last,
                            Out_Itor __result,
                            BinaryPredicate __binary_pred)
{
  if (__first == __last) 
    return __result;
 
  return Aleph::__unique_copy(__first, __last, __result, __binary_pred);
}
 
template<class Itor,
         class BinaryPredicate = Aleph::equal_to<typename Itor::value_type>>
inline Itor unique(Itor __first, Itor __last, 
                   BinaryPredicate __binary_pred = BinaryPredicate())
{
  // Skip the beginning, if already unique.
  __first = Aleph::adjacent_find(__first, __last, __binary_pred);
 
  if (__first == __last)
    return __last;
 
  // Do the real copy work.
  Itor __dest = __first;
  ++__first;
 
  while (++__first != __last)
    if (not __binary_pred(*__dest, *__first))
      *++__dest = *__first;
 
  return ++__dest;
}
 
 
// ============================================================================
// Mutating Algorithms
// ============================================================================
 
template <class Itor>
inline void reverse(Itor beg, Itor end)
{
  while (beg != end and beg != --end)
    std::swap(*beg++, *end);
}
 
template <class Itor1, class Itor2>
inline Itor2 reverse_copy(Itor1 sourceBeg, Itor1 sourceEnd, Itor2 destBeg)
{
  while (sourceBeg != sourceEnd)
    {
      --sourceEnd;
      *destBeg = *sourceEnd;
      ++destBeg;
    }
 
  return destBeg;
}
 
template <class Itor>
inline void rotate(Itor beg, Itor pos, Itor end)
{
  Aleph::reverse(beg, pos);
  Aleph::reverse(pos, end);
  Aleph::reverse(beg, end);
}
 
template <class Itor1, class Itor2>
inline Itor2 rotate_copy(const Itor1& beg, const Itor1& pos, const Itor1& end, 
                         Itor2 tgt_beg)
{
  return Aleph::copy(beg, pos, Aleph::copy(pos, end, tgt_beg));
}
 
 
// ============================================================================
// Sorted Range Algorithms
// ============================================================================
 
template <class Itor, class T>
[[nodiscard]] inline Itor lower_bound(Itor beg, Itor end, const T& value)
{
  while (beg != end and *beg < value)
    ++beg;
 
  return beg;
}
 
template <class Itor, class T, class BinaryPredicate>
[[nodiscard]] inline Itor lower_bound(Itor beg, Itor end, const T& value, 
                                       BinaryPredicate op)
{
  while (beg != end and op(*beg, value))
    ++beg;
 
  return beg;
}
 
template <class Itor, class T>
[[nodiscard]] inline Itor upper_bound(Itor beg, Itor end, const T& value)
{
  while (beg != end and not (value < *beg))
    ++beg;
 
  return beg;
}
 
template <class Itor, class T, class BinaryPredicate>
[[nodiscard]] inline Itor upper_bound(Itor beg, Itor end, const T& value, 
                                       BinaryPredicate op)
{
  while (beg != end and (op(*beg, value) or not op(value, *beg)))
    ++beg;
 
  return beg;
}
 
template<class Itor, class T>
[[nodiscard]] inline bool binary_search(Itor beg, Itor end, const T& value)
{
  Itor i = Aleph::lower_bound(beg, end, value);
  return i != end and not (value < *i);
}
 
template<class Itor, class T, class BinaryPredicate>
[[nodiscard]] inline bool binary_search(Itor beg, Itor end, const T& value, 
                                         BinaryPredicate op)
{
  Itor i = Aleph::lower_bound(beg, end, value, op);
  return i != end and not op(value, *i);
}
 
template <class Itor, class T>
[[nodiscard]] inline std::pair<Itor, Itor> 
equal_range(Itor beg, Itor end, const T& value)
{
  return std::make_pair(Aleph::lower_bound(beg, end, value),
                        Aleph::upper_bound(beg, end, value));
}
 
template <class Itor, class T, class BinaryPredicate>
[[nodiscard]] inline std::pair<Itor, Itor> 
equal_range(Itor beg, Itor end, const T& value, BinaryPredicate op)
{
  return std::make_pair(Aleph::lower_bound(beg, end, value, op),
                        Aleph::upper_bound(beg, end, value, op));
}
 
template <class Itor1, class Itor2>
[[nodiscard]] inline bool includes(Itor1 beg, Itor1 end, 
                                    Itor2 searchBeg, Itor2 searchEnd)
{
  while (beg != end and searchBeg != searchEnd)
    {
      if (*searchBeg < *beg)
        return false;
      else if (*beg < *searchBeg)
        ++beg;
      else
        {
          ++beg;
          ++searchBeg;
        }
    }
  
  return searchBeg == searchEnd;
}
 
template <class Itor1, class Itor2, class Itor3>
inline Itor3 merge(Itor1 source1Beg, Itor1 source1End, 
                   Itor2 source2Beg, Itor2 source2End, 
                   Itor3 destBeg) 
{
  while (source1Beg != source1End and source2Beg != source2End) 
    {
      if (*source2Beg < *source1Beg) 
        {
          *destBeg = *source2Beg;
          ++source2Beg;
        }
      else 
        {
          *destBeg = *source1Beg;
          ++source1Beg;
        }
      ++destBeg;
    }
  return Aleph::copy(source2Beg, source2End, 
                     Aleph::copy(source1Beg, source1End, destBeg));
}
 
template <class Itor1, class Itor2, class Itor3, class BinaryPredicate>
inline Itor3 merge(Itor1 source1Beg, Itor1 source1End, 
                   Itor2 source2Beg, Itor2 source2End, 
                   Itor3 destBeg, BinaryPredicate op) 
{
  while (source1Beg != source1End and source2Beg != source2End) 
    {
      if (op(*source2Beg, *source1Beg)) 
        {
          *destBeg = *source2Beg;
          ++source2Beg;
        }
      else 
        {
          *destBeg = *source1Beg;
          ++source1Beg;
        }
      ++destBeg;
    }
  return Aleph::copy(source2Beg, source2End, 
                     Aleph::copy(source1Beg, source1End, destBeg));
}
 
 
// ============================================================================
// Numeric Algorithms
// ============================================================================
 
template <class Itor, class T>
[[nodiscard]] inline T accumulate(Itor beg, Itor end, T initValue)
{
  for ( ; beg != end; ++beg)
    initValue = initValue + *beg;
 
  return initValue;
}
 
template <class Itor, class T, class BinaryFunc>
[[nodiscard]] inline T accumulate(Itor beg, Itor end, T initValue, BinaryFunc op)
{
  for ( ; beg != end; ++beg)
    initValue = op(initValue, *beg);
 
  return initValue;
}
 
template <class Itor1, class Itor2, class T>
[[nodiscard]] inline T inner_product(Itor1 beg1, Itor1 end1, Itor2 beg2, T initValue)
{
  for ( ; beg1 != end1; ++beg1, ++beg2)
    initValue = initValue + (*beg1 * *beg2);
 
  return initValue;
}
 
template <class Itor1, class Itor2, class T, class BinaryFunc1, class BinaryFunc2>
[[nodiscard]] inline T inner_product(Itor1 beg1, Itor1 end1, Itor2 beg2, 
                                      T initValue, BinaryFunc1 op1, BinaryFunc2 op2)
{
  for ( ; beg1 != end1; ++beg1, ++beg2)
    initValue = op1(initValue, op2(*beg1, *beg2));
 
  return initValue;
}
 
template <class Itor1, class Itor2>
inline Itor2 partial_sum(Itor1 sourceBeg, Itor1 sourceEnd, Itor2 destBeg)
{
  if (sourceBeg == sourceEnd)
    return destBeg;
 
  typename Itor1::value_type sum = *sourceBeg;
  *destBeg = sum;
  ++sourceBeg;
  ++destBeg;
 
  for ( ; sourceBeg != sourceEnd; ++sourceBeg, ++destBeg)
    {
      sum = sum + *sourceBeg;
      *destBeg = sum;
    }
 
  return destBeg;
}
 
template <class Itor1, class Itor2, class BinaryFunc>
inline Itor2 partial_sum(Itor1 sourceBeg, Itor1 sourceEnd, 
                         Itor2 destBeg, BinaryFunc op)
{
  if (sourceBeg == sourceEnd)
    return destBeg;
 
  typename Itor1::value_type sum = *sourceBeg;
  *destBeg = sum;
  ++sourceBeg;
  ++destBeg;
 
  for ( ; sourceBeg != sourceEnd; ++sourceBeg, ++destBeg)
    {
      sum = op(sum, *sourceBeg);
      *destBeg = sum;
    }
 
  return destBeg;
}
 
template <class Itor1, class Itor2>
inline Itor2 adjacent_difference(Itor1 sourceBeg, Itor1 sourceEnd, Itor2 destBeg)
{
  if (sourceBeg == sourceEnd)
    return destBeg;
 
  typename Itor1::value_type prev = *sourceBeg;
  *destBeg = prev;
  ++sourceBeg;
  ++destBeg;
 
  for ( ; sourceBeg != sourceEnd; ++sourceBeg, ++destBeg)
    {
      typename Itor1::value_type curr = *sourceBeg;
      *destBeg = curr - prev;
      prev = curr;
    }
 
  return destBeg;
}
 
template <class Itor1, class Itor2, class BinaryFunc>
inline Itor2 adjacent_difference(Itor1 sourceBeg, Itor1 sourceEnd, 
                                 Itor2 destBeg, BinaryFunc op)
{
  if (sourceBeg == sourceEnd)
    return destBeg;
 
  typename Itor1::value_type prev = *sourceBeg;
  *destBeg = prev;
  ++sourceBeg;
  ++destBeg;
 
  for ( ; sourceBeg != sourceEnd; ++sourceBeg, ++destBeg)
    {
      typename Itor1::value_type curr = *sourceBeg;
      *destBeg = op(curr, prev);
      prev = curr;
    }
 
  return destBeg;
}
 
} // end namespace Aleph
 
#endif // AHALGO_H