|
||||
0001 /* 0002 * Licensed to the Apache Software Foundation (ASF) under one or more 0003 * contributor license agreements. See the NOTICE file distributed with 0004 * this work for additional information regarding copyright ownership. 0005 * The ASF licenses this file to You under the Apache License, Version 2.0 0006 * (the "License"); you may not use this file except in compliance with 0007 * the License. You may obtain a copy of the License at 0008 * 0009 * http://www.apache.org/licenses/LICENSE-2.0 0010 * 0011 * Unless required by applicable law or agreed to in writing, software 0012 * distributed under the License is distributed on an "AS IS" BASIS, 0013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 0014 * See the License for the specific language governing permissions and 0015 * limitations under the License. 0016 */ 0017 0018 /* 0019 * Based on TimSort.java from the Android Open Source Project 0020 * 0021 * Copyright (C) 2008 The Android Open Source Project 0022 * 0023 * Licensed under the Apache License, Version 2.0 (the "License"); 0024 * you may not use this file except in compliance with the License. 0025 * You may obtain a copy of the License at 0026 * 0027 * http://www.apache.org/licenses/LICENSE-2.0 0028 * 0029 * Unless required by applicable law or agreed to in writing, software 0030 * distributed under the License is distributed on an "AS IS" BASIS, 0031 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 0032 * See the License for the specific language governing permissions and 0033 * limitations under the License. 0034 */ 0035 0036 package org.apache.spark.util.collection; 0037 0038 import java.util.Comparator; 0039 0040 /** 0041 * A port of the Android TimSort class, which utilizes a "stable, adaptive, iterative mergesort." 0042 * See the method comment on sort() for more details. 0043 * 0044 * This has been kept in Java with the original style in order to match very closely with the 0045 * Android source code, and thus be easy to verify correctness. The class is package private. We put 0046 * a simple Scala wrapper {@link org.apache.spark.util.collection.Sorter}, which is available to 0047 * package org.apache.spark. 0048 * 0049 * The purpose of the port is to generalize the interface to the sort to accept input data formats 0050 * besides simple arrays where every element is sorted individually. For instance, the AppendOnlyMap 0051 * uses this to sort an Array with alternating elements of the form [key, value, key, value]. 0052 * This generalization comes with minimal overhead -- see SortDataFormat for more information. 0053 * 0054 * We allow key reuse to prevent creating many key objects -- see SortDataFormat. 0055 * 0056 * @see org.apache.spark.util.collection.SortDataFormat 0057 * @see org.apache.spark.util.collection.Sorter 0058 */ 0059 class TimSort<K, Buffer> { 0060 0061 /** 0062 * This is the minimum sized sequence that will be merged. Shorter 0063 * sequences will be lengthened by calling binarySort. If the entire 0064 * array is less than this length, no merges will be performed. 0065 * 0066 * This constant should be a power of two. It was 64 in Tim Peter's C 0067 * implementation, but 32 was empirically determined to work better in 0068 * this implementation. In the unlikely event that you set this constant 0069 * to be a number that's not a power of two, you'll need to change the 0070 * minRunLength computation. 0071 * 0072 * If you decrease this constant, you must change the stackLen 0073 * computation in the TimSort constructor, or you risk an 0074 * ArrayOutOfBounds exception. See listsort.txt for a discussion 0075 * of the minimum stack length required as a function of the length 0076 * of the array being sorted and the minimum merge sequence length. 0077 */ 0078 private static final int MIN_MERGE = 32; 0079 0080 private final SortDataFormat<K, Buffer> s; 0081 0082 public TimSort(SortDataFormat<K, Buffer> sortDataFormat) { 0083 this.s = sortDataFormat; 0084 } 0085 0086 /** 0087 * A stable, adaptive, iterative mergesort that requires far fewer than 0088 * n lg(n) comparisons when running on partially sorted arrays, while 0089 * offering performance comparable to a traditional mergesort when run 0090 * on random arrays. Like all proper mergesorts, this sort is stable and 0091 * runs O(n log n) time (worst case). In the worst case, this sort requires 0092 * temporary storage space for n/2 object references; in the best case, 0093 * it requires only a small constant amount of space. 0094 * 0095 * This implementation was adapted from Tim Peters's list sort for 0096 * Python, which is described in detail here: 0097 * 0098 * http://svn.python.org/projects/python/trunk/Objects/listsort.txt 0099 * 0100 * Tim's C code may be found here: 0101 * 0102 * http://svn.python.org/projects/python/trunk/Objects/listobject.c 0103 * 0104 * The underlying techniques are described in this paper (and may have 0105 * even earlier origins): 0106 * 0107 * "Optimistic Sorting and Information Theoretic Complexity" 0108 * Peter McIlroy 0109 * SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), 0110 * pp 467-474, Austin, Texas, 25-27 January 1993. 0111 * 0112 * While the API to this class consists solely of static methods, it is 0113 * (privately) instantiable; a TimSort instance holds the state of an ongoing 0114 * sort, assuming the input array is large enough to warrant the full-blown 0115 * TimSort. Small arrays are sorted in place, using a binary insertion sort. 0116 * 0117 * @author Josh Bloch 0118 */ 0119 public void sort(Buffer a, int lo, int hi, Comparator<? super K> c) { 0120 assert c != null; 0121 0122 int nRemaining = hi - lo; 0123 if (nRemaining < 2) 0124 return; // Arrays of size 0 and 1 are always sorted 0125 0126 // If array is small, do a "mini-TimSort" with no merges 0127 if (nRemaining < MIN_MERGE) { 0128 int initRunLen = countRunAndMakeAscending(a, lo, hi, c); 0129 binarySort(a, lo, hi, lo + initRunLen, c); 0130 return; 0131 } 0132 0133 /** 0134 * March over the array once, left to right, finding natural runs, 0135 * extending short natural runs to minRun elements, and merging runs 0136 * to maintain stack invariant. 0137 */ 0138 SortState sortState = new SortState(a, c, hi - lo); 0139 int minRun = minRunLength(nRemaining); 0140 do { 0141 // Identify next run 0142 int runLen = countRunAndMakeAscending(a, lo, hi, c); 0143 0144 // If run is short, extend to min(minRun, nRemaining) 0145 if (runLen < minRun) { 0146 int force = nRemaining <= minRun ? nRemaining : minRun; 0147 binarySort(a, lo, lo + force, lo + runLen, c); 0148 runLen = force; 0149 } 0150 0151 // Push run onto pending-run stack, and maybe merge 0152 sortState.pushRun(lo, runLen); 0153 sortState.mergeCollapse(); 0154 0155 // Advance to find next run 0156 lo += runLen; 0157 nRemaining -= runLen; 0158 } while (nRemaining != 0); 0159 0160 // Merge all remaining runs to complete sort 0161 assert lo == hi; 0162 sortState.mergeForceCollapse(); 0163 assert sortState.stackSize == 1; 0164 } 0165 0166 /** 0167 * Sorts the specified portion of the specified array using a binary 0168 * insertion sort. This is the best method for sorting small numbers 0169 * of elements. It requires O(n log n) compares, but O(n^2) data 0170 * movement (worst case). 0171 * 0172 * If the initial part of the specified range is already sorted, 0173 * this method can take advantage of it: the method assumes that the 0174 * elements from index {@code lo}, inclusive, to {@code start}, 0175 * exclusive are already sorted. 0176 * 0177 * @param a the array in which a range is to be sorted 0178 * @param lo the index of the first element in the range to be sorted 0179 * @param hi the index after the last element in the range to be sorted 0180 * @param start the index of the first element in the range that is 0181 * not already known to be sorted ({@code lo <= start <= hi}) 0182 * @param c comparator to used for the sort 0183 */ 0184 @SuppressWarnings("fallthrough") 0185 private void binarySort(Buffer a, int lo, int hi, int start, Comparator<? super K> c) { 0186 assert lo <= start && start <= hi; 0187 if (start == lo) 0188 start++; 0189 0190 K key0 = s.newKey(); 0191 K key1 = s.newKey(); 0192 0193 Buffer pivotStore = s.allocate(1); 0194 for ( ; start < hi; start++) { 0195 s.copyElement(a, start, pivotStore, 0); 0196 K pivot = s.getKey(pivotStore, 0, key0); 0197 0198 // Set left (and right) to the index where a[start] (pivot) belongs 0199 int left = lo; 0200 int right = start; 0201 assert left <= right; 0202 /* 0203 * Invariants: 0204 * pivot >= all in [lo, left). 0205 * pivot < all in [right, start). 0206 */ 0207 while (left < right) { 0208 int mid = (left + right) >>> 1; 0209 if (c.compare(pivot, s.getKey(a, mid, key1)) < 0) 0210 right = mid; 0211 else 0212 left = mid + 1; 0213 } 0214 assert left == right; 0215 0216 /* 0217 * The invariants still hold: pivot >= all in [lo, left) and 0218 * pivot < all in [left, start), so pivot belongs at left. Note 0219 * that if there are elements equal to pivot, left points to the 0220 * first slot after them -- that's why this sort is stable. 0221 * Slide elements over to make room for pivot. 0222 */ 0223 int n = start - left; // The number of elements to move 0224 // Switch is just an optimization for arraycopy in default case 0225 switch (n) { 0226 case 2: s.copyElement(a, left + 1, a, left + 2); 0227 case 1: s.copyElement(a, left, a, left + 1); 0228 break; 0229 default: s.copyRange(a, left, a, left + 1, n); 0230 } 0231 s.copyElement(pivotStore, 0, a, left); 0232 } 0233 } 0234 0235 /** 0236 * Returns the length of the run beginning at the specified position in 0237 * the specified array and reverses the run if it is descending (ensuring 0238 * that the run will always be ascending when the method returns). 0239 * 0240 * A run is the longest ascending sequence with: 0241 * 0242 * a[lo] <= a[lo + 1] <= a[lo + 2] <= ... 0243 * 0244 * or the longest descending sequence with: 0245 * 0246 * a[lo] > a[lo + 1] > a[lo + 2] > ... 0247 * 0248 * For its intended use in a stable mergesort, the strictness of the 0249 * definition of "descending" is needed so that the call can safely 0250 * reverse a descending sequence without violating stability. 0251 * 0252 * @param a the array in which a run is to be counted and possibly reversed 0253 * @param lo index of the first element in the run 0254 * @param hi index after the last element that may be contained in the run. 0255 It is required that {@code lo < hi}. 0256 * @param c the comparator to used for the sort 0257 * @return the length of the run beginning at the specified position in 0258 * the specified array 0259 */ 0260 private int countRunAndMakeAscending(Buffer a, int lo, int hi, Comparator<? super K> c) { 0261 assert lo < hi; 0262 int runHi = lo + 1; 0263 if (runHi == hi) 0264 return 1; 0265 0266 K key0 = s.newKey(); 0267 K key1 = s.newKey(); 0268 0269 // Find end of run, and reverse range if descending 0270 if (c.compare(s.getKey(a, runHi++, key0), s.getKey(a, lo, key1)) < 0) { // Descending 0271 while (runHi < hi && c.compare(s.getKey(a, runHi, key0), s.getKey(a, runHi - 1, key1)) < 0) 0272 runHi++; 0273 reverseRange(a, lo, runHi); 0274 } else { // Ascending 0275 while (runHi < hi && c.compare(s.getKey(a, runHi, key0), s.getKey(a, runHi - 1, key1)) >= 0) 0276 runHi++; 0277 } 0278 0279 return runHi - lo; 0280 } 0281 0282 /** 0283 * Reverse the specified range of the specified array. 0284 * 0285 * @param a the array in which a range is to be reversed 0286 * @param lo the index of the first element in the range to be reversed 0287 * @param hi the index after the last element in the range to be reversed 0288 */ 0289 private void reverseRange(Buffer a, int lo, int hi) { 0290 hi--; 0291 while (lo < hi) { 0292 s.swap(a, lo, hi); 0293 lo++; 0294 hi--; 0295 } 0296 } 0297 0298 /** 0299 * Returns the minimum acceptable run length for an array of the specified 0300 * length. Natural runs shorter than this will be extended with 0301 * {@link #binarySort}. 0302 * 0303 * Roughly speaking, the computation is: 0304 * 0305 * If n < MIN_MERGE, return n (it's too small to bother with fancy stuff). 0306 * Else if n is an exact power of 2, return MIN_MERGE/2. 0307 * Else return an int k, MIN_MERGE/2 <= k <= MIN_MERGE, such that n/k 0308 * is close to, but strictly less than, an exact power of 2. 0309 * 0310 * For the rationale, see listsort.txt. 0311 * 0312 * @param n the length of the array to be sorted 0313 * @return the length of the minimum run to be merged 0314 */ 0315 private int minRunLength(int n) { 0316 assert n >= 0; 0317 int r = 0; // Becomes 1 if any 1 bits are shifted off 0318 while (n >= MIN_MERGE) { 0319 r |= (n & 1); 0320 n >>= 1; 0321 } 0322 return n + r; 0323 } 0324 0325 private class SortState { 0326 0327 /** 0328 * The Buffer being sorted. 0329 */ 0330 private final Buffer a; 0331 0332 /** 0333 * Length of the sort Buffer. 0334 */ 0335 private final int aLength; 0336 0337 /** 0338 * The comparator for this sort. 0339 */ 0340 private final Comparator<? super K> c; 0341 0342 /** 0343 * When we get into galloping mode, we stay there until both runs win less 0344 * often than MIN_GALLOP consecutive times. 0345 */ 0346 private static final int MIN_GALLOP = 7; 0347 0348 /** 0349 * This controls when we get *into* galloping mode. It is initialized 0350 * to MIN_GALLOP. The mergeLo and mergeHi methods nudge it higher for 0351 * random data, and lower for highly structured data. 0352 */ 0353 private int minGallop = MIN_GALLOP; 0354 0355 /** 0356 * Maximum initial size of tmp array, which is used for merging. The array 0357 * can grow to accommodate demand. 0358 * 0359 * Unlike Tim's original C version, we do not allocate this much storage 0360 * when sorting smaller arrays. This change was required for performance. 0361 */ 0362 private static final int INITIAL_TMP_STORAGE_LENGTH = 256; 0363 0364 /** 0365 * Temp storage for merges. 0366 */ 0367 private Buffer tmp; // Actual runtime type will be Object[], regardless of T 0368 0369 /** 0370 * Length of the temp storage. 0371 */ 0372 private int tmpLength = 0; 0373 0374 /** 0375 * A stack of pending runs yet to be merged. Run i starts at 0376 * address base[i] and extends for len[i] elements. It's always 0377 * true (so long as the indices are in bounds) that: 0378 * 0379 * runBase[i] + runLen[i] == runBase[i + 1] 0380 * 0381 * so we could cut the storage for this, but it's a minor amount, 0382 * and keeping all the info explicit simplifies the code. 0383 */ 0384 private int stackSize = 0; // Number of pending runs on stack 0385 private final int[] runBase; 0386 private final int[] runLen; 0387 0388 /** 0389 * Creates a TimSort instance to maintain the state of an ongoing sort. 0390 * 0391 * @param a the array to be sorted 0392 * @param c the comparator to determine the order of the sort 0393 */ 0394 private SortState(Buffer a, Comparator<? super K> c, int len) { 0395 this.aLength = len; 0396 this.a = a; 0397 this.c = c; 0398 0399 // Allocate temp storage (which may be increased later if necessary) 0400 tmpLength = len < 2 * INITIAL_TMP_STORAGE_LENGTH ? len >>> 1 : INITIAL_TMP_STORAGE_LENGTH; 0401 tmp = s.allocate(tmpLength); 0402 0403 /* 0404 * Allocate runs-to-be-merged stack (which cannot be expanded). The 0405 * stack length requirements are described in listsort.txt. The C 0406 * version always uses the same stack length (85), but this was 0407 * measured to be too expensive when sorting "mid-sized" arrays (e.g., 0408 * 100 elements) in Java. Therefore, we use smaller (but sufficiently 0409 * large) stack lengths for smaller arrays. The "magic numbers" in the 0410 * computation below must be changed if MIN_MERGE is decreased. See 0411 * the MIN_MERGE declaration above for more information. 0412 * The maximum value of 49 allows for an array up to length 0413 * Integer.MAX_VALUE-4, if array is filled by the worst case stack size 0414 * increasing scenario. More explanations are given in section 4 of: 0415 * http://envisage-project.eu/wp-content/uploads/2015/02/sorting.pdf 0416 */ 0417 int stackLen = (len < 120 ? 5 : 0418 len < 1542 ? 10 : 0419 len < 119151 ? 24 : 49); 0420 runBase = new int[stackLen]; 0421 runLen = new int[stackLen]; 0422 } 0423 0424 /** 0425 * Pushes the specified run onto the pending-run stack. 0426 * 0427 * @param runBase index of the first element in the run 0428 * @param runLen the number of elements in the run 0429 */ 0430 private void pushRun(int runBase, int runLen) { 0431 this.runBase[stackSize] = runBase; 0432 this.runLen[stackSize] = runLen; 0433 stackSize++; 0434 } 0435 0436 /** 0437 * Examines the stack of runs waiting to be merged and merges adjacent runs 0438 * until the stack invariants are reestablished: 0439 * 0440 * 1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1] 0441 * 2. runLen[i - 2] > runLen[i - 1] 0442 * 0443 * This method is called each time a new run is pushed onto the stack, 0444 * so the invariants are guaranteed to hold for i < stackSize upon 0445 * entry to the method. 0446 * 0447 * Thanks to Stijn de Gouw, Jurriaan Rot, Frank S. de Boer, 0448 * Richard Bubel and Reiner Hahnle, this is fixed with respect to 0449 * the analysis in "On the Worst-Case Complexity of TimSort" by 0450 * Nicolas Auger, Vincent Jug, Cyril Nicaud, and Carine Pivoteau. 0451 */ 0452 private void mergeCollapse() { 0453 while (stackSize > 1) { 0454 int n = stackSize - 2; 0455 if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1] || 0456 n > 1 && runLen[n-2] <= runLen[n] + runLen[n-1]) { 0457 if (runLen[n - 1] < runLen[n + 1]) 0458 n--; 0459 } else if (n < 0 || runLen[n] > runLen[n + 1]) { 0460 break; // Invariant is established 0461 } 0462 mergeAt(n); 0463 } 0464 } 0465 0466 /** 0467 * Merges all runs on the stack until only one remains. This method is 0468 * called once, to complete the sort. 0469 */ 0470 private void mergeForceCollapse() { 0471 while (stackSize > 1) { 0472 int n = stackSize - 2; 0473 if (n > 0 && runLen[n - 1] < runLen[n + 1]) 0474 n--; 0475 mergeAt(n); 0476 } 0477 } 0478 0479 /** 0480 * Merges the two runs at stack indices i and i+1. Run i must be 0481 * the penultimate or antepenultimate run on the stack. In other words, 0482 * i must be equal to stackSize-2 or stackSize-3. 0483 * 0484 * @param i stack index of the first of the two runs to merge 0485 */ 0486 private void mergeAt(int i) { 0487 assert stackSize >= 2; 0488 assert i >= 0; 0489 assert i == stackSize - 2 || i == stackSize - 3; 0490 0491 int base1 = runBase[i]; 0492 int len1 = runLen[i]; 0493 int base2 = runBase[i + 1]; 0494 int len2 = runLen[i + 1]; 0495 assert len1 > 0 && len2 > 0; 0496 assert base1 + len1 == base2; 0497 0498 /* 0499 * Record the length of the combined runs; if i is the 3rd-last 0500 * run now, also slide over the last run (which isn't involved 0501 * in this merge). The current run (i+1) goes away in any case. 0502 */ 0503 runLen[i] = len1 + len2; 0504 if (i == stackSize - 3) { 0505 runBase[i + 1] = runBase[i + 2]; 0506 runLen[i + 1] = runLen[i + 2]; 0507 } 0508 stackSize--; 0509 0510 K key0 = s.newKey(); 0511 0512 /* 0513 * Find where the first element of run2 goes in run1. Prior elements 0514 * in run1 can be ignored (because they're already in place). 0515 */ 0516 int k = gallopRight(s.getKey(a, base2, key0), a, base1, len1, 0, c); 0517 assert k >= 0; 0518 base1 += k; 0519 len1 -= k; 0520 if (len1 == 0) 0521 return; 0522 0523 /* 0524 * Find where the last element of run1 goes in run2. Subsequent elements 0525 * in run2 can be ignored (because they're already in place). 0526 */ 0527 len2 = gallopLeft(s.getKey(a, base1 + len1 - 1, key0), a, base2, len2, len2 - 1, c); 0528 assert len2 >= 0; 0529 if (len2 == 0) 0530 return; 0531 0532 // Merge remaining runs, using tmp array with min(len1, len2) elements 0533 if (len1 <= len2) 0534 mergeLo(base1, len1, base2, len2); 0535 else 0536 mergeHi(base1, len1, base2, len2); 0537 } 0538 0539 /** 0540 * Locates the position at which to insert the specified key into the 0541 * specified sorted range; if the range contains an element equal to key, 0542 * returns the index of the leftmost equal element. 0543 * 0544 * @param key the key whose insertion point to search for 0545 * @param a the array in which to search 0546 * @param base the index of the first element in the range 0547 * @param len the length of the range; must be > 0 0548 * @param hint the index at which to begin the search, 0 <= hint < n. 0549 * The closer hint is to the result, the faster this method will run. 0550 * @param c the comparator used to order the range, and to search 0551 * @return the int k, 0 <= k <= n such that a[b + k - 1] < key <= a[b + k], 0552 * pretending that a[b - 1] is minus infinity and a[b + n] is infinity. 0553 * In other words, key belongs at index b + k; or in other words, 0554 * the first k elements of a should precede key, and the last n - k 0555 * should follow it. 0556 */ 0557 private int gallopLeft(K key, Buffer a, int base, int len, int hint, Comparator<? super K> c) { 0558 assert len > 0 && hint >= 0 && hint < len; 0559 int lastOfs = 0; 0560 int ofs = 1; 0561 K key0 = s.newKey(); 0562 0563 if (c.compare(key, s.getKey(a, base + hint, key0)) > 0) { 0564 // Gallop right until a[base+hint+lastOfs] < key <= a[base+hint+ofs] 0565 int maxOfs = len - hint; 0566 while (ofs < maxOfs && c.compare(key, s.getKey(a, base + hint + ofs, key0)) > 0) { 0567 lastOfs = ofs; 0568 ofs = (ofs << 1) + 1; 0569 if (ofs <= 0) // int overflow 0570 ofs = maxOfs; 0571 } 0572 if (ofs > maxOfs) 0573 ofs = maxOfs; 0574 0575 // Make offsets relative to base 0576 lastOfs += hint; 0577 ofs += hint; 0578 } else { // key <= a[base + hint] 0579 // Gallop left until a[base+hint-ofs] < key <= a[base+hint-lastOfs] 0580 final int maxOfs = hint + 1; 0581 while (ofs < maxOfs && c.compare(key, s.getKey(a, base + hint - ofs, key0)) <= 0) { 0582 lastOfs = ofs; 0583 ofs = (ofs << 1) + 1; 0584 if (ofs <= 0) // int overflow 0585 ofs = maxOfs; 0586 } 0587 if (ofs > maxOfs) 0588 ofs = maxOfs; 0589 0590 // Make offsets relative to base 0591 int tmp = lastOfs; 0592 lastOfs = hint - ofs; 0593 ofs = hint - tmp; 0594 } 0595 assert -1 <= lastOfs && lastOfs < ofs && ofs <= len; 0596 0597 /* 0598 * Now a[base+lastOfs] < key <= a[base+ofs], so key belongs somewhere 0599 * to the right of lastOfs but no farther right than ofs. Do a binary 0600 * search, with invariant a[base + lastOfs - 1] < key <= a[base + ofs]. 0601 */ 0602 lastOfs++; 0603 while (lastOfs < ofs) { 0604 int m = lastOfs + ((ofs - lastOfs) >>> 1); 0605 0606 if (c.compare(key, s.getKey(a, base + m, key0)) > 0) 0607 lastOfs = m + 1; // a[base + m] < key 0608 else 0609 ofs = m; // key <= a[base + m] 0610 } 0611 assert lastOfs == ofs; // so a[base + ofs - 1] < key <= a[base + ofs] 0612 return ofs; 0613 } 0614 0615 /** 0616 * Like gallopLeft, except that if the range contains an element equal to 0617 * key, gallopRight returns the index after the rightmost equal element. 0618 * 0619 * @param key the key whose insertion point to search for 0620 * @param a the array in which to search 0621 * @param base the index of the first element in the range 0622 * @param len the length of the range; must be > 0 0623 * @param hint the index at which to begin the search, 0 <= hint < n. 0624 * The closer hint is to the result, the faster this method will run. 0625 * @param c the comparator used to order the range, and to search 0626 * @return the int k, 0 <= k <= n such that a[b + k - 1] <= key < a[b + k] 0627 */ 0628 private int gallopRight(K key, Buffer a, int base, int len, int hint, Comparator<? super K> c) { 0629 assert len > 0 && hint >= 0 && hint < len; 0630 0631 int ofs = 1; 0632 int lastOfs = 0; 0633 K key1 = s.newKey(); 0634 0635 if (c.compare(key, s.getKey(a, base + hint, key1)) < 0) { 0636 // Gallop left until a[b+hint - ofs] <= key < a[b+hint - lastOfs] 0637 int maxOfs = hint + 1; 0638 while (ofs < maxOfs && c.compare(key, s.getKey(a, base + hint - ofs, key1)) < 0) { 0639 lastOfs = ofs; 0640 ofs = (ofs << 1) + 1; 0641 if (ofs <= 0) // int overflow 0642 ofs = maxOfs; 0643 } 0644 if (ofs > maxOfs) 0645 ofs = maxOfs; 0646 0647 // Make offsets relative to b 0648 int tmp = lastOfs; 0649 lastOfs = hint - ofs; 0650 ofs = hint - tmp; 0651 } else { // a[b + hint] <= key 0652 // Gallop right until a[b+hint + lastOfs] <= key < a[b+hint + ofs] 0653 int maxOfs = len - hint; 0654 while (ofs < maxOfs && c.compare(key, s.getKey(a, base + hint + ofs, key1)) >= 0) { 0655 lastOfs = ofs; 0656 ofs = (ofs << 1) + 1; 0657 if (ofs <= 0) // int overflow 0658 ofs = maxOfs; 0659 } 0660 if (ofs > maxOfs) 0661 ofs = maxOfs; 0662 0663 // Make offsets relative to b 0664 lastOfs += hint; 0665 ofs += hint; 0666 } 0667 assert -1 <= lastOfs && lastOfs < ofs && ofs <= len; 0668 0669 /* 0670 * Now a[b + lastOfs] <= key < a[b + ofs], so key belongs somewhere to 0671 * the right of lastOfs but no farther right than ofs. Do a binary 0672 * search, with invariant a[b + lastOfs - 1] <= key < a[b + ofs]. 0673 */ 0674 lastOfs++; 0675 while (lastOfs < ofs) { 0676 int m = lastOfs + ((ofs - lastOfs) >>> 1); 0677 0678 if (c.compare(key, s.getKey(a, base + m, key1)) < 0) 0679 ofs = m; // key < a[b + m] 0680 else 0681 lastOfs = m + 1; // a[b + m] <= key 0682 } 0683 assert lastOfs == ofs; // so a[b + ofs - 1] <= key < a[b + ofs] 0684 return ofs; 0685 } 0686 0687 /** 0688 * Merges two adjacent runs in place, in a stable fashion. The first 0689 * element of the first run must be greater than the first element of the 0690 * second run (a[base1] > a[base2]), and the last element of the first run 0691 * (a[base1 + len1-1]) must be greater than all elements of the second run. 0692 * 0693 * For performance, this method should be called only when len1 <= len2; 0694 * its twin, mergeHi should be called if len1 >= len2. (Either method 0695 * may be called if len1 == len2.) 0696 * 0697 * @param base1 index of first element in first run to be merged 0698 * @param len1 length of first run to be merged (must be > 0) 0699 * @param base2 index of first element in second run to be merged 0700 * (must be aBase + aLen) 0701 * @param len2 length of second run to be merged (must be > 0) 0702 */ 0703 private void mergeLo(int base1, int len1, int base2, int len2) { 0704 assert len1 > 0 && len2 > 0 && base1 + len1 == base2; 0705 0706 // Copy first run into temp array 0707 Buffer a = this.a; // For performance 0708 Buffer tmp = ensureCapacity(len1); 0709 s.copyRange(a, base1, tmp, 0, len1); 0710 0711 int cursor1 = 0; // Indexes into tmp array 0712 int cursor2 = base2; // Indexes int a 0713 int dest = base1; // Indexes int a 0714 0715 // Move first element of second run and deal with degenerate cases 0716 s.copyElement(a, cursor2++, a, dest++); 0717 if (--len2 == 0) { 0718 s.copyRange(tmp, cursor1, a, dest, len1); 0719 return; 0720 } 0721 if (len1 == 1) { 0722 s.copyRange(a, cursor2, a, dest, len2); 0723 s.copyElement(tmp, cursor1, a, dest + len2); // Last elt of run 1 to end of merge 0724 return; 0725 } 0726 0727 K key0 = s.newKey(); 0728 K key1 = s.newKey(); 0729 0730 Comparator<? super K> c = this.c; // Use local variable for performance 0731 int minGallop = this.minGallop; // " " " " " 0732 outer: 0733 while (true) { 0734 int count1 = 0; // Number of times in a row that first run won 0735 int count2 = 0; // Number of times in a row that second run won 0736 0737 /* 0738 * Do the straightforward thing until (if ever) one run starts 0739 * winning consistently. 0740 */ 0741 do { 0742 assert len1 > 1 && len2 > 0; 0743 if (c.compare(s.getKey(a, cursor2, key0), s.getKey(tmp, cursor1, key1)) < 0) { 0744 s.copyElement(a, cursor2++, a, dest++); 0745 count2++; 0746 count1 = 0; 0747 if (--len2 == 0) 0748 break outer; 0749 } else { 0750 s.copyElement(tmp, cursor1++, a, dest++); 0751 count1++; 0752 count2 = 0; 0753 if (--len1 == 1) 0754 break outer; 0755 } 0756 } while ((count1 | count2) < minGallop); 0757 0758 /* 0759 * One run is winning so consistently that galloping may be a 0760 * huge win. So try that, and continue galloping until (if ever) 0761 * neither run appears to be winning consistently anymore. 0762 */ 0763 do { 0764 assert len1 > 1 && len2 > 0; 0765 count1 = gallopRight(s.getKey(a, cursor2, key0), tmp, cursor1, len1, 0, c); 0766 if (count1 != 0) { 0767 s.copyRange(tmp, cursor1, a, dest, count1); 0768 dest += count1; 0769 cursor1 += count1; 0770 len1 -= count1; 0771 if (len1 <= 1) // len1 == 1 || len1 == 0 0772 break outer; 0773 } 0774 s.copyElement(a, cursor2++, a, dest++); 0775 if (--len2 == 0) 0776 break outer; 0777 0778 count2 = gallopLeft(s.getKey(tmp, cursor1, key0), a, cursor2, len2, 0, c); 0779 if (count2 != 0) { 0780 s.copyRange(a, cursor2, a, dest, count2); 0781 dest += count2; 0782 cursor2 += count2; 0783 len2 -= count2; 0784 if (len2 == 0) 0785 break outer; 0786 } 0787 s.copyElement(tmp, cursor1++, a, dest++); 0788 if (--len1 == 1) 0789 break outer; 0790 minGallop--; 0791 } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP); 0792 if (minGallop < 0) 0793 minGallop = 0; 0794 minGallop += 2; // Penalize for leaving gallop mode 0795 } // End of "outer" loop 0796 this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field 0797 0798 if (len1 == 1) { 0799 assert len2 > 0; 0800 s.copyRange(a, cursor2, a, dest, len2); 0801 s.copyElement(tmp, cursor1, a, dest + len2); // Last elt of run 1 to end of merge 0802 } else if (len1 == 0) { 0803 throw new IllegalArgumentException( 0804 "Comparison method violates its general contract!"); 0805 } else { 0806 assert len2 == 0; 0807 assert len1 > 1; 0808 s.copyRange(tmp, cursor1, a, dest, len1); 0809 } 0810 } 0811 0812 /** 0813 * Like mergeLo, except that this method should be called only if 0814 * len1 >= len2; mergeLo should be called if len1 <= len2. (Either method 0815 * may be called if len1 == len2.) 0816 * 0817 * @param base1 index of first element in first run to be merged 0818 * @param len1 length of first run to be merged (must be > 0) 0819 * @param base2 index of first element in second run to be merged 0820 * (must be aBase + aLen) 0821 * @param len2 length of second run to be merged (must be > 0) 0822 */ 0823 private void mergeHi(int base1, int len1, int base2, int len2) { 0824 assert len1 > 0 && len2 > 0 && base1 + len1 == base2; 0825 0826 // Copy second run into temp array 0827 Buffer a = this.a; // For performance 0828 Buffer tmp = ensureCapacity(len2); 0829 s.copyRange(a, base2, tmp, 0, len2); 0830 0831 int cursor1 = base1 + len1 - 1; // Indexes into a 0832 int cursor2 = len2 - 1; // Indexes into tmp array 0833 int dest = base2 + len2 - 1; // Indexes into a 0834 0835 K key0 = s.newKey(); 0836 K key1 = s.newKey(); 0837 0838 // Move last element of first run and deal with degenerate cases 0839 s.copyElement(a, cursor1--, a, dest--); 0840 if (--len1 == 0) { 0841 s.copyRange(tmp, 0, a, dest - (len2 - 1), len2); 0842 return; 0843 } 0844 if (len2 == 1) { 0845 dest -= len1; 0846 cursor1 -= len1; 0847 s.copyRange(a, cursor1 + 1, a, dest + 1, len1); 0848 s.copyElement(tmp, cursor2, a, dest); 0849 return; 0850 } 0851 0852 Comparator<? super K> c = this.c; // Use local variable for performance 0853 int minGallop = this.minGallop; // " " " " " 0854 outer: 0855 while (true) { 0856 int count1 = 0; // Number of times in a row that first run won 0857 int count2 = 0; // Number of times in a row that second run won 0858 0859 /* 0860 * Do the straightforward thing until (if ever) one run 0861 * appears to win consistently. 0862 */ 0863 do { 0864 assert len1 > 0 && len2 > 1; 0865 if (c.compare(s.getKey(tmp, cursor2, key0), s.getKey(a, cursor1, key1)) < 0) { 0866 s.copyElement(a, cursor1--, a, dest--); 0867 count1++; 0868 count2 = 0; 0869 if (--len1 == 0) 0870 break outer; 0871 } else { 0872 s.copyElement(tmp, cursor2--, a, dest--); 0873 count2++; 0874 count1 = 0; 0875 if (--len2 == 1) 0876 break outer; 0877 } 0878 } while ((count1 | count2) < minGallop); 0879 0880 /* 0881 * One run is winning so consistently that galloping may be a 0882 * huge win. So try that, and continue galloping until (if ever) 0883 * neither run appears to be winning consistently anymore. 0884 */ 0885 do { 0886 assert len1 > 0 && len2 > 1; 0887 count1 = len1 - gallopRight(s.getKey(tmp, cursor2, key0), a, base1, len1, len1 - 1, c); 0888 if (count1 != 0) { 0889 dest -= count1; 0890 cursor1 -= count1; 0891 len1 -= count1; 0892 s.copyRange(a, cursor1 + 1, a, dest + 1, count1); 0893 if (len1 == 0) 0894 break outer; 0895 } 0896 s.copyElement(tmp, cursor2--, a, dest--); 0897 if (--len2 == 1) 0898 break outer; 0899 0900 count2 = len2 - gallopLeft(s.getKey(a, cursor1, key0), tmp, 0, len2, len2 - 1, c); 0901 if (count2 != 0) { 0902 dest -= count2; 0903 cursor2 -= count2; 0904 len2 -= count2; 0905 s.copyRange(tmp, cursor2 + 1, a, dest + 1, count2); 0906 if (len2 <= 1) // len2 == 1 || len2 == 0 0907 break outer; 0908 } 0909 s.copyElement(a, cursor1--, a, dest--); 0910 if (--len1 == 0) 0911 break outer; 0912 minGallop--; 0913 } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP); 0914 if (minGallop < 0) 0915 minGallop = 0; 0916 minGallop += 2; // Penalize for leaving gallop mode 0917 } // End of "outer" loop 0918 this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field 0919 0920 if (len2 == 1) { 0921 assert len1 > 0; 0922 dest -= len1; 0923 cursor1 -= len1; 0924 s.copyRange(a, cursor1 + 1, a, dest + 1, len1); 0925 s.copyElement(tmp, cursor2, a, dest); // Move first elt of run2 to front of merge 0926 } else if (len2 == 0) { 0927 throw new IllegalArgumentException( 0928 "Comparison method violates its general contract!"); 0929 } else { 0930 assert len1 == 0; 0931 assert len2 > 0; 0932 s.copyRange(tmp, 0, a, dest - (len2 - 1), len2); 0933 } 0934 } 0935 0936 /** 0937 * Ensures that the external array tmp has at least the specified 0938 * number of elements, increasing its size if necessary. The size 0939 * increases exponentially to ensure amortized linear time complexity. 0940 * 0941 * @param minCapacity the minimum required capacity of the tmp array 0942 * @return tmp, whether or not it grew 0943 */ 0944 private Buffer ensureCapacity(int minCapacity) { 0945 if (tmpLength < minCapacity) { 0946 // Compute smallest power of 2 > minCapacity 0947 int newSize = minCapacity; 0948 newSize |= newSize >> 1; 0949 newSize |= newSize >> 2; 0950 newSize |= newSize >> 4; 0951 newSize |= newSize >> 8; 0952 newSize |= newSize >> 16; 0953 newSize++; 0954 0955 if (newSize < 0) // Not bloody likely! 0956 newSize = minCapacity; 0957 else 0958 newSize = Math.min(newSize, aLength >>> 1); 0959 0960 tmp = s.allocate(newSize); 0961 tmpLength = newSize; 0962 } 0963 return tmp; 0964 } 0965 } 0966 }
[ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
This page was automatically generated by the 2.1.0 LXR engine. The LXR team |