## Last version: 25 September 2019

from linked import *      

## A class implementing Multiset using a singly linked list implementation

class Multiset:
    """
    Fields: _first points to the first node (if any) in a singly-linked list
    """
    
    ## Multiset() produces a newly constructed empty multiset.
    ## __init__: -> Multiset
    def __init__(self):
        self._first = None

    ## repr(self) produces a string of the data stored.
    ## __repr__: Multiset -> Str
    def __repr__(self):
        current = self._first
        to_return = "("
        while current != None:
            to_print = current.access()
            current = current.next()
            to_return = to_return + str(to_print) + ","
        return to_return[:-1] + ")"

    ## value in self produces True if value is an item in self.
    ## __contains__: Multiset Any -> Bool
    def __contains__(self, value):
         current = self._first
         while current != None:
             if value == current.access():
                 return True
             current = current.next()
         return False

    ## self.add(value) adds value to self.
    ## Effects: Mutates self by adding value to self.
    ## add: Multiset Any -> None
    def add(self, value):
        new_node = Single(value, self._first)
        self._first = new_node
    
    ## self.delete(value) removes an item with value from self.
    ## Effects: Mutates self by removing an item with value from self.
    ## delete: Multiset Any -> None
    ## Requires: self contains an item with value value
    def delete(self, value):
        if self._first != None and self._first.access() == value:
            self._first = self._first.next()
        elif self._first != None:
            previous = self._first
            current = self._first.next()
            found = False
            while current != None and found == False:
                if current.access() == value:
                    found = True
                else:
                    current = current.next()
                    previous = previous.next()
            previous.link(current.next())