org.conqat.lib.commons.collections

Class SortedCounterSet<E extends java.lang.Comparable<? super E>>

java.lang.Object

org.conqat.lib.commons.collections.CounterSet<E>

org.conqat.lib.commons.collections.SortedCounterSet<E>

All Implemented Interfaces:

java.io.Serializable, java.lang.Iterable<Pair<E,java.lang.Integer>>

public class SortedCounterSet<E extends java.lang.Comparable<? super E>>
extends CounterSet<E>

A counter set supporting ranged access to its values, i.e. it is possible to query the sum of values for all keys in a given range. Inserting items works in (amortized) constant time, but the range query is potentially expensive.

Author:

Florian Deissenboeck

See Also:

Serialized Form

Field Summary

Fields inherited from class org.conqat.lib.commons.collections.CounterSet

map, total

Constructor Summary

Constructors

Constructor and Description
SortedCounterSet() Create new counter array that orders its elements by the natural order.
SortedCounterSet(java.util.Comparator<? super E> comparator) Create new counter array with specific comparator to define order.

Method Summary

Modifier and Type	Method and Description
int	getRangeSum(E firstElement, E lastElement) Obtain the sum of all values in a certain range of elements.

Methods inherited from class org.conqat.lib.commons.collections.CounterSet

add, clear, contains, equals, getKeys, getKeysByValueAscending, getKeysByValueDescending, getTotal, getValue, hashCode, inc, inc, incAll, incAll, iterator, printValueDistribution, printValueDistribution, remove, removeAll, removeIf, removeSecondFromFirst, toMap, toMapWithoutZeroEntries, toString, values

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

SortedCounterSet

public SortedCounterSet()

Create new counter array that orders its elements by the natural order.

SortedCounterSet

public SortedCounterSet(java.util.Comparator<? super E> comparator)

Create new counter array with specific comparator to define order.

Method Detail

getRangeSum

public int getRangeSum(E firstElement,
                       E lastElement)

Obtain the sum of all values in a certain range of elements. This operation runs in time O(n*log(n)) where n is the size of this set, as the list of items is sorted each time.

Parameters:

firstElement - the first element to include. If the element is not present in the list, the smallest element greater than this one is used.

lastElement - the last element to include. If the element is not present in the list, the largest element smaller than this one is used.