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 }