Interval Comparison With Wraparound

From CodeCodex

I was reading the fourth edition of Andrew Tanenbaum’s wonderful Computer Networks book a while back and came across the following routine (page 224, reformatted for clarity):

static boolean between
    seq_nr a,
    seq_nr b,
    seq_nr c
            ((a <= b) && (b < c))
            ((c < a) && (a <= b))
            ((b < c) && (c < a));
  } /*between*/

What this is doing is checking whether the integral value b lies in the interval [a .. c), where it can be equal to a but not to c. The trick lies in the fact that all the values “wraparound” after they hit an upper limit MAX_SEQ, so if a > c, the valid ranges for b become [a ..MAX_SEQ] and, if c > 0, also [0 .. c - 1].

Now, aside from all the unnecessary parentheses, I couldn’t help wondering whether the expression couldn't be simplified in some way, at least getting rid of the need to write each comparison twice.

To start with, here’s another way of writing the expression:

    a <= c ?
        a <= b && b < c
        a <= b || b < c

Now, it so happens that, if a <= c, the comparisons (a <= b) and (b < c) can either or both be true, but they can’t both be false (b can be less than a or greater than or equal to c, but can’t be both at once). And correspondingly, if a > c, the two comparisons can either or both be false, but they can’t both be true.

Therefore, we can change the arms of the conditional to return different values in these impossible cases, without affecting the correctness of the result. If we change the first arm of the conditional from “(a <= b) and (b < c) must both be true” to “(a <= b) and (b < c) must be both true or both false”, and the second arm from “(a <= b) and (b < c) must not be both false” to “(a <= b) and (b < c) must not be both false or both true”, we can rewrite the expression as

    a <= c ?
        a <= b == b < c
        a <= b != b < c

Doesn’t seem like much: all we’ve done is change a “&&” to a “==”, and a “||” to a “!=”. But the two arms of the conditional are now simply logical complements of each other! That is

    a <= c ?
        a <= b == b < c
        !(a <= b == b < c)

Since the selection expression is doing nothing more than negating (or not) the rest of the conditional, this can be simplified to

    a <= b == b < c == a <= c


Or, if you feel happier seeing parentheses around everything:

    ((a <= b) == (b < c)) == (a <= c)

The original expression had 11 operators in it, this one has only 5.

Very nice, but is it short enough? -- Daniel


Assuming that seq_nr is an unsigned type, the way I usually write this is simply

     b-a < c-a

That's three operators and (omitting spaces) 7 characters. It also compiles to better code, as there's only one comparison. 21:28, 31 January 2008 (CST)

Original article posting: [1].