Hst hst

Better equality and superset comparisons for intsets

This patch introduces a better algorithm for comparing two sets for

equality or containment. Before, we would check S1 ⊇ S2 by looping

through all of the elements of S2, ensuring that each was in S1.

Since intset::contains isn't constant-time, this superset algorithm

isn't linear.

Now, we exploit the fact that intset's iterators return their elements

in sorted order. We loop through the elements of S1 and S2 at the

same time. If S1's iterator ever “passes” S2's, then we've found an

element of S2 that's not in S1, meaning that S1 ⊉ S2. This algorithm

is linear in the maximum of #S1 and #S2.

We can use a similar algorithm for equality. Before, we checked S1 ==

S2 by checking S1 ⊇ S2 and S2 ⊇ S1. Now, we have a similar loop as

with the superset test, but we abort the loop if either iterator

passes the other.

Finally, the new algorithms are implemented as standalone functions

that take iterators as parameters, rather than directly taking

intsets. This makes them more flexible. The >= and == operators in

intset have been redefined to use the new functions.

http://github.com/dcreager/hst/c...