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 305dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey/** 315dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * Cursor wrapper that presents a sorted view of the underlying cursor. Handles 325dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * common {@link Document} sorting modes, such as ordering directories first. 335dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey */ 345dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkeypublic class SortingCursorWrapper extends AbstractCursor { 355dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey private final Cursor mCursor; 365dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 375dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey private final int[] mPosition; 385dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey private final String[] mValueString; 395dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey private final long[] mValueLong; 405dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 415dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public SortingCursorWrapper(Cursor cursor, int sortOrder) { 425dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mCursor = cursor; 435dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 445dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final int count = cursor.getCount(); 455dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mPosition = new int[count]; 465dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey switch (sortOrder) { 47b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey case SORT_ORDER_DISPLAY_NAME: 485dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mValueString = new String[count]; 495dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mValueLong = null; 505dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey break; 51b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey case SORT_ORDER_LAST_MODIFIED: 52b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey case SORT_ORDER_SIZE: 535dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mValueString = null; 545dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mValueLong = new long[count]; 555dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey break; 565dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey default: 575dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey throw new IllegalArgumentException(); 585dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 595dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 605dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey cursor.moveToPosition(-1); 615dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey for (int i = 0; i < count; i++) { 625dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey cursor.moveToNext(); 635dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mPosition[i] = i; 645dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 655dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey switch (sortOrder) { 66b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey case SORT_ORDER_DISPLAY_NAME: 675d321d472d9983db52610393e6506e2b2d2da4bfJeff Sharkey final String mimeType = getCursorString(cursor, Document.COLUMN_MIME_TYPE); 685d321d472d9983db52610393e6506e2b2d2da4bfJeff Sharkey final String displayName = getCursorString( 695d321d472d9983db52610393e6506e2b2d2da4bfJeff Sharkey cursor, Document.COLUMN_DISPLAY_NAME); 705dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey if (Document.MIME_TYPE_DIR.equals(mimeType)) { 715dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mValueString[i] = '\001' + displayName; 725dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } else { 735dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mValueString[i] = displayName; 745dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 755dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey break; 76b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey case SORT_ORDER_LAST_MODIFIED: 775d321d472d9983db52610393e6506e2b2d2da4bfJeff Sharkey mValueLong[i] = getCursorLong(cursor, Document.COLUMN_LAST_MODIFIED); 785dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey break; 79b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey case SORT_ORDER_SIZE: 805d321d472d9983db52610393e6506e2b2d2da4bfJeff Sharkey mValueLong[i] = getCursorLong(cursor, Document.COLUMN_SIZE); 815dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey break; 825dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 835dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 845dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 855dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey switch (sortOrder) { 86b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey case SORT_ORDER_DISPLAY_NAME: 875dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey synchronized (SortingCursorWrapper.class) { 885dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 895dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey binarySort(mPosition, mValueString); 905dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 915dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey break; 92b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey case SORT_ORDER_LAST_MODIFIED: 93b51331116eb2ebbc41aaf69142916f9af6dffdd5Jeff Sharkey case SORT_ORDER_SIZE: 945dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey binarySort(mPosition, mValueLong); 955dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey break; 965dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 975dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 985dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 995dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 100954be0232655d316bc5decbbd35579af902c75c2Jeff Sharkey public Bundle getExtras() { 101954be0232655d316bc5decbbd35579af902c75c2Jeff Sharkey return mCursor.getExtras(); 102954be0232655d316bc5decbbd35579af902c75c2Jeff Sharkey } 103954be0232655d316bc5decbbd35579af902c75c2Jeff Sharkey 104954be0232655d316bc5decbbd35579af902c75c2Jeff Sharkey @Override 1055dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public void close() { 1065dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey super.close(); 1075dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey mCursor.close(); 1085dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1095dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1105dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1115dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public boolean onMove(int oldPosition, int newPosition) { 1125dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.moveToPosition(mPosition[newPosition]); 1135dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1145dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1155dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1165dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public String[] getColumnNames() { 1175dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.getColumnNames(); 1185dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1195dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1205dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1215dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public int getCount() { 1225dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.getCount(); 1235dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1245dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1255dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1265dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public double getDouble(int column) { 1275dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.getDouble(column); 1285dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1295dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1305dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1315dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public float getFloat(int column) { 1325dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.getFloat(column); 1335dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1345dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1355dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1365dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public int getInt(int column) { 1375dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.getInt(column); 1385dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1395dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1405dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1415dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public long getLong(int column) { 1425dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.getLong(column); 1435dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1445dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1455dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1465dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public short getShort(int column) { 1475dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.getShort(column); 1485dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1495dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1505dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1515dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public String getString(int column) { 1525dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.getString(column); 1535dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1545dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1555dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1565dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public int getType(int column) { 1575dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.getType(column); 1585dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1595dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1605dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey @Override 1615dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey public boolean isNull(int column) { 1625dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey return mCursor.isNull(column); 1635dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1645dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1655dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey /** 1665dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * Borrowed from TimSort.binarySort(), but modified to sort two column 1675dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * dataset. 1685dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey */ 1695dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey private static void binarySort(int[] position, String[] value) { 1705dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final int count = position.length; 1715dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey for (int start = 1; start < count; start++) { 1725dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final int pivotPosition = position[start]; 1735dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final String pivotValue = value[start]; 1745dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1755dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey int left = 0; 1765dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey int right = start; 1775dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1785dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey while (left < right) { 1795dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey int mid = (left + right) >>> 1; 1805dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1815dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final String lhs = pivotValue; 1825dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final String rhs = value[mid]; 1835dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final int compare; 1845dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey if (lhs == null) { 1855dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey compare = -1; 1865dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } else if (rhs == null) { 1875dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey compare = 1; 1885dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } else { 1895dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey compare = lhs.compareToIgnoreCase(rhs); 1905dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1915dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1925dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey if (compare < 0) { 1935dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey right = mid; 1945dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } else { 1955dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey left = mid + 1; 1965dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1975dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 1985dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 1995dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey int n = start - left; 2005dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey switch (n) { 2015dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey case 2: 2025dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey position[left + 2] = position[left + 1]; 2035dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey value[left + 2] = value[left + 1]; 2045dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey case 1: 2055dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey position[left + 1] = position[left]; 2065dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey value[left + 1] = value[left]; 2075dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey break; 2085dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey default: 2095dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey System.arraycopy(position, left, position, left + 1, n); 2105dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey System.arraycopy(value, left, value, left + 1, n); 2115dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 2125dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 2135dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey position[left] = pivotPosition; 2145dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey value[left] = pivotValue; 2155dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 2165dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 2175dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 2185dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey /** 2195dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * Borrowed from TimSort.binarySort(), but modified to sort two column 2205dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey * dataset. 2215dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey */ 2225dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey private static void binarySort(int[] position, long[] value) { 2235dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final int count = position.length; 2245dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey for (int start = 1; start < count; start++) { 2255dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final int pivotPosition = position[start]; 2265dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final long pivotValue = value[start]; 2275dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 2285dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey int left = 0; 2295dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey int right = start; 2305dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 2315dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey while (left < right) { 2325dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey int mid = (left + right) >>> 1; 2335dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 2345dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final long lhs = pivotValue; 2355dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final long rhs = value[mid]; 2365dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey final int compare = Long.compare(lhs, rhs); 2375dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey if (compare > 0) { 2385dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey right = mid; 2395dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } else { 2405dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey left = mid + 1; 2415dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 2425dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 2435dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 2445dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey int n = start - left; 2455dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey switch (n) { 2465dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey case 2: 2475dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey position[left + 2] = position[left + 1]; 2485dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey value[left + 2] = value[left + 1]; 2495dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey case 1: 2505dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey position[left + 1] = position[left]; 2515dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey value[left + 1] = value[left]; 2525dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey break; 2535dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey default: 2545dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey System.arraycopy(position, left, position, left + 1, n); 2555dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey System.arraycopy(value, left, value, left + 1, n); 2565dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 2575dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey 2585dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey position[left] = pivotPosition; 2595dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey value[left] = pivotValue; 2605dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 2615dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey } 2625dfb345df7cb17b3a7e534a80a270b4afe7934daJeff Sharkey} 263