/*******************************************************************************
 * You may amend and distribute as you like, but don't remove this header!
 *
 * EPPlus provides server-side generation of Excel 2007/2010 spreadsheets.
 * See http://www.codeplex.com/EPPlus for details.
 *
 * Copyright (C) 2011  Jan Källman
 *
 * 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.
 *
 * The GNU Lesser General Public License can be viewed at http://www.opensource.org/licenses/lgpl-license.php
 * If you unfamiliar with this license or have questions about it, here is an http://www.gnu.org/licenses/gpl-faq.html
 *
 * All code and executables are provided "as is" with no warranty either express or implied.
 * The author accepts no liability for any damage or loss of business that this product may cause.
 *
 * Code change notes:
 *
 * Author							Change						Date
 * ******************************************************************************
 * Jan Källman		    Added       		        2012-11-25
 *******************************************************************************/

using System;
using System.Collections;
using System.Collections.Generic;
using OfficeOpenXml;

internal class IndexBase : IComparable<IndexBase> {
  internal short Index;

  public int CompareTo(IndexBase other) {
    return Index < other.Index
        ? -1
        : Index > other.Index
            ? 1
            : 0;
  }
}

internal class IndexItem : IndexBase {
  internal int IndexPointer { get; set; }
}

internal class ColumnIndex : IndexBase {
  private readonly IndexBase _searchIx = new();

  internal int GetPosition(int row) {
    var page = (short)(row >> CellStore<int>._pageBits);
    _searchIx.Index = page;
    var res =
        (_pages != null
                && page >= 0
                && page < PageCount
                && page < _pages.Length
                && _pages[page] != null
                && _pages[page].Index == page)
            ? page
            : Array.BinarySearch(_pages, 0, PageCount, _searchIx);
    if (res >= 0) {
      GetPage(row, ref res);
      return res;
    }
    var p = ~res;

    if (GetPage(row, ref p)) {
      return p;
    }
    return res;
  }

  private bool GetPage(int row, ref int res) {
    if (res < PageCount && _pages[res].MinIndex <= row && _pages[res].MaxIndex >= row) {
      return true;
    }
    if (res + 1 < PageCount && (_pages[res + 1].MinIndex <= row)) {
      do {
        res++;
      } while (res + 1 < PageCount && _pages[res + 1].MinIndex <= row);
      //if (res + 1 < PageCount && _pages[res + 1].MaxIndex >= Row)
      //{
      return true;
      //}
      //else
      //{
      //    return false;
      //}
    }
    if (res - 1 >= 0 && _pages[res - 1].MaxIndex >= row) {
      do {
        res--;
      } while (res - 1 > 0 && _pages[res - 1].MaxIndex >= row);
      //if (res > 0)
      //{
      return true;
      //}
      //else
      //{
      //    return false;
      //}
    }
    return false;
  }

  internal int GetNextRow(int row) {
    //var page = (int)((ulong)row >> CellStore<int>.pageBits);
    var p = GetPosition(row);
    if (p < 0) {
      p = ~p;
      if (p >= PageCount) {
        return -1;
      }
      if (_pages[p].IndexOffset + _pages[p].Rows[0].Index < row) {
        if (p + 1 >= PageCount) {
          return -1;
        }
        return _pages[p + 1].IndexOffset + _pages[p].Rows[0].Index;
      }
      return _pages[p].IndexOffset + _pages[p].Rows[0].Index;
    }
    if (p < PageCount) {
      var r = _pages[p].GetNextRow(row);
      if (r >= 0) {
        return _pages[p].IndexOffset + _pages[p].Rows[r].Index;
      } else {
        if (++p < PageCount) {
          return _pages[p].IndexOffset + _pages[p].Rows[0].Index;
        } else {
          return -1;
        }
      }
    }
    return -1;
  }

  internal PageIndex[] _pages = new PageIndex[CellStore<int>._pagesPerColumnMin];
  internal int PageCount;
}

internal class PageIndex : IndexBase {
  private readonly IndexBase _searchIx = new();

  public PageIndex() {
    Rows = new IndexItem[CellStore<int>._pageSizeMin];
    RowCount = 0;
  }

  public PageIndex(IndexItem[] rows, int count) {
    Rows = rows;
    RowCount = count;
  }

  public PageIndex(PageIndex pageItem, int start, int size)
      : this(pageItem, start, size, pageItem.Index, pageItem.Offset) {}

  public PageIndex(PageIndex pageItem, int start, int size, short index, int offset) {
    Rows = new IndexItem[CellStore<int>.GetSize(size)];
    Array.Copy(pageItem.Rows, start, Rows, 0, size);
    RowCount = size;
    Index = index;
    Offset = offset;
  }

  internal int Offset;

  internal int IndexOffset => IndexExpanded + Offset;

  internal int IndexExpanded => (Index << CellStore<int>._pageBits);

  internal IndexItem[] Rows { get; set; }

  internal int RowCount;

  internal int GetPosition(int offset) {
    _searchIx.Index = (short)offset;
    return (Rows != null
            && offset > 0
            && offset - 1 < RowCount
            && offset - 1 < Rows.Length
            && Rows[offset - 1] != null
            && Rows[offset - 1].Index == offset)
        ? offset - 1
        : Array.BinarySearch(Rows, 0, RowCount, _searchIx);
  }

  internal int GetNextRow(int row) {
    int offset = row - IndexOffset;
    var o = GetPosition(offset);
    if (o < 0) {
      o = ~o;
      if (o < RowCount) {
        return o;
      }
      return -1;
    }
    return o;
  }

  public int MinIndex {
    get {
      if (Rows.Length > 0) {
        return IndexOffset + Rows[0].Index;
      }
      return -1;
    }
  }

  public int MaxIndex {
    get {
      if (RowCount > 0) {
        return IndexOffset + Rows[RowCount - 1].Index;
      }
      return -1;
    }
  }

