deques.clay

import data.sequences.handle.*;
import data.sequences.*;


/// @section  Deque coordinates 

record DequeCoordinate[T] (
    current: Pointer[T],
    first: Pointer[T],
    last: Pointer[T],
    node: Pointer[Pointer[T]],
);

[T] overload DequeCoordinate[T]() = DequeCoordinate[T](
    Pointer[T](0),
    Pointer[T](0),
    Pointer[T](0),
    Pointer[Pointer[T]](0)
);

[T] private nodeBegin(node: Pointer[Pointer[T]]) : Pointer[T] = node^;
[T] private nodeEnd(node: Pointer[Pointer[T]]) : Pointer[T] = node^ + DequeBufferSize(T);
[T] private setNode(i: DequeCoordinate[T], node: Pointer[Pointer[T]]) {
    i.node = node;
    i.first = nodeBegin(node);
    i.last  = nodeEnd(node);
}

[T] overload DequeCoordinate[T](current: Pointer[T], node: Pointer[Pointer[T]])
    = DequeCoordinate[T](current, nodeBegin(node), nodeEnd(node), node);

[T] overload inc(ref i: DequeCoordinate[T]) {
    inc(i.current);
    if(i.current == i.last) {
        setNode(i, i.node + 1);
        i.current = i.first;
    }
}

[T] overload dec(ref i: DequeCoordinate[T]) {
    if (i.current == i.first) {
        setNode(i, i.node - 1);
        i.current = i.last;
    }
    dec(i.current);
}

[T, I when Integer?(I)] overload updateAssign(#add, ref i: DequeCoordinate[T], n: I) {
    i +: PtrInt(n);
}

[T] overload updateAssign(#add, ref i: DequeCoordinate[T], n: PtrInt) {
    var offset = n + PtrInt(i.current - i.first);
    if (offset >= 0 and offset < DequeBufferSSize(T))
        i.current +: n;
    else {
        var nodeOffset =
            if (offset > 0)
                PtrInt(offset) \ DequeBufferSSize(T)
            else
                -PtrInt(-offset - 1) \ DequeBufferSSize(T) - 1;

        setNode(i, i.node + nodeOffset);
        i.current = i.first + (offset - nodeOffset * DequeBufferSSize(T));
    }
}

[T, I when Integer?(I)] overload add(i: DequeCoordinate[T], n: I) --> j: DequeCoordinate[T] {
    j <-- i;
    j +: n;
}

[T, I when Integer?(I)] overload updateAssign(#subtract, ref i: DequeCoordinate[T], n: I) {
    i +: (-PtrInt(n));
}

[T, I when Integer?(I)] overload subtract(i: DequeCoordinate[T], n: I) --> j: DequeCoordinate[T] {
    j <-- i;
    j +: (-PtrInt(n));
}

[T] overload subtract(i: DequeCoordinate[T], j: DequeCoordinate[T]) : PtrInt {
    var mapDistance = PtrInt(i.node - j.node - 1);
    var iNodeDistance = PtrInt(i.current - i.first);
    var jNodeDistance = PtrInt(j.last - j.current);
    return DequeBufferSSize(T) * mapDistance + iNodeDistance + jNodeDistance;
}

[T] overload dereference(i: DequeCoordinate[T]) = ref i.current^;
[T, I when Integer?(I)] overload index(i: DequeCoordinate[T], n: I) = ref (i + n)^;

[T] overload lesser?(x: DequeCoordinate[T], y: DequeCoordinate[T])
    = x.node < y.node
    or (x.node == y.node and x.current < y.current);

[T] forceinline overload hasValue?(i: DequeCoordinate[T]) = not null?(i.current);
[T] forceinline overload getValue(i: DequeCoordinate[T]) = ref i.current^;


/// @section  Deque object interface 
record Deque[T] (
    map: Pointer[Pointer[T]],
    mapSize: SizeT,
    begin: DequeCoordinate[T],
    end: DequeCoordinate[T],
);

[T] private validDequeCoordinate?(d: Deque[T], coord: DequeCoordinate[T]) : Bool
    = coord.node >= d.map and coord.node < d.map + d.mapSize
      and coord >= d.begin and coord <= d.end;

