import { Color , RedBlackTree , Node } from "../pageModel" ; import { SENTINEL_INDEX , nextNode , treeMinimum , recomputeTreeMetadata , resetSentinel , } from "./tree" ; import { leftRotate , rightRotate } from "./rotate" ; import { isContentRedBlackTree } from "../contentTree/contentModel" ; import { calculateCharCount , calculateLineFeedCount , updateContentTreeMetadata , } from "../contentTree/tree" ; import { isStructureRedBlackTree } from "../structureTree/structureModel" ; import { calculateLengthCount , updateStructureTreeMetadata , } from "../structureTree/tree" ; param tree param x export function fixDelete < T extends Node > ( tree , x ) { let w ; while ( x !== tree . root && tree . nodes [ x ] . color === Color . Black ) { if ( x === tree . nodes [ tree . nodes [ x ] . parent ] . left ) { w = tree . nodes [ tree . nodes [ x ] . parent ] . right ; if ( tree . nodes [ w ] . color === Color . Red ) { tree . nodes [ w ] . color = Color . Black ; tree . nodes [ tree . nodes [ x ] . parent ] . color = Color . Red ; leftRotate ( tree , tree . nodes [ x ] . parent ) ; w = tree . nodes [ tree . nodes [ x ] . parent ] . right ; } if ( tree . nodes [ tree . nodes [ w ] . left ] . color === Color . Black && tree . nodes [ tree . nodes [ w ] . right ] . color === Color . Black ) { tree . nodes [ w ] . color = Color . Red ; x = tree . nodes [ x ] . parent ; } else { if ( tree . nodes [ tree . nodes [ w ] . right ] . color === Color . Black ) { tree . nodes [ tree . nodes [ w ] . left ] . color = Color . Black ; tree . nodes [ w ] . color = Color . Red ; rightRotate ( tree , w ) ; w = tree . nodes [ tree . nodes [ x ] . parent ] . right ; } tree . nodes [ w ] . color = tree . nodes [ tree . nodes [ x ] . parent ] . color ; tree . nodes [ tree . nodes [ x ] . parent ] . color = Color . Black ; tree . nodes [ tree . nodes [ w ] . right ] . color = Color . Black ; leftRotate ( tree , tree . nodes [ x ] . parent ) ; x = tree . root ; } } else { w = tree . nodes [ tree . nodes [ x ] . parent ] . left ; if ( tree . nodes [ w ] . color === Color . Red ) { tree . nodes [ w ] . color = Color . Black ; tree . nodes [ tree . nodes [ x ] . parent ] . color = Color . Red ; rightRotate ( tree , tree . nodes [ x ] . parent ) ; w = tree . nodes [ tree . nodes [ x ] . parent ] . left ; } if ( tree . nodes [ tree . nodes [ w ] . left ] . color === Color . Black && tree . nodes [ tree . nodes [ w ] . right ] . color === Color . Black ) { tree . nodes [ w ] . color = Color . Red ; x = tree . nodes [ x ] . parent ; } else { if ( tree . nodes [ tree . nodes [ w ] . left ] . color === Color . Black ) { tree . nodes [ tree . nodes [ w ] . right ] . color = Color . Black ; tree . nodes [ w ] . color = Color . Red ; leftRotate ( tree , w ) ; w = tree . nodes [ tree . nodes [ x ] . parent ] . left ; } tree . nodes [ w ] . color = tree . nodes [ tree . nodes [ x ] . parent ] . color ; tree . nodes [ tree . nodes [ x ] . parent ] . color = Color . Black ; tree . nodes [ tree . nodes [ w ] . left ] . color = Color . Black ; rightRotate ( tree , tree . nodes [ x ] . parent ) ; x = tree . root ; } } } tree . nodes [ x ] . color = Color . Black ; } param tree param node export function detach < T extends Node > ( tree , node ) { const parent = tree . nodes [ tree . nodes [ node ] . parent ] ; if ( parent . left === node ) { tree . nodes [ tree . nodes [ node ] . parent ] . left = SENTINEL_INDEX ; } else if ( parent . right === node ) { tree . nodes [ tree . nodes [ node ] . parent ] . right = SENTINEL_INDEX ; } tree . nodes [ node ] . color = Color . Black ; tree . nodes [ node ] . parent = SENTINEL_INDEX ; tree . nodes [ node ] . left = SENTINEL_INDEX ; tree . nodes [ node ] . right = SENTINEL_INDEX ; } param tree param z export function deleteNode < T extends Node > ( tree , z ) { let xTemp ; let yTemp ; if ( tree . nodes [ z ] . left === SENTINEL_INDEX ) { yTemp = z ; tree . nodes [ yTemp ] = tree . nodes [ z ] ; xTemp = tree . nodes [ yTemp ] . right ; } else if ( tree . nodes [ z ] . right === SENTINEL_INDEX ) { yTemp = z ; tree . nodes [ yTemp ] = tree . nodes [ z ] ; xTemp = tree . nodes [ yTemp ] . left ; } else { const result = treeMinimum ( tree . nodes , tree . nodes [ z ] . right ) ; yTemp = result . index ; tree . nodes [ yTemp ] = result . node ; xTemp = tree . nodes [ yTemp ] . right ; } const x = xTemp ; const y = yTemp ; if ( y === tree . root ) { tree . root = x ; ( tree . nodes [ x ] as T ) . color = Color . Black ; detach ( tree , z ) ; tree . nodes [ tree . root ] . parent = SENTINEL_INDEX ; resetSentinel ( tree ) ; return ; } const yWasRed = tree . nodes [ y ] . color === Color . Red ; if ( y === tree . nodes [ tree . nodes [ y ] . parent ] . left ) { tree . nodes [ tree . nodes [ y ] . parent ] . left = x ; } else { tree . nodes [ tree . nodes [ y ] . parent ] . right = x ; } if ( y === z ) { tree . nodes [ x ] . parent = tree . nodes [ y ] . parent ; recomputeTreeMetadata ( tree , x ) ; } else { if ( tree . nodes [ y ] . parent === z ) { tree . nodes [ x ] . parent = y ; } else { tree . nodes [ x ] . parent = tree . nodes [ y ] . parent ; } recomputeTreeMetadata ( tree , x ) ; ( tree . nodes [ y ] as T ) . left = tree . nodes [ z ] . left ; ( tree . nodes [ y ] as T ) . right = tree . nodes [ z ] . right ; ( tree . nodes [ y ] as T ) . parent = tree . nodes [ z ] . parent ; ( tree . nodes [ y ] as T ) . color = tree . nodes [ z ] . color ; if ( z === tree . root ) { tree . root = y ; } else { if ( z === tree . nodes [ tree . nodes [ z ] . parent ] . left ) { tree . nodes [ tree . nodes [ z ] . parent ] . left = y ; } else { tree . nodes [ tree . nodes [ z ] . parent ] . right = y ; } } if ( tree . nodes [ y ] . left !== SENTINEL_INDEX ) { tree . nodes [ tree . nodes [ y ] . left ] . parent = y ; } if ( tree . nodes [ y ] . right !== SENTINEL_INDEX ) { tree . nodes [ tree . nodes [ y ] . right ] . parent = y ; } if ( isContentRedBlackTree ( tree ) ) { tree . nodes [ y ] . leftCharCount = tree . nodes [ z ] . leftCharCount ; tree . nodes [ y ] . leftLineFeedCount = tree . nodes [ z ] . leftLineFeedCount ; } else if ( isStructureRedBlackTree ( tree ) ) { tree . nodes [ y ] . leftSubTreeLength = tree . nodes [ z ] . leftSubTreeLength ; } recomputeTreeMetadata ( tree , y ) ; } detach ( tree , z ) ; if ( tree . nodes [ tree . nodes [ x ] . parent ] . left === x ) { if ( isContentRedBlackTree ( tree ) ) { const newSizeLeft = calculateCharCount ( tree , x ) ; const newLFLeft = calculateLineFeedCount ( tree , x ) ; if ( newSizeLeft !== tree . nodes [ tree . nodes [ x ] . parent ] . leftCharCount || newLFLeft !== tree . nodes [ tree . nodes [ x ] . parent ] . leftLineFeedCount ) { const charDelta = newSizeLeft - tree . nodes [ tree . nodes [ x ] . parent ] . leftCharCount ; const lineFeedDelta = newLFLeft - tree . nodes [ tree . nodes [ x ] . parent ] . leftLineFeedCount ; tree . nodes [ tree . nodes [ x ] . parent ] . leftCharCount = newSizeLeft ; tree . nodes [ tree . nodes [ x ] . parent ] . leftLineFeedCount = newSizeLeft ; updateContentTreeMetadata ( tree , tree . nodes [ x ] . parent , charDelta , lineFeedDelta ) ; } } else if ( isStructureRedBlackTree ( tree ) ) { const newLeftSubTreeLength = calculateLengthCount ( tree , x ) ; if ( newLeftSubTreeLength !== tree . nodes [ tree . nodes [ x ] . parent ] . leftSubTreeLength ) { const lengthDelta = newLeftSubTreeLength - tree . nodes [ tree . nodes [ x ] . parent ] . leftSubTreeLength ; updateStructureTreeMetadata ( tree , tree . nodes [ x ] . parent , lengthDelta ) ; } } } recomputeTreeMetadata ( tree , tree . nodes [ x ] . parent ) ; if ( yWasRed ) { resetSentinel ( tree ) ; } fixDelete ( tree , x ) ; resetSentinel ( tree ) ; return ; } param tree param startIndex param endIndex export function deleteBetweenNodes < T extends Node > ( tree , startIndex , endIndex ) { let currentIndex = startIndex ; let nextIndex = currentIndex ; while ( nextIndex !== endIndex ) { currentIndex = nextIndex ; nextIndex = nextNode ( tree . nodes , currentIndex ) . index ; deleteNode ( tree , currentIndex ) ; } }