protected void convertToPointerRepresentation ( ArrayDBIDs ids , DoubleLongHeap heap , WritableDBIDDataStore pi , WritableDoubleDataStore lambda ) { final Logging LOG = getLogger ( ) ; // Initialize parent array: for ( DBIDArrayIter iter = ids . iter ( ) ; iter . valid ( ) ; iter . advance ( ) ) { pi . put ( iter , iter ) ; // Initialize } DBIDVar p = DBIDUtil . newVar ( ) , q = DBIDUtil . newVar ( ) , n = DBIDUtil . newVar ( ) ; FiniteProgress pprog = LOG . isVerbose ( ) ? new FiniteProgress ( "Converting MST to pointer representation" , heap . size ( ) , LOG ) : null ; while ( ! heap . isEmpty ( ) ) { final double dist = heap . peekKey ( ) ; final long pair = heap . peekValue ( ) ; final int i = ( int ) ( pair >>> 31 ) , j = ( int ) ( pair & 0x7FFFFFFF L ) ; ids . assignVar ( i , p ) ; // Follow p to its parent. while ( ! DBIDUtil . equal ( p , pi . assignVar ( p , n ) ) ) { p . set ( n ) ; } // Follow q to its parent. ids . assignVar ( j , q ) ; while ( ! DBIDUtil . equal ( q , pi . assignVar ( q , n ) ) ) { q . set ( n ) ; } // By definition of the pointer representation, the largest element in // each cluster is the cluster lead. // The extraction methods currently rely on this! int c = DBIDUtil . compare ( p , q ) ; if ( c < 0 ) { // p joins q: pi . put ( p , q ) ; lambda . put ( p , dist ) ; } else { assert ( c != 0 ) : "This should never happen!" ; // q joins p: pi . put ( q , p ) ; lambda . put ( q , dist ) ; } heap . poll ( ) ; LOG . incrementProcessed ( pprog ) ; } LOG . ensureCompleted ( pprog ) ; // Hack to ensure a valid pointer representation: // If distances are tied, the heap may return edges such that the n-way join // does not fulfill the property that the last element has the largest id. for ( DBIDArrayIter iter = ids . iter ( ) ; iter . valid ( ) ; iter . advance ( ) ) { double d = lambda . doubleValue ( iter ) ; // Parent: pi . assignVar ( iter , p ) ; q . set ( p ) ; // Follow parent while tied. while ( d >= lambda . doubleValue ( q ) && ! DBIDUtil . equal ( q , pi . assignVar ( q , n ) ) ) { q . set ( n ) ; } if ( ! DBIDUtil . equal ( p , q ) ) { if ( LOG . isDebuggingFinest ( ) ) { LOG . finest ( "Correcting parent: " + p + " -> " + q ) ; } pi . put ( iter , q ) ; } } }
Convert spanning tree to a pointer representation .