[T] overload RegularRecord?(#Deque[T]) = false;

[T] overload SequenceContainer?(#Deque[T]) = true;

[T] overload UnderlyingContainerConstructor(#Deque[T]) = Deque;

[T] overload Deque[T]() --> deque: Deque[T] {
    initializeDequeMap(deque, SizeT(0));
}

[T, A when Sequence?(A) and T == SequenceElementType(A)]
overload Deque[T](forward from: A) --> to: Deque[T] {
    initializeDequeMap(to, SizeT(0));

    try {
        for (x in from) {
            push(to, x);
        }
    } catch (ex) {
        destroy(to);
        throw ex;
    }
}

[T, A when SizedSequence?(A) and T == SequenceElementType(A)]
overload Deque[T](forward from: A) --> to: Deque[T] {
    initializeDequeMap(to, size(from));

    var i = to.begin;
    try {
        for (x in from) {
            i^ <-- x;
            inc(i);
        }
    } catch (ex) {
        destroyDequeValues(to.begin, i);
        destroyDequeMap(to);
        throw ex;
    }
}

[T, ..A when countValues(..A) > 0 and equalValues?(T, ..A)]
overload Deque[T](forward ..from: A) --> to: Deque[T] {
    initializeDequeMap(to, SizeT(countValues(..A)));

    var i = to.begin;
    try {
        ..for (x in from) {
            i^ <-- x;
            inc(i);
        }
    } catch (ex) {
        destroyDequeValues(to.begin, i);
        destroyDequeMap(to);
        throw ex;
    }
}

[A when Sequence?(A)]
overload Deque(forward from:A) {
    alias T = SequenceElementType(A);
    return Deque[T](from);
}

[A when MultiValuedSequence?(A)]
overload Deque(forward from:A) = Deque(mapped(Tuple, from));

[T] overload assign(ref to: Deque[T], from: Deque[T]) {
    resize(to, size(from));
    var toI = to.begin;
    var fromI = from.begin;
    while (toI != to.end) {
        toI^ = fromI^;
        inc(toI);
        inc(fromI);
    }
}

[T] overload destroy(deque: Deque[T]) {
    if (not null?(deque.map)) {
        destroyDequeValues(deque.begin, deque.end);
        destroyDequeMap(deque);
    }
}

[T] overload BitwiseMovedType?(#Deque[T]) = true;

[T] overload resetUnsafe(d: Deque[T]) {
    d.map <-- Pointer[Pointer[T]](0);
    d.mapSize <-- SizeT(0);
    d.begin <-- DequeCoordinate[T]();
    d.end <-- DequeCoordinate[T]();
}

[T] overload begin(d: Deque[T]) = d.begin;
[T] overload end(d: Deque[T]) = d.end;
[T] overload iterator(d: Deque[T]) = coordinateRange(d.begin, d.end);
[T] overload reverseIterator(d: Deque[T]) = reverseCoordinateRange(d.end, d.begin);

[T] overload size(d: Deque[T]) = SizeT(d.end - d.begin);
[T, I when Integer?(I)] overload index(d: Deque[T], i: I) {
    assert["boundsChecks"](i >= 0 and i < size(d), Deque[T], " index out of bounds");
    return ref (d.begin + i)^;
}

[T] overload front(d: Deque[T]) {
    assert["boundsChecks"](not empty?(d), "front of empty ", Deque[T]);
    return ref d.begin^;
}
[T] overload back(d: Deque[T]) {
    assert["boundsChecks"](not empty?(d), "back of empty ", Deque[T]);
    var backi = d.end;
    dec(backi);
    return ref backi^;
}

[T] overload pushFront(deque: Deque[T], forward value) {
    if (deque.begin.current != deque.begin.first) {
        var newCurrent = deque.begin.current - 1;
        newCurrent^ <-- value;
        deque.begin.current = newCurrent;
    } else
        pushFrontDeque1(deque, value);
}

define pushFrontAll(s, vs);

[T, S when Sequence?(S) and SequenceElementType(S) == T]
overload pushFrontAll(deque: Deque[T], forward seq: S) {
    for (x in reversed(seq))
        pushFront(deque, x);
}

[T, S when SizedSequence?(S) and SequenceElementType(S) == T]
overload pushFrontAll(deque: Deque[T], forward seq: S) {
    var seqSize = size(seq);
    deque.begin = reserveDequeFrontElements(deque, seqSize);
    var i = deque.begin + seqSize;
    try {
        for (x in reversed(seq)) {
            dec(i);
            i^ <-- x;
        }
    } catch(ex) {
        inc(i);
        destroyDequeFrontNodes(deque, i);
        throw ex;
    }
}

[T] overload push(deque: Deque[T], forward value: T) {
    if (deque.end.current != deque.end.last - 1) {
        deque.end.current^ <-- value;
        deque.end.current +: 1;
    } else
        pushDeque1(deque, value);
}

[T, S when SizedSequence?(S) and SequenceElementType(S) == T]
overload pushAll(deque: Deque[T], forward seq: S) {
    var seqSize = size(seq);
    deque.end = reserveDequeBackElements(deque, seqSize);
    var i = deque.end - seqSize;
    try {
        for (x in seq) {
            i^ <-- x;
            inc(i);
        }
    } catch(ex) {
        destroyDequeBackNodes(deque, i);
        throw ex;
    }
}

[T] overload popFront(deque: Deque[T]) --> value: T {
    assert["boundsChecks"](not empty?(deque), "popFront of empty ", Deque[T]);
    if (deque.begin.current != deque.begin.last - 1) {
        value <-- moveUnsafe(deque.begin.current^);
        deque.begin.current +: 1;
    } else
        value <-- popFrontDeque1(deque);
}

[T] overload pop(deque: Deque[T]) {
    assert["boundsChecks"](not empty?(deque), "pop of empty ", Deque[T]);
    if (deque.end.current != deque.end.first) {
        deque.end.current -: 1;
        return moveUnsafe(deque.end.current^);
    } else
        return popDeque1(deque);
}

[T] overload clear(deque: Deque[T]) {
    destroyDequeValues(deque.begin, deque.end);
    destroyDequeBackNodes(deque, deque.begin);
}

[T, I when Integer?(I)]
overload insert(deque: Deque[T], n: I, forward value: T) {
    insert(deque, deque.begin + n, value);
}

[T] overload insert(deque: Deque[T], i: DequeCoordinate[T], forward value: T) {
    assert["boundsChecks"](validDequeCoordinate?(deque, i),
        "invalid insert coordinate into ", Deque[T]);
    if (i.current == deque.begin.current)
        pushFront(deque, value);
    else if (i.current == deque.end.current)
        push(deque, value);
    else
        insertDequeValue(deque, i, value);
}

[T, S, I when Sequence?(S) and SequenceElementType(S) == T and Integer?(I)]
overload insert(deque: Deque[T], n: I, forward seq: S) {
    insert(deque, deque.begin + n, seq);
}

[T, S when Sequence?(S) and SequenceElementType(S) == T]
overload insertAll(deque: Deque[T], i: DequeCoordinate[T], forward seq: S) {
    assert["boundsChecks"](validDequeCoordinate?(deque, i),
        "invalid insert coordinate into ", Deque[T]);
    if (i.current == deque.begin.current)
        pushFrontAll(deque, seq);
    else if (i.current == deque.end.current)
        pushAll(deque, seq);
    else
        insertDequeSequence(deque, i, seq);
}

[T, I, J when Integer?(I) and Integer?(J)]
overload remove(deque: Deque[T], fromN: I, toN: J) {
    remove(deque, deque.begin+fromN, deque.begin+toN);
}

[T]
overload remove(deque: Deque[T], from: DequeCoordinate[T], to: DequeCoordinate[T]) {
    assert["boundsChecks"](validDequeCoordinate?(deque, from),
        "invalid remove start coordinate into ", Deque[T]);
    assert["boundsChecks"](validDequeCoordinate?(deque, to),
        "invalid remove end coordinate into ", Deque[T]);
    if (from == deque.begin and to == deque.end)
        clear(deque);
    else {
        destroyDequeValues(from, to);

        var count = SizeT(to - from);
        var elemsBefore = SizeT(from - deque.begin);
        if (elemsBefore <= (size(deque) - count) \ SizeT(2)) {
            var newBegin = deque.begin + count;
            if (from != deque.begin)
                moveDequeValuesBackwards(newBegin, to, deque.begin);
            destroyDequeFrontNodes(deque, newBegin);
        } else {
            var newEnd = deque.end - count;
            if (to != deque.end)
                moveDequeValues(from, newEnd, to);
            destroyDequeBackNodes(deque, newEnd);
        }
    }
}

[T, I when Integer?(I)]
overload remove(deque: Deque[T], n: I) {
    remove(deque, deque.begin+n);
}

[T]
overload remove(deque: Deque[T], i: DequeCoordinate[T]) {
    assert["boundsChecks"](validDequeCoordinate?(deque, i),
        "invalid remove coordinate into ", Deque[T]);
    destroy(i^);
    var next = i;
    inc(next);
    var index = SizeT(i - deque.begin);
    if (index < size(deque) \ SizeT(2)) {
        var newBegin = deque.begin;
        inc(newBegin);
        if (i != deque.begin)
            moveDequeValuesBackwards(newBegin, next, deque.begin);
        if (newBegin.node != deque.begin.node)
            freeRawMemory(deque.begin.node^);
        deque.begin = newBegin;
    } else {
        var newEnd = deque.end;
        dec(newEnd);
        if (next != deque.end)
            moveDequeValues(i, newEnd, next);
        if (newEnd.node != deque.end.node)
            freeRawMemory(deque.end.node^);
        deque.end = newEnd;
    }
}

[T, I when Integer?(I)] overload resize(deque: Deque[T], newSize: I) {
    resize(deque, SizeT(newSize));
}

[T] overload resize(deque: Deque[T], newSize: SizeT) {
    var oldSize = size(deque);
    if (newSize < oldSize) {
        var newEnd = deque.begin + newSize;
        destroyDequeValues(newEnd, deque.end);
        destroyDequeBackNodes(deque, newEnd);
    } else {
        // XXX more efficient implementation
        for (i in range(newSize - oldSize))
            push(deque, T());
    }
}

// XXX deque comparison


/// @section  Deque implementation details 

private alias DEQUE_TARGET_BUFFER_SIZE = SizeT(512);
private alias DEQUE_INITIAL_MAP_SIZE = SizeT(8);

define DequeBufferSize;

overload DequeBufferSize(T) {
    if (TypeSize(T) < DEQUE_TARGET_BUFFER_SIZE)
        return DEQUE_TARGET_BUFFER_SIZE \ TypeSize(T);
    else
        return SizeT(1);
}

DequeBufferSSize(T) = PtrInt(DequeBufferSize(T));

private allocateNode(T) = allocateRawMemory(T, DequeBufferSize(T));

[T] private initializeDequeMap(deque: Deque[T], size: SizeT) {
    var numNodes = size \ DequeBufferSize(T) + SizeT(1);

    deque.mapSize = max(numNodes + 2, DEQUE_INITIAL_MAP_SIZE);
    deque.map = allocateRawMemory(Pointer[T], deque.mapSize);

    var nodeBegin = deque.map + (deque.mapSize - numNodes) \ 2;
    var nodeEnd = nodeBegin + numNodes;

    try { createDequeNodes(nodeBegin, nodeEnd); }
    catch(ex) {
        freeRawMemory(deque.map);
        deque.map = null(Pointer[T]);
        deque.mapSize = SizeT(0);
        throw ex;
    }

    setNode(deque.begin, nodeBegin);
    deque.begin.current = deque.begin.first;
    setNode(deque.end, nodeEnd - 1);
    deque.end.current = deque.end.first + size % DequeBufferSize(T);
}

[T] private destroyDequeMap(deque: Deque[T]) {
    destroyDequeNodes(deque.begin.node, deque.end.node + 1);
    freeRawMemory(deque.map);
}

[T] private destroyDequeValues(begin: DequeCoordinate[T], end: DequeCoordinate[T]) {
    var i = begin;
    while (i != end) {
        destroy(i^);
        inc(i);
    }
}

[T] private moveDequeValues(
    toBegin: DequeCoordinate[T],
    toEnd: DequeCoordinate[T],
    fromBegin: DequeCoordinate[T]
) {
    var toI = toBegin;
    var fromI = fromBegin;
    while (toI != toEnd) {
        toI^ <-- moveUnsafe(fromI^);
        inc(toI);
        inc(fromI);
    }
}

[T] private moveDequeValuesBackwards(
    toBegin: DequeCoordinate[T],
    toEnd: DequeCoordinate[T],
    fromBegin: DequeCoordinate[T]
) {
    var toI = toEnd;
    var fromI = fromBegin + (toEnd - toBegin);
    while (toI != toBegin) {
        dec(toI);
        dec(fromI);
        toI^ <-- moveUnsafe(fromI^);
    }
}

[T] private reserveMapFrontNodes(deque: Deque[T], count: SizeT) {
    if (count > deque.begin.node - deque.map)
        reallocateDequeMap(deque, count, true);
}

[T] private reserveMapBackNodes(deque: Deque[T], count: SizeT) {
    if (count + SizeT(1) > deque.mapSize - (deque.end.node - deque.map))
        reallocateDequeMap(deque, count, false);
}

[T] private reallocateDequeMap(deque: Deque[T], addCount: SizeT, addAtFront?: Bool) {
    var oldNodeCount = SizeT(deque.end.node - deque.begin.node) + SizeT(1);
    var newNodeCount = oldNodeCount + addCount;

    var newBeginNode = Pointer[Pointer[T]]();
    var frontOffset = SizeT();
    if (addAtFront?)
        frontOffset = addCount;
    else
        frontOffset = SizeT(0);
    if (deque.mapSize > SizeT(2)*newNodeCount) {
        newBeginNode = deque.map + (deque.mapSize - newNodeCount) \ SizeT(2) + frontOffset;
        moveMemoryUnsafe(
            newBeginNode,
            deque.begin.node,
            deque.begin.node + oldNodeCount,
        );
    } else {
        var newMapSize = deque.mapSize + max(deque.mapSize, addCount) + SizeT(2);
        var newMap = allocateRawMemory(Pointer[T], newMapSize);
        newBeginNode = newMap + (newMapSize - newNodeCount) \ SizeT(2) + frontOffset;
        moveMemoryUnsafe(
            newBeginNode,
            deque.begin.node,
            deque.begin.node + oldNodeCount,
        );

        freeRawMemory(deque.map);
        deque.map <-- newMap;
        deque.mapSize <-- newMapSize;
    }
    deque.begin.node = newBeginNode;
    deque.end.node = newBeginNode + oldNodeCount - SizeT(1);
}

[T] private createDequeNodes(begin: Pointer[Pointer[T]], end: Pointer[Pointer[T]]) {
    var i = begin;
    try {
        while (i < end) {
            i^ = allocateNode(T);
            inc(i);
        }
    } catch(ex) {
        destroyDequeNodes(begin, i);
        throw ex;
    }
}

[T] private destroyDequeNodes(begin: Pointer[Pointer[T]], end: Pointer[Pointer[T]]) {
    var i = begin;
    while (i < end) {
        freeRawMemory(i^);
        inc(i);
    }
}

[T] private destroyDequeFrontNodes(deque: Deque[T], newBegin: DequeCoordinate[T]) {
    destroyDequeNodes(deque.begin.node, newBegin.node);
    deque.begin = newBegin;
}

[T] private destroyDequeBackNodes(deque: Deque[T], newEnd: DequeCoordinate[T]) {
    destroyDequeNodes(newEnd.node + 1, deque.end.node + 1);
    deque.end = newEnd;
}

[T] private reserveDequeFrontElements(deque: Deque[T], count: SizeT) {
    var vacancies = deque.begin.current - deque.begin.first;
    if (count > vacancies)
        newDequeFrontElements(deque, count - vacancies);
    return deque.begin - count;
}

[T] private reserveDequeBackElements(deque: Deque[T], count: SizeT) {
    var vacancies = (deque.end.last - deque.end.current) - SizeT(1);
    if (count > vacancies)
        newDequeBackElements(deque, count - vacancies);
    return deque.end + count;
}

private printMap(deque) {
    for (x in CoordinateRange(deque.map, deque.map + deque.mapSize)) {
        print(@x, " => ", x);
        if (@x == deque.begin.node)
            println(" <- begin");
        else if (@x == deque.end.node)
            println(" <- end");
        else
            println();
    }
}

[T] private newDequeFrontElements(deque: Deque[T], count: SizeT) {
    var newNodes = SizeT(count + DequeBufferSize(T) - 1) \ DequeBufferSize(T);
    reserveMapFrontNodes(deque, newNodes);
    createDequeNodes(deque.begin.node - newNodes, deque.begin.node);
}

[T] private newDequeBackElements(deque: Deque[T], count: SizeT) {
    var newNodes = SizeT(count + DequeBufferSize(T) - 1) \ DequeBufferSize(T);
    reserveMapBackNodes(deque, newNodes);
    createDequeNodes(deque.end.node + 1, deque.end.node + newNodes + 1);
}

[T] private insertDequeValue(deque: Deque[T], i: DequeCoordinate[T], forward value) {
    var index = SizeT(i - deque.begin);
    if (index < size(deque) \ SizeT(2)) {
        deque.begin = reserveDequeFrontElements(deque, SizeT(1));
        var oldBegin = deque.begin;
        inc(oldBegin);
        i = oldBegin + index;
        var prev = i;
        dec(prev);
        moveDequeValues(deque.begin, prev, oldBegin);
        try {
            prev^ <-- value;
        } catch (ex) {
            resetUnsafe(prev^);
            throw ex;
        }
    } else {
        deque.end = reserveDequeBackElements(deque, SizeT(1));
        var oldEnd = deque.end;
        dec(oldEnd);
        i = deque.begin + index;
        var next = i;
        inc(next);
        moveDequeValuesBackwards(next, deque.end, i);
        try {
            i^ <-- value;
        } catch (ex) {
            resetUnsafe(i^);
            throw ex;
        }
    }
}

private define insertDequeSequence;

[T, S when Sequence?(S)]
overload insertDequeSequence(deque: Deque[T], i: DequeCoordinate[T], forward seq: S) {
    for (x in reversed(seq))
        insertDequeValue(deque, i, seq);
}

[T, S when SizedSequence?(S)]
overload insertDequeSequence(deque: Deque[T], i: DequeCoordinate[T], forward seq: S) {
    var index = SizeT(i - deque.begin);
    var seqSize = size(seq);
    if (index < size(deque) \ SizeT(2)) {
        deque.begin = reserveDequeFrontElements(deque, seqSize);
        var oldBegin = deque.begin + seqSize;
        i = oldBegin + index;
        var prev = i - seqSize;
        moveDequeValues(deque.begin, prev, oldBegin);

        var ii = prev;
        try {
            for (x in seq) {
                ii^ <-- x;
                inc(ii);
            }
        } catch (ex) {
            while (ii != i) {
                resetUnsafe(ii^);
                inc(ii);
            }
            throw ex;
        }
    } else {
        deque.end = reserveDequeBackElements(deque, seqSize);
        var oldEnd = deque.end - seqSize;
        i = deque.begin + index;
        var next = i + seqSize;
        moveDequeValuesBackwards(next, deque.end, i);

        var ii = i;
        try {
            for (x in seq) {
                ii^ <-- x;
                inc(ii);
            }
        } catch (ex) {
            while (ii != next) {
                resetUnsafe(ii^);
                inc(ii);
            }
            throw ex;
        }
    }
}

[T] private pushFrontDeque1(deque: Deque[T], forward value) {
    reserveMapFrontNodes(deque, SizeT(1));
    var newBeginNode = deque.begin.node - 1;
    newBeginNode^ = allocateNode(T);
    setNode(deque.begin, newBeginNode);
    deque.begin.current = deque.begin.last - 1;
    try {
        deque.begin.current^ <-- value;
    } catch(ex) {
        inc(deque.begin);
        freeRawMemory(newBeginNode^);
        throw ex;
    }
}

[T] private pushDeque1(deque: Deque[T], forward value) {
    reserveMapBackNodes(deque, SizeT(1));
    var newEndNode = deque.end.node + 1;
    newEndNode^ = allocateNode(T);
    try {
        deque.end.current^ <-- value;
    } catch(ex) {
        freeRawMemory(newEndNode^);
        throw ex;
    }
    setNode(deque.end, newEndNode);
    deque.end.current = deque.end.first;
}

[T] private popFrontDeque1(deque: Deque[T]) --> value: T {
    value <-- moveUnsafe(deque.begin.current^);
    freeRawMemory(deque.begin.first);
    setNode(deque.begin, deque.begin.node + 1);
    deque.begin.current = deque.begin.first;
}

[T] private popDeque1(deque: Deque[T]) {
    freeRawMemory(deque.end.first);
    setNode(deque.end, deque.end.node - 1);
    deque.end.current = deque.end.last - 1;
    return moveUnsafe(deque.end.current^);
}