Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / General / July 2007

Tip: Looking for answers? Try searching our database.

Generics syntax and Comparing Comparables of type ?

Thread view: 
Sideswipe - 11 Jul 2007 18:29 GMT
I am trying to write a RangedMap and when I "genericify" it, it
occurred to me that I am not completely sure how I can Quite express
the syntax. Admittedly I am learning my generics, but the code is
definitely correct when I remove the generics (run main for a test).

Essentially, I want to be able to apply this Map to any Comparable
object such as Date, Integer, String, whatever. Clearly though, the
comparison must be between comparables of the Same Type.

So, Comparable<?> min and Comparable<?> max could both be Integers,
but 1 can't be Integer and the other Date. Maybe the code will explain
better. Anyone have some input?

Christian
http://christian.bongiorno.org

/**
* Date: Jul 9, 2007
* Time: 4:25:18 PM
* This Map allows for a ranged mapping of values. The key can be
anything comparable such
* as Numbers and Dates or Strings
*/

import java.util.TreeMap;
import java.util.Map;

public class RangedMap<RangedKey, V> extends TreeMap<RangedKey, V> {

   public static void main(String[] args) {
       Map<RangedKey, String> testMap = new RangedMap<RangedKey,
String>();
       testMap.put(new RangedKey(50, 60), "Blue");
       testMap.put(new RangedKey(61, 70), "Yellow");
       testMap.put(new RangedKey(71, 80), "Red");

       System.out.println(testMap.get(new RangedKey(55)));
       System.out.println(testMap.get(new RangedKey(67)));
       System.out.println(testMap.get(new RangedKey(73)));

       System.out.println(testMap.get(new RangedKey(1)));
       System.out.println(testMap.get(new RangedKey(90)));

       testMap.put(new RangedKey(62, 80), "Fail");

   }

   public V put(RangedKey key, V value) {
       rangeCheck(key.getMin());
       rangeCheck(key.getMax());

       return super.put(key, value);
   }

   public void putAll(Map<? extends RangedKey, ? extends V> map) {
       for (Map.Entry<? extends RangedKey, ? extends V> entry :
map.entrySet())
           put(entry.getKey(), entry.getValue());
   }

