Package com.tangosol.util

Class SortedBag<E>

java.lang.Object

java.util.AbstractCollection<E>

com.tangosol.util.SortedBag<E>

All Implemented Interfaces:

Iterable<E>, Collection<E>

Direct Known Subclasses:

SortedBag.ViewBag, TopNAggregator.PartialResult

public class SortedBag<E>
extends AbstractCollection<E>

SortedBag is a multiset or bag implementation that supports sorted traversal of the contained elements and is optimized for insertions and removals.

This implementation is not thread-safe and does not support null elements.

Author:

rhl 2013.04.24

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected class	SortedBag.UniqueElement<E>	UniqueElement represents a unique instance of a logical element in the bag.
protected class	SortedBag.ViewBag	A range-limited view of the SortedBag.
protected class	SortedBag.WrapperComparator	WrapperComparator is a Comparator implementation that is aware of SortedBag.UniqueElement wrappers and will delegate the comparison of the elements in both forms to the wrapped comparator.

Field Summary

Fields

Modifier and Type	Field	Description
protected AtomicLong	m_atomicNonce	The nonce used to increment the unique element ids.
protected Comparator<? super E>	m_comparator	The comparator used to compare logical elements.
protected NavigableMap	m_map	The internal sorted map holding the bag contents.
protected static Object	NO_VALUE	Marker value object.

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	SortedBag()	Default constructor.
	SortedBag(Comparator<? super E> comparator)	Construct a SortedBag whose elements are to be ordered by the specified comparator.

Method Summary

Modifier and Type	Method	Description
boolean	add(E o)
boolean	contains(Object o)
E	first()	Returns the first (lowest) element currently in this bag.
protected Comparator<? super E>	getComparator()	Return the Comparator used to order the bag contents.
protected NavigableMap	getInternalMap()	Return the internal sorted-map holding the bag contents.
protected AtomicLong	getNonceCounter()	Return the nonce counter used to assign unique element ids.
SortedBag<E>	headBag(E toElement)	Returns a view of the portion of this bag whose elements are strictly less than toElement.
protected NavigableMap	instantiateInternalMap(Comparator comparator)	Factory for the sorted internal map to use to hold the bag elements.
boolean	isEmpty()
Iterator<E>	iterator()
E	last()	Returns the last (highest) element currently in this bag.
boolean	remove(Object o)
E	removeFirst()	Remove and return the least element in this bag, or null if empty.
E	removeLast()	Remove and return the greatest element in this bag, or null if empty.
int	size()
SortedBag<E>	subBag(E fromElement, E toElement)	Returns a view of the portion of this bag whose elements range from fromElement, inclusive, to toElement, exclusive.
SortedBag<E>	tailBag(E fromElement)	Returns a view of the portion of this bag whose elements are greater than or equal to fromElement.
protected E	unwrap(Object o)	Unwrap the specified element (which could be a wrapped or an "actual") element.
protected SortedBag.UniqueElement<E>	wrap(E o)	Wrap the specified element to ensure uniqueness.

Methods inherited from class java.util.AbstractCollection

addAll, clear, containsAll, 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

equals, hashCode, parallelStream, removeIf, spliterator, stream, toArray

Methods inherited from interface java.lang.Iterable

forEach

Field Detail

NO_VALUE

protected static final Object NO_VALUE

Marker value object.

m_atomicNonce

protected AtomicLong m_atomicNonce

The nonce used to increment the unique element ids.

m_map

protected NavigableMap m_map

The internal sorted map holding the bag contents.

m_comparator

protected Comparator<? super E> m_comparator

The comparator used to compare logical elements.

Constructor Detail

SortedBag

protected SortedBag()

Default constructor.

SortedBag

public SortedBag(Comparator<? super E> comparator)

Construct a SortedBag whose elements are to be ordered by the specified comparator.

Parameters:

comparator - the comparator to use to order the elements

Method Detail

getInternalMap

protected NavigableMap getInternalMap()

Return the internal sorted-map holding the bag contents.

Returns:

the internal sorted map holding the bag contents

getComparator

protected Comparator<? super E> getComparator()

Return the Comparator used to order the bag contents.

Returns:

the Comparator used to order the bag contents

getNonceCounter

protected AtomicLong getNonceCounter()

Return the nonce counter used to assign unique element ids.

Returns:

the nonce counter

size

public int size()

Specified by:

size in interface Collection<E>

Specified by:

size in class AbstractCollection<E>

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface Collection<E>

Overrides:

isEmpty in class AbstractCollection<E>

contains

public boolean contains(Object o)

Specified by:

contains in interface Collection<E>

Overrides:

contains in class AbstractCollection<E>

iterator

public Iterator<E> iterator()

