Extending java.util.Set

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Hi,

I am using sets intensively, and have to do a lot of mathematical
manipulations with them, that are not part of the standard API, such as
set intersection, cartesian product (with itself, for arbitrary n, or
with other), and so forth. Now I am wondering whether the best way
would be to extend HashSet, or to keep a reference to a HashSet to store
the elements. In other words, I am not so sure about When Not To Use
Inheritance. This seems like a border case to me.

Related question: is there a nice API which already has this sort of
stuff implemented, open source?

TIA, H.
--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFD81oue+7xMGD3itQRAkD3AJ9UoyA4CKCQ939a26GDz5oKirx8WACfSWx5
qp+hOStCjDTo4blIocyb6aM=
=WFnX
-----END PGP SIGNATURE-----

 

[Oliver Wong]

Hi,

I am using sets intensively, and have to do a lot of mathematical
manipulations with them, that are not part of the standard API, such as
set intersection, cartesian product (with itself, for arbitrary n, or
with other), and so forth. Now I am wondering whether the best way
would be to extend HashSet, or to keep a reference to a HashSet to store
the elements. In other words, I am not so sure about When Not To Use
Inheritance. This seems like a border case to me.

Related question: is there a nice API which already has this sort of
stuff implemented, open source?

Seems to me that the fact that your mathematical concept of a set
(currently) uses a HashSet is an implementation detail, rather than having
to do with the interface.

I would consider extending java.util.Set rather than HashSet, and then
use a HashSet internally for storage. E.g. something like:

<pseudo code>
public class MathSet extends Set {
private HashSet myData;

//methods go here
}
</pseudo code>

In the future, you might find using an array backing works better than a
hashset, or maybe devise your own custom data structure, and so your new Set
type would not behave like a HashSet anymore (e.g. no longer O(1) running
time for certain operations), violating the API.

- Oliver

 

[Stefan Schulz]

Set is an interface, so you'd have to go the following route

public interface MathSet extends Set {

// new methods here
}

And either

public class MathHashSet extends Hashset implements MathSet {
// implementations go here
}

or

public class MathHashSet implements MathSet {

private Set backing = new HashSet();

// implementations go here
}

 

[Stefan Schulz]

What operations are you missing?

Intersection can be modeled easily. a intersect b is simpy

Set r = new HashSet(a);
r.retainAll(b);

Cartesian product actually creates new sets with some tuple type. You'd
need to generate that "tuple type" on the fly, which is far from
trivial, unless you wish to use Pair(Pair(Pair(a,b), c), d)-like
constructs, or lists.

 

[Chris Uppal]

I am using sets intensively, and have to do a lot of mathematical
manipulations with them, that are not part of the standard API, such as
set intersection, cartesian product (with itself, for arbitrary n, or
with other), and so forth. Now I am wondering whether the best way
would be to extend HashSet, or to keep a reference to a HashSet to store
the elements.

I doubt if it makes any difference in this case.

Since you are creating your own set implementation (in the sense of defining an
extended API) you will define your own class, HendriksSet. You may (probably
will) choose to have that implement the java.util.Set interface. So code that
uses the sets will either "know" that they are instances of HendriksSet, or
they will only know that they implement java.util.Set. There is (or shouldn't
be) any reason to use one in a context where concrete Set class from java.util
(such as HashSet) is expected.

That being the case, the inheritance from HashSet (if you choose to go that
route) is irrelevant, and essentially private. For instance you could start
off with an extended set implementation that inherits from HashSet for
convenience, then migrate to a custom extended set implementation (tuned for
O(n) intersection, perhaps) as/when you need it. If that happens then changing
from an implementation which inherits from HashSet to one that doesn't will
impact /no/ other code.

And that's the point.

-- chris

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Stefan Schulz schreef:

Set is an interface, so you'd have to go the following route

public interface MathSet extends Set {

// new methods here
}

And either

public class MathHashSet extends Hashset implements MathSet {
// implementations go here
}

or

public class MathHashSet implements MathSet {

private Set backing = new HashSet();

// implementations go here
}

I see. Of course, an interface is the way to go, and the implementation
is my case, as Chris also pointed out.

Thanks all.
H.

--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFD9GJVe+7xMGD3itQRArenAJ9FIM5Nqa8am3uqT863bv0OuZb9kgCdG6Ql
7S8atDc7HnuxUXdGe/vtl+Q=
=XwWi
-----END PGP SIGNATURE-----

 

[Roedy Green]

Now I am wondering whether the best way
would be to extend HashSet, or to keep a reference to a HashSet to store
the elements. In other words, I am not so sure about When Not To Use
Inheritance. This seems like a border case to me.

There are two other possible approaches to consider to deal with
Pascalian style sets:

java.util.BitSet http://mindprod.com/jgloss/binary.html#BITSET
java.lang.Enumset http://mindprod.com/jgloss/enumset.html

 

[Mike Schilling]

I doubt if it makes any difference in this case.

Since you are creating your own set implementation (in the sense of
defining an
extended API) you will define your own class, HendriksSet. You may
(probably
will) choose to have that implement the java.util.Set interface. So code
that
uses the sets will either "know" that they are instances of HendriksSet,
or
they will only know that they implement java.util.Set. There is (or
shouldn't
be) any reason to use one in a context where concrete Set class from
java.util
(such as HashSet) is expected.

That being the case, the inheritance from HashSet (if you choose to go
that
route) is irrelevant, and essentially private. For instance you could
start
off with an extended set implementation that inherits from HashSet for
convenience, then migrate to a custom extended set implementation (tuned
for
O(n) intersection, perhaps) as/when you need it. If that happens then
changing
from an implementation which inherits from HashSet to one that doesn't
will
impact /no/ other code.

Except code like:

HashSet hs = new HendriksSet();

Which is perverse, but not impossible.

I admit that putting in all the forwarding methods (rather than inheriting
them) is tedious, but I'd probably do that first thing just to avoid such
problems.

 

[Chris Uppal]

Mike Schilling wrote:

[me:]

Except code like:

HashSet hs = new HendriksSet();

Which is perverse, but not impossible.

Well, I did say:

There is (or shouldn't be) any reason to use one in a context
where concrete Set class from java.util (such as HashSet) is
expected.

If there are such contexts (which I doubt) then I think the problems probably
go much deeper than mere inheritance/delegation confusion (unless they are mere
typos). If such contexts /did/ exist, and if they /were/ valid (which I doubt
even more) then Hendryk would have no choice but to extend HashSet...

-- chris

 

[Mike Schilling]

Mike Schilling wrote:

[me:]

Except code like:

HashSet hs = new HendriksSet();

Which is perverse, but not impossible.

Well, I did say:

There is (or shouldn't be) any reason to use one in a context
where concrete Set class from java.util (such as HashSet) is
expected.

Sure, but you're conflating "no reason to do it" with "it won't happen".

Where is it you work, again?

 

[Chris Uppal]

Sure, but you're conflating "no reason to do it" with "it won't happen".

;-)

More accurately: I am conflating "it shouldn't happen" with "if it does then
your code is so badly broken that extending HashSet is the least of your
problems".

(An exaggeration, of course, but I trust you see what I mean).

-- chris

 

[Mike Schilling]

;-)

More accurately: I am conflating "it shouldn't happen" with "if it does
then
your code is so badly broken that extending HashSet is the least of your
problems".

(An exaggeration, of course, but I trust you see what I mean).

Perhaps we were thinking of different situations: I was picturing other
developers using the class, and possibly casting it to HashSet out of
sloppiness and/or sheer perverseness. Not deriving from HashSet in the
first place prevents that, and allows me to change implementations without
breaking any client code.