import { calculateCharCount , calculateLineFeedCount , resetSentinelContent , } from "../contentTree/tree" ; import { Node , RedBlackTree } from "../pageModel" ; import { isContentRedBlackTree , isContentNode , } from "../contentTree/contentModel" ; import { isStructureRedBlackTree , isStructureNode , } from "../structureTree/structureModel" ; import { calculateLengthCount , resetSentinelStructure , } from "../structureTree/tree" ; /**
 * The index of the sentinel node in the `nodes` array of a page/piece table.
 */ export const SENTINEL_INDEX = 0 ; /**
 * The root of the tree when there are no nodes in the tree.
 */ export const EMPTY_TREE_ROOT = - 1 ; /**
 * Contains a node and its index in a red-black tree.
 */ export interface NodePosition < T extends Node > { node : T ; index : number ; } param nodes param x export function treeMinimum < T extends Node > ( nodes , x ) { while ( nodes [ x ] . left !== SENTINEL_INDEX ) { x = nodes [ x ] . left ; } return { index : x , node : nodes [ x ] } ; } param nodes param x export function treeMaximum < T extends Node > ( nodes , x ) { while ( nodes [ x ] . right !== SENTINEL_INDEX ) { x = nodes [ x ] . right ; } return { index : x , node : nodes [ x ] } ; } param nodes param currentNode export function nextNode < T extends Node > ( nodes , currentNode ) { if ( nodes [ currentNode ] . right !== SENTINEL_INDEX ) { return treeMinimum < T > ( nodes , nodes [ currentNode ] . right ) ; } while ( nodes [ currentNode ] . parent !== SENTINEL_INDEX ) { if ( nodes [ nodes [ currentNode ] . parent ] . left === currentNode ) { break ; } currentNode = nodes [ currentNode ] . parent ; } if ( nodes [ currentNode ] . parent === SENTINEL_INDEX ) { return { index : SENTINEL_INDEX , node : nodes [ 0 ] } ; } else { return { index : nodes [ currentNode ] . parent , node : nodes [ nodes [ currentNode ] . parent ] , } ; } } param nodes param currentNode export function prevNode < T extends Node > ( nodes , currentNode ) { if ( nodes [ currentNode ] . left !== SENTINEL_INDEX ) { return treeMaximum ( nodes , nodes [ currentNode ] . left ) ; } while ( nodes [ currentNode ] . parent !== SENTINEL_INDEX ) { if ( nodes [ nodes [ currentNode ] . parent ] . right === currentNode ) { break ; } currentNode = nodes [ currentNode ] . parent ; } if ( nodes [ currentNode ] . parent === SENTINEL_INDEX ) { return { index : SENTINEL_INDEX , node : nodes [ 0 ] } ; } else { return { index : nodes [ currentNode ] . parent , node : nodes [ nodes [ currentNode ] . parent ] , } ; } } param tree param index export function recomputeTreeMetadata < T extends Node > ( tree , x ) { let lengthDelta ; let lineFeedDelta ; if ( x === tree . root ) { return ; } while ( x !== tree . root && x === tree . nodes [ tree . nodes [ x ] . parent ] . right && x !== SENTINEL_INDEX ) { x = tree . nodes [ x ] . parent ; } if ( x === tree . root ) { return ; } x = tree . nodes [ x ] . parent ; if ( isContentRedBlackTree ( tree ) ) { lengthDelta = calculateCharCount ( tree , tree . nodes [ x ] . left ) - tree . nodes [ x ] . leftCharCount ; lineFeedDelta = calculateLineFeedCount ( tree , tree . nodes [ x ] . left ) - tree . nodes [ x ] . leftLineFeedCount ; tree . nodes [ x ] . leftCharCount += lengthDelta ; tree . nodes [ x ] . leftLineFeedCount += lineFeedDelta ; } else if ( isStructureRedBlackTree ( tree ) ) { lengthDelta = calculateLengthCount ( tree , tree . nodes [ x ] . left ) - tree . nodes [ x ] . leftSubTreeLength ; tree . nodes [ x ] . leftSubTreeLength += lengthDelta ; } if ( lengthDelta !== undefined && ! ( lengthDelta !== 0 || lineFeedDelta !== 0 ) ) { return ; } while ( x !== tree . root ) { if ( tree . nodes [ tree . nodes [ x ] . parent ] . left === x ) { if ( isContentRedBlackTree ( tree ) ) { tree . nodes [ tree . nodes [ x ] . parent ] . leftCharCount += lengthDelta ! ; tree . nodes [ tree . nodes [ x ] . parent ] . leftLineFeedCount += lineFeedDelta ! ; } else if ( isStructureRedBlackTree ( tree ) ) { tree . nodes [ tree . nodes [ x ] . parent ] . leftSubTreeLength += lengthDelta ! ; } } x = tree . nodes [ x ] . parent ; } } param tree export function resetSentinel < T extends Node > ( tree ) { if ( isContentRedBlackTree ( tree ) ) { resetSentinelContent ( tree ) ; } else if ( isStructureRedBlackTree ( tree ) ) { resetSentinelStructure ( tree ) ; } } param startNode export function * inorderTreeTraversal < T extends Node > ( tree , startNode ? ) { let value ; if ( startNode ) { if ( startNode >= tree . nodes . length ) { throw new RangeError ( `The given start node of ${ startNode } is too large for this tree.` ) ; } value = { index : startNode , node : tree . nodes [ startNode ] } ; } else { value = treeMinimum ( tree . nodes , tree . root ) ; } let offset = 0 ; while ( value . index !== SENTINEL_INDEX ) { yield { ... value , offset } ; if ( isContentNode ( value . node ) || isStructureNode ( value . node ) ) { offset += value . node . length ; } value = nextNode ( tree . nodes , value . index ) ; } }