views:

758

answers:

10

With the type Integer you can do this:

int lowest = Integer.MIN_VALUE;

What can I do if I use generics?

K lowest = <...>;

I need this in order to implement something similar to a PriorityQueue. I have access to a node I want to remove from the queue, but it is not the min.

1. I need to make it the min by decreasing the key of that node,
2. And then remove the min.

I am stuck on the first step. The only thing I can do is set the key of the node to the current min. Not sure it is enough.

+1  A: 

Uh doesn't this depend on what type K is?

The point of Generics is that K can be any type (or any subclass of a certain type); in order to be able to call methods on K or access properties of it, you need to restrict it's type bounds with wildcards.

matt b
Well, K is Comparable.
xhaker
It seems like a valid thing to want--if it's an int, I want the lowest value, but if it's a long, I want the lowest long value. I'm not sure there is a simple answer though. If you weren't using Generics (just passing in a number or a comparable), you could probably use reflection to solve most of the cases (numbers generally have that same .MIN_VALUE field I think)
Bill K
Comparable to what ?It's only comparable to other K's which you won't know.
Eoin Campbell
Not all Comparables have maximum or minimum values (or even a single value, really).
matt b
+2  A: 

This doesn't make any sense...

Given that you don't know what K is at that point, (i.e. You're implementing it generically... duh!) you can't specify a min/max bound for it.

in a case where K could be a int, long, string OR object, you couldn't sensibly guess to use

Integer.MIN_VALUE, "" OR NULL.

I guess what you're looking for is a K.MIN_VALUE_OF_EVENTUAL_TYPE but that doesn't exist.

Eoin Campbell
This may be someone coming from a C++ background, where it's trivial to just use numeric_limits<K>::max and numeric_limits<K>::min. This lets you write code that handles chars, doubles, ints, 64 bit ints, or even custom numeric classes.
Eclipse
+1  A: 

There is no generic form of MIN_VALUE or MAX_VALUE for all Comparable types.

Think about a Time class that implements comparable. There is no MAX_VALUE for Time even though it is Comparable.

Alex B
A: 

just because an object is a comparable does not mean it has to have a minimum value. The reason int has a min value of -(2^(31)) is because you need 1 bit for a sign, so 2^31 is the largest (or smallest) possible integer that can be stored. For things like string, it does not make any sense since there is no largest/smallest possible string, it is memory bound.

yx
There certainly is a smallest possible string: "". It's only the largest that's memory bound,
Eclipse
Sorting rules are contextual. I could just as easily define an order that put empty strings last.
erickson
A: 

You might have to create an interface "IInfinity", and have K extends IInfinity, and IInfinity to have a method "getInfinityValue()", and then wrap/extend Integer, Double, BigDecimal, etc in a class that implements IInfinity ... and ugh!

JeeBee
A: 

Basically you want any type K to implement some static functions say lowest and highest which obey the standard mathematical properties.

I assume that for this sense of lowest (or highest) to be usable you would want any Comparable object to have these methods. (or static fields). If you are only interested in your own custom objects, the way to do this would be to have everything inherit from an abstract data type which declared static fields for MINVALUE and MAX_VALUE and then your type varaibles would be . If you need this functionality for other classes you will need to cre4ate some sort of external hashmap which tracks these properties for different classes (but that would get pretty ugly)

luke
+2  A: 

I am trying to imagine what scenario would require such behavior. This is the best I can come up with...

WARNING: This code is dangerous. Please be merciful to me for posting such an abomination. It is only a proof of concept.

public class Lowest<K> implements Comparable<K> {
    public int compareTo(K other) {
        return -1;
    }
}

And then...

