refactor Index into abstract base class with SimpleIndex implementation to allow for phased introduction of BigIndex support

git-svn-id: https://svn.code.sf.net/p/jackcess/code/jackcess/trunk@304 f203690c-595d-4dc9-a70b-905162fa7fd2

1 files changed, 471 insertions, 0 deletions

diff --git a/src/java/com/healthmarketscience/jackcess/SimpleIndex.java b/src/java/com/healthmarketscience/jackcess/SimpleIndex.java
new file mode 100644
index 0000000..0d77aa1
--- /dev/null
+++ b/src/java/com/healthmarketscience/jackcess/SimpleIndex.java
@@ -0,0 +1,471 @@
+/*
+Copyright (c) 2005 Health Market Science, Inc.
+
+This library is free software; you can redistribute it and/or
+modify it under the terms of the GNU Lesser General Public
+License as published by the Free Software Foundation; either
+version 2.1 of the License, or (at your option) any later version.
+
+This library is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+Lesser General Public License for more details.
+
+You should have received a copy of the GNU Lesser General Public
+License along with this library; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307
+USA
+
+You can contact Health Market Science at info@healthmarketscience.com
+or at the following address:
+
+Health Market Science
+2700 Horizon Drive
+Suite 200
+King of Prussia, PA 19406
+*/
+
+package com.healthmarketscience.jackcess;
+
+import java.io.IOException;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+
+
+/**
+ * Simple implementation of an Access table index
+ * @author Tim McCune
+ */
+public class SimpleIndex extends Index {
+
+  /** data for the single index page.  if this data came from multiple pages,
+      the index is read-only. */
+  private SimpleDataPage _dataPage;
+  
+  public SimpleIndex(Table table, int uniqueEntryCount,
+                     int uniqueEntryCountOffset)
+  {
+    super(table, uniqueEntryCount, uniqueEntryCountOffset);
+  }
+
+  private List<Entry> getEntries() {
+    return _dataPage.getEntries();
+  }
+  
+  @Override
+  protected int getEntryCount()
+    throws IOException
+  {
+    initialize();
+    return getEntries().size();
+  }
+
+  @Override
+  protected void updateImpl() throws IOException {
+    writeDataPage(_dataPage);
+  }
+
+  /**
+   * Reads the actual index entries.
+   */
+  @Override
+  protected void readIndexEntries()
+    throws IOException
+  {
+    // find first leaf page
+    int nextPageNumber = getRootPageNumber();
+    SimpleDataPage indexPage = null;
+    while(true) {
+      indexPage = new SimpleDataPage(nextPageNumber);
+      readDataPage(indexPage);
+
+      if(!indexPage.isLeaf()) {
+        // FIXME we can't modify this index at this point in time
+        setReadOnly();
+
+        // found another node page
+        nextPageNumber = indexPage.getEntries().get(0).getSubPageNumber();
+        indexPage = null;
+      } else {
+        // found first leaf
+        break;
+      }
+    }
+
+    // save the first leaf page
+    _dataPage = indexPage;
+    
+    // read all leaf pages.
+    while(indexPage.getNextPageNumber() != INVALID_INDEX_PAGE_NUMBER) {
+        
+      // FIXME we can't modify this index at this point in time
+      setReadOnly();
+        
+      // found another one
+      indexPage = new SimpleDataPage(indexPage.getNextPageNumber());
+      readDataPage(indexPage);
+
+      // since we read all the entries in sort order, we can insert them
+      // directly into the entries list
+      _dataPage.getEntries().addAll(indexPage.getEntries());
+      int totalSize = (_dataPage.getTotalEntrySize() +
+                       indexPage.getTotalEntrySize());
+      _dataPage.setTotalEntrySize(totalSize);
+    }
+
+    // check the entry order, just to be safe
+    List<Entry> entries = _dataPage.getEntries();
+    for(int i = 0; i < (entries.size() - 1); ++i) {
+      Entry e1 = entries.get(i);
+      Entry e2 = entries.get(i + 1);
+      if(e1.compareTo(e2) > 0) {
+        throw new IOException("Unexpected order in index entries, " +
+                              e1 + " is greater than " + e2);
+      }
+    }
+  }
+
+  @Override
+  protected EntryCursor cursor(Position startPos, Position endPos)
+  {
+    return new SimpleEntryCursor(startPos, endPos);
+  }
+  
+  /**
+   * Finds the index of given entry in the entries list.
+   * @return the index if found, (-<insertion_point> - 1) if not found
+   */
+  private int findEntry(Entry entry) {
+    return Collections.binarySearch(getEntries(), entry);
+  }
+
+  /**
+   * Adds an entry to the entries list, maintaining the order.
+   */
+  @Override
+  protected boolean addEntry(Entry newEntry, boolean isNullEntry, Object[] row)
+    throws IOException
+  {
+    int idx = findEntry(newEntry);
+    if(idx < 0) {
+      // this is a new entry
+      idx = missingIndexToInsertionPoint(idx);
+
+      // determine if the addition of this entry would break the uniqueness
+      // constraint.  See isUnique() for some notes about uniqueness as
+      // defined by Access.
+      boolean isDupeEntry =
+        (((idx > 0) &&
+          newEntry.equalsEntryBytes(getEntries().get(idx - 1))) ||
+          ((idx < getEntries().size()) &&
+           newEntry.equalsEntryBytes(getEntries().get(idx))));
+      if(isUnique() && !isNullEntry && isDupeEntry)
+      {
+        throw new IOException(
+            "New row " + Arrays.asList(row) +
+            " violates uniqueness constraint for index " + this);
+      }
+
+      if(!isDupeEntry) {
+        addedUniqueEntry();
+      }
+      
+      getEntries().add(idx, newEntry);
+      return true;
+    }
+    return false;
+  }
+
+  /**
+   * Removes an entry from the entries list, maintaining the order.  Will
+   * search by RowId if entry is not found in case a partial entry was
+   * provided.
+   */
+  @Override
+  protected boolean removeEntry(Entry oldEntry)
+  {
+    int idx = findEntry(oldEntry);
+    boolean removed = false;
+    if(idx < 0) {
+      // the caller may have only read some of the row data, if this is the
+      // case, just search for the page/row numbers
+      for(Iterator<Entry> iter = getEntries().iterator(); iter.hasNext(); ) {
+        Entry entry = iter.next();
+        if(entry.getRowId().equals(oldEntry.getRowId())) {
+          iter.remove();
+          removed = true;
+          break;
+        }
+      }
+    } else {
+      // found it!
+      getEntries().remove(idx);
+      removed = true;
+    }
+    
+    return removed;
+  }
+    
+
+  /**
+   * Utility class to traverse the entries in the Index.  Remains valid in the
+   * face of index entry modifications.
+   */
+  protected final class SimpleEntryCursor extends EntryCursor
+  {
+    /** handler for moving the page cursor forward */
+    private final DirHandler _forwardDirHandler = new ForwardDirHandler();
+    /** handler for moving the page cursor backward */
+    private final DirHandler _reverseDirHandler = new ReverseDirHandler();
+    /** the first valid index for this cursor */
+    private int _minIndex;
+    /** the last valid index for this cursor */
+    private int _maxIndex;
+
+    private SimpleEntryCursor(Position firstPos, Position lastPos) {
+      super(firstPos, lastPos);
+      reset();
+    }
+
+    /**
+     * Returns the DirHandler for the given direction
+     */
+    private DirHandler getDirHandler(boolean moveForward) {
+      return (moveForward ? _forwardDirHandler : _reverseDirHandler);
+    }
+
+    @Override
+    protected Position getFirstPosition(boolean moveForward) {
+      return getDirHandler(moveForward).getBeginningPosition();
+    }
+
+    @Override
+    protected void updateBounds() {
+      int idx = findEntry(_firstPos.getEntry());
+      if(idx < 0) {
+        idx = missingIndexToInsertionPoint(idx);
+      }
+      _minIndex = idx;
+
+      idx = findEntry(_lastPos.getEntry());
+      if(idx < 0) {
+        idx = missingIndexToInsertionPoint(idx) - 1;
+      }
+      _maxIndex = idx;
+    }
+    
+    @Override
+    protected Position updatePosition(Entry entry) {
+      if(entry.isValid()) {
+        
+        // find the new position for this entry
+        int curIdx = findEntry(entry);
+        boolean between = false;
+        if(curIdx < 0) {
+          // given entry was not found exactly.  our current position is now
+          // really between two indexes, but we cannot support that as an
+          // integer value so we set a flag instead
+          curIdx = missingIndexToInsertionPoint(curIdx);
+          between = true;
+        }
+
+        if(curIdx < _minIndex) {
+          curIdx = _minIndex;
+          between = true;
+        } else if(curIdx > _maxIndex) {
+          curIdx = _maxIndex + 1;
+          between = true;
+        }
+        
+        return new Position(getRootPageNumber(), curIdx, entry, between);
+        
+      } else if(entry.equals(_firstPos.getEntry())) {
+        return _firstPos;
+      } else if(entry.equals(_lastPos.getEntry())) {
+        return _lastPos;
+      } else {
+        throw new IllegalArgumentException("Invalid entry given: " + entry);
+      }
+    }
+    
+    /**
+     * Gets another entry in the given direction, returning the new entry.
+     */
+    @Override
+    protected Entry getAnotherEntry(boolean moveForward) {
+      DirHandler handler = getDirHandler(moveForward);
+      if(_curPos.equals(handler.getEndPosition())) {
+        if(!isUpToDate()) {
+          restorePosition(_prevPos.getEntry());
+          // drop through and retry moving to another entry
+        } else {
+          // at end, no more
+          return _curPos.getEntry();
+        }
+      }
+
+      checkForModification();
+
+      _prevPos = _curPos;
+      _curPos = handler.getAnotherPosition(_curPos.getIndex(),
+                                           _curPos.isBetween());
+      return _curPos.getEntry();
+    }
+
+    @Override
+    public String toString() {
+      return getClass().getSimpleName() + " CurPosition " + _curPos +
+        ", PrevPosition " + _prevPos;
+    }
+    
+    /**
+     * Handles moving the cursor in a given direction.  Separates cursor
+     * logic from value storage.
+     */
+    private abstract class DirHandler {
+      public abstract Position getAnotherPosition(int curIdx, boolean between);
+      public abstract Position getBeginningPosition();
+      public abstract Position getEndPosition();
+      protected final Position newPosition(int curIdx) {
+        return new Position(getRootPageNumber(), curIdx,
+                            getEntries().get(curIdx));
+      }
+      protected final Position newForwardPosition(int curIdx) {
+        return((curIdx <= _maxIndex) ?
+               newPosition(curIdx) : _lastPos);
+      }
+      protected final Position newReversePosition(int curIdx) {
+        return ((curIdx >= _minIndex) ?
+                newPosition(curIdx) : _firstPos);
+      }
+    }
+        
+    /**
+     * Handles moving the cursor forward.
+     */
+    private final class ForwardDirHandler extends DirHandler {
+      @Override
+      public Position getAnotherPosition(int curIdx, boolean between) {
+        // note, curIdx does not need to be advanced if it was pointing at a
+        // between position
+        if(!between) {
+          curIdx = ((curIdx == getBeginningPosition().getIndex()) ?
+                    _minIndex : (curIdx + 1));
+        }
+        return newForwardPosition(curIdx);
+      }
+      @Override
+      public Position getBeginningPosition() {
+        return _firstPos;
+      }
+      @Override
+      public Position getEndPosition() {
+        return _lastPos;
+      }
+    }
+        
+    /**
+     * Handles moving the cursor backward.
+     */
+    private final class ReverseDirHandler extends DirHandler {
+      @Override
+      public Position getAnotherPosition(int curIdx, boolean between) {
+        // note, we ignore the between flag here because the index will be
+        // pointing at the correct next index in either the between or
+        // non-between case
+        curIdx = ((curIdx == getBeginningPosition().getIndex()) ?
+                  _maxIndex : (curIdx - 1));
+        return newReversePosition(curIdx);
+      }
+      @Override
+      public Position getBeginningPosition() {
+        return _lastPos;
+      }
+      @Override
+      public Position getEndPosition() {
+        return _firstPos;
+      }
+    }
+  }
+
+  /**
+   * Simple implementation of a DataPage
+   */
+  private static final class SimpleDataPage extends DataPage {
+    private final int _pageNumber;
+    private boolean _leaf;
+    private int _nextPageNumber;
+    private int _totalEntrySize;
+    private List<Entry> _entries;
+
+    private SimpleDataPage(int pageNumber) {
+      _pageNumber = pageNumber;
+    }
+    
+    @Override
+    public int getPageNumber() {
+      return _pageNumber;
+    }
+    
+    @Override
+    public boolean isLeaf() {
+      return _leaf;
+    }
+    @Override
+    public void setLeaf(boolean isLeaf) {
+      _leaf = isLeaf;
+    }
+
+    @Override
+    public int getPrevPageNumber() { return 0; }
+    @Override
+    public void setPrevPageNumber(int pageNumber) {
+      // ignored
+    }
+    @Override
+    public int getNextPageNumber() {
+      return _nextPageNumber;
+    }
+    @Override
+    public void setNextPageNumber(int pageNumber) {
+      _nextPageNumber = pageNumber;
+    }
+    @Override
+    public int getChildTailPageNumber() { return 0; }
+    @Override
+    public void setChildTailPageNumber(int pageNumber) {
+      // ignored
+    }
+    
+    @Override
+    public int getTotalEntrySize() {
+      return _totalEntrySize;
+    }
+    @Override
+    public void setTotalEntrySize(int totalSize) {
+      _totalEntrySize = totalSize;
+    }
+    @Override
+    public byte[] getEntryPrefix() {
+      return EMPTY_PREFIX;
+    }
+    @Override
+    public void setEntryPrefix(byte[] entryPrefix) {
+      // ignored
+    }
+
+    @Override
+    public List<Entry> getEntries() {
+      return _entries;
+    }
+    
+    @Override
+    public void setEntries(List<Entry> entries) {
+      
+      _entries = entries;
+    }
+  }
+  
+}