Extending java.util.Set

Discussion in 'Java' started by Hendrik Maryns, Feb 15, 2006.

  1. -----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-----
     
    Hendrik Maryns, Feb 15, 2006
    #1
    1. Advertising

  2. Hendrik Maryns

    Oliver Wong Guest

    "Hendrik Maryns" <> wrote in message
    news:dsvli3$vob$-tuebingen.de...
    > 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
     
    Oliver Wong, Feb 15, 2006
    #2
    1. Advertising

  3. 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, Feb 15, 2006
    #3
  4. 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.
     
    Stefan Schulz, Feb 15, 2006
    #4
  5. Hendrik Maryns

    Chris Uppal Guest

    Hendrik Maryns wrote:

    > 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
     
    Chris Uppal, Feb 16, 2006
    #5
  6. -----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-----
     
    Hendrik Maryns, Feb 16, 2006
    #6
  7. Hendrik Maryns

    Roedy Green Guest

    On Wed, 15 Feb 2006 17:43:26 +0100, Hendrik Maryns
    <> wrote, quoted or indirectly quoted
    someone who said :

    > 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

    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
     
    Roedy Green, Feb 16, 2006
    #7
  8. "Chris Uppal" <-THIS.org> wrote in message
    news:43f45630$2$1175$...
    > Hendrik Maryns wrote:
    >
    >> 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.


    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.
     
    Mike Schilling, Feb 16, 2006
    #8
  9. Hendrik Maryns

    Chris Uppal Guest

    Mike Schilling wrote:

    [me:]
    > > 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.


    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
     
    Chris Uppal, Feb 16, 2006
    #9
  10. "Chris Uppal" <-THIS.org> wrote in message
    news:43f4d214$0$1172$...
    > Mike Schilling wrote:
    >
    > [me:]
    >> > 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.

    >
    > 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? :)
     
    Mike Schilling, Feb 16, 2006
    #10
  11. Hendrik Maryns

    Chris Uppal Guest

    Mike Schilling wrote:

    > > 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".


    ;-)

    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
     
    Chris Uppal, Feb 17, 2006
    #11
  12. "Chris Uppal" <-THIS.org> wrote in message
    news:43f5cf02$1$1173$...
    > Mike Schilling wrote:
    >
    >> > 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".

    >
    > ;-)
    >
    > 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.
     
    Mike Schilling, Feb 17, 2006
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Zhao
    Replies:
    2
    Views:
    456
    John C. Bollinger
    Oct 24, 2003
  2. Robert Mark Bram
    Replies:
    0
    Views:
    596
    Robert Mark Bram
    Apr 30, 2007
  3. Rakesh
    Replies:
    10
    Views:
    12,182
    Mike Schilling
    Apr 8, 2008
  4. Santha
    Replies:
    0
    Views:
    1,083
    Santha
    Jan 14, 2010
  5. J.Cottingim

    set Bad variable type - SNMP::Util set

    J.Cottingim, Jul 3, 2007, in forum: Perl Misc
    Replies:
    0
    Views:
    104
    J.Cottingim
    Jul 3, 2007
Loading...

Share This Page