import { Color , RedBlackTree , Node } from "../pageModel" ; import { SENTINEL_INDEX , recomputeTreeMetadata , EMPTY_TREE_ROOT , nextNode , prevNode , } from "./tree" ; import { isContentNode } from "../contentTree/contentModel" ; import { leftRotate , rightRotate } from "./rotate" ; import { isStructureNode } from "../structureTree/structureModel" ; param page param x export function fixInsert < T extends Node > ( tree , x ) { recomputeTreeMetadata ( tree , x ) ; if ( x === tree . root ) { ( tree . nodes [ x ] as T ) . color = Color . Black ; return ; } while ( tree . nodes [ x ] . parent !== SENTINEL_INDEX && tree . nodes [ tree . nodes [ x ] . parent ] . parent !== SENTINEL_INDEX && x !== tree . root && tree . nodes [ tree . nodes [ x ] . parent ] . color === Color . Red ) { if ( tree . nodes [ x ] . parent === tree . nodes [ tree . nodes [ tree . nodes [ x ] . parent ] . parent ] . left ) { const y = tree . nodes [ tree . nodes [ tree . nodes [ x ] . parent ] . parent ] . right ; if ( tree . nodes [ y ] . color === Color . Red ) { tree . nodes [ tree . nodes [ x ] . parent ] . color = Color . Black ; ( tree . nodes [ y ] as T ) . color = Color . Black ; tree . nodes [ tree . nodes [ tree . nodes [ x ] . parent ] . parent ] . color = Color . Red ; x = tree . nodes [ tree . nodes [ x ] . parent ] . parent ; } else { if ( x === tree . nodes [ tree . nodes [ x ] . parent ] . right ) { x = tree . nodes [ x ] . parent ; leftRotate ( tree , x ) ; } tree . nodes [ tree . nodes [ x ] . parent ] . color = Color . Black ; tree . nodes [ tree . nodes [ tree . nodes [ x ] . parent ] . parent ] . color = Color . Red ; rightRotate ( tree , tree . nodes [ tree . nodes [ x ] . parent ] . parent ) ; } } else { const y = tree . nodes [ tree . nodes [ tree . nodes [ x ] . parent ] . parent ] . left ; if ( tree . nodes [ y ] . color === Color . Red ) { tree . nodes [ tree . nodes [ x ] . parent ] . color = Color . Black ; ( tree . nodes [ y ] as T ) . color = Color . Black ; tree . nodes [ tree . nodes [ tree . nodes [ x ] . parent ] . parent ] . color = Color . Red ; x = tree . nodes [ tree . nodes [ x ] . parent ] . parent ; } else { if ( tree . nodes [ x ] === tree . nodes [ tree . nodes [ tree . nodes [ x ] . parent ] . left ] ) { x = tree . nodes [ x ] . parent ; rightRotate ( tree , x ) ; } tree . nodes [ tree . nodes [ x ] . parent ] . color = Color . Black ; tree . nodes [ tree . nodes [ tree . nodes [ x ] . parent ] . parent ] . color = Color . Red ; leftRotate ( tree , tree . nodes [ tree . nodes [ x ] . parent ] . parent ) ; } } } tree . nodes [ tree . root ] . color = Color . Black ; } /**
 * Returns the value for the LHS check for binary search for the red-black tree
 * , for different types.
 */ function getLHSValue ( currentNode ) { if ( isContentNode ( currentNode ) ) { return currentNode . leftCharCount ; } else if ( isStructureNode ( currentNode ) ) { return currentNode . leftSubTreeLength + 1 ; } else { throw new TypeError ( "Passed an unknown node type for the red-black tree." ) ; } } /**
 * Returns the value for the RHS check for binary search for the red-black tree
 * , for different types.
 */ function getRHSValue ( currentNode ) { if ( isContentNode ( currentNode ) ) { return currentNode . leftCharCount + currentNode . length ; } else if ( isStructureNode ( currentNode ) ) { return currentNode . leftSubTreeLength + 1 ; } else { throw new TypeError ( "Passed an unknown node type for the red-black tree." ) ; } } function insertAfterNodeWithoutInserting < T extends Node > ( tree , newNode , indexToInsertAfter ) { if ( tree . nodes [ indexToInsertAfter ] . right === SENTINEL_INDEX ) { tree . nodes [ indexToInsertAfter ] . right = tree . nodes . length - 1 ; newNode . parent = indexToInsertAfter ; } else { const next = nextNode ( tree . nodes , indexToInsertAfter ) ; tree . nodes [ next . index ] . left = tree . nodes . length - 1 ; newNode . parent = next . index ; } } export function insertAfterNode < T extends Node > ( tree , newNode , indexToInsertAfter ) { tree . nodes . push ( newNode ) ; insertAfterNodeWithoutInserting ( tree , newNode , indexToInsertAfter ) ; } export function insertBeforeNode < T extends Node > ( tree , newNode , indexToInsertBefore ) { tree . nodes . push ( newNode ) ; if ( indexToInsertBefore === SENTINEL_INDEX ) { tree . root = tree . nodes . length - 1 ; newNode . color = Color . Black ; } else if ( tree . nodes [ indexToInsertBefore ] . left === SENTINEL_INDEX ) { tree . nodes [ indexToInsertBefore ] . left = tree . nodes . length - 1 ; newNode . parent = indexToInsertBefore ; } else { const prev = prevNode ( tree . nodes , indexToInsertBefore ) ; tree . nodes [ prev . index ] . right = tree . nodes . length - 1 ; newNode . parent = prev . index ; } } param tree param newNode param offset param nodeIndex param indexToInsertAfter export function insertNodeWithoutInserting < T extends Node > ( tree , newNode , offset , nodeIndex , indexToInsertAfter ? ) { if ( indexToInsertAfter ) { insertAfterNodeWithoutInserting ( tree , newNode , indexToInsertAfter ) ; return ; } let prevIndex = SENTINEL_INDEX ; let currentIndex = tree . root ; if ( currentIndex === EMPTY_TREE_ROOT ) { tree . root = 1 ; newNode . color = Color . Black ; return ; } let currentNode = tree . nodes [ currentIndex ] ; let nodeLocalOffset = 0 ; while ( currentIndex !== SENTINEL_INDEX ) { prevIndex = currentIndex ; if ( offset <= nodeLocalOffset + getLHSValue ( currentNode ) ) { currentIndex = currentNode . left ; if ( currentIndex === SENTINEL_INDEX ) { tree . nodes [ prevIndex ] . left = nodeIndex ; newNode . parent = prevIndex ; return ; } currentNode = tree . nodes [ currentIndex ] ; } else if ( offset >= nodeLocalOffset + getRHSValue ( currentNode ) ) { nodeLocalOffset += getRHSValue ( currentNode ) ; currentIndex = currentNode . right ; if ( currentIndex === SENTINEL_INDEX ) { tree . nodes [ prevIndex ] . right = nodeIndex ; newNode . parent = prevIndex ; return ; } currentNode = tree . nodes [ currentIndex ] ; } else { throw RangeError ( "Looking for the place to insert a node should never result in " + "looking in the middle of another node." ) ; } } throw RangeError ( "The currentIndex has reached a SENTINEL node before locating a suitable " + "insertion location." ) ; } param tree param newNode param offset param indexToInsertAfter export function insertNode < T extends Node > ( tree , newNode , offset , indexToInsertAfter ? ) { tree . nodes . push ( newNode ) ; insertNodeWithoutInserting ( tree , newNode , offset , tree . nodes . length - 1 , indexToInsertAfter ) ; }