import java.util.*;

public class LimitedSetClass<T> implements LimitedSet<T> {
    /** Maximum set size. */
    private final int maxSetSize = 4;
    /** Set's elements with 'contains' methods usage count */
    private final Set<T> elements = new HashSet<T>();

    private final LinkedList<T> objects = new LinkedList<T>();
    private final LinkedList<Integer> usages = new LinkedList<Integer>();

    @Override
    public void add(T t) {
        if (!elements.contains(t)) {
            if (elements.size() == maxSetSize) {
                elements.remove(objects.getFirst());
                objects.removeFirst();
                usages.removeFirst();
            }

            elements.add(t);
            objects.addFirst(t);
            usages.addFirst(0);
        }
    }

    @Override
    public boolean remove(T t) {
        boolean isRemoved = false;

        if (elements.contains(t)) {
            int index = objects.indexOf(t);
            usages.remove(index);
            isRemoved = objects.remove(t) && elements.remove(t);
        }

        return isRemoved;
    }

    @Override
    public boolean contains(T t) {
        boolean contains = false;

        if (elements.contains(t)) {
            contains = true;
            swapListsValues(t);
        }

        return contains;
    }

    private void swapListsValues(T t) {
        int index = objects.indexOf(t);
        int usageValue = usages.get(index) + 1;
        int size = elements.size();

        for (int i = index; i < size; i++) {
            if (i == size - 1) {
                Collections.swap(objects, index, i);
                Collections.swap(usages, index, i);
                usages.set(i, usageValue);
            }

            if (usages.get(i) == usageValue) {
                Collections.swap(objects, index, i - 1);
                Collections.swap(usages, index, i - 1);
                usages.set(i - 1, usageValue);
            }
        }
    }
}