type Iterator = {
    reset->Void
    hasNext->Boolean
    get->T
    next->T}

type Collection = {
    size->Number
    isEmpty->Boolean
    clear->Void
    contains(_:T)->Boolean
    addFirst(_:T)->Void
    addLast(_:T)->Void
    firstElement->T
    lastElement->T
    removeFirst->T
    removeLast->T
    removeValue(_:T)->T
    indexOf(_:T)->Number
    at(_:Number)->T
    setValue(_:T)at(_:Number)->T
    add(_:T)at(_:Number)->Void
    removeFromIndex(_:Number)->T
    iterator->Iterator
    asString->String
    forEachDo(_:Block)->Void
    map(_:Block)->Collection}

type Vector = Collection & {
    ensureCapacity(_:Number)->Void
    capacity->Number
    copyInto(_)->Void
    indexOf(_:T)startingFrom(_:Number)->Number
    setSize(_:Number)->Void
    trimToSize->Void}

// object to return as null value
def missing is public, readable = object{
    method asString->String{"-"}
}

def defaultCapacity:Number is public, readable= 10

method new->Vector is public{VectorClass.new(defaultCapacity, 0, missing)}

method withSize(cap:Number)->Vector is public{VectorClass.new(cap, 0, missing)}

method withSize(cap:Number)increment(inc:Number)->Vector is public{
    VectorClass.new(cap, inc, missing)}

method withSize(cap:Number)increment(inc:Number)initialVal(initVal)->Vector is public{
    VectorClass.new(cap, inc, initVal)}

class VectorClass.new(cap:Number, inc:Number, initVal:Dynamic){

    // Data associated with vector. Size of array always
    // at least as large as the vector. The array is only
    // extended when necessary.
    var elementData is private := PrimitiveArray.new(cap)

    // Actual number of elements logically stored within
    // vector. May be smaller than length of array.
    var elementCount:Number is readable := 0

    // Size of size increment, should vector become full.
    // 0 indicates vector should be doubled when capacity
    // of array reached.
    var capacityIncrement:Number is readable:= inc

    // Initial value of any new elements appended to vector.
    // By default, missing. 
    var initialValue:Dynamic is readable:= initVal
    
    // Ensure vector capable of holding at least
    // minCapacity values w/o expansion.
    // @post capacity is at least minCapacity
    // @param minCapacity minimum size of array before expansion
    method ensureCapacity(minCapacity:Number)->Void is public{
        if(elementData.size < minCapacity) then{
            var newSize:Number := elementData.size
            if(capacityIncrement == 0) then{
            // increment of 0 suggests doubling
                if(newSize == 0) then {newSize := 1}
                while{newSize < minCapacity} do {newSize := newSize * 2}
            }
            else{
                while{newSize < minCapacity} do{
                    newSize := newSize + capacityIncrement}
            }
            var newElementData := PrimitiveArray.new(newSize)
            for(0..(elementCount - 1)) do{i->
                newElementData[i] := elementData[i]}
            elementData := newElementData}
    }
    
    // Add element to low end of array, possibly expanding vector
    // @post adds new element to beginning of possibly extended vector
    // @param val the new value to be added to beginning of vector
    method addFirst(val:Dynamic)->Void is public{add(val)at(1)}

    // Add element to high end of array, possibly expanding vector
    // @post adds new element to end of possibly extended vector
    // @param val new value to be added to end of vector
    method addLast(val:Dynamic)->Void is public{
        ensureCapacity(elementCount + 1)
        elementData[elementCount] := val
        elementCount := elementCount + 1}

    // Remove element from low end of array
    // @pre !isEmpty
    // @post removes element from beginning of vector
    // @return element removed
    method removeFirst->Dynamic is public{removeFromIndex(1)}

    // Remove element from high end of array
    // @pre !isEmpty
    // @post removes element from end of vector
    // @return element removed
    method removeLast->Dynamic is public{removeFromIndex(size)}

    // Remove an element, by value, from vector
    // @post element equal to parameter is removed and returned
    // @param val the element to be removed
    // @return the element removed
    method removeValue(val:Dynamic)->Dynamic is public{
        var result := missing
        var i:Number := indexOf(val)
        if(i > 0) then{
            result := at(i)
            removeFromIndex(i)}
        return result}

    // Determine capacity of vector. The capacity is always
    // at least as large as its size.
    // @post returns allocated size of vector
    // @return size of array underlying vector
    method capacity->Number is public{elementData.size}

    // Determine if value appears in vector.
    // @post returns true iff vector contains value
    // @param val is the value sought
    // @return true iff the value appears in vector
    method contains(val:Dynamic)->Boolean is public{
        for(0..(elementCount - 1)) do{i->
            if(val == elementData[i]) then {return true}}
        return false}

    // Copy contents of vector into an array.
    // Array must be large enough to accept all values
    // in vector.
    // @pre dest has at least size elements
    // @post copy of vector is stored in the dest array
    // @param dest an array of size at least size
    method copyInto(dest)->Void is public{
        if(dest.size < size) then {print "Destination array not large enough"}
        else{
            for(0..(elementCount - 1)) do{i->
                dest[i] := elementData[i]}}
    }