Specified by:

iterator in interface Collection<E>

Specified by:

iterator in interface Iterable<E>

Specified by:

iterator in class AbstractCollection<E>

add

public boolean add(E o)

Specified by:

add in interface Collection<E>

Overrides:

add in class AbstractCollection<E>

remove

public boolean remove(Object o)

Specified by:

remove in interface Collection<E>

Overrides:

remove in class AbstractCollection<E>

subBag

public SortedBag<E> subBag(E fromElement,
                           E toElement)

Returns a view of the portion of this bag whose elements range from fromElement, inclusive, to toElement, exclusive. (If fromElement and toElement are equal, the returned bag is empty.) The returned bag is backed by this bag, so changes in the returned bag are reflected in this bag, and vice-versa. The returned bag supports all optional bag operations that this bag supports.

The returned bag will throw an IllegalArgumentException on an attempt to insert an element outside its range.

Parameters:

fromElement - low endpoint (inclusive) of the returned bag

toElement - high endpoint (exclusive) of the returned bag

Returns:

a view of the portion of this bag whose elements range from fromElement, inclusive, to toElement, exclusive

Throws:

ClassCastException - if fromElement and toElement cannot be compared to one another using this bag's comparator (or, if the bag has no comparator, using natural ordering). Implementations may, but are not required to, throw this exception if fromElement or toElement cannot be compared to elements currently in the bag.

NullPointerException - if fromElement or toElement is null and this bag does not permit null elements

IllegalArgumentException - if fromElement is greater than toElement; or if this bag itself has a restricted range, and fromElement or toElement lies outside the bounds of the range

headBag

public SortedBag<E> headBag(E toElement)

Returns a view of the portion of this bag whose elements are strictly less than toElement. The returned bag is backed by this bag, so changes in the returned bag are reflected in this bag, and vice-versa. The returned bag supports all optional bag operations that this bag supports.

The returned bag will throw an IllegalArgumentException on an attempt to insert an element outside its range.

Parameters:

toElement - high endpoint (exclusive) of the returned bag

Returns:

a view of the portion of this bag whose elements are strictly less than toElement

Throws:

ClassCastException - if toElement is not compatible with this bag's comparator (or, if the bag has no comparator, if toElement does not implement Comparable). Implementations may, but are not required to, throw this exception if toElement cannot be compared to elements currently in the bag.

NullPointerException - if toElement is null and this bag does not permit null elements

IllegalArgumentException - if this bag itself has a restricted range, and toElement lies outside the bounds of the range

tailBag

public SortedBag<E> tailBag(E fromElement)

Returns a view of the portion of this bag whose elements are greater than or equal to fromElement. The returned bag is backed by this bag, so changes in the returned bag are reflected in this bag, and vice-versa. The returned bag supports all optional bag operations that this bag supports.

The returned bag will throw an IllegalArgumentException on an attempt to insert an element outside its range.

Parameters:

fromElement - low endpoint (inclusive) of the returned bag

Returns:

a view of the portion of this bag whose elements are greater than or equal to fromElement

Throws:

ClassCastException - if fromElement is not compatible with this bag's comparator (or, if the bag has no comparator, if fromElement does not implement Comparable). Implementations may, but are not required to, throw this exception if fromElement cannot be compared to elements currently in the bag.

NullPointerException - if fromElement is null and this bag does not permit null elements

IllegalArgumentException - if this bag itself has a restricted range, and fromElement lies outside the bounds of the range

first

public E first()

Returns the first (lowest) element currently in this bag.

Returns:

the first (lowest) element currently in this bag

Throws:

NoSuchElementException - if this bag is empty

last

public E last()

Returns the last (highest) element currently in this bag.

Returns:

the last (highest) element currently in this bag

Throws:

NoSuchElementException - if this bag is empty

removeFirst

public E removeFirst()

Remove and return the least element in this bag, or null if empty.

Returns:

the removed first element of this bag, or null if empty

removeLast

public E removeLast()

Remove and return the greatest element in this bag, or null if empty.

Returns:

the removed last element of this bag, or null if empty

instantiateInternalMap

protected NavigableMap instantiateInternalMap(Comparator comparator)

Factory for the sorted internal map to use to hold the bag elements.

Parameters:

comparator - the comparator to use to sort the bag elements

Returns:

a sorted map

wrap

protected SortedBag.UniqueElement<E> wrap(E o)

Wrap the specified element to ensure uniqueness.

Parameters:

o - the element to wrap

Returns:

a unique element representing the specified element

unwrap

protected E unwrap(Object o)

Unwrap the specified element (which could be a wrapped or an "actual") element.

Parameters:

o - the element to unwrap

Returns:

the unwrapped element