  public int GetIndex(int pos) {
    return IndexOffset + Rows[pos].Index;
  }
}

/// <summary>
/// This is the store for all Rows, Columns and Cells.
/// It is a Dictionary implementation that allows you to change the Key (the RowID, ColumnID or CellID )
/// </summary>
internal class CellStore<T> {
  /**** Size constants ****/
  internal const int _pageBits = 10; //13bits=8192  Note: Maximum is 13 bits since short is used (PageMax=16K)
  internal const int _pageSize = 1 << _pageBits;
  internal const int _pageSizeMin = 1 << 10;
  internal const int _pageSizeMax = _pageSize << 1; //Double page size
  internal const int _colSizeMin = 32;
  internal const int _pagesPerColumnMin = 32;

  private List<T> _values = new();
  internal ColumnIndex[] _columnIndex = new ColumnIndex[_colSizeMin];
  internal IndexBase _searchIx = new();
  internal int ColumnCount;

  ~CellStore() {
    if (_values != null) {
      _values.Clear();
      _values = null;
    }
    _columnIndex = null;
  }

  internal int GetPosition(int column) {
    _searchIx.Index = (short)column;
    return (_columnIndex != null
            && column > 0
            && column - 1 < ColumnCount
            && column - 1 < _columnIndex.Length
            && _columnIndex[column - 1] != null
            && _columnIndex[column - 1].Index == column)
        ? column - 1
        : Array.BinarySearch(_columnIndex, 0, ColumnCount, _searchIx);
  }

  internal bool GetDimension(out int fromRow, out int fromCol, out int toRow, out int toCol) {
    if (ColumnCount == 0) {
      fromRow = fromCol = toRow = toCol = 0;
      return false;
    }
    fromCol = _columnIndex[0].Index;
    var fromIndex = 0;
    if (fromCol <= 0 && ColumnCount > 1) {
      fromCol = _columnIndex[1].Index;
      fromIndex = 1;
    } else if (ColumnCount == 1 && fromCol <= 0) {
      fromRow = fromCol = toRow = toCol = 0;
      return false;
    }
    var col = ColumnCount - 1;
    while (col > 0) {
      if (_columnIndex[col].PageCount == 0
          || _columnIndex[col]._pages[0].RowCount > 1
          || _columnIndex[col]._pages[0].Rows[0].Index > 0) {
        break;
      }
      col--;
    }
    toCol = _columnIndex[col].Index;
    if (toCol == 0) {
      fromRow = fromCol = toRow = toCol = 0;
      return false;
    }
    fromRow = toRow = 0;

    for (int c = fromIndex; c < ColumnCount; c++) {
      int first,
          last;
      if (_columnIndex[c].PageCount == 0) {
        continue;
      }
      if (_columnIndex[c]._pages[0].RowCount > 0 && _columnIndex[c]._pages[0].Rows[0].Index > 0) {
        first = _columnIndex[c]._pages[0].IndexOffset + _columnIndex[c]._pages[0].Rows[0].Index;
      } else {
        if (_columnIndex[c]._pages[0].RowCount > 1) {
          first = _columnIndex[c]._pages[0].IndexOffset + _columnIndex[c]._pages[0].Rows[1].Index;
        } else if (_columnIndex[c].PageCount > 1) {
          first = _columnIndex[c]._pages[0].IndexOffset + _columnIndex[c]._pages[1].Rows[0].Index;
        } else {
          first = 0;
        }
      }
      var lp = _columnIndex[c].PageCount - 1;
      while (_columnIndex[c]._pages[lp].RowCount == 0 && lp != 0) {
        lp--;
      }
      var p = _columnIndex[c]._pages[lp];
      if (p.RowCount > 0) {
        last = p.IndexOffset + p.Rows[p.RowCount - 1].Index;
      } else {
        last = first;
      }
      if (first > 0 && (first < fromRow || fromRow == 0)) {
        fromRow = first;
      }
      if (first > 0 && (last > toRow || toRow == 0)) {
        toRow = last;
      }
    }
    if (fromRow <= 0 || toRow <= 0) {
      fromRow = fromCol = toRow = toCol = 0;
      return false;
    }
    return true;
  }

  internal int FindNext(int column) {
    var c = GetPosition(column);
    if (c < 0) {
      return ~c;
    }
    return c;
  }

  internal T GetValue(int row, int column) {
    int i = GetPointer(row, column);
    if (i >= 0) {
      return _values[i];
    }
    return default(T);
  }

  private int GetPointer(int row, int column) {
    var col = GetPosition(column);
    if (col >= 0) {
      var pos = _columnIndex[col].GetPosition(row);
      if (pos >= 0 && pos < _columnIndex[col].PageCount) {
        var pageItem = _columnIndex[col]._pages[pos];
        if (pageItem.MinIndex > row) {
          pos--;
          if (pos < 0) {
            return -1;
          }
          pageItem = _columnIndex[col]._pages[pos];
        }
        short ix = (short)(row - pageItem.IndexOffset);
        _searchIx.Index = ix;
        var cellPos =
            (pageItem.Rows != null
                    && ix > 0
                    && ix - 1 < pageItem.RowCount
                    && ix - 1 < pageItem.Rows.Length
                    && pageItem.Rows[ix - 1] != null
                    && pageItem.Rows[ix - 1].Index == ix)
                ? ix - 1
                : Array.BinarySearch(pageItem.Rows, 0, pageItem.RowCount, _searchIx);
        if (cellPos >= 0) {
          return pageItem.Rows[cellPos].IndexPointer;
        } //Cell does not exist
        return -1;
      } //Page does not exist
      return -1;
    } //Column does not exist
    return -1;
  }

  internal bool Exists(int row, int column) {
    return GetPointer(row, column) >= 0;
  }

