import java.util.*;

public class MyHashSet<E> implements Collection<E> {
  // Definicja domyślnej pojemności tablicy z haszowaniem (musi być potęgą liczby 2)
  private final static int DEFAULT_INITIAL_CAPACITY = 4;
  
  // Maksymalna pojemność tablicy z haszowaniem (1 << 30 oznacza to samo co 2^30)
  private final static int MAXIMUM_CAPACITY = 1 << 30; 
  
  // Aktualna pojemność tablicy z haszowaniem (wartości to potęgi liczby 2)
  private int capacity;
  
  // Domyślny maksymalny współczynnik wypełnienia
  private final static float DEFAULT_MAX_LOAD_FACTOR = 0.75f; 

  // Wartość progowa współczynnika wypełnienia tablicy z haszowaniem
  private float loadFactorThreshold; 
  
  // Liczba elementów w zbiorze
  private int size = 0; 
  
  // Tablica z haszowaniem jest tu zwykłą tablicą, której elementy to listy powiązane
  private LinkedList<E>[] table;

  /** Tworzy zbiór z domyślną pojemnością i domyślnym współczynnikiem wypełnienia */
  public MyHashSet() {  
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);    
  }
  
  /** Tworzy zbiór o podanej początkowej pojemności i z 
    * domyślnym współczynnikiem wypełnienia */
  public MyHashSet(int initialCapacity) { 
    this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);    
  }
  
  /** Tworzy zbiór o podanej pojemności początkowej 
    * i o określonym współczynniku wypełnienia */
  public MyHashSet(int initialCapacity, float loadFactorThreshold) { 
    if (initialCapacity > MAXIMUM_CAPACITY)
      this.capacity = MAXIMUM_CAPACITY;
    else
      this.capacity = trimToPowerOf2(initialCapacity);
    
    this.loadFactorThreshold = loadFactorThreshold;    
    table = new LinkedList[capacity];
  }
  
  @Override /** Usuwa wszystkie elementy ze zbioru */ 
  public void clear() {
    size = 0;
    removeElements();
  }

  @Override /** Zwraca true, jeśli element znajduje się w zbiorze */
  public boolean contains(Object e) {
    int bucketIndex = hash(e.hashCode());
    if (table[bucketIndex] != null) {
      LinkedList<E> bucket = table[bucketIndex]; 
      return bucket.contains(e);
    }
    
    return false;
  }
  
  @Override /** Dodaje element do zbioru */
  public boolean add(E e) {
    if (contains(e)) // Powtarzające się elementy nie są zapisywane
      return false;
    
    if (size + 1 > capacity * loadFactorThreshold) {
      if (capacity == MAXIMUM_CAPACITY)
        throw new RuntimeException("Przekroczono maksymalną pojemność");
    
      rehash();
    }
    
    int bucketIndex = hash(e.hashCode());
    
    // Tworzenie listy powiązanej dla kubełka, jeśli taka lista jeszcze nie istnieje 
    if (table[bucketIndex] == null) {
      table[bucketIndex] = new LinkedList<E>();
    }

    // Dodawanie e do hashTable[index]
    table[bucketIndex].add(e);

    size++; // Zwiększanie wielkości
    
    return true;
  }

  @Override /** Usuwanie elementu ze zbioru */
  public boolean remove(Object e) {
    if (!contains(e))
      return false;
    
    int bucketIndex = hash(e.hashCode());
    
    // Tworzenie listy powiązanej dla kubełka, jeśli taka lista jeszcze nie istnieje
    if (table[bucketIndex] != null) {
      LinkedList<E> bucket = table[bucketIndex]; 
      bucket.remove(e);
    }

    size--; // Zmniejszanie wielkości
    
    return true;
  }

  @Override /** Zwraca true, jeśli zbiór nie zawiera żadnych elementów */
  public boolean isEmpty() {
    return size == 0;
  }

  @Override /** Zwraca liczbę elementów w zbiorze */
  public int size() {
    return size;
  }

  @Override /** Zwraca iterator do pobierania elementów zbioru */
  public java.util.Iterator<E> iterator() {
    return new MyHashSetIterator(this);
  }
  
  /** Klasa wewnętrzna na potrzeby iteratora */
  private class MyHashSetIterator implements java.util.Iterator<E> {
    // Przechowuje elementy na liście
    private java.util.ArrayList<E> list;
    private int current = 0; // Wskazuje bieżący element listy
    private MyHashSet<E> set;
    
    /** Tworzenie listy na podstawie zbioru */
    public MyHashSetIterator(MyHashSet<E> set) {
      this.set = set;
      list = setToList();
    }

    @Override /** Czy dostępny jest następny element? */
    public boolean hasNext() {
      return current < list.size();
    }

    @Override /** Pobieranie bieżącego elementu i przenoszenie kursora do następnego */
    public E next() {
      return list.get(current++);
    }

    @Override /** Usuwa bieżący element zwrócony przez ostatnie wywołanie next() */
    public void remove() {
      // Ćwiczenie dla czytelników.
      // Trzeba usunąć element ze 
      // zbioru i z listy
    }
  }  
  
  /** Funkcja haszująca */
  private int hash(int hashCode) {
    return hashCode & (capacity - 1);
  }

  /** Gwarantuje równomierny rozkład elementów */
  private static int supplementalHash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
  }

  /** Zwraca potęgę liczby 2 na podstawie wartości initialCapacity */
  private int trimToPowerOf2(int initialCapacity) {
    int capacity = 1;
    while (capacity < initialCapacity) {
      capacity <<= 1; // Daje ten sam wynik co *= 2 (operacja <= jest wydajniejsza)
    }
    
    return capacity;
  }
  
  /** Usuwa wszystkie elementy z każdego kubełka */
  private void removeElements() {
    for (int i = 0; i < capacity; i++) {
      if (table[i] != null) {
        table[i].clear();
      }
    }
  }
  
  /** Ponowne haszowanie zbioru */
  private void rehash() {
    java.util.ArrayList<E> list = setToList(); // Kopiowanie elementów na listę
    capacity <<= 1; // Daje ten sam wynik co *= 2 (operacja <= jest wydajniejsza)
    table = new LinkedList[capacity]; // Tworzenie nowej tablicy z haszowaniem
    size = 0; 
    
    for (E element: list) {
      add(element); // Dodawanie elementów z dawnej tablicy do nowej
    }
  }

  /** Kopiowanie elementów ze zbioru z haszowaniem na listę ArrayList */
  private java.util.ArrayList<E> setToList() {
    java.util.ArrayList<E> list = new java.util.ArrayList<>();
    
    for (int i = 0; i < capacity; i++) {
      if (table[i] != null) {
        for (E e: table[i]) {
          list.add(e);
        }
      }
    }  
    
    return list;
  }

  @Override /** Zwraca tekstową reprezentację zbioru */
  public String toString() {
    java.util.ArrayList<E> list = setToList();
    StringBuilder builder = new StringBuilder("[");
    
    // Dodaje elementy (oprócz ostatniego) do obiektu typu StringBuilder
    for (int i = 0; i < list.size() - 1; i++) {
      builder.append(list.get(i) + ", ");
    }
    
    // Dodawanie ostatniego elementu listy do obiektu typu StringBuilder
    if (list.size() == 0)
      builder.append("]");
    else
      builder.append(list.get(list.size() - 1) + "]");
    
    return builder.toString();
  }

  @Override
  public boolean addAll(Collection<? extends E> arg0) {
    // Ćwiczenie dla czytelników
    return false;
  }

  @Override
  public boolean containsAll(Collection<?> arg0) {
    // Ćwiczenie dla czytelników
    return false;
  }

  @Override
  public boolean removeAll(Collection<?> arg0) {
    // Ćwiczenie dla czytelników
    return false;
  }

  @Override
  public boolean retainAll(Collection<?> arg0) {
    // Ćwiczenie dla czytelników
    return false;
  }

  @Override
  public Object[] toArray() {
    // Ćwiczenie dla czytelników
    return null;
  }

  @Override
  public <T> T[] toArray(T[] arg0) {
    // Ćwiczenie dla czytelników
    return null;
  }
}