import { expect } from "chai" ; import { UnionFindContext } from "../../numerics/UnionFind" ; import { Checker } from "../Checker" ; describe ( "UnionFind" , ( ) => { it ( "BinaryTree" , ( ) => { const ck = new Checker ( ) ; const noisy = Checker . noisy . unionFind ; for ( const numLeaf of [ 4 , 2 , 16 , 1 , 128 , 5 , 29 , 77 , 78 , 79 ] ) { if ( noisy ) console . log ( `tree size ${ numLeaf }` ) ; let context ; if ( numLeaf < 20 ) { context = new UnionFindContext ( ) ; for ( let i = 0 ; i < numLeaf ; i ++ ) { context . addLeaf ( ) ; } } else context = new UnionFindContext ( numLeaf ) ; ck . testExactNumber ( numLeaf , context . length ) ; ck . testFalse ( context . isValidIndex ( - 1 ) ) ; for ( const invalidIndex of [ - 1 , numLeaf , numLeaf + 100 ] ) { ck . testExactNumber ( invalidIndex , context . askParent ( invalidIndex ) , "askParent with invalid index is identity function." ) ; ck . testExactNumber ( invalidIndex , context . findRoot ( invalidIndex ) , "findRoot with invalid index is identity" ) ; } ck . testExactNumber ( numLeaf , context . countRoots ( ) , "Root count in singleton context" ) ; let numSubset = numLeaf ; for ( let blockSize = 1 ; blockSize < numLeaf ; blockSize *= 2 ) { if ( noisy ) console . log ( `blockSize ${ blockSize }` ) ; for ( let i0 = 0 ; i0 < numLeaf ; i0 += blockSize ) { for ( let i = 0 ; i < blockSize ; i ++ ) { context . mergeSubsets ( i0 , i0 + i ) ; if ( context . isValidIndex ( i0 ) && context . isValidIndex ( i0 + i ) ) ck . testExactNumber ( context . askParent ( i0 ) , context . askParent ( i0 + i ) , "verify merge happened" ) ; } if ( blockSize > 1 ) numSubset -- ; if ( numLeaf / blockSize === Math . floor ( numLeaf / blockSize ) ) ck . testExactNumber ( numSubset , context . countRoots ( ) , "Expected root count after merge at binary depth" ) ; } if ( numLeaf / blockSize === Math . floor ( numLeaf / blockSize ) ) ck . testExactNumber ( numLeaf / blockSize , context . countRoots ( ) , "Expected root count after merge at binary depth" ) ; } const numRoot0 = context . countRoots ( ) ; const numLongPath0 = context . countNonTrivialPaths ( ) ; for ( let i = 0 ; i < numLeaf ; i ++ ) context . findRoot ( i ) ; const numRoot1 = context . countRoots ( ) ; const numLongPath1 = context . countNonTrivialPaths ( ) ; ck . testExactNumber ( numRoot0 , numRoot1 , "Leaf queries do not change root count" ) ; ck . testLE ( numLongPath1 , numLongPath0 , "Leaf queries can reduce number of long paths" ) ; ck . testExactNumber ( 0 , numLongPath1 , "Leaf queries eliminate long paths" ) ; } expect ( ck . getNumErrors ( ) ) . equals ( 0 ) ; } ) ; } ) ;