import node
import singly_linked_list

type Iterator = {
     reset->Void
     hasNext->Boolean
     next->T
     get->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)->Dynamic
    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 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}

// Constructs empty set
method new->Set is public{SetList.new}

class SetList.new{

    // Underlying structure to hold elements of set
    var data:Collection is readable := singly_linked_list.new

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

    // @post @return true iff no elements in set
    method isEmpty->Boolean is public{data.isEmpty}

    // @pre e is not "missing"
    // @post adds e to set
    // @param e the new value to be added
    method add(e:Dynamic)->Void is public{
        if(!data.contains(e)) then{data.addLast(e)}
    }

    // @pre e is not "missing"
    // @post e is removed from set
    // @param e the element to be removed
    // @return value actually removed
    method removeValue(e:Dynamic)->Void is public{data.removeValue(e)}

    // @pre e is not "missing"
    // @post @return true iff e is in set
    // @param e the element sought
    method contains(e:Dynamic)->Boolean is public{data.contains(e)}

    // @post @return true iff this set is 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}

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

    // @post adds all elements of other to this
    // @param other 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)}
    }

    // @post removes items of this that are not in other
    // @param other the set to be intersected with this
    method retainAll(other:Set)->Void is public{
        var temp:Set := SetList.new
        var myElements:Iterator := data.iterator
        while{myElements.hasNext} do{
            var v:Dynamic := myElements.next
            if(other.contains(v)) then{temp.add(v)}
        }
        clear
        addAll(temp)}

    // @post removes members of other from this
    // @param other the set whose values are to be 
    // eliminated from this
    method removeAll(other:Set)->Void is public{
        var yourElements:Iterator := other.iterator
        while{yourElements.hasNext} do{
            removeValue(yourElements.next)}
    }

    // @post @return iterator to traverse elements
    // of set in no particular order
    method iterator->Iterator is public{data.iterator}

    // @post @return number of elements in set
    method size->Number is public{data.size}
    
    // @post @return string representation of set
    method asString->String is public{""}
}