TUM CCSM Commons

edu.tum.cs.commons.collections
Class SortedCounterSet<E extends java.lang.Comparable<? super E>>

java.lang.Object
  extended by edu.tum.cs.commons.collections.CounterSet<E>
      extended by edu.tum.cs.commons.collections.SortedCounterSet<E>

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.

Version:
$Rev: 26283 $
Author:
Florian Deissenboeck, $Author: juergens $
Rating:
GREEN Hash: FFB54DECEAD398EF790F0858C9E970D4

Field Summary
 
Fields inherited from class edu.tum.cs.commons.collections.CounterSet
map, total
 
Constructor Summary
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
 int getRangeSum(E firstElement, E lastElement)
          Obtain the sum of all values in a certain range of elements.
 
Methods inherited from class edu.tum.cs.commons.collections.CounterSet
contains, getKeys, getTotal, getValue, inc, inc
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

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.

TUM CCSM Commons

TUM CCSM Commons - 2.7