Home | History | Annotate | Download | only in collect 
      1 /*
      2  * Copyright (C) 2011 The Guava Authors
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
      5  * in compliance with the License. You may obtain a copy of the License at
      6  *
      7  * http://www.apache.org/licenses/LICENSE-2.0
      8  *
      9  * Unless required by applicable law or agreed to in writing, software distributed under the
     10  * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
     11  * express or implied. See the License for the specific language governing permissions and
     12  * limitations under the License.
     13  */
     14 
     15 package com.google.common.collect;
     16 
     17 import static com.google.common.collect.BoundType.CLOSED;
     18 import static com.google.common.collect.BoundType.OPEN;
     19 import static com.google.common.collect.BstSide.LEFT;
     20 import static com.google.common.collect.BstSide.RIGHT;
     21 import static com.google.common.collect.BstTesting.assertInOrderTraversalIs;
     22 import static com.google.common.collect.BstTesting.balancePolicy;
     23 import static com.google.common.collect.BstTesting.countAggregate;
     24 import static com.google.common.collect.BstTesting.defaultNullPointerTester;
     25 import static com.google.common.collect.BstTesting.nodeFactory;
     26 import static com.google.common.collect.BstTesting.pathFactory;
     27 import static com.google.common.collect.BstTesting.pathToList;
     28 import static org.junit.contrib.truth.Truth.ASSERT;
     29 
     30 import com.google.common.annotations.GwtCompatible;
     31 import com.google.common.annotations.GwtIncompatible;
     32 import com.google.common.collect.BstTesting.SimpleNode;
     33 
     34 import junit.framework.TestCase;
     35 
     36 import java.util.SortedSet;
     37 
     38 /**
     39  * Tests for {@code BSTRangeOps}.
     40  *
     41  * @author Louis Wasserman
     42  */
     43 @GwtCompatible(emulated = true)
     44 public class BstRangeOpsTest extends TestCase {
     45   private static final SortedSet<Character> MODEL =
     46       ImmutableSortedSet.of('a', 'b', 'c', 'd', 'e', 'f', 'g');
     47   private static final SimpleNode ROOT;
     48 
     49   static {
     50     SimpleNode a = new SimpleNode('a', null, null);
     51     SimpleNode c = new SimpleNode('c', null, null);
     52     SimpleNode b = new SimpleNode('b', a, c);
     53     SimpleNode e = new SimpleNode('e', null, null);
     54     SimpleNode g = new SimpleNode('g', null, null);
     55     SimpleNode f = new SimpleNode('f', e, g);
     56     SimpleNode d = new SimpleNode('d', b, f);
     57     ROOT = d;
     58   }
     59 
     60   public void testCountInRangeLowerBound() {
     61     for (char c : "abcdefg".toCharArray()) {
     62       for (BoundType type : BoundType.values()) {
     63         long count = BstRangeOps.totalInRange(
     64             countAggregate, GeneralRange.downTo(Ordering.natural(), c, type), ROOT);
     65         char d = c;
     66         if (type == BoundType.OPEN) {
     67           d++;
     68         }
     69         assertEquals(MODEL.tailSet(d).size(), count);
     70       }
     71     }
     72   }
     73 
     74   public void testCountInRangeUpperBound() {
     75     for (char c : "abcdefg".toCharArray()) {
     76       for (BoundType type : BoundType.values()) {
     77         long count = BstRangeOps.totalInRange(
     78             countAggregate, GeneralRange.upTo(Ordering.natural(), c, type), ROOT);
     79         char d = c;
     80         if (type == BoundType.CLOSED) {
     81           d++;
     82         }
     83         assertEquals(MODEL.headSet(d).size(), count);
     84       }
     85     }
     86   }
     87 
     88   public void testCountInRangeBothBounds() {
     89     String chars = "abcdefg";
     90     for (int i = 0; i < chars.length(); i++) {
     91       for (BoundType lb : BoundType.values()) {
     92         for (int j = i; j < chars.length(); j++) {
     93           for (BoundType ub : BoundType.values()) {
     94             if (i == j && lb == BoundType.OPEN && ub == BoundType.OPEN) {
     95               continue;
     96             }
     97             long count = BstRangeOps.totalInRange(countAggregate, GeneralRange.range(
     98                 Ordering.natural(), chars.charAt(i), lb, chars.charAt(j), ub), ROOT);
     99             char lo = chars.charAt(i);
    100             if (lb == BoundType.OPEN) {
    101               lo++;
    102             }
    103             char hi = chars.charAt(j);
    104             if (ub == BoundType.CLOSED) {
    105               hi++;
    106             }
    107             if (lo > hi) {
    108               lo = hi;
    109             }
    110             assertEquals(MODEL.subSet(lo, hi).size(), count);
    111           }
    112         }
    113       }
    114     }
    115   }
    116 
    117   public void testCountInRangeAll() {
    118     assertEquals(MODEL.size(), BstRangeOps.totalInRange(
    119         countAggregate, GeneralRange.<Character>all(Ordering.natural()), ROOT));
    120   }
    121 
    122   public void testCountInRangeEmpty() {
    123     SimpleNode empty = null;
    124     GeneralRange<Character> range = GeneralRange.all(Ordering.natural());
    125     assertEquals(0, BstRangeOps.totalInRange(countAggregate, range, empty));
    126   }
    127 
    128   public void testClearRangeLowerBound() {
    129     //     d
    130     //    / \
    131     //   b   f
    132     //  /   / \
    133     //  a   e g
    134     SimpleNode a = new SimpleNode('a', null, null);
    135     SimpleNode b = new SimpleNode('b', a, null);
    136     SimpleNode e = new SimpleNode('e', null, null);
    137     SimpleNode g = new SimpleNode('g', null, null);
    138     SimpleNode f = new SimpleNode('f', e, g);
    139     SimpleNode d = new SimpleNode('d', b, f);
    140 
    141     assertInOrderTraversalIs(d, "abdefg");
    142     GeneralRange<Character> range1 = GeneralRange.downTo(Ordering.natural(), 'f', CLOSED);
    143     testTraversalAfterClearingRangeIs(d, range1, "abde");
    144 
    145     GeneralRange<Character> range2 = GeneralRange.downTo(Ordering.natural(), 'f', OPEN);
    146     testTraversalAfterClearingRangeIs(d, range2, "abdef");
    147 
    148     GeneralRange<Character> range3 = GeneralRange.downTo(Ordering.natural(), 'a', CLOSED);
    149     testTraversalAfterClearingRangeIs(d, range3, "");
    150 
    151     GeneralRange<Character> range4 = GeneralRange.downTo(Ordering.natural(), 'a', OPEN);
    152     testTraversalAfterClearingRangeIs(d, range4, "a");
    153 
    154     GeneralRange<Character> range5 = GeneralRange.downTo(Ordering.natural(), 'c', OPEN);
    155     testTraversalAfterClearingRangeIs(d, range5, "ab");
    156 
    157     GeneralRange<Character> range6 = GeneralRange.downTo(Ordering.natural(), 'c', CLOSED);
    158     testTraversalAfterClearingRangeIs(d, range6, "ab");
    159   }
    160 
    161   public void testClearRangeUpperBound() {
    162     //     d
    163     //    / \
    164     //   b   f
    165     //  /   / \
    166     //  a   e g
    167     SimpleNode a = new SimpleNode('a', null, null);
    168     SimpleNode b = new SimpleNode('b', a, null);
    169     SimpleNode e = new SimpleNode('e', null, null);
    170     SimpleNode g = new SimpleNode('g', null, null);
    171     SimpleNode f = new SimpleNode('f', e, g);
    172     SimpleNode d = new SimpleNode('d', b, f);
    173 
    174     assertInOrderTraversalIs(d, "abdefg");
    175     GeneralRange<Character> range1 = GeneralRange.upTo(Ordering.natural(), 'f', CLOSED);
    176     testTraversalAfterClearingRangeIs(d, range1, "g");
    177 
    178     GeneralRange<Character> range2 = GeneralRange.upTo(Ordering.natural(), 'f', OPEN);
    179     testTraversalAfterClearingRangeIs(d, range2, "fg");
    180 
    181     GeneralRange<Character> range3 = GeneralRange.upTo(Ordering.natural(), 'a', CLOSED);
    182     testTraversalAfterClearingRangeIs(d, range3, "bdefg");
    183 
    184     GeneralRange<Character> range4 = GeneralRange.upTo(Ordering.natural(), 'a', OPEN);
    185     testTraversalAfterClearingRangeIs(d, range4, "abdefg");
    186 
    187     GeneralRange<Character> range5 = GeneralRange.upTo(Ordering.natural(), 'c', OPEN);
    188     testTraversalAfterClearingRangeIs(d, range5, "defg");
    189 
    190     GeneralRange<Character> range6 = GeneralRange.upTo(Ordering.natural(), 'c', CLOSED);
    191     testTraversalAfterClearingRangeIs(d, range6, "defg");
    192   }
    193 
    194   public void testClearRangeDoublyBounded() {
    195     //     d
    196     //    / \
    197     //   b   f
    198     //  / \ / \
    199     //  a c e g
    200     SimpleNode a = new SimpleNode('a', null, null);
    201     SimpleNode c = new SimpleNode('c', null, null);
    202     SimpleNode b = new SimpleNode('b', a, c);
    203     SimpleNode e = new SimpleNode('e', null, null);
    204     SimpleNode g = new SimpleNode('g', null, null);
    205     SimpleNode f = new SimpleNode('f', e, g);
    206     SimpleNode d = new SimpleNode('d', b, f);
    207 
    208     GeneralRange<Character> range1 =
    209         GeneralRange.range(Ordering.natural(), 'c', OPEN, 'f', CLOSED);
    210     testTraversalAfterClearingRangeIs(d, range1, "abcg");
    211 
    212     GeneralRange<Character> range2 =
    213         GeneralRange.range(Ordering.natural(), 'a', CLOSED, 'h', OPEN);
    214     testTraversalAfterClearingRangeIs(d, range2, "");
    215 
    216   }
    217 
    218   public void testClearRangeAll() {
    219     //     d
    220     //    / \
    221     //   b   f
    222     //  / \ / \
    223     //  a c e g
    224     SimpleNode a = new SimpleNode('a', null, null);
    225     SimpleNode c = new SimpleNode('c', null, null);
    226     SimpleNode b = new SimpleNode('b', a, c);
    227     SimpleNode e = new SimpleNode('e', null, null);
    228     SimpleNode g = new SimpleNode('g', null, null);
    229     SimpleNode f = new SimpleNode('f', e, g);
    230     SimpleNode d = new SimpleNode('d', b, f);
    231 
    232     testTraversalAfterClearingRangeIs(d, GeneralRange.<Character>all(Ordering.natural()), "");
    233   }
    234 
    235   private void testTraversalAfterClearingRangeIs(
    236       SimpleNode d, GeneralRange<Character> range, String expected) {
    237     assertInOrderTraversalIs(
    238         BstRangeOps.minusRange(range, balancePolicy, nodeFactory, d), expected);
    239   }
    240 
    241   public void testLeftmostPathAll() {
    242     //     d
    243     //    / \
    244     //   b   f
    245     //    \ / \
    246     //    c e g
    247     SimpleNode c = new SimpleNode('c', null, null);
    248     SimpleNode b = new SimpleNode('b', null, c);
    249     SimpleNode e = new SimpleNode('e', null, null);
    250     SimpleNode g = new SimpleNode('g', null, null);
    251     SimpleNode f = new SimpleNode('f', e, g);
    252     SimpleNode d = new SimpleNode('d', b, f);
    253 
    254     GeneralRange<Character> range1 = GeneralRange.all(Ordering.natural());
    255     ASSERT.that(pathToList(BstRangeOps.furthestPath(range1, LEFT, pathFactory, d)))
    256         .hasContentsInOrder(b, d);
    257 
    258     assertNull(BstRangeOps.furthestPath(range1, LEFT, pathFactory, null));
    259   }
    260 
    261   public void testLeftmostPathDownTo() {
    262     //     d
    263     //    / \
    264     //   b   f
    265     //    \ / \
    266     //    c e g
    267     SimpleNode c = new SimpleNode('c', null, null);
    268     SimpleNode b = new SimpleNode('b', null, c);
    269     SimpleNode e = new SimpleNode('e', null, null);
    270     SimpleNode g = new SimpleNode('g', null, null);
    271     SimpleNode f = new SimpleNode('f', e, g);
    272     SimpleNode d = new SimpleNode('d', b, f);
    273 
    274     GeneralRange<Character> range1 = GeneralRange.downTo(Ordering.natural(), 'd', OPEN);
    275     ASSERT.that(pathToList(BstRangeOps.furthestPath(range1, LEFT, pathFactory, d)))
    276         .hasContentsInOrder(e, f, d);
    277 
    278     GeneralRange<Character> range2 = GeneralRange.downTo(Ordering.natural(), 'd', CLOSED);
    279     ASSERT.that(pathToList(BstRangeOps.furthestPath(range2, LEFT, pathFactory, d)))
    280         .hasContentsInOrder(d);
    281 
    282     GeneralRange<Character> range3 = GeneralRange.downTo(Ordering.natural(), 'a', CLOSED);
    283     ASSERT.that(pathToList(BstRangeOps.furthestPath(range3, LEFT, pathFactory, d)))
    284         .hasContentsInOrder(b, d);
    285 
    286     GeneralRange<Character> range4 = GeneralRange.downTo(Ordering.natural(), 'h', CLOSED);
    287     assertNull(BstRangeOps.furthestPath(range4, LEFT, pathFactory, d));
    288   }
    289 
    290   public void testLeftmostPathUpTo() {
    291     //     d
    292     //    / \
    293     //   b   f
    294     //    \ / \
    295     //    c e g
    296     SimpleNode c = new SimpleNode('c', null, null);
    297     SimpleNode b = new SimpleNode('b', null, c);
    298     SimpleNode e = new SimpleNode('e', null, null);
    299     SimpleNode g = new SimpleNode('g', null, null);
    300     SimpleNode f = new SimpleNode('f', e, g);
    301     SimpleNode d = new SimpleNode('d', b, f);
    302 
    303     GeneralRange<Character> range1 = GeneralRange.upTo(Ordering.natural(), 'd', OPEN);
    304     ASSERT.that(pathToList(BstRangeOps.furthestPath(range1, LEFT, pathFactory, d)))
    305         .hasContentsInOrder(b, d);
    306 
    307     GeneralRange<Character> range2 = GeneralRange.upTo(Ordering.natural(), 'd', CLOSED);
    308     ASSERT.that(pathToList(BstRangeOps.furthestPath(range2, LEFT, pathFactory, d)))
    309         .hasContentsInOrder(b, d);
    310 
    311     GeneralRange<Character> range3 = GeneralRange.upTo(Ordering.natural(), 'a', CLOSED);
    312     assertNull(BstRangeOps.furthestPath(range3, LEFT, pathFactory, d));
    313   }
    314 
    315   public void testRightmostPathAll() {
    316     //     d
    317     //    / \
    318     //   b   f
    319     //    \ / \
    320     //    c e g
    321     SimpleNode c = new SimpleNode('c', null, null);
    322     SimpleNode b = new SimpleNode('b', null, c);
    323     SimpleNode e = new SimpleNode('e', null, null);
    324     SimpleNode g = new SimpleNode('g', null, null);
    325     SimpleNode f = new SimpleNode('f', e, g);
    326     SimpleNode d = new SimpleNode('d', b, f);
    327 
    328     GeneralRange<Character> range1 = GeneralRange.all(Ordering.natural());
    329     ASSERT.that(pathToList(BstRangeOps.furthestPath(range1, RIGHT, pathFactory, d)))
    330         .hasContentsInOrder(g, f, d);
    331 
    332     assertNull(BstRangeOps.furthestPath(range1, RIGHT, pathFactory, null));
    333   }
    334 
    335   public void testRightmostPathDownTo() {
    336     //     d
    337     //    / \
    338     //   b   f
    339     //    \ / \
    340     //    c e g
    341     SimpleNode c = new SimpleNode('c', null, null);
    342     SimpleNode b = new SimpleNode('b', null, c);
    343     SimpleNode e = new SimpleNode('e', null, null);
    344     SimpleNode g = new SimpleNode('g', null, null);
    345     SimpleNode f = new SimpleNode('f', e, g);
    346     SimpleNode d = new SimpleNode('d', b, f);
    347 
    348     GeneralRange<Character> range1 = GeneralRange.downTo(Ordering.natural(), 'd', OPEN);
    349     ASSERT.that(pathToList(BstRangeOps.furthestPath(range1, RIGHT, pathFactory, d)))
    350         .hasContentsInOrder(g, f, d);
    351 
    352     GeneralRange<Character> range2 = GeneralRange.downTo(Ordering.natural(), 'd', CLOSED);
    353     ASSERT.that(pathToList(BstRangeOps.furthestPath(range2, RIGHT, pathFactory, d)))
    354         .hasContentsInOrder(g, f, d);
    355 
    356     GeneralRange<Character> range3 = GeneralRange.downTo(Ordering.natural(), 'a', CLOSED);
    357     ASSERT.that(pathToList(BstRangeOps.furthestPath(range3, RIGHT, pathFactory, d)))
    358         .hasContentsInOrder(g, f, d);
    359 
    360     GeneralRange<Character> range4 = GeneralRange.downTo(Ordering.natural(), 'h', CLOSED);
    361     assertNull(BstRangeOps.furthestPath(range4, RIGHT, pathFactory, d));
    362   }
    363 
    364   public void testRightmostPathUpTo() {
    365     //     d
    366     //    / \
    367     //   b   f
    368     //    \ / \
    369     //    c e g
    370     SimpleNode c = new SimpleNode('c', null, null);
    371     SimpleNode b = new SimpleNode('b', null, c);
    372     SimpleNode e = new SimpleNode('e', null, null);
    373     SimpleNode g = new SimpleNode('g', null, null);
    374     SimpleNode f = new SimpleNode('f', e, g);
    375     SimpleNode d = new SimpleNode('d', b, f);
    376 
    377     GeneralRange<Character> range1 = GeneralRange.upTo(Ordering.natural(), 'd', OPEN);
    378     ASSERT.that(pathToList(BstRangeOps.furthestPath(range1, RIGHT, pathFactory, d)))
    379         .hasContentsInOrder(c, b, d);
    380 
    381     GeneralRange<Character> range2 = GeneralRange.upTo(Ordering.natural(), 'd', CLOSED);
    382     ASSERT.that(pathToList(BstRangeOps.furthestPath(range2, RIGHT, pathFactory, d)))
    383         .hasContentsInOrder(d);
    384 
    385     GeneralRange<Character> range3 = GeneralRange.upTo(Ordering.natural(), 'a', CLOSED);
    386     assertNull(BstRangeOps.furthestPath(range3, RIGHT, pathFactory, d));
    387 
    388     GeneralRange<Character> range4 = GeneralRange.upTo(Ordering.natural(), 'h', CLOSED);
    389     ASSERT.that(pathToList(BstRangeOps.furthestPath(range4, RIGHT, pathFactory, d)))
    390         .hasContentsInOrder(g, f, d);
    391   }
    392 
    393   @GwtIncompatible("NullPointerTester")
    394   public void testNullPointers() throws Exception {
    395     defaultNullPointerTester().testAllPublicStaticMethods(BstRangeOps.class);
    396   }
    397 }
    398