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)->Void
    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{VectorHeap.new}

class VectorHeap.new{

    var data:Vector is readable:= vector.new
    
    // Returns parent index
    // @param i a node index
    // @return parent of node at i
    // @pre 1 <= i <= size
    // @post returns parent of node at location i
    method parent(i:Number)->Number is confidential{
        var x:Number := i / 2
        return x.truncate}

    // Returns left child index
    // @param i a node index
    // @return left child of node at i
    // @pre 1 <= i <= size
    // @post returns index of left child of node at location i
    method left(i:Number)->Number is confidential{2 * i}

    // Returns right child index
    // @param i a node index
    // @return right child of node at i
    // @pre 1 <= i <= size
    // @post returns index of right child of node at location i
    method right(i:Number)->Number is confidential{2 * i + 1}

    // Fetch lowest valued (highest priority) item from queue
    // @pre !isEmpty
    // @post @return minimum value in priority queue
    method getFirst->Dynamic is public{data.at(1)}

    // Returns minimum value from queue
    // @pre !isEmpty
    // @post return and remove min value
    // @return min value
    method remove->Dynamic is public{
        var minVal:Dynamic := getFirst
        data.setValue(data.at(data.size))at(1)
        data.setSize(data.size - 1)
        if (data.size > 1) then {pushDownRoot(1)}
        return minVal}

    // Add value to priority queue
    // @pre value is non-null comparable
    // @post value is added to priority queue
    // @param value the value to be added
    method add(value:Dynamic)->Void is public{
        data.addLast(value)
        percolateUp(data.size)}

    // Determine if queue is empty
    // @post @return true iff no elements in queue
    method isEmpty->Boolean is public{data.size == 0}

    // Moves node upward to appropriate position in heap
    // @param leaf index of node in heap
    // @pre 1 <= leaf <= size
    // @post moves node at index leaf up to appropriate position
    method percolateUp(leaf:Number)->Void is confidential{
        var parIndex:Number := 
            if(parent(leaf) == 0) then{1}
            else{parent(leaf)}
        var value:Dynamic := data.at(leaf)
        while{(leaf > 1)  && (value < data.at(parIndex))} do{
            data.setValue(data.at(parIndex))at(leaf)
            leaf := parIndex
            parIndex := 
                if(parent(leaf) == 0) then{1}
                else{parent(leaf)}
        }
        data.setValue(value)at(leaf)}

    // Moves node downward, into appropriate position in subheap
    // @param root index of the root in subheap
    // @pre 1 <= root <= size
    // @post moves node at index root down to appropriate position
    method pushDownRoot(root:Number)->Void is confidential{
        var heapSize:Number := data.size
        var value:Dynamic := data.at(root) 
        while{root <= heapSize} do{
            var childpos:Number := left(root)
            if(childpos <= heapSize) then{
                if(right(root) <= heapSize) then{
                    if(data.at(childpos + 1) < data.at(childpos)) then{
                        childpos := childpos + 1}}
                var getCP:Dynamic := data.at(childpos)
                if(getCP < value) then{
                    data.setValue(getCP)at(root)
                    root := childpos}
                else{
                    data.setValue(value)at(root)
                    return None}
                }
            else{
                data.setValue(value)at(root)
                return None}
        }
    }

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

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

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