Generics syntax and Comparing Comparables of type ?
Sideswipe
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
> 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?
>
> public static final class RangedKey implements
> Comparable<RangedKey> {
> 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
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() {
Roedy Green
<christian...@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
Sideswipe wrote:
> 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;
> }
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
Hendrik Maryns
Hash: SHA1
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
> 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>
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
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFGljDBe+7xMGD3itQRAt/YAJ9NomhjD6BXeVwZMZzTfTJPU4a+AACfX4Pp
QfUhCvh6OjkYMJ1fJKv2W9k=
=AEOG
-----END PGP SIGNATURE-----
Piotr Kobzda
> 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
Hash: SHA1
Piotr Kobzda schreef:
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> {
}
return super.put(key, value);
}
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
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFGlkmge+7xMGD3itQRAv8aAJsHURJ2p+sl90LWRn/bdFPq5N3AaACfZhHw
ipnThRxo2PZRO1tA3Vt1RjY=
=l4d2
-----END PGP SIGNATURE-----
Sideswipe
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
Sideswipe wrote:
> 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.
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
Piotr Kobzda
> 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
Twisted
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
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