current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 6 down vote favorite

I implemented a fixed sized priority queue. How can I improve my code?

public class FixedSizedPriorityQueue {
    private final int capacity;
    private boolean sorted = false;
    private double smallest = Double.POSITIVE_INFINITY;
    private ArrayList<Double> list;

    protected static final Comparator<Double> comparator = new Comparator<Double>() {
        @Override
        public int compare(Double o1, Double o2) {
            return o2.compareTo(o1);
        }
    };

    public FixedSizedPriorityQueue(int capacity) {
        this.capacity = capacity;
        list = new ArrayList<Double>(capacity);
    }

    public void add(double value) {
        if (list.size() < capacity) {
            list.add(value);
            sorted = false;
            if (value < smallest) {
                smallest = value;
            }
        } else {
            if (value > smallest) {
                if (!sorted) {
                    Collections.sort(list, comparator);
                    sorted = true;
                }
                list.set(capacity - 1, value);
                if (list.get(capacity - 2) > value) {
                    smallest = value;
                } else {
                    smallest = list.get(capacity - 2);
                    sorted = false;
                }
            }
        }
    }

    public int getSize() {
        return list.size();
    }

    public Double poll() {
        if (list.size() == 0) return null;
        if (!sorted) {
            Collections.sort(list, comparator);
            sorted = true;
        }
        Double value = list.get(0);
        list.remove(0);
        if (list.size() == 0) smallest = Double.POSITIVE_INFINITY;
        return value;
    }

    public void print() {
        for (int i = 0; i < list.size(); i++) {
            System.out.println(i + ": " + list.get(i));
        }
        System.out.println("Smallest: " + smallest);
    }
}
share|improve this question
2  
You may want to implement the Queue interface as well – tanyehzheng Sep 18 '12 at 6:29
up vote 7 down vote accepted

  1. The following is used multiple times and it could be extracted out:

    if (!sorted) {
    Collections.sort(list, comparator);
    sorted = true;
}

    to a helper method:

    private void sortIfNeccessary() {
    if (sorted) {
        return;
    }
    Collections.sort(list, comparator);
    sorted = true;
}

    Note the guard clause.

  2. List.remove returns the removed elements.

    Double value = list.get(0);
list.remove(0);

    The code above could be simplified to this:

    final Double value = list.remove(0);

  3. The comparator could be substituted with the reverseOrder method/comparator:

    Collections.sort(list, Collections.reverseOrder());

  4. The list could be final. final helps readers, because they know that the reference always points to the same instance and it doesn't change later. http://programmers.stackexchange.com/questions/115690/why-declare-final-variables-inside-methods but you can find other questions on Programmers.SE in the topic.

  5. Furthermore, its type could be only List<Double> instead of ArrayList<Double>. See: Effective Java, 2nd edition, Item 52: Refer to objects by their interfaces

  6. The print method violates the single responsibility principle. Other clients may want to write the elements to a log file or a network socket so you shouldn't mix the queue logic with the printing. I'd consider creating a List<Double> getElements method (which would return a copy or unmodifiable version of list to make sure that malicious clients does not modify the inner state of the queue) or providing an iterator to clients and move the print method to another class.

  7. Does it make sense to create a queue with negative capacity? If not, check it and throw an IllegalArgumentException. Actually, it does not work with capacities less than 2. It throws a java.lang.ArrayIndexOutOfBoundsException: -1 when the capacity is 1 because of the list.get(capacity - 2) call. (Effective Java, Second Edition, Item 38: Check parameters for validity)

    public FixedSizedPriorityQueue(final int capacity) {
    if (capacity < 2) {
        throw new IllegalArgumentException("Illegal capacity: " + capacity);
    }
    ...
}

  8. Instead of 

    if (list.size() == 0) ...

    you could use 

    if (list.isEmpty()) ...

    It's the same but easier to read.

share|improve this answer
up vote 3 down vote

I think your code would be a lot simpler if you kept your list sorted at all times. It would also probably be faster. Constantly resorting the list is going to more expensive then inserting new items in the proper location. You might be saving a little by not sorting in certain cases, but probably less then you lose by having to resort the list rather then just insert in the correct location.

You could also consider using a data structure such as a heap. Heaps are often used for priority queues. It lets you fetch the smallest element, but is cheaper then the expense of maintaing a sorted list.

share|improve this answer
    
I think you didn't look at my code very carefully. I DON'T insert a new element in a correct location. I rather use a lazy ordered list, so sorting only occurs when it is really needed. As I understand, to implement such a lazy style priority queue, heaps cannot be used. – Heejin Sep 18 '12 at 6:14
    
@heejin there seems to be a misunderstanding here. Winston was suggesting that you don't lazy-sort. He does recommend that you insert items in the correct location instead. – codesparkle Sep 18 '12 at 6:57
1  
Arghhhh sorry for my poor English. I was confused. Sorry, Winston! – Heejin Sep 18 '12 at 7:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.