import unsafe.memory.* import values.* import hashing.( hash hashSequence ) import sequences.( equalSequence? lesserSequence? ) import containers.* import unsafe.compositetypes.* import unsafe.coordinates.* import unsafe.valuesemantics.* def Vector['T] as CompositeType(size:UInt, capacity:UInt, data:ContiguousCoordinate['T]) extend #Container?(Vector['T]) = true extend Vector['T]() = initializeRecord(Vector['T], 0u, 0u, ContiguousCoordinate['T]()) extend #InitializeDoesNotThrow?(Vector['T]) = true extend #BitwiseZeroInitialized?(Vector['T]) = true extend Vector['T](forward s:'S) inline --> returned:Vector['T] | Sequence?('S) and sequenceElementType('S) == 'T returned <-- Vector['T]() try push(returned, s) catch ex destroy(returned) throw ex extend Vector(forward s:'S) inline | Sequence?('S) = Vector[sequenceElementType('S)](s) extend Vector['T](..forward elements:'TT) inline --> returned:Vector['T] | not emptyValues?(..'TT) and equalValues?('T, ..'TT) returned <-- Vector['T]() try push(returned, ..elements) catch ex destroy(returned) throw ex extend copyAssign(ref to:Vector['T], from:Vector['U]) inline | AssignableTypes?('T, 'U) resizeUnsafe(to, size(from)) assignRange(begin(to), begin(from), end(from)) extend destroy(ref a:Vector['T]) inline destroyRange(begin(a), end(a)) freeUninitializedValues(a.data) extend copy(a:Vector['T]) inline = Vector['T](a) extend size(v:Vector['T]) inline = v.size extend index(forward v:Vector['T], i:'I) inline | Integer?('I) = forward v.data[i] extend index(rvalue v:Vector['T], i:'I) inline var w = v return w.data[i] extend begin(v:Vector['T]) inline = v.data extend end(v:Vector['T]) inline = v.data + v.size extend push(ref v:Vector['T], ..forward elements:'TT) inline | countValues(..'TT) != 1 and allValues?((U) -> callDefined?(push, Ref[Vector['T]], U), ..'TT) reserve(v, countValues(..'TT)) static for forward e in ..elements push(v, e) extend push(ref v:Vector['T], forward seq:'S) inline | Sequence?('S) and sequenceElementType('S) == 'T insert(v, size(v), seq) extend push(ref v:Vector['T], forward elt:'T) inline insert(v, size(v), elt) extend pop(ref v:Vector['T]) inline --> returned:'T returned <-- moveRvalue(back(v)) removeLocations(v, end(v) - 1, end(v)) extend reserve(ref v:Vector['T], n:'I) inline | Integer?('I) if v.capacity < UInt(n) requestCapacity(v, UInt(n)) extend resize(ref v:Vector['T], n:'I) inline | Integer?('I) resizeInternal(v, UInt(n), initializeRange) extend resizeUnsafe(ref v:Vector['T], n:'I) inline | Integer?('I) resizeInternal(v, UInt(n), resetRange) extend insert(ref v:Vector['T], i:'I, seq:'S) | Integer?('I) and Sequence?('S) and sequenceElementType('S) == 'T var pos = UInt(i) var iter = iterator(seq) while hasNext?(iter) insert(v, pos, next(iter)) pos += 1u extend insert(ref v:Vector['T], i:'I, seq:'S) | Integer?('I) and SizedSequence?('S) and sequenceElementType('S) == 'T var first, last = ..insertLocations(v, UInt(i), size(seq)) try var iter = iterator(seq) while hasNext?(iter) first^ <-- next(iter) inc(first) catch ex resetRange(first, last) throw ex extend insert(ref v:Vector['T], i:'I, x:'T) | Integer?('I) var first, last = ..insertLocations(v, UInt(i), 1u) try first^ <-- x catch ex reset(first^) throw ex extend insert(ref v:Vector['T], i:'I, rvalue x:'T) | Integer?('I) var first, last = ..insertLocations(v, UInt(i), 1u) first^ <-- x extend insert(ref v:Vector['T], i:ContiguousCoordinate['T], forward seq:'S) | Sequence?('S) and sequenceElementType('S) == 'T insert(v, i - begin(v), seq) extend insert(ref v:Vector['T], i:ContiguousCoordinate['T], x:'T) insert(v, i - begin(v), x) extend clear(ref v:Vector['T]) inline remove(v, begin(v), end(v)) extend remove(ref v:Vector['T], i:ContiguousCoordinate['T], j:ContiguousCoordinate['T]) inline destroyRange(i, j) removeLocations(v, i, j) extend remove(ref v:Vector['T], i:ContiguousCoordinate['T]) inline remove(v, i, i + 1) extend remove(ref v:Vector['T], i:'I) inline | Integer?('I) remove(v, begin(v) + i) extend remove(ref v:Vector['T], i:'I, j:'J) inline | Integer?('I) and Integer?('J) remove(v, begin(v) + i, begin(v) + j) private def requestCapacity(ref v:Vector['T], capacity:UInt) assert(-> capacity >= v.size) if capacity < v.capacity return var n = max(capacity, 16u) n = max(n, 2u * v.capacity) reallocVector(v, n) private def reallocVector(ref v:Vector['T], capacity:UInt) var data = allocateUninitializedValues(capacity, 'T) moveRvalueNonoverlappingRange(data, v.data, v.data + v.size) freeUninitializedValues(v.data) v.data = data v.capacity = capacity extend reallocVector(ref v:Vector['T], capacity:UInt) | BitwiseMoved?('T) v.data = reallocateUninitializedValues(capacity, v.data) v.capacity = capacity private def resizeInternal(ref v:Vector['T], n:UInt, initializer) if v.size < n reserve(v, n) initializer(end(v), begin(v) + n) else if v.size > n destroyRange(begin(v) + n, end(v)) v.size = n private def ensureSpace(ref v, space) inline reserve(v, v.size + space) private def insertLocations(ref v:Vector['T], pos:UInt, n:UInt) ensureSpace(v, n) var first = begin(v) + pos moveRvalueRange(first + n, first, end(v)) v.size += n return first, first + n private def removeLocations(ref v:Vector['T], from:ContiguousCoordinate['T], to:ContiguousCoordinate['T]) var n = end(v) - to moveRvalueRange(from, to, end(v)) v.size -= UInt(to - from) extend equals?(a:Vector['A], b:Vector['B]) inline | callDefined?(equals?, 'A, 'B) = equalSequence?(a, b) extend lesser?(a:Vector['A], b:Vector['B]) inline | callDefined?(lesser?, 'A, 'B) = lesserSequence?(a, b) extend hash(v:Vector['V]) = hashSequence(v)