From 01c8f369cfa93ac9fbe54f177006fa29d846d3e7 Mon Sep 17 00:00:00 2001 From: James Ahlborn Date: Wed, 21 Nov 2007 15:10:48 +0000 Subject: [PATCH] add reverse cursor traversal git-svn-id: https://svn.code.sf.net/p/jackcess/code/jackcess/trunk@179 f203690c-595d-4dc9-a70b-905162fa7fd2 --- .../healthmarketscience/jackcess/Cursor.java | 216 +++++++++++++++--- .../healthmarketscience/jackcess/Table.java | 14 +- .../jackcess/UsageMap.java | 214 ++++++++++++----- .../jackcess/CursorTest.java | 28 ++- 4 files changed, 369 insertions(+), 103 deletions(-) diff --git a/src/java/com/healthmarketscience/jackcess/Cursor.java b/src/java/com/healthmarketscience/jackcess/Cursor.java index e0ae0a7..600396a 100644 --- a/src/java/com/healthmarketscience/jackcess/Cursor.java +++ b/src/java/com/healthmarketscience/jackcess/Cursor.java @@ -29,8 +29,8 @@ import static com.healthmarketscience.jackcess.RowId.INVALID_ROW_NUMBER; */ public abstract class Cursor implements Iterable> { - private static final int FIRST_PAGE_NUMBER = INVALID_PAGE_NUMBER; - private static final int LAST_PAGE_NUMBER = Integer.MAX_VALUE; + public static final int FIRST_PAGE_NUMBER = INVALID_PAGE_NUMBER; + public static final int LAST_PAGE_NUMBER = Integer.MAX_VALUE; public static final RowId FIRST_ROW_ID = new RowId( FIRST_PAGE_NUMBER, INVALID_ROW_NUMBER); @@ -44,11 +44,11 @@ public abstract class Cursor implements Iterable> /** State used for reading the table rows */ protected final RowState _rowState; /** the first (exclusive) row id for this iterator */ - protected final RowId _firstRowId; + private final RowId _firstRowId; /** the last (exclusive) row id for this iterator */ - protected final RowId _lastRowId; + private final RowId _lastRowId; /** the current row */ - protected RowId _currentRowId; + private RowId _currentRowId; protected Cursor(Table table, RowId firstRowId, RowId lastRowId) { @@ -78,7 +78,10 @@ public abstract class Cursor implements Iterable> return getTable().getPageChannel(); } - + public RowId getCurrentRowId() { + return _currentRowId; + } + /** * Returns the first row id (exclusive) as defined by this cursor. */ @@ -92,12 +95,54 @@ public abstract class Cursor implements Iterable> protected RowId getLastRowId() { return _lastRowId; } - + + /** + * Resets this cursor for forward iteration. Calls {@link #beforeFirst}. + */ public void reset() { - _currentRowId = getFirstRowId(); + beforeFirst(); + } + + /** + * Resets this cursor for forward iteration (sets cursor to before the first + * row). + */ + public void beforeFirst() { + reset(true); + } + + /** + * Resets this cursor for reverse iteration (sets cursor to after the last + * row). + */ + public void afterLast() { + reset(false); + } + + /** + * Resets this cursor for iterating the given direction. + */ + protected void reset(boolean moveForward) { + _currentRowId = getBeginningRowId(moveForward); _rowState.reset(); } + protected final RowId getEndRowId(boolean moveForward) { + return (moveForward ? getLastRowId() : getFirstRowId()); + } + + protected final RowId getBeginningRowId(boolean moveForward) { + return (moveForward ? getFirstRowId() : getLastRowId()); + } + + /** + * Returns {@code true} if the cursor is currently pointing at a valid row, + * {@code false} otherwise. + */ + public boolean isCurrentRowValid() { + return _currentRowId.isValidRow(); + } + /** * Calls reset on this table and returns a modifiable Iterator * which will iterate through all the rows of this table. Use of the @@ -145,11 +190,41 @@ public abstract class Cursor implements Iterable> public Map getNextRow(Collection columnNames) throws IOException { - if(moveToNextRow()) { + return getNextRow(columnNames, true); + } + + /** + * @return The previous row in this table (Column name -> Column value) + */ + public Map getPreviousRow() throws IOException { + return getPreviousRow(null); + } + + /** + * @param columnNames Only column names in this collection will be returned + * @return The previous row in this table (Column name -> Column value) + */ + public Map getPreviousRow(Collection columnNames) + throws IOException + { + return getNextRow(columnNames, false); + } + + + /** + * @param columnNames Only column names in this collection will be returned + * @return The next row in this table (Column name -> Column value), where + * "next" may be backwards if moveForward is {@code false}. + */ + private Map getNextRow(Collection columnNames, + boolean moveForward) + throws IOException + { + if(moveToNextRow(moveForward)) { return getCurrentRow(columnNames); } return null; - } + } /** * Moves to the next row as defined by this cursor. @@ -159,14 +234,37 @@ public abstract class Cursor implements Iterable> public boolean moveToNextRow() throws IOException { - if(_currentRowId.equals(getLastRowId())) { + return moveToNextRow(true); + } + + /** + * Moves to the previous row as defined by this cursor. + * @return {@code true} if a valid previous row was found, {@code false} + * otherwise + */ + public boolean moveToPreviousRow() + throws IOException + { + return moveToNextRow(false); + } + + /** + * Moves to the next row as defined by this cursor. + * @return {@code true} if a valid next row was found, {@code false} + * otherwise + */ + private boolean moveToNextRow(boolean moveForward) + throws IOException + { + RowId endRowId = getEndRowId(moveForward); + if(_currentRowId.equals(endRowId)) { // already at end return false; } _rowState.reset(); - _currentRowId = findNextRowId(_currentRowId); - return(!_currentRowId.equals(getLastRowId())); + _currentRowId = findNextRowId(_currentRowId, moveForward, endRowId); + return(!_currentRowId.equals(endRowId)); } /** @@ -178,9 +276,10 @@ public abstract class Cursor implements Iterable> * {@code false} if no row was found (and the cursor is now pointing * past the end of the table) */ - public boolean moveToRow(Column column, Object value) + public boolean findRow(Column column, Object value) throws IOException { + beforeFirst(); while(moveToNextRow()) { if(ObjectUtils.equals(value, getCurrentRowSingleColumn(column))) { return true; @@ -198,11 +297,13 @@ public abstract class Cursor implements Iterable> * {@code false} if no row was found (and the cursor is now pointing * past the end of the table) */ - public boolean moveToRow(Map row) + public boolean findRow(Map row) throws IOException { + beforeFirst(); while(moveToNextRow()) { - if(ObjectUtils.equals(row, getCurrentRow(row.keySet()))) { + Object value = getCurrentRow(row.keySet()); + if(ObjectUtils.equals(row, value)) { return true; } } @@ -213,7 +314,21 @@ public abstract class Cursor implements Iterable> * Skips as many rows as possible up to the given number of rows. * @return the number of rows skipped. */ - public int skipRows(int numRows) + public int skipNextRows(int numRows) + throws IOException + { + int numSkippedRows = 0; + while((numSkippedRows < numRows) && moveToNextRow()) { + ++numSkippedRows; + } + return numSkippedRows; + } + + /** + * Skips as many rows as possible up to the given number of rows. + * @return the number of rows skipped. + */ + public int skipPreviousRows(int numRows) throws IOException { int numSkippedRows = 0; @@ -223,6 +338,21 @@ public abstract class Cursor implements Iterable> return numSkippedRows; } + /** + * Skips as many rows as possible in the given direction up to the given + * number of rows. + * @return the number of rows skipped. + */ + private int skipRows(int numRows, boolean moveForward) + throws IOException + { + int numSkippedRows = 0; + while((numSkippedRows < numRows) && moveToNextRow(moveForward)) { + ++numSkippedRows; + } + return numSkippedRows; + } + /** * Returns the current row in this cursor (Column name -> Column value). * @param columnNames Only column names in this collection will be returned @@ -284,11 +414,15 @@ public abstract class Cursor implements Iterable> } /** - * Finds the next non-deleted row after the given row as defined by this - * cursor and returns the id of the row. If there are no more rows, the - * returned rowId should equal the value returned by {@link #getLastRowId}. + * Finds the next non-deleted row after the given row (as defined by this + * cursor) and returns the id of the row, where "next" may be backwards if + * moveForward is {@code false}. If there are no more rows, the returned + * rowId should equal the value returned by {@link #getLastRowId} if moving + * forward and {@link #getFirstRowId} if moving backward. */ - protected abstract RowId findNextRowId(RowId currentRowId) + protected abstract RowId findNextRowId(RowId currentRowId, + boolean moveForward, + RowId endRowId) throws IOException; /** @@ -335,6 +469,19 @@ public abstract class Cursor implements Iterable> } + protected abstract class DirHandler + { + public abstract RowId getBeginningRowId(); + public abstract RowId getEndRowId(); + } + + protected abstract class ForwardDirHandler + { + public abstract RowId getBeginningRowId(); + public abstract RowId getEndRowId(); + } + + /** * Simple un-indexed cursor. */ @@ -349,9 +496,9 @@ public abstract class Cursor implements Iterable> } @Override - public void reset() { - _ownedPagesIterator.reset(); - super.reset(); + protected void reset(boolean moveForward) { + _ownedPagesIterator.reset(moveForward); + super.reset(moveForward); } /** @@ -359,7 +506,8 @@ public abstract class Cursor implements Iterable> * @return a ByteBuffer narrowed to the next row, or null if none */ @Override - protected RowId findNextRowId(RowId currentRowId) + protected RowId findNextRowId(RowId currentRowId, boolean moveForward, + RowId endRowId) throws IOException { @@ -370,28 +518,35 @@ public abstract class Cursor implements Iterable> int rowsOnPage = getRowsOnCurrentDataPage( _rowState.setRow(currentPageNumber, currentRowNumber)); + int inc = (moveForward ? 1 : -1); // loop until we find the next valid row or run out of pages while(true) { - currentRowNumber++; - if(currentRowNumber < rowsOnPage) { + currentRowNumber += inc; + if((currentRowNumber >= 0) && (currentRowNumber < rowsOnPage)) { _rowState.setRow(currentPageNumber, currentRowNumber); } else { // load next page currentRowNumber = INVALID_ROW_NUMBER; - currentPageNumber = _ownedPagesIterator.getNextPage(); - + currentPageNumber = + (moveForward ? + _ownedPagesIterator.getNextPage() : + _ownedPagesIterator.getPreviousPage()); + ByteBuffer rowBuffer = _rowState.setRow( currentPageNumber, currentRowNumber); if(rowBuffer == null) { //No more owned pages. No more rows. - return getLastRowId(); + return endRowId; } // update row count rowsOnPage = getRowsOnCurrentDataPage(rowBuffer); + if(!moveForward) { + currentRowNumber = rowsOnPage; + } // start again from the top continue; @@ -404,6 +559,7 @@ public abstract class Cursor implements Iterable> } } + } } diff --git a/src/java/com/healthmarketscience/jackcess/Table.java b/src/java/com/healthmarketscience/jackcess/Table.java index dc064cb..0790dc1 100644 --- a/src/java/com/healthmarketscience/jackcess/Table.java +++ b/src/java/com/healthmarketscience/jackcess/Table.java @@ -40,6 +40,7 @@ import java.util.List; import java.util.Map; import java.util.NoSuchElementException; +import com.healthmarketscience.jackcess.Table.RowState; import org.apache.commons.logging.Log; import org.apache.commons.logging.LogFactory; @@ -195,10 +196,6 @@ public class Table return _ownedPages.iterator(); } - protected UsageMap.PageIterator getOwnedPagesReverseIterator() { - return _ownedPages.reverseIterator(); - } - /** * @return All of the columns in this table (unmodifiable List) */ @@ -997,10 +994,10 @@ public class Table // find last data page (Not bothering to check other pages for free // space.) - for(UsageMap.PageIterator revPageIter = _ownedPages.reverseIterator(); - revPageIter.hasNextPage(); ) + for(UsageMap.PageIterator revPageIter = _ownedPages.iteratorAtEnd(); + revPageIter.hasPreviousPage(); ) { - int tmpPageNumber = revPageIter.getNextPage(); + int tmpPageNumber = revPageIter.getPreviousPage(); getPageChannel().readPage(dataPage, tmpPageNumber); if(dataPage.get() == PageTypes.DATA) { // found last data page @@ -1511,7 +1508,8 @@ public class Table checkForModification(); _rowNumber = rowNumber; _finalRowNumber = rowNumber; - if(pageNumber == PageChannel.INVALID_PAGE_NUMBER) { + if((pageNumber == Cursor.FIRST_PAGE_NUMBER) || + (pageNumber == Cursor.LAST_PAGE_NUMBER)) { return null; } _finalRowBuffer = _rowBufferH.setPage(getPageChannel(), pageNumber); diff --git a/src/java/com/healthmarketscience/jackcess/UsageMap.java b/src/java/com/healthmarketscience/jackcess/UsageMap.java index 3305f11..07d711f 100644 --- a/src/java/com/healthmarketscience/jackcess/UsageMap.java +++ b/src/java/com/healthmarketscience/jackcess/UsageMap.java @@ -143,11 +143,13 @@ public class UsageMap } public PageIterator iterator() { - return new ForwardPageIterator(); + return new PageIterator(); } - public PageIterator reverseIterator() { - return new ReversePageIterator(); + public PageIterator iteratorAtEnd() { + PageIterator iterator = new PageIterator(); + iterator.afterLast(); + return iterator; } protected short getRowStart() { @@ -679,8 +681,12 @@ public class UsageMap * iterators hold on to page numbers, they should stay valid even as the * usage map handlers shift around the bits. */ - public abstract class PageIterator + public class PageIterator { + /** handler for moving the page iterator forward */ + private final DirHandler _forwardDirHandler = new ForwardDirHandler(); + /** handler for moving the page iterator backward */ + private final DirHandler _reverseDirHandler = new ReverseDirHandler(); /** the next used page number */ private int _nextPageNumber; /** the previous used page number */ @@ -690,26 +696,53 @@ public class UsageMap and act accordingly */ private int _lastModCount; - protected PageIterator() { + private PageIterator() { + reset(); } /** - * @return {@code true} if there is another valid page, {@code false} - * otherwise. + * Returns the DirHandler for the given direction + */ + private DirHandler getDirHandler(boolean moveForward) { + return (moveForward ? _forwardDirHandler : _reverseDirHandler); + } + + /** + * @return {@code true} if there is another valid page after the current + * page, {@code false} otherwise. */ public final boolean hasNextPage() { - if((_nextPageNumber == PageChannel.INVALID_PAGE_NUMBER) && - (_lastModCount != _modCount)) { + return hasAnotherPage(true); + } + + /** + * @return {@code true} if there is another valid page before the current + * page, {@code false} otherwise. + */ + public final boolean hasPreviousPage() { + return hasAnotherPage(false); + } + + private boolean hasAnotherPage(boolean moveForward) { + DirHandler handler = getDirHandler(moveForward); + int curPageNumber = handler.getCurrentPageNumber(); + int otherPageNumber = handler.getOtherPageNumber(); + + if((curPageNumber == PageChannel.INVALID_PAGE_NUMBER) && + (_lastModCount != UsageMap.this._modCount)) { // recheck the last page, in case more showed up - if(_prevPageNumber == PageChannel.INVALID_PAGE_NUMBER) { + if(otherPageNumber == PageChannel.INVALID_PAGE_NUMBER) { // we were at the beginning - reset(); + reset(moveForward); } else { - _lastModCount = _modCount; - _nextPageNumber = getNextPage(_prevPageNumber); + // we were at the end + _lastModCount = UsageMap.this._modCount; + handler.setCurrentPageNumber( + handler.getAnotherPageNumber(otherPageNumber)); } + curPageNumber = handler.getCurrentPageNumber(); } - return(_nextPageNumber != PageChannel.INVALID_PAGE_NUMBER); + return(curPageNumber != PageChannel.INVALID_PAGE_NUMBER); } /** @@ -717,69 +750,128 @@ public class UsageMap * {@link PageChannel#INVALID_PAGE_NUMBER} otherwise */ public final int getNextPage() { - if (hasNextPage()) { - _lastModCount = _modCount; - _prevPageNumber = _nextPageNumber; - _nextPageNumber = getNextPage(_nextPageNumber); - return _prevPageNumber; + return getAnotherPage(true); + } + + /** + * @return valid page number if there was another page to read, + * {@link PageChannel#INVALID_PAGE_NUMBER} otherwise + */ + public final int getPreviousPage() { + return getAnotherPage(false); + } + + /** + * Gets another page in the given direction, returning the current page. + */ + private int getAnotherPage(boolean moveForward) { + if (hasAnotherPage(moveForward)) { + _lastModCount = UsageMap.this._modCount; + DirHandler handler = getDirHandler(moveForward); + int anotherPage = handler.getCurrentPageNumber(); + handler.setOtherPageNumber(anotherPage); + handler.setCurrentPageNumber( + handler.getAnotherPageNumber(anotherPage)); + return anotherPage; } return PageChannel.INVALID_PAGE_NUMBER; } - + /** * After calling this method, getNextPage will return the first page in * the map */ public final void reset() { - _lastModCount = _modCount; - _prevPageNumber = PageChannel.INVALID_PAGE_NUMBER; - _nextPageNumber = getInitialPage(); + beforeFirst(); } - protected abstract int getInitialPage(); - - protected abstract int getNextPage(int curPage); - } - - /** - * Utility class to iterate forward over the pages in the UsageMap. - */ - public class ForwardPageIterator extends PageIterator - { - private ForwardPageIterator() { - reset(); + /** + * After calling this method, {@link #getNextPage} will return the first + * page in the map + */ + public void beforeFirst() { + reset(true); } - - @Override - protected int getNextPage(int curPage) { - return UsageMap.this.getNextPageNumber(curPage); + + /** + * After calling this method, {@link #getPreviousPage} will return the + * last page in the map + */ + public void afterLast() { + reset(false); } - @Override - protected int getInitialPage() { - return UsageMap.this.getFirstPageNumber(); + /** + * Resets this page iterator for iterating the given direction. + */ + protected void reset(boolean moveForward) { + _lastModCount = UsageMap.this._modCount; + getDirHandler(moveForward).reset(); } - } - - /** - * Utility class to iterate backward over the pages in the UsageMap. - */ - public class ReversePageIterator extends PageIterator - { - private ReversePageIterator() { - reset(); + + /** + * Handles moving the iterator in a given direction. Separates iterator + * logic from value storage. + */ + private abstract class DirHandler { + public abstract int getCurrentPageNumber(); + public abstract void setCurrentPageNumber(int newPageNumber); + public abstract int getOtherPageNumber(); + public abstract void setOtherPageNumber(int newPageNumber); + public abstract int getAnotherPageNumber(int curPageNumber); + public abstract void reset(); } - - @Override - protected int getNextPage(int curPage) { - return UsageMap.this.getPrevPageNumber(curPage); + + /** + * Handles moving the iterator forward. + */ + private final class ForwardDirHandler extends DirHandler { + public int getCurrentPageNumber() { + return _nextPageNumber; + } + public void setCurrentPageNumber(int newPageNumber) { + _nextPageNumber = newPageNumber; + } + public int getOtherPageNumber() { + return _prevPageNumber; + } + public void setOtherPageNumber(int newPageNumber) { + _prevPageNumber = newPageNumber; + } + public int getAnotherPageNumber(int curPageNumber) { + return UsageMap.this.getNextPageNumber(curPageNumber); + } + public void reset() { + _nextPageNumber = UsageMap.this.getFirstPageNumber(); + _prevPageNumber = PageChannel.INVALID_PAGE_NUMBER; + } } - - @Override - protected int getInitialPage() { - return UsageMap.this.getLastPageNumber(); + + /** + * Handles moving the iterator backward. + */ + private final class ReverseDirHandler extends DirHandler { + public int getCurrentPageNumber() { + return _prevPageNumber; + } + public void setCurrentPageNumber(int newPageNumber) { + _prevPageNumber = newPageNumber; + } + public int getOtherPageNumber() { + return _nextPageNumber; + } + public void setOtherPageNumber(int newPageNumber) { + _nextPageNumber = newPageNumber; + } + public int getAnotherPageNumber(int curPageNumber) { + return UsageMap.this.getPrevPageNumber(curPageNumber); + } + public void reset() { + _nextPageNumber = PageChannel.INVALID_PAGE_NUMBER; + _prevPageNumber = UsageMap.this.getLastPageNumber(); + } } - } - + + } } diff --git a/test/src/java/com/healthmarketscience/jackcess/CursorTest.java b/test/src/java/com/healthmarketscience/jackcess/CursorTest.java index 9e6c187..d527c0f 100644 --- a/test/src/java/com/healthmarketscience/jackcess/CursorTest.java +++ b/test/src/java/com/healthmarketscience/jackcess/CursorTest.java @@ -3,6 +3,7 @@ package com.healthmarketscience.jackcess; import java.util.ArrayList; +import java.util.Collections; import java.util.List; import java.util.Map; @@ -80,13 +81,13 @@ public class CursorTest extends TestCase { List> foundRows = new ArrayList>(); foundRows.add(cursor.getNextRow()); - assertEquals(3, cursor.skipRows(3)); + assertEquals(3, cursor.skipNextRows(3)); while(cursor.moveToNextRow()) { foundRows.add(cursor.getCurrentRow()); } assertEquals(expectedRows, foundRows); - assertEquals(0, cursor.skipRows(3)); + assertEquals(0, cursor.skipNextRows(3)); db.close(); } @@ -99,12 +100,12 @@ public class CursorTest extends TestCase { Cursor cursor = Cursor.createCursor(table); - assertTrue(cursor.moveToRow(table.getColumn("id"), 3)); + assertTrue(cursor.findRow(table.getColumn("id"), 3)); assertEquals(createExpectedRow("id", 3, "value", "data" + 3), cursor.getCurrentRow()); - assertTrue(cursor.moveToRow(createExpectedRow( + assertTrue(cursor.findRow(createExpectedRow( "id", 6, "value", "data" + 6))); assertEquals(createExpectedRow("id", 6, @@ -114,5 +115,24 @@ public class CursorTest extends TestCase { db.close(); } + public void testReverse() throws Exception { + Database db = createTestTable(); + + Table table = db.getTable("test"); + List> expectedRows = createTestTableData(); + Collections.reverse(expectedRows); + + Cursor cursor = Cursor.createCursor(table); + cursor.afterLast(); + List> foundRows = + new ArrayList>(); + while(cursor.moveToPreviousRow()) { + foundRows.add(cursor.getCurrentRow()); + } + assertEquals(expectedRows, foundRows); + + db.close(); + } + } -- 2.39.5