  internal bool Exists(int row, int column, ref T value) {
    var p = GetPointer(row, column);
    if (p >= 0) {
      value = _values[p];
      return true;
    }
    return false;
  }

  internal void SetValue(int row, int column, T value) {
    var col =
        (_columnIndex != null
                && column > 0
                && column - 1 < ColumnCount
                && column - 1 < _columnIndex.Length
                && _columnIndex[column - 1] != null
                && _columnIndex[column - 1].Index == column)
            ? column - 1
            : Array.BinarySearch(
                _columnIndex,
                0,
                ColumnCount,
                new IndexBase {
                  Index = (short)(column),
                });
    var page = (short)(row >> _pageBits);
    if (col >= 0) {
      //var pos = Array.BinarySearch(_columnIndex[col].Pages, 0, _columnIndex[col].Count, new IndexBase() { Index = page });
      var pos = _columnIndex[col].GetPosition(row);
      if (pos < 0) {
        pos = ~pos;
        if (pos - 1 < 0 || _columnIndex[col]._pages[pos - 1].IndexOffset + _pageSize - 1 < row) {
          AddPage(_columnIndex[col], pos, page);
        } else {
          pos--;
        }
      }
      if (pos >= _columnIndex[col].PageCount) {
        AddPage(_columnIndex[col], pos, page);
      }
      var pageItem = _columnIndex[col]._pages[pos];
      if (pageItem.IndexOffset > row) {
        pos--;
        page--;
        if (pos < 0) {
          throw (new("Unexpected error when setting value"));
        }
        pageItem = _columnIndex[col]._pages[pos];
      }

      short ix = (short)(row - ((pageItem.Index << _pageBits) + pageItem.Offset));
      _searchIx.Index = ix;
      var cellPos =
          (pageItem.Rows != null
                  && ix >= 0
                  && ix < pageItem.RowCount
                  && ix < pageItem.Rows.Length
                  && pageItem.Rows[ix] != null
                  && pageItem.Rows[ix].Index == ix)
              ? ix
              : Array.BinarySearch(pageItem.Rows, 0, pageItem.RowCount, _searchIx);
      if (cellPos < 0) {
        cellPos = ~cellPos;
        AddCell(_columnIndex[col], pos, cellPos, ix, value);
      } else {
        _values[pageItem.Rows[cellPos].IndexPointer] = value;
      }
    } else //Column does not exist
    {
      col = ~col;
      AddColumn(col, column);
      AddPage(_columnIndex[col], 0, page);
      short ix = (short)(row - (page << _pageBits));
      AddCell(_columnIndex[col], 0, 0, ix, value);
    }
  }

  internal void Insert(int fromRow, int fromCol, int rows, int columns) {
    if (columns > 0) {
      var col = GetPosition(fromCol);
      if (col < 0) {
        col = ~col;
      }
      for (var c = col; c < ColumnCount; c++) {
        _columnIndex[c].Index += (short)columns;
      }
    } else {
      var page = fromRow >> _pageBits;
      for (int c = 0; c < ColumnCount; c++) {
        var column = _columnIndex[c];
        var pagePos = column.GetPosition(fromRow);
        if (pagePos >= 0) {
          if (fromRow >= column._pages[pagePos].MinIndex
              && fromRow
                  <= column._pages[pagePos].MaxIndex) //The row is inside the page
          {
            int offset = fromRow - column._pages[pagePos].IndexOffset;
            var rowPos = column._pages[pagePos].GetPosition(offset);
            if (rowPos < 0) {
              rowPos = ~rowPos;
            }
            UpdateIndexOffset(column, pagePos, rowPos, fromRow, rows);
          } else if (column._pages[pagePos].MinIndex > fromRow - 1
              && pagePos
                  > 0) //The row is on the page before.
          {
            int offset = fromRow - ((page - 1) << _pageBits);
            var rowPos = column._pages[pagePos - 1].GetPosition(offset);
            if (rowPos > 0 && pagePos > 0) {
              UpdateIndexOffset(column, pagePos - 1, rowPos, fromRow, rows);
            }
          } else if (column.PageCount >= pagePos + 1) {
            int offset = fromRow - column._pages[pagePos].IndexOffset;
            var rowPos = column._pages[pagePos].GetPosition(offset);
            if (rowPos < 0) {
              rowPos = ~rowPos;
            }
            if (column._pages[pagePos].RowCount > rowPos) {
              UpdateIndexOffset(column, pagePos, rowPos, fromRow, rows);
            } else {
              UpdateIndexOffset(column, pagePos + 1, 0, fromRow, rows);
            }
          }
        } else {
          UpdateIndexOffset(column, ~pagePos, 0, fromRow, rows);
        }
      }
    }
  }

  internal void Clear(int fromRow, int fromCol, int rows, int columns) {
    Delete(fromRow, fromCol, rows, columns, false);
  }

  internal void Delete(int fromRow, int fromCol, int rows, int columns) {
    Delete(fromRow, fromCol, rows, columns, true);
  }

