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 }