Java Forum / General / July 2007
Generics syntax and Comparing Comparables of type ?
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 MagazinesGet 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 ...
|
|
|