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}

type Set = {
    clear->Void
    isEmpty->Void
    add(_:T)->Void
    removeValue(_:T)->T
    contains(_:T)->Boolean
    containsAll(_:Set)->Boolean
    clone->Set
    addAll(_:Set)->Void
    retainAll(_:Set)->Void
    removeAll(_:Set)->Void
    iterator->Iterator
    size->Number
    asString->String}

method new->Set is public{SetVector.new}

class SetVector.new{

    // underlying structure; new, empty set
    var data:Vector is readable := vector.new

    // @post removes all elements from the set
    method clear->Void is public{data.clear}
 
    // @post @return true iff set is empty
    method isEmpty->Boolean is public{data.isEmpty}

    // Add element to set if not already present
    // @pre is non-null (whatever that means for Grace) object
    // @post adds element e to set
    // @param e new value to be added
    method add(e)->Void is public{
        if(!data.contains(e)) then{data.addLast(e)}
    }

    // Remove element froms set
    // @pre e is non-null* object
    // @post e removed, value returned
    // @param e the element of the set to be removed
    // @return value actually removed
    method removeValue(e)->Dynamic is public{data.removeValue(e)}

    // @pre e is non-null*
    // @post @return true iff e is in set
    // @param e the element sought
    method contains(e)->Boolean is public{data.contains(e)}

    // Determine if this set is a subset of other
    // @pre other is reference to set
    // @post @return true iff this set subset of other
    // @param other the potential superset
    method containsAll(other:Set)->Boolean is public{
        var myElements:Iterator := data.iterator
        while {myElements.hasNext} do {
            if(!other.contains(myElements.next)) then {return false}
        }
        return true}

    // Returns shallow clone of this set.
    // @post @return new set with same values
    method clone->Set is public{
        var result:Set := SetVector.new
        var myElements:Iterator := iterator
        while {myElements.hasNext} do {
            result.add(myElements.next)}
        return result}

    // Compute union of this set with other
    // @pre other is reference to set
    // @post add all elements of other to set, if needed
    // @param other the set to be unioned with this
    method addAll(other:Set)->Void is public{
        var yourElements:Iterator := other.iterator
        while {yourElements.hasNext} do {
            add(yourElements.next)}
    }
    
    // Compute intersection of this set and other
    // Members of result are in both this and other
    // @pre other is reference to set
    // @post @return set containing intersection of this and other
    // @param other the other set to be intersected with this
    method retainAll(other:Set)->Void is public{
        var temp:Set := SetVector.new
        var myElements:Iterator := data.iterator
        while {myElements.hasNext} do {
            var v := myElements.next
            if(other.contains(v)) then {temp.add(v)}
        }
        clear
        addAll(temp)}

    // Compute difference between two sets
    // Values of the result are members of this, but not other
    // @pre other is reference to set
    // @post @return set containing difference of this and other
    // @param other the set whose values are to be eliminated from
    method removeAll(other:Set)->Void is public{
        var yourElements:Iterator := other.iterator
        while {yourElements.hasNext} do {
            removeValue(yourElements.next)}
    }

    // @post @return an iterator to traverse set (elements not
    // in any particular order)
    method iterator->Iterator is public{data.iterator}

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

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