Generics syntax and Comparing Comparables of type ?

S

Sideswipe

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;
}
}
}
 
J

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) {
....
 
S

Sideswipe

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;
}
}
 
R

Roedy Green

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

Ingo R. Homann

Hi,
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
 
H

Hendrik Maryns

-----BEGIN PGP SIGNED MESSAGE-----
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-----
 
P

Piotr Kobzda

Hendrik said:
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
 
H

Hendrik Maryns

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

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


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
-----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-----
 
S

Sideswipe

Hi,



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

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

Ingo R. Homann

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
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
 
P

Piotr Kobzda

Sideswipe said:
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
 
T

Twisted

Hi,



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?

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).
 
S

Sideswipe

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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads


Members online

Forum statistics

Threads
473,818
Messages
2,569,727
Members
45,664
Latest member
Phil79581

Latest Threads

Top