private TimeoutExtImpl removeNode ( int index ) { // INV: assertExpr(index > 0); // INV: assertExpr(index <= size); TimeoutExtImpl res = queue [ index ] ; // INV: assertExpr(res != null); // INV: assertExpr(res.index == index); if ( index == size ) { -- size ; queue [ index ] = null ; return res ; } swap ( index , size ) ; // Exchange removed node with last leaf node -- size ; // INV: assertExpr(res.index == size + 1); queue [ res . index ] = null ; if ( normalizeUp ( index ) ) return res ; // Node moved up, so it shouldn't move down long t = queue [ index ] . time ; int c = index << 1 ; while ( c <= size ) { // INV: assertExpr(q[index].time == t); TimeoutExtImpl l = queue [ c ] ; // INV: assertExpr(l != null); // INV: assertExpr(l.index == c); if ( c + 1 <= size ) { // two children, swap with smallest TimeoutExtImpl r = queue [ c + 1 ] ; // INV: assertExpr(r != null); // INV: assertExpr(r.index == c+1); if ( l . time <= r . time ) { if ( t <= l . time ) break ; // done swap ( index , c ) ; index = c ; } else { if ( t <= r . time ) break ; // done swap ( index , c + 1 ) ; index = c + 1 ; } } else { // one child if ( t <= l . time ) break ; // done swap ( index , c ) ; index = c ; } c = index << 1 ; } return res ; }
Remove a node from the tree and normalize .