    // Fetch element at particular index.
    // Primitive arrays indexed from 0, but user will 
    // index from 1.
    // @pre 1<= index && index <= size
    // @post returns element stored in location indes
    // @param index the index of value sought
    // @return reference to value found in vector
    method at(index:Number)->Dynamic is public{
        if((1 > index) || (index > size)) then{
            print "02Invalid index {index}"
            return missing}
        else{return elementData[index - 1]}
    }

    // At access to first element of vector
    // @pre vector contains an element
    // @post returns first value in vector
    // @return access to first element of vector
    method firstElement->Dynamic is public{at(1)}

    // Assuming data is not in order, find the index
    // of a value or return -1 if not found.
    // @post returns index of element equal to val or -1; starts at first
    // @param val the value sought in vector
    // @return the index of the first occurrence of the value
    method indexOf(val:Dynamic)->Number is public{indexOf(val)startingFrom(1)}

    // @post returns index of element; starts at index
    // @param val the value sought
    // @param index the first location considered
    // @return the index of the first location or -1
    method indexOf(val:Dynamic)startingFrom(index:Number)->Number is public{
        for(index..elementCount) do {i->
            if(val == elementData[i - 1]) then{return i}
        }
        return -1}

    // Insert element at particular location
    // @pre 1 <= index <= size + 1
    // @post inserts new value in vector w/desired index
    // moving elements from index to size -1 to right
    // @param val the value to be inserted
    // @param index the location of new value
    method add(val:Dynamic)at(index:Number)->Void is public{
        if(index >= (size + 1)) then {addLast(val)}
        else{
            var previous := at(index)
            add(previous)at(index + 1)
            setValue(val)at(index)}
    }

    // Determine if vector contains no values
    // @post returns true iff there are no elements in vector
    // @return true iff vector is empty
    method isEmpty->Boolean is public{size == 0}

    // Fetch reference to last value in vector
    // @pre vector is not empty
    // @post @return last element of vector
    method lastElement->Dynamic is public{at(elementCount)}
    
    // Remove all the values of the vector.
    // @post vector is empty
    method clear->Void is public{setSize(0)}

    // Remove element at a particular location.
    // @pre 1 <= i && i <= size
    // @post indicated element removed, size decreases by 1
    // @return the element removed
    // @param i the location of the element to be removed
    method removeFromIndex(i:Number)->Dynamic is public{
        if((i < 1) || (i > size)) then {
            print "00Invalid index {i}"
            return missing}
        else{
            var result := at(i)
            elementCount := elementCount  - 1
            while{i <= elementCount} do {
                elementData[i - 1] := elementData[i]
                i := i + 1}
            elementData[elementCount] := missing
            return result}
    }

    // Change value stored at location index.
    // @pre 1 <= index && i <= size
    // @post element value changed to val
    // @param val the new value to be stored
    // @param index the index of the new value
    method setValue(val:Dynamic)at(index:Number)->Dynamic is public{
        if((index < 1) || (index > size)) then {
            print "01nvalid index {index}"
            return missing}
        else{
            var previous := elementData[index - 1]
            elementData[index - 1] := val
            return previous}
    }

    // Explicitly set size of array.
    // Any new elements initialized to default value.
    // @pre newSize >= 0
    // @post vector is resized, any new elements are initialized
    // @param newSize the ultimate size of the vector
    method setSize(newSize:Number)->Void is public{
        if(newSize < elementCount) then{
            for(newSize..(elementCount-1)) do{i->
                elementData[i] := missing}
        }
        else{
            ensureCapacity(newSize)
            for(elementCount..(newSize-1)) do{i->
                 elementData[i] := initialValue}
        }
        elementCount := newSize}

    // Determine number of elements in vector.
    //  @post @return size of vector
    method size->Number is public{elementCount}

    // Trim vector to exactly correct size.
    // @post minimizes allocated size of vector
    method trimToSize->Void is public{
        var newElementData := PrimitiveArray.new(elementCount)
        copyInto(newElementData)
        elementData := newElementData}

    // Determine string representation for vector.
    // @post @return string representation of vector
    method asString->String is public{
        var s:String := "
            s := s ++ " {at(i)}"}
        s := s ++ ">"
        return s}
    
    // Construct iterator over elements of vector.
    // Iterator considers elements with increasing index.
    // @post @return iterator to traverse vector
    method iterator->Iterator is public{VectorIterator.new(self)}
    
    // Performs closure for each element in vector
    method forEachDo(closure:Block)->Void is public{
        for(1..size) do {i->
            closure.apply(at(i))}
    }

    // Applies function to each element in vector
    method map(fun:Block)->Vector is public{
        var result:Vector := VectorClass.new(size, inc, initVal)
        for(1..size) do {i->
            result.addLast(fun.apply(at(i)))}
        return result
    }
}


class VectorIterator.new(v:Vector){

    // The associated vector
    var theVector:Vector is readable := v

    // The index of the current value
    var current:Number is readable:= 1
    
    // @post iterator reset to beginning of traversal
    method reset->Void is public{current := 1}

    // Determine if some elements yet to be considered
    // @post @return true if more elements to be considered
    method hasNext->Boolean is public{current <= theVector.size}

    // Fetch reference to current value
    // @pre traversal has more elements
    // @post @return reference to current value being considered
    method get->Dynamic is public{theVector.at(current)}

    // Return current value and increment iterator
    // @pre traversal has more elements
    // @post increments iterated traversal
    // @return reference to current value, before increment
    method next->Dynamic is public{
        var nextItem := theVector.at(current)
        current := current + 1
        return nextItem}
}