import java.util.Iterator;


/**
 * A Multiset implementation that uses a fixed-capacity array of counters. Each counter stores
 * an element and the number of its occurrences, which is more space-efficient than storing
 * duplicate elements individually (as done in ArrayMultiset).
 *
 * @author
 * @version
 * @param <E> the type of elements in this multiset
 */
public class CounterMultiset<E> implements Multiset<E> {

  private final int capacity;
  private Counter[] counters;
  private int size; // Total number of elements (including duplicates)
  private int uniqueElements; // Number of unique elements stored

  /**
   * Inner class to represent an element and its count.
   */
  private class Counter {
    private E element;
    private int count;

    public Counter(E element, int count) {
      this.element = element;
      this.count = count;
    }

    /**
     * Get the element stored in this entry.
     *
     * @return the element
     */
    public E getElement() {
      return element;
    }

    /**
     * Get the count of occurrences for this element.
     *
     * @return the count
     */
    public int getCount() {
      return count;
    }

    /**
     * Update the count of occurrences for this element.
     *
     * @param count the new count
     */
    public void setCount(int count) {
      this.count = count;
    }
  }

  /**
   * Create an empty CounterMultiset with the specified capacity.
   *
   * @param capacity the maximum number of unique elements this multiset can hold
   */
  @SuppressWarnings("unchecked")
  public CounterMultiset(int capacity) {
    this.capacity = capacity;
    this.counters = (Counter[]) new CounterMultiset.Counter[capacity];
    size = 0;
    uniqueElements = 0;
  }

  @Override
  @SuppressWarnings("unchecked")
  public void clear() {
    this.counters = (Counter[]) new CounterMultiset.Counter[capacity];
    size = 0;
    uniqueElements = 0;
  }

  /**
   * Return the index of the counter Entry for the indicated item, or -1 if there is no such item.
   * This helper method is useful for several other methods in this class. Returning the index is
   * more useful than returning the Entry itself because it supports operations like removal and
   * modification.
   *
   * @param item the item to search for
   * @return the index of the item in the counters array, or -1 if not found
   */
  private int counterIndex(Object item) {

    // Suggestion: Use Objects.equals to avoid trouble with null comparisons.

    // UNFINISHED

    return -1;
  }


  @Override
  public boolean add(E item) {

    // UNFINISHED

    return false;
  }

  @Override
  public boolean add(E item, int occurrences) {

    // UNFINISHED

    return false;
  }


  @Override
  public boolean contains(Object item) {

    // UNFINISHED

    return false;
  }

  @Override
  public int getCount(Object item) {

    // UNFINISHED

    return -1;
  }

  @Override
  public boolean equals(Object other) {

    // Suggestion: Feel free to use the ArrayMultiset.equals method as a model, but don't copy it
    // directly. The result would be needlessly inefficient.  (Make sure you understand why.)

    // UNFINISHED

    return false;
  }

  @Override
  public Iterator<E> iterator() {
    return new CountIterator();
  }

  /**
   * Iterator implementation that returns each element as many times as its count indicates.
   */
  private class CountIterator implements Iterator<E> {

    // Implementation advice:
    //
    // This is tricky!
    //
    // I suggest tracking two peices of state information: 1) The index of the current Entry 2) A
    // counter representing the number of times we still need to return the corresponding item. When
    // next is called, the count is decremented, or if the counter has reached zero, the index is
    // moved forward to the next Entry and the counter is reset appropriately.
    //
    // Remove will also be a bit complicated: if the count for an Entry is positive, remove should
    // decrement the counter. If the count is zero, the Entry should
    // be removed from the array.
    //
    // You will probably want a proper constructor for this class to set up the counter for the
    // initial entry (if it exists.)



    @Override
    public boolean hasNext() {
      // UNFINISHED Auto-generated method stub
      return false;
    }


    @Override
    public E next() {
      // UNFINISHED Auto-generated method stub
      throw new UnsupportedOperationException("Unimplemented method 'next'");
    }

    @Override
    public void remove() {
      // UNFINISHED method stub
      throw new UnsupportedOperationException("Unimplemented method 'remove'");
    }


  }

  @Override
  public boolean remove(Object item) {

    // UNFINISHED

    return false;
  }


  @Override
  public int size() {

    // UNFINISHED

    return -1;
  }

  @Override
  public String toString() {

    // UNFINISHED

    return "";
  }

}