scala/scala — pull request #3322 by rklaehn (2014-01-02 18:55:33+00:00)
Title: SI-6253 HashSet should implement union

Implements of HashSet.union that reuses the two trees as much as
possible when calculating the union of two sets. This leads to significant
performance improvements as well as to much better structural sharing.

There is a comprehensive correctness test for union since there was not a single test
for HashSet.union before. In addition, there are some tests of the desirable
properties of the new implementation (structural sharing and efficiency
regarding calls of key.hashCode.

The other operations diff and intersect, which are conceptually very
similar to union, are also implemented along with comprehensive test cases
for both correctness and structural sharing.

Note that while it appears that there is some code duplication between the
three methods, they are sufficiently different that it is not possible
to merge them into one without sacrificing performance.