Mercurial > jhg

annotate src/org/tmatesoft/hg/internal/ArrayHelper.java @ 310:237de162be28

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fix building sort reverse array when element was initially in correct position.
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Sat, 24 Sep 2011 13:25:33 +0200
parents 2f2ab5c27f41
children b9592e21176a
rev   line source
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
1 /*
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
2 * Copyright (c) 2011 TMate Software Ltd
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
3 *
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
4 * This program is free software; you can redistribute it and/or modify
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
5 * it under the terms of the GNU General Public License as published by
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
6 * the Free Software Foundation; version 2 of the License.
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
7 *
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
8 * This program is distributed in the hope that it will be useful,
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
11 * GNU General Public License for more details.
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
12 *
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
13 * For information on how to redistribute this software under
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
14 * the terms of a license other than GNU General Public License
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
15 * contact TMate Software at support@hg4j.com
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
16 */
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
17 package org.tmatesoft.hg.internal;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
18
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
19 /**
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
20 *
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
21 * @author Artem Tikhomirov
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
22 * @author TMate Software Ltd.
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
23 */
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
24 public class ArrayHelper {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
25 private int[] reverse;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
26
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
27 @SuppressWarnings("unchecked")
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
28 public void sort(Comparable<?>[] a) {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
29 // Object[] aux = (Object[]) a.clone();
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
30 reverse = new int[a.length];
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
31 sort1((Comparable<Object>[])a, 0, a.length);
310
237de162be28 Fix building sort reverse array when element was initially in correct position.
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 307
diff changeset
32 for (int i = 0; i < reverse.length; i++) {
237de162be28 Fix building sort reverse array when element was initially in correct position.
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 307
diff changeset
33 // element that was not moved don't have an index in reverse.
237de162be28 Fix building sort reverse array when element was initially in correct position.
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 307
diff changeset
34 // perhaps, can do it inside sort alg?
237de162be28 Fix building sort reverse array when element was initially in correct position.
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 307
diff changeset
35 // TODO tests!
237de162be28 Fix building sort reverse array when element was initially in correct position.
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 307
diff changeset
36 if (reverse[i] == 0) {
237de162be28 Fix building sort reverse array when element was initially in correct position.
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 307
diff changeset
37 reverse[i] = i+1;
237de162be28 Fix building sort reverse array when element was initially in correct position.
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 307
diff changeset
38 }
237de162be28 Fix building sort reverse array when element was initially in correct position.
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 307
diff changeset
39 }
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
40 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
41
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
42 private void sort1(Comparable<Object> x[], int off, int len) {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
43 // Insertion sort on smallest arrays
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
44 if (len < 7) {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
45 for (int i=off; i<len+off; i++)
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
46 for (int j=i; j>off && x[j-1].compareTo(x[j]) > 0; j--)
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
47 swap(x, j, j-1);
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
48 return;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
49 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
50
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
51 // Choose a partition element, v
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
52 int m = off + (len >> 1); // Small arrays, middle element
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
53 if (len > 7) {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
54 int l = off;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
55 int n = off + len - 1;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
56 if (len > 40) { // Big arrays, pseudomedian of 9
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
57 int s = len/8;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
58 l = med3(x, l, l+s, l+2*s);
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
59 m = med3(x, m-s, m, m+s);
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
60 n = med3(x, n-2*s, n-s, n);
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
61 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
62 m = med3(x, l, m, n); // Mid-size, med of 3
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
63 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
64 Comparable<Object> v = x[m];
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
65
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
66 // Establish Invariant: v* (<v)* (>v)* v*
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
67 int a = off, b = a, c = off + len - 1, d = c;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
68 while(true) {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
69 while (b <= c && x[b].compareTo(v) <= 0) {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
70 if (x[b] == v)
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
71 swap(x, a++, b);
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
72 b++;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
73 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
74 while (c >= b && x[c].compareTo(v) >= 0) {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
75 if (x[c] == v)
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
76 swap(x, c, d--);
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
77 c--;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
78 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
79 if (b > c)
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
80 break;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
81 swap(x, b++, c--);
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
82 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
83
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
84 // Swap partition elements back to middle
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
85 int s, n = off + len;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
86 s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
87 s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
88
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
89 // Recursively sort non-partition-elements
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
90 if ((s = b-a) > 1)
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
91 sort1(x, off, s);
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
92 if ((s = d-c) > 1)
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
93 sort1(x, n-s, s);
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
94 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
95
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
96 /**
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
97 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
98 */
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
99 private void vecswap(Object[] x, int a, int b, int n) {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
100 for (int i=0; i<n; i++, a++, b++) {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
101 swap(x, a, b);
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
102 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
103 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
104
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
105 /**
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
106 * Returns the index of the median of the three indexed integers.
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
107 */
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
108 private static int med3(Comparable<Object>[] x, int a, int b, int c) {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
109 return (x[a].compareTo(x[b]) < 0 ?
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
110 (x[b].compareTo(x[c]) < 0 ? b : x[a].compareTo(x[c]) < 0 ? c : a) :
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
111 (x[b].compareTo(x[c]) > 0 ? b : x[a].compareTo(x[c]) > 0 ? c : a));
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
112 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
113
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
114
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
115 /**
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
116 * @return the reverse
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
117 */
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
118 public int[] getReverse() {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
119 return reverse;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
120 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
121
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
122 /**
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
123 * Swaps x[a] with x[b].
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
124 */
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
125 private void swap(Object[] x, int a, int b) {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
126 Object t = x[a];
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
127 x[a] = x[b];
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
128 x[b] = t;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
129 int z1 = reverse[a] != 0 ? reverse[a] : a+1;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
130 int z2 = reverse[b] != 0 ? reverse[b] : b+1;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
131 reverse[b] = z1;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
132 reverse[a] = z2;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
133 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
134 }