import java.util.LinkedList;

public class MyHashMap<K, V> implements MyMap<K, V> {
  // Określa domyślną wielkość tablicy z haszowaniem (musi być potęgą liczby 2)
  private final static int DEFAULT_INITIAL_CAPACITY = 4;
  
  // Określa maksymalną wielkość tablicy z haszowaniem. 1 << 30 jest równe 2^30
  private final static int MAXIMUM_CAPACITY = 1 << 30; 
  
  // Aktualna pojemność tablicy z haszowaniem (potęga liczby 2)
  private int capacity;
  
  // Domyślny 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 wpisów w odwzorowaniu
  private int size = 0; 
  
  // Tablica z haszowaniem jest tu tablicą, w której każda komórka to lista powiązana
  LinkedList<MyMap.Entry<K,V>>[] table;

  /** Tworzy odwzorowanie z domyślną pojemnością i domyślnym współczynnikiem wypełnienia */
  public MyHashMap() {  
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);    
  }
  
  /** Tworzy odwzorowanie z podaną pojemnością początkową i 
    * domyślnym współczynnikiem wypełnienia */
  public MyHashMap(int initialCapacity) { 
    this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);    
  }
  
  /** Tworzy odwzorowanie z początkową podaną pojemnością
    * i określonym współczynnikiem wypełnienia */
  public MyHashMap(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 wpisy z odwzorowania */ 
  public void clear() {
    size = 0;
    removeEntries();
  }

  @Override /** Zwraca true, jeśli dany klucz znajduje się w odwzorowaniu */
  public boolean containsKey(K key) {    
    if (get(key) != null)
      return true;
    else
      return false;
  }
  
  @Override /** Zwraca true, jeśli odwzorowanie zawiera daną wartość */
  public boolean containsValue(V value) {
    for (int i = 0; i < capacity; i++) {
      if (table[i] != null) {
        LinkedList<Entry<K, V>> bucket = table[i]; 
        for (Entry<K, V> entry: bucket)
          if (entry.getValue().equals(value)) 
            return true;
      }
    }
    
    return false;
  }
  
  @Override /** Zwraca zbiór wpisów z odwzorowania */
  public java.util.Set<MyMap.Entry<K,V>> entrySet() {
    java.util.Set<MyMap.Entry<K, V>> set = 
      new java.util.HashSet<>();
    
    for (int i = 0; i < capacity; i++) {
      if (table[i] != null) {
        LinkedList<Entry<K, V>> bucket = table[i]; 
        for (Entry<K, V> entry: bucket)
          set.add(entry); 
      }
    }
    
    return set;
  }

  @Override /** Zwraca wartość powiązaną z podanym kluczem */
  public V get(K key) {
    int bucketIndex = hash(key.hashCode());
    if (table[bucketIndex] != null) {
      LinkedList<Entry<K, V>> bucket = table[bucketIndex]; 
      for (Entry<K, V> entry: bucket)
        if (entry.getKey().equals(key)) 
          return entry.getValue();
    }
    
    return null;
  }
  
  @Override /** Zwraca true, jeśli odwzorowanie jest puste */
  public boolean isEmpty() {
    return size == 0;
  }  
  
  @Override /** Zwraca zbiór zawierający klucze z danego odwzorowania */
  public java.util.Set<K> keySet() {
    java.util.Set<K> set = new java.util.HashSet<>();
    
    for (int i = 0; i < capacity; i++) {
      if (table[i] != null) {
        LinkedList<Entry<K, V>> bucket = table[i]; 
        for (Entry<K, V> entry: bucket)
          set.add(entry.getKey()); 
      }
    }
    
    return set;
  }
      
  @Override /** Dodaje do odwzorowania wpis (klucz, wartość) */
  public V put(K key, V value) {
    if (get(key) != null) { // Dany klucz już znajduje się w odwzorowaniu
      int bucketIndex = hash(key.hashCode());
      LinkedList<Entry<K, V>> bucket = table[bucketIndex]; 
      for (Entry<K, V> entry: bucket)
        if (entry.getKey().equals(key)) {
          V oldValue = entry.getValue();
          // Zastępowanie poprzedniej wartości nową
          entry.value = value; 
          // Zwraca dawną wartość dla danego klucza
          return oldValue;
        }
    }
  
    // Sprawdzanie współczynnika wypełnienia
    if (size >= capacity * loadFactorThreshold) {
      if (capacity == MAXIMUM_CAPACITY)
        throw newRuntimeException("Przekroczenie maksymalnej pojemności");
      
      rehash();
    }
    
    int bucketIndex = hash(key.hashCode());
    
    // Tworzenie listy powiązanej dla kubełka (jeśli jeszcze nie istnieje)
    if (table[bucketIndex] == null) {
      table[bucketIndex] = new LinkedList<Entry<K, V>>();
    }

    // Dodawanie nowego wpisu (key, value) do hashTable[index]
    table[bucketIndex].add(new MyMap.Entry<K, V>(key, value));

    size++; // Zwiększanie wielkości
    
    return value;  
  } 
 
  @Override /** Usuwa wpisy z podanym kluczem */
  public void remove(K key) {
    int bucketIndex = hash(key.hashCode());
    
    // Usuwa z kubełka pierwszy wpis pasujący do klucza
    if (table[bucketIndex] != null) {
      LinkedList<Entry<K, V>> bucket = table[bucketIndex]; 
      for (Entry<K, V> entry: bucket)
        if (entry.getKey().equals(key)) {
          bucket.remove(entry);
          size--; // Zmniejszanie wielkości
          break; // Usuwanie tylko jednego wpisu pasującego do klucza
        }
    }
  }
  
  @Override /** Zwraca liczbę wpisów w odwzorowaniu */
  public int size() {
    return size;
  }
  
  @Override /** Zwraca zbiór zawierający wartości z odwzorowania */
  public java.util.Set<V> values() {
    java.util.Set<V> set = new java.util.HashSet<>();
    
    for (int i = 0; i < capacity; i++) {
      if (table[i] != null) {
        LinkedList<Entry<K, V>> bucket = table[i]; 
        for (Entry<K, V> entry: bucket)
          set.add(entry.getValue()); 
      }
    }
    
    return set;
  }
  
  /** Funkcja haszująca */
  private int hash(int hashCode) {
    return supplementalHash(hashCode) & (capacity - 1);
  }
  
  /** Zapewnia równomierny rozkład skrótó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 initialCapacity */
  private int trimToPowerOf2(int initialCapacity) {
    int capacity = 1;
    while (capacity < initialCapacity) {
      capacity <<= 1; // Ten sam wynik co dla capacity *= 2 (<= jest wydajniejsze)
    }
    
    return capacity;
  }
  
  /** Usuwa wszystkie wpisy z każdego kubełka */
  private void removeEntries() {
    for (int i = 0; i < capacity; i++) {
      if (table[i] != null) {
        table[i].clear();
      }
    }
  }
  
  /** Ponowne haszowanie odwzorowania */
  private void rehash() {
    java.util.Set<Entry<K, V>> set = entrySet(); // Pobieranie wpisów
    capacity <<= 1; // Ten sam wynik co *= 2 (<= jest wydajniejsze)
    table = new LinkedList[capacity]; // Tworzenie nowej tablicy z haszowaniem
    size = 0; // Zerowanie pola size
    
    for (Entry<K, V> entry: set) {
      put(entry.getKey(), entry.getValue()); // Zapisywanie w nowej tablicy
    }
  }

  @Override
  public String toString() {
    StringBuilder builder = new StringBuilder("[");
    
    for (int i = 0; i < capacity; i++) {
      if (table[i] != null && table[i].size() > 0) 
        for (Entry<K, V> entry: table[i])
          builder.append(entry);
    }
    
    builder.append("]");
    return builder.toString();
  }
}