[Java/Android] java.util.PriorityQueue negeert compareTo

[NMe]

Oh hai.

Ik ben bezig met het schrijven van een downloadmanager aangezien die pas vanaf Android 2.3 standaard in het framework zit. Gegeven de volgende code:

Java:

public class DownloadManager
{
    public static final int PRIORITY_URGENT = 100;
    public static final int PRIORITY_HIGH   = 75;
    public static final int PRIORITY_NORMAL = 50;
    public static final int PRIORITY_LOW    = 25;
    public static final int PRIORITY_IDLE   = 0;

    private PriorityQueue<DownloadTask> downloadQueue = new PriorityQueue<DownloadTask>();
    private int downloadSequence = 0;

    public class DownloadTask extends AsyncTask<Void, Void, DownloadTask> implements Comparable<DownloadTask>
    {
        @Override
        public int compareTo(DownloadTask other) {
            if (other == null)
                return 1;
            if (this.priority == other.priority)
                return this.sequence - other.sequence;
            return other.priority - this.priority;
        }
    }

    public synchronized DownloadTask queueDownload(URL url, int priority, OnDownloadCompletedListener onCompleted, boolean undub)
    {
        DownloadTask dt = new DownloadTask(this, url, priority, onCompleted, downloadSequence++);

        // *Knip undub-code*

        downloadQueue.add(dt);
        checkDownloads();
        return dt;
    }

    protected synchronized void checkDownloads() {
        while (downloadQueue.peek() != null && (downloadQueue.peek().priority == PRIORITY_URGENT || (downloadSemaphore.availablePermits() > maxConcurrentDownloads)))
        {
            downloadQueue.remove().execute();
        }
    }
}

Vervolgens mijn testcase:

Java:

dMgr.queueDownload(new URL("151"), DownloadManager.PRIORITY_IDLE, listener);
dMgr.queueDownload(new URL("152"), DownloadManager.PRIORITY_LOW, listener);
dMgr.queueDownload(new URL("153"), DownloadManager.PRIORITY_NORMAL, listener);
dMgr.queueDownload(new URL("154"), DownloadManager.PRIORITY_HIGH, listener);
dMgr.queueDownload(new URL("155"), DownloadManager.PRIORITY_URGENT, listener);
dMgr.queueDownload(new URL("156"), DownloadManager.PRIORITY_IDLE, listener);
dMgr.queueDownload(new URL("157"), DownloadManager.PRIORITY_LOW, listener);
dMgr.queueDownload(new URL("158"), DownloadManager.PRIORITY_NORMAL, listener);
dMgr.queueDownload(new URL("159"), DownloadManager.PRIORITY_HIGH, listener);
dMgr.queueDownload(new URL("160"), DownloadManager.PRIORITY_URGENT, listener);

Url's zijn (uiteraard) ingekort, dat is in de app zelf gewoon een echte url.

Wat nu de bedoeling is, en wat ik dacht ook voor elkaar te krijgen met die PriorityQueue en mijn compareTo-method, is dat eerst de eerste 3 aanroepen in de queue gezet worden (queueDownload) en vervolgens meteen als thread gestart worden (checkDownloads). Daarna wordt de vierde aanroep gedaan, die een PRIORITY_HIGH heeft. Er zijn dan geen slots meer vrij, dus die wordt gequeued. Aanroep 5 heeft een urgent-prioriteit, en die wordt dan ook meteen geactiveerd. Aanroepen 6 t/m 9 gaan op de queue, en aanroep 10 is weer urgent en wordt dus ook meteen gestart. Ik ga uit van 3 normale downloadslots by default, plus maximaal 3 extra slots voor urgent downloads; bij de uitvoer van deze code verwacht ik dus dat 5 van de 6 slots bezet zijn. Middels een semaphore zorg ik ervoor dat er pas weer iets van de queue getrokken wordt als er minder dan 3 slots in gebruik zijn. Middels een sequence-number zorg ik ervoor dat spul met dezelfde priority gewoon FiFo binnengehaald wordt.

De voorwaarde (downloadSemaphore.availablePermits() > maxConcurrentDownloads) op regel 38 zorgt ervoor dat mijn semaphore met een size van 6 hooguit 3 keer acquired wordt door "normale" downloads zodat ik de overige drie slots aan urgent downloads kan toekennen.

Wat ik nu verwacht is deze volgorde van (het beginnen met) binnenhalen van files:

1. 151 (idle, gequeued toen alledrie de slots leeg waren, dus meteen gestart)
2. 152 (low, gequeued met 2 slots vrij, dus meteen gestart)
3. 153 (normal, gequeued in het laatste slot, dus meteen gestart)
4. 155 (urgent, dus gequeued in een anderzijds onbeschikbaar slot)
5. 160 (urgent, idem)
6. 154 (high, dus hoogste prio die gequeued kan worden)
7. 159 (high, maar later toegevoegd dan 154)
8. 158 (normal)
9. 157 (low)
10. 156 (idle)

Wat ik echter krijg is een standaard FiFo-systeem waarbij het eerste dat ik erin stop ook het eerste eruit komt. Mijn compareTo-method lijkt compleet genegeerd te worden. Dat wil zeggen: hij wordt blijkbaar wél gewoon aangeroepen voor elke sorteeroperatie en returnt ook met de waardes die ik verwacht, maar vervolgens worden mijn tasks nog steeds in FiFo-volgorde in mijn downloadslots gepropt. Doe/verwacht ik iets verkeerd?

[ Voor 16% gewijzigd door NMe op 16-04-2011 02:28 ]

[NMe]

Urgh, met dank aan curry684 heb ik het probleem gevonden. remove() (zonder parameters) op een PriorityQueue komt van AbstractQueue vandaan en wordt niet overriden door PriorityQueue; remove(<T>) komt wél van PriorityQueue. De remove() zonder parameters is dus niet priority-aware. Dit verklaart meteen waarom hij wél 5 items op de queue gooide waar ik er ook 5 verwachtte, maar niet de juiste items. Op regel 38 remove() vervangen door poll() loste het probleem op.