//////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga 2025-2026. Distributed under the Boost
// Software License, Version 1.0. (See accompanying file
// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
//
// See http://www.boost.org/libs/container for documentation.
//
//////////////////////////////////////////////////////////////////////////////
#ifndef BOOST_CONTAINER_EXPERIMENTAL_DETAIL_SEGMENTED_COMMON_ALGO_HPP
#define BOOST_CONTAINER_EXPERIMENTAL_DETAIL_SEGMENTED_COMMON_ALGO_HPP

#ifndef BOOST_CONFIG_HPP
#  include <boost/config.hpp>
#endif

#if defined(BOOST_HAS_PRAGMA_ONCE)
#  pragma once
#endif

#include <boost/container/detail/config_begin.hpp>
#include <boost/container/detail/workaround.hpp>
#include <boost/container/detail/iterator.hpp>
#include <boost/container/experimental/segmented_iterator_traits.hpp>

#include <boost/move/utility_core.hpp>

//Category tag dispatch value-initialises iterator categories and
//seg_is_ra_iterator tests convertibility between them, but std_fwd.hpp only
//forward-declares the std tag types, so they must be completed here.
#include <iterator>

// When defined, segmented algorithms that count elements (e.g. segmented_count,
// segmented_count_if) will use a branchless counting strategy in their
// innermost loops, incrementing the count by the boolean result of the
// predicate rather than testing the predicate result in a branch and conditionally
// incrementing.  This can improve performance on some platforms by avoiding branch mispredictions,
// at the cost of potentially increased instruction count and/or reduced vectorization opportunities.
// 
// However, the optimal strategy is highly platform- and algorithm-specific, so this is disabled by default.
// There are regressions on some algorithms and platforms when this is enabled, and the performance impact
// varies widely across different scenarios.
//
//#define BOOST_CONTAINER_SEGMENTED_COUNT_BRANCHLESS

// Enables random-access leaf specializations for some segmented algorithms
// Defaults to 1; define to 0 before including segmented headers to fall back
// to the generic leaves.
#if !defined(BOOST_CONTAINER_SEGMENTED_ENABLE_RA_SPECIALIZATIONS)
#define BOOST_CONTAINER_SEGMENTED_ENABLE_RA_SPECIALIZATIONS 1
#endif

#define BOOST_CONTAINER_SEGMENTED_DISABLE_PRAGMA_UNROLL
//#define BOOST_CONTAINER_SEGMENTED_ENABLE_PRAGMA_UNROLL

#if defined(BOOST_CONTAINER_SEGMENTED_DISABLE_PRAGMA_UNROLL) && defined (BOOST_CONTAINER_SEGMENTED_ENABLE_PRAGMA_UNROLL)
#error "Cannot define both BOOST_CONTAINER_SEGMENTED_DISABLE_PRAGMA_UNROLL and BOOST_CONTAINER_SEGMENTED_ENABLE_PRAGMA_UNROLL"
#endif

#if !defined(BOOST_CONTAINER_SEGMENTED_DISABLE_PRAGMA_UNROLL) && !defined (BOOST_CONTAINER_SEGMENTED_ENABLE_PRAGMA_UNROLL)
   #if defined(BOOST_CLANG)
      //Let clang decide when to unroll loops, as it can auto-vectorize more aggressively when unrolling is disabled.
      #define BOOST_CONTAINER_SEGMENTED_DISABLE_PRAGMA_UNROLL
   #else
      #define BOOST_CONTAINER_SEGMENTED_ENABLE_PRAGMA_UNROLL
   #endif
#endif

#if defined(BOOST_CONTAINER_SEGMENTED_ENABLE_PRAGMA_UNROLL) && defined(BOOST_CONTAINER_SEGMENTED_DISABLE_PRAGMA_UNROLL)
#error "Can't define both BOOST_CONTAINER_SEGMENTED_ENABLE_PRAGMA_UNROLL and BOOST_CONTAINER_SEGMENTED_DISABLE_PRAGMA_UNROLL"
#elif defined(BOOST_CONTAINER_SEGMENTED_ENABLE_PRAGMA_UNROLL)
   #define BOOST_CONTAINER_SEGMENTED_UNROLL(N) BOOST_CONTAINER_UNROLL(N)
   #define BOOST_CONTAINER_SEGMENTED_AUTO_UNROLL BOOST_CONTAINER_AUTO_UNROLL
