import org.junit.Assert;
import org.junit.BeforeClass;
import org.junit.Test;

import java.util.Arrays;
import java.util.List;

public class SimpleTest {
    private static PathGraph pathGraph;

    @BeforeClass
    public static void init() {
        pathGraph = new DynamicPathGraph();
    }

    @Test
    public void test1() {
        List<Integer> weights = Arrays.asList(1, 4, 5, 4);
        check(weights, pathGraph.maximumIndependentSet(weights), 8);
    }

    @Test
    public void test2() {
        List<Integer> weights = Arrays.asList(10, 2, 1, 4);
        check(weights, pathGraph.maximumIndependentSet(weights), 14);
    }

    @Test
    public void test3() {
        List<Integer> weights = Arrays.asList(1, 3, 10, 9);
        check(weights, pathGraph.maximumIndependentSet(weights), 12);
    }

    @Test
    public void test4() {
        List<Integer> weights = Arrays.asList(1, 9, 7, 1, 5);
        check(weights, pathGraph.maximumIndependentSet(weights), 14);
    }

    static void check(List<Integer> weights, List<Integer> subset, int maximum) {
        int weight = subset.isEmpty() ? 0 : weights.get(subset.get(0));
        for (int i = 1; i < subset.size(); i++) {
            int previous = subset.get(i - 1);
            int index = subset.get(i);
            Assert.assertTrue("Indices are not increasing.", index > previous);
            Assert.assertTrue("Subset is not independent.", index > previous + 1);
            weight += weights.get(index);
        }
        Assert.assertEquals("Weight of independent set is not maximum.", maximum, weight);
    }
}