  internal void Delete(int fromRow, int fromCol, int rows, int columns, bool shift) {
    if (columns > 0 && fromRow == 1 && rows >= ExcelPackage.MaxRows) {
      DeleteColumns(fromCol, columns, shift);
    } else {
      var toCol = fromCol + columns - 1;
      var pageFromRow = fromRow >> _pageBits;
      for (int c = 0; c < ColumnCount; c++) {
        var column = _columnIndex[c];
        if (column.Index >= fromCol) {
          if (column.Index > toCol) {
            break;
          }
          var pagePos = column.GetPosition(fromRow);
          if (pagePos < 0) {
            pagePos = ~pagePos;
          }
          if (pagePos < column.PageCount) {
            var page = column._pages[pagePos];
            if (shift
                && page.RowCount > 0
                && page.MinIndex > fromRow
                && page.MaxIndex >= fromRow + rows) {
              var o = page.MinIndex - fromRow;
              if (o < rows) {
                rows -= o;
                page.Offset -= o;
                UpdatePageOffset(column, pagePos, o);
              } else {
                page.Offset -= rows;
                UpdatePageOffset(column, pagePos, rows);
                continue;
              }
            }
            if (page.RowCount > 0
                && page.MinIndex <= fromRow + rows - 1
                && page.MaxIndex
                    >= fromRow) //The row is inside the page
            {
              var endRow = fromRow + rows;
              var delEndRow = DeleteCells(column._pages[pagePos], fromRow, endRow, shift);
              if (shift && delEndRow != fromRow) {
                UpdatePageOffset(column, pagePos, delEndRow - fromRow);
              }
              if (endRow > delEndRow
                  && pagePos < column.PageCount
                  && column._pages[pagePos].MinIndex < endRow) {
                pagePos = (delEndRow == fromRow ? pagePos : pagePos + 1);
                var rowsLeft = DeletePage(
                    shift ? fromRow : delEndRow,
                    endRow - delEndRow,
                    column,
                    pagePos,
                    shift);
                //if (shift) UpdatePageOffset(column, pagePos, endRow - fromRow - rowsLeft);
                if (rowsLeft > 0) {
                  var fr = shift ? fromRow : endRow - rowsLeft;
                  pagePos = column.GetPosition(fr);
                  DeleteCells(column._pages[pagePos], fr, shift ? fr + rowsLeft : endRow, shift);
                  if (shift) {
                    UpdatePageOffset(column, pagePos, rowsLeft);
                  }
                }
              }
            } else if (pagePos > 0
                && column._pages[pagePos].IndexOffset
                    > fromRow) //The row is on the page before.
            {
              int offset = fromRow + rows - 1 - ((pageFromRow - 1) << _pageBits);
              var rowPos = column._pages[pagePos - 1].GetPosition(offset);
              if (rowPos > 0 && pagePos > 0) {
                if (shift) {
                  UpdateIndexOffset(column, pagePos - 1, rowPos, fromRow + rows - 1, -rows);
                }
              }
            } else {
              if (shift && pagePos + 1 < column.PageCount) {
                UpdateIndexOffset(
                    column,
                    pagePos + 1,
                    0,
                    column._pages[pagePos + 1].MinIndex,
                    -rows);
              }
            }
          }
        }
      }
    }
  }

  private void UpdatePageOffset(ColumnIndex column, int pagePos, int rows) {
    //Update Pageoffset

    if (++pagePos < column.PageCount) {
      for (int p = pagePos; p < column.PageCount; p++) {
        if (column._pages[p].Offset - rows <= -_pageSize) {
          column._pages[p].Index--;
          column._pages[p].Offset -= rows - _pageSize;
        } else {
          column._pages[p].Offset -= rows;
        }
      }

      if (Math.Abs(column._pages[pagePos].Offset) > _pageSize
          || Math.Abs(column._pages[pagePos].Rows[column._pages[pagePos].RowCount - 1].Index)
              > _pageSizeMax) //Split or Merge???
      {
        ResetPageOffset(column, pagePos, rows);
      }
    }
  }

  private void ResetPageOffset(ColumnIndex column, int pagePos, int rows) {
    PageIndex fromPage = column._pages[pagePos];
    PageIndex toPage;
    short pageAdd = 0;
    if (fromPage.Offset < -_pageSize) {
      toPage = column._pages[pagePos - 1];
      pageAdd = -1;
      if (fromPage.Index - 1 == toPage.Index) {
        if (fromPage.IndexOffset
                + fromPage.Rows[fromPage.RowCount - 1].Index
                - toPage.IndexOffset
                + toPage.Rows[0].Index
            <= _pageSizeMax) {
          MergePage(column, pagePos - 1);
        }
      } else //No page after
      {
        fromPage.Index -= pageAdd;
        fromPage.Offset += _pageSize;
      }
    } else if (fromPage.Offset > _pageSize) {
      toPage = column._pages[pagePos + 1];
      pageAdd = 1;
      if (fromPage.Index + 1 == toPage.Index) {} else {
        fromPage.Index += pageAdd;
        fromPage.Offset += _pageSize;
      }
    }
  }

  private int DeletePage(int fromRow, int rows, ColumnIndex column, int pagePos, bool shift) {
    PageIndex page = column._pages[pagePos];
    var startRows = rows;
    while (page != null
            && page.MinIndex >= fromRow
            && ((shift && page.MaxIndex < fromRow + rows)
                    || (!shift && page.MaxIndex < fromRow + startRows))) {
      //Delete entire page.
      var delSize = page.MaxIndex - page.MinIndex + 1;
      rows -= delSize;
      var prevOffset = page.Offset;
      Array.Copy(
          column._pages,
          pagePos + 1,
          column._pages,
          pagePos,
          column.PageCount - pagePos + 1);
      column.PageCount--;
      if (column.PageCount == 0) {
        return 0;
      }
      if (shift) {
        for (int i = pagePos; i < column.PageCount; i++) {
          column._pages[i].Offset -= delSize;
          if (column._pages[i].Offset <= -_pageSize) {
            column._pages[i].Index--;
            column._pages[i].Offset += _pageSize;
          }
        }
      }
      if (column.PageCount > pagePos) {
        page = column._pages[pagePos];
        //page.Offset = pagePos == 0 ? 1 : prevOffset;  //First page can only reference to rows starting from Index == 1
      } else {
        //No more pages, return 0
        return 0;
      }
    }
    return rows;
  }

