generic sorting?

[willitheowl]

Hello group,

Given a "List<T> objects;" and a "List<R extends Comparable>
weights;", which have the same size and where weights.get(i) is the
weight for objects.get(i), I want to sort the objects according to
weights. (In all that follows, I think, List<T> can be replaced with
T[] without changing the issue.)
To preserve the relationship between objects and weights, I think, I
would be practical to sort indirectly, using a "List<int> index;",
such that after sorting "objects" and "elements" are unchanged,
while weights.get(index.get(0)) is the smallest weight and
weights.get(index.get(1)) the second smallest and so on. (Consequently,
objects.get(index.get(0)) is the object that has the smallest
weight...)

I suppose that this can be implemented by calling the standard
"sort" function with a comparator. The comparison function will
thus look like

public class IndirectComparator<...> implements Comparator<...> // 1
{
public int compare(int i, int j)
{
return weight.compareTo(weight[j]); // 2
}

}

Now it seems that this is not quite correct, since on the line // 2, I
get the warning
"Type safety: The method compareTo(Object) belongs to the raw type
Comparable. References to generic type Comparable<T> should be
parameterized"

Furthermore, what are the proper things to write into the <...> at line
// 1?

thanks for your help and opinions,
Bob

 

[Daniel Dyer]

Hello group,

Given a "List<T> objects;" and a "List<R extends Comparable>
weights;", which have the same size and where weights.get(i) is the
weight for objects.get(i), I want to sort the objects according to
weights. (In all that follows, I think, List<T> can be replaced with
T[] without changing the issue.)
To preserve the relationship between objects and weights, I think, I
would be practical to sort indirectly, using a "List<int> index;",
such that after sorting "objects" and "elements" are unchanged,
while weights.get(index.get(0)) is the smallest weight and
weights.get(index.get(1)) the second smallest and so on. (Consequently,
objects.get(index.get(0)) is the object that has the smallest
weight...)

From your problem description, it looks like "object" and weight ought to
be combined into the same entity. What is the type of these objects? Is
there any reason why you can't add a weight property to the class and then
simply implement Comparable? If it's not possible, another approach would
be to write a wrapper that combines the two elements. At the moment the
association between the two concepts is implicit in the ordering of the
two lists, which is a fragile relationship.

Dan.

 

[Mark Rafn]

Given a "List<T> objects;" and a "List<R extends Comparable>
weights;", which have the same size and where weights.get(i) is the
weight for objects.get(i), I want to sort the objects according to
weights.

The "clean" way is to create a WeightedObject class which contains an Object
and a weight, and is Comparable based on weight. Go through the lists and
create a third list of these objects. Sort it via Collections.sort().

 

[danharrisandrews]

public class IndirectComparator<...> implements Comparator<...> // 1
{
public int compare(int i, int j)
{
return weight.compareTo(weight[j]); // 2
}

}

Hi Bob,

Not sure if this is what you had in mind, but see if this helps
(below). Some days I have a heck of a time wrapping my head around
generics and I find Eclipse to have very straight forward tips when I
go astray.

public final class IndirectComparator<T, R extends Comparable<? super
R>>
implements Comparator<T> // 1
{
List<R> weights;
List<T> objs;
public IndirectComparator(List<R> weights, List<T> objs) {
this.weights = weights;
this.objs = objs;
}

public int compare(T i, T j) {
return weights.get(objs.indexOf(i)).compareTo(
weights.get(objs.indexOf(j))); // 2
}

}

Cheers,

Dan Andrews
- - - - - - - - - - - - - - - - - - - - - - - - -
Ansir Development Limited http://www.ansir.ca
- - - - - - - - - - - - - - - - - - - - - - - - -

 

[Patricia Shanahan]

Hello group,

