RBTree implements Serializable { public Node<K, V> findNearestNode(K key, boolean allowEqual, Boundary boundary) { Node<K, V> nearest = null; Node<K, V> n = root; while ( n != null ) { int compResult = key.compareTo( n.key ); if ( allowEqual && compResult == 0 ) { return n; } boolean accepted = acceptNode(compResult, boundary); if ( acceptNode( compResult, boundary ) && ( nearest == null || acceptNode( n.key.compareTo( nearest.key ), boundary ) ) ) { nearest = n; } if ( compResult == 0 ) { n = boundary == Boundary.LOWER ? n.right : n.left; } else { n = accepted ^ boundary == Boundary.LOWER ? n.right : n.left; } } return nearest; } RBTree(); void verifyProperties(); boolean isEmpty(); Node<K, V> first(); Node<K, V> last(); FastIterator fastIterator(); FastIterator range(K lowerBound,
                              boolean testLowerEqual,
                              K upperBound,
                              boolean testUpperEqual); Node<K, V> findNearestNode(K key, boolean allowEqual, Boundary boundary); V lookup(K key); void insert(K key,
                       V value); void delete(K key); void print(); static final boolean VERIFY_RBTREE; public Node<K, V> root; }
@Test public void testFindNearestNode() { RBTree<Integer, String> tree = new RBTree<Integer, String>(); tree.insert( 10, "" + 10 ); tree.insert( 20, "" + 20 ); tree.insert( 25, "" + 25 ); tree.insert( 15, "" + 15 ); tree.insert( 5, "" + 5 ); assertEquals(5, (int)tree.findNearestNode(2, false, RBTree.Boundary.LOWER).key); assertEquals(null, tree.findNearestNode(2, false, RBTree.Boundary.UPPER)); assertEquals(5, (int)tree.findNearestNode(2, true, RBTree.Boundary.LOWER).key); assertEquals(null, tree.findNearestNode(2, true, RBTree.Boundary.UPPER)); assertEquals(10, (int)tree.findNearestNode(5, false, RBTree.Boundary.LOWER).key); assertEquals(null, tree.findNearestNode(5, false, RBTree.Boundary.UPPER)); assertEquals(5, (int)tree.findNearestNode(5, true, RBTree.Boundary.LOWER).key); assertEquals(5, (int)tree.findNearestNode(5, true, RBTree.Boundary.UPPER).key); assertEquals(15, (int)tree.findNearestNode(12, false, RBTree.Boundary.LOWER).key); assertEquals(10, (int)tree.findNearestNode(12, false, RBTree.Boundary.UPPER).key); assertEquals(20, (int)tree.findNearestNode(15, false, RBTree.Boundary.LOWER).key); assertEquals(10, (int)tree.findNearestNode(15, false, RBTree.Boundary.UPPER).key); assertEquals(15, (int)tree.findNearestNode(15, true, RBTree.Boundary.UPPER).key); assertEquals(15, (int)tree.findNearestNode(15, true, RBTree.Boundary.LOWER).key); assertEquals(20, (int)tree.findNearestNode(25, false, RBTree.Boundary.UPPER).key); assertEquals(null, tree.findNearestNode(25, false, RBTree.Boundary.LOWER)); assertEquals(25, (int)tree.findNearestNode(25, true, RBTree.Boundary.LOWER).key); assertEquals(25, (int)tree.findNearestNode(25, true, RBTree.Boundary.UPPER).key); assertEquals(25, (int)tree.findNearestNode(27, false, RBTree.Boundary.UPPER).key); assertEquals(null, tree.findNearestNode(27, false, RBTree.Boundary.LOWER)); assertEquals(25, (int)tree.findNearestNode(27, true, RBTree.Boundary.UPPER).key); assertEquals(null, tree.findNearestNode(27, true, RBTree.Boundary.LOWER)); }