Operator with Ternary Return and Short-Circuit

I want an operator capable of short-circuiting an evaluation on true or false but also having a return that indicates continued testing is needed.

For example, lexicographic string comparison between two strings first and second:

if first[0] < second[0], we can end the comparison by returning true
otherwise, if first[0] > second[0], we can end the comparison by returning false
otherwise, first[0] == second[0] holds, and we need to continue with the second character of both strings.

The trivial solution requires two comparisons:

bool firstIsEarlier(std::string first, std::string second){
    if(first[0] < second[0]){
        return true;
    }else if(first[0] > second[0]){
        return false;
    }
    // first[0] == second[0] holds
    // continue with second character..
}

My hack solution has been to use if-else if blocks and an int which will give me a positive number for true or a negative number for false, a 0 indicates continue testing.

bool firstIsEarlier(std::string first, std::string second){
    if(int i = first[0] - second[0]){
        return i < 0;
    }
    else if(i = first[1] - second[1]){
        return i < 0;
    }
    else if(i = first[2] - second[2]){
        return i < 0;
    }
    return false;
}

So as you can see the only way for me to force the short-circuit is to list each condition in an else if. A good solution would be a way for me to do this all on one line and preserve the short circuit. A great solution would be if there was an operator# to do something like this:

bool firstIsEarlier(std::string first, std::string second){
    return first[0] # second[0] ## first[1] # second[1] ## first[2] < second[2];
}

Solution

You probably should achieve this with

bool firstIsEarlier(std::string first, std::string second) {
    return first < second;
}

or more generally with std::lexicographical_compare.

You can do exactly what you ask with expression templates though, and I'll show you how.

There are a few limitations though:

you can't create new operators, so you have to choose two operators you want to overload: one for the leaf comparisons, and one for the short-circuit combination.

(You could use a single operator if you really wanted, but it'd be (even more) confusing and would require lots of parentheses)
you can't really do this when both operands are primitives. If you could, your code would look like:
```
bool firstIsEarlier(std::string first, std::string second){
    return first[0]^second[0] <<= first[1]^second[1] <<= first[2]^second[2];
}
```
but actually you'd need to wrap your chars in some value container for it to work.

First, we need a simple tri-state type. We can just enumerate it:

enum class TriState {
    True = -1,
    Maybe = 0,
    False = 1
};

Next, we need some thing to represent our first[0]^second[0] leaf expression, which evaluates to our tri-state type:

template <typename LHS, typename RHS>
struct TriStateExpr {
    LHS const &lhs_;
    RHS const &rhs_;

    TriStateExpr(LHS const &lhs, RHS const &rhs) : lhs_(lhs), rhs_(rhs) {}

    operator bool () const { return lhs_ < rhs_; }    
    operator TriState () const {
        return (lhs_ < rhs_ ? TriState::True :
                (rhs_ < lhs_ ? TriState::False : TriState::Maybe)
               );
    }
};

Note that we're just requiring a working operator< for our types - we could generalize this to use an explicit comparator if necessary.

Now, we need the non-leaf part of the expression tree. I'm forcing it to a right-to-left expression tree, so the left-hand expression is always a leaf, and the right-hand expression can be a leaf or a complete sub-tree.

template <typename LLHS, typename LRHS, typename RHS>
struct TriStateShortCircuitExpr {
    TriStateExpr<LLHS, LRHS> const &lhs_;
    RHS const &rhs_;

    TriStateShortCircuitExpr(TriStateExpr<LLHS, LRHS> const &lhs, RHS const &rhs)
        : lhs_(lhs), rhs_(rhs)
    {}

    operator TriState () const {
        TriState ts(lhs_);
        switch (ts) {
        case TriState::True:
        case TriState::False:
            return ts;
        case TriState::Maybe:
            return TriState(rhs_);
        }
    }

    operator bool () const {
        switch (TriState(lhs_)) {
        case TriState::True:
            return true;
        case TriState::False:
            return false;
        case TriState::Maybe:
            return bool(rhs_);
        }
    }
};

Now, you want some syntactic sugar, so we have to choose which operators to overload. I'll use ^ for the leaves (on the grounds that it's like < rotated 90 degrees clockwise):

template <typename LHS, typename RHS>
TriStateExpr<LHS, RHS> operator^ (LHS const &l, RHS const &r) {
    return TriStateExpr<LHS, RHS>(l,r);
}

and <<= for the non-leaves:

template <typename LLHS, typename LRHS, typename RLHS, typename RRHS>
TriStateShortCircuitExpr<LLHS, LRHS, TriStateExpr<RLHS, RRHS>>
    operator<<= (TriStateExpr<LLHS, LRHS> const &l,
                 TriStateExpr<RLHS, RRHS> const &r) {
    return TriStateShortCircuitExpr<LLHS, LRHS, TriStateExpr<RLHS, RRHS>>(l, r);
}

template <typename LLHS, typename LRHS, typename... RARGS>
TriStateShortCircuitExpr<LLHS, LRHS, TriStateShortCircuitExpr<RARGS...>>
    operator<<= (TriStateExpr<LLHS, LRHS> const &l,
                 TriStateShortCircuitExpr<RARGS...> const &r) {
    return TriStateShortCircuitExpr<LLHS, LRHS,
                                    TriStateShortCircuitExpr<RARGS...>>(l, r);
}

The main considerations are that the leaf operator should ideally have higher precedence, and the non-leaf operator should associate right-to-left. If you used a left-to-right associative operator instead, TriStateShortCircuitExpr::operator would recurse down the left-hand-side subtree, which seems inelegant for this application.