This is java

Randomized bag. A randomized bag is similar to a stack or queue, except that the item removed is chosen uniformly at random from items in the data structure. Create a generic data type RandomizedBag that implements the following API:

public class RandomizedBag implements Iterable { public RandomizedBag() // construct an empty randomized bag public boolean isEmpty() // is the bag empty? public int size() // return the number of items on the bag public void put(Item item) // add the item public Item get() // remove and return a random item public Item sample() // return a random item (but do not remove it) public Iterator iterator() // return an independent iterator over items in random order public static void main(String[] args) // unit testing } 

Throw a java.lang.NullPointerException if the client attempts to add a null item

Throw a java.util.NoSuchElementException if the client attempts to sample() or get() an item from an empty randomized bag

Throw a java.lang.UnsupportedOperationException if the client calls the remove() method in the iterator

Throw a java.util.NoSuchElementException if the client calls the next() method in the iterator and there are no more items to return.

Performance requirements.

Your randomized bag implementation should support each operation (besides creating an iterator) in constant amortized time and and use space linear in the number of items currently in the bag. That is, any sequence of M randomized bag operations (starting from an empty bag) must take at most cM steps in the worst case, for some constant c. (You may want to think back to your implementation of a doubling stack in Lab2).

Additionally, your iterator implementation must support next() and hasNext() in constant worst-case time and construction in linear time; you may use a linear amount of extra memory per iterator.

A client should be able to create two or more iterators to the same randomized bag concurrently, and they must be mutually independent (i.e. each iterator must maintain its own random order). How to implement this? I strongly suggest doing the work for this in the Iterator constructor, which is allowed to take time linear in the current size of the bag.