IntMap: incorrect behaviour of the union function

[dfurian]

Hi,

The IntMap implementation for the union function seems to present an incorrect behaviour when comparing the rank of the two sets S1 and S2 it's supposed to unite:

• if rank(S1) < rank(S2) then S2 is the taller tree and S1 is appended to its root;
• if their ranks are equal then S1 is appended to S2 and its rank is increased;
• if rank(S1) > rank(S2) then S2 is overwritten onto S1 and used as the taller tree.

The third case seems to contradict the intended behaviour of the union by rank operation, since the set with the highest rank (i.e. S1) is appended to the other.

The issue can be traced to line 64 of IntMap.hs:

63      GT ->
64        let !eqs1 = IM.insert i1 (Info r2 a2) eqs
65            !eqs2 = IM.insert i2 (Link i1) eqs1 in
66        PointSupply next eqs2

Since r2 is the lower rank, the function should not replace p1 with p2's Info; overwriting p2 as a Link to p1 should be enough.