public class Test {
    public <K extends Comparable<K>> K findMaximum(List<K> values) throws Exception {
        K lowest = (K) new Lowest<K>(); /// XXX DANGER! Losing compile-time safety!!!

        K maximum = lowest;
        for (K value : values) {
            if (maximum.compareTo(value) < 0) {
                maximum = value;
            }
        }

        if (maximum == lowest) {
            throw new Exception("Could not find a maximum value");
        } else {
            return maximum;
        }
    }
}
Adam Paynter
Ok, this is totally weird. We made the same comment on the question within a second of each other, and then we waited 20 minutes and posted almost the same code within 15 seconds of each other. I think I need to take a short break...
Michael Myers
@mmyers: Weird! I think I will take a long break, myself. :)
Adam Paynter
I'm not sure which is worse, though: my use of reflection to find a constructor (for a potentially non-trivial class), or your cast of a non-K to K.
Michael Myers
Turns out my solution is worse (it's hard even with Integers). +1 this and deleted mine.
Michael Myers
weird but basically a great idea! +1 as long as you are not pass out the new Lowest this is a save approach. you should make Lowest a inner "private static class", maybe with a final reference
Andreas Petersson
A: 

Consider not making K a generic, but using an interface that wraps the primitive wrapper (a double wrapper!).

import java.util.HashMap;


public class NodeWrapper<K extends Comparable<K>> implements Comparable<NodeWrapper<K>> {

    private static HashMap<Class, NodeWrapper> minVals = new HashMap<Class, NodeWrapper>();

    private K value;

    private NodeWrapper() {
     super();
    }

    public NodeWrapper(K value, Class<K> clazz) {
     super();
     this.value = value;

     if (minVals.get(clazz)==null) {
      minVals.put(clazz, new NodeWrapper<K>());
     }
    }

    public K getValue() {
     return value;
    }

    public static NodeWrapper getMinValue(Class clazz){
     return minVals.get(clazz);
    }

    public void setValue(K value) {
     this.value = value;
    }

    @Override
    public int compareTo(NodeWrapper<K> o) {
     NodeWrapper min = minVals.get(this.getClass());
     if (this==min && o==min)  {
      return 0;
     } else if (this==min){
      return -1;
     } else if (o==min){
      return 1;
     } else {
      return this.value.compareTo(o.value);
     }
    }

}

Briefly, the idea is that whenever a new class is instantiated, a minimum value is created and put into a static hashmap that stores the minimum values for each class. (In fact, these values are NOTHING at all, just a sentinel object, but since we will use object equality to determine if something is the min value, this is no problem at all.) All that's necessary is that the wrapped object be comparable to other instances of itself in general.

One drawback is that when you call getMinValue you will have compiler warnings, since the return type will have no generic information. There may be a more elegant way around this, but I can't think of it right now.

This general idea might be rather nice overall. However, I should really stress: this will absolutely break if you try it with any polymorphism or any mixing of mutually comparable classes. Longs and Integers in the same tree will completely destroy you.

David Berger
+2  A: 

er... what's the problem again?

PriorityQueue, like all Collections, allows you to use an instance of an object to remove it from the collection.

R. Bemrose
Haha. Focus :-)
KarlP
Well said. I recommend that xhaker check the source code for the PriorityQueue class for an example.
Adam Paynter
A: 

You can make a wrapper class that "adds" a minimum and maximum value to all types. It just has two static instances that represent minimum and maximum, and then other instances wrap some other value of some type. When we do a comparison, we check if one of the things is the minimum or maximum, and return the proper result; and otherwise we just do the same comparison as the underlying type. Something like this:

class Extended<T extends Comparable<? super T>> implements Comparable<Extended<T>> {
    private Extended() { }

    private static Extended min = new Extended();
    private static Extended max = new Extended();

    @SuppressWarnings("unchecked")
    public static <T extends Comparable<? super T>> Extended<T> getMin() {
        return (Extended<T>)min;
    }
    @SuppressWarnings("unchecked")
    public static <T extends Comparable<? super T>> Extended<T> getMax() {
        return (Extended<T>)max;
    }

    public T value;

    public Extended(T x) { value = x; }

    public int compareTo(Extended<T> other) {
        if (this == other) return 0;
        else if (this == min || other == max) return -1;
        else if (this == max || other == min) return 1;
        else return this.value.compareTo(other.value);
    }
}
newacct