PSet has no set intersection operation

hrldcpr / pcollections

A Persistent Java Collections Library

Other

765 stars 79 forks source link

PSet has no set intersection operation #96

Closed prdoyle closed 2 years ago

prdoyle commented 2 years ago

PSet offers plusAll (set union) and minusAll (set difference) but no set intersection.

I have code that currently uses retainAll (which is set intersection) and I'm not sure how to do it efficiently.

The original Stephen Adams paper only hints at how to implement this, but I think I could give it a shot.

prdoyle commented 2 years ago

I suppose a.intersect(b) could be implemented as a.minusAll(a.minusAll(b)) with the right asymptotic complexity.

hrldcpr commented 2 years ago

Yeah that implementation sounds good I think? Or just iterating over a and checking each element against b, while adding to a new set. (And in either case we iterate on the smaller set, so we get logarithmic on the larger set.) Either way is O(mlgn) I think, not sure if we can do better than that.

[ ] add intersection method to PSet, with a default implementation

prdoyle commented 2 years ago

Ok sounds reasonable. Could even be a default method in the interface if you like those.

hrldcpr commented 2 years ago

Oh yeah good idea, this library only recently switched to Java 8, now we get to use nice things like default!