Stack/Queue-like collection that contains no duplicates

[Royan]

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?

 

[Tom Anderson]

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

HashSet.

Push is just add().

Pop is:

Foo pop(Set<Foo> s) {
Iterator<Foo> it = s.iterator() ;
Foo popped = it.next() ;
it.remove() ;
return popped ;
}

Push is O(1). I would hazard a guess that pop will be O(1), but i really
don't know for sure.

tom

 

[Daniel Pitts]

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();
}
}

 

[Royan]

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();
š š š}

}

Thanks Daniel,
well I was actually looking for something that already exists as a
standard collection, but since there is nothing like that I'll use
your solution... not that I'm that lazy, but why not? Public domain,
no warranty, cool!
Because it does not have built-in push and pop methods and my app
severely relies on them, so writing that "for loop" would really
annoying.