Given a "List<T> objects;" and a "List<R extends Comparable>
weights;", which have the same size and where weights.get(i) is the
weight for objects.get(i), I want to sort the objects according to
weights. (In all that follows, I think, List<T> can be replaced with
T[] without changing the issue.)
To preserve the relationship between objects and weights, I think, I
would be practical to sort indirectly, using a "List<int> index;",
such that after sorting "objects" and "elements" are unchanged,
while weights.get(index.get(0)) is the smallest weight and
weights.get(index.get(1)) the second smallest and so on. (Consequently,
objects.get(index.get(0)) is the object that has the smallest
weight...)

I suppose that this can be implemented by calling the standard
"sort" function with a comparator. The comparison function will
thus look like

public class IndirectComparator<...> implements Comparator<...> // 1
{
public int compare(int i, int j)
{
return weight.compareTo(weight[j]); // 2
}

}

If you go ahead with this approach, sort an Integer[] or List<Integer>
instead of an int[].

There is no problem writing a Comparator<Integer> whose compare(Integer
i, Integer j) method uses the weight array to get the ordering.

I do agree with the general opinion in favor of combining the weight and
object classes, rather than the rather fragile array index matching
approach.

Patricia

 

[willitheowl]

Hi group,

I want to thank all of you for your help, I tried out what you told me
and think it's really great.

First of all, I have replaced all "int"s with Integer, because Java's
"int"s don't really support genericity. So that's fine now.

Second, I have implemented WeightedObjects like this:
public class WeightedObject<T, C extends Comparable<C>>
implements Comparable<WeightedObject<T, C>>
{
public final T t;
public final C c;

public WeightedObject(T tt, C cc)
{
c = cc;
t = tt;
}

public int compareTo(WeightedObject<T, C> o)
{
return c.compareTo(o.c);
}

} // class

My application code becomes really simple, then:
List<WeightedObject<Plot, Integer>> plots_with_distance
= new Vector<WeightedObject<Plot, Integer>>();
for (Plot plot : plots)
{
plots_with_distance.add(new WeightedObject<Plot, Integer>
(plot,
(int)p.distance_to(plot.point))
);
}
Collections.sort(plots_with_distance);

