1 /* 2 * Copyright (C) 2016 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 com.android.documentsui.sorting; 18 19 import static com.android.documentsui.base.DocumentInfo.getCursorLong; 20 import static com.android.documentsui.base.DocumentInfo.getCursorString; 21 22 import android.database.AbstractCursor; 23 import android.database.Cursor; 24 import android.os.Bundle; 25 import android.provider.DocumentsContract.Document; 26 27 import com.android.documentsui.base.Lookup; 28 import com.android.documentsui.base.Shared; 29 import com.android.documentsui.sorting.SortModel.SortDimensionId; 30 31 /** 32 * Cursor wrapper that presents a sorted view of the underlying cursor. Handles 33 * common {@link Document} sorting modes, such as ordering directories first. 34 */ 35 class SortingCursorWrapper extends AbstractCursor { 36 private final Cursor mCursor; 37 38 private final int[] mPosition; 39 40 public SortingCursorWrapper( 41 Cursor cursor, SortDimension dimension, Lookup<String, String> fileTypeLookup) { 42 mCursor = cursor; 43 44 final int count = cursor.getCount(); 45 mPosition = new int[count]; 46 boolean[] isDirs = new boolean[count]; 47 String[] stringValues = null; 48 long[] longValues = null; 49 String[] ids = new String[count]; 50 51 final @SortDimensionId int id = dimension.getId(); 52 switch (id) { 53 case SortModel.SORT_DIMENSION_ID_TITLE: 54 case SortModel.SORT_DIMENSION_ID_FILE_TYPE: 55 stringValues = new String[count]; 56 break; 57 case SortModel.SORT_DIMENSION_ID_DATE: 58 case SortModel.SORT_DIMENSION_ID_SIZE: 59 longValues = new long[count]; 60 break; 61 } 62 63 cursor.moveToPosition(-1); 64 for (int i = 0; i < count; i++) { 65 cursor.moveToNext(); 66 mPosition[i] = i; 67 68 final String mimeType = getCursorString(mCursor, Document.COLUMN_MIME_TYPE); 69 isDirs[i] = Document.MIME_TYPE_DIR.equals(mimeType); 70 ids[i] = getCursorString(mCursor, Document.COLUMN_DOCUMENT_ID); 71 72 switch(id) { 73 case SortModel.SORT_DIMENSION_ID_TITLE: 74 final String displayName = getCursorString( 75 mCursor, Document.COLUMN_DISPLAY_NAME); 76 stringValues[i] = displayName; 77 break; 78 case SortModel.SORT_DIMENSION_ID_FILE_TYPE: 79 stringValues[i] = fileTypeLookup.lookup(mimeType); 80 break; 81 case SortModel.SORT_DIMENSION_ID_DATE: 82 longValues[i] = getLastModified(mCursor); 83 break; 84 case SortModel.SORT_DIMENSION_ID_SIZE: 85 longValues[i] = getCursorLong(mCursor, Document.COLUMN_SIZE); 86 break; 87 } 88 89 } 90 91 switch (id) { 92 case SortModel.SORT_DIMENSION_ID_TITLE: 93 case SortModel.SORT_DIMENSION_ID_FILE_TYPE: 94 binarySort(stringValues, isDirs, mPosition, ids, dimension.getSortDirection()); 95 break; 96 case SortModel.SORT_DIMENSION_ID_DATE: 97 case SortModel.SORT_DIMENSION_ID_SIZE: 98 binarySort(longValues, isDirs, mPosition, ids, dimension.getSortDirection()); 99 break; 100 } 101 102 } 103 104 @Override 105 public void close() { 106 super.close(); 107 mCursor.close(); 108 } 109 110 @Override 111 public boolean onMove(int oldPosition, int newPosition) { 112 return mCursor.moveToPosition(mPosition[newPosition]); 113 } 114 115 @Override 116 public String[] getColumnNames() { 117 return mCursor.getColumnNames(); 118 } 119 120 @Override 121 public int getCount() { 122 return mCursor.getCount(); 123 } 124 125 @Override 126 public double getDouble(int column) { 127 return mCursor.getDouble(column); 128 } 129 130 @Override 131 public float getFloat(int column) { 132 return mCursor.getFloat(column); 133 } 134 135 @Override 136 public int getInt(int column) { 137 return mCursor.getInt(column); 138 } 139 140 @Override 141 public long getLong(int column) { 142 return mCursor.getLong(column); 143 } 144 145 @Override 146 public short getShort(int column) { 147 return mCursor.getShort(column); 148 } 149 150 @Override 151 public String getString(int column) { 152 return mCursor.getString(column); 153 } 154 155 @Override 156 public int getType(int column) { 157 return mCursor.getType(column); 158 } 159 160 @Override 161 public boolean isNull(int column) { 162 return mCursor.isNull(column); 163 } 164 165 @Override 166 public Bundle getExtras() { 167 return mCursor.getExtras(); 168 } 169 170 /** 171 * @return Timestamp for the given document. Some docs (e.g. active downloads) have a null 172 * timestamp - these will be replaced with MAX_LONG so that such files get sorted to the top 173 * when sorting descending by date. 174 */ 175 private static long getLastModified(Cursor cursor) { 176 long l = getCursorLong(cursor, Document.COLUMN_LAST_MODIFIED); 177 return (l == -1) ? Long.MAX_VALUE : l; 178 } 179 180 /** 181 * Borrowed from TimSort.binarySort(), but modified to sort two column 182 * dataset. 183 */ 184 private static void binarySort( 185 String[] sortKey, 186 boolean[] isDirs, 187 int[] positions, 188 String[] ids, 189 @SortDimension.SortDirection int direction) { 190 final int count = positions.length; 191 for (int start = 1; start < count; start++) { 192 final int pivotPosition = positions[start]; 193 final String pivotValue = sortKey[start]; 194 final boolean pivotIsDir = isDirs[start]; 195 final String pivotId = ids[start]; 196 197 int left = 0; 198 int right = start; 199 200 while (left < right) { 201 int mid = (left + right) >>> 1; 202 203 // Directories always go in front. 204 int compare = 0; 205 final boolean rhsIsDir = isDirs[mid]; 206 if (pivotIsDir && !rhsIsDir) { 207 compare = -1; 208 } else if (!pivotIsDir && rhsIsDir) { 209 compare = 1; 210 } else { 211 final String lhs = pivotValue; 212 final String rhs = sortKey[mid]; 213 switch (direction) { 214 case SortDimension.SORT_DIRECTION_ASCENDING: 215 compare = Shared.compareToIgnoreCaseNullable(lhs, rhs); 216 break; 217 case SortDimension.SORT_DIRECTION_DESCENDING: 218 compare = -Shared.compareToIgnoreCaseNullable(lhs, rhs); 219 break; 220 default: 221 throw new IllegalArgumentException( 222 "Unknown sorting direction: " + direction); 223 } 224 } 225 226 // Use document ID as a tie breaker to achieve stable sort result. 227 if (compare == 0) { 228 compare = pivotId.compareTo(ids[mid]); 229 } 230 231 if (compare < 0) { 232 right = mid; 233 } else { 234 left = mid + 1; 235 } 236 } 237 238 int n = start - left; 239 switch (n) { 240 case 2: 241 positions[left + 2] = positions[left + 1]; 242 sortKey[left + 2] = sortKey[left + 1]; 243 isDirs[left + 2] = isDirs[left + 1]; 244 case 1: 245 positions[left + 1] = positions[left]; 246 sortKey[left + 1] = sortKey[left]; 247 isDirs[left + 1] = isDirs[left]; 248 break; 249 default: 250 System.arraycopy(positions, left, positions, left + 1, n); 251 System.arraycopy(sortKey, left, sortKey, left + 1, n); 252 System.arraycopy(isDirs, left, isDirs, left + 1, n); 253 } 254 255 positions[left] = pivotPosition; 256 sortKey[left] = pivotValue; 257 isDirs[left] = pivotIsDir; 258 } 259 } 260 261 /** 262 * Borrowed from TimSort.binarySort(), but modified to sort two column 263 * dataset. 264 */ 265 private static void binarySort( 266 long[] sortKey, 267 boolean[] isDirs, 268 int[] positions, 269 String[] ids, 270 @SortDimension.SortDirection int direction) { 271 final int count = positions.length; 272 for (int start = 1; start < count; start++) { 273 final int pivotPosition = positions[start]; 274 final long pivotValue = sortKey[start]; 275 final boolean pivotIsDir = isDirs[start]; 276 final String pivotId = ids[start]; 277 278 int left = 0; 279 int right = start; 280 281 while (left < right) { 282 int mid = ((left + right) >>> 1); 283 284 // Directories always go in front. 285 int compare = 0; 286 final boolean rhsIsDir = isDirs[mid]; 287 if (pivotIsDir && !rhsIsDir) { 288 compare = -1; 289 } else if (!pivotIsDir && rhsIsDir) { 290 compare = 1; 291 } else { 292 final long lhs = pivotValue; 293 final long rhs = sortKey[mid]; 294 switch (direction) { 295 case SortDimension.SORT_DIRECTION_ASCENDING: 296 compare = Long.compare(lhs, rhs); 297 break; 298 case SortDimension.SORT_DIRECTION_DESCENDING: 299 compare = -Long.compare(lhs, rhs); 300 break; 301 default: 302 throw new IllegalArgumentException( 303 "Unknown sorting direction: " + direction); 304 } 305 } 306 307 // If numerical comparison yields a tie, use document ID as a tie breaker. This 308 // will yield stable results even if incoming items are continually shuffling and 309 // have identical numerical sort keys. One common example of this scenario is seen 310 // when sorting a set of active downloads by mod time. 311 if (compare == 0) { 312 compare = pivotId.compareTo(ids[mid]); 313 } 314 315 if (compare < 0) { 316 right = mid; 317 } else { 318 left = mid + 1; 319 } 320 } 321 322 int n = start - left; 323 switch (n) { 324 case 2: 325 positions[left + 2] = positions[left + 1]; 326 sortKey[left + 2] = sortKey[left + 1]; 327 isDirs[left + 2] = isDirs[left + 1]; 328 ids[left + 2] = ids[left + 1]; 329 case 1: 330 positions[left + 1] = positions[left]; 331 sortKey[left + 1] = sortKey[left]; 332 isDirs[left + 1] = isDirs[left]; 333 ids[left + 1] = ids[left]; 334 break; 335 default: 336 System.arraycopy(positions, left, positions, left + 1, n); 337 System.arraycopy(sortKey, left, sortKey, left + 1, n); 338 System.arraycopy(isDirs, left, isDirs, left + 1, n); 339 System.arraycopy(ids, left, ids, left + 1, n); 340 } 341 342 positions[left] = pivotPosition; 343 sortKey[left] = pivotValue; 344 isDirs[left] = pivotIsDir; 345 ids[left] = pivotId; 346 } 347 } 348 } 349