#elif defined(BOOST_CONTAINER_SEGMENTED_DISABLE_PRAGMA_UNROLL)
   #define BOOST_CONTAINER_SEGMENTED_UNROLL(N)
   #define BOOST_CONTAINER_SEGMENTED_AUTO_UNROLL
#else
#error "Must define either BOOST_CONTAINER_SEGMENTED_ENABLE_PRAGMA_UNROLL or BOOST_CONTAINER_SEGMENTED_DISABLE_PRAGMA_UNROLL"
#endif

namespace boost {
namespace container {

//! Sentinel whose comparison with any iterator always yields false (not equal).
//! Passes through segmented_remove_if_result_bounded to express an unbounded
//! destination, letting the compiler eliminate the dead destination-full branch.
template<class T1, class T2>
struct segduo
{
   T1 first;
   T2 second;

   BOOST_CONTAINER_FORCEINLINE segduo() {}

   template<class U1, class U2>
   BOOST_CONTAINER_FORCEINLINE segduo(const U1 &f, const U2 &s) : first(f), second(s) {}

   template<class U1, class U2>
   BOOST_CONTAINER_FORCEINLINE segduo(const segduo<U1, U2> &sd) : first(sd.first), second(sd.second) {}
};

template<class T1, class T2, class T3>
struct segtrio
{
   T1 first;
   T2 second;
   T3 third;

   BOOST_CONTAINER_FORCEINLINE segtrio() {}

   template<class U1, class U2, class U3>
   BOOST_CONTAINER_FORCEINLINE segtrio(const U1 &f, const U2 &s, const U3 &t)
      : first(f), second(s), third(t) {}

   template<class U1, class U2, class U3>
   BOOST_CONTAINER_FORCEINLINE segtrio(const segtrio<U1, U2, U3> &sd)
      : first(sd.first), second(sd.second), third(sd.third) {}
};

template<class T1, class T2, class T3, class T4>
struct segquartet
{
   T1 first;
   T2 second;
   T3 third;
   T4 fourth;

   BOOST_CONTAINER_FORCEINLINE segquartet() {}

   template<class U1, class U2, class U3, class U4>
   BOOST_CONTAINER_FORCEINLINE segquartet(const U1 &f, const U2 &s, const U3 &t, const U4 &q)
      : first(f), second(s), third(t), fourth(q) {}

   template<class U1, class U2, class U3, class U4>
   BOOST_CONTAINER_FORCEINLINE segquartet(const segquartet<U1, U2, U3, U4> &sq)
      : first(sq.first), second(sq.second), third(sq.third), fourth(sq.fourth) {}
};

struct unreachable_sentinel_t
{
   template <class It>
   BOOST_CONTAINER_FORCEINLINE friend bool operator==(const It&, unreachable_sentinel_t) { return false; }
   
   template <class It>
   BOOST_CONTAINER_FORCEINLINE friend bool operator==(unreachable_sentinel_t, const It&) { return false; }
   
   template <class It>
   BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const It&, unreachable_sentinel_t) { return true; }
   
   template <class It>
   BOOST_CONTAINER_FORCEINLINE friend bool operator!=(unreachable_sentinel_t, const It&) { return true; }
};

//! Disambiguator tag passed by the dual-RA fast-path overload of certain
//! bounded helpers (e.g. segmented_copy_if_dst_bounded,
//! segmented_remove_copy_if_dst_bounded) when it has decided that the
//! remaining source does not fit the destination capacity and a real
//! bounded scan is required.  The tag's only role is to perturb the
//! signature of the recursive call so that the dual-RA overload itself
//! cannot re-match: only the unrolled / generic terminal overloads remain
//! viable, leaving the random-access category of both iterators intact.
struct dual_ra_skip_t {};

namespace detail_algo {

//! Default less-than function object used by segmented algorithms when the
//! user does not provide an explicit comparator.  Centralised here to avoid
//! duplicating the same struct across every algorithm header.
struct segmented_default_less
{
   template <class T>
   BOOST_CONTAINER_FORCEINLINE
   bool operator()(const T& a, const T& b) const { return a < b; }
};

//! Default equality function object used by segmented algorithms when the
//! user does not provide an explicit binary predicate.  Centralised here to
//! avoid duplicating the same struct across every algorithm header.
struct segmented_default_equal_to
{
   template <class T, class U>
   BOOST_CONTAINER_FORCEINLINE bool operator()(const T& a, const U& b) const { return a == b; }
};

//! Proxy-safe "equal to *it" predicate.  Holds the iterator by value and
//! re-dereferences on every invocation, so a prvalue proxy returned by
//! operator*() only lives for the full expression of the comparison and
//! never outlives it.  This avoids the lifetime hazard of caching *it in
//! a const-reference member (as equal_to_value would).
template <class Iter>
struct equal_to_deref
{
   Iter it_;

