Assignment_9 03 LINKED_BAG.e

class
    LINKED_BAG [G]

feature -- Access

    occurrences (v: G): INTEGER
            -- Number of occurrences of `v'.
        local
            c: BAG_CELL [G]
        do
            from
                c := first
            until
                c = Void or else c.value = v
            loop
                c := c.next
            end
            if c /= Void then
                Result := c.count
            end
        ensure
            non_negative_result: Result >= 0
        end

feature -- Element change

    add (v: G; n: INTEGER)
            -- Add `n' copies of `v'.
        require
            n_positive: n > 0
        local
            next_cell, specific: BAG_CELL [G]
        do
            if
                occurrences (v) <= 0
            then
                if
                    first = void
                then
                    create first.make (v)
                    first.set_count (n)
                    last := first
                else
                    create next_cell.make (v)
                    next_cell.set_count (n)
                    last.set_next (next_cell)
                    last := last.next
                end
            else
                from
                    specific := first
                until
                    specific.value = v
                loop
                    specific := specific.next
                end
                specific.set_count (specific.count + n)
            end
        ensure
            n_more: occurrences (v) = old occurrences (v) + n
        end

    remove (v: G; n: INTEGER)
            -- Remove as many copies of `v' as possible, up to `n'.
        require
            n_positive: n > 0
        local
            specific: BAG_CELL [G]
        do
            from
                specific := first
            until
                specific.value = v
            loop
                specific := specific.next
            end
            if
                (specific.count - n) > 0
            then
                specific.set_count (specific.count - n)
            else
                from
                    specific := first
                until
                    specific.next.value = v
                loop
                    specific := specific.next
                end
                specific.set_next (specific.next.next)
            end
        ensure
            n_less: occurrences (v) = (old occurrences (v) - n).max (0)
        end

    subtract (other: LINKED_BAG [G])
            -- Remove all elements of `other'.
        require
            other_exists: other /= Void
        local
            iteration, specific: BAG_CELL [G]
        do
            from
                iteration := other.first
            until
                iteration = void
            loop
                if
                    iteration /= void and then occurrences (iteration.value) > 0
                then
                    remove (iteration.value, iteration.count)
                end
                iteration := iteration.next
            end
        end

feature {LINKED_BAG} -- Implementation

    first: BAG_CELL [G]
            -- First cell.

    last: BAG_CELL [G]
            -- Last cell.

end