import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class SimpleHashSet<T> {
    private static final int INITIAL_CAPACITY = 16;
    private static final int MIN_CAPACITY = 16;
    private static final double LOAD_FACTOR = 0.75;
    private static final double SHRINK_THRESHOLD = 0.25;

    private List<T>[] buckets;
    private int size;

    public MyHashSet() {
        this.size = 0;
        buckets = new ArrayList[INITIAL_CAPACITY];
        initBuckets(buckets);
    }

    private void initBuckets(List<T>[] bucketArray) {
        for (int i = 0; i < bucketArray.length; i++) {
            bucketArray[i] = new ArrayList<>();
        }
    }

    private int getBucketIndex(T value, int capacity) {
        return (value.hashCode() & 0x7FFFFFFF) % capacity;
    }

    private void resize(int newCapacity) {
        List<T>[] newBuckets = new ArrayList[newCapacity];
        initBuckets(newBuckets);

        for (List<T> bucket : this.buckets) {
            for (T value : bucket) {
                int newIndex = getBucketIndex(value, newCapacity);
                newBuckets[newIndex].add(value);
            }
        }
        this.buckets = newBuckets;
    }

    public boolean add(T el) {
        if (contains(el)) {
            return false;
        }
        if (this.size > this.buckets.length * LOAD_FACTOR) {
            resize(this.buckets.length * 4);
        }
        int bucketIndex = getBucketIndex(el, this.buckets.length);
        this.buckets[bucketIndex].add(el);
        this.size += 1;
        return true;
    }

    public boolean remove(T el) {
        int index = getBucketIndex(el, buckets.length);
        if (this.buckets[index].remove(el)) {
            this.size -= 1;
            if (this.buckets.length > MIN_CAPACITY && size <= buckets.length * SHRINK_THRESHOLD) {
                resize(this.buckets.length / 2);
            }
            return true;
        }
        return false;
    }
    public boolean contains(T el) {
        int index = getBucketIndex(el, this.buckets.length);
        return buckets[index].contains(el);
    }

    public int size() {
        return size;
    }

    public void internalPrint() {
        //
        for (int i = 0; i < buckets.length; i++) {
            String s = i + ": ";
            for (T value : buckets[i]) {
                s += value + " ";
            }
            System.out.println(s);
        }
    }
}