1/*
2 * Copyright (C) 2007 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.internal.database;
18
19import android.database.AbstractCursor;
20import android.database.Cursor;
21import android.database.DataSetObserver;
22import android.util.Log;
23
24/**
25 * A variant of MergeCursor that sorts the cursors being merged. If decent
26 * performance is ever obtained, it can be put back under android.database.
27 */
28public class SortCursor extends AbstractCursor
29{
30    private static final String TAG = "SortCursor";
31    private Cursor mCursor; // updated in onMove
32    private Cursor[] mCursors;
33    private int [] mSortColumns;
34    private final int ROWCACHESIZE = 64;
35    private int mRowNumCache[] = new int[ROWCACHESIZE];
36    private int mCursorCache[] = new int[ROWCACHESIZE];
37    private int mCurRowNumCache[][];
38    private int mLastCacheHit = -1;
39
40    private DataSetObserver mObserver = new DataSetObserver() {
41
42        @Override
43        public void onChanged() {
44            // Reset our position so the optimizations in move-related code
45            // don't screw us over
46            mPos = -1;
47        }
48
49        @Override
50        public void onInvalidated() {
51            mPos = -1;
52        }
53    };
54
55    public SortCursor(Cursor[] cursors, String sortcolumn)
56    {
57        mCursors = cursors;
58
59        int length = mCursors.length;
60        mSortColumns = new int[length];
61        for (int i = 0 ; i < length ; i++) {
62            if (mCursors[i] == null) continue;
63
64            // Register ourself as a data set observer
65            mCursors[i].registerDataSetObserver(mObserver);
66
67            mCursors[i].moveToFirst();
68
69            // We don't catch the exception
70            mSortColumns[i] = mCursors[i].getColumnIndexOrThrow(sortcolumn);
71        }
72        mCursor = null;
73        String smallest = "";
74        for (int j = 0 ; j < length; j++) {
75            if (mCursors[j] == null || mCursors[j].isAfterLast())
76                continue;
77            String current = mCursors[j].getString(mSortColumns[j]);
78            if (mCursor == null || current.compareToIgnoreCase(smallest) < 0) {
79                smallest = current;
80                mCursor = mCursors[j];
81            }
82        }
83
84        for (int i = mRowNumCache.length - 1; i >= 0; i--) {
85            mRowNumCache[i] = -2;
86        }
87        mCurRowNumCache = new int[ROWCACHESIZE][length];
88    }
89
90    @Override
91    public int getCount()
92    {
93        int count = 0;
94        int length = mCursors.length;
95        for (int i = 0 ; i < length ; i++) {
96            if (mCursors[i] != null) {
97                count += mCursors[i].getCount();
98            }
99        }
100        return count;
101    }
102
103    @Override
104    public boolean onMove(int oldPosition, int newPosition)
105    {
106        if (oldPosition == newPosition)
107            return true;
108
109        /* Find the right cursor
110         * Because the client of this cursor (the listadapter/view) tends
111         * to jump around in the cursor somewhat, a simple cache strategy
112         * is used to avoid having to search all cursors from the start.
113         * TODO: investigate strategies for optimizing random access and
114         * reverse-order access.
115         */
116
117        int cache_entry = newPosition % ROWCACHESIZE;
118
119        if (mRowNumCache[cache_entry] == newPosition) {
120            int which = mCursorCache[cache_entry];
121            mCursor = mCursors[which];
122            if (mCursor == null) {
123                Log.w(TAG, "onMove: cache results in a null cursor.");
124                return false;
125            }
126            mCursor.moveToPosition(mCurRowNumCache[cache_entry][which]);
127            mLastCacheHit = cache_entry;
128            return true;
129        }
130
131        mCursor = null;
132        int length = mCursors.length;
133
134        if (mLastCacheHit >= 0) {
135            for (int i = 0; i < length; i++) {
136                if (mCursors[i] == null) continue;
137                mCursors[i].moveToPosition(mCurRowNumCache[mLastCacheHit][i]);
138            }
139        }
140
141        if (newPosition < oldPosition || oldPosition == -1) {
142            for (int i = 0 ; i < length; i++) {
143                if (mCursors[i] == null) continue;
144                mCursors[i].moveToFirst();
145            }
146            oldPosition = 0;
147        }
148        if (oldPosition < 0) {
149            oldPosition = 0;
150        }
151
152        // search forward to the new position
153        int smallestIdx = -1;
154        for(int i = oldPosition; i <= newPosition; i++) {
155            String smallest = "";
156            smallestIdx = -1;
157            for (int j = 0 ; j < length; j++) {
158                if (mCursors[j] == null || mCursors[j].isAfterLast()) {
159                    continue;
160                }
161                String current = mCursors[j].getString(mSortColumns[j]);
162                if (smallestIdx < 0 || current.compareToIgnoreCase(smallest) < 0) {
163                    smallest = current;
164                    smallestIdx = j;
165                }
166            }
167            if (i == newPosition) break;
168            if (mCursors[smallestIdx] != null) {
169                mCursors[smallestIdx].moveToNext();
170            }
171        }
172        mCursor = mCursors[smallestIdx];
173        mRowNumCache[cache_entry] = newPosition;
174        mCursorCache[cache_entry] = smallestIdx;
175        for (int i = 0; i < length; i++) {
176            if (mCursors[i] != null) {
177                mCurRowNumCache[cache_entry][i] = mCursors[i].getPosition();
178            }
179        }
180        mLastCacheHit = -1;
181        return true;
182    }
183
184    @Override
185    public boolean deleteRow()
186    {
187        return mCursor.deleteRow();
188    }
189
190    @Override
191    public boolean commitUpdates() {
192        int length = mCursors.length;
193        for (int i = 0 ; i < length ; i++) {
194            if (mCursors[i] != null) {
195                mCursors[i].commitUpdates();
196            }
197        }
198        onChange(true);
199        return true;
200    }
201
202    @Override
203    public String getString(int column)
204    {
205        return mCursor.getString(column);
206    }
207
208    @Override
209    public short getShort(int column)
210    {
211        return mCursor.getShort(column);
212    }
213
214    @Override
215    public int getInt(int column)
216    {
217        return mCursor.getInt(column);
218    }
219
220    @Override
221    public long getLong(int column)
222    {
223        return mCursor.getLong(column);
224    }
225
226    @Override
227    public float getFloat(int column)
228    {
229        return mCursor.getFloat(column);
230    }
231
232    @Override
233    public double getDouble(int column)
234    {
235        return mCursor.getDouble(column);
236    }
237
238    @Override
239    public boolean isNull(int column)
240    {
241        return mCursor.isNull(column);
242    }
243
244    @Override
245    public byte[] getBlob(int column)
246    {
247        return mCursor.getBlob(column);
248    }
249
250    @Override
251    public String[] getColumnNames()
252    {
253        if (mCursor != null) {
254            return mCursor.getColumnNames();
255        } else {
256            // All of the cursors may be empty, but they can still return
257            // this information.
258            int length = mCursors.length;
259            for (int i = 0 ; i < length ; i++) {
260                if (mCursors[i] != null) {
261                    return mCursors[i].getColumnNames();
262                }
263            }
264            throw new IllegalStateException("No cursor that can return names");
265        }
266    }
267
268    @Override
269    public void deactivate()
270    {
271        int length = mCursors.length;
272        for (int i = 0 ; i < length ; i++) {
273            if (mCursors[i] == null) continue;
274            mCursors[i].deactivate();
275        }
276    }
277
278    @Override
279    public void close() {
280        int length = mCursors.length;
281        for (int i = 0 ; i < length ; i++) {
282            if (mCursors[i] == null) continue;
283            mCursors[i].close();
284        }
285    }
286
287    @Override
288    public void registerDataSetObserver(DataSetObserver observer) {
289        int length = mCursors.length;
290        for (int i = 0 ; i < length ; i++) {
291            if (mCursors[i] != null) {
292                mCursors[i].registerDataSetObserver(observer);
293            }
294        }
295    }
296
297    @Override
298    public void unregisterDataSetObserver(DataSetObserver observer) {
299        int length = mCursors.length;
300        for (int i = 0 ; i < length ; i++) {
301            if (mCursors[i] != null) {
302                mCursors[i].unregisterDataSetObserver(observer);
303            }
304        }
305    }
306
307    @Override
308    public boolean requery()
309    {
310        int length = mCursors.length;
311        for (int i = 0 ; i < length ; i++) {
312            if (mCursors[i] == null) continue;
313
314            if (mCursors[i].requery() == false) {
315                return false;
316            }
317        }
318
319        return true;
320    }
321}
322