import algorithms.heaps.*;

record Queue[S] (seq: S);

alias VectorQueue[T] = Queue[Vector[T]];

[S] overload Queue[S]() = Queue(S());

[S] overload Queue(forward seq: S) --> returned: Queue[S] {
    returned.seq <-- seq;
    try {
        makeHeap(begin(returned.seq), end(returned.seq), lesser?);
    } catch (ex) {
        destroy(returned.seq);
        throw ex;
    }
}

[S, S2 | SequenceElementType(S) == SequenceElementType(S2)]
overload Queue[S](forward seq: S2) --> returned: Queue[S] {
    returned.seq <-- S(seq);
    try {
        makeHeap(begin(returned.seq), end(returned.seq), lesser?);
    } catch (ex) {
        destroy(returned.seq);
        throw ex;
    }
}

[S, ..A | countValues(..A) > 0 and equalValues?(SequenceElementType(S), ..A)]
overload Queue[S](forward ..values: A) --> returned: Queue[S] {
    returned <-- Queue[S]();
    try {
        ..for (v in values)
            queuePush(returned, v);
    } catch (ex) {
        destroy(returned);
        throw ex;
    }
}

[S] queueEmpty?(q: Queue[S]) = empty?(q.seq);
[S] queueSize(q: Queue[S]) = size(q.seq);
[S] queueTop(q: Queue[S]) = front(q.seq);

[S, T | T == SequenceElementType(S)]
queuePush(q: Queue[S], forward v_: T) {
    var v = v_;
    push(q.seq, v);
    pushHeap(begin(q.seq), size(q.seq) - 1, 0, move(v), lesser?);
}

[S]
queuePop(q: Queue[S]) {
    var backi = end(q.seq) - 1;
    popHeap(begin(q.seq), backi, backi, lesser?);
    return pop(q.seq);
}

