001    /*--------------------------------------------------------------------------+
002    $Id: SortableDataUtils.java 29399 2010-07-27 15:03:17Z 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    /**
021     * Abstraction for sortable/comparable data. This class supports basic
022     * algorithms, such as sorting and binary search on any data which can be mapped
023     * to a random access list. The main benefit of this class, is that the type of
024     * data is operated on must not be known (or be a concrete type), thus it can
025     * also be used to sort data spread over multiple lists or arrays.
026     * 
027     * @author hummelb
028     * @author $Author: juergens $
029     * @version $Rev: 29399 $
030     * @levd.rating GREEN Hash: D91A00D48171C7C62E158FE291D7FCA9
031     */
032    public class SortableDataUtils {
033    
034            /**
035             * Performs a binary search for the element at the given index. The returned
036             * index will be the first index at which the element could be inserted
037             * without violating the sorting order. If the underlying data is not
038             * sorted, the result is undefined. The result will be between 0 and
039             * {@link ISortableData#size()} inclusive. The given element index may be
040             * larger than {@link ISortableData#size()}, i.e. the element does not have
041             * to be in the list.
042             */
043            public static int binarySearch(ISortableData data, int elementIndex) {
044                    int lower = 0;
045                    int upper = data.size();
046                    while (lower < upper) {
047                            // For next line see
048                            // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
049                            int mid = lower + upper >>> 1;
050                            if (data.isLess(mid, elementIndex)) {
051                                    lower = mid + 1;
052                            } else {
053                                    upper = mid;
054                            }
055                    }
056                    return lower;
057            }
058    
059            /** Sorts the data in place using a randomized quick sort algorithm. */
060            public static void sort(ISortableData data) {
061                    sort(data, 0, data.size());
062            }
063    
064            /**
065             * Sorts the data between <code>begin</code> (inclusive) and
066             * <code>end</code> (exclusive).
067             */
068            private static void sort(ISortableData data, int begin, int end) {
069                    if (end - begin < 5) {
070                            bubbleSort(data, begin, end);
071                            return;
072                    }
073    
074                    int pivot = begin + (int) (Math.random() * (end - begin));
075                    int lower = begin;
076                    int upper = end - 1;
077                    while (lower <= upper) {
078                            if (data.isLess(lower, pivot)) {
079                                    ++lower;
080                            } else {
081                                    pivot = swapFixPivot(data, lower, upper, pivot);
082                                    --upper;
083                            }
084                    }
085    
086                    // make pivot the central element
087                    if (lower != pivot) {
088                            data.swap(lower, pivot);
089                    }
090    
091                    sort(data, begin, lower);
092                    sort(data, lower + 1, end);
093            }
094    
095            /**
096             * Performs a swap but preserves the index of the pivot element. So, if the
097             * swap affects the pivot element, the new pivot index is returned.
098             */
099            private static int swapFixPivot(ISortableData data, int i, int j, int pivot) {
100                    data.swap(i, j);
101                    if (i == pivot) {
102                            return j;
103                    }
104                    if (j == pivot) {
105                            return i;
106                    }
107                    return pivot;
108            }
109    
110            /**
111             * Performs bubble sort on the given sub range. This is used for the base
112             * case in the quick sort algorithm.
113             */
114            // package visible for testing
115            /* package */static void bubbleSort(ISortableData data, int begin, int end) {
116                    for (int i = end - 1; i > begin; --i) {
117                            for (int j = begin; j < i; ++j) {
118                                    if (data.isLess(j + 1, j)) {
119                                            data.swap(j, j + 1);
120                                    }
121                            }
122                    }
123            }
124    }