   private void rangeCheck(Comparable<?> c) throws
IllegalArgumentException {
       V val = get(new RangedKey(c));
       if (val != null)
           throw new IllegalArgumentException("range: " + c + "
overlaps with another range and would cause an ambiguous mapping ");
   }

   public static final class RangedKey implements
Comparable<RangedKey> {
       private Comparable<?> min;
       private Comparable<?> max;

       public RangedKey(Comparable<?> single) {
           this.min = single;
           this.max = single;
       }

       public RangedKey(Comparable<?> min, Comparable<?> max) {
           this.min = min;
           this.max = max;
       }

       public int compareTo(RangedKey range) {

           if (this.max.compareTo(range.min) < 0)
               return -1;
           if (this.min.compareTo(range.max) > 0)
               return 1;
           else
               return 0;
       }

       public Comparable<?> getMin() {
           return min;
       }

       public Comparable<?> getMax() {
           return max;
       }

       public String toString() {
           return min + "-" + max;
       }
   }
}
Joshua Cranmer - 11 Jul 2007 22:23 GMT
> I am trying to write a RangedMap and when I "genericify" it, it occurred
> to me that I am not completely sure how I can Quite express the syntax.
[quoted text clipped - 13 lines]
>         private Comparable<?> min;
>         private Comparable<?> max;

This seems suspicious hacking used to avoid rare types. The answer is to
generify RangedKey to RangedKey<T>. A sample of code:

public static final class RangedKey<T extends Comparable<T>> implements
Comparable<RangedKey<T>> {
   private T min;
   private T max;

...

   public int compareTo(RangedKey<T extends Comparable<T>> range) {
       if (this.max.compareTo(range.min) < 0) {
...
Sideswipe - 11 Jul 2007 22:43 GMT
No attempt at hacking at all. I made the changes that you recommended.
The RangedKey is happy with itself now, but the tests produce
unbounded check warnings and the range checking flat out produces
errors. Here is the updated RangeKey class. I admit I don't understand
generics so, I will be studying this code intensely when it compiles
and runs without warnings.

Christian

public static final class RangedKey<T extends Comparable<T>>
implements Comparable<RangedKey<T>> {
       private T min;
       private T max;

       public int compareTo(RangedKey<T> range) {

           if (this.max.compareTo(range.min) < 0)
               return -1;
           if (this.min.compareTo(range.max) > 0)
               return 1;
           else
               return 0;
       }
       public RangedKey(T single) {
           this.min = single;
           this.max = single;
       }

       public RangedKey(T min, T max) {
           this.min = min;
           this.max = max;
       }

       public T getMin() {
           return min;
       }

       public T getMax() {
           return max;
       }

       public String toString() {
           return min + "-" + max;
       }
   }
Roedy Green - 12 Jul 2007 03:04 GMT
On Wed, 11 Jul 2007 21:43:55 -0000, Sideswipe
<christian.bongiorno@gmail.com> wrote, quoted or indirectly quoted
someone who said :

>Here is the updated RangeKey class. I admit I don't understand
>generics so, I will be studying this code intensely when it compiles
>and runs without warnings.

one thing you can do is decompile the code and check out it makes
sense with the generics stripped.

Another route is to implement with some very concrete classes, then
one by one parameterise them.
--
Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com
Ingo R. Homann - 12 Jul 2007 08:19 GMT
Hi,

>         public int compareTo(RangedKey<T> range) {
>
[quoted text clipped - 5 lines]
>                 return 0;
>         }

Note that this will not give you a mathematically correct order of
ranges, because you consider two ranges as equal if only they overlap.
So, that might (!) cause problems (depending on how you use it).

Ciao,
Ingo
Sideswipe - 12 Jul 2007 20:02 GMT
> Hi,
>
[quoted text clipped - 14 lines]
> Ciao,
> Ingo

Well, I specifically want only ranges that overlap to match. I mean,
if I supply 2 ranges of (60,70) (60,70) these are exact matches of
ranges and indeed, I could legally replace what they map too (although
I don't allow it now). However, the clutch part of this working, and
removing the ambiguity of the mapping is to validate the input for
ambiguous mappings, such as: {60,70} {65,72}. The range between
{65,70} can apply to both mappings and so the result is undefined. To
remove this mathematically incorrect situation I remove the case
entirely by validating input.

If I am missing something, please supply a use case that produces an
unexpected result. I certainly wouldn't mind improvements of this
implementation. But, for safety purposes, this map MUST use it's own
range type.
Ingo R. Homann - 13 Jul 2007 10:13 GMT
Hi,

> Well, I specifically want only ranges that overlap to match. I mean,
> if I supply 2 ranges of (60,70) (60,70) these are exact matches of
[quoted text clipped - 10 lines]
> implementation. But, for safety purposes, this map MUST use it's own
> range type.

See the docu for Comparable: "It is strongly recommended, but not
strictly required that (x.compareTo(y)==0) == (x.equals(y)). "

IMHO the problem is, what you do with the Ranges. e.g. if you put them
in a TreeSet, it might cause problems, because following your
implementation,

    Range(0,10) equals Range(5,15)
and Range(5,15) equals Range(11,20)

Because of the fact that "equals" should be transitive, it should follow:

Range(0,10) equals Range(11,20)
which is not true!

If you only work with non-overlapping ranges, you will never encounter
that problem, but if you do the following:

set.add(new Range(0,10));
set.add(new Range(11,20));
set.remove(new Range(5,15));

What do you expect *should* happen?

Ciao,
Ingo
Twisted - 14 Jul 2007 04:39 GMT
> Hi,
>
[quoted text clipped - 36 lines]
>
> What do you expect *should* happen?

As I recall, he said elsewhere in the thread that he made his map
throw exceptions if ranges overlapped but weren't equal.

Another method is to have ranges "eat" the overlapping parts of
earlier ranges. So if you put X at 0,10 in a RangeMap and Y at 11,20
you'd have a map with two keys, 0,10 and 11,20, and X at the first and
Y at the second. Put Z at 5,15 and it would change to have three keys,
0,4 with X, 5,15 with Z, and 16,20 with Y. And if you then looked up
"7" you'd get Z, as you should, as only the one range contains 7. In
other words, it would emulate a Map<Integer,ValueType> with range puts
putting at every single value in the range, only without ridiculous
memory requirements (especially if the numbers get large, or worse,
they're Doubles rather than Integers).
Sideswipe - 26 Jul 2007 01:39 GMT
Another reason I specifically require the use of my own ranging keys
and test for exclusivity of ranges. You are right that, in those cases
it would be a problem. Validating the input limits the functionality a
bit but removes that condition.

So, I suppose the question becomes from all of this discussion: Can a
RangedMap be properly implemented per the Map interface? I don't think
so. Ranges are inherently analog (yes, yes, their digital
representations aren't, but too many possible values to be usable) and
Map are defined as discreet input -> discreet output

Christian Bongiorno
http://christian.bongiorno.org
Piotr Kobzda - 13 Jul 2007 11:08 GMT
> If I am missing something, please supply a use case that produces an
> unexpected result.

The following is allowed with your map:

   map.put(Range.of(1, 2), "X");
   map.put(Range.of(0, 3), "Y");

In put(), you shouldn't check for min and max containment separately.
Using your current range implementation, just checking if map
contains(range) should work.

> I certainly wouldn't mind improvements of this
> implementation. But, for safety purposes, this map MUST use it's own
> range type.

Maybe, because of reasons pointed out by Ingo, you should maintain a
range key in this map internally only?  Unfortunately, it will probably
lead to a number of different problems, generally complicating all that
things (own implementation of entries, mapping iterator, etc.).  So,
from pragmatic point of view, your current approach seems to be satisfying.

piotr
Hendrik Maryns - 12 Jul 2007 14:46 GMT
Sideswipe schreef:
> I am trying to write a RangedMap and when I "genericify" it, it
> occurred to me that I am not completely sure how I can Quite express
[quoted text clipped - 24 lines]
>
> public class RangedMap<RangedKey, V>

In this statement, you declare RangedKey as a type variable.  Thus the
compilers thinks all occurrences of RangedKey in the class are a
variable.  You don’t need the variable at all here.  However, it indeed
makes sense to make RangeKey generic as well, so then you need it again.
The correct syntax would be either

public class RangedMap<V> extends TreeMap<RangedKey, V> {

or

public class RangedMap<T extends Comparable<T>, V> extends
TreeMap<RangedKey<T>, V> {

But that is not the only problem.  You will have to make RangedKey a
top-level class for this to work.  I do not really understand why.

The following works:

/**
* Date: Jul 9, 2007
* Time: 4:25:18 PM
* This Map allows for a ranged mapping of values. The key can be
anything comparable such
* as Numbers and Dates or Strings
*/

import java.util.TreeMap;
import java.util.Map;

public class RangedMap<T extends Comparable<T>, V> extends
TreeMap<RangedKey<T>, V> {

   public static void main(String[] args) {
       Map<RangedKey<Integer>, String> testMap = new RangedMap<Integer,
String>();
       testMap.put(new RangedKey<Integer>(50, 60), "Blue");
       testMap.put(new RangedKey<Integer>(61, 70), "Yellow");
       testMap.put(new RangedKey<Integer>(71, 80), "Red");

       System.out.println(testMap.get(new RangedKey<Integer>(55)));
       System.out.println(testMap.get(new RangedKey<Integer>(67)));
       System.out.println(testMap.get(new RangedKey<Integer>(73)));

       System.out.println(testMap.get(new RangedKey<Integer>(1)));
       System.out.println(testMap.get(new RangedKey<Integer>(90)));

       testMap.put(new RangedKey<Integer>(62, 80), "Fail");

   }

   @Override
   public V put(RangedKey<T> key, V value) {
       rangeCheck(key.getMin());
       rangeCheck(key.getMax());

       return super.put(key, value);
   }

   @Override
   public void putAll(Map<? extends RangedKey<T>, ? extends V> map) {
       for (Map.Entry<? extends RangedKey<T>, ? extends V> entry :
map.entrySet())
           put(entry.getKey(), entry.getValue());
   }

   private void rangeCheck(T c) throws IllegalArgumentException {
       V val = get(new RangedKey<T>(c));
       if (val != null)
           throw new IllegalArgumentException("range: " + c + "overlaps
with another range and would cause an ambiguous mapping");
   }

}

/**
* A key which represents a range.
*
* @param <T> The comparable class which has ranges.
*/
public final class RangedKey<T extends Comparable<T>> implements
       Comparable<RangedKey<T>> {

   private T min;

   private T max;

   public int compareTo(RangedKey<T> range) {

       if (this.max.compareTo(range.min) < 0)
           return -1;
       if (this.min.compareTo(range.max) > 0)
           return 1;
       else
           return 0;
   }

   public RangedKey(T single) {
       this.min = single;
       this.max = single;
   }

   public RangedKey(T min, T max) {
       this.min = min;
       this.max = max;
   }

   public T getMin() {
       return min;
   }

   public T getMax() {
       return max;
   }

   @Override
   public String toString() {
       return min + "-" + max;
   }
}

Output:
Blue
Yellow
Red
null
null
Exception in thread "main" java.lang.IllegalArgumentException: range:
62overlaps with another range and would cause an ambiguous mapping
    at RangedMap.rangeCheck(RangedMap.java:48)
    at RangedMap.put(RangedMap.java:33)
    at RangedMap.put(RangedMap.java:1)
    at RangedMap.main(RangedMap.java:27)

HTH, H.

- --
Hendrik Maryns
http://tcl.sfs.uni-tuebingen.de/~hendrik/
==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html
Piotr Kobzda - 12 Jul 2007 16:22 GMT
> You will have to make RangedKey a
> top-level class for this to work.

Not necessarily.  Having it nested, you can import it, or use its
qualified name (RangedMap.RangedKey).

> I do not really understand why.

Because a class body defines a namespace separated from a header of a
class declaration (i.e. modifiers, name, type parameters, etc.).

piotr
Hendrik Maryns - 12 Jul 2007 16:32 GMT
Piotr Kobzda schreef:

>> You will have to make RangedKey a
>> top-level class for this to work.
[quoted text clipped - 6 lines]
> Because a class body defines a namespace separated from a header of a
> class declaration (i.e. modifiers, name, type parameters, etc.).

Ah, thanks.

Indeed, the following works as well:

/**
* Date: Jul 9, 2007
* Time: 4:25:18 PM
* This Map allows for a ranged mapping of values. The key can be
anything comparable such
* as Numbers and Dates or Strings
*/

import java.util.TreeMap;
import java.util.Map;

public class RangedMap<T extends Comparable<T>, V> extends
TreeMap<RangedMap.RangedKey<T>, V> {

   public static void main(String[] args) {
       Map<RangedKey<Integer>, String> testMap = new RangedMap<Integer,
String>();
       testMap.put(new RangedKey<Integer>(50, 60), "Blue");
       testMap.put(new RangedKey<Integer>(61, 70), "Yellow");
       testMap.put(new RangedKey<Integer>(71, 80), "Red");

       System.out.println(testMap.get(new RangedKey<Integer>(55)));
       System.out.println(testMap.get(new RangedKey<Integer>(67)));
       System.out.println(testMap.get(new RangedKey<Integer>(73)));

       System.out.println(testMap.get(new RangedKey<Integer>(1)));
       System.out.println(testMap.get(new RangedKey<Integer>(90)));

       testMap.put(new RangedKey<Integer>(62, 80), "Fail");

   }

   @Override
   public V put(RangedKey<T> key, V value) {
       rangeCheck(key.getMin());
       rangeCheck(key.getMax());

       return super.put(key, value);
   }

   @Override
   public void putAll(Map<? extends RangedKey<T>, ? extends V> map) {
       for (Map.Entry<? extends RangedKey<T>, ? extends V> entry :
map.entrySet())
           put(entry.getKey(), entry.getValue());
   }

   private void rangeCheck(T c) throws IllegalArgumentException {
       V val = get(new RangedKey<T>(c));
       if (val != null)
           throw new IllegalArgumentException("range: " + c + "overlaps
with another range and would cause an ambiguous mapping");
   }

   /**
    * A key which represents a range.
    *
    * @param <T> The comparable class which has ranges.
    */
   public static final class RangedKey<T extends Comparable<T>> implements
           Comparable<RangedKey<T>> {

       private T min;

       private T max;

       public int compareTo(RangedKey<T> range) {

           if (this.max.compareTo(range.min) < 0)
               return -1;
           if (this.min.compareTo(range.max) > 0)
               return 1;
           else
               return 0;
       }

       public RangedKey(T single) {
           this.min = single;
           this.max = single;
       }

       public RangedKey(T min, T max) {
           this.min = min;
           this.max = max;
       }

       public T getMin() {
           return min;
       }

       public T getMax() {
           return max;
       }

       @Override
       public String toString() {
           return min + "-" + max;
       }
   }
}

H.
- --
Hendrik Maryns
http://tcl.sfs.uni-tuebingen.de/~hendrik/
==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html


Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2009 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.