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