@@ -46,23 +46,67 @@ export function parseRange(a1: string): CellRange | undefined {
4646
4747/** Grows a range until it covers every merged cell it touches, as Excel selects. */
4848export function coverMerges ( range : CellRange , merges : readonly CellRange [ ] ) : CellRange {
49- const grown = merges . reduce (
50- ( current , merge ) =>
51- overlaps ( current , merge )
52- ? {
53- top : Math . min ( current . top , merge . top ) ,
54- left : Math . min ( current . left , merge . left ) ,
55- bottom : Math . max ( current . bottom , merge . bottom ) ,
56- right : Math . max ( current . right , merge . right ) ,
57- }
58- : current ,
59- range ,
60- ) ;
61-
62- // A merge the range grew into can touch another one it did not reach before.
63- if ( same ( grown , range ) ) return grown ;
49+ let grown = range ;
50+ for ( let pass = 0 ; pass < 2 ; pass ++ ) {
51+ const next = merges . reduce (
52+ ( current , merge ) =>
53+ overlaps ( current , merge )
54+ ? {
55+ top : Math . min ( current . top , merge . top ) ,
56+ left : Math . min ( current . left , merge . left ) ,
57+ bottom : Math . max ( current . bottom , merge . bottom ) ,
58+ right : Math . max ( current . right , merge . right ) ,
59+ }
60+ : current ,
61+ grown ,
62+ ) ;
63+ if ( same ( next , grown ) ) return next ;
64+ grown = next ;
65+ }
6466
65- return coverMerges ( grown , merges ) ;
67+ // Each overlap inequality becomes true only once as the selection grows. Sweep sorted
68+ // edges so a chain of merges cannot force repeated full scans or recursive stack growth.
69+ const sweeps = (
70+ [
71+ { mergeEdge : "top" , rangeEdge : "bottom" , direction : 1 } ,
72+ { mergeEdge : "bottom" , rangeEdge : "top" , direction : - 1 } ,
73+ { mergeEdge : "left" , rangeEdge : "right" , direction : 1 } ,
74+ { mergeEdge : "right" , rangeEdge : "left" , direction : - 1 } ,
75+ ] as const
76+ ) . map ( ( { mergeEdge, rangeEdge, direction } ) => ( {
77+ rangeEdge,
78+ direction,
79+ position : 0 ,
80+ edges : merges
81+ . map ( ( merge , index ) => ( { index, value : direction * merge [ mergeEdge ] } ) )
82+ . sort ( ( a , b ) => a . value - b . value ) ,
83+ } ) ) ;
84+ const crossed = new Uint8Array ( merges . length ) ;
85+ let changed ;
86+ do {
87+ changed = false ;
88+ for ( const sweep of sweeps ) {
89+ let edge = sweep . edges [ sweep . position ] ;
90+ while ( edge && edge . value <= sweep . direction * grown [ sweep . rangeEdge ] ) {
91+ const index = edge . index ;
92+ crossed [ index ] = crossed [ index ] ! + 1 ;
93+ if ( crossed [ index ] === 4 ) {
94+ const merge = merges [ index ] ! ;
95+ const next = {
96+ top : Math . min ( grown . top , merge . top ) ,
97+ left : Math . min ( grown . left , merge . left ) ,
98+ bottom : Math . max ( grown . bottom , merge . bottom ) ,
99+ right : Math . max ( grown . right , merge . right ) ,
100+ } ;
101+ changed ||= ! same ( grown , next ) ;
102+ grown = next ;
103+ }
104+ edge = sweep . edges [ ++ sweep . position ] ;
105+ }
106+ }
107+ } while ( changed ) ;
108+
109+ return grown ;
66110}
67111
68112/**
0 commit comments