src/test/java/com/android/tools/r8/utils/SegmentTreeTests.java

// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

package com.android.tools.r8.utils;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNull;

import com.android.tools.r8.TestBase;
import com.android.tools.r8.TestParameters;
import com.android.tools.r8.TestParametersCollection;
import java.util.Map;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

@RunWith(Parameterized.class)
public class SegmentTreeTests extends TestBase {

  @Parameters(name = "{0}")
  public static TestParametersCollection data() {
    return getTestParameters().withNoneRuntime().build();
  }

  public SegmentTreeTests(TestParameters parameters) {
    parameters.assertNoneRuntime();
  }

  private SegmentTree<Integer> tree(boolean allowOverrides) {
    return new SegmentTree<>(allowOverrides);
  }

  @Test
  public void testInsertSimpleRange() {
    SegmentTree<Integer> tree = tree(false).add(1, 100, 3);
    Map.Entry<Integer, Integer> entry = tree.findEntry(50);
    assertEntry(tree, 50, 1, 3);
    assertNull(tree.find(0));
    assertNull(tree.find(101));
  }

  @Test
  public void testInsertMultipleRanges() {
    SegmentTree<Integer> tree = tree(false).add(1, 10, 3).add(20, 30, 7).add(31, 100, 9);
    assertEntry(tree, 10, 1, 3);
    assertNull(tree.findEntry(11));
    assertEntry(tree, 20, 20, 7);
    assertEquals(tree.findEntry(31), tree.findEntry(100));
    assertNull(tree.find(101));
  }

  @Test(expected = AssertionError.class)
  public void testAssertingNoOverrides() {
    tree(false).add(1, 10, 3).add(7, 2, 4);
  }

  @Test
  public void testOverrideLeft() {
    SegmentTree<Integer> tree = tree(true).add(7, 9, 2).add(6, 7, 1);
    assertNull(tree.findEntry(5));
    assertEntry(tree, 7, 6, 1);
    assertEntry(tree, 9, 8, 2);
    assertNull(tree.findEntry(10));
    assertEquals(2, tree.size());
  }

  @Test
  public void testOverrideRight() {
    SegmentTree<Integer> tree = tree(true).add(6, 7, 1).add(7, 9, 2);
    assertNull(tree.findEntry(5));
    assertEntry(tree, 6, 6, 1);
    assertEntry(tree, 8, 7, 2);
    assertNull(tree.findEntry(10));
    assertEquals(2, tree.size());
  }

  @Test
  public void testOverrideContained() {
    SegmentTree<Integer> tree = tree(true).add(0, 100, 1).add(25, 75, 2);
    assertEntry(tree, 24, 0, 1);
    assertEntry(tree, 75, 25, 2);
    assertEntry(tree, 100, 76, 1);
    assertNull(tree.findEntry(101));
    assertEquals(2, tree.size());
  }

  @Test
  public void testOverrideContainer() {
    SegmentTree<Integer> tree = tree(true).add(25, 75, 2).add(0, 100, 1);
    assertEntry(tree, 24, 0, 1);
    assertEntry(tree, 75, 0, 1);
    assertEntry(tree, 100, 0, 1);
    assertNull(tree.findEntry(101));
    assertEquals(1, tree.size());
  }

  private void assertEntry(
      SegmentTree<Integer> tree, int index, int expectedStart, int expectedValue) {
    assertEquals(expectedStart, (int) tree.findEntry(index).getKey());
    assertEquals(expectedValue, (int) tree.findEntry(index).getValue());
  }
}