Priority Queue in Java

can you h开发者_StackOverflow中文版ave 2 parameters? for instance, i want to add a string and a corresponding integer to a priority key. Then I am going to sort it by that integer. I know how to add either a string or a integer, but I dont know how to add both. Can someone please point me in the right direction and let me know if i am even going about this the right way?

There are two ways to do this. Either way, you want to create a custom object that holds both the String (the value you want) and the integer (the priority).

The first solution is to have this data object implement Comparable:

class Data implements Comparable<Data> {
  private final String message;
  private final int priority;

  public Data(String message, int priority) {
    this.message = message;
    this.priority = priority;
  }

  @Override
  int compareTo(Data other) {
    return Integer.valueOf(priority).compareTo(other.priority);
  }

  // also implement equals() and hashCode()
}

Then when you do

PriorityQueue<Data> queue = new PriorityQueue<Data>();

the queue will order items by the order defined by the compareTo method.

The problem with this solution is that if you want the ordering to be only on the integer, then either equals method and your compareTo method will not be consistent or your equals method will not be correct.

A better solution would be to use the PriorityQueue constructor that takes a Comparator. In this case, Data wouldn't have to implement Comparable; you just need a Comparator that defines your ordering:

public final class OrderDataByPriority implements Comparator<Data> {
  public static final OrderDataByPriority INSTANCE = new OrderDataByPriority();

  private OrderDataByPriority() {}

  @Override
  public int compare(Data data1, Data data2) {
    return Integer.valueOf(data1.priority).compareTo(data2.priority);
  }

  @Override
  public boolean equals(Object other) {
    return other == OrderDataByInteger.INSTANCE;
  }

  private Object readResolve() {
    return INSTANCE;
  }
}

Note that since this comparator takes no data, I made it a singleton.

You can then create the queue line this:

PriorityQueue<Data> queue = new PriorityQueue<Data>(
    initialCapacity, OrderDataByPrority.INSTANCE);

Here is a generic way of doing it:

public class PriorityQueue<T> {

    private java.util.PriorityQueue<IntPriorityComparableWrapper<T>> queue;

    public PriorityQueue() {
            queue = new java.util.PriorityQueue<IntPriorityComparableWrapper<T>>();
    }

    public void add( int priority, T object ) {
            queue.add( new IntPriorityComparableWrapper<T>(object, priority) );
    }

    public T get() {
            return (null != queue.peek())? queue.poll().getObject() : null;
    }


    /**
     * A "wrapper" to impose comparable properties on any object placed in the
     * queue.
     */
    private static class IntPriorityComparableWrapper<T>
    implements Comparable<IntPriorityComparableWrapper<T>> {

            private T object;
            private int priority;

            public IntPriorityComparableWrapper( T object, int priority ) {
                    this.object = object;
                    this.priority = priority;
            }

            public int compareTo( IntPriorityComparableWrapper<T> anotherObject ) {
                    return this.priority - anotherObject.priority;
            }

            public int getPriority() {
                    return priority;
            }

            public T getObject() {
                    return object;
            }
    }

}

How about creating a new class that contains those two fields (int and String) and then implementing Comparable (comparing on the int field). Don't forget to override also hashCode() and equals() (see the Comparable class javadoc for reasoning behind overriding these methods).

Is that what you are after?

If you want to use multiple elements as a key, you can create a class that encapsulates both, and then use that type as the key. Likewise for the values. You should make this custom key class Comparable, override equals(), and override hashCode() for the custom key class that you create.