Re: Stack/Queue-like collection that contains no duplicates

From:

Daniel Pitts <newsgroup.spamfilter@virtualinfinity.net>

Newsgroups:

comp.lang.java.programmer

Date:

Tue, 05 Aug 2008 18:45:21 -0700

Message-ID:

<48990256$0$16952$7836cce5@newsrazor.net>

Royan wrote:

I'm looking for the collection with following properties.

- Contains no duplicate elements
- Has push/pop (offer/poll) like methods
- Insertion order does not matter

The best I could find was TreeSet but it maintains ordering which
produced log(n) overhead for add/remove operations. As far as this is
not that critical for me I'll eventually use TreeSet, but perhaps
someone knows some other collection that does not maintain order of
elements and at the same time has all those characteristics I've
listed above?

Took me 20 minutes:

Public domain, no warranty.

import java.util.*;

/**
  * @author Daniel Pitts
  */
public class UniqueQueue<T> implements Queue<T>, Set<T> {
     private final Set<T> data = new LinkedHashSet<T>();

     public int size() {
         return data.size();
     }

     public boolean isEmpty() {
         return data.isEmpty();
     }

     public boolean contains(Object o) {
         return data.contains(o);
     }

     public Iterator<T> iterator() {
         return data.iterator();
     }

     public Object[] toArray() {
         return data.toArray();
     }

     public <T> T[] toArray(T[] a) {
         return data.toArray(a);
     }

     public boolean add(T t) {
         return data.add(t);
     }

     public boolean offer(T t) {
         return add(t);
     }

     public T remove() {
         final Iterator<T> iterator = data.iterator();
         T t = iterator.next();
         iterator.remove();
         return t;
     }

     public T poll() {
         final Iterator<T> iterator = data.iterator();
         if (iterator.hasNext()) {
             T t = iterator.next();
             iterator.remove();
             return t;
         }
         return null;
     }

     public T element() {
         return data.iterator().next();
     }

     public T peek() {
         final Iterator<T> iterator = data.iterator();
         if (iterator.hasNext()) {
             return iterator.next();
         }
         return null;
     }

     public boolean remove(Object o) {
         return data.remove(o);
     }

     public boolean containsAll(Collection<?> c) {
         return data.containsAll(c);
     }

     public boolean addAll(Collection<? extends T> c) {
         return data.addAll(c);
     }

     public boolean retainAll(Collection<?> c) {
         return data.retainAll(c);
     }

     public boolean removeAll(Collection<?> c) {
         return data.removeAll(c);
     }

     public void clear() {
         data.clear();
     }

     public boolean equals(Object o) {
         return data.equals(o);
     }

     public int hashCode() {
         return data.hashCode();
     }
}

--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>