15dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey/* 25dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * Copyright (C) 2013 The Android Open Source Project 35dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * 45dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * Licensed under the Apache License, Version 2.0 (the "License"); 55dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * you may not use this file except in compliance with the License. 65dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * You may obtain a copy of the License at 75dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * 85dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * http://www.apache.org/licenses/LICENSE-2.0 95dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * 105dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * Unless required by applicable law or agreed to in writing, software 115dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * distributed under the License is distributed on an "AS IS" BASIS, 125dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 135dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * See the License for the specific language governing permissions and 145dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * limitations under the License. 155dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey */ 165dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 175dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkeypackage com.android.documentsui; 185dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 19b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkeyimport static com.android.documentsui.DocumentsActivity.State.SORT_ORDER_DISPLAY_NAME; 20b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkeyimport static com.android.documentsui.DocumentsActivity.State.SORT_ORDER_LAST_MODIFIED; 21b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkeyimport static com.android.documentsui.DocumentsActivity.State.SORT_ORDER_SIZE; 225d321d472d9983db52610393e6506e2b2d2da4bfJeff Sharkeyimport static com.android.documentsui.model.DocumentInfo.getCursorLong; 235d321d472d9983db52610393e6506e2b2d2da4bfJeff Sharkeyimport static com.android.documentsui.model.DocumentInfo.getCursorString; 24b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey 255dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkeyimport android.database.AbstractCursor; 265dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkeyimport android.database.Cursor; 27954be0232655d316bc5decbbd35579af902c75c2Jeff Sharkeyimport android.os.Bundle; 285dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkeyimport android.provider.DocumentsContract.Document; 295dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 30fa5ec770ec9278b471670969ca56e1bdec3d050eJeff Sharkeyimport com.android.documentsui.model.DocumentInfo; 31fa5ec770ec9278b471670969ca56e1bdec3d050eJeff Sharkey 325dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey/** 335dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * Cursor wrapper that presents a sorted view of the underlying cursor. Handles 345dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * common {@link Document} sorting modes, such as ordering directories first. 355dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey */ 365dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkeypublic class SortingCursorWrapper extends AbstractCursor { 375dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey private final Cursor mCursor; 385dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 395dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey private final int[] mPosition; 405dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey private final String[] mValueString; 415dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey private final long[] mValueLong; 425dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 435dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public SortingCursorWrapper(Cursor cursor, int sortOrder) { 445dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mCursor = cursor; 455dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 465dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final int count = cursor.getCount(); 475dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mPosition = new int[count]; 485dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey switch (sortOrder) { 49b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey case SORT_ORDER_DISPLAY_NAME: 505dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mValueString = new String[count]; 515dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mValueLong = null; 525dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey break; 53b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey case SORT_ORDER_LAST_MODIFIED: 54b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey case SORT_ORDER_SIZE: 555dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mValueString = null; 565dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mValueLong = new long[count]; 575dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey break; 585dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey default: 595dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey throw new IllegalArgumentException(); 605dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 615dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 625dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey cursor.moveToPosition(-1); 635dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey for (int i = 0; i < count; i++) { 645dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey cursor.moveToNext(); 655dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mPosition[i] = i; 665dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 675dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey switch (sortOrder) { 68b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey case SORT_ORDER_DISPLAY_NAME: 695d321d472d9983db52610393e6506e2b2d2da4bfJeff Sharkey final String mimeType = getCursorString(cursor, Document.COLUMN_MIME_TYPE); 705d321d472d9983db52610393e6506e2b2d2da4bfJeff Sharkey final String displayName = getCursorString( 715d321d472d9983db52610393e6506e2b2d2da4bfJeff Sharkey cursor, Document.COLUMN_DISPLAY_NAME); 725dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey if (Document.MIME_TYPE_DIR.equals(mimeType)) { 73fa5ec770ec9278b471670969ca56e1bdec3d050eJeff Sharkey mValueString[i] = DocumentInfo.DIR_PREFIX + displayName; 745dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } else { 755dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mValueString[i] = displayName; 765dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 775dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey break; 78b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey case SORT_ORDER_LAST_MODIFIED: 795d321d472d9983db52610393e6506e2b2d2da4bfJeff Sharkey mValueLong[i] = getCursorLong(cursor, Document.COLUMN_LAST_MODIFIED); 805dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey break; 81b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey case SORT_ORDER_SIZE: 825d321d472d9983db52610393e6506e2b2d2da4bfJeff Sharkey mValueLong[i] = getCursorLong(cursor, Document.COLUMN_SIZE); 835dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey break; 845dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 855dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 865dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 875dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey switch (sortOrder) { 88b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey case SORT_ORDER_DISPLAY_NAME: 895dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey synchronized (SortingCursorWrapper.class) { 905dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 915dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey binarySort(mPosition, mValueString); 925dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 935dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey break; 94b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey case SORT_ORDER_LAST_MODIFIED: 95b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey case SORT_ORDER_SIZE: 965dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey binarySort(mPosition, mValueLong); 975dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey break; 985dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 995dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1005dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1015dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 102954be0232655d316bc5decbbd35579af902c75c2Jeff Sharkey public Bundle getExtras() { 103954be0232655d316bc5decbbd35579af902c75c2Jeff Sharkey return mCursor.getExtras(); 104954be0232655d316bc5decbbd35579af902c75c2Jeff Sharkey } 105954be0232655d316bc5decbbd35579af902c75c2Jeff Sharkey 106954be0232655d316bc5decbbd35579af902c75c2Jeff Sharkey @Override 1075dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public void close() { 1085dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey super.close(); 1095dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mCursor.close(); 1105dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1115dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1125dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1135dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public boolean onMove(int oldPosition, int newPosition) { 1145dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.moveToPosition(mPosition[newPosition]); 1155dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1165dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1175dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1185dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public String[] getColumnNames() { 1195dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.getColumnNames(); 1205dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1215dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1225dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1235dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public int getCount() { 1245dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.getCount(); 1255dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1265dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1275dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1285dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public double getDouble(int column) { 1295dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.getDouble(column); 1305dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1315dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1325dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1335dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public float getFloat(int column) { 1345dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.getFloat(column); 1355dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1365dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1375dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1385dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public int getInt(int column) { 1395dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.getInt(column); 1405dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1415dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1425dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1435dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public long getLong(int column) { 1445dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.getLong(column); 1455dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1465dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1475dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1485dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public short getShort(int column) { 1495dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.getShort(column); 1505dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1515dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1525dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1535dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public String getString(int column) { 1545dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.getString(column); 1555dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1565dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1575dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1585dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public int getType(int column) { 1595dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.getType(column); 1605dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1615dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1625dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1635dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public boolean isNull(int column) { 1645dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.isNull(column); 1655dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1665dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1675dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey /** 1685dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * Borrowed from TimSort.binarySort(), but modified to sort two column 1695dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * dataset. 1705dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey */ 1715dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey private static void binarySort(int[] position, String[] value) { 1725dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final int count = position.length; 1735dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey for (int start = 1; start < count; start++) { 1745dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final int pivotPosition = position[start]; 1755dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final String pivotValue = value[start]; 1765dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1775dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey int left = 0; 1785dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey int right = start; 1795dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1805dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey while (left < right) { 1815dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey int mid = (left + right) >>> 1; 1825dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1835dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final String lhs = pivotValue; 1845dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final String rhs = value[mid]; 185fa5ec770ec9278b471670969ca56e1bdec3d050eJeff Sharkey final int compare = DocumentInfo.compareToIgnoreCaseNullable(lhs, rhs); 1865dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1875dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey if (compare < 0) { 1885dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey right = mid; 1895dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } else { 1905dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey left = mid + 1; 1915dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1925dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1935dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1945dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey int n = start - left; 1955dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey switch (n) { 1965dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey case 2: 1975dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey position[left + 2] = position[left + 1]; 1985dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey value[left + 2] = value[left + 1]; 1995dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey case 1: 2005dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey position[left + 1] = position[left]; 2015dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey value[left + 1] = value[left]; 2025dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey break; 2035dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey default: 2045dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey System.arraycopy(position, left, position, left + 1, n); 2055dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey System.arraycopy(value, left, value, left + 1, n); 2065dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 2075dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 2085dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey position[left] = pivotPosition; 2095dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey value[left] = pivotValue; 2105dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 2115dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 2125dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 2135dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey /** 2145dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * Borrowed from TimSort.binarySort(), but modified to sort two column 2155dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * dataset. 2165dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey */ 2175dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey private static void binarySort(int[] position, long[] value) { 2185dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final int count = position.length; 2195dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey for (int start = 1; start < count; start++) { 2205dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final int pivotPosition = position[start]; 2215dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final long pivotValue = value[start]; 2225dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 2235dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey int left = 0; 2245dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey int right = start; 2255dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 2265dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey while (left < right) { 2275dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey int mid = (left + right) >>> 1; 2285dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 2295dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final long lhs = pivotValue; 2305dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final long rhs = value[mid]; 2315dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final int compare = Long.compare(lhs, rhs); 2325dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey if (compare > 0) { 2335dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey right = mid; 2345dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } else { 2355dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey left = mid + 1; 2365dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 2375dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 2385dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 2395dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey int n = start - left; 2405dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey switch (n) { 2415dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey case 2: 2425dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey position[left + 2] = position[left + 1]; 2435dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey value[left + 2] = value[left + 1]; 2445dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey case 1: 2455dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey position[left + 1] = position[left]; 2465dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey value[left + 1] = value[left]; 2475dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey break; 2485dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey default: 2495dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey System.arraycopy(position, left, position, left + 1, n); 2505dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey System.arraycopy(value, left, value, left + 1, n); 2515dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 2525dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 2535dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey position[left] = pivotPosition; 2545dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey value[left] = pivotValue; 2555dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 2565dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 2575dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey} 258