import vector

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

type Vector = {
    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)->Vector
    ensureCapacity(_:Number)->Void
    capacity->Number
    copyInto(_)->Void
    indexOf(_:T)startingFrom(_:Number)->Number
    setSize(_:Number)->Void
    trimToSize->Void}


// T needs to have <(_:T)->Boolean as a method
type PriorityQueue = {
    getFirst->T
    remove->T
    add(_:T)->Void
    isEmpty->Boolean
    size->Number
    clear->Void
    asString->String}

method new->PriorityQueue is public{PriorityVector.new}

class PriorityVector.new{
    // Data maintained in increasing order
    var data:Vector is readable := vector.new

    // Fetch smallest value of priority queue
    // @pre !isEmpty
    // @post @return minimum value in priority queue
    method getFirst->Dynamic is public{data.at(1)}
    
    // Remove smallest value of structure
    // @pre !isEmpty
    // @post remove and return min value in priority queue
    // @return smallest value of structure
    method remove->Dynamic is public{data.removeFirst}

    // @pre value is Number (until we make Comparables)
    // @post inserts value in priority queue, leaves elements in order
    // @param value the value to be added
    method add(value:Dynamic)->Void is public{
        var position:Number := indexOf(value)
        data.add(value)at(position)}

    method indexOf(target:Dynamic)->Number is confidential{
        var midValue:Dynamic
        var low:Number := 1 //lowest possible location
        var high:Number := data.size + 1 //highest possible location
        var mid:Number := ((low + high)/2).truncate
        while {low < high} do {
            if(mid < high) then {
                midValue := data.at(mid)
                if(midValue < target) then {low := mid + 1}
                else{high := mid}
                mid := ((low + high)/2).truncate}
        }
        return low}

    // @post @return true iff priority queue is empty
    method isEmpty->Boolean is public{data.size == 0}

    // @post @return number of elements in priority queue
    method size->Number is public{data.size}

    // @post removes all elements from priority queue
    method clear->Void is public{data.clear}

    // @post @return string representation of priority vector
    method asString->String is public{""}
}