private static < T extends RingPosition < T > > List < Range < T > > deoverlap ( List < Range < T > > ranges ) { if ( ranges . isEmpty ( ) ) return ranges ; List < Range < T > > output = new ArrayList < Range < T > > ( ) ; Iterator < Range < T > > iter = ranges . iterator ( ) ; Range < T > current = iter . next ( ) ; @ SuppressWarnings ( "unchecked" ) T min = ( T ) current . partitioner . minValue ( current . left . getClass ( ) ) ; while ( iter . hasNext ( ) ) { // If current goes to the end of the ring, we're done if ( current . right . equals ( min ) ) { // If one range is the full range, we return only that if ( current . left . equals ( min ) ) return Collections . < Range < T > > singletonList ( current ) ; output . add ( new Range < T > ( current . left , min ) ) ; return output ; } Range < T > next = iter . next ( ) ; // if next left is equal to current right, we do not intersect per se, but replacing (A, B] and (B, C] by (A, C] is // legit, and since this avoid special casing and will result in more "optimal" ranges, we do the transformation if ( next . left . compareTo ( current . right ) <= 0 ) { // We do overlap // (we've handled current.right.equals(min) already) if ( next . right . equals ( min ) || current . right . compareTo ( next . right ) < 0 ) current = new Range < T > ( current . left , next . right ) ; } else { output . add ( current ) ; current = next ; } } output . add ( current ) ; return output ; }
Given a list of unwrapped ranges sorted by left position return an equivalent list of ranges but with no overlapping ranges .