@ SuppressWarnings ( "unchecked" ) private void sift ( TreeNode < K > x ) { Deque < TreeNode < K >> stack = new ArrayDeque < TreeNode < K > > ( ) ; stack . push ( x ) ; while ( ! stack . isEmpty ( ) ) { x = stack . peek ( ) ; TreeNode < K > xLeft = x . left ; TreeNode < K > xRight = x . right ; // if leaf or list has enough elements, skip if ( xLeft == null && xRight == null || x . cSize >= targetSize ( x . rank ) ) { stack . pop ( ) ; continue ; } // swap if needed if ( xLeft == null || xRight != null && ( ( comparator == null && ( ( Comparable < ? super K > ) xLeft . cKey ) . compareTo ( xRight . cKey ) > 0 ) || ( comparator != null && comparator . compare ( xLeft . cKey , xRight . cKey ) > 0 ) ) ) { x . left = xRight ; x . right = xLeft ; xLeft = x . left ; xRight = x . right ; } // grab non-empty list from left child xLeft . cTail . next = x . cHead ; x . cHead = xLeft . cHead ; if ( x . cTail == null ) { x . cTail = xLeft . cTail ; } x . cSize += xLeft . cSize ; // set new corrupted key x . cKey = xLeft . cKey ; // clear left child list xLeft . cKey = null ; xLeft . cHead = null ; xLeft . cTail = null ; xLeft . cSize = 0 ; // recursively to left child if not a leaf if ( xLeft . left != null || xLeft . right != null ) { stack . push ( xLeft ) ; } else { x . left = null ; } } }
Sift elements from children nodes until the current node has enough elements in its list .