1/*
2 * Copyright (C) 2013 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
17package com.android.documentsui;
18
19import static com.android.documentsui.DocumentsActivity.State.SORT_ORDER_DISPLAY_NAME;
20import static com.android.documentsui.DocumentsActivity.State.SORT_ORDER_LAST_MODIFIED;
21import static com.android.documentsui.DocumentsActivity.State.SORT_ORDER_SIZE;
22import static com.android.documentsui.model.DocumentInfo.getCursorLong;
23import static com.android.documentsui.model.DocumentInfo.getCursorString;
24
25import android.database.AbstractCursor;
26import android.database.Cursor;
27import android.os.Bundle;
28import android.provider.DocumentsContract.Document;
29
30/**
31 * Cursor wrapper that presents a sorted view of the underlying cursor. Handles
32 * common {@link Document} sorting modes, such as ordering directories first.
33 */
34public class SortingCursorWrapper extends AbstractCursor {
35    private final Cursor mCursor;
36
37    private final int[] mPosition;
38    private final String[] mValueString;
39    private final long[] mValueLong;
40
41    public SortingCursorWrapper(Cursor cursor, int sortOrder) {
42        mCursor = cursor;
43
44        final int count = cursor.getCount();
45        mPosition = new int[count];
46        switch (sortOrder) {
47            case SORT_ORDER_DISPLAY_NAME:
48                mValueString = new String[count];
49                mValueLong = null;
50                break;
51            case SORT_ORDER_LAST_MODIFIED:
52            case SORT_ORDER_SIZE:
53                mValueString = null;
54                mValueLong = new long[count];
55                break;
56            default:
57                throw new IllegalArgumentException();
58        }
59
60        cursor.moveToPosition(-1);
61        for (int i = 0; i < count; i++) {
62            cursor.moveToNext();
63            mPosition[i] = i;
64
65            switch (sortOrder) {
66                case SORT_ORDER_DISPLAY_NAME:
67                    final String mimeType = getCursorString(cursor, Document.COLUMN_MIME_TYPE);
68                    final String displayName = getCursorString(
69                            cursor, Document.COLUMN_DISPLAY_NAME);
70                    if (Document.MIME_TYPE_DIR.equals(mimeType)) {
71                        mValueString[i] = '\001' + displayName;
72                    } else {
73                        mValueString[i] = displayName;
74                    }
75                    break;
76                case SORT_ORDER_LAST_MODIFIED:
77                    mValueLong[i] = getCursorLong(cursor, Document.COLUMN_LAST_MODIFIED);
78                    break;
79                case SORT_ORDER_SIZE:
80                    mValueLong[i] = getCursorLong(cursor, Document.COLUMN_SIZE);
81                    break;
82            }
83        }
84
85        switch (sortOrder) {
86            case SORT_ORDER_DISPLAY_NAME:
87                synchronized (SortingCursorWrapper.class) {
88
89                    binarySort(mPosition, mValueString);
90                }
91                break;
92            case SORT_ORDER_LAST_MODIFIED:
93            case SORT_ORDER_SIZE:
94                binarySort(mPosition, mValueLong);
95                break;
96        }
97    }
98
99    @Override
100    public Bundle getExtras() {
101        return mCursor.getExtras();
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    /**
166     * Borrowed from TimSort.binarySort(), but modified to sort two column
167     * dataset.
168     */
169    private static void binarySort(int[] position, String[] value) {
170        final int count = position.length;
171        for (int start = 1; start < count; start++) {
172            final int pivotPosition = position[start];
173            final String pivotValue = value[start];
174
175            int left = 0;
176            int right = start;
177
178            while (left < right) {
179                int mid = (left + right) >>> 1;
180
181                final String lhs = pivotValue;
182                final String rhs = value[mid];
183                final int compare;
184                if (lhs == null) {
185                    compare = -1;
186                } else if (rhs == null) {
187                    compare = 1;
188                } else {
189                    compare = lhs.compareToIgnoreCase(rhs);
190                }
191
192                if (compare < 0) {
193                    right = mid;
194                } else {
195                    left = mid + 1;
196                }
197            }
198
199            int n = start - left;
200            switch (n) {
201                case 2:
202                    position[left + 2] = position[left + 1];
203                    value[left + 2] = value[left + 1];
204                case 1:
205                    position[left + 1] = position[left];
206                    value[left + 1] = value[left];
207                    break;
208                default:
209                    System.arraycopy(position, left, position, left + 1, n);
210                    System.arraycopy(value, left, value, left + 1, n);
211            }
212
213            position[left] = pivotPosition;
214            value[left] = pivotValue;
215        }
216    }
217
218    /**
219     * Borrowed from TimSort.binarySort(), but modified to sort two column
220     * dataset.
221     */
222    private static void binarySort(int[] position, long[] value) {
223        final int count = position.length;
224        for (int start = 1; start < count; start++) {
225            final int pivotPosition = position[start];
226            final long pivotValue = value[start];
227
228            int left = 0;
229            int right = start;
230
231            while (left < right) {
232                int mid = (left + right) >>> 1;
233
234                final long lhs = pivotValue;
235                final long rhs = value[mid];
236                final int compare = Long.compare(lhs, rhs);
237                if (compare > 0) {
238                    right = mid;
239                } else {
240                    left = mid + 1;
241                }
242            }
243
244            int n = start - left;
245            switch (n) {
246                case 2:
247                    position[left + 2] = position[left + 1];
248                    value[left + 2] = value[left + 1];
249                case 1:
250                    position[left + 1] = position[left];
251                    value[left + 1] = value[left];
252                    break;
253                default:
254                    System.arraycopy(position, left, position, left + 1, n);
255                    System.arraycopy(value, left, value, left + 1, n);
256            }
257
258            position[left] = pivotPosition;
259            value[left] = pivotValue;
260        }
261    }
262}
263