Mercurial > hg4j

annotate src/org/tmatesoft/hg/internal/ArrayHelper.java @ 598:d29d9dc6c128

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Utilize the fact nodeids are very different and are read anyway to speed up reverse lookup
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Fri, 03 May 2013 15:19:18 +0200
parents b9592e21176a
children 6334b0267103
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 /**
311
b9592e21176a Tests for array sort and reverse index building helper
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 310
diff changeset
20 * Internal alternative to Arrays.sort to build reversed index along with sorting
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
21 *
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
22 * @author Artem Tikhomirov
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
23 * @author TMate Software Ltd.
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
24 */
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
25 public class ArrayHelper {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
26 private int[] reverse;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
27
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
28 @SuppressWarnings("unchecked")
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
29 public void sort(Comparable<?>[] a) {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
30 // Object[] aux = (Object[]) a.clone();
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
31 reverse = new int[a.length];
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
32 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
33 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
34 // 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
35 // perhaps, can do it inside sort alg?
311
b9592e21176a Tests for array sort and reverse index building helper
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 310
diff changeset
36 // Alternatively, may start with filling reverse[] array with initial indexes and
b9592e21176a Tests for array sort and reverse index building helper
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 310
diff changeset
37 // avoid != 0 comparisons in #swap altogether?
310
237de162be28 Fix building sort reverse array when element was initially in correct position.
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 307
diff changeset
38 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
39 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
40 }
237de162be28 Fix building sort reverse array when element was initially in correct position.
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 307
diff changeset
41 }
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
42 }
311
b9592e21176a Tests for array sort and reverse index building helper
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 310
diff changeset
43
b9592e21176a Tests for array sort and reverse index building helper
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 310
diff changeset
44 /**
b9592e21176a Tests for array sort and reverse index building helper
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 310
diff changeset
45 * Slightly modified version of Arrays.sort1(int[], int, int) quicksort alg (just to deal with Object[])
b9592e21176a Tests for array sort and reverse index building helper
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 310
diff changeset
46 */
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
47 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
48 // Insertion sort on smallest arrays
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
49 if (len < 7) {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
50 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
51 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
52 swap(x, j, j-1);
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
53 return;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
54 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
55
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
56 // Choose a partition element, v
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
57 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
58 if (len > 7) {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
59 int l = off;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
60 int n = off + len - 1;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
61 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
62 int s = len/8;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
63 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
64 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
65 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
66 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
67 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
68 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
69 Comparable<Object> v = x[m];
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
70
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
71 // Establish Invariant: v* (<v)* (>v)* v*
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
72 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
73 while(true) {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
74 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
75 if (x[b] == v)
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
76 swap(x, a++, b);
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
77 b++;
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 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
80 if (x[c] == v)
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
81 swap(x, c, d--);
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
82 c--;
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 if (b > c)
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
85 break;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
86 swap(x, b++, c--);
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
87 }
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 // Swap partition elements back to middle
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
90 int s, n = off + len;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
91 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
92 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
93
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
94 // Recursively sort non-partition-elements
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
95 if ((s = b-a) > 1)
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
96 sort1(x, off, s);
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
97 if ((s = d-c) > 1)
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
98 sort1(x, n-s, s);
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
99 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
100
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
101 /**
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
102 * 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
103 */
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
104 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
105 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
106 swap(x, a, b);
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 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
109
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
110 /**
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
111 * 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
112 */
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
113 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
114 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
115 (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
116 (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
117 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
118
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
119
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 * @return the reverse
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 public int[] getReverse() {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
124 return reverse;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
125 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
126
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
127 /**
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
128 * Swaps x[a] with x[b].
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
129 */
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
130 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
131 Object t = x[a];
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
132 x[a] = x[b];
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
133 x[b] = t;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
134 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
135 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
136 reverse[b] = z1;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
137 reverse[a] = z2;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
138 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
139 }