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
|
package ij.util;
/** A simple QuickSort for String arrays. */
public class StringSorter {
/** Sorts the array. */
public static void sort(String[] a) {
if (a==null)
return;
if (!alreadySorted(a))
sort(a, 0, a.length - 1);
}
static void sort(String[] a, int from, int to) {
int i = from, j = to;
String center = a[ (from + to) / 2 ];
do {
while ( i < to && center.compareTo(a[i]) > 0 ) i++;
while ( j > from && center.compareTo(a[j]) < 0 ) j--;
if (i < j) {String temp = a[i]; a[i] = a[j]; a[j] = temp; }
if (i <= j) { i++; j--; }
} while(i <= j);
if (from < j) sort(a, from, j);
if (i < to) sort(a, i, to);
}
static boolean alreadySorted(String[] a) {
for (int i=1; i<a.length; i++ ) {
if (a[i].compareTo(a[i-1]) < 0 )
return false;
}
return true;
}
/** Sorts file names containing numerical components.
* Author: Norbert Vischer
*/
public static String[] sortNumerically(String[] list) {
int n = list.length;
String[] paddedList = getPaddedNames(list);
String[] sortedList = new String[n];
int[] indexes = Tools.rank(paddedList);
for (int i = 0; i < n; i++)
sortedList[i] = list[indexes[i]];
return sortedList;
}
// Pads individual numeric string components with zeroes for correct sorting
private static String[] getPaddedNames(String[] names) {
int nNames = names.length;
String[] paddedNames = new String[nNames];
int maxLen = 0;
for (int jj = 0; jj < nNames; jj++) {
if (names[jj].length() > maxLen) {
maxLen = names[jj].length();
}
}
int maxNums = maxLen / 2 + 1;//calc array sizes
int[][] numberStarts = new int[names.length][maxNums];
int[][] numberLengths = new int[names.length][maxNums];
int[] maxDigits = new int[maxNums];
//a) record position and digit count of 1st, 2nd, .. n-th number in string
for (int jj = 0; jj < names.length; jj++) {
String name = names[jj];
boolean inNumber = false;
int nNumbers = 0;
int nDigits = 0;
for (int pos = 0; pos < name.length(); pos++) {
boolean isDigit = name.charAt(pos) >= '0' && name.charAt(pos) <= '9';
if (isDigit) {
nDigits++;
if (!inNumber) {
numberStarts[jj][nNumbers] = pos;
inNumber = true;
}
}
if (inNumber && (!isDigit || (pos == name.length() - 1))) {
inNumber = false;
if (maxDigits[nNumbers] < nDigits) {
maxDigits[nNumbers] = nDigits;
}
numberLengths[jj][nNumbers] = nDigits;
nNumbers++;
nDigits = 0;
}
}
}
//b) perform padding
for (int jj = 0; jj < names.length; jj++) {
String name = names[jj];
int numIndex = 0;
StringBuilder destName = new StringBuilder();
for (int srcPtr = 0; srcPtr < name.length(); srcPtr++) {
if (srcPtr == numberStarts[jj][numIndex]) {
int numLen = numberLengths[jj][numIndex];
if (numLen > 0) {
for (int pad = 0; pad < (maxDigits[numIndex] - numLen); pad++) {
destName.append('0');
}
}
numIndex++;
}
destName.append(name.charAt(srcPtr));
}
paddedNames[jj] = destName.toString();
}
return paddedNames;
}
}
|
