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    }