diff --git a/ClosedXML/Excel/Cells/XLCell.cs b/ClosedXML/Excel/Cells/XLCell.cs index 07f6cea..ff51a6c 100644 --- a/ClosedXML/Excel/Cells/XLCell.cs +++ b/ClosedXML/Excel/Cells/XLCell.cs @@ -1062,8 +1062,7 @@ //Checking if called from range to avoid stack overflow if (!calledFromRange && IsMerged()) { - var asRange = AsRange(); - var firstOrDefault = Worksheet.Internals.MergedRanges.FirstOrDefault(asRange.Intersects); + var firstOrDefault = Worksheet.Internals.MergedRanges.GetIntersectedRanges(Address).FirstOrDefault(); if (firstOrDefault != null) firstOrDefault.Clear(clearOptions); } @@ -1896,9 +1895,9 @@ var srcSheet = fromRange.Worksheet; int minRo = fromRange.RangeAddress.FirstAddress.RowNumber; int minCo = fromRange.RangeAddress.FirstAddress.ColumnNumber; - if (srcSheet.ConditionalFormats.Any(r => r.Ranges.Any(range => range.Intersects(fromRange)))) + if (srcSheet.ConditionalFormats.Any(r => r.Ranges.GetIntersectedRanges(fromRange.RangeAddress).Any())) { - var fs = srcSheet.ConditionalFormats.SelectMany(cf => cf.Ranges).Where(range => range.Intersects(fromRange)).ToArray(); + var fs = srcSheet.ConditionalFormats.SelectMany(cf => cf.Ranges.GetIntersectedRanges(fromRange.RangeAddress)).ToArray(); if (fs.Any()) { minRo = fs.Max(r => r.RangeAddress.LastAddress.RowNumber); @@ -1910,11 +1909,11 @@ rCnt = Math.Min(rCnt, fromRange.RowCount()); cCnt = Math.Min(cCnt, fromRange.ColumnCount()); var toRange = Worksheet.Range(this, Worksheet.Cell(_rowNumber + rCnt - 1, _columnNumber + cCnt - 1)); - var formats = srcSheet.ConditionalFormats.Where(f => f.Ranges.Any(range => range.Intersects(fromRange))); + var formats = srcSheet.ConditionalFormats.Where(f => f.Ranges.GetIntersectedRanges(fromRange.RangeAddress).Any()); foreach (var cf in formats.ToList()) { var fmtRanges = cf.Ranges - .Where(r => r.Intersects(fromRange)) + .GetIntersectedRanges(fromRange.RangeAddress) .Select(r => Relative(Intersection(r, fromRange), fromRange, toRange) as XLRange) .ToList(); @@ -1969,8 +1968,7 @@ private void ClearMerged() { - List mergeToDelete = Worksheet.Internals.MergedRanges - .Where(merge => merge.Intersects(AsRange())).ToList(); + List mergeToDelete = Worksheet.Internals.MergedRanges.GetIntersectedRanges(Address).ToList(); mergeToDelete.ForEach(m => Worksheet.Internals.MergedRanges.Remove(m)); } diff --git a/ClosedXML/Excel/ConditionalFormats/XLConditionalFormats.cs b/ClosedXML/Excel/ConditionalFormats/XLConditionalFormats.cs index a122b9d..e7b33c9 100644 --- a/ClosedXML/Excel/ConditionalFormats/XLConditionalFormats.cs +++ b/ClosedXML/Excel/ConditionalFormats/XLConditionalFormats.cs @@ -67,14 +67,14 @@ var nextFormat = formats[i]; var intersectsSkipped = - skippedRanges.Any(left => nextFormat.Ranges.Any(right => left.Intersects(right))); + skippedRanges.Any(left => nextFormat.Ranges.GetIntersectedRanges(left.RangeAddress).Any()); if (IsSameFormat(nextFormat) && !intersectsSkipped) { similarFormats.Add(nextFormat); nextFormat.Ranges.ForEach(r => rangesToJoin.Add(r)); } - else if (rangesToJoin.Any(left => nextFormat.Ranges.Any(right => left.Intersects(right))) || + else if (rangesToJoin.Any(left => nextFormat.Ranges.GetIntersectedRanges(left.RangeAddress).Any()) || intersectsSkipped) { // if we reached the rule intersecting any of captured ranges stop for not breaking the priorities diff --git a/ClosedXML/Excel/Patterns/Quadrant.cs b/ClosedXML/Excel/Patterns/Quadrant.cs new file mode 100644 index 0000000..34a6ef0 --- /dev/null +++ b/ClosedXML/Excel/Patterns/Quadrant.cs @@ -0,0 +1,343 @@ +using System; +using System.Collections.Generic; +using System.Linq; + +namespace ClosedXML.Excel.Patterns +{ + /// + /// Implementation of QuadTree adapted to Excel worksheet specifics. Differences with the classic implementation + /// are that the topmost level is split to 128 square parts (2 columns of 64 blocks, each 8192*8192 cells) and that splitting + /// the quadrand onto 4 smaller quadrants does not depent on the number of items in this quadrant. When the range is added to the + /// QuadTree it is placed on the bottommost level where it fits to a single quadrant. That means, row-wide and column-wide ranges + /// are always placed at the level 0, and the smaller the range is the deeper it goes down the tree. This approach eliminates + /// the need of trasferring ranges between levels. + /// + internal class Quadrant + { + #region Public Properties + + /// + /// Smaller quadrants which the current one is splitted to. Is NULL until ranges are added to child quadrants. + /// + public IEnumerable Children { get; private set; } + + /// + /// The level of current quadrant. Top most has level 0, child quadrants has levels (Level + 1). + /// + public byte Level { get; } + + /// + /// Minimum column included in this quadrant. + /// + public int MinimumColumn { get; } + + /// + /// Minimun row included in this quadrant. + /// + public int MinimumRow { get; } + + /// + /// Maximum column included in this quadrant. + /// + public int MaximumColumn { get; } + + /// + /// Maximum row included in this quadrant. + /// + public int MaximumRow { get; } + + /// + /// Collection of ranges belonging to this quadrant (does not include ranges from child quadrants). + /// + public IEnumerable Ranges + { + get => _ranges?.AsEnumerable(); + } + + /// + /// The number of current quadrant by horizontal axis. + /// + public short X { get; private set; } + + /// + /// The number of current quadrant by vertical axis. + /// + public short Y { get; private set; } + + #endregion Public Properties + + #region Constructors + + public Quadrant() : this(0, 0, 0) + { } + + private Quadrant(byte level, short x, short y) + { + Level = level; + X = x; + Y = y; + + MinimumColumn = (Level == 0) ? 1 : 1 + XLHelper.MaxColumnNumber / (int)Math.Pow(2, Level) * X; + MinimumRow = (Level == 0) ? 1 : 1 + XLHelper.MaxColumnNumber / (int)Math.Pow(2, Level) * Y; //MaxColumnNumber here is not a mistake + MaximumColumn = (Level == 0) + ? XLHelper.MaxColumnNumber + : XLHelper.MaxColumnNumber / (int)Math.Pow(2, Level) * (X + 1); + MaximumRow = (Level == 0) + ? XLHelper.MaxRowNumber + : XLHelper.MaxColumnNumber / (int)Math.Pow(2, Level) * (Y + 1); //MaxColumnNumber here is not a mistake + } + + #endregion Constructors + + #region Public Methods + + /// + /// Add a range to the quadrant or to one of the child quadrants (recursively). + /// + /// True, if range was successfully added, false if it has been added before. + public bool Add(IXLRangeBase range) + { + bool res = false; + var children = Children ?? CreateChildren().ToList(); + bool addToChild = false; + foreach (var childQuadrant in children) + { + var rangeAddress = range.RangeAddress; + if (childQuadrant.Covers(in rangeAddress)) + { + res |= childQuadrant.Add(range); + addToChild = true; + break; + } + } + + if (!addToChild) + res = AddInternal(range); + + if (Children == null && addToChild) + Children = children; + + return res; + } + + /// + /// Get all ranges from the quadrant and all child quadrants (recursively). + /// + public IEnumerable GetAll() + { + if (Ranges != null) + { + foreach (var range in Ranges) + yield return range; + } + + if (Children != null) + { + foreach (var childQuadrant in Children) + { + var childRanges = childQuadrant.GetAll(); + foreach (var range in childRanges) + yield return range; + } + } + } + + /// + /// Get all ranges from the quadrant and all child quadrants (recursively) that intersect the specified address. + /// + public IEnumerable GetIntersectedRanges(IXLRangeAddress rangeAddress) + { + if (Ranges != null) + { + foreach (var range in Ranges) + { + if (range.RangeAddress.Intersects(rangeAddress)) + yield return range; + } + } + + if (Children != null) + { + foreach (var childQuadrant in Children) + { + if (childQuadrant.Intersects(in rangeAddress)) + { + var childRanges = childQuadrant.GetIntersectedRanges(rangeAddress); + foreach (var range in childRanges) + yield return range; + } + } + } + } + + /// + /// Get all ranges from the quadrant and all child quadrants (recursively) that cover the specified address. + /// + public IEnumerable GetIntersectedRanges(IXLAddress address) + { + if (Ranges != null) + { + foreach (var range in Ranges) + { + if (range.RangeAddress.Contains(address)) + yield return range; + } + } + + if (Children != null) + { + foreach (var childQuadrant in Children) + { + if (childQuadrant.Covers(in address)) + { + var childRanges = childQuadrant.GetIntersectedRanges(address); + foreach (var range in childRanges) + yield return range; + } + } + } + } + + /// + /// Remove the range from the quadrant or from child quadrants (recursively). + /// + /// True if the range was removed, false if it does not exist in the QuadTree. + public bool Remove(IXLRangeBase range) + { + bool res = false; + var rangeAddress = range.RangeAddress; + + bool coveredByChild = false; + if (Children != null) + { + foreach (var childQuadrant in Children) + { + if (childQuadrant.Covers(in rangeAddress)) + { + res |= childQuadrant.Remove(range); + coveredByChild = true; + } + } + } + + if (!coveredByChild) + { + if (_ranges?.Remove(range) == true) + res = true; + } + + return res; ; + } + + /// + /// Remove all the ranges matching specified criteria from the quadrant and its child quadrants (recursively). + /// Don't use it for searching intersections as it would be much less efficient than . + /// + public IEnumerable RemoveAll(Predicate predicate) + { + if (_ranges != null) + { + var ranges = _ranges.Where(r => predicate(r)); + foreach (var range in ranges) + { + yield return range; + } + _ranges.RemoveWhere(predicate); + } + + if (Children != null) + { + foreach (var childQuadrant in Children) + foreach (var childRange in childQuadrant.RemoveAll(predicate)) + { + yield return childRange; + } + } + } + + #endregion Public Methods + + #region Private Fields + + /// + /// Maximum depth of the QuadTree. Value 10 corresponds to the smallest quadrants having size 16*16 cells. + /// + private const byte MAX_LEVEL = 10; + + /// + /// Collection of ranges belonging to the current quandrant (that cannot fit into child quadrants). + /// + private HashSet _ranges; + + #endregion Private Fields + + #region Private Methods + + /// + /// Add a range to the collection of quandrant's own ranges. + /// + /// True if the range was succesfully added, false if it had been added before. + private bool AddInternal(IXLRangeBase range) + { + if (_ranges == null) + _ranges = new HashSet(); + return _ranges.Add(range); + } + + /// + /// Check if the current quadrant fully covers the specified address. + /// + private bool Covers(in IXLRangeAddress rangeAddress) + { + return MinimumColumn <= rangeAddress.FirstAddress.ColumnNumber && + MaximumColumn >= rangeAddress.LastAddress.ColumnNumber && + MinimumRow <= rangeAddress.FirstAddress.RowNumber && + MaximumRow >= rangeAddress.LastAddress.RowNumber; + } + + /// + /// Check if the current quadrant covers the specified address. + /// + private bool Covers(in IXLAddress address) + { + return MinimumColumn <= address.ColumnNumber && + MaximumColumn >= address.ColumnNumber && + MinimumRow <= address.RowNumber && + MaximumRow >= address.RowNumber; + } + + /// + /// Check if the current quadrant intersects the specified address. + /// + private bool Intersects(in IXLRangeAddress rangeAddress) + { + return ((MinimumRow <= rangeAddress.FirstAddress.RowNumber && rangeAddress.FirstAddress.RowNumber <= MaximumRow) || + (rangeAddress.FirstAddress.RowNumber <= MinimumRow && MinimumRow <= rangeAddress.LastAddress.RowNumber)) + && + ((MinimumColumn <= rangeAddress.FirstAddress.ColumnNumber && rangeAddress.FirstAddress.ColumnNumber <= MaximumColumn) || + (rangeAddress.FirstAddress.ColumnNumber <= MinimumColumn && MinimumColumn <= rangeAddress.LastAddress.ColumnNumber)); + } + + /// + /// Create a collection of child quadrants dividing the current one. + /// + private IEnumerable CreateChildren() + { + byte childLevel = (byte)(Level + 1); + if (childLevel > MAX_LEVEL) + yield break; + byte xCount = 2; // Always divide on halfs + byte yCount = (byte)((Level == 0) ? (XLHelper.MaxRowNumber / XLHelper.MaxColumnNumber) : 2); // Level 0 divide onto 64 parts, the rest - on halfs + + for (byte dy = 0; dy < yCount; dy++) + { + for (byte dx = 0; dx < xCount; dx++) + { + yield return new Quadrant(childLevel, (short)(X * 2 + dx), (short)(Y * 2 + dy)); + } + } + } + + #endregion Private Methods + } +} diff --git a/ClosedXML/Excel/Ranges/IXLRangeAddress.cs b/ClosedXML/Excel/Ranges/IXLRangeAddress.cs index de1b017..93f13e3 100644 --- a/ClosedXML/Excel/Ranges/IXLRangeAddress.cs +++ b/ClosedXML/Excel/Ranges/IXLRangeAddress.cs @@ -43,5 +43,9 @@ String ToStringRelative(); String ToStringRelative(Boolean includeSheet); + + bool Intersects(IXLRangeAddress otherAddress); + + bool Contains(IXLAddress address); } } diff --git a/ClosedXML/Excel/Ranges/IXLRanges.cs b/ClosedXML/Excel/Ranges/IXLRanges.cs index afbb967..7942719 100644 --- a/ClosedXML/Excel/Ranges/IXLRanges.cs +++ b/ClosedXML/Excel/Ranges/IXLRanges.cs @@ -32,6 +32,19 @@ Boolean Contains(IXLRange range); + /// + /// Filter ranges from a collection that intersect the specified address. Is much more efficient + /// that using Linq expression .Where(). + /// + IEnumerable GetIntersectedRanges(IXLRangeAddress rangeAddress); + + /// + /// Filter ranges from a collection that intersect the specified address. Is much more efficient + /// that using Linq expression .Where(). + /// + IEnumerable GetIntersectedRanges(IXLAddress address); + + IXLStyle Style { get; set; } IXLDataValidation SetDataValidation(); diff --git a/ClosedXML/Excel/Ranges/Index/IXLRangeIndex.cs b/ClosedXML/Excel/Ranges/Index/IXLRangeIndex.cs new file mode 100644 index 0000000..7cb6d3f --- /dev/null +++ b/ClosedXML/Excel/Ranges/Index/IXLRangeIndex.cs @@ -0,0 +1,43 @@ +using System; +using System.Collections.Generic; + +namespace ClosedXML.Excel.Ranges.Index +{ + /// + /// Interface for the engine aimed to speed-up the search for the range intersections. + /// + internal interface IXLRangeIndex + { + bool Add(IXLRangeBase range); + + bool Remove(IXLRangeBase range); + + int RemoveAll(Predicate predicate = null); + + IEnumerable GetIntersectedRanges(XLRangeAddress rangeAddress); + + IEnumerable GetIntersectedRanges(XLAddress address); + + IEnumerable GetAll(); + + bool Intersects(in XLRangeAddress rangeAddress); + + bool Contains(in XLAddress address); + } + + internal interface IXLRangeIndex : IXLRangeIndex + where T : IXLRangeBase + { + bool Add(T range); + + bool Remove(T range); + + int RemoveAll(Predicate predicate = null); + + new IEnumerable GetIntersectedRanges(XLRangeAddress rangeAddress); + + new IEnumerable GetIntersectedRanges(XLAddress address); + + new IEnumerable GetAll(); + } +} diff --git a/ClosedXML/Excel/Ranges/Index/XLRangeIndex.cs b/ClosedXML/Excel/Ranges/Index/XLRangeIndex.cs new file mode 100644 index 0000000..2bcba8c --- /dev/null +++ b/ClosedXML/Excel/Ranges/Index/XLRangeIndex.cs @@ -0,0 +1,144 @@ +using ClosedXML.Excel.Patterns; +using System; +using System.Collections.Generic; +using System.Linq; + +namespace ClosedXML.Excel.Ranges.Index +{ + /// + /// Implementation of internally using QuadTree. + /// + internal class XLRangeIndex : IXLRangeIndex + { + #region Public Constructors + + public XLRangeIndex(IXLWorksheet worksheet) + { + _worksheet = worksheet; + _quadTree = new Quadrant(); + } + + #endregion Public Constructors + + #region Public Methods + + public bool Add(IXLRangeBase range) + { + if (range == null) + throw new ArgumentNullException(nameof(range)); + + if (!range.RangeAddress.IsValid) + throw new ArgumentException("Range is invalid"); + + CheckWorksheet(range.Worksheet); + + return _quadTree.Add(range); + } + + public bool Contains(in XLAddress address) + { + CheckWorksheet(address.Worksheet); + return _quadTree.GetIntersectedRanges(address).Any(); + } + + public bool Intersects(in XLRangeAddress rangeAddress) + { + CheckWorksheet(rangeAddress.Worksheet); + return _quadTree.GetIntersectedRanges(rangeAddress).Any(); + } + + public bool Remove(IXLRangeBase range) + { + if (range == null) + throw new ArgumentNullException(nameof(range)); + + CheckWorksheet(range.Worksheet); + + return _quadTree.Remove(range); + } + + public int RemoveAll(Predicate predicate = null) + { + return _quadTree.RemoveAll(predicate ?? (_ => true)).Count(); + } + + public IEnumerable GetAll() + { + return _quadTree.GetAll(); + } + + public IEnumerable GetIntersectedRanges(XLRangeAddress rangeAddress) + { + CheckWorksheet(rangeAddress.Worksheet); + + return _quadTree.GetIntersectedRanges(rangeAddress); + } + + public IEnumerable GetIntersectedRanges(XLAddress address) + { + CheckWorksheet(address.Worksheet); + + return _quadTree.GetIntersectedRanges(address); + } + + #endregion Public Methods + + #region Private Fields + + private readonly Quadrant _quadTree; + private readonly IXLWorksheet _worksheet; + + #endregion Private Fields + + #region Private Methods + + private void CheckWorksheet(IXLWorksheet worksheet) + { + if (worksheet != _worksheet) + throw new ArgumentException("Range belongs to a different worksheet"); + } + + #endregion Private Methods + } + + /// + /// Generic version of . + /// + internal class XLRangeIndex : XLRangeIndex, IXLRangeIndex + where T : IXLRangeBase + { + public XLRangeIndex(IXLWorksheet worksheet) : base(worksheet) + { + } + + public bool Add(T range) + { + return base.Add(range); + } + + public bool Remove(T range) + { + return base.Remove(range); + } + + public int RemoveAll(Predicate predicate) + { + return base.RemoveAll(r => predicate((T)r)); + } + + public new IEnumerable GetIntersectedRanges(XLRangeAddress rangeAddress) + { + return base.GetIntersectedRanges(rangeAddress).Cast(); + } + + public new IEnumerable GetIntersectedRanges(XLAddress address) + { + return base.GetIntersectedRanges(address).Cast(); + } + + public new IEnumerable GetAll() + { + return base.GetAll().Cast(); + } + } +} diff --git a/ClosedXML/Excel/Ranges/XLRangeAddress.cs b/ClosedXML/Excel/Ranges/XLRangeAddress.cs index d774b6a..08156bd 100644 --- a/ClosedXML/Excel/Ranges/XLRangeAddress.cs +++ b/ClosedXML/Excel/Ranges/XLRangeAddress.cs @@ -194,6 +194,36 @@ LastAddress.ToStringRelative()); } + public bool Intersects(IXLRangeAddress otherAddress) + { + var xlOtherAddress = (XLRangeAddress) otherAddress; + return Intersects(in xlOtherAddress); + } + + internal bool Intersects(in XLRangeAddress otherAddress) + { + return !( // See if the two ranges intersect... + otherAddress.FirstAddress.ColumnNumber > LastAddress.ColumnNumber + || otherAddress.LastAddress.ColumnNumber < FirstAddress.ColumnNumber + || otherAddress.FirstAddress.RowNumber > LastAddress.RowNumber + || otherAddress.LastAddress.RowNumber < FirstAddress.RowNumber + ); + } + + public bool Contains(IXLAddress address) + { + var xlAddress = (XLAddress)address; + return Contains(in xlAddress); + } + + internal bool Contains(in XLAddress address) + { + return FirstAddress.RowNumber <= address.RowNumber && + address.RowNumber <= LastAddress.RowNumber && + FirstAddress.ColumnNumber <= address.ColumnNumber && + address.ColumnNumber <= LastAddress.ColumnNumber; + } + public String ToStringFixed(XLReferenceStyle referenceStyle) { return ToStringFixed(referenceStyle, false); diff --git a/ClosedXML/Excel/Ranges/XLRangeBase.cs b/ClosedXML/Excel/Ranges/XLRangeBase.cs index 370b9b7..57524e8 100644 --- a/ClosedXML/Excel/Ranges/XLRangeBase.cs +++ b/ClosedXML/Excel/Ranges/XLRangeBase.cs @@ -8,6 +8,7 @@ namespace ClosedXML.Excel { + internal abstract class XLRangeBase : XLStylizedBase, IXLRangeBase, IXLStylized { #region Fields @@ -290,13 +291,10 @@ { if (checkIntersect) { - var range = Worksheet.Range(RangeAddress); - foreach (var mergedRange in Worksheet.Internals.MergedRanges) + var intersectedMergedRanges = Worksheet.Internals.MergedRanges.GetIntersectedRanges(RangeAddress).ToList(); + foreach (var intersectedMergedRange in intersectedMergedRanges) { - if (mergedRange.Intersects(range)) - { - Worksheet.Internals.MergedRanges.Remove(mergedRange); - } + Worksheet.Internals.MergedRanges.Remove(intersectedMergedRange); } } @@ -350,7 +348,7 @@ { var mf = RangeAddress.FirstAddress; var ml = RangeAddress.LastAddress; - foreach (var format in Worksheet.ConditionalFormats.Where(x => x.Ranges.Any(r => r.Intersects(this))).ToList()) + foreach (var format in Worksheet.ConditionalFormats.Where(x => x.Ranges.GetIntersectedRanges(RangeAddress).Any()).ToList()) { var cfRanges = format.Ranges.ToList(); format.Ranges.RemoveAll(); @@ -452,13 +450,7 @@ return false; var ma = range.RangeAddress; var ra = RangeAddress; - - return !( // See if the two ranges intersect... - ma.FirstAddress.ColumnNumber > ra.LastAddress.ColumnNumber - || ma.LastAddress.ColumnNumber < ra.FirstAddress.ColumnNumber - || ma.FirstAddress.RowNumber > ra.LastAddress.RowNumber - || ma.LastAddress.RowNumber < ra.FirstAddress.RowNumber - ); + return ra.Intersects(ma); } IXLRange IXLRangeBase.AsRange() @@ -644,12 +636,11 @@ } } - if (Worksheet.MergedRanges.Any(r => r.Intersects(this))) + var intersectedRanges = Worksheet.MergedRanges.GetIntersectedRanges(RangeAddress).ToList(); + if (intersectedRanges.Any()) { - Int32 minRo = - Worksheet.MergedRanges.Where(r => r.Intersects(this)).Min(r => r.RangeAddress.FirstAddress.RowNumber); - Int32 minCo = - Worksheet.MergedRanges.Where(r => r.Intersects(this)).Min(r => r.RangeAddress.FirstAddress.ColumnNumber); + Int32 minRo = intersectedRanges.Min(r => r.RangeAddress.FirstAddress.RowNumber); + Int32 minCo = intersectedRanges.Min(r => r.RangeAddress.FirstAddress.ColumnNumber); return Worksheet.Cell(minRo, minCo); } @@ -735,12 +726,11 @@ } } - if (Worksheet.MergedRanges.Any(r => r.Intersects(this))) + var intersectedRanges = Worksheet.MergedRanges.GetIntersectedRanges(RangeAddress).ToList(); + if (intersectedRanges.Any()) { - Int32 minRo = - Worksheet.MergedRanges.Where(r => r.Intersects(this)).Max(r => r.RangeAddress.LastAddress.RowNumber); - Int32 minCo = - Worksheet.MergedRanges.Where(r => r.Intersects(this)).Max(r => r.RangeAddress.LastAddress.ColumnNumber); + Int32 minRo = intersectedRanges.Max(r => r.RangeAddress.LastAddress.RowNumber); + Int32 minCo = intersectedRanges.Max(r => r.RangeAddress.LastAddress.ColumnNumber); return Worksheet.Cell(minRo, minCo); } @@ -1401,7 +1391,7 @@ private void ClearMerged() { - var mergeToDelete = Worksheet.Internals.MergedRanges.Where(Intersects).ToList(); + var mergeToDelete = Worksheet.Internals.MergedRanges.GetIntersectedRanges(RangeAddress).ToList(); mergeToDelete.ForEach(m => Worksheet.Internals.MergedRanges.Remove(m)); } @@ -1417,10 +1407,7 @@ public bool Contains(XLAddress address) { - return RangeAddress.FirstAddress.RowNumber <= address.RowNumber && - address.RowNumber <= RangeAddress.LastAddress.RowNumber && - RangeAddress.FirstAddress.ColumnNumber <= address.ColumnNumber && - address.ColumnNumber <= RangeAddress.LastAddress.ColumnNumber; + return RangeAddress.Contains(in address); } public void Delete(XLShiftDeletedCells shiftDeleteCells) @@ -1972,7 +1959,7 @@ var dvEmpty = new List(); foreach (IXLDataValidation dv in Worksheet.DataValidations) { - foreach (IXLRange dvRange in dv.Ranges.Where(dvRange => dvRange.Intersects(this))) + foreach (IXLRange dvRange in dv.Ranges.GetIntersectedRanges(RangeAddress).ToList()) { if (dataValidationToCopy == null) dataValidationToCopy = dv; diff --git a/ClosedXML/Excel/Ranges/XLRanges.cs b/ClosedXML/Excel/Ranges/XLRanges.cs index f6cbc2d..71fc32a 100644 --- a/ClosedXML/Excel/Ranges/XLRanges.cs +++ b/ClosedXML/Excel/Ranges/XLRanges.cs @@ -1,6 +1,7 @@ using System; using System.Collections.Generic; using System.Linq; +using ClosedXML.Excel.Ranges.Index; namespace ClosedXML.Excel { @@ -8,30 +9,43 @@ internal class XLRanges : XLStylizedBase, IXLRanges, IXLStylized { - private readonly List _ranges = new List(); + /// + /// Normally, XLRanges collection includes ranges from a single worksheet, but not necessarily. + /// + private readonly Dictionary> _indexes; + private IEnumerable Ranges => _indexes.Values.SelectMany(index => index.GetAll()).ToList(); + + + private IXLRangeIndex GetRangeIndex(IXLWorksheet worksheet) + { + if (!_indexes.ContainsKey(worksheet)) + _indexes.Add(worksheet, new XLRangeIndex(worksheet)); + + return _indexes[worksheet]; + } public XLRanges() : base(XLWorkbook.DefaultStyleValue) { + _indexes = new Dictionary>(); } #region IXLRanges Members public IXLRanges Clear(XLClearOptions clearOptions = XLClearOptions.All) { - _ranges.ForEach(c => c.Clear(clearOptions)); + Ranges.ForEach(c => c.Clear(clearOptions)); return this; } public void Add(XLRange range) { - Count++; - _ranges.Add(range); + if (GetRangeIndex(range.Worksheet).Add(range)) + Count++; } public void Add(IXLRangeBase range) { - Count++; - _ranges.Add(range.AsRange() as XLRange); + Add(range.AsRange() as XLRange); } public void Add(IXLCell cell) @@ -41,8 +55,8 @@ public void Remove(IXLRange range) { - Count--; - _ranges.RemoveAll(r => r.ToString() == range.ToString()); + if (GetRangeIndex(range.Worksheet).Remove(range)) + Count--; } /// @@ -54,7 +68,10 @@ /// row/column shifting events. Until ranges are unsubscribed they cannot be collected by GC. public void RemoveAll(Predicate match = null, bool releaseEventHandlers = true) { - Count -= _ranges.RemoveAll(match ?? (_ => true)); + foreach (var index in _indexes.Values) + { + Count -= index.RemoveAll(match ?? (_ => true)); + } } public int Count { get; private set; } @@ -62,7 +79,7 @@ public IEnumerator GetEnumerator() { var retList = new List(); - retList.AddRange(_ranges.Where(r => XLHelper.IsValidRangeAddress(r.RangeAddress)).Cast()); + retList.AddRange(Ranges.Where(r => XLHelper.IsValidRangeAddress(r.RangeAddress)).Cast()); return retList.GetEnumerator(); } @@ -73,17 +90,50 @@ public Boolean Contains(IXLCell cell) { - return _ranges.Any(r => r.RangeAddress.IsValid && r.Contains(cell)); + return GetIntersectedRanges((XLAddress)cell.Address).Any(); } public Boolean Contains(IXLRange range) { - return _ranges.Any(r => r.RangeAddress.IsValid && r.Contains(range)); + return GetIntersectedRanges((XLRangeAddress)range.RangeAddress) + .Any(r => r.Contains(range)); + } + + /// + /// Filter ranges from a collection that intersect the specified address. Is much more efficient + /// that using Linq expression .Where(). + /// + public IEnumerable GetIntersectedRanges(IXLRangeAddress rangeAddress) + { + var xlRangeAddress = (XLRangeAddress)rangeAddress; + return GetIntersectedRanges(in xlRangeAddress); + } + + internal IEnumerable GetIntersectedRanges(in XLRangeAddress rangeAddress) + { + return GetRangeIndex(rangeAddress.Worksheet) + .GetIntersectedRanges(rangeAddress); + } + + /// + /// Filter ranges from a collection that intersect the specified address. Is much more efficient + /// that using Linq expression .Where(). + /// + public IEnumerable GetIntersectedRanges(IXLAddress address) + { + var xlAddress = (XLAddress) address; + return GetIntersectedRanges(in xlAddress); + } + + internal IEnumerable GetIntersectedRanges(in XLAddress address) + { + return GetRangeIndex(address.Worksheet) + .GetIntersectedRanges(address); } public IEnumerable DataValidation { - get { return _ranges.Select(range => range.DataValidation).Where(dv => dv != null); } + get { return Ranges.Select(range => range.DataValidation).Where(dv => dv != null); } } public IXLRanges AddToNamed(String rangeName) @@ -98,25 +148,25 @@ public IXLRanges AddToNamed(String rangeName, XLScope scope, String comment) { - _ranges.ForEach(r => r.AddToNamed(rangeName, scope, comment)); + Ranges.ForEach(r => r.AddToNamed(rangeName, scope, comment)); return this; } public Object Value { - set { _ranges.ForEach(r => r.Value = value); } + set { Ranges.ForEach(r => r.Value = value); } } public IXLRanges SetValue(T value) { - _ranges.ForEach(r => r.SetValue(value)); + Ranges.ForEach(r => r.SetValue(value)); return this; } public IXLCells Cells() { var cells = new XLCells(false, false); - foreach (XLRange container in _ranges) + foreach (XLRange container in Ranges) cells.Add(container.RangeAddress); return cells; } @@ -124,7 +174,7 @@ public IXLCells CellsUsed() { var cells = new XLCells(true, false); - foreach (XLRange container in _ranges) + foreach (XLRange container in Ranges) cells.Add(container.RangeAddress); return cells; } @@ -132,14 +182,14 @@ public IXLCells CellsUsed(Boolean includeFormats) { var cells = new XLCells(true, includeFormats); - foreach (XLRange container in _ranges) + foreach (XLRange container in Ranges) cells.Add(container.RangeAddress); return cells; } public IXLRanges SetDataType(XLDataType dataType) { - _ranges.ForEach(c => c.DataType = dataType); + Ranges.ForEach(c => c.DataType = dataType); return this; } @@ -152,7 +202,7 @@ get { yield return Style; - foreach (XLRange rng in _ranges) + foreach (XLRange rng in Ranges) { yield return rng.Style; foreach (XLCell r in rng.Worksheet.Internals.CellsCollection.GetCells( @@ -169,7 +219,7 @@ { get { - foreach (XLRange rng in _ranges) + foreach (XLRange rng in Ranges) yield return rng; } } @@ -183,7 +233,7 @@ public override string ToString() { - String retVal = _ranges.Aggregate(String.Empty, (agg, r) => agg + (r.ToString() + ",")); + String retVal = Ranges.Aggregate(String.Empty, (agg, r) => agg + (r.ToString() + ",")); if (retVal.Length > 0) retVal = retVal.Substring(0, retVal.Length - 1); return retVal; } @@ -198,22 +248,22 @@ if (other == null) return false; - return _ranges.Count == other._ranges.Count && - _ranges.Select(thisRange => Enumerable.Contains(other._ranges, thisRange)).All(foundOne => foundOne); + return Ranges.Count() == other.Ranges.Count() && + Ranges.Select(thisRange => Enumerable.Contains(other.Ranges, thisRange)).All(foundOne => foundOne); } public override int GetHashCode() { - return _ranges.Aggregate(0, (current, r) => current ^ r.GetHashCode()); + return Ranges.Aggregate(0, (current, r) => current ^ r.GetHashCode()); } public IXLDataValidation SetDataValidation() { - foreach (XLRange range in _ranges) + foreach (XLRange range in Ranges) { foreach (IXLDataValidation dv in range.Worksheet.DataValidations) { - foreach (IXLRange dvRange in dv.Ranges.Where(dvRange => dvRange.Intersects(range))) + foreach (IXLRange dvRange in dv.Ranges.GetIntersectedRanges(range.RangeAddress)) { dv.Ranges.Remove(dvRange); foreach (IXLCell c in dvRange.Cells().Where(c => !range.Contains(c.Address.ToString()))) @@ -225,7 +275,7 @@ } var dataValidation = new XLDataValidation(this); - _ranges.First().Worksheet.DataValidations.Add(dataValidation); + Ranges.First().Worksheet.DataValidations.Add(dataValidation); return dataValidation; } diff --git a/ClosedXML/Excel/XLWorksheet.cs b/ClosedXML/Excel/XLWorksheet.cs index 4e4afad..826f35b 100644 --- a/ClosedXML/Excel/XLWorksheet.cs +++ b/ClosedXML/Excel/XLWorksheet.cs @@ -6,6 +6,7 @@ using System.Drawing; using System.IO; using System.Linq; +using ClosedXML.Excel.Ranges.Index; namespace ClosedXML.Excel { @@ -17,6 +18,7 @@ private readonly Dictionary _rowOutlineCount = new Dictionary(); private readonly XLRangeFactory _rangeFactory; private readonly XLRangeRepository _rangeRepository; + private readonly List _rangeIndices; internal Int32 ZOrder = 1; private String _name; internal Int32 _position; @@ -52,6 +54,7 @@ RangeAddress = new XLRangeAddress(firstAddress, lastAddress); _rangeFactory = new XLRangeFactory(this); _rangeRepository = new XLRangeRepository(workbook, _rangeFactory.Create); + _rangeIndices = new List(); Pictures = new XLPictures(this); NamedRanges = new XLNamedRanges(this); @@ -978,11 +981,17 @@ return ColumnsUsed(false, predicate); } + internal void RegisterRangeIndex(IXLRangeIndex rangeIndex) + { + _rangeIndices.Add(rangeIndex); + } + public void Dispose() { Internals.Dispose(); Pictures.ForEach(p => p.Dispose()); _rangeRepository.Clear(); + _rangeIndices.Clear(); } #endregion IXLWorksheet Members @@ -1153,10 +1162,11 @@ { if (!range.IsEntireColumn()) { - var model = Worksheet.Range(range.RangeAddress.FirstAddress, + var model = new XLRangeAddress( + range.RangeAddress.FirstAddress, new XLAddress(range.RangeAddress.LastAddress.RowNumber, XLHelper.MaxColumnNumber, false, false)); var rangesToSplit = Worksheet.MergedRanges - .Where(mr => mr.Intersects(model)) // in #803 this must be optimized too + .GetIntersectedRanges(model) .Where(r => r.RangeAddress.FirstAddress.RowNumber < range.RangeAddress.FirstAddress.RowNumber || r.RangeAddress.LastAddress.RowNumber > range.RangeAddress.LastAddress.RowNumber) .ToList(); @@ -1234,10 +1244,11 @@ { if (!range.IsEntireRow()) { - var model = Worksheet.Range(range.RangeAddress.FirstAddress, + var model = new XLRangeAddress( + range.RangeAddress.FirstAddress, new XLAddress(XLHelper.MaxRowNumber, range.RangeAddress.LastAddress.ColumnNumber, false, false)); var rangesToSplit = Worksheet.MergedRanges - .Where(mr => mr.Intersects(model)) // in #803 this must be optimized too + .GetIntersectedRanges(model) .Where(r => r.RangeAddress.FirstAddress.ColumnNumber < range.RangeAddress.FirstAddress.ColumnNumber || r.RangeAddress.LastAddress.ColumnNumber > range.RangeAddress.LastAddress.ColumnNumber) .ToList(); @@ -1715,8 +1726,14 @@ if (_rangeRepository == null) return; - _rangeRepository.Replace(new XLRangeKey(rangeType, oldAddress), - new XLRangeKey(rangeType, newAddress)); + var range = _rangeRepository.Replace(new XLRangeKey(rangeType, oldAddress), + new XLRangeKey(rangeType, newAddress)); + + foreach (var rangeIndex in _rangeIndices) + { + if (rangeIndex.Remove(range)) + rangeIndex.Add(range); + } } internal void DeleteColumn(int columnNumber) diff --git a/ClosedXML_Tests/Excel/Ranges/RangeIndexTest.cs b/ClosedXML_Tests/Excel/Ranges/RangeIndexTest.cs new file mode 100644 index 0000000..3103a84 --- /dev/null +++ b/ClosedXML_Tests/Excel/Ranges/RangeIndexTest.cs @@ -0,0 +1,270 @@ +using ClosedXML.Excel; +using ClosedXML.Excel.Patterns; +using ClosedXML.Excel.Ranges.Index; +using NUnit.Framework; +using System.Collections.Generic; +using System.Linq; + +namespace ClosedXML_Tests.Excel.Ranges +{ + [TestFixture] + public class RangeIndexTest + { + private const int TEST_COUNT = 10000; + + [Test] + public void FindExistingMatches() + { + using (var wb = new XLWorkbook()) + { + var ws = wb.Worksheets.Add("Sheet1") as XLWorksheet; + var index = FillIndexWithTestData(ws); + + for (int i = 1; i <= TEST_COUNT; i++) + { + for (int j = 2; j <= 4; j++) + { + var address = new XLAddress(ws, i * 2, j, false, false); + Assert.True(index.Contains(in address)); + } + } + } + } + + [Test] + public void FindNonExistingMatches() + { + using (var wb = new XLWorkbook()) + { + var ws = wb.Worksheets.Add("Sheet1") as XLWorksheet; + var index = FillIndexWithTestData(ws); + + for (int i = 1; i <= TEST_COUNT; i++) + { + var address = new XLAddress(ws, i * 2 + 1, 3, false, false); + Assert.False(index.Contains(in address)); + } + } + } + + [Test] + public void FindExistingIntersections() + { + using (var wb = new XLWorkbook()) + { + var ws = wb.Worksheets.Add("Sheet1") as XLWorksheet; + var index = FillIndexWithTestData(ws); + + for (int i = 1; i <= TEST_COUNT; i++) + { + var rangeAddress = new XLRangeAddress( + new XLAddress(ws, i * 2, 1 + i % 4, false, false), + new XLAddress(ws, i * 2 + 1, 8 - i % 3, false, false)); + + Assert.True(index.Intersects(in rangeAddress)); + } + + for (int i = 2; i < 4; i++) + { + var columnAddress = XLRangeAddress.EntireColumn(ws, i); + Assert.True(index.Intersects(in columnAddress)); + } + } + } + + [Test] + public void FindNonExistingIntersections() + { + using (var wb = new XLWorkbook()) + { + var ws = wb.Worksheets.Add("Sheet1") as XLWorksheet; + var index = FillIndexWithTestData(ws); + + for (int i = 1; i <= TEST_COUNT; i++) + { + var rangeAddress = new XLRangeAddress( + new XLAddress(ws, i * 2 + 1, 1 + i % 4, false, false), + new XLAddress(ws, i * 2 + 1, 8 - i % 3, false, false)); + + Assert.False(index.Intersects(in rangeAddress)); + } + + var columnAddress = XLRangeAddress.EntireColumn(ws, 1); + Assert.False(index.Intersects(in columnAddress)); + columnAddress = XLRangeAddress.EntireColumn(ws, 5); + Assert.False(index.Intersects(in columnAddress)); + } + } + + [Test] + public void FindMatchAfterColumnShifting() + { + using (var wb = new XLWorkbook()) + { + var ws = wb.Worksheets.Add("Sheet1") as XLWorksheet; + var index = FillIndexWithTestData(ws); + + ws.Column(3).InsertColumnsBefore(2); + + var address = new XLAddress(ws, 102, 6, false, false); + + Assert.True(index.Contains(in address)); + } + } + + [Test] + public void FindIntersectionsAfterColumnShifting() + { + using (var wb = new XLWorkbook()) + { + var ws = wb.Worksheets.Add("Sheet1") as XLWorksheet; + var index = FillIndexWithTestData(ws); + + ws.Column(3).InsertColumnsBefore(2); + + var rangeAddress = new XLRangeAddress(ws, "F102:E103"); + + Assert.True(index.Intersects(in rangeAddress)); + } + } + + [Test] + public void FindMatchAfterRowShifting() + { + using (var wb = new XLWorkbook()) + { + var ws = wb.Worksheets.Add("Sheet1") as XLWorksheet; + var index = FillIndexWithTestData(ws); + + ws.Row(10).InsertRowsBelow(3); + + var address = new XLAddress(ws, 103, 4, false, false); + + Assert.True(index.Contains(in address)); + } + } + + [Test] + public void FindIntersectionsAfterRowShifting() + { + using (var wb = new XLWorkbook()) + { + var ws = wb.Worksheets.Add("Sheet1") as XLWorksheet; + var index = FillIndexWithTestData(ws); + + ws.Row(10).InsertRowsBelow(3); + + var rangeAddress = new XLRangeAddress(ws, "C103:E103"); + + Assert.True(index.Intersects(in rangeAddress)); + } + } + + [Test] + public void CreateQuadTree() + { + using (var wb = new XLWorkbook()) + { + var ws = wb.Worksheets.Add("Sheet1") as XLWorksheet; + var quadTree = new Quadrant(); + var range = ws.Range("BT76:CA87"); + + quadTree.Add(range); + + var level0 = quadTree; + Assert.AreEqual(1, level0.MinimumColumn); + Assert.AreEqual(XLHelper.MaxColumnNumber, level0.MaximumColumn); + Assert.AreEqual(1, level0.MinimumRow); + Assert.AreEqual(XLHelper.MaxRowNumber, level0.MaximumRow); + Assert.IsNull(level0.Ranges); + Assert.AreEqual(128, level0.Children.Count()); + Assert.True(level0.Children.All(child => child.Level == 1)); + Assert.AreEqual(64, level0.Children.Count(child => + child.MinimumColumn == 1 && + child.MaximumColumn == 8192 && + child.X == 0)); + Assert.AreEqual(64, level0.Children.Count(child => + child.MinimumColumn == 8193 && + child.MaximumColumn == 16384 && + child.X == 1)); + Assert.AreEqual(2, level0.Children.Count(child => + child.MinimumRow == 1 && + child.MaximumRow == 8192 && + child.Y == 0)); + Assert.AreEqual(2, level0.Children.Count(child => + child.MinimumRow == 16385 && + child.MaximumRow == 24576 && + child.Y == 2)); + + Assert.True(level0.Children.ElementAt(0).Children.Any()); + Assert.True(level0.Children.Skip(1).All(child => child.Children == null)); + + var level8 = level0 + .Children.First() // 1 + .Children.First() // 2 + .Children.First() // 3 + .Children.First() // 4 + .Children.First() // 5 + .Children.First() // 6 + .Children.First() // 7 + .Children.Last(); // 8 + + Assert.AreEqual(65, level8.MinimumColumn); + Assert.AreEqual(65, level8.MinimumRow); + Assert.AreEqual(128, level8.MaximumColumn); + Assert.AreEqual(128, level8.MaximumRow); + + var level9 = level8.Children.First(); + Assert.NotNull(level9.Ranges); + Assert.AreEqual(range, level9.Ranges.Single()); + } + } + + [Test] + public void XLRangesCountChangesCorrectly() + { + using (var wb = new XLWorkbook()) + { + var ws = wb.Worksheets.Add("Sheet1") as XLWorksheet; + var range1 = ws.Range("A1:B2"); + var range2 = ws.Range("A2:B3"); + var range3 = ws.Range("A1:B2"); // same as range1 + + var ranges = new XLRanges(); + ranges.Add(range1); + Assert.AreEqual(1, ranges.Count); + ranges.Add(range2); + Assert.AreEqual(2, ranges.Count); + ranges.Add(range3); + Assert.AreEqual(2, ranges.Count); + + Assert.AreEqual(ranges.Count, ranges.Count()); + + ranges.Remove(range3); + Assert.AreEqual(1, ranges.Count); + ranges.Remove(range2); + Assert.AreEqual(0, ranges.Count); + ranges.Remove(range1); + Assert.AreEqual(0, ranges.Count); + } + } + + private IXLRangeIndex CreateRangeIndex(IXLWorksheet worksheet) + { + return new XLRangeIndex((XLWorksheet)worksheet); + } + + private IXLRangeIndex FillIndexWithTestData(IXLWorksheet worksheet) + { + var ranges = new List(); + for (int i = 1; i <= TEST_COUNT; i++) + { + ranges.Add(worksheet.Range(i * 2, 2, i * 2, 4)); + } + + var index = CreateRangeIndex(worksheet); + ranges.ForEach(r => index.Add(r)); + return index; + } + } +} diff --git a/ClosedXML_Tests/Excel/Ranges/RangesConsolidationTests.cs b/ClosedXML_Tests/Excel/Ranges/RangesConsolidationTests.cs index 42e314f..a86f19c 100644 --- a/ClosedXML_Tests/Excel/Ranges/RangesConsolidationTests.cs +++ b/ClosedXML_Tests/Excel/Ranges/RangesConsolidationTests.cs @@ -47,7 +47,11 @@ ranges.Add(ws.Column("F")); ranges.Add(ws.Column("E")); - var consRanges = ranges.Consolidate().ToList(); + var consRanges = ranges.Consolidate() + .OrderBy(r => r.Worksheet.Name) + .ThenBy(r => r.RangeAddress.FirstAddress.RowNumber) + .ThenBy(r => r.RangeAddress.FirstAddress.ColumnNumber) + .ToList(); Assert.AreEqual(3, consRanges.Count); Assert.AreEqual("D1:F1048576", consRanges[0].RangeAddress.ToString()); @@ -80,7 +84,11 @@ ranges.Add(ws1.Range("I9:I13")); ranges.Add(ws1.Range("C4:D5")); - var consRanges = ranges.Consolidate().ToList(); + var consRanges = ranges.Consolidate() + .OrderBy(r => r.Worksheet.Name) + .ThenBy(r => r.RangeAddress.FirstAddress.RowNumber) + .ThenBy(r => r.RangeAddress.FirstAddress.ColumnNumber) + .ToList(); Assert.AreEqual(9, consRanges.Count); Assert.AreEqual("Sheet1!$A$1:$E$9", consRanges[0].RangeAddress.ToStringFixed(XLReferenceStyle.Default, true));