Mercurial > jhg

comparison src/org/tmatesoft/hg/internal/ArrayHelper.java @ 311:b9592e21176a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Tests for array sort and reverse index building helper
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Mon, 26 Sep 2011 04:06:04 +0200
parents 237de162be28
children 6334b0267103
comparison
equal deleted inserted replaced
310:237de162be28 311:b9592e21176a
15 * contact TMate Software at support@hg4j.com 15 * contact TMate Software at support@hg4j.com
16 */ 16 */
17 package org.tmatesoft.hg.internal; 17 package org.tmatesoft.hg.internal;
18 18
19 /** 19 /**
20 * Internal alternative to Arrays.sort to build reversed index along with sorting
20 * 21 *
21 * @author Artem Tikhomirov 22 * @author Artem Tikhomirov
22 * @author TMate Software Ltd. 23 * @author TMate Software Ltd.
23 */ 24 */
24 public class ArrayHelper { 25 public class ArrayHelper {
30 reverse = new int[a.length]; 31 reverse = new int[a.length];
31 sort1((Comparable<Object>[])a, 0, a.length); 32 sort1((Comparable<Object>[])a, 0, a.length);
32 for (int i = 0; i < reverse.length; i++) { 33 for (int i = 0; i < reverse.length; i++) {
33 // element that was not moved don't have an index in reverse. 34 // element that was not moved don't have an index in reverse.
34 // perhaps, can do it inside sort alg? 35 // perhaps, can do it inside sort alg?
35 // TODO tests! 36 // Alternatively, may start with filling reverse[] array with initial indexes and
37 // avoid != 0 comparisons in #swap altogether?
36 if (reverse[i] == 0) { 38 if (reverse[i] == 0) {
37 reverse[i] = i+1; 39 reverse[i] = i+1;
38 } 40 }
39 } 41 }
40 } 42 }
41 43
44 /**
45 * Slightly modified version of Arrays.sort1(int[], int, int) quicksort alg (just to deal with Object[])
46 */
42 private void sort1(Comparable<Object> x[], int off, int len) { 47 private void sort1(Comparable<Object> x[], int off, int len) {
43 // Insertion sort on smallest arrays 48 // Insertion sort on smallest arrays
44 if (len < 7) { 49 if (len < 7) {
45 for (int i=off; i<len+off; i++) 50 for (int i=off; i<len+off; i++)
46 for (int j=i; j>off && x[j-1].compareTo(x[j]) > 0; j--) 51 for (int j=i; j>off && x[j-1].compareTo(x[j]) > 0; j--)