public class Cache {
    private static int RowsPerPage;
    // DATAPAGE STRUCT
    public struct DataPage {
      public DataTable table;
      private int lowestIndex;
      private int highestIndex;
      public DataPage( DataTable table, int rowIndex ) {
        this.table = table;
        lowestIndex = MapToLowerBoundary( rowIndex );
        highestIndex = MapToUpperBoundary( rowIndex );
        System.Diagnostics.Debug.Assert( lowestIndex >= 0 );
        System.Diagnostics.Debug.Assert( highestIndex >= 0 );
      }
      public int LowestIndex {
        get { return lowestIndex; }
      }
      public int HighestIndex {
        get { return highestIndex; }
      }
      public static int MapToLowerBoundary( int rowIndex ) {
        // Return lowest index of a page containing given index.
        return ( rowIndex / RowsPerPage ) * RowsPerPage;
      }
      private static int MapToUpperBoundary( int rowIndex ) {
        // Return highest index of a page containing given index.
        return MapToLowerBoundary( rowIndex ) + RowsPerPage - 1;
      }
    } // END DATAPAGE STRUCT
    private DataPage[] cachePages;
    private IDataPageRetriever dataSupply;
    public Cache( IDataPageRetriever dataSupplier, int rowsPerPage ) {
      dataSupply = dataSupplier;
      Cache.RowsPerPage = rowsPerPage;
      LoadFirstTwoPages();
    }
    public Cache( IDataPageRetriever dataSupplier, int rowsPerPage, int rowIndex ) {
      dataSupply = dataSupplier;
      Cache.RowsPerPage = rowsPerPage;
      LoadTwoPages( rowIndex );
    }
    // Sets the value of the element parameter if the value is in the cache.
    private bool IfPageCached_ThenSetElement( int rowIndex, int columnIndex, ref string element ) {
      if ( IsRowCachedInPage( 0, rowIndex ) ) {
        // System.Diagnostics.Debug.Assert( columnIndex < cachePages[0].table.Columns.Count );
        if ( columnIndex < cachePages[0].table.Columns.Count ) {
          element = cachePages[0].table.Rows[rowIndex % RowsPerPage][columnIndex].ToString();
          return true;
        }
      }
      else if ( IsRowCachedInPage( 1, rowIndex ) ) {
        if ( columnIndex < cachePages[0].table.Columns.Count ) {
          element = cachePages[1].table.Rows[rowIndex % RowsPerPage][columnIndex].ToString();
          return true;
        }
      }
      return false;
    }
    public string RetrieveElement( int rowIndex, int columnIndex ) {
      string element = null;
      if ( IfPageCached_ThenSetElement( rowIndex, columnIndex, ref element ) ) {
        return element;
      }
      else {
        return RetrieveData_CacheIt_ThenReturnElement( rowIndex, columnIndex );
      }
    }
    private void LoadTwoPages( int rowIndex ) {
      cachePages = new DataPage[] {
        new DataPage( dataSupply.SupplyPageOfData( DataPage.MapToLowerBoundary(rowIndex), RowsPerPage), rowIndex ), 
        new DataPage( dataSupply.SupplyPageOfData( DataPage.MapToLowerBoundary(rowIndex + RowsPerPage), RowsPerPage), 
                                                   rowIndex + RowsPerPage )
      };
    }
    private void LoadFirstTwoPages() {
      cachePages = new DataPage[] {
        new DataPage( dataSupply.SupplyPageOfData( DataPage.MapToLowerBoundary(0), RowsPerPage), 0 ), 
        new DataPage( dataSupply.SupplyPageOfData( DataPage.MapToLowerBoundary(RowsPerPage), RowsPerPage), RowsPerPage )
      };
    }
    public string RetrieveData_CacheIt_ThenReturnElement( int rowIndex, int columnIndex ) {
      // Retrieve a page of data containing the requested value.
      DataTable table = dataSupply.SupplyPageOfData( DataPage.MapToLowerBoundary( rowIndex ), RowsPerPage );
      // Replace cached page farthest from requested cell with new page containing newly retrieved data.
      cachePages[GetIndexToUnusedPage( rowIndex )] = new DataPage( table, rowIndex );
      return RetrieveElement( rowIndex, columnIndex );
    }
    // Return index of cached page farthest from given index so least likely to be reused.
    private int GetIndexToUnusedPage( int rowIndex ) {
      if ( rowIndex > cachePages[0].HighestIndex && rowIndex > cachePages[1].HighestIndex ) {
        int offsetFromPage0 = rowIndex - cachePages[0].HighestIndex;
        int offsetFromPage1 = rowIndex - cachePages[1].HighestIndex;
        if ( offsetFromPage0 < offsetFromPage1 ) {
          return 1;
        }
        return 0;
      }
      else {
        int offsetFromPage0 = cachePages[0].LowestIndex - rowIndex;
        int offsetFromPage1 = cachePages[1].LowestIndex - rowIndex;
        if ( offsetFromPage0 < offsetFromPage1 ) {
          return 1;
        }
        return 0;
      }
    }
    // Return value indicating whether given row index is in given DataPage. 
    private bool IsRowCachedInPage( int pageNumber, int rowIndex ) {
      return rowIndex <= cachePages[pageNumber].HighestIndex &&
             rowIndex >= cachePages[pageNumber].LowestIndex &&
             ( rowIndex % RowsPerPage ) < cachePages[pageNumber].table.Rows.Count;
    }
  }