001/* 002 * Sonar, open source software quality management tool. 003 * Copyright (C) 2008-2012 SonarSource 004 * mailto:contact AT sonarsource DOT com 005 * 006 * Sonar is free software; you can redistribute it and/or 007 * modify it under the terms of the GNU Lesser General Public 008 * License as published by the Free Software Foundation; either 009 * version 3 of the License, or (at your option) any later version. 010 * 011 * Sonar is distributed in the hope that it will be useful, 012 * but WITHOUT ANY WARRANTY; without even the implied warranty of 013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 014 * Lesser General Public License for more details. 015 * 016 * You should have received a copy of the GNU Lesser General Public 017 * License along with Sonar; if not, write to the Free Software 018 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 019 */ 020package org.sonar.duplications.index; 021 022public final class DataUtils { 023 024 public interface Sortable { 025 026 /** 027 * @return the number of elements. 028 */ 029 int size(); 030 031 /** 032 * Swaps elements in positions i and j. 033 */ 034 void swap(int i, int j); 035 036 /** 037 * @return true if element in position i less than in position j. 038 */ 039 boolean isLess(int i, int j); 040 041 } 042 043 /** 044 * Value for search must be stored in position {@link Sortable#size() size}. 045 */ 046 public static int binarySearch(Sortable data) { 047 int value = data.size(); 048 int lower = 0; 049 int upper = data.size(); 050 while (lower < upper) { 051 int mid = (lower + upper) >> 1; 052 if (data.isLess(mid, value)) { 053 lower = mid + 1; 054 } else { 055 upper = mid; 056 } 057 } 058 return lower; 059 } 060 061 public static void sort(Sortable data) { 062 quickSort(data, 0, data.size() - 1); 063 } 064 065 private static void bubbleSort(Sortable data, int left, int right) { 066 for (int i = right; i > left; i--) { 067 for (int j = left; j < i; j++) { 068 if (data.isLess(j + 1, j)) { 069 data.swap(j, j + 1); 070 } 071 } 072 } 073 } 074 075 private static int partition(Sortable data, int i, int j) { 076 // can be selected randomly 077 int pivot = i + (j - i) / 2; 078 while (i <= j) { 079 while (data.isLess(i, pivot)) { 080 i++; 081 } 082 while (data.isLess(pivot, j)) { 083 j--; 084 } 085 if (i <= j) { 086 data.swap(i, j); 087 if (i == pivot) { 088 pivot = j; 089 } else if (j == pivot) { 090 pivot = i; 091 } 092 i++; 093 j--; 094 } 095 } 096 return i; 097 } 098 099 private static void quickSort(Sortable data, int low, int high) { 100 if (high - low < 5) { 101 bubbleSort(data, low, high); 102 return; 103 } 104 int i = partition(data, low, high); 105 if (low < i - 1) { 106 quickSort(data, low, i - 1); 107 } 108 if (i < high) { 109 quickSort(data, i, high); 110 } 111 } 112 113 private DataUtils() { 114 } 115 116}