## Last version: 8 July 2019

from contiguous import *      

INFINITY = 100
## A class implementing Multiset using a contiguous implementation

class Multiset:
    """
    Fields: _data is a one-dimensional array of the items
            _first is the index of the next place to fill 
    """
    
    ## Multiset() produces a newly constructed empty multiset.
    ## __init__: -> Multiset
    def __init__(self):
        self._data = Contiguous(INFINITY)
        self._first = 0

    ## repr(self) produces a string of the data stored.
    ## __repr__: Multiset -> Str
    def __repr__(self):
        all_values = str(self._data)
        length = len(all_values)
        delete_pos = []
        for pos in range(length):
            if all_values[pos:pos+4] == "None":
                delete_pos = delete_pos + [pos, pos+1, pos+2, pos+3]
                if pos-1 >= 0 and all_values[pos-1] == ",":
                    delete_pos.append(pos-1)
        new_string = ""
        for pos in range(length):
            if pos not in delete_pos:
                new_string = new_string + all_values[pos]
        return new_string

    ## value in self produces True if value is an item in self.
    ## __contains__: Multiset Any -> Bool
    def __contains__(self, value):
        for index in range(self._data.size()):
            if self._data.access(index) == value:
                return True
        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):
        self._data.store(self._first, value)
        self._first = self._first + 1
    
    ## 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):
        position = -1
        current = 0
        while position == -1 and current < self._data.size():
            if self._data.access(current) == value:
                position = current
                to_replace = self._data.access(self._first - 1)
                self._data.store(position, to_replace)
                self._data.store(self._first - 1, None)
                self._first = self._first - 1
            else:
                current = current + 1