


//
// generic vector requirements
//

define Vector?;
overload Vector?(x) = false;

define vectorData;
define vectorSize;
define vectorSetSize;
define vectorCapacity;
define vectorRequestCapacity;



//
// predicates
//

[V | Vector?(V)]
overload ContiguousSequence?(static V) = true;



//
// size, index
//

[V | Vector?(V)]
inline overload size(a:V) = vectorSize(a);

[V,I | Vector?(V) and Integer?(I)]
inline overload index(a:V, i:I) {
    assert[#boundsChecks](i >= 0 and i < size(a),
        V, " index out of bounds");
    return ref (vectorData(a) + SizeT(i))^;
}



//
// vector coordinates
//

alias VectorCoordinate[T] = Pointer[T];

[V | Vector?(V)]
inline overload begin(a:V) = vectorData(a);

[V | Vector?(V)]
inline overload end(a:V) = vectorData(a) + size(a);



//
// vector iteration
//

[V | Vector?(V)]
inline overload iterator(a:V) = coordinateRange(begin(a), end(a));

[V | Vector?(V)]
inline overload reverseIterator(a:V) =
    reverseCoordinateRange(end(a), begin(a));



//
// equals?, lesser?
//

[V | Vector?(V)]
overload equals?(a:V, b:V) {
    if (size(a) != size(b))
        return false;
    for (x, y in zipped(a, b)) {
        if (x != y)
            return false;
    }
    return true;
}

[V | Vector?(V)]
overload lesser?(a:V, b:V) {
    for (x, y in zipped(a, b)) {
        if (x != y)
            return x < y;
    }
    return size(a) < size(b);
}



//
// front, back, push, pop
//

[V | Vector?(V)]
inline overload front(a:V) = ref a[0];

[V | Vector?(V)]
inline overload back(a:V) = ref a[size(a) - 1];

[V, S | Vector?(V) and Sequence?(S) and (SequenceElementType(S) == SequenceElementType(V))]
overload push(a:V, forward seq:S) {
    insert(a, size(a), seq);
}

[V, T | Vector?(V) and (SequenceElementType(V) == T)]
overload push(a:V, forward x:T) {
    insert(a, size(a), x);
}

[V, A1, A2, ..AA | Vector?(V)]
inline overload push(v:V, forward e1:A1, forward e2:A2, forward ..ee:AA) {
    reserve(v, countValues(A1, A2, ..AA));
    ..for (x in e1, e2, ..ee) {
        push(v, x);
    }
}

[V | Vector?(V)]
inline overload push(v:V) { }

[V | Vector?(V)]
overload pop(a:V) {
    assert(not empty?(a), "pop of empty ", V);
    var temp = moveUnsafe(back(a));
    removeLocations(a, end(a)-1, end(a));
    return move(temp);
}



//
// reserve, resize, resizeUnsafe, ensureSpace
//

[V, I | Vector?(V) and Integer?(I)]
overload reserve(a:V, n:I) {
    if (vectorCapacity(a) < SizeT(n))
        vectorRequestCapacity(a, SizeT(n));
}

[V, I | Vector?(V) and Integer?(I)]
inline overload resize(a:V, n:I) {
    resizeInternal(a, SizeT(n), initializeMemory);
}

[V, I | Vector?(V) and Integer?(I)]
inline overload resizeUnsafe(a:V, n:I) {
    resizeInternal(a, SizeT(n), resetMemoryUnsafe);
}

[V | Vector?(V)]
private resizeInternal(a:V, n:SizeT, initializer) {
    var currentSize = vectorSize(a);
    if (currentSize < n) {
        reserve(a, n);
        initializer(end(a), begin(a)+n);
    }
    else if (currentSize > n) {
        destroyMemory(begin(a)+n, end(a));
    }
    vectorSetSize(a, n);
}

private inline ensureSpace(a, space:SizeT) {
    reserve(a, size(a) + space);
}



//
// insert
//

[I, J | Integer?(I) and Integer?(J)]
private insertLocationsUnsafe(a, pos:I, n:J) {
    return ..insertLocationsUnsafe(a, SizeT(pos), SizeT(n));
}

overload insertLocationsUnsafe(a, pos:SizeT, n:SizeT) {
    ensureSpace(a, n);
    var first = begin(a) + pos;
    moveMemoryUnsafe(first+n, first, end(a));
    vectorSetSize(a, vectorSize(a) + n);
    return first, first+n;
}

[V,I,S | Vector?(V) and Integer?(I) and Sequence?(S) and
         (SequenceElementType(S) == SequenceElementType(V))]
overload insert(a:V, i:I, seq:S) {
    assert(i >= 0 and i <= size(a), "invalid position for insert into ", V);
    var pos = SizeT(i);
    var iter = iterator(seq);
    while (hasNext?(iter)) {
        insert(a, pos, next(iter));
        pos += 1;
    }
}

[V,I,S | Vector?(V) and Integer?(I) and SizedSequence?(S) and
         (SequenceElementType(S) == SequenceElementType(V))]
