Mercurial > jhg
annotate src/org/tmatesoft/hg/internal/ArrayHelper.java @ 330:9747a786a34d
Patch merging algorithm complete trial
author | Artem Tikhomirov <tikhomirov.artem@gmail.com> |
---|---|
date | Tue, 25 Oct 2011 03:30:02 +0200 (2011-10-25) |
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 } |