import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;

/**
 * Naive array-based implementation of the Multiset interface.
 * Elements are literally stored multiple times in the array.
 *
 * @param <E> the type of elements in this multiset
 * @author CS 240 Instructors
 */
public class ArrayMultiset<E> implements Multiset<E> {

  private final int capacity;
  private  E[] elements;
  private int size;

  /**
   * Constructs a new ArrayMultiset with the specified capacity.
   *
   * @param capacity the maximum number of elements this multiset can hold
   */
  public ArrayMultiset(int capacity) {
    this.capacity = capacity;
    clear();
  }

  @SuppressWarnings("unchecked")
  @Override
  public void clear() {
    this.elements = (E[]) new Object[capacity];
    this.size = 0;
  }

  @Override
  public boolean add(E item) {
    if (size >= capacity) {
      return false; // No space left
    }
    elements[size] = item;
    size++;
    return true;
  }

  @Override
  public boolean add(E item, int occurrences) {
    if (occurrences < 0) {
      throw new IllegalArgumentException("Occurrences cannot be negative");
    }

    // Check if we have enough space for all occurrences
    if (size + occurrences > capacity) {
      return false; // Not enough space
    }

    for (int i = 0; i < occurrences; i++) {
      add(item);
    }

    return true;
  }



  @Override
  public boolean contains(Object item) {
    for (int i = 0; i < size; i++) {
      if (Objects.equals(elements[i], item)) { // Objects.equals handles nulls safely
        return true;
      }
    }
    return false;
  }

  @Override
  public int getCount(Object item) {
    int count = 0;
    for (int i = 0; i < size; i++) {
      if (Objects.equals(elements[i], item)) {
        count++;
      }
    }
    return count;
  }

  @Override
  public boolean equals(Object other) {
    if (this == other) {
      return true;
    }
    if (!(other instanceof Multiset)) {
      return false;
    }

    Multiset<?> otherMultiset = (Multiset<?>) other;

    if (this.size() != otherMultiset.size()) {
      return false;
    }

    // Check that this multiset has same counts for all elements
    // This is inefficient but works for the naive implementation
    for (int i = 0; i < size; i++) {
      if (this.getCount(elements[i]) != otherMultiset.getCount(elements[i])) {
        return false;
      }
    }

    return true;
  }



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

  /**
   * Helper method to remove an element at a specific index by shifting remaining elements left.
   *
   * @param index the index of the element to remove
   */
  private void removeAtIndex(int index) {
    for (int i = index; i < size - 1; i++) {
      elements[i] = elements[i + 1];
    }
    elements[size - 1] = null;
    size--;
  }

  @Override
  public boolean remove(Object item) {
    for (int i = 0; i < size; i++) {
      if (Objects.equals(elements[i], item)) {
        removeAtIndex(i);
        return true;
      }
    }
    return false; // Item not found
  }

  @Override
  public int size() {
    return size;
  }

  @Override
  public String toString() {
    if (size == 0) {
      return "[]";
    }

    StringBuilder sb = new StringBuilder();
    sb.append("[");

    boolean first = true;
    for (E element : this) {
      if (!first) {
        sb.append(", ");
      }
      sb.append(element);
      first = false;
    }

    sb.append("]");
    return sb.toString();
  }

  /**
   * Simple iterator that goes through all elements in order (including duplicates).
   */
  private class ArrayMultisetIterator implements Iterator<E> {
    private int currentIndex;
    private int lastReturnedIndex;
    private boolean canRemove;

    public ArrayMultisetIterator() {
      this.currentIndex = 0;
      this.lastReturnedIndex = -1;
      this.canRemove = false;
    }

    @Override
    public boolean hasNext() {
      return currentIndex < size;
    }

    @Override
    public E next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }

      E result = elements[currentIndex];
      lastReturnedIndex = currentIndex;
      currentIndex++;
      canRemove = true;
      return result;
    }

    @Override
    public void remove() {
      if (!canRemove) {
        throw new IllegalStateException("next() must be called before remove()");
      }

      removeAtIndex(lastReturnedIndex);

      // Adjust currentIndex since we removed an element before the current position
      currentIndex--;
      canRemove = false;
    }
  }
}