overload insert(a:V, i:I, seq:S) {
    assert(i >= 0 and i <= size(a), "invalid position for insert into ", V);
    var first, last = ..insertLocationsUnsafe(a, i, size(seq));
    try {
        var iter = iterator(seq);
        while (hasNext?(iter)) {
            first^ <-- next(iter);
            inc(first);
        }
    }
    catch (e) {
        resetMemoryUnsafe(first, last);
        throw e;
    }
}

[V,I,S | Vector?(V) and Integer?(I)
         and SizedSequence?(S) and ContiguousSequence?(S)
         and (SequenceElementType(S) == SequenceElementType(V))]
overload insert(a:V, i:I, seq:S) {
    assert(i >= 0 and i <= size(a), "invalid position for insert into ", V);
    var first, last = ..insertLocationsUnsafe(a, i, size(seq));
    try {
        var src = begin(seq);
        copyNonoverlappingMemory(first, src, src+size(seq));
    }
    catch (e) {
        resetMemoryUnsafe(first, last);
        throw e;
    }
}

[V,I,S | Vector?(V) and Integer?(I)
         and SequenceContainer?(S) and SizedSequence?(S)
         and (SequenceElementType(S) == SequenceElementType(V))]
overload insert(a:V, i:I, rvalue seq:S) {
    assert(i >= 0 and i <= size(a), "invalid position for insert into ", V);
    var first, last = ..insertLocationsUnsafe(a, i, size(seq));
    for (x in seq) {
        first^ <-- move(x);
        inc(first);
    }
}

[V,I,S | Vector?(V) and Integer?(I)
         and SequenceContainer?(S) and ContiguousSequence?(S)
         and (SequenceElementType(S) == SequenceElementType(V))]
overload insert(a:V, i:I, rvalue seq:S) {
    assert(i >= 0 and i <= size(a), "invalid position for insert into ", V);
    var first, last = ..insertLocationsUnsafe(a, i, size(seq));
    var src = begin(seq);
    moveNonoverlappingMemory(first, src, src+size(seq));
}

[V,I,T | Vector?(V) and Integer?(I) and (SequenceElementType(V) == T)]
overload insert(a:V, i:I, ref x:T) {
    // NOTE: when 'x' is an lvalue, it _may_ be pointing inside 'a'.
    // so make a copy and insert it as an rvalue.
    insert(a, i, copy(x));
}

[V,I,T | Vector?(V) and Integer?(I) and (SequenceElementType(V) == T)]
overload insert(a:V, i:I, rvalue x:T) {
    var first, last = ..insertLocationsUnsafe(a, i, 1);
    first^ <-- move(x);
}

[V,T,S | Vector?(V) and (SequenceElementType(V) == T) and
         Sequence?(S) and (SequenceElementType(S) == T)]
overload insert(a:V, i:VectorCoordinate[T], forward seq:S) {
    insert(a, i-begin(a), seq);
}

[V,T | Vector?(V) and (SequenceElementType(V) == T)]
overload insert(a:V, i:VectorCoordinate[T], forward x:T) {
    insert(a, i-begin(a), x);
}



//
// clear, remove
//

[V | Vector?(V)]
inline overload clear(a:V) {
    remove(a, begin(a), end(a));
}

[V,T | Vector?(V) and SequenceElementType(V) == T]
private validVectorCoordinate?(v:V, i:VectorCoordinate[T])
    = i >= begin(v) and i <= end(v);

[V,T | Vector?(V) and (SequenceElementType(V) == T)]
private removeLocations(a:V, i:VectorCoordinate[T], j:VectorCoordinate[T]) {
    assert[#boundsChecks](validVectorCoordinate?(a, i),
        "invalid first coordinate for remove from ", V);
    assert[#boundsChecks](validVectorCoordinate?(a, j),
        "invalid last coordinate for remove from ", V);
    var n = end(a) - j;
    moveMemoryUnsafe(i, j, end(a));
    vectorSetSize(a, vectorSize(a) - (j-i));
}

[V,T | Vector?(V) and (SequenceElementType(V) == T)]
overload remove(a:V, i:VectorCoordinate[T], j:VectorCoordinate[T]) {
    assert[#boundsChecks](validVectorCoordinate?(a, i),
        "invalid first coordinate for remove from ", V);
    assert[#boundsChecks](validVectorCoordinate?(a, j),
        "invalid last coordinate for remove from ", V);
    destroyMemory(i, j);
    removeLocations(a, i, j);
}

[V,T | Vector?(V) and (SequenceElementType(V) == T)]
overload remove(a:V, i:VectorCoordinate[T]) {
    remove(a, i, i+1);
}

[V,I | Vector?(V) and Integer?(I)]
overload remove(a:V, i:I) {
    remove(a, begin(a)+i);
}

[V,I,J | Vector?(V) and Integer?(I) and Integer?(J)]
overload remove(a:V, i:I, j:J) {
    remove(a, begin(a)+i, begin(a)+j);
}