  private int DeleteCells(PageIndex page, int fromRow, int toRow, bool shift) {
    var fromPos = page.GetPosition(fromRow - (page.IndexOffset));
    if (fromPos < 0) {
      fromPos = ~fromPos;
    }
    var maxRow = page.MaxIndex;
    var offset = toRow - page.IndexOffset;
    if (offset > _pageSizeMax) {
      offset = _pageSizeMax;
    }
    var toPos = page.GetPosition(offset);
    if (toPos < 0) {
      toPos = ~toPos;
    }

    if (fromPos <= toPos && fromPos < page.RowCount && page.GetIndex(fromPos) < toRow) {
      if (toRow > page.MaxIndex) {
        if (fromRow
            == page.MinIndex) //Delete entire page, late in the page delete method
        {
          return fromRow;
        }
        var r = page.MaxIndex;
        var deletedRow = page.RowCount - fromPos;
        page.RowCount -= deletedRow;
        return r + 1;
      }
      var rows = toRow - fromRow;
      if (shift) {
        UpdateRowIndex(page, toPos, rows);
      }
      Array.Copy(page.Rows, toPos, page.Rows, fromPos, page.RowCount - toPos);
      page.RowCount -= toPos - fromPos;

      return toRow;
    }
    if (shift) {
      UpdateRowIndex(page, toPos, toRow - fromRow);
    }
    return toRow < maxRow ? toRow : maxRow;
  }

  private static void UpdateRowIndex(PageIndex page, int toPos, int rows) {
    for (int r = toPos; r < page.RowCount; r++) {
      page.Rows[r].Index -= (short)rows;
    }
  }

  private void DeleteColumns(int fromCol, int columns, bool shift) {
    var fPos = GetPosition(fromCol);
    if (fPos < 0) {
      fPos = ~fPos;
    }
    int tPos = fPos;
    for (var c = fPos; c <= ColumnCount; c++) {
      tPos = c;
      if (tPos == ColumnCount || _columnIndex[c].Index >= fromCol + columns) {
        break;
      }
    }

    if (ColumnCount <= fPos) {
      return;
    }

    if (_columnIndex[fPos].Index >= fromCol && _columnIndex[fPos].Index <= fromCol + columns) {
      if (tPos < ColumnCount) {
        Array.Copy(_columnIndex, tPos, _columnIndex, fPos, ColumnCount - tPos);
      }
      ColumnCount -= (tPos - fPos);
    }
    if (shift) {
      for (var c = fPos; c < ColumnCount; c++) {
        _columnIndex[c].Index -= (short)columns;
      }
    }
  }

  private void UpdateIndexOffset(ColumnIndex column, int pagePos, int rowPos, int row, int rows) {
    if (pagePos >= column.PageCount) {
      return; //A page after last cell.
    }
    var page = column._pages[pagePos];
    if (rows > _pageSize) {
      short addPages = (short)(rows >> _pageBits);
      int offset = +(rows - (_pageSize * addPages));
      for (int p = pagePos + 1; p < column.PageCount; p++) {
        if (column._pages[p].Offset + offset > _pageSize) {
          column._pages[p].Index += (short)(addPages + 1);
          column._pages[p].Offset += offset - _pageSize;
        } else {
          column._pages[p].Index += addPages;
          column._pages[p].Offset += offset;
        }
      }

      var size = page.RowCount - rowPos;
      if (page.RowCount > rowPos) {
        if (column.PageCount - 1
            == pagePos) //No page after, create a new one.
        {
          //Copy rows to next page.
          var newPage = CopyNew(page, rowPos, size);
          newPage.Index = (short)((row + rows) >> _pageBits);
          newPage.Offset = row + rows - (newPage.Index * _pageSize) - newPage.Rows[0].Index;
          if (newPage.Offset > _pageSize) {
            newPage.Index++;
            newPage.Offset -= _pageSize;
          }
          AddPage(column, pagePos + 1, newPage);
          page.RowCount = rowPos;
        } else {
          if (column._pages[pagePos + 1].RowCount + size
              > _pageSizeMax) //Split Page
          {
            SplitPageInsert(column, pagePos, rowPos, rows, size, addPages);
          } else //Copy Page.
          {
            CopyMergePage(page, rowPos, rows, size, column._pages[pagePos + 1]);
          }
        }
      }
    } else {
      //Add to Pages.
      for (int r = rowPos; r < page.RowCount; r++) {
        page.Rows[r].Index += (short)rows;
      }
      if (page.Offset + page.Rows[page.RowCount - 1].Index
          >= _pageSizeMax) //Can not be larger than the max size of the page.
      {
        AdjustIndex(column, pagePos);
        if (page.Offset + page.Rows[page.RowCount - 1].Index >= _pageSizeMax) {
          pagePos = SplitPage(column, pagePos);
        }
        //IndexItem[] newRows = new IndexItem[GetSize(page.RowCount - page.Rows[r].Index)];
        //var newPage = new PageIndex(newRows, r);
        //newPage.Index = (short)(pagePos + 1);
        //TODO: MoveRows to next page.
      }

      for (int p = pagePos + 1; p < column.PageCount; p++) {
        if (column._pages[p].Offset + rows < _pageSize) {
          column._pages[p].Offset += rows;
        } else {
          column._pages[p].Index++;
          column._pages[p].Offset = (column._pages[p].Offset + rows) % _pageSize;
        }
      }
    }
  }

  private void SplitPageInsert(
      ColumnIndex column,
      int pagePos,
      int rowPos,
      int rows,
      int size,
      int addPages) {
    var newRows = new IndexItem[GetSize(size)];
    var page = column._pages[pagePos];

    var rStart = -1;
    for (int r = rowPos; r < page.RowCount; r++) {
      if (page.IndexExpanded - (page.Rows[r].Index + rows) > _pageSize) {
        rStart = r;
        break;
      }
      page.Rows[r].Index += (short)rows;
    }
    var rc = page.RowCount - rStart;
    page.RowCount = rStart;
    if (rc > 0) {
      //Copy to a new page
      var row = page.IndexOffset;
      var newPage = CopyNew(page, rStart, rc);
      var ix = (short)(page.Index + addPages);
      var offset = page.IndexOffset + rows - (ix * _pageSize);
      if (offset > _pageSize) {
        ix += (short)(offset / _pageSize);
        offset %= _pageSize;
      }
      newPage.Index = ix;
      newPage.Offset = offset;
      AddPage(column, pagePos + 1, newPage);
    }

    //Copy from next Row
  }

