Mercurial > jhg

annotate src/org/tmatesoft/hg/internal/ArrayHelper.java @ 709:497e697636fc

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Report merged lines as changed block if possible, not as a sequence of added/deleted blocks. To facilitate access to merge parent lines AddBlock got mergeLineAt() method that reports index of the line in the second parent (if any), while insertedAt() has been changed to report index in the first parent always
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Wed, 21 Aug 2013 16:23:27 +0200
parents f568330dd9c0
children
rev   line source
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
1 /*
682
f568330dd9c0 Compile with Java5, ensure generics are fine for other compilers, too
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 658
diff changeset
2 * Copyright (c) 2011-2013 TMate Software Ltd
307
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
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
19 import java.util.Arrays;
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
20
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
21 /**
311
b9592e21176a Tests for array sort and reverse index building helper
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 310
diff changeset
22 * Internal alternative to Arrays.sort to build reversed index along with sorting
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
23 * and to perform lookup (binary search) without sorted array, using reversed index.
307
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 * @author Artem Tikhomirov
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
26 * @author TMate Software Ltd.
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
27 */
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
28 public final class ArrayHelper<T extends Comparable<T>> {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
29 private int[] reverse; // aka sorted2natural
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
30 private final T[] data;
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
31 private T[] sorted;
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
32
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
33 public ArrayHelper(T[] _data) {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
34 assert _data != null;
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
35 data = _data;
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
36 }
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
37
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
38 /**
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
39 * Sort data this helper wraps, possibly using supplied array (optional)
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
40 * to keep sorted elements
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
41 * @param sortDest array to keep sorted values at, or <code>null</code>
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
42 * @param sortDestIsEmpty <code>false</code> when sortDest already contains copy of data to be sorted
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
43 * @param keepSorted <code>true</code> to save sorted array for future use (e.g. in
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
44 */
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
45 public void sort(T[] sortDest, boolean sortDestIsEmpty, boolean keepSorted) {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
46 if (sortDest != null) {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
47 assert sortDest.length >= data.length;
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
48 if (sortDestIsEmpty) {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
49 System.arraycopy(data, 0, sortDest, 0, data.length);
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
50 }
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
51 sorted = sortDest;
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
52 } else {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
53 sorted = data.clone();
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
54 }
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
55 reverse = new int[data.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
56 for (int i = 0; i < reverse.length; i++) {
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
57 // initial reverse indexes, so that elements that do
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
58 // not move during sort got correct indexes
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
59 reverse[i] = i;
310
237de162be28 Fix building sort reverse array when element was initially in correct position.
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 307
diff changeset
60 }
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
61 sort1(0, data.length);
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
62 if (!keepSorted) {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
63 sorted = null;
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
64 }
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
65 }
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
66
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
67 /**
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
68 * @return all reverse indexes
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
69 */
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
70 public int[] getReverseIndexes() {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
71 return reverse;
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
72 }
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
73
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
74 public int getReverseIndex(int sortedIndex) {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
75 return reverse[sortedIndex];
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
76 }
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
77
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
78 public T get(int index) {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
79 return data[index];
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
80 }
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
81
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
82 public T[] getData() {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
83 return data;
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
84 }
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
85
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
86 /**
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
87 * Look up sorted index of the value, using sort information
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
88 * @return same value as {@link Arrays#binarySearch(Object[], Object)} does
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
89 */
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
90 public int binarySearchSorted(T value) {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
91 if (sorted != null) {
682
f568330dd9c0 Compile with Java5, ensure generics are fine for other compilers, too
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 658
diff changeset
92 int x = Arrays.binarySearch(sorted, value);
f568330dd9c0 Compile with Java5, ensure generics are fine for other compilers, too
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 658
diff changeset
93 // fulfill the Arrays#binarySearch contract in case sorted array is greater than data
f568330dd9c0 Compile with Java5, ensure generics are fine for other compilers, too
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 658
diff changeset
94 return x >= data.length ? -(data.length - 1) : x;
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
95 }
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
96 return binarySearchWithReverse(0, data.length, value);
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
97 }
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
98
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
99 /**
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
100 * Look up index of the value in the original array.
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
101 * @return index in original data, or <code>defaultValue</code> if value not found
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
102 */
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
103 public int binarySearch(T value, int defaultValue) {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
104 int x = binarySearchSorted(value);
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
105 if (x < 0) {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
106 return defaultValue;
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
107 }
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
108 return reverse[x];
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
109 }
311
b9592e21176a Tests for array sort and reverse index building helper
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 310
diff changeset
110
b9592e21176a Tests for array sort and reverse index building helper
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 310
diff changeset
111 /**
b9592e21176a Tests for array sort and reverse index building helper
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 310
diff changeset
112 * 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
113 */
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
114 private void sort1(int off, int len) {
658
d10399f80f4e javac complained about casts, while eclipse compiler is fine
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 657
diff changeset
115 Comparable<Object>[] x = comparableSorted();
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
116 // Insertion sort on smallest arrays
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
117 if (len < 7) {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
118 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
119 for (int j=i; j>off && x[j-1].compareTo(x[j]) > 0; j--)
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
120 swap(j, j-1);
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
121 return;
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
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
124 // Choose a partition element, v
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
125 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
126 if (len > 7) {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
127 int l = off;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
128 int n = off + len - 1;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
129 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
130 int s = len/8;
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
131 l = med3(l, l+s, l+2*s);
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
132 m = med3(m-s, m, m+s);
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
133 n = med3(n-2*s, n-s, n);
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
134 }
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
135 m = med3(l, m, n); // Mid-size, med of 3
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
136 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
137 Comparable<Object> v = x[m];
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 // Establish Invariant: v* (<v)* (>v)* v*
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
140 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
141 while(true) {
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
142 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
143 if (x[b] == v)
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
144 swap(a++, b);
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
145 b++;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
146 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
147 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
148 if (x[c] == v)
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
149 swap(c, d--);
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
150 c--;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
151 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
152 if (b > c)
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
153 break;
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
154 swap(b++, c--);
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
155 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
156
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
157 // Swap partition elements back to middle
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
158 int s, n = off + len;
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
159 s = Math.min(a-off, b-a ); vecswap(off, b-s, s);
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
160 s = Math.min(d-c, n-d-1); vecswap(b, n-s, s);
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
161
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
162 // Recursively sort non-partition-elements
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
163 if ((s = b-a) > 1)
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
164 sort1(off, s);
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
165 if ((s = d-c) > 1)
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
166 sort1(n-s, s);
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
167 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
168
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
169 /**
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
170 * 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
171 */
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
172 private void vecswap(int a, int b, int n) {
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
173 for (int i=0; i<n; i++, a++, b++) {
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
174 swap(a, b);
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
175 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
176 }
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
177
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
178 /**
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
179 * 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
180 */
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
181 private int med3(int a, int b, int c) {
658
d10399f80f4e javac complained about casts, while eclipse compiler is fine
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 657
diff changeset
182 Comparable<Object>[] x = comparableSorted();
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
183 return (x[a].compareTo(x[b]) < 0 ?
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
184 (x[b].compareTo(x[c]) < 0 ? b : x[a].compareTo(x[c]) < 0 ? c : a) :
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
185 (x[b].compareTo(x[c]) > 0 ? b : x[a].compareTo(x[c]) > 0 ? c : a));
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
186 }
658
d10399f80f4e javac complained about casts, while eclipse compiler is fine
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 657
diff changeset
187
d10399f80f4e javac complained about casts, while eclipse compiler is fine
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 657
diff changeset
188 private Comparable<Object>[] comparableSorted() {
d10399f80f4e javac complained about casts, while eclipse compiler is fine
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 657
diff changeset
189 // Comparable<Object>[] x = (Comparable<Object>[]) sorted
d10399f80f4e javac complained about casts, while eclipse compiler is fine
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 657
diff changeset
190 // eclipse compiler is ok with the line above, while javac doesn't understand it:
d10399f80f4e javac complained about casts, while eclipse compiler is fine
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 657
diff changeset
191 // inconvertible types found : T[] required: java.lang.Comparable<java.lang.Object>[]
d10399f80f4e javac complained about casts, while eclipse compiler is fine
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 657
diff changeset
192 // so need to add another step
d10399f80f4e javac complained about casts, while eclipse compiler is fine
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 657
diff changeset
193 Comparable<?>[] oo = sorted;
d10399f80f4e javac complained about casts, while eclipse compiler is fine
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 657
diff changeset
194 @SuppressWarnings("unchecked")
d10399f80f4e javac complained about casts, while eclipse compiler is fine
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 657
diff changeset
195 Comparable<Object>[] x = (Comparable<Object>[]) oo;
d10399f80f4e javac complained about casts, while eclipse compiler is fine
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 657
diff changeset
196 return x;
d10399f80f4e javac complained about casts, while eclipse compiler is fine
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 657
diff changeset
197 }
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
198
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
199 /**
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
200 * Swaps x[a] with x[b].
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
201 */
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
202 private void swap(int a, int b) {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
203 Object[] x = sorted;
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
204 Object t = x[a];
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
205 x[a] = x[b];
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
206 x[b] = t;
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
207 int z1 = reverse[a];
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
208 int z2 = reverse[b];
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
209 reverse[b] = z1;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
210 reverse[a] = z2;
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
211 }
657
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
212
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
213 // copied from Arrays.binarySearch0, update to be instance method and to use reverse indexes
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
214 private int binarySearchWithReverse(int fromIndex, int toIndex, T key) {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
215 int low = fromIndex;
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
216 int high = toIndex - 1;
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
217
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
218 while (low <= high) {
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
219 int mid = (low + high) >>> 1;
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
220 // data[reverse[x]] gives sorted value at index x
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
221 T midVal = data[reverse[mid]];
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
222 int cmp = midVal.compareTo(key);
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
223
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
224 if (cmp < 0)
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
225 low = mid + 1;
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
226 else if (cmp > 0)
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
227 high = mid - 1;
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
228 else
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
229 return mid; // key found
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
230 }
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
231 return -(low + 1); // key not found.
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
232 }
6334b0267103 ParentChildMap can supply RevisionMap. Refactor ArrayHelper to keep most of sorted/reverse index magic inside
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 311
diff changeset
233
307
2f2ab5c27f41 Collect sort reverse indexes along with array sorting
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
234 }