EXHIBIT E
G:\eclair21 - GOOGLE-00-00000525\dalvik\libcore\luni\src\main\java\java\util\Com
mparableTimSort.java
1 /*
2
* Copyright (C) 2008 The Android Open Source Project
3
*
4
* Licensed under the Apache License, Version 2.0 (the "License");
5
* you may not use this file except in compliance with the License.
6
* You may obtain a copy of the License at
7
*
8
*
http://www.apache.org/licenses/LICENSE-2.0
9
*
10
* Unless required by applicable law or agreed to in writing, software
11
* distributed under the License is distributed on an "AS IS" BASIS,
12
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied.
13
* See the License for the specific language governing permissions and
14
* limitations under the License.
15
*/
16
17 package java.util;
18
19 /**
20
* This is a near duplicate of {@link TimSort}, modified for use with
21
* arrays of objects that implement {@link Comparable}, instead of using
22
* explicit comparators.
23
*
24
*
If you are using an optimizing VM, you may find that
ComparableTimSort
25
* offers no performance benefit over TimSort in conjunction with a
26
* comparator that simply returns {@code
((Comparable)first).compareTo(Second)}.
27
* If this is the case, you are better off deleting ComparableTimSort to
28
* eliminate the code duplication. (See Arrays.java for details.)
29
*/
30 class ComparableTimSort {
31
/**
32
* This is the minimum sized sequence that will be merged. Shorter
33
* sequences will be lengthened by calling binarySort. If the
entire
34
* array is less than this length, no merges will be performed.
35
*
36
* This constant should be a power of two. It was 64 in Tim Peter's
C
37
* implementation, but 32 was empirically determined to work better
in
38
* this implementation. In the unlikely event that you set this
constant
39
* to be a number that's not a power of two, you'll need to change
the
40
* {@link #minRunLength} computation.
41
*
42
* If you decrease this constant, you must change the stackLen
43
* computation in the TimSort constructor, or you risk an
44
* ArrayOutOfBounds exception. See listsort.txt for a discussion
45
* of the minimum stack length required as a function of the length
46
* of the array being sorted and the minimum merge sequence length.
47
*/
48
private static final int MIN_MERGE = 32;
49
50
/**
51
* The array being sorted.
52
*/
Page 1 of 17
Trial Exhibit 45.2, Page 1 of 17
UNITED STATES DISTRICT COURT
NORTHERN DISTRICT OF CALIFORNIA
TRIAL EXHIBIT
CASE NO. 10-03561 WHA
DATE ENTERED
BY
DEPUTY CLERK
45.2
G:\eclair21 - GOOGLE-00-00000525\dalvik\libcore\luni\src\main\java\java\util\Com
mparableTimSort.java
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
private final Object[] a;
/**
* When we get into galloping mode, we stay there until both runs
win less
* often than MIN_GALLOP consecutive times.
*/
private static final int MIN_GALLOP = 7;
/**
* This controls when we get *into* galloping mode. It is
initialized
* to MIN_GALLOP. The mergeLo and mergeHi methods nudge it higher
for
* random data, and lower for highly structured data.
*/
private int minGallop = MIN_GALLOP;
/**
* Maximum initial size of tmp array, which is used for merging.
The array
* can grow to accommodate demand.
*
* Unlike Tim's original C version, we do not allocate this much
storage
* when sorting smaller arrays. This change was required for
performance.
*/
private static final int INITIAL_TMP_STORAGE_LENGTH = 256;
/**
* Temp storage for merges.
*/
private Object[] tmp;
/**
* A stack of pending runs yet to be merged. Run i starts at
* address base[i] and extends for len[i] elements. It's always
* true (so long as the indices are in bounds) that:
*
*
runBase[i] + runLen[i] == runBase[i + 1]
*
* so we could cut the storage for this, but it's a minor amount,
* and keeping all the info explicit simplifies the code.
*/
private int stackSize = 0; // Number of pending runs on stack
private final int[] runBase;
private final int[] runLen;
/**
* Asserts have been placed in if-statements for performace. To
enable them,
* set this field to true and enable them in VM with a command line
flag.
* If you modify this class, please do test the asserts!
*/
private static final boolean DEBUG = false;
/**
* Creates a TimSort instance to maintain the state of an ongoing
Page 2 of 17
Trial Exhibit 45.2, Page 2 of 17
G:\eclair21 - GOOGLE-00-00000525\dalvik\libcore\luni\src\main\java\java\util\Com
mparableTimSort.java
105
106
107
108
109
110
111
sort.
*
* @param a the array to be sorted
*/
private ComparableTimSort(Object[] a) {
this.a = a;
// Allocate temp storage (which may be increased later if
necessary)
int len = a.length;
@SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
Object[] newArray = new Object[len < 2 *
INITIAL_TMP_STORAGE_LENGTH ?
len >>> 1 :
INITIAL_TMP_STORAGE_LENGTH];
tmp = newArray;
112
113
114
115
116
117
118
119
/*
* Allocate runs-to-be-merged stack (which cannot be expanded).
The
* stack length requirements are described in listsort.txt. The
C
* version always uses the same stack length (85), but this was
* measured to be too expensive when sorting "mid-sized" arrays
(e.g.,
* 100 elements) in Java. Therefore, we use smaller (but
sufficiently
* large) stack lengths for smaller arrays. The "magic numbers"
in the
* computation below must be changed if MIN_MERGE is decreased.
See
* the MIN_MERGE declaration above for more information.
*/
int stackLen = (len <
120 ? 5 :
len <
1542 ? 10 :
len < 119151 ? 19 : 40);
runBase = new int[stackLen];
runLen = new int[stackLen];
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
}
/*
* The next two methods (which are package private and static)
constitute
* the entire API of this class. Each of these methods obeys the
contract
* of the public method with the same signature in java.util.Arrays.
*/
static void sort(Object[] a) {
sort(a, 0, a.length);
}
static void sort(Object[] a, int lo, int hi) {
rangeCheck(a.length, lo, hi);
int nRemaining = hi - lo;
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
Page 3 of 17
Trial Exhibit 45.2, Page 3 of 17
G:\eclair21 - GOOGLE-00-00000525\dalvik\libcore\luni\src\main\java\java\util\Com
mparableTimSort.java
153
154
155
156
157
158
159
int initRunLen = countRunAndMakeAscending(a, lo, hi);
binarySort(a, lo, hi, lo + initRunLen);
return;
}
/**
* March over the array once, left to right, finding natural
runs,
* extending short natural runs to minRun elements, and merging
runs
* to maintain stack invariant.
*/
ComparableTimSort ts = new ComparableTimSort(a);
int minRun = minRunLength(nRemaining);
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi);
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen);
runLen = force;
}
// Push run onto pending-run stack, and maybe merge
ts.pushRun(lo, runLen);
ts.mergeCollapse();
// Advance to find next run
lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);
// Merge all remaining runs to complete sort
if (DEBUG) assert lo == hi;
ts.mergeForceCollapse();
if (DEBUG) assert ts.stackSize == 1;
}
/**
* Sorts the specified portion of the specified array using a binary
* insertion sort. This is the best method for sorting small
numbers
* of elements. It requires O(n log n) compares, but O(n^2) data
* movement (worst case).
*
* If the initial part of the specified range is already sorted,
* this method can take advantage of it: the method assumes that the
* elements from index {@code lo}, inclusive, to {@code start},
* exclusive are already sorted.
*
* @param a the array in which a range is to be sorted
* @param lo the index of the first element in the range to be
sorted
* @param hi the index after the last element in the range to be
sorted
* @param start the index of the first element in the range that is
*
not already known to be sorted (@code lo <= start <= hi}
*/
Page 4 of 17
Trial Exhibit 45.2, Page 4 of 17
G:\eclair21 - GOOGLE-00-00000525\dalvik\libcore\luni\src\main\java\java\util\Com
mparableTimSort.java
208
209
210
211
212
213
214
215
216
217
@SuppressWarnings("fallthrough")
private static void binarySort(Object[] a, int lo, int hi, int
start) {
if (DEBUG) assert lo <= start && start <= hi;
if (start == lo)
start++;
for ( ; start < hi; start++) {
@SuppressWarnings("unchecked")
Comparable
Disclaimer: Justia Dockets & Filings provides public litigation records from the federal appellate and district courts. These filings and docket sheets should not be considered findings of fact or liability, nor do they necessarily reflect the view of Justia.