1/*
2 * Copyright (C) 2008 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 android.database;
18
19import java.util.Iterator;
20
21/**
22 * Does a join on two cursors using the specified columns. The cursors must already
23 * be sorted on each of the specified columns in ascending order. This joiner only
24 * supports the case where the tuple of key column values is unique.
25 * <p>
26 * Typical usage:
27 *
28 * <pre>
29 * CursorJoiner joiner = new CursorJoiner(cursorA, keyColumnsofA, cursorB, keyColumnsofB);
30 * for (CursorJointer.Result joinerResult : joiner) {
31 *     switch (joinerResult) {
32 *         case LEFT:
33 *             // handle case where a row in cursorA is unique
34 *             break;
35 *         case RIGHT:
36 *             // handle case where a row in cursorB is unique
37 *             break;
38 *         case BOTH:
39 *             // handle case where a row with the same key is in both cursors
40 *             break;
41 *     }
42 * }
43 * </pre>
44 */
45public final class CursorJoiner
46        implements Iterator<CursorJoiner.Result>, Iterable<CursorJoiner.Result> {
47    private Cursor mCursorLeft;
48    private Cursor mCursorRight;
49    private boolean mCompareResultIsValid;
50    private Result mCompareResult;
51    private int[] mColumnsLeft;
52    private int[] mColumnsRight;
53    private String[] mValues;
54
55    /**
56     * The result of a call to next().
57     */
58    public enum Result {
59        /** The row currently pointed to by the left cursor is unique */
60        RIGHT,
61        /** The row currently pointed to by the right cursor is unique */
62        LEFT,
63        /** The rows pointed to by both cursors are the same */
64        BOTH
65    }
66
67    /**
68     * Initializes the CursorJoiner and resets the cursors to the first row. The left and right
69     * column name arrays must have the same number of columns.
70     * @param cursorLeft The left cursor to compare
71     * @param columnNamesLeft The column names to compare from the left cursor
72     * @param cursorRight The right cursor to compare
73     * @param columnNamesRight The column names to compare from the right cursor
74     */
75    public CursorJoiner(
76            Cursor cursorLeft, String[] columnNamesLeft,
77            Cursor cursorRight, String[] columnNamesRight) {
78        if (columnNamesLeft.length != columnNamesRight.length) {
79            throw new IllegalArgumentException(
80                    "you must have the same number of columns on the left and right, "
81                            + columnNamesLeft.length + " != " + columnNamesRight.length);
82        }
83
84        mCursorLeft = cursorLeft;
85        mCursorRight = cursorRight;
86
87        mCursorLeft.moveToFirst();
88        mCursorRight.moveToFirst();
89
90        mCompareResultIsValid = false;
91
92        mColumnsLeft = buildColumnIndiciesArray(cursorLeft, columnNamesLeft);
93        mColumnsRight = buildColumnIndiciesArray(cursorRight, columnNamesRight);
94
95        mValues = new String[mColumnsLeft.length * 2];
96    }
97
98    public Iterator<Result> iterator() {
99        return this;
100    }
101
102    /**
103     * Lookup the indicies of the each column name and return them in an array.
104     * @param cursor the cursor that contains the columns
105     * @param columnNames the array of names to lookup
106     * @return an array of column indices
107     */
108    private int[] buildColumnIndiciesArray(Cursor cursor, String[] columnNames) {
109        int[] columns = new int[columnNames.length];
110        for (int i = 0; i < columnNames.length; i++) {
111            columns[i] = cursor.getColumnIndexOrThrow(columnNames[i]);
112        }
113        return columns;
114    }
115
116    /**
117     * Returns whether or not there are more rows to compare using next().
118     * @return true if there are more rows to compare
119     */
120    public boolean hasNext() {
121        if (mCompareResultIsValid) {
122            switch (mCompareResult) {
123                case BOTH:
124                    return !mCursorLeft.isLast() || !mCursorRight.isLast();
125
126                case LEFT:
127                    return !mCursorLeft.isLast() || !mCursorRight.isAfterLast();
128
129                case RIGHT:
130                    return !mCursorLeft.isAfterLast() || !mCursorRight.isLast();
131
132                default:
133                    throw new IllegalStateException("bad value for mCompareResult, "
134                            + mCompareResult);
135            }
136        } else {
137            return !mCursorLeft.isAfterLast() || !mCursorRight.isAfterLast();
138        }
139    }
140
141    /**
142     * Returns the comparison result of the next row from each cursor. If one cursor
143     * has no more rows but the other does then subsequent calls to this will indicate that
144     * the remaining rows are unique.
145     * <p>
146     * The caller must check that hasNext() returns true before calling this.
147     * <p>
148     * Once next() has been called the cursors specified in the result of the call to
149     * next() are guaranteed to point to the row that was indicated. Reading values
150     * from the cursor that was not indicated in the call to next() will result in
151     * undefined behavior.
152     * @return LEFT, if the row pointed to by the left cursor is unique, RIGHT
153     *   if the row pointed to by the right cursor is unique, BOTH if the rows in both
154     *   cursors are the same.
155     */
156    public Result next() {
157        if (!hasNext()) {
158            throw new IllegalStateException("you must only call next() when hasNext() is true");
159        }
160        incrementCursors();
161        assert hasNext();
162
163        boolean hasLeft = !mCursorLeft.isAfterLast();
164        boolean hasRight = !mCursorRight.isAfterLast();
165
166        if (hasLeft && hasRight) {
167            populateValues(mValues, mCursorLeft, mColumnsLeft, 0 /* start filling at index 0 */);
168            populateValues(mValues, mCursorRight, mColumnsRight, 1 /* start filling at index 1 */);
169            switch (compareStrings(mValues)) {
170                case -1:
171                    mCompareResult = Result.LEFT;
172                    break;
173                case 0:
174                    mCompareResult = Result.BOTH;
175                    break;
176                case 1:
177                    mCompareResult = Result.RIGHT;
178                    break;
179            }
180        } else if (hasLeft) {
181            mCompareResult = Result.LEFT;
182        } else  {
183            assert hasRight;
184            mCompareResult = Result.RIGHT;
185        }
186        mCompareResultIsValid = true;
187        return mCompareResult;
188    }
189
190    public void remove() {
191        throw new UnsupportedOperationException("not implemented");
192    }
193
194    /**
195     * Reads the strings from the cursor that are specifed in the columnIndicies
196     * array and saves them in values beginning at startingIndex, skipping a slot
197     * for each value. If columnIndicies has length 3 and startingIndex is 1, the
198     * values will be stored in slots 1, 3, and 5.
199     * @param values the String[] to populate
200     * @param cursor the cursor from which to read
201     * @param columnIndicies the indicies of the values to read from the cursor
202     * @param startingIndex the slot in which to start storing values, and must be either 0 or 1.
203     */
204    private static void populateValues(String[] values, Cursor cursor, int[] columnIndicies,
205            int startingIndex) {
206        assert startingIndex == 0 || startingIndex == 1;
207        for (int i = 0; i < columnIndicies.length; i++) {
208            values[startingIndex + i*2] = cursor.getString(columnIndicies[i]);
209        }
210    }
211
212    /**
213     * Increment the cursors past the rows indicated in the most recent call to next().
214     * This will only have an affect once per call to next().
215     */
216    private void incrementCursors() {
217        if (mCompareResultIsValid) {
218            switch (mCompareResult) {
219                case LEFT:
220                    mCursorLeft.moveToNext();
221                    break;
222                case RIGHT:
223                    mCursorRight.moveToNext();
224                    break;
225                case BOTH:
226                    mCursorLeft.moveToNext();
227                    mCursorRight.moveToNext();
228                    break;
229            }
230            mCompareResultIsValid = false;
231        }
232    }
233
234    /**
235     * Compare the values. Values contains n pairs of strings. If all the pairs of strings match
236     * then returns 0. Otherwise returns the comparison result of the first non-matching pair
237     * of values, -1 if the first of the pair is less than the second of the pair or 1 if it
238     * is greater.
239     * @param values the n pairs of values to compare
240     * @return -1, 0, or 1 as described above.
241     */
242    private static int compareStrings(String... values) {
243        if ((values.length % 2) != 0) {
244            throw new IllegalArgumentException("you must specify an even number of values");
245        }
246
247        for (int index = 0; index < values.length; index+=2) {
248            if (values[index] == null) {
249                if (values[index+1] == null) continue;
250                return -1;
251            }
252
253            if (values[index+1] == null) {
254                return 1;
255            }
256
257            int comp = values[index].compareTo(values[index+1]);
258            if (comp != 0) {
259                return comp < 0 ? -1 : 1;
260            }
261        }
262
263        return 0;
264    }
265}
266