   BOOST_CONTAINER_FORCEINLINE explicit equal_to_deref(Iter it)
      : it_(it)
   {}

   template <class U>
   BOOST_CONTAINER_FORCEINLINE bool operator()(const U &u) const
   {  return u == *it_; }
};

template <bool B> struct void_if_true;
template <> struct void_if_true<true> { typedef void type; };

template <class T> struct make_void { typedef void type; };

template <bool, class T = void> struct algo_enable_if_c {};
template <class T> struct algo_enable_if_c<true, T> { typedef T type; };

template <class T, class Enable = void>
struct has_iterator_category { static const bool value = false; };

template <class T>
struct has_iterator_category<T, typename make_void<typename T::iterator_category>::type>
{ static const bool value = true; };

template <class T>
struct constref_generator
{
    const T& value;
    BOOST_CONTAINER_FORCEINLINE explicit constref_generator(const T& v)
       : value(v)
    {}

    BOOST_CONTAINER_FORCEINLINE const T& operator()() const { return value; }
};

//////////////////////////////////////////////////////////////////////////////
// Transfer helper: copy (Move=false) or move (Move=true) a single element.
//////////////////////////////////////////////////////////////////////////////

template <bool> struct transfer_op;
template <> struct transfer_op<false>
{
   template <class D, class S>
   BOOST_CONTAINER_FORCEINLINE static void apply(D& d, S& s) { d = s; }
};
template <> struct transfer_op<true>
{
   template <class D, class S>
   BOOST_CONTAINER_FORCEINLINE static void apply(D& d, S& s) { d = boost::move(s); }
};

//////////////////////////////////////////////////////////////////////////////
// Combined check used by dual-RA fixed-block kernels: both source ranges
// hold at least n elements and the destination has at least n free slots.
// The unreachable_sentinel_t overload drops the destination test, which
// always holds for unbounded output.
//////////////////////////////////////////////////////////////////////////////

template <class RAIter1, class RAIter2, class RADstIter, class Diff>
BOOST_CONTAINER_FORCEINLINE bool seg_srcs_dst_room_at_least
   (RAIter1 first1, RAIter1 last1, RAIter2 first2, RAIter2 last2,
    RADstIter dst_first, RADstIter dst_last, Diff n)
{
   return static_cast<Diff>(last1 - first1) >= n
       && static_cast<Diff>(last2 - first2) >= n
       && static_cast<Diff>(dst_last - dst_first) >= n;
}

template <class RAIter1, class RAIter2, class DstIter, class Diff>
BOOST_CONTAINER_FORCEINLINE bool seg_srcs_dst_room_at_least
   (RAIter1 first1, RAIter1 last1, RAIter2 first2, RAIter2 last2,
    DstIter, unreachable_sentinel_t, Diff n)
{
   return static_cast<Diff>(last1 - first1) >= n
       && static_cast<Diff>(last2 - first2) >= n;
}

//! True when the iterator's category is (convertible to) random access.
template <class It>
struct seg_is_ra_iterator
{
   static const bool value = dtl::is_convertible
      < typename boost::container::iterator_traits<It>::iterator_category
      , std::random_access_iterator_tag >::value;
};

} // namespace detail_algo

//! Detects whether \c Sent is a true sentinel for \c Iter.
//! A sentinel is a type that is not the same as the iterator and
//! does not model an iterator (lacks \c iterator_category).
//! When \c is_sentinel is false, algorithms use the \c (Iter, Iter)
//! overload, avoiding extra template instantiations from mixed
//! iterator types such as \c iterator / \c const_iterator.
template <class Sent, class Iter>
struct is_sentinel
{
   static const bool value = !detail_algo::has_iterator_category<Sent>::value;
};

template <class Iter>
struct is_sentinel<Iter, Iter>
{
   static const bool value = false;
};

namespace detail_algo {

//////////////////////////////////////////////////////////////////////////////
// sent_filter: when [first, last) is closed by a true sentinel
// (Sent != Iter), segment walkers cannot decompose Sent and bidirectional
// algorithms cannot step backwards from it; in that case both the iterator
// category and the segmentation tag are downgraded to
// (std::forward_iterator_tag, non_segmented_iterator_tag) so that algorithms
// route through the flat, forward-only path.  When Sent == Iter, the
// iterator's natural category and segmentation are preserved.
//
// Used by bidirectional/segmented algorithms (e.g. segmented_partition,
// segmented_find_last_if) that need a single dispatch point covering both
// the (Iter, Iter) and (Iter, Sentinel) call signatures.
//////////////////////////////////////////////////////////////////////////////

template <class Iter, class Sent, bool = is_sentinel<Sent, Iter>::value>
struct sent_filter
{
   typedef std::forward_iterator_tag                          cat_t;
   typedef non_segmented_iterator_tag                         seg_t;
};

template <class Iter>
struct sent_filter<Iter, Iter, false>
{
   typedef typename boost::container::iterator_traits<Iter>
      ::iterator_category                                     cat_t;
   typedef typename segmented_iterator_traits<Iter>
      ::is_segmented_iterator                                 seg_t;
};

template <class Iter, class Sent>
struct sent_filter<Iter, Sent, false>
   : public sent_filter<Iter, Iter, false>
{};

// Compile-time metafunction that unwraps a (possibly recursively) segmented
// iterator to its deepest non-segmented `local_iterator` type.
//
//   deepest_local_iterator<It>::type == It                         (non-segmented)
//   deepest_local_iterator<It>::type ==
//      deepest_local_iterator<segmented_iterator_traits<It>::local_iterator>::type
//                                                                   (segmented)
//
// Used by segmented algorithms that need to hold cross-segment state of
// iterator type rather than element type (e.g. a "previous element" pointer
// that survives the boundary between sub-ranges), by reducing that state to a
// single unified type across all levels of recursion.
template <bool IsSeg, class It>
struct deepest_local_iterator_impl;

template <class It>
struct deepest_local_iterator_impl<false, It>
{
   typedef It type;
   BOOST_CONTAINER_FORCEINLINE static type get(It it) { return it; }
};

template <class It>
struct deepest_local_iterator_impl<true, It>
{
   private:

