% File "set.tu".
% The class Set maintains a set of generic elements
% Written by Paul Gries, Fall 96.

unit
class Set

    export addElement, removeElement, isMember, isEmpty,
        size, clear, Subset, Copy, GetNextElement, GetRandomElement


    % Instance variables
    %-------------------

    % Implementation: linked list.
    type elementType : ^anyclass

    % Each node contains information about the current student,
    % where the next student is, and whether the current student
    % has been marked for deletion.
    type nodeType :
        record
            element : elementType
            link : ^nodeType
            deleted : boolean
        end record

    % The start of the linked list of elements.
    var front : ^nodeType := nil

    % The current item, for get_next
    var current : ^nodeType := nil

    % The size of the linked list of elements.
    var numElements : int := 0


    % isMember
    %----------------------------------------------------------------
    % Return true iff element is in the set.

    function isMember (element : elementType) : boolean
        var current : ^nodeType := front

        % Search the list for element.
        loop
            exit when current = nil or
                (not current -> deleted and element = current -> element)
            current := current -> link
        end loop

        % If found, return true.
        result current not= nil
    end isMember


    % addElement
    %----------------------------------------------------------------
    % Add element newElement to the set of elementTypes.

    proc addElement (newElement : elementType)
        if not isMember (newElement) then
            var newNode : ^nodeType
            new newNode
            assert newNode not= nil

            newNode -> element := newElement
            newNode -> deleted := false

            % Insert it at the front of the list.
            newNode -> link := front
            front := newNode

            numElements += 1
        end if
    end addElement


    % removeElement
    %----------------------------------------------------------------
    % Remove element elem from the set of elementTypes.

    proc removeElement (element : elementType)
        var previous : ^nodeType
        var current : ^nodeType := front

        % Find the element to be deleted.
        loop
            exit when current = nil or
                (not current -> deleted and element = current -> element)
            previous := current
            current := current -> link
        end loop

        % If found, mark it deleted.
        if current not= nil then
            current -> deleted := true
            numElements -= 1
        end if
    end removeElement


    % isEmpty
    %----------------------------------------------------------------
    % Return true iff the set is empty.

    function isEmpty : boolean
        result numElements = 0
    end isEmpty


    % size
    %----------------------------------------------------------------
    % Return the size of the set.

    function size : int
        result numElements
    end size


    % clear
    %----------------------------------------------------------------
    % Remove everything from the set.

    proc clear
        var current : ^nodeType := front

        loop
            current := front
            exit when current = nil
            front := front -> link
            free current
        end loop

        numElements := 0
    end clear


    % Subset
    %----------------------------------------------------------------
    % Return a Set of elements who have property f.

    function Subset (function f (e : elementType) : boolean) : ^Set
        var newset : ^Set
        new newset

        var current : ^nodeType := front

        % Cycle through the list, applying p.
        loop
            exit when current = nil
            if not current -> deleted then
                if f (current -> element) then
                    newset -> addElement (current -> element)
                end if
            end if
            current := current -> link
        end loop
    end Subset

    % Copy
    %-----------------------------------------------------------------
    % Make a new set using elements of this set
    function Copy : ^Set
        var copyset : ^Set
        new copyset

        var current : ^nodeType := front

        % Cycle through my list and copy nodes into teh new list
        loop
            exit when current = nil
            if not current -> deleted then
                copyset -> addElement (current -> element)
            end if
            current := current -> link
        end loop
    end Copy

    % Union
    %----------------------------------------------------------------
    % Return all elements of me plus those in otherSet.  Does not
    % check for duplicates (yet).

    function Union (otherSet : ^Set) : ^Set

        % Add all the elements from otherSet to newset.
        var newset : ^Set
        newset := otherSet -> Copy

        var current : ^nodeType := front

        % Cycle through my list, adding my elements to newset.
        loop
            exit when current = nil
            if not current -> deleted then
                newset -> addElement (current -> element)
            end if
            current := current -> link
        end loop

    end Union


    % Difference
    %----------------------------------------------------------------
    % Return a Set of those elements in me that are not in otherSet.

    function Difference (otherSet : ^Set) : ^Set
        var newset : ^Set

        var u : ^Set := Union (otherSet)
    end Difference

    % GetNextElement
    %----------------------------------------------------------------
    % this is used to loop through the elements of the set.
    % To start the process, pass nil in, then for each subsequent
    % element, pass a pointer to previous element.
    % Returns nil at the end, or for an empty list.
    %----------------------------------------------------------------

    function GetNextElement (prev : elementType) : elementType
        if prev = nil then
            current := front
        end if

        var next : elementType

        if current = nil then
            next := nil
        else
            next := current -> element
            current := current -> link
        end if

        result next
    end GetNextElement


    % GetRandomElement
    %----------------------------------------------------------------
    % Return a randomly-selected element.

    function GetRandomElement : elementType
        pre size > 0

        % The number of elements to count past the first.
        var which : int := Rand.Int (0, size - 1)

        var current : ^nodeType := front
        % Skip the deleted ones...
        loop
            exit when not current -> deleted
            current := current -> link
        end loop

        for i : 1 .. which
            current := current -> link
            % Skip the deleted ones...
            loop
                exit when not current -> deleted
                current := current -> link
            end loop
        end for

        result current -> element
    end GetRandomElement



end Set