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

From:

Royan <romayankin@gmail.com>

Newsgroups:

comp.lang.java.programmer

Date:

Wed, 6 Aug 2008 01:20:17 -0700 (PDT)

Message-ID:

<5595559a-c8dc-4987-b7ad-7a481aba0374@w7g2000hsa.googlegroups.com>

On 6 =C1=D7=C7, 05:45, Daniel Pitts
<newsgroup.spamfil...@virtualinfinity.net> wrote:

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.*;

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

=9A =9A =9Apublic int size() {
=9A =9A =9A =9A =9Areturn data.size();
=9A =9A =9A}

=9A =9A =9Apublic boolean isEmpty() {
=9A =9A =9A =9A =9Areturn data.isEmpty();
=9A =9A =9A}

=9A =9A =9Apublic boolean contains(Object o) {
=9A =9A =9A =9A =9Areturn data.contains(o);
=9A =9A =9A}

=9A =9A =9Apublic Iterator<T> iterator() {
=9A =9A =9A =9A =9Areturn data.iterator();
=9A =9A =9A}

=9A =9A =9Apublic Object[] toArray() {
=9A =9A =9A =9A =9Areturn data.toArray();
=9A =9A =9A}

=9A =9A =9Apublic <T> T[] toArray(T[] a) {
=9A =9A =9A =9A =9Areturn data.toArray(a);
=9A =9A =9A}

=9A =9A =9Apublic boolean add(T t) {
=9A =9A =9A =9A =9Areturn data.add(t);
=9A =9A =9A}

=9A =9A =9Apublic boolean offer(T t) {
=9A =9A =9A =9A =9Areturn add(t);
=9A =9A =9A}

=9A =9A =9Apublic T remove() {
=9A =9A =9A =9A =9Afinal Iterator<T> iterator = data.iterator();
=9A =9A =9A =9A =9AT t = iterator.next();
=9A =9A =9A =9A =9Aiterator.remove();
=9A =9A =9A =9A =9Areturn t;
=9A =9A =9A}

=9A =9A =9Apublic T poll() {
=9A =9A =9A =9A =9Afinal Iterator<T> iterator = data.iterator();
=9A =9A =9A =9A =9Aif (iterator.hasNext()) {
=9A =9A =9A =9A =9A =9A =9AT t = iterator.next();
=9A =9A =9A =9A =9A =9A =9Aiterator.remove();
=9A =9A =9A =9A =9A =9A =9Areturn t;
=9A =9A =9A =9A =9A}
=9A =9A =9A =9A =9Areturn null;
=9A =9A =9A}

=9A =9A =9Apublic T element() {
=9A =9A =9A =9A =9Areturn data.iterator().next();
=9A =9A =9A}

=9A =9A =9Apublic T peek() {
=9A =9A =9A =9A =9Afinal Iterator<T> iterator = data.iterator();
=9A =9A =9A =9A =9Aif (iterator.hasNext()) {
=9A =9A =9A =9A =9A =9A =9Areturn iterator.next();
=9A =9A =9A =9A =9A}
=9A =9A =9A =9A =9Areturn null;
=9A =9A =9A}

=9A =9A =9Apublic boolean remove(Object o) {
=9A =9A =9A =9A =9Areturn data.remove(o);
=9A =9A =9A}

=9A =9A =9Apublic boolean containsAll(Collection<?> c) {
=9A =9A =9A =9A =9Areturn data.containsAll(c);
=9A =9A =9A}

=9A =9A =9Apublic boolean addAll(Collection<? extends T> c) {
=9A =9A =9A =9A =9Areturn data.addAll(c);
=9A =9A =9A}

=9A =9A =9Apublic boolean retainAll(Collection<?> c) {
=9A =9A =9A =9A =9Areturn data.retainAll(c);
=9A =9A =9A}

=9A =9A =9Apublic boolean removeAll(Collection<?> c) {
=9A =9A =9A =9A =9Areturn data.removeAll(c);
=9A =9A =9A}

=9A =9A =9Apublic void clear() {
=9A =9A =9A =9A =9Adata.clear();
=9A =9A =9A}

=9A =9A =9Apublic boolean equals(Object o) {
=9A =9A =9A =9A =9Areturn data.equals(o);
=9A =9A =9A}

=9A =9A =9Apublic int hashCode() {
=9A =9A =9A =9A =9Areturn data.hashCode();
=9A =9A =9A}

}

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

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!

why is HashSet not appropriate for whatever you're trying to do?

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.