   typedef typename segmented_iterator_traits<It>::local_iterator local_t;
   typedef deepest_local_iterator_impl
      < segmented_iterator_traits<local_t>::is_segmented_iterator::value
      , local_t> next_layer_t;

   public:

   typedef typename next_layer_t::type type;

   BOOST_CONTAINER_FORCEINLINE static typename next_layer_t::type get(It it)
   {  return next_layer_t::get(segmented_iterator_traits<It>::local(it)); }
};

template <class It>
struct deepest_local_iterator
{
   typedef deepest_local_iterator_impl
      < segmented_iterator_traits<It>::is_segmented_iterator::value
      , It> next_layer_t;

   public:

   typedef typename next_layer_t::type type;

   BOOST_CONTAINER_FORCEINLINE static typename next_layer_t::type get(It it)
   {  return next_layer_t::get(it);  }
};

//////////////////////////////////////////////////////////////////////////////
// Bounded iter2 helper: compares source [first1, last1) against
// [first2, last2), stopping when source, iter2, or a mismatch
// is encountered.
// Returns segtrio<SrcIter, Iter2, bool> with the final positions of both
// iterators and the reason the walk stopped.
// Recursively walks iter2 segments when iter2 is segmented.
//
// third is true when the walk ended for a reason the caller cannot resume
// from (a mismatch was found, or the source was consumed), and false when
// only [first2, last2) ran out.  That last case is the only one in which a
// segmented caller advances to its next segment and calls again, so one flag
// is enough to drive the segment loop.  Reporting it here spares the caller
// the two comparisons it would otherwise need to re-derive it, which are the
// very comparisons this helper has just made.
//
// When last2 is unreachable_sentinel_t the segment-boundary check is
// optimised away, giving the same code as an unbounded loop, and third folds
// to a constant true.
//
// Shared by segmented_mismatch and segmented_equal, which differ only in what
// they make of the final positions; the walk itself is the same.
//////////////////////////////////////////////////////////////////////////////

template <class SrcIter, class Sent, class Iter2, class Iter2Sent, class BinaryPred, class Iter2Tag, class SrcCat>
BOOST_CONTAINER_FORCEINLINE
typename algo_enable_if_c<!Iter2Tag::value, segtrio<SrcIter, Iter2, bool> >::type
segmented_iter2_bounded
   (SrcIter first1, Sent last1, Iter2 first2, Iter2Sent last2, BinaryPred pred, Iter2Tag, SrcCat)
{
   typedef segtrio<SrcIter, Iter2, bool> result_t;

   bool stop = true;

   BOOST_CONTAINER_SEGMENTED_UNROLL(4)
   for(; first1 != last1; ++first1) {
      if(first2 == last2) {
         stop = false;
         break;
      }

      if(!pred(*first1, *first2))
         break;
      ++first2;
   }

   return result_t(first1, first2, stop);
}

#if BOOST_CONTAINER_SEGMENTED_ENABLE_RA_SPECIALIZATIONS
template <class RASrcIter, class RAIter2, class BinaryPred>
BOOST_CONTAINER_FORCEINLINE
typename iterator_enable_if_tag
   <RAIter2, std::random_access_iterator_tag, segtrio<RASrcIter, RAIter2, bool> >::type
segmented_iter2_bounded
   (RASrcIter first1, RASrcIter last1, RAIter2 first2, RAIter2 last2, BinaryPred pred,
    const non_segmented_iterator_tag &, const std::random_access_iterator_tag &)
{
   typedef segtrio<RASrcIter, RAIter2, bool> result_t;
   typedef typename iterator_traits<RASrcIter>::difference_type difference_type;
   const difference_type src_n  = last1 - first1;
   const difference_type iter2_n = difference_type(last2 - first2);
   difference_type n = src_n < iter2_n ? src_n : iter2_n;

   bool stop;

   BOOST_CONTAINER_SEGMENTED_UNROLL(4)
   while(n) {
      --n;
      if (!pred(*first1, *first2)) {
         stop = true;
         goto out_path;
      }
      ++first1;
      ++first2;
   }
   //Derived from first1/last1 and not from src_n/iter2_n: comparing the two
   //lengths again would force the min above to be materialised as a value and
   //costs the cmov.
   stop = first1 == last1;

   out_path:
   return result_t(first1, first2, stop);
}
#endif   // BOOST_CONTAINER_SEGMENTED_ENABLE_RA_SPECIALIZATIONS

template <class SrcIter, class Sent, class SegIter2, class BinaryPred, class SrcCat>
segtrio<SrcIter, SegIter2, bool> segmented_iter2_bounded
   (SrcIter first1, Sent last1, SegIter2 first2, SegIter2 last2, BinaryPred pred,
    segmented_iterator_tag, SrcCat)
{
   typedef segmented_iterator_traits<SegIter2>  iter2_traits;
   typedef typename iter2_traits::local_iterator    iter2_local_iterator;
   typedef typename iter2_traits::segment_iterator  iter2_segment_iterator;
   typedef typename segmented_iterator_traits<iter2_local_iterator>::is_segmented_iterator iter2_is_local_seg_t;

   typedef segtrio<SrcIter, SegIter2, bool>              result_t;
   typedef segtrio<SrcIter, iter2_local_iterator, bool>  local_result_t;

   iter2_segment_iterator       sfirst = iter2_traits::segment(first2);
   const iter2_segment_iterator slast  = iter2_traits::segment(last2);

   iter2_local_iterator lb2 = iter2_traits::local(first2);

   for(;;) {
      const bool last_seg = sfirst == slast;
      const iter2_local_iterator le2 = last_seg ? iter2_traits::local(last2) : iter2_traits::end(sfirst);
      {
         const local_result_t r = (segmented_iter2_bounded)
            (first1, last1, lb2, le2, pred, iter2_is_local_seg_t(), SrcCat());
         first1 = r.first;
         if(last_seg || BOOST_UNLIKELY(r.third))
            return result_t(first1, iter2_traits::compose(sfirst, r.second), r.third);
      }

      for(++sfirst; sfirst != slast; ++sfirst) {
         const local_result_t r = (segmented_iter2_bounded)
            (first1, last1, iter2_traits::begin(sfirst), iter2_traits::end(sfirst), pred
            , iter2_is_local_seg_t(), SrcCat());
         first1 = r.first;
         if(BOOST_UNLIKELY(r.third))
            return result_t(first1, iter2_traits::compose(sfirst, r.second), true);
      }

      lb2 = iter2_traits::begin(sfirst);
   }
}

} // namespace detail_algo

} // namespace container
} // namespace boost

#include <boost/container/detail/config_end.hpp>

#endif // BOOST_CONTAINER_EXPERIMENTAL_DETAIL_SEGMENTED_COMMON_ALGO_HPP
