+ * null if there is no node with a higher key than the given key. + */ + public K findGreater( K key ) + { + if ( size == 0 ) + { + return null; + } + + int current = size >> 1; + int end = size; + int start = 0; + int previousCurrent = -1; + + while ( previousCurrent != current ) + { + int res = comparator.compare( array[current], key ) ; + + if ( res == 0 ) + { + if ( current == size - 1 ) + { + return null; + } + else + { + position = current + 1; + return array[position]; + } + } + else if ( res < 0 ) + { + start = current; + previousCurrent = current; + current = (start + end ) >> 1; + } + else + { + end = current; + previousCurrent = current; + current = (start + end ) >> 1 ; + } + } + + // We haven't found the element, so take the next one + if ( current == size - 1 ) + { + return null; + } + else + { + position = current + 1; + return array[position]; + } + } + + + /** + * Finds a key higher than the given key. + * + * @param key the key + * @return the key chich is greater than the given key ,
+ * null if there is no higher key than the given key. + */ + public K findGreaterOrEqual( K key ) + { + if ( size == 0 ) + { + return null; + } + + int current = size >> 1; + int end = size; + int start = 0; + int previousCurrent = -1; + + while ( previousCurrent != current ) + { + int res = comparator.compare( array[current], key ) ; + + if ( res == 0 ) + { + position = current; + return array[current]; + } + else if ( res < 0 ) + { + start = current; + previousCurrent = current; + current = (current + end ) >> 1; + } + else + { + end = current; + previousCurrent = current; + current = (current + start ) >> 1 ; + } + } + + // We haven't found the element, so take the next one + if ( current == size - 1 ) + { + return null; + } + else + { + position = current + 1; + return array[position]; + } + } + + + /** + * Finds a key which is lower than the given key. + * + * @param key the key + * @return the key lower than the given key ,
+ * null if there is no node with a lower key than the given key. + */ + public K findLess( K key ) + { + if ( size == 0 ) + { + return null; + } + + int current = size >> 1; + int end = size; + int start = 0; + int previousCurrent = -1; + + while ( previousCurrent != current ) + { + int res = comparator.compare( array[current], key ) ; + + if ( res == 0 ) + { + if ( current == 0 ) + { + return null; + } + else + { + position = current - 1; + return array[position]; + } + } + else if ( res < 0 ) + { + start = current; + previousCurrent = current; + current = (current + end ) >> 1; + } + else + { + end = current; + previousCurrent = current; + current = (current + start ) >> 1 ; + } + } + + // We haven't found the element, so take the previous one + if ( current == 0 ) + { + return null; + } + else + { + position = current; + return array[current]; + } + } + + + /** + * Finds a key chich is lower than the given key. + * + * @param key the key + * @return the key which is lower than the given key ,