import * as vscode from 'vscode' ; import * as textUtil from './text-util' ; export class DisjointRangeSet { private ranges : vscode . Range [ ] ; constructor ( ) { this . ranges = [ ] ; } private static makeFromSortedRanges ( ranges ) { const result = new DisjointRangeSet ( ) ; result . ranges = ranges ; return result ; } public getStart ( ) { if ( this . ranges . length > 0 ) return this . ranges [ 0 ] . start ; else return new vscode . Position ( 0 , 0 ) ; } public getEnd ( ) { if ( this . ranges . length > 0 ) return this . ranges [ this . ranges . length - 1 ] . end ; else return new vscode . Position ( 0 , 0 ) ; } public getTotalRange ( ) { if ( this . ranges . length > 0 ) return new vscode . Range ( this . ranges [ 0 ] . start , this . ranges [ this . ranges . length - 1 ] . end ) ; else return new vscode . Range ( 0 , 0 , 0 , 0 ) ; } public isEmpty ( ) { return this . ranges . length == 0 ; } public isEmptyRange ( ) { return this . ranges . length == 0 || this . ranges [ 0 ] . start . isEqual ( this . ranges [ this . ranges . length - 1 ] . end ) ; } public insertRanges ( newRanges ) { const totalRange = newRanges . getTotalRange ( ) ; const insertionIdx = this . findIndex ( totalRange . start ) ; const next = this . ranges [ insertionIdx ] ; if ( next && totalRange . end . isAfter ( next . start ) ) return false ; this . ranges . splice . apply ( this . ranges , ( < any [ ] > [ insertionIdx , 0 ] ) . concat ( newRanges . ranges ) ) ; } returns public insert ( range ) { const insertionIdx = this . findIndex ( range . start ) ; const next = this . ranges [ insertionIdx ] ; if ( next && range . end . isAfter ( next . start ) ) return false ; this . ranges . splice ( insertionIdx , 0 , range ) ; return true ; } public isOverlapping ( range ) { const insertionIdx = this . findIndex ( range . start ) ; const next = this . ranges [ insertionIdx ] ; if ( next && range . end . isAfter ( next . start ) ) return true ; return false ; } public removeOverlapping ( range , options = { includeTouchingStart : false , includeTouchingEnd : false } ) { const inclStart = options . includeTouchingStart || false ; const inclEnd = options . includeTouchingEnd || false ; let begin = this . findIndex ( range . start ) ; if ( inclStart && begin > 0 && this . ranges [ begin - 1 ] . end . isEqual ( range . start ) ) -- begin ; let end = begin ; while ( end < this . ranges . length && this . ranges [ end ] . start . isBefore ( range . end ) ) ++ end ; if ( inclEnd && end < this . ranges . length && this . ranges [ end ] . start . isEqual ( range . end ) ) ++ end ; return this . ranges . splice ( begin , end - begin ) ; } public subtractRanges ( ranges ) { let idx1 = 0 ; const newRanges = this . ranges . filter ( ( r ) => { let idx = ranges . ranges . indexOf ( r , idx1 ) ; if ( idx != - 1 ) { idx1 = idx ; return false ; } else return true ; } ) ; return DisjointRangeSet . makeFromSortedRanges ( newRanges ) ; } private validateFoundIndex ( idx , pos , exclStart , inclEnd ) { if ( idx > this . ranges . length || idx < 0 ) throw "idx is out of range: idx > this.ranges.length || idx < 0" ; else if ( this . ranges . length == 0 ) return ; else if ( idx < this . ranges . length && ! textUtil . rangeContains ( this . ranges [ idx ] , pos , exclStart , inclEnd ) && this . ranges [ idx ] . start . isBefore ( pos ) ) throw "idx is too big; range comes before pos" ; else if ( idx > 0 && this . ranges [ idx - 1 ] . end . isAfter ( pos ) ) throw "idx is too big; previous element comes after pos" ; else if ( idx < this . ranges . length - 1 && this . ranges [ idx + 1 ] . start . isBefore ( pos ) && ( ! inclEnd || ! this . ranges [ idx ] . end . isEqual ( pos ) ) ) throw "idx is too small; next element comes before pos" ; } /** returns the index of the range that starts at or after the given position
     * if pos is after all range-starts, then this returns this.ranges.length
     */ private findIndex ( pos , options = { excludeStart : false , includeEnd : false } ) { const exclStart = options . excludeStart || false ; const inclEnd = options . includeEnd || false ; let begin = 0 ; let end = this . ranges . length ; if ( this . ranges . length == 0 ) return 0 ; if ( this . ranges [ this . ranges . length - 1 ] . end . isBeforeOrEqual ( pos ) && ( ! inclEnd || ! this . ranges [ this . ranges . length - 1 ] . end . isEqual ( pos ) ) ) return this . ranges . length ; let idx = Math . floor ( ( begin + end ) / 2 ) ; while ( begin < end ) { const range = this . ranges [ idx ] ; if ( textUtil . rangeContains ( range , pos , exclStart , inclEnd ) ) break ; else if ( pos . isBefore ( range . start ) || ( exclStart && pos . isEqual ( range . start ) ) ) end = idx ; else begin = idx + 1 ; idx = Math . floor ( ( begin + end ) / 2 ) ; } this . validateFoundIndex ( idx , pos , exclStart , inclEnd ) ; return idx ; } /** returns the range that contains pos, or else undefined */ public find ( pos , options = { excludeStart : false , includeEnd : false } ) { const idx = this . findIndex ( pos , options ) ; const match = this . ranges [ idx ] ; if ( match && textUtil . rangeContains ( match , pos , options . excludeStart , options . includeEnd ) ) return match ; else return undefined ; } public findPreceding ( pos ) { const idx = this . findIndex ( pos ) ; const match = this . ranges [ idx - 1 ] ; return match ; } public * getRangesStartingAt ( pos ) { for ( let idx = this . findIndex ( pos ) ; idx < this . ranges . length ; ++ idx ) yield this . ranges [ idx ] ; } public getRanges ( ) { return this . ranges ; } public shiftRangeDelta ( delta ) { if ( this . ranges . length == 0 || ( delta . linesDelta == 0 && delta . endCharactersDelta == 0 ) ) return new vscode . Range ( delta . start , delta . end ) ; let firstIdx = this . findIndex ( delta . start ) ; let idx = firstIdx ; if ( delta . linesDelta != 0 ) { for ( ; idx < this . ranges . length ; ++ idx ) this . ranges [ idx ] = textUtil . rangeTranslate ( this . ranges [ idx ] , delta ) ; } else { for ( ; idx < this . ranges . length && this . ranges [ idx ] . start . line <= delta . end . line ; ++ idx ) { this . ranges [ idx ] = textUtil . rangeTranslate ( this . ranges [ idx ] , delta ) ; } } if ( firstIdx == idx ) return new vscode . Range ( 0 , 0 , 0 , 0 ) ; else if ( idx == this . ranges . length ) return new vscode . Range ( this . ranges [ firstIdx ] . start , this . ranges [ idx - 1 ] . end ) ; else return new vscode . Range ( this . ranges [ firstIdx ] . start , this . ranges [ idx - 1 ] . end ) ; } public shiftTextChange ( target , text ) { return this . shiftRangeDelta ( textUtil . toRangeDelta ( target , text ) ) ; } public getOverlapRanges ( range ) { const begin = this . findIndex ( range . start ) ; const end = this . findIndex ( range . end ) ; return this . ranges . slice ( begin , end ) ; } public getOverlap ( range , options = { excludeStart : false , includeEnd : false } ) { const begin = this . findIndex ( range . start , { excludeStart : options . excludeStart , includeEnd : range . isEmpty } ) ; let end = this . findIndex ( range . end , { excludeStart : true , includeEnd : options . includeEnd } ) ; if ( end < this . ranges . length && textUtil . rangeContains ( this . ranges [ end ] , range . end , ! range . isEmpty , options . includeEnd ) ) ++ end ; return DisjointRangeSet . makeFromSortedRanges ( this . ranges . slice ( begin , end ) ) ; } }