Skip navigation links

com.tangosol.util
Class SortedBag

java.lang.Object
java.util.AbstractCollection
com.tangosol.util.SortedBag

All Implemented Interfaces:

java.lang.Iterable, java.util.Collection

Direct Known Subclasses:

SortedBag.ViewBag, TopNAggregator.PartialResult

public class SortedBag

extends java.util.AbstractCollection

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

protected class	SortedBag.UniqueElement UniqueElement represents a unique instance of a logical element in the bag.
protected class	SortedBag.ViewBag A range-limited view of the SortedBag.
protected static 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

protected java.util.concurrent.atomic.AtomicLong	m_atomicNonce The nonce used to increment the unique element ids.
protected java.util.Comparator	m_comparator The comparator used to compare logical elements.
protected java.util.NavigableMap	m_map The internal sorted map holding the bag contents.
protected static java.lang.Object	NO_VALUE Marker value object.

Constructor Summary

protected	SortedBag() Default constructor.
	SortedBag(java.util.Comparator comparator) Construct a SortedBag whose elements are to be ordered by the specified comparator.

Method Summary

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

equals, hashCode

Field Detail

NO_VALUE

protected static final java.lang.Object NO_VALUE

Marker value object.

m_atomicNonce

protected java.util.concurrent.atomic.AtomicLong m_atomicNonce

The nonce used to increment the unique element ids.

m_map

protected java.util.NavigableMap m_map

The internal sorted map holding the bag contents.

m_comparator

protected java.util.Comparator m_comparator

The comparator used to compare logical elements.

Constructor Detail

SortedBag

protected SortedBag()

Default constructor.

SortedBag

public SortedBag(java.util.Comparator 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 java.util.NavigableMap getInternalMap()

Return the internal sorted-map holding the bag contents.

Returns:

the internal sorted map holding the bag contents

getComparator

protected java.util.Comparator getComparator()

Return the Comparator used to order the bag contents.

Returns:

the Comparator used to order the bag contents

getNonceCounter

protected java.util.concurrent.atomic.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 java.util.Collection

Specified by:

size in class java.util.AbstractCollection

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Collection

Overrides:

isEmpty in class java.util.AbstractCollection

contains

public boolean contains(java.lang.Object o)

Specified by:

contains in interface java.util.Collection

Overrides:

contains in class java.util.AbstractCollection

iterator

public java.util.Iterator iterator()

Specified by:

iterator in interface java.lang.Iterable

Specified by:

iterator in interface java.util.Collection

Specified by:

iterator in class java.util.AbstractCollection

add

public boolean add(java.lang.Object o)

Specified by:

add in interface java.util.Collection

Overrides:

add in class java.util.AbstractCollection

remove

public boolean remove(java.lang.Object o)

Specified by:

remove in interface java.util.Collection

Overrides:

remove in class java.util.AbstractCollection

subBag

public SortedBag subBag(java.lang.Object fromElement,
                        java.lang.Object 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:

java.lang.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.

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

java.lang.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 headBag(java.lang.Object 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:

java.lang.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.

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

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

tailBag

public SortedBag tailBag(java.lang.Object 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:

java.lang.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.

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

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

first

public java.lang.Object 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 java.lang.Object 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 java.lang.Object 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 java.lang.Object 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 java.util.NavigableMap instantiateInternalMap(java.util.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 wrap(java.lang.Object o)

Wrap the specified element to ensure uniqueness.

Parameters:

o - the element to wrap

Returns:

a unique element representing the specified element

unwrap

protected java.lang.Object unwrap(java.lang.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

Skip navigation links