Set + Queue + a get method backed by a Map The other day I stumbled upon this question on Stack Overflow about the lack of a get method on the Set and loved the suggestion of using a Map&lt;E,E&gt; to back the Set. I decided to try this out. Since this is quite a generic object that could serve a lot of purposes, I would like to know if there is something weird with my implementation.

NB: I am using Java 7.

Here is the interface:

public interface QueuedSetWithGet&lt;E&gt; extends Set&lt;E&gt;, Queue&lt;E&gt; {
    public E get(E e);
}


And here is the implementation I wrote:

public class QueuedSetWithGetImpl&lt;E&gt; implements QueuedSetWithGet&lt;E&gt; {

    LinkedHashMap&lt;E, E&gt; map = new LinkedHashMap&lt;E, E&gt;();

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

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public boolean contains(Object paramObject) {
        return map.containsKey(paramObject);
    }

    @Override
    public Iterator&lt;E&gt; iterator() {
        return map.keySet().iterator();
    }

    @Override
    public Object[] toArray() {
        return map.keySet().toArray();
    }

    @Override
    public &lt;T&gt; T[] toArray(T[] paramArrayOfT) {
        return map.keySet().toArray(paramArrayOfT);
    }

    @Override
    public boolean add(E paramE) {
        boolean notAlreadyPresent = !map.containsKey(paramE);
        if (notAlreadyPresent) {
            map.put(paramE, paramE);
        }
        return notAlreadyPresent;
    }

    @Override
    public boolean remove(Object paramObject) {
        return map.remove(paramObject) != null;
    }

    @Override
    public boolean containsAll(Collection&lt;?&gt; paramCollection) {
        return map.keySet().containsAll(paramCollection);
    }

    @Override
    public boolean addAll(Collection&lt;? extends E&gt; paramCollection) {
        boolean mapChanged = false;
        for (E e : paramCollection) {
            mapChanged |= this.add(e);
        }
        return mapChanged;
    }

    @Override
    public boolean retainAll(Collection&lt;?&gt; paramCollection) {
        boolean mapChanged = false;
        for (Object e : paramCollection) {
            if (!this.contains(e)) {
                mapChanged = true;
                this.remove(e);
            }
        }
        return mapChanged;
    }

    @Override
    public boolean removeAll(Collection&lt;?&gt; paramCollection) {
        boolean mapChanged = false;
        for (Object e : paramCollection) {
            mapChanged |= this.remove(e);
        }
        return mapChanged;
    }

    @Override
    public void clear() {
        map.clear();
    }

    @Override
    public boolean offer(E paramE) {
        return this.add(paramE);
    }

    @Override
    public E remove() {
        E head = this.element();
        this.remove(head);
        return head;
    }

    @Override
    public E poll() {
        return this.isEmpty() ? null : this.remove();
    }

    @Override
    public E element() {
        E e = this.peek();
        if (e == null) {
            throw new NoSuchElementException("queue is empty");
        } else {
            return e;
        }
    }

    @Override
    public E peek() {
        return this.isEmpty() ? null : map.keySet().iterator().next();
    }

    @Override
    public E get(E e) {
        return map.get(e);
    }
}
Bug in retainAll

The method retainAll does not respect its contract. It is supposed to remove from this set all the elements that are not contained in the given set. However, the following code:

Set&lt;String&gt; set = new QueuedSetWithGetImpl&lt;&gt;();
set.add("foo");
set.add("bar");
set.retainAll(Arrays.asList("foo"));
System.out.println(set.size()); // prints 2!


does not remove the "bar" element from the set (the size is still 2).

The issue with the current code is that it doesn't loop over the elements of the set to find the ones not contained in the given collection. To implement it correctly, you can use an Iterator and call remove():

@Override
public boolean retainAll(Collection&lt;?&gt; paramCollection) {
    boolean mapChanged = false;
    Iterator&lt;E&gt; it = iterator();
    while (it.hasNext()) {
        if (!paramCollection.contains(it.next())) {
            mapChanged = true;
            it.remove();
        }
    }
    return mapChanged;
}


Access control


LinkedHashMap&lt;E, E&gt; map = new LinkedHashMap&lt;E, E&gt;();



This map needs to be private. It is the backing map of your implementation and is not intended to be used by other classes.

Possible simplification


boolean notAlreadyPresent = !map.containsKey(paramE);
if (notAlreadyPresent) {
    map.put(paramE, paramE);
}
return notAlreadyPresent;



This can be simplified a bit by using the result of put, which is either the previous value or null if there was no mapping. As such, you can have:

return map.put(paramE, paramE) == null;


Note that will replace the old value with the given new value, but it won't break the contract of the Set which defines equality in terms of equals and not ==. To not replace, you could use putIfAbsent on Java 8, but since you're using Java 7, you could keep what you have.