Check whether a given boolean function is partitioned (tools/is_partitioned.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2025-05-10 15:13:30+09:00
Include: #include "tools/is_partitioned.hpp"

template <typename T, typename F>
bool is_partitioned(T l, T r, F f);

It returns whether the indices $i$ such that $l \leq i \leq r$ are partitioned with respect to the expression f(i) or !f(i).

Constraints

<T> is a built-in integral type.
$l \leq r$
$f$ accepts T and returns bool.

Time Complexity

It calls f up to $r - l + 1$ times.

License

Author

anqooqie

Verified with

tests/is_partitioned.test.cpp

Code

#ifndef TOOLS_IS_PARTITIONED_HPP
#define TOOLS_IS_PARTITIONED_HPP

#include <cassert>

namespace tools {
  template <typename T, typename F>
  bool is_partitioned(const T l, const T r, const F& f) {
    assert(l <= r);

    if (r - l <= 1) return true;

    const bool f_l = f(l);
    T m;
    for (m = l + 1; m <= r && f(m) == f_l; ++m);
    if (r < m) return true;

    for (++m; m <= r && f(m) != f_l; ++m);
    if (r < m) return true;

    return false;
  }
}

#endif

#line 1 "tools/is_partitioned.hpp"



#include <cassert>

namespace tools {
  template <typename T, typename F>
  bool is_partitioned(const T l, const T r, const F& f) {
    assert(l <= r);

    if (r - l <= 1) return true;

    const bool f_l = f(l);
    T m;
    for (m = l + 1; m <= r && f(m) == f_l; ++m);
    if (r < m) return true;

    for (++m; m <= r && f(m) != f_l; ++m);
    if (r < m) return true;

    return false;
  }
}