6 Replies Latest reply: Jun 15, 2010 3:14 AM by YoungWinston RSS

    NavigableSet and NavigableMap might compare to a wider class of Objects

    843793
      I have a mutable and an immutable class describing the same kind of object Foo.
      Since all subclasses of an immutable class ought to be immutable, I have created a class MutableFoo and subclass it as ImmutableFoo.
      The immutable subclass throws an exception whenever a setter is invoked, by overriding all setters.

      The Foos have a natural order relation. Now I need to store them in a NavigableSet.
      Since I do not want the order to change once the set has been set up, I define
      NavigableSet fooSet = new TreeSet<ImmutableFoo>()
      and fill it with some ImmutableFoos, this way guaranteeing that my Foos cannot be modified, destroying the given order and making fooSet invalid.

      Now I am given an object mutableFoo of class MutableFoo (some kind of "Pointer") and want to be calling
      fooSet.higher(mutableFoo)
      and
      fooSet.lower(mutableFoo).
      Obviously, this is not possible, since higher() and lower() are declared with an argument of the same class as the set entries in the NavigableSet interface. The only way to do this is
      fooSet.higher(new ImmutableFoo(mutableFoo))
      resp.
      fooSet.lower(new ImmutableFoo(mutableFoo)),
      with the obvious performance penalites (I have assumed that there is a copy constructor).

      A possible solution would be to subclass TreeSet<MutableFoo> and override the add() methods, only to accept immutable arguments.
      What makes me sad is that basically, everything is there in the NavigableSet - you can even hand over a Comparator which can handle superclasses
      of the set's class. A similar argument can be given for NavigableMap.
      The easiest solution (or am I mistaken?) would be to define a method
      E higher(Comparable<E> e); 
      or the like in the interface NavigableSet<E>. Have I overseen something?
        • 1. Re: NavigableSet and NavigableMap might compare to a wider class of Objects
          EJP
          NavigableSet fooSet = new TreeSet<ImmutableFoo>()
          You mean
          NavigableSet<ImmutableFoo> fooSet = new TreeSet<ImmutableFoo>()
          Now I am given an object mutableFoo of class MutableFoo (some kind of "Pointer") and want to be calling
          fooSet.higher(mutableFoo)
          and
          fooSet.lower(mutableFoo).
          So you need an ImmutableFoo.
          with the obvious performance penalites (I have assumed that there is a copy constructor).
          (a) ImmutableFoo(MutableFoo mf) is not a copy constructor
          (b) performance penalties compared to what?
          • 2. Re: NavigableSet and NavigableMap might compare to a wider class of Objects
            jtahlborn
            Why not just make your set a "NavigableSet<Foo>"?

            Edited by: jtahlborn on Jun 3, 2010 8:22 AM
            • 3. Re: NavigableSet and NavigableMap might compare to a wider class of Objects
              800268
              Better might be NavigabeSet<? extends Foo>. The <? extends> is sometimes explained as 'read-only' - you cannot put anything in because you don't know the type (?), but you can get Foo's out.

              Note that MutableFoo (interface) extending Foo (interface without setters) might make more sense in this case.
              • 4. Re: NavigableSet and NavigableMap might compare to a wider class of Objects
                jtahlborn
                WalterLaan wrote:
                Better might be NavigabeSet<? extends Foo>. The <? extends> is sometimes explained as 'read-only' - you cannot put anything in because you don't know the type (?), but you can get Foo's out.
                thought of that one as well, but i don't think it will work since the OP is trying to invoke the higher()/lower() methods, which are strongly typed.
                Note that MutableFoo (interface) extending Foo (interface without setters) might make more sense in this case.
                yeah, that's a good suggestion.
                • 5. Re: NavigableSet and NavigableMap might compare to a wider class of Objects
                  843793
                  The suggestion to restructure ImmutableFoo and MutableFoo to derive from some common interface Foo is quite nice.
                  However, thinking hard about the problem at hand, I don't like the idea to start allowing mutable elements into the tree set and
                  then disallowing them by some trick etc.

                  I have implemented the following construct to solve the problem:
                  Based on the additional assumption that the order of the Foos depends on a single member field "long orderKey" with package
                  visibility, I have declared a set class (in the same package as the Foo class)
                  public class FooSet extends TreeSet<ImmutableFoo> {
                  
                      // constructor, etc.
                  
                      // private mutable ImmutableFoo
                      private class FooPointer extends ImmutableFoo {
                          public void setOrderKey(long orderKey) {
                              this.orderKey = orderKey;
                          }
                      }
                  
                      // Never to be passed outside.
                      private FooPointer fooPointer = new FooPointer();
                  
                      // new implementation of lower() with different signature, no override
                      public ImmutableFoo lower(MutableFoo mutableFoo) {
                          fooPointer.setOrderKey(mutableFoo.getOrderKey());
                          return lower(fooPointer);
                      }
                  }
                  Since we are in the same package as Foo, the order key may be accessed. We never export FooPointer or the fooPointer out of the class.
                  When we need synchronized access, we have to synchronize by the fooPointer (anyhow, TreeSet is not synchronized).

                  Pro: It works. MutableFoos are simply forbidden in the TreeSet - it seems to me that is clear style.
                  Con: Have to provide implementations for higher(), lower(), floor(), ceiling(), subset(), etc. Works only if there is a simple and short orderKey.

                  Edited by: quantango on Jun 4, 2010 3:07 AM

                  Edited by: quantango on Jun 4, 2010 3:22 AM
                  • 6. Re: NavigableSet and NavigableMap might compare to a wider class of Objects
                    YoungWinston
                    quantango wrote:
                    The suggestion to restructure ImmutableFoo and MutableFoo to derive from some common interface Foo is quite nice.
                    Seems to me that there are two other alternatives to your problem:
                    1. Make MutableFoo a final extension to ImmutableFoo rather than the other way around.
                    2. Make ImmutableFoo a wrapper to a MutableFoo that hides its mutation methods, as opposed to a subclass that has them throw an exception. Seems to me that MutableFoo could also include an 'asImmutable()' method; although with this setup it would still involve creating a new object.

                    Winston