static < T extends Comparable < ? super T > > void rangeQueryLeft ( TreeNode < T > node , Interval < T > query , Set < Interval < T > > result ) { while ( node != null ) { if ( query . contains ( node . midpoint ) ) { result . addAll ( node . increasing ) ; if ( node . right != null ) { for ( Interval < T > next : node . right ) result . ( next ) ; } node = node . left ; } else { for ( Interval < T > next : node . decreasing ) { if ( next . isLeftOf ( query ) ) break ; result . add ( next ) ; } node = node . right ; } } }
A helper method for the range search used in the interval intersection query in the tree . This corresponds to the left branch of the range search once we find a node whose midpoint is contained in the query interval . All intervals in the left subtree of that node are guaranteed to intersect with the query if they have an endpoint greater or equal than the start of the query interval . Basically this means that every time we branch to the left in the binary search we need to add the whole right subtree to the result set .