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