2
\$\begingroup\$

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<E,E> 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<E> extends Set<E>, Queue<E> {
    public E get(E e);
}

And here is the implementation I wrote:

public class QueuedSetWithGetImpl<E> implements QueuedSetWithGet<E> {

    LinkedHashMap<E, E> map = new LinkedHashMap<E, E>();

    @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<E> iterator() {
        return map.keySet().iterator();
    }

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

    @Override
    public <T> 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<?> paramCollection) {
        return map.keySet().containsAll(paramCollection);
    }

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

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

    @Override
    public boolean removeAll(Collection<?> 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);
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ notAlreadyPresent feels weird, and isn't descriptive anymore once you've called map.put. How about initiallyAbsent? \$\endgroup\$ – Aaron Sep 8 '16 at 13:16
3
\$\begingroup\$

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<String> set = new QueuedSetWithGetImpl<>();
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<?> paramCollection) {
    boolean mapChanged = false;
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        if (!paramCollection.contains(it.next())) {
            mapChanged = true;
            it.remove();
        }
    }
    return mapChanged;
}

Access control

LinkedHashMap<E, E> map = new LinkedHashMap<E, E>();

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your review. Your simplification is counter-intuitive. According to the javadoc, If the map previously contained a mapping for the key, the old value is replaced. In my understanding it means that if I build two objects a and b with a.equals(b) and a!=b and if I add both of them to the Set, using your simplification erases the first inserted object with the reference of the second object, which breaks the contract of the set, or am I misunderstanding something? \$\endgroup\$ – Aldian Sep 9 '16 at 9:07
  • \$\begingroup\$ @Aldian It doesn't break the contract of the set since equality in a Set is defined in terms of equals, not ==. In the Set javadoc, there is: More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2). But yes, you're right that it replaces the previous value, however I don't think it shouldn't really matter since a and b will also have the same hash code. To not replace, you could use putIfAbsent if on Java 8, or keep the code you have. \$\endgroup\$ – Tunaki Sep 9 '16 at 9:31
  • \$\begingroup\$ in my scenario it really matters, because the objects I want to store in the set are used for synchronisation purposes. Being equals is not enough, I have to make sure that the java reference of objects in the set cannot change. And the javadoc of the Set goes in that way: il the object is already present the set is left unchanged. So a replacement is not an option. Thanks for your reply. \$\endgroup\$ – Aldian Sep 9 '16 at 9:49
  • \$\begingroup\$ @Aldian I edited to reflect this fact, thanks for poiting it out! \$\endgroup\$ – Tunaki Sep 9 '16 at 10:00
-1
\$\begingroup\$

This class feels as though it is trying to fulfill to many things. A Set, Queue and Hashmap are all different data structures for a reason.

As someone answered in the linked Stack Overflow question; there would be no point in having a get method for a Set object because each item in the Set needs to be unique. You acheive the same functinality by checking if the object is in the Set without having any issues with how to deal with the object not being in the Set (ie. returning the object if it is there or null if it isn't).

A Set by definition isn't really ordered either (and if its needed Java has the TreeSet class) . A method such as peek doesn't really make sense for a Set.

This seems like an unnecessary blend of multiple data structures. Specialized classes are a good thing. What use case would such a class have? It would likely lead to inexperienced programmers misusing it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.