1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
/*
* SonarQube
* Copyright (C) 2009-2025 SonarSource SA
* mailto:info AT sonarsource DOT com
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 3 of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
package org.sonar.duplications.index;
public final class DataUtils {
public interface Sortable {
/**
* @return the number of elements.
*/
int size();
/**
* Swaps elements in positions i and j.
*/
void swap(int i, int j);
/**
* @return true if element in position i less than in position j.
*/
boolean isLess(int i, int j);
}
/**
* Value for search must be stored in position {@link Sortable#size() size}.
*/
public static int binarySearch(Sortable data) {
int value = data.size();
int lower = 0;
int upper = data.size();
while (lower < upper) {
int mid = (lower + upper) >> 1;
if (data.isLess(mid, value)) {
lower = mid + 1;
} else {
upper = mid;
}
}
return lower;
}
public static void sort(Sortable data) {
quickSort(data, 0, data.size() - 1);
}
private static void bubbleSort(Sortable data, int left, int right) {
for (int i = right; i > left; i--) {
for (int j = left; j < i; j++) {
if (data.isLess(j + 1, j)) {
data.swap(j, j + 1);
}
}
}
}
private static int partition(Sortable data, int i, int j) {
// can be selected randomly
int pivot = i + (j - i) / 2;
while (i <= j) {
while (data.isLess(i, pivot)) {
i++;
}
while (data.isLess(pivot, j)) {
j--;
}
if (i <= j) {
data.swap(i, j);
if (i == pivot) {
pivot = j;
} else if (j == pivot) {
pivot = i;
}
i++;
j--;
}
}
return i;
}
private static void quickSort(Sortable data, int low, int high) {
if (high - low < 5) {
bubbleSort(data, low, high);
return;
}
int i = partition(data, low, high);
if (low < i - 1) {
quickSort(data, low, i - 1);
}
if (i < high) {
quickSort(data, i, high);
}
}
private DataUtils() {
}
}
|