  private void CopyMergePage(PageIndex page, int rowPos, int rows, int size, PageIndex toPage) {
    var startRow = page.IndexOffset + page.Rows[rowPos].Index + rows;
    var newRows = new IndexItem[GetSize(toPage.RowCount + size)];
    page.RowCount -= size;
    Array.Copy(page.Rows, rowPos, newRows, 0, size);
    for (int r = 0; r < size; r++) {
      newRows[r].Index += (short)(page.IndexOffset + rows - toPage.IndexOffset);
    }

    Array.Copy(toPage.Rows, 0, newRows, size, toPage.RowCount);
    toPage.Rows = newRows;
    toPage.RowCount += size;
  }

  private void MergePage(ColumnIndex column, int pagePos) {
    PageIndex page1 = column._pages[pagePos];
    PageIndex page2 = column._pages[pagePos + 1];

    var newPage = new PageIndex(page1, 0, page1.RowCount + page2.RowCount);
    newPage.RowCount = page1.RowCount + page2.RowCount;
    Array.Copy(page1.Rows, 0, newPage.Rows, 0, page1.RowCount);
    Array.Copy(page2.Rows, 0, newPage.Rows, page1.RowCount, page2.RowCount);
    for (int r = page1.RowCount; r < newPage.RowCount; r++) {
      newPage.Rows[r].Index += (short)(page2.IndexOffset - page1.IndexOffset);
    }

    column._pages[pagePos] = newPage;
    column.PageCount--;

    if (column.PageCount > (pagePos + 1)) {
      Array.Copy(
          column._pages,
          pagePos + 2,
          column._pages,
          pagePos + 1,
          column.PageCount - (pagePos + 1));
      for (int p = pagePos + 1; p < column.PageCount; p++) {
        column._pages[p].Index--;
        column._pages[p].Offset += _pageSize;
      }
    }
  }

  private PageIndex CopyNew(PageIndex pageFrom, int rowPos, int size) {
    IndexItem[] newRows = new IndexItem[GetSize(size)];
    Array.Copy(pageFrom.Rows, rowPos, newRows, 0, size);
    return new(newRows, size);
  }

  internal static int GetSize(int size) {
    var newSize = 256;
    while (newSize < size) {
      newSize <<= 1;
    }
    return newSize;
  }

  private void AddCell(ColumnIndex columnIndex, int pagePos, int pos, short ix, T value) {
    PageIndex pageItem = columnIndex._pages[pagePos];
    if (pageItem.RowCount == pageItem.Rows.Length) {
      if (pageItem.RowCount
          == _pageSizeMax) //Max size-->Split
      {
        pagePos = SplitPage(columnIndex, pagePos);
        if (columnIndex._pages[pagePos - 1].RowCount > pos) {
          pagePos--;
        } else {
          pos -= columnIndex._pages[pagePos - 1].RowCount;
        }
        pageItem = columnIndex._pages[pagePos];
      } else //Expand to double size.
      {
        var rowsTmp = new IndexItem[pageItem.Rows.Length << 1];
        Array.Copy(pageItem.Rows, 0, rowsTmp, 0, pageItem.RowCount);
        pageItem.Rows = rowsTmp;
      }
    }
    if (pos < pageItem.RowCount) {
      Array.Copy(pageItem.Rows, pos, pageItem.Rows, pos + 1, pageItem.RowCount - pos);
    }
    pageItem.Rows[pos] = new() {
      Index = ix,
      IndexPointer = _values.Count,
    };
    _values.Add(value);
    pageItem.RowCount++;
  }

  private int SplitPage(ColumnIndex columnIndex, int pagePos) {
    var page = columnIndex._pages[pagePos];
    if (page.Offset != 0) {
      var offset = page.Offset;
      page.Offset = 0;
      for (int r = 0; r < page.RowCount; r++) {
        page.Rows[r].Index -= (short)offset;
      }
    }
    //Find Split pos
    int splitPos = 0;
    for (int r = 0; r < page.RowCount; r++) {
      if (page.Rows[r].Index > _pageSize) {
        splitPos = r;
        break;
      }
    }
    var newPage = new PageIndex(page, 0, splitPos);
    var nextPage = new PageIndex(
        page,
        splitPos,
        page.RowCount - splitPos,
        (short)(page.Index + 1),
        page.Offset);

    for (int r = 0; r < nextPage.RowCount; r++) {
      nextPage.Rows[r].Index = (short)(nextPage.Rows[r].Index - _pageSize);
    }

    columnIndex._pages[pagePos] = newPage;
    if (columnIndex.PageCount + 1 > columnIndex._pages.Length) {
      var pageTmp = new PageIndex[columnIndex._pages.Length << 1];
      Array.Copy(columnIndex._pages, 0, pageTmp, 0, columnIndex.PageCount);
      columnIndex._pages = pageTmp;
    }
    Array.Copy(
        columnIndex._pages,
        pagePos + 1,
        columnIndex._pages,
        pagePos + 2,
        columnIndex.PageCount - pagePos - 1);
    columnIndex._pages[pagePos + 1] = nextPage;
    page = nextPage;
    //pos -= PageSize;
    columnIndex.PageCount++;
    return pagePos + 1;
  }

