001 /*--------------------------------------------------------------------------+ 002 $Id: SortedCounterSet.java 26283 2010-02-18 11:18:57Z juergens $ 003 | | 004 | Copyright 2005-2010 Technische Universitaet Muenchen | 005 | | 006 | Licensed under the Apache License, Version 2.0 (the "License"); | 007 | you may not use this file except in compliance with the License. | 008 | You may obtain a copy of the License at | 009 | | 010 | http://www.apache.org/licenses/LICENSE-2.0 | 011 | | 012 | Unless required by applicable law or agreed to in writing, software | 013 | distributed under the License is distributed on an "AS IS" BASIS, | 014 | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | 015 | See the License for the specific language governing permissions and | 016 | limitations under the License. | 017 +--------------------------------------------------------------------------*/ 018 package edu.tum.cs.commons.collections; 019 020 import java.util.ArrayList; 021 import java.util.Collections; 022 import java.util.Comparator; 023 import java.util.List; 024 025 /** 026 * A counter set supporting ranged access to its values, i.e. it is possible to 027 * query the sum of values for all keys in a given range. Inserting items works 028 * in (amortized) constant time, but the range query is potentially expensive. 029 * 030 * @author Florian Deissenboeck 031 * @author $Author: juergens $ 032 * @version $Rev: 26283 $ 033 * @levd.rating GREEN Hash: FFB54DECEAD398EF790F0858C9E970D4 034 */ 035 public class SortedCounterSet<E extends Comparable<? super E>> extends 036 CounterSet<E> { 037 038 /** 039 * The comparator used to define the order of the elements. This may be 040 * <code>null</code>. 041 */ 042 private final Comparator<? super E> comparator; 043 044 /** 045 * Create new counter array that orders its elements by the natural order. 046 */ 047 public SortedCounterSet() { 048 comparator = null; 049 } 050 051 /** 052 * Create new counter array with specific comparator to define order. 053 */ 054 public SortedCounterSet(Comparator<? super E> comparator) { 055 this.comparator = comparator; 056 } 057 058 /** 059 * Obtain the sum of all values in a certain range of elements. This 060 * operation runs in time <code>O(n*log(n))</code> where <code>n</code> 061 * is the size of this set, as the list of items is sorted each time. 062 * 063 * @param firstElement 064 * the first element to include. If the element is not present in 065 * the list, the smallest element greater than this one is used. 066 * @param lastElement 067 * the last element to include. If the element is not present in 068 * the list, the largest element smaller than this one is used. 069 */ 070 public int getRangeSum(E firstElement, E lastElement) { 071 072 List<E> elementList = new ArrayList<E>(getKeys()); 073 074 // if the list is empty the sum must be zero 075 if (elementList.isEmpty()) { 076 return 0; 077 } 078 079 // this uses natural ordering if compartor is null 080 Collections.sort(elementList, comparator); 081 082 // determine first index in the list 083 int firstIndex; 084 // this uses natural ordering if compartor is null 085 firstIndex = Collections.binarySearch(elementList, firstElement, 086 comparator); 087 // see API documentation of Collections.binarySearch 088 if (firstIndex < 0) { 089 firstIndex = (firstIndex + 1) * (-1); 090 } 091 092 // determine last index in the lst 093 int lastIndex; 094 lastIndex = Collections.binarySearch(elementList, lastElement, 095 comparator); 096 097 // see API documentation of Collections.binarySearch 098 if (lastIndex < 0) { 099 lastIndex = (lastIndex + 2) * (-1); 100 } 101 102 int sum = 0; 103 // iterate over the range and add values 104 for (int i = firstIndex; i <= lastIndex; i++) { 105 sum += getValue(elementList.get(i)); 106 } 107 108 return sum; 109 } 110 }