(I only use the (int) cast to round from a double, so that's no typing
problem. I just don't want to sort by the decimal fraction...)

Third, for learning, I have also changed my original approach to use
Integer and that gives a nice example:

package bob.util;

import java.util.Arrays;
import java.util.Comparator;

public class IndirectComparator<T extends Comparable<T>> implements
Comparator<Integer>
{
protected T[] weight;

public IndirectComparator(T[] w)
{
weight = w;
}

public int compare(Integer i, Integer j)
{
return (weight.compareTo(weight[j]));
}

public static <T extends Comparable<T>> void sort(Integer[] index, T[]
weight)
{
Arrays.sort(index, new IndirectComparator<T>(weight));
}

}

It's not as clear as what you suggested, but I like it, too. ;-)

Cheers,
Bob

 

[Patricia Shanahan]

public class IndirectComparator<...> implements Comparator<...> // 1
{
public int compare(int i, int j)
{
return weight.compareTo(weight[j]); // 2
}

}

Hi Bob,

Not sure if this is what you had in mind, but see if this helps
(below). Some days I have a heck of a time wrapping my head around
generics and I find Eclipse to have very straight forward tips when I
go astray.

public final class IndirectComparator<T, R extends Comparable<? super
R>>
implements Comparator<T> // 1
{
List<R> weights;
List<T> objs;
public IndirectComparator(List<R> weights, List<T> objs) {
this.weights = weights;
this.objs = objs;
}

public int compare(T i, T j) {
return weights.get(objs.indexOf(i)).compareTo(
weights.get(objs.indexOf(j))); // 2
}

}

If the lists are at all long, using indexOf could cause a performance
problem. It changes the sort complexity from O(n*log(n)) to O(n*n*log(n)).

However, if that is a a problem, it does suggest the alternative of
constructing a HashMap with the objects as keys, and the weights as values:

public final class IndirectComparator<T, R extends Comparable<? super
R>>
implements Comparator<T> // 1
{
Map<T,R> weightMap = new HashMap<T,R>();

public IndirectComparator(List<R> weights, List<T> objs) {
Iterator<R> wIt = weights.iterator();
Iterator<T> oIt = objs.iterator();
while(oIt.hasNext()){
weightMap.put(oIt.next(),wIt.next());
}
}

public int compare(T i, T j) {
return weightMap.get(i).compareTo(weightMap.get(j));
}
}

Patricia

 

[Dan Andrews]

public class IndirectComparator<...> implements Comparator<...> // 1
{
public int compare(int i, int j)
{
return weight.compareTo(weight[j]); // 2
}

}

Hi Bob,

Not sure if this is what you had in mind, but see if this helps
(below). Some days I have a heck of a time wrapping my head around
generics and I find Eclipse to have very straight forward tips when I
go astray.

public final class IndirectComparator<T, R extends Comparable<? super
R>>
implements Comparator<T> // 1
{
List<R> weights;
List<T> objs;
public IndirectComparator(List<R> weights, List<T> objs) {
this.weights = weights;
this.objs = objs;
}

public int compare(T i, T j) {
return weights.get(objs.indexOf(i)).compareTo(
weights.get(objs.indexOf(j))); // 2
}

}

If the lists are at all long, using indexOf could cause a performance
problem. It changes the sort complexity from O(n*log(n)) to O(n*n*log(n)).

However, if that is a a problem, it does suggest the alternative of
constructing a HashMap with the objects as keys, and the weights as values:

public final class IndirectComparator<T, R extends Comparable<? super
R>>
implements Comparator<T> // 1
{
Map<T,R> weightMap = new HashMap<T,R>();

public IndirectComparator(List<R> weights, List<T> objs) {
Iterator<R> wIt = weights.iterator();
Iterator<T> oIt = objs.iterator();
while(oIt.hasNext()){
weightMap.put(oIt.next(),wIt.next());
}
}

public int compare(T i, T j) {
return weightMap.get(i).compareTo(weightMap.get(j));
}
}

Patricia

Patricia,

Yes that's better and what I wrote wouldn't work anyhow as "return
weights.get( objs.indexOf( i )).compareTo( weights.get(objs.indexOf(j) )
); // 2" would end up messing up the index order as the list got sorted.

I also thought if there is a one to one relationship between the Integer
weights and the objects then a TreeMap<Integer,T> would do the sort in
O(nlogn) in one step without bothering with implementing a Comparator.

Cheers,

Dan Andrews
- - - - - - - - - - - - - - - - - - - - - - - - -
Ansir Development Limited http://www.ansir.ca
- - - - - - - - - - - - - - - - - - - - - - - - -

 

[willitheowl]

I also thought if there is a one to one relationship between the Integer
weights and the objects then a TreeMap<Integer,T> would do the sort in
O(nlogn) in one step without bothering with implementing a Comparator.

Of course it would!

In fact that's the nicest solution proposed and I am really embarassed
that I didn't think of it ;-)
(After all, I already spent much time of my life implementing Maps in
other programming languages.)

Bob

 

[Mark Rafn]

In fact that's the nicest solution proposed and I am really embarassed
that I didn't think of it ;-)

Be VERY careful about this method. Dan includes the "if there is a one to one
relationship" bit, but your example of weights and objects implies that there
may not be.

If you have two objects with the same weight, the more complicated solutions
(either sorting a list of indices, or making a WeightedObject object which you
can sort naturally) work. Making a TreeMap will discard an object if it has
the same weight as a later object.

 

[Bob]

Be VERY careful about [using the TreeMap]. Dan includes the "if there is a one to one
relationship" bit, but your example of weights and objects implies that there
may not be.

Huh, yes, I have been too optimistic. I don't have the
one-to-one-relationship. I pretended that this wasn't a problem because
I simply could use a TreeBag.... before realizing that such a thing is
not provided by the JDK java.util. Guess I'll stick two my
WeightedObjects before I'll implement my own "really complete"
Collections Hierarchy.

Bob