  private PageIndex AdjustIndex(ColumnIndex columnIndex, int pagePos) {
    PageIndex page = columnIndex._pages[pagePos];
    //First Adjust indexes
    if (page.Offset + page.Rows[0].Index >= _pageSize
        || page.Offset >= _pageSize
        || page.Rows[0].Index >= _pageSize) {
      page.Index++;
      page.Offset -= _pageSize;
    } else if (page.Offset + page.Rows[0].Index <= -_pageSize
        || page.Offset <= -_pageSize
        || page.Rows[0].Index <= -_pageSize) {
      page.Index--;
      page.Offset += _pageSize;
    }
    return page;
  }

  private void AddPage(ColumnIndex column, int pos, short index) {
    AddPage(column, pos);
    column._pages[pos] = new() {
      Index = index,
    };
    if (pos > 0) {
      var pp = column._pages[pos - 1];
      if (pp.RowCount > 0 && pp.Rows[pp.RowCount - 1].Index > _pageSize) {
        column._pages[pos].Offset = pp.Rows[pp.RowCount - 1].Index - _pageSize;
      }
    }
  }

  /// <summary>
  /// Add a new page to the collection
  /// </summary>
  /// <param name="column">The column</param>
  /// <param name="pos">Position</param>
  /// <param name="page">The new page object to add</param>
  private void AddPage(ColumnIndex column, int pos, PageIndex page) {
    AddPage(column, pos);
    column._pages[pos] = page;
  }

  /// <summary>
  /// Add a new page to the collection
  /// </summary>
  /// <param name="column">The column</param>
  /// <param name="pos">Position</param>
  private void AddPage(ColumnIndex column, int pos) {
    if (column.PageCount == column._pages.Length) {
      var pageTmp = new PageIndex[column._pages.Length * 2];
      Array.Copy(column._pages, 0, pageTmp, 0, column.PageCount);
      column._pages = pageTmp;
    }
    if (pos < column.PageCount) {
      Array.Copy(column._pages, pos, column._pages, pos + 1, column.PageCount - pos);
    }
    column.PageCount++;
  }

  private void AddColumn(int pos, int column) {
    if (ColumnCount == _columnIndex.Length) {
      var colTmp = new ColumnIndex[_columnIndex.Length * 2];
      Array.Copy(_columnIndex, 0, colTmp, 0, ColumnCount);
      _columnIndex = colTmp;
    }
    if (pos < ColumnCount) {
      Array.Copy(_columnIndex, pos, _columnIndex, pos + 1, ColumnCount - pos);
    }
    _columnIndex[pos] = new() {
      Index = (short)(column),
    };
    ColumnCount++;
  }

  internal bool NextCell(ref int row, ref int col) {
    return NextCell(ref row, ref col, 0, 0, ExcelPackage.MaxRows, ExcelPackage.MaxColumns);
  }

  internal bool NextCell(
      ref int row,
      ref int col,
      int minRow,
      int minColPos,
      int maxRow,
      int maxColPos) {
    if (minColPos >= ColumnCount) {
      return false;
    }
    if (maxColPos >= ColumnCount) {
      maxColPos = ColumnCount - 1;
    }
    var c = GetPosition(col);
    if (c >= 0) {
      if (c > maxColPos) {
        if (col <= minColPos) {
          return false;
        }
        col = minColPos;
        return NextCell(ref row, ref col);
      }
      var r = GetNextCell(ref row, ref c, minColPos, maxRow, maxColPos);
      col = _columnIndex[c].Index;
      return r;
    }
    c = ~c;
    if (c > _columnIndex[c].Index) {
      if (col <= minColPos) {
        return false;
      }
      col = minColPos;
      return NextCell(ref row, ref col, minRow, minColPos, maxRow, maxColPos);
    }
    {
      var r = GetNextCell(ref c, ref row, minColPos, maxRow, maxColPos);
      col = _columnIndex[c].Index;
      return r;
    }
  }

  internal bool GetNextCell(
      ref int row,
      ref int colPos,
      int startColPos,
      int endRow,
      int endColPos) {
    if (ColumnCount == 0) {
      return false;
    }
    if (++colPos < ColumnCount && colPos <= endColPos) {
      var r = _columnIndex[colPos].GetNextRow(row);
      if (r
          == row) //Exists next Row
      {
        return true;
      }
      int minRow,
          minCol;
      if (r > row) {
        minRow = r;
        minCol = colPos;
      } else {
        minRow = int.MaxValue;
        minCol = 0;
      }

      var c = colPos + 1;
      while (c < ColumnCount && c <= endColPos) {
        r = _columnIndex[c].GetNextRow(row);
        if (r
            == row) //Exists next Row
        {
          colPos = c;
          return true;
        }
        if (r > row && r < minRow) {
          minRow = r;
          minCol = c;
        }
        c++;
      }
      c = startColPos;
      if (row < endRow) {
        row++;
        while (c < colPos) {
          r = _columnIndex[c].GetNextRow(row);
          if (r
              == row) //Exists next Row
          {
            colPos = c;
            return true;
          }
          if (r > row && (r < minRow || (r == minRow && c < minCol)) && r <= endRow) {
            minRow = r;
            minCol = c;
          }
          c++;
        }
      }

      if (minRow == int.MaxValue || minRow > endRow) {
        return false;
      }
      row = minRow;
      colPos = minCol;
      return true;
    }
    if (colPos <= startColPos || row >= endRow) {
      return false;
    }
    colPos = startColPos - 1;
    row++;
    return GetNextCell(ref row, ref colPos, startColPos, endRow, endColPos);
  }

  internal bool PrevCell(ref int row, ref int col) {
    return PrevCell(ref row, ref col, 0, 0, ExcelPackage.MaxRows, ExcelPackage.MaxColumns);
  }

  private bool PrevCell(
      ref int row,
      ref int col,
      int minRow,
      int minColPos,
      int maxRow,
      int maxColPos) {
    if (minColPos >= ColumnCount) {
      return false;
    }
    if (maxColPos >= ColumnCount) {
      maxColPos = ColumnCount - 1;
    }
    var c = GetPosition(col);
    if (c >= 0) {
      if (c == 0) {
        if (col >= maxColPos) {
          return false;
        }
        if (row == minRow) {
          return false;
        }
        row--;
        col = maxColPos;
        return PrevCell(ref row, ref col, minRow, minColPos, maxRow, maxColPos);
      }
      var ret = GetPrevCell(ref row, ref c, minRow, minColPos, maxColPos);
      if (ret) {
        col = _columnIndex[c].Index;
      }
      return ret;
    }
    c = ~c;
    if (c == 0) {
      if (col >= maxColPos || row <= 0) {
        return false;
      }
      col = maxColPos;
      row--;
      return PrevCell(ref row, ref col, minRow, minColPos, maxRow, maxColPos);
    }
    {
      var ret = GetPrevCell(ref row, ref c, minRow, minColPos, maxColPos);
      if (ret) {
        col = _columnIndex[c].Index;
      }
      return ret;
    }
  }

  internal bool GetPrevCell(
      ref int row,
      ref int colPos,
      int startRow,
      int startColPos,
      int endColPos) {
    if (ColumnCount == 0) {
      return false;
    }
    if (--colPos >= startColPos)
    //                if (++colPos < ColumnCount && colPos <= endColPos)
    {
      var r = _columnIndex[colPos].GetNextRow(row);
      if (r
          == row) //Exists next Row
      {
        return true;
      }
      int minRow,
          minCol;
      if (r > row && r >= startRow) {
        minRow = r;
        minCol = colPos;
      } else {
        minRow = int.MaxValue;
        minCol = 0;
      }

      var c = colPos - 1;
      if (c >= startColPos) {
        while (c >= startColPos) {
          r = _columnIndex[c].GetNextRow(row);
          if (r
              == row) //Exists next Row
          {
            colPos = c;
            return true;
          }
          if (r > row && r < minRow && r >= startRow) {
            minRow = r;
            minCol = c;
          }
          c--;
        }
      }
      if (row > startRow) {
        c = endColPos;
        row--;
        while (c > colPos) {
          r = _columnIndex[c].GetNextRow(row);
          if (r
              == row) //Exists next Row
          {
            colPos = c;
            return true;
          }
          if (r > row && r < minRow && r >= startRow) {
            minRow = r;
            minCol = c;
          }
          c--;
        }
      }
      if (minRow == int.MaxValue || startRow < minRow) {
        return false;
      }
      row = minRow;
      colPos = minCol;
      return true;
    }
    colPos = ColumnCount;
    row--;
    if (row < startRow) {
      return false;
    }
    return GetPrevCell(ref colPos, ref row, startRow, startColPos, endColPos);
  }
}

internal class CellsStoreEnumerator<T> : IEnumerable<T>, IEnumerator<T> {
  private readonly CellStore<T> _cellStore;
  private int row,
      colPos;
  private int[] pagePos,
      cellPos;
  private readonly int _startRow;
  private readonly int _startCol;
  private readonly int _endRow;
  private readonly int _endCol;
  private int minRow,
      minColPos,
      maxRow,
      maxColPos;

  public CellsStoreEnumerator(CellStore<T> cellStore)
      : this(cellStore, 0, 0, ExcelPackage.MaxRows, ExcelPackage.MaxColumns) {}

  public CellsStoreEnumerator(
      CellStore<T> cellStore,
      int startRow,
      int startCol,
      int endRow,
      int endCol) {
    _cellStore = cellStore;

    _startRow = startRow;
    _startCol = startCol;
    _endRow = endRow;
    _endCol = endCol;

    Init();
  }

  internal void Init() {
    minRow = _startRow;
    maxRow = _endRow;

    minColPos = _cellStore.GetPosition(_startCol);
    if (minColPos < 0) {
      minColPos = ~minColPos;
    }
    maxColPos = _cellStore.GetPosition(_endCol);
    if (maxColPos < 0) {
      maxColPos = ~maxColPos - 1;
    }
    row = minRow;
    colPos = minColPos - 1;

    var cols = maxColPos - minColPos + 1;
    pagePos = new int[cols];
    cellPos = new int[cols];
    for (int i = 0; i < cols; i++) {
      pagePos[i] = -1;
      cellPos[i] = -1;
    }
  }

  internal int Row => row;

  internal int Column {
    get {
      if (colPos == -1) {
        MoveNext();
      }
      if (colPos == -1) {
        return 0;
      }
      return _cellStore._columnIndex[colPos].Index;
    }
  }

  internal T Value {
    get => _cellStore.GetValue(row, Column);
    set => _cellStore.SetValue(row, Column, value);
  }

  internal bool Next() {
    return _cellStore.GetNextCell(ref row, ref colPos, minColPos, maxRow, maxColPos);
  }

  public string CellAddress => ExcelCellBase.GetAddress(Row, Column);

  public IEnumerator<T> GetEnumerator() {
    Reset();
    return this;
  }

  IEnumerator IEnumerable.GetEnumerator() {
    Reset();
    return this;
  }

  public T Current => Value;

  public void Dispose() {}

  object IEnumerator.Current {
    get {
      Reset();
      return this;
    }
  }

  public bool MoveNext() {
    return Next();
  }

  public void Reset() {
    Init();
  }
}

internal class FlagCellStore : CellStore<byte> {
  internal void SetFlagValue(int row, int col, bool value, CellFlags cellFlags) {
    CellFlags currentValue = (CellFlags)GetValue(row, col);
    if (value) {
      SetValue(row, col, (byte)(currentValue | cellFlags)); // add the CellFlag bit
    } else {
      SetValue(row, col, (byte)(currentValue & ~cellFlags)); // remove the CellFlag bit
    }
  }

  internal bool GetFlagValue(int row, int col, CellFlags cellFlags) {
    return !(((byte)cellFlags & GetValue(row, col)) == 0);
  }
}