@Test public void testRange() { 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 ); FastIterator fastIterator = tree.range(2, true, 15, false); Node<Integer, String> node = (Node<Integer, String>)fastIterator.next(null); assertEquals(5, (int)node.key); node = (Node<Integer, String>)fastIterator.next(node); assertEquals(10, (int)node.key); node = (Node<Integer, String>)fastIterator.next(node); assertNull(node); fastIterator = tree.range(2, true, 5, false); node = (Node<Integer, String>)fastIterator.next(null); assertNull(node); fastIterator = tree.range(5, false, 35, false); node = (Node<Integer, String>)fastIterator.next(null); assertEquals(10, (int)node.key); node = (Node<Integer, String>)fastIterator.next(node); assertEquals(15, (int)node.key); node = (Node<Integer, String>)fastIterator.next(node); assertEquals(20, (int)node.key); node = (Node<Integer, String>)fastIterator.next(node); assertEquals(25, (int)node.key); node = (Node<Integer, String>)fastIterator.next(node); assertNull(node); }
public FastIterator range(K lowerBound, boolean testLowerEqual, K upperBound, boolean testUpperEqual) { Node<K, V> lowerNearest = findNearestNode( lowerBound, testLowerEqual, Boundary.LOWER ); Node<K, V> upperNearest = findNearestNode( upperBound, testUpperEqual, Boundary.UPPER ); if ( lowerNearest == null || upperNearest == null ) { return FastIterator.EMPTY; } if ( lowerNearest.key.compareTo( upperNearest.key ) > 0 ) { upperNearest = lowerNearest; } return new RBTreeFastIterator( lowerNearest, upperNearest ); }
RBTree implements Serializable { public FastIterator range(K lowerBound, boolean testLowerEqual, K upperBound, boolean testUpperEqual) { Node<K, V> lowerNearest = findNearestNode( lowerBound, testLowerEqual, Boundary.LOWER ); Node<K, V> upperNearest = findNearestNode( upperBound, testUpperEqual, Boundary.UPPER ); if ( lowerNearest == null || upperNearest == null ) { return FastIterator.EMPTY; } if ( lowerNearest.key.compareTo( upperNearest.key ) > 0 ) { upperNearest = lowerNearest; } return new RBTreeFastIterator( lowerNearest, upperNearest ); } }
RBTree implements Serializable { public FastIterator range(K lowerBound, boolean testLowerEqual, K upperBound, boolean testUpperEqual) { Node<K, V> lowerNearest = findNearestNode( lowerBound, testLowerEqual, Boundary.LOWER ); Node<K, V> upperNearest = findNearestNode( upperBound, testUpperEqual, Boundary.UPPER ); if ( lowerNearest == null || upperNearest == null ) { return FastIterator.EMPTY; } if ( lowerNearest.key.compareTo( upperNearest.key ) > 0 ) { upperNearest = lowerNearest; } return new RBTreeFastIterator( lowerNearest, upperNearest ); } RBTree(); }
RBTree implements Serializable { public FastIterator range(K lowerBound, boolean testLowerEqual, K upperBound, boolean testUpperEqual) { Node<K, V> lowerNearest = findNearestNode( lowerBound, testLowerEqual, Boundary.LOWER ); Node<K, V> upperNearest = findNearestNode( upperBound, testUpperEqual, Boundary.UPPER ); if ( lowerNearest == null || upperNearest == null ) { return FastIterator.EMPTY; } if ( lowerNearest.key.compareTo( upperNearest.key ) > 0 ) { upperNearest = lowerNearest; } return new RBTreeFastIterator( lowerNearest, upperNearest ); } 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(); }
RBTree implements Serializable { public FastIterator range(K lowerBound, boolean testLowerEqual, K upperBound, boolean testUpperEqual) { Node<K, V> lowerNearest = findNearestNode( lowerBound, testLowerEqual, Boundary.LOWER ); Node<K, V> upperNearest = findNearestNode( upperBound, testUpperEqual, Boundary.UPPER ); if ( lowerNearest == null || upperNearest == null ) { return FastIterator.EMPTY; } if ( lowerNearest.key.compareTo( upperNearest.key ) > 0 ) { upperNearest = lowerNearest; } return new RBTreeFastIterator( lowerNearest, upperNearest ); } 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; }