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 }