Package com.intellij.util.containers

Class HashSetQueue<T>

java.lang.Object

java.util.AbstractCollection<T>

com.intellij.util.containers.HashSetQueue<T>

All Implemented Interfaces:

java.lang.Iterable<T>, java.util.Collection<T>, java.util.Queue<T>

public class HashSetQueue<T>
extends java.util.AbstractCollection<T>
implements java.util.Queue<T>

Unbounded non-thread-safe Queue with fast add/remove/contains.
Differs from the conventional Queue by:

• The new method #find(T) which finds the queue element equivalent to its parameter in O(1) avg. time
• The contains(Object) method is O(1)
• The remove(Object) method is O(1)

Implementation is backed by gnu.trove.THashSet containing double-linked QueueEntry nodes holding elements themselves.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	HashSetQueue.PositionalIterator<T>

Constructor Summary

Constructors

Constructor and Description
HashSetQueue()

Method Summary

Modifier and Type	Method and Description
boolean	add(T t)
boolean	contains(java.lang.Object o)
T	element()
T	find(T t)
HashSetQueue.PositionalIterator<T>	iterator()
boolean	offer(T t)
T	peek()
T	poll()
T	remove()
boolean	remove(java.lang.Object o)
int	size()

Methods inherited from class java.util.AbstractCollection

addAll, clear, containsAll, isEmpty, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection

addAll, clear, containsAll, equals, hashCode, isEmpty, parallelStream, removeAll, removeIf, retainAll, spliterator, stream, toArray, toArray

Methods inherited from interface java.lang.Iterable

forEach

Constructor Detail

HashSetQueue

public HashSetQueue()

Method Detail

offer

public boolean offer(T t)

Specified by:

offer in interface java.util.Queue<T>

add

public boolean add(T t)

Specified by:

add in interface java.util.Collection<T>

Specified by:

add in interface java.util.Queue<T>

Overrides:

add in class java.util.AbstractCollection<T>

remove

public T remove()

Specified by:

remove in interface java.util.Queue<T>

poll

public T poll()

Specified by:

poll in interface java.util.Queue<T>

element

public T element()

Specified by:

element in interface java.util.Queue<T>

peek

public T peek()

Specified by:

peek in interface java.util.Queue<T>

find

public T find(T t)

remove

public boolean remove(java.lang.Object o)

Specified by:

remove in interface java.util.Collection<T>

Overrides:

remove in class java.util.AbstractCollection<T>

size

public int size()

Specified by:

size in interface java.util.Collection<T>

Specified by:

size in class java.util.AbstractCollection<T>

contains

public boolean contains(java.lang.Object o)

Specified by:

contains in interface java.util.Collection<T>

Overrides:

contains in class java.util.AbstractCollection<T>

iterator

public HashSetQueue.PositionalIterator<T> iterator()

Specified by:

iterator in interface java.lang.Iterable<T>

Specified by:

iterator in interface java.util.Collection<T>

Specified by:

iterator in class java.util.AbstractCollection<T>