View Javadoc
1   /*
2   Copyright (c) 2011 James Ahlborn
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.healthmarketscience.jackcess.impl;
18  
19  import java.io.IOException;
20  import java.util.Collection;
21  import java.util.HashSet;
22  import java.util.Iterator;
23  import java.util.Map;
24  import java.util.Set;
25  
26  import com.healthmarketscience.jackcess.Index;
27  import com.healthmarketscience.jackcess.IndexCursor;
28  import com.healthmarketscience.jackcess.Row;
29  import com.healthmarketscience.jackcess.RuntimeIOException;
30  import com.healthmarketscience.jackcess.impl.TableImpl.RowState;
31  import com.healthmarketscience.jackcess.util.CaseInsensitiveColumnMatcher;
32  import com.healthmarketscience.jackcess.util.ColumnMatcher;
33  import com.healthmarketscience.jackcess.util.EntryIterableBuilder;
34  import com.healthmarketscience.jackcess.util.SimpleColumnMatcher;
35  import org.apache.commons.logging.Log;
36  import org.apache.commons.logging.LogFactory;
37  
38  /**
39   * Cursor backed by an index with extended traversal options.
40   *
41   * @author James Ahlborn
42   */
43  public class IndexCursorImpl extends CursorImpl implements IndexCursor
44  {
45    private static final Log LOG = LogFactory.getLog(IndexCursorImpl.class);  
46  
47    /** IndexDirHandler for forward traversal */
48    private final IndexDirHandler _forwardDirHandler =
49      new ForwardIndexDirHandler();
50    /** IndexDirHandler for backward traversal */
51    private final IndexDirHandler _reverseDirHandler =
52      new ReverseIndexDirHandler();
53    /** logical index which this cursor is using */
54    private final IndexImpl _index;
55    /** Cursor over the entries of the relevant index */
56    private final IndexData.EntryCursor _entryCursor;
57    /** column names for the index entry columns */
58    private Set<String> _indexEntryPattern;
59  
60    private IndexCursorImpl(TableImpl table, IndexImpl index,
61                            IndexData.EntryCursor entryCursor)
62      throws IOException
63    {
64      super(new IdImpl(table, index), table,
65            new IndexPosition(entryCursor.getFirstEntry()),
66            new IndexPosition(entryCursor.getLastEntry()));
67      _index = index;
68      _index.initialize();
69      _entryCursor = entryCursor;
70    }
71    
72    /**
73     * Creates an indexed cursor for the given table, narrowed to the given
74     * range.
75     * <p>
76     * Note, index based table traversal may not include all rows, as certain
77     * types of indexes do not include all entries (namely, some indexes ignore
78     * null entries, see {@link Index#shouldIgnoreNulls}).
79     * 
80     * @param table the table over which this cursor will traverse
81     * @param index index for the table which will define traversal order as
82     *              well as enhance certain lookups
83     * @param startRow the first row of data for the cursor, or {@code null} for
84     *                 the first entry
85     * @param startInclusive whether or not startRow is inclusive or exclusive
86     * @param endRow the last row of data for the cursor, or {@code null} for
87     *               the last entry
88     * @param endInclusive whether or not endRow is inclusive or exclusive
89     */
90    public static IndexCursorImpl createCursor(TableImpl table, IndexImpl index,
91                                               Object[] startRow,
92                                               boolean startInclusive,
93                                               Object[] endRow,
94                                               boolean endInclusive)
95      throws IOException
96    {
97      if(table != index.getTable()) {
98        throw new IllegalArgumentException(
99            "Given index is not for given table: " + index + ", " + table);
100     }
101     if(!table.getFormat().INDEXES_SUPPORTED) {
102       throw new IllegalArgumentException(
103           "JetFormat " + table.getFormat() + 
104           " does not currently support index lookups");
105     }
106     if(index.getIndexData().getUnsupportedReason() != null) {
107       throw new IllegalArgumentException(
108           "Given index " + index + 
109           " is not usable for indexed lookups due to " +
110           index.getIndexData().getUnsupportedReason());
111     }
112     IndexCursorImpl cursor = new IndexCursorImpl(
113         table, index, index.cursor(startRow, startInclusive,
114                                    endRow, endInclusive));
115     // init the column matcher appropriately for the index type
116     cursor.setColumnMatcher(null);
117     return cursor;
118   }  
119 
120   private Set<String> getIndexEntryPattern()
121   {
122     if(_indexEntryPattern == null) {
123       // init our set of index column names
124       _indexEntryPattern = new HashSet<String>();
125       for(IndexData.ColumnDescriptor col : getIndex().getColumns()) {
126         _indexEntryPattern.add(col.getName());
127       }
128     }
129     return _indexEntryPattern;
130   }
131 
132   public IndexImpl getIndex() {
133     return _index;
134   }
135 
136   public Row findRowByEntry(Object... entryValues) 
137     throws IOException
138   {
139     if(findFirstRowByEntry(entryValues)) {
140       return getCurrentRow();
141     }
142     return null;
143   }
144   
145   public boolean findFirstRowByEntry(Object... entryValues) 
146     throws IOException 
147   {
148     PositionImpl curPos = _curPos;
149     PositionImpl prevPos = _prevPos;
150     boolean found = false;
151     try {
152       found = findFirstRowByEntryImpl(toRowValues(entryValues), true, 
153                                       _columnMatcher);
154       return found;
155     } finally {
156       if(!found) {
157         try {
158           restorePosition(curPos, prevPos);
159         } catch(IOException e) {
160           LOG.error("Failed restoring position", e);
161         }
162       }
163     }
164   }
165 
166   public void findClosestRowByEntry(Object... entryValues) 
167     throws IOException 
168   {
169     PositionImpl curPos = _curPos;
170     PositionImpl prevPos = _prevPos;
171     boolean found = false;
172     try {
173       findFirstRowByEntryImpl(toRowValues(entryValues), false,
174                               _columnMatcher);
175       found = true;
176     } finally {
177       if(!found) {
178         try {
179           restorePosition(curPos, prevPos);
180         } catch(IOException e) {
181           LOG.error("Failed restoring position", e);
182         }
183       }
184     }
185   }
186 
187   public boolean currentRowMatchesEntry(Object... entryValues) 
188     throws IOException 
189   {
190     return currentRowMatchesEntryImpl(toRowValues(entryValues), _columnMatcher);
191   }
192 
193   public EntryIterableBuilder newEntryIterable(Object... entryValues) {
194     return new EntryIterableBuilder(this, entryValues);
195   }
196 
197   public Iterator<Row> entryIterator(EntryIterableBuilder iterBuilder) {
198     return new EntryIterator(iterBuilder.getColumnNames(),
199                              toRowValues(iterBuilder.getEntryValues()),
200                              iterBuilder.getColumnMatcher());
201   }
202   
203   @Override
204   protected IndexDirHandler getDirHandler(boolean moveForward) {
205     return (moveForward ? _forwardDirHandler : _reverseDirHandler);
206   }
207     
208   @Override
209   protected boolean isUpToDate() {
210     return(super.isUpToDate() && _entryCursor.isUpToDate());
211   }
212     
213   @Override
214   protected void reset(boolean moveForward) {
215     _entryCursor.reset(moveForward);
216     super.reset(moveForward);
217   }
218 
219   @Override
220   protected void restorePositionImpl(PositionImpl curPos, PositionImpl prevPos)
221     throws IOException
222   {
223     if(!(curPos instanceof IndexPosition) ||
224        !(prevPos instanceof IndexPosition)) {
225       throw new IllegalArgumentException(
226           "Restored positions must be index positions");
227     }
228     _entryCursor.restorePosition(((IndexPosition)curPos).getEntry(),
229                                  ((IndexPosition)prevPos).getEntry());
230     super.restorePositionImpl(curPos, prevPos);
231   }
232 
233   @Override
234   protected PositionImpl getRowPosition(RowIdImpl rowId) throws IOException
235   {
236     // we need to get the index entry which corresponds with this row
237     Row row = getTable().getRow(getRowState(), rowId, getIndexEntryPattern());
238     _entryCursor.beforeEntry(getTable().asRow(row));
239     return new IndexPosition(_entryCursor.getNextEntry());
240   }
241 
242   @Override
243   protected boolean findAnotherRowImpl(
244       ColumnImpl columnPattern, Object valuePattern, boolean moveForward,
245       ColumnMatcher columnMatcher, Object searchInfo)
246     throws IOException
247   {
248     Object[] rowValues = (Object[])searchInfo;
249 
250     if((rowValues == null) || !isAtBeginning(moveForward)) {
251       // use the default table scan if we don't have index data or we are
252       // mid-cursor
253       return super.findAnotherRowImpl(columnPattern, valuePattern, moveForward,
254                                       columnMatcher, rowValues);
255     }
256       
257     // sweet, we can use our index
258     if(!findPotentialRow(rowValues, true)) {
259       return false;
260     }
261 
262     // either we found a row with the given value, or none exist in the table
263     return currentRowMatchesImpl(columnPattern, valuePattern, columnMatcher);
264   }
265 
266   /**
267    * Moves to the first row (as defined by the cursor) where the index entries
268    * match the given values.  Caller manages save/restore on failure.
269    *
270    * @param rowValues the column values built from the index column values
271    * @param requireMatch whether or not an exact match is found
272    * @return {@code true} if a valid row was found with the given values,
273    *         {@code false} if no row was found
274    */
275   protected boolean findFirstRowByEntryImpl(Object[] rowValues,
276                                             boolean requireMatch,
277                                             ColumnMatcher columnMatcher) 
278     throws IOException 
279   {
280     if(!findPotentialRow(rowValues, requireMatch)) {
281       return false;
282     } else if(!requireMatch) {
283       // nothing more to do, we have moved to the closest row
284       return true;
285     }
286 
287     return currentRowMatchesEntryImpl(rowValues, columnMatcher);
288   }
289 
290   @Override
291   protected boolean findAnotherRowImpl(
292       Map<String,?> rowPattern, boolean moveForward,
293       ColumnMatcher columnMatcher, Object searchInfo)
294     throws IOException
295   {
296     Object[] rowValues = (Object[])searchInfo;
297 
298     if((rowValues == null) || !isAtBeginning(moveForward)) {
299       // use the default table scan if we don't have index data or we are
300       // mid-cursor
301       return super.findAnotherRowImpl(rowPattern, moveForward, columnMatcher,
302                                       rowValues);
303     }
304 
305     // sweet, we can use our index
306     if(!findPotentialRow(rowValues, true)) {
307       // at end of index, no potential matches
308       return false;
309     }
310 
311     // determine if the pattern columns exactly match the index columns
312     boolean exactColumnMatch = rowPattern.keySet().equals(
313         getIndexEntryPattern());
314     
315     // there may be multiple rows which fit the pattern subset used by
316     // the index, so we need to keep checking until our index values no
317     // longer match
318     do {
319 
320       if(!currentRowMatchesEntryImpl(rowValues, columnMatcher)) {
321         // there are no more rows which could possibly match
322         break;
323       }
324 
325       // note, if exactColumnMatch, no need to do an extra comparison with the
326       // current row (since the entry match check above is equivalent to this
327       // check)
328       if(exactColumnMatch || currentRowMatchesImpl(rowPattern, columnMatcher)) {
329         // found it!
330         return true;
331       }
332 
333     } while(moveToAnotherRow(moveForward));
334         
335     // none of the potential rows matched
336     return false;
337   }
338 
339   private boolean currentRowMatchesEntryImpl(Object[] rowValues, 
340                                              ColumnMatcher columnMatcher)
341     throws IOException
342   {
343     // check the next row to see if it actually matches
344     Row row = getCurrentRow(getIndexEntryPattern());
345 
346     for(IndexData.ColumnDescriptor col : getIndex().getColumns()) {
347 
348       Object patValue = rowValues[col.getColumnIndex()];
349 
350       if((patValue == IndexData.MIN_VALUE) || 
351          (patValue == IndexData.MAX_VALUE)) {
352         // all remaining entry values are "special" (used for partial lookups)
353         return true;
354       }
355 
356       String columnName = col.getName();
357       Object rowValue = row.get(columnName);
358       if(!columnMatcher.matches(getTable(), columnName, patValue, rowValue)) {
359         return false;
360       }
361     }
362 
363     return true;    
364   }
365   
366   private boolean findPotentialRow(Object[] rowValues, boolean requireMatch)
367     throws IOException
368   {
369     _entryCursor.beforeEntry(rowValues);
370     IndexData.Entry startEntry = _entryCursor.getNextEntry();
371     if(requireMatch && !startEntry.getRowId().isValid()) {
372       // at end of index, no potential matches
373       return false;
374     }
375     // move to position and check it out
376     restorePosition(new IndexPosition(startEntry));
377     return true;
378   }
379 
380   @Override
381   protected Object prepareSearchInfo(ColumnImpl columnPattern, Object valuePattern)
382   {
383     // attempt to generate a lookup row for this index
384     return _entryCursor.getIndexData().constructPartialIndexRow(
385         IndexData.MIN_VALUE, columnPattern.getName(), valuePattern);
386   }
387 
388   @Override
389   protected Object prepareSearchInfo(Map<String,?> rowPattern)
390   {
391     // attempt to generate a lookup row for this index
392     return _entryCursor.getIndexData().constructPartialIndexRow(
393         IndexData.MIN_VALUE, rowPattern);
394   }
395 
396   @Override
397   protected boolean keepSearching(ColumnMatcher columnMatcher, 
398                                   Object searchInfo) 
399     throws IOException
400   {
401     if(searchInfo instanceof Object[]) {
402       // if we have a lookup row for this index, then we only need to continue
403       // searching while we are looking at rows which match the index lookup
404       // value(s).  once we move past those rows, no other rows could possibly
405       // match.
406       return currentRowMatchesEntryImpl((Object[])searchInfo, columnMatcher);
407     }
408     // we are doing a full table scan
409     return true;
410   }
411 
412   private Object[] toRowValues(Object[] entryValues)
413   {
414     return _entryCursor.getIndexData().constructPartialIndexRowFromEntry(
415         IndexData.MIN_VALUE, entryValues);
416   }
417   
418   @Override
419   protected PositionImpl findAnotherPosition(
420       RowState rowState, PositionImpl curPos, boolean moveForward)
421     throws IOException
422   {
423     IndexDirHandler handler = getDirHandler(moveForward);
424     IndexPosition endPos = (IndexPosition)handler.getEndPosition();
425     IndexData.Entry entry = handler.getAnotherEntry();
426     return ((!entry.equals(endPos.getEntry())) ?
427             new IndexPosition(entry) : endPos);
428   }
429 
430   @Override
431   protected ColumnMatcher getDefaultColumnMatcher() {
432     if(getIndex().isUnique()) {
433       // text indexes are case-insensitive, therefore we should always use a
434       // case-insensitive matcher for unique indexes.
435       return CaseInsensitiveColumnMatcher.INSTANCE;
436     }
437     return SimpleColumnMatcher.INSTANCE;
438   }
439 
440   /**
441    * Handles moving the table index cursor in a given direction.  Separates
442    * cursor logic from value storage.
443    */
444   private abstract class IndexDirHandler extends DirHandler {
445     public abstract IndexData.Entry getAnotherEntry()
446       throws IOException;
447   }
448     
449   /**
450    * Handles moving the table index cursor forward.
451    */
452   private final class ForwardIndexDirHandler extends IndexDirHandler {
453     @Override
454     public PositionImpl getBeginningPosition() {
455       return getFirstPosition();
456     }
457     @Override
458     public PositionImpl getEndPosition() {
459       return getLastPosition();
460     }
461     @Override
462     public IndexData.Entry getAnotherEntry() throws IOException {
463       return _entryCursor.getNextEntry();
464     }
465   }
466     
467   /**
468    * Handles moving the table index cursor backward.
469    */
470   private final class ReverseIndexDirHandler extends IndexDirHandler {
471     @Override
472     public PositionImpl getBeginningPosition() {
473       return getLastPosition();
474     }
475     @Override
476     public PositionImpl getEndPosition() {
477       return getFirstPosition();
478     }
479     @Override
480     public IndexData.Entry getAnotherEntry() throws IOException {
481       return _entryCursor.getPreviousEntry();
482     }
483   }    
484     
485   /**
486    * Value object which maintains the current position of an IndexCursor.
487    */
488   private static final class IndexPosition extends PositionImpl
489   {
490     private final IndexData.Entry _entry;
491     
492     private IndexPosition(IndexData.Entry entry) {
493       _entry = entry;
494     }
495 
496     @Override
497     public RowIdImpl getRowId() {
498       return getEntry().getRowId();
499     }
500     
501     public IndexData.Entry getEntry() {
502       return _entry;
503     }
504     
505     @Override
506     protected boolean equalsImpl(Object o) {
507       return getEntry().equals(((IndexPosition)o).getEntry());
508     }
509 
510     @Override
511     public String toString() {
512       return "Entry = " + getEntry();
513     }
514   }
515 
516   /**
517    * Row iterator (by matching entry) for this cursor, modifiable.
518    */
519   private final class EntryIterator extends BaseIterator
520   {
521     private final Object[] _rowValues;
522     
523     private EntryIterator(Collection<String> columnNames, Object[] rowValues,
524                           ColumnMatcher columnMatcher)
525     {
526       super(columnNames, false, MOVE_FORWARD, columnMatcher);
527       _rowValues = rowValues;
528       try {
529         _hasNext = findFirstRowByEntryImpl(rowValues, true, _columnMatcher);
530         _validRow = _hasNext;
531       } catch(IOException e) {
532           throw new RuntimeIOException(e);
533       }
534     }
535 
536     @Override
537     protected boolean findNext() throws IOException {
538       return (moveToNextRow() && 
539               currentRowMatchesEntryImpl(_rowValues, _colMatcher));
540     }    
541   }
542 
543 }