Add has_unbalanced_marker algorithm

[JohelEGP]

Has unbalanced marker

Interface

template <class I>
struct has_unbalanced_marker_result
{
    bool value;
    RANGES_NO_UNIQUE_ADDRESS I in;

    explicit constexpr operator bool() const noexcept
    {
        return value;
    }

    template <class I2>
    constexpr operator has_unbalanced_marker_result<I2>() const&;

    template <class I2>
    constexpr operator has_unbalanced_marker_result<I2>() &&;
};

template <class I, class S, class T, class Proj = ranges::identity>
constexpr has_unbalanced_marker_result<I> has_unbalanced_marker(
    I first, S last, const T& opening_marker, const T& closing_marker,
    Proj proj = {}) const noexcept;
template <class R, class T, class Proj = ranges::identity>
constexpr has_unbalanced_marker_result<ranges::safe_iterator_t<R>>
has_unbalanced_marker(
    R&& r, const T& opening_marker, const T& closing_marker,
    Proj proj = {}) const noexcept;

Constraints:

For the first form:

• ranges::InputIterator<I> is true,
• ranges::Sentinel<S, I> is true, and
• ranges::IndirectRelation<ranges::equal_to, ranges::projected<I, Proj>, const T*> is true.

For the second form:

• ranges::InputRange<R> is true, and
• ranges::IndirectRelation<ranges::equal_to, ranges::projected<ranges::iterator_t<R>, Proj>, const T*> is true.

Expects: opening_marker is not equal to closing_marker.

Let opening and closing be the number of projected elements that equal opening_marker and closing_marker, respectively, in [first, i + 1) if i is specified and [first, last) otherwise.

Returns: {true, i} for the first iterator i in the range [first, last) for which opening < closing. Otherwise, {opening != closing, last}.

Complexity: At most last - first applications of the projection and no more than twice as many comparisons.

template <class I>
template <class I2>
constexpr has_unbalanced_marker_result<
    I>::operator has_unbalanced_marker_result<I2>() const&;

Constraints: ranges::ConvertibleTo<const I&, I2> is true.

Returns: {value, in}.

template <class I>
template <class I2>
constexpr has_unbalanced_marker_result<
    I>::operator has_unbalanced_marker_result<I2>() &&;

Constraints: ranges::ConvertibleTo<I, I2> is true.

Returns: {value, std::move(in)}.

Possible implementation

template <class I>
struct has_unbalanced_marker_result
{
    bool value;
    I in;

    explicit constexpr operator bool() const noexcept
    {
        return value;
    }

    template <
        class I2,
        std::enable_if_t<ranges::ConvertibleTo<const I&, I2>>* = nullptr>
    constexpr operator has_unbalanced_marker_result<I2>() const&
    {
        return {value, in};
    }

    template <
        class I2, std::enable_if_t<ranges::ConvertibleTo<I, I2>>* = nullptr>
    constexpr operator has_unbalanced_marker_result<I2>() &&
    {
        return {value, std::move(in)};
    }
};

struct has_unbalanced_marker_fn
{
    template <
        class I, class S, class T, class Proj = ranges::identity,
        std::enable_if_t<
            ranges::InputIterator<I> && ranges::Sentinel<S, I> &&
            ranges::IndirectRelation<
                ranges::equal_to, ranges::projected<I, Proj>, const T*>>* =
            nullptr>
    constexpr has_unbalanced_marker_result<I> operator()(
        I first, S last, const T& opening_marker, const T& closing_marker,
        Proj proj = {}) const noexcept
    {
        std::make_signed_t<ranges::iter_difference_t<I>> open_pairs{0};
        for (; first != last; ++first)
        {
            auto&& x{ranges::invoke(proj, *first)};
            if (x == opening_marker)
                ++open_pairs;
            else if (x == closing_marker && open_pairs-- == 0)
                return {true, std::move(first)};
        }
        return {open_pairs != 0, std::move(first)};
    }

    template <
        class R, class T, class Proj = ranges::identity,
        std::enable_if_t<
            ranges::InputRange<R> &&
            ranges::IndirectRelation<
                ranges::equal_to,
                ranges::projected<ranges::iterator_t<R>, Proj>, const T*>>* =
            nullptr>
    constexpr has_unbalanced_marker_result<ranges::safe_iterator_t<R>>
    operator()(
        R&& r, const T& opening_marker, const T& closing_marker,
        Proj proj = {}) const noexcept
    {
        return (*this)(
            ranges::begin(r), ranges::end(r), opening_marker, closing_marker,
            std::move(proj));
    }
};

inline constexpr has_unbalanced_marker_fn has_unbalanced_marker{};

[tower120]

Just for curiosity - what it should do, or better say what it good for? Usage example would be nice.

[JohelEGP]

I use it to assert that some input has balanced pairs of parentheses: https://github.github.com/gfm/#example-505.

[tower120]

I would never guessed that "balanced pairs" means "balanced parentheses"...

"balanced scopes" ?

[JohelEGP]

Perhaps "brackets" would be clearer.

[tower120]

What if that not brackets, but some begin/end markers? But I agree, that brackets clearer than pairs...

[JohelEGP]

has_balanced_markers sounds good to me. But not too much more than has_balanced_brackets.

[tower120]

BTW, if it tests that ALL markers are balanced, it probably should start with "is", not "has" . Like "is_balanced". Or on the contrary - "has_unbalanced_brackets".

Because "has_balanced_brackets" imply that at least some brackets are balanced.

[JohelEGP]

It's true that has might imply that there are some unbalanced markers. But does is really implies that all the markers are balanced? And yes, it's supposed to test that all markers are balanced.

[JohelEGP]

Thank you for helping me improve this.

The iterator in the returned result type is last or the first unbalanced closing_marker. If there was a unbalanced_marker(r, opening_marker, closing_marker) that only returned the iterator, what would you call the algorithm to return unbalanced_marker(r, opening_marker, closing_marker) == end(r)?

[tower120]

contains_unbalanced_marker contains_unbalanced_markers

Or better - has_unbalanced_scope

[JohelEGP]

Those names have the same problem as the prefix has_ in that they imply that not all markers are balanced.

[tower120]

!has_unbalanced_scope = all_scopes_are_balanced if there is no a single unbalanced scope - then all scopes are balanced.

[tower120]

find_open_block(rng, block_start, block_end) -> option<iterator_range(block_begin, block_end)>

[JohelEGP]

That's the best. Thank you. I'll let others chime in on whether to prefer marker or scope, assuming that the project owner is OK with me pushing my algorithms here rather than making my personal algorithm's library.

find_open_block(rng, block_start, block_end) -> option<iterator_range(block_begin, block_end)>

Are you proposing a generalization?

[tower120]

Are you proposing a generalization?

Hmm... that probably would be separate algorithm.

template<
    class Rng, 
    class Start, class End, 
    class StartProj = ident, class EndProj = ident, 
    class StartComparator = default_equal, class EndComparator = default_equal>
auto /* sequence of not closed (unbalanced) blocks */
find_open_blocks(
    Rng&& range, 
    const Start& block_start, const End& block_end,
    StartProj start_proj = StartProj{}, EndProj end_proj = EndProj{},
    StartComparator start_comp = StartComparator{}, EndComparator end_comp = EndComparator{}
)

Usage:

std::string str = "[ Hello [World [[!!!] ]"
auto open_blocks = find_open_blocks(str, '[', ']');
// Output:
// "[Hello ... ]"
// "[World ... ]"

That would require ForwardRange and temporary std::stack<Iterator> to track curently opened blocks.

---

Which in turns ....

// return range of custom ranges:
// struct Block{ iterator begin();  iterator end();  bool is_open(); } 
auto blocks = find_blocks(str, '[', ']');
bool all_blocks_closed = contains(find_blocks(str, '[', ']'), true, &Block::is_open);

---

Which probably is not what you want.... Because this begin to look like a parser...