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

  • Field Details

    • 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 Details

    • 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 Details

    • 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<E>.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