package org.simantics.scl.compiler.elaboration.chr.planning;

import java.util.Arrays;

public class PlanPriorityQueue {
    PrePlanItem[] items = new PrePlanItem[16];
    int size = 0;

    public PrePlanItem head() {
        return items[0];
    }

    public void pop() {
        items[0].queuePos = -1;
        --size;
        if (size > 0) {
            PrePlanItem e = items[size];
            items[0] = e;
            e.queuePos = 0;
            adjustDown(e);
        }
        items[size] = null;
    }

    public void add(PrePlanItem e) {
        if (size == items.length)
            items = Arrays.copyOf(items, size + size / 2);
        items[size] = e;
        e.queuePos = size;
        ++size;
        adjustUp(e);
    }

    private boolean adjustUp(PrePlanItem e) {
        int pos = e.queuePos;
        while (pos > 0) {
            int upId = (pos - 1) / 2;
            PrePlanItem upE = items[upId];
            if (e.compare(upE) >= 0)
                break;
            items[pos] = upE;
            upE.queuePos = pos;
            pos = upId;
        }
        if (e.queuePos != pos) {
            items[pos] = e;
            e.queuePos = pos;
            return true;
        } else
            return false;
    }

    private void adjustDown(PrePlanItem e) {
        int pos = e.queuePos;
        while (true) {
            int downId = pos * 2 + 1;
            if (downId >= size)
                break;
            if (downId + 1 < size
                    && items[downId].compare(items[downId + 1]) > 0)
                ++downId;
            PrePlanItem downE = items[downId];
            if (e.compare(downE) > 0) {
                items[pos] = downE;
                downE.queuePos = pos;
                pos = downId;
            } else
                break;
        }
        if (e.queuePos != pos) {
            items[pos] = e;
            e.queuePos = pos;
        }
    }

    public void adjust(PrePlanItem e) {
        if(e.queuePos == -1)
            return;
        if (!adjustUp(e))
            adjustDown(e);
    }

    public boolean isEmpty() {
        return size == 0;
    }
}