Test cases for the most common ancestor problem

TestFCA.java

package findcommonancestor;

import org.junit.Test;

import static org.junit.Assert.*;

public class TestFCA {
    FindCommonAncestor fca = new MyFindCommonAncestor();
    String result, commit1, commit2;

    @Test
    public void atlassianTest() {

        //     E-F
        //    /   \
        // A-B-C-D-G

        String[] commits = {"G", "F", "E", "D", "C", "B", "A"};
        String[][] parents = {{"F","D"},{"E"}, {"B"}, {"C"}, {"B"}, {"A"}, null};

        commit1 = "D";
        commit2 = "F";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("atlassian: standard example", "B", result);

        commit1 = "B";
        commit2 = "F";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("atlassian: both merge commit and commit to be searched for", "B", result);

        commit1 = "G";
        commit2 = "A";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("atlassian: latest to root", "A", result);

        commit1 = "A";
        commit2 = "G";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("atlassian: root to latest", "A", result);
    }

    @Test
    public void atlassianTwoBranchesTest() {

        //     E-F
        //    /
        // A-B-C-D

        String[] commits = {"F", "E", "D", "C", "B", "A"};
        String[][] parents = {{"E"}, {"B"}, {"C"}, {"B"}, {"A"}, null};

        commit1 = "D";
        commit2 = "F";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("simple atlassian: standard example 1/5", "B", result);

        commit1 = "B";
        commit2 = "F";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("simple atlassian: both merge commit and commit to be searched for", "B", result);

        commit1 = "D";
        commit2 = "A";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("simple atlassian: latest to root (branch 1)", "A", result);

        commit1 = "A";
        commit2 = "D";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("simple atlassian: root to latest (branch 1)", "A", result);

        commit1 = "F";
        commit2 = "A";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("simple atlassian: latest to root (branch 2)", "A", result);

        commit1 = "A";
        commit2 = "F";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("simple atlassian: root to latest (branch 2)", "A", result);

        commit1 = "F";
        commit2 = "F";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("simple atlassian: same branch 1/3", "F", result);

        commit1 = "E";
        commit2 = "F";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("simple atlassian: same branch 2/3", "E", result);

        commit1 = "A";
        commit2 = "F";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("simple atlassian: same branch 3/3", "A", result);
    }

    @Test
    public void sameCommitsTest() {

        //     E-F
        //    /   \
        // A-B-C-D-G

        String[] commits = {"G", "F", "E", "D", "C", "B", "A"};
        String[][] parents = {{"F","D"}, {"E"}, {"B"}, {"C"}, {"B"}, {"A"}, null};

        commit1 = "E";
        commit2 = "E";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("E", result);

        commit1 = "G";
        commit2 = "G";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("G", result);

        commit1 = "A";
        commit2 = "A";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("A", result);
    }

    @Test
    public void linearGraphTest() {

        // A-B-C-D

        String[] commits = {"D", "C", "B", "A"};
        String[][] parents = {{"C"}, {"B"}, {"A"}, null};

        commit1 = "D";
        commit2 = "B";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("linear graph, newest>oldest", "B", result);

        commit1 = "B";
        commit2 = "D";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("linear graph, oldest>newest", "B", result);

        commit1 = "D";
        commit2 = "C";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("linear graph, adjacent commits", "C", result);

        commit1 = "D";
        commit2 = "A";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("linear graph, from latest to root", "A", result);

        commit1 = "A";
        commit2 = "A";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("linear graph, root", "A", result);

        commit1 = "D";
        commit2 = "D";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("linear graph, latest", "D", result);
    }

    @Test
    public void mergeOfThreeCommitsTest() {

        //   B
        //  /
        // A-C
        //  \
        //   D

        String[] commits = {"D", "C", "B", "A"};
        String[][] parents = {{"A"}, {"A"}, {"A"}, null};

        commit1 = "D";
        commit2 = "B";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("three commits merge: 1/3", "A", result);

        commit1 = "D";
        commit2 = "C";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("three commits merge: 2/3", "A", result);

        commit1 = "B";
        commit2 = "C";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("three commits merge: 3/3", "A", result);

        commit1 = "A";
        commit2 = "D";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("three commits merge: with root 1/3", "A", result);

        commit1 = "C";
        commit2 = "A";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("three commits merge: with root 2/3", "A", result);

        commit1 = "A";
        commit2 = "B";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("three commits merge: with root 3/3", "A", result);
    }

    @Test
    public void emptyCommitIdsTest() {

        // A-B-C-D

        String[] commits = {"D", "C", "B", "A"};
        String[][] parents = {{"C"}, {"B"}, {"A"}, null};

        commit1 = "";
        commit2 = "B";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("empty commits", "", result);

        commit1 = "B";
        commit2 = "";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("empty commits", "", result);

        commit1 = "";
        commit2 = "";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("empty commits", "", result);

        commit1 = null;
        commit2 = "";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("null commit", "", result);

        commit1 = "E";
        commit2 = "E";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("same commits not-present in the commit history", "", result);
    }

    @Test
    public void brokenCommitArraysTest() {

        // A-B-C-D

        String[] commits = {"D", "C", "B"};
        String[][] parents = {{"C"}, {"B"}, {"A"}, null};

        commit1 = "A";
        commit2 = "B";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("commits.length < parents.length", "", result);

        commits = new String[]{"E", "D", "C", "B", "A"};

        commit1 = "C";
        commit2 = "B";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("commits.length > parents.length", "", result);

        commits = new String[]{"D", null, "B"};
        commit1 = "D";
        commit2 = "B";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("null in commit hashes", "", result);
    }

    @Test
    public void orphanCommitsTest() {

        // A
        //
        // B

        String[] commits = {"B", "A"};
        String[][] parents = {null, null};

        commit1 = "A";
        commit2 = "A";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("same different orphan commits: A", "A", result);

        commit1 = "B";
        commit2 = "B";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("same different orphan commits: B", "B", result);

        commit1 = "A";
        commit2 = "B";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("different orphan commits 1/2", "", result);

        commit1 = "B";
        commit2 = "A";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("different orphan commits 2/2", "", result);
    }

    @Test
    public void disjointGraphsCommitsOnSameGraphsTest() {

        //   B-C
        //  /
        // A-D-E
        //
        // X-Y-Z

        String[] commits = {"E", "D", "C", "B", "A", "Z", "Y", "X"};
        String[][] parents = {{"D"}, {"A"}, {"B"}, {"A"}, null, {"Y"}, {"X"}, null};

        commit1 = "E";
        commit2 = "C";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("disjoint graphs: same graph 1/4", "A", result);

        commit1 = "E";
        commit2 = "A";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("disjoint graphs: same graph 2/4", "A", result);

        commit1 = "C";
        commit2 = "A";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("disjoint graphs: same graph 3/4", "A", result);

        commit1 = "C";
        commit2 = "B";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("disjoint graphs: same graph 4/4", "B", result);

        commit1 = "Z";
        commit2 = "Y";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("disjoint graphs: same graph[2] 1/3", "Y", result);

        commit1 = "Z";
        commit2 = "X";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("disjoint graphs: same graph[2] 2/3", "X", result);

        commit1 = "X";
        commit2 = "Y";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("disjoint graphs: same graph[2] 3/3", "X", result);
    }

    @Test
    public void disjointGraphsCommitsOnDifferentGraphsTest() {

        //   B-C
        //  /
        // A-D-E
        //
        // X-Y-Z

        String[] commits =   {  "E",   "D",   "C",   "B",  "A",   "Z",   "Y",   "X" };
        String[][] parents = { {"D"}, {"A"}, {"B"}, {"A"}, null, {"Y"}, {"X"}, null };

        commit1 = "E";
        commit2 = "Z";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("disjoint graphs: different graphs 1/6", "", result);

        commit1 = "E";
        commit2 = "X";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("disjoint graphs: different graphs 2/6", "", result);

        commit1 = "A";
        commit2 = "X";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("disjoint graphs: different graphs 3/6 (roots)", "", result);

        commit1 = "B";
        commit2 = "Y";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("disjoint graphs: different graphs 4/6", "", result);

        commit1 = "B";
        commit2 = "Z";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("disjoint graphs: different graphs 5/6", "", result);

        commit1 = "Y";
        commit2 = "C";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("disjoint graphs: different graphs 6/6", "", result);
    }

    @Test
    public void longerDisjointGraphTest() {

        //       B-C
        //      /
        // K-L-A-D-E
        //
        // X-Y-Z

        String[] commits =   { "E",   "D",   "C",   "B",   "A",   "L",  "K",   "Z",   "Y",  "X" };
        String[][] parents = {{"D"}, {"A"}, {"B"}, {"A"}, {"L"}, {"K"}, null, {"Y"}, {"X"}, null};

        commit1 = "E";
        commit2 = "C";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("longer disjoint graphs: same graph 1/6", "A", result);

        commit1 = "E";
        commit2 = "A";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("longer disjoint graphs: same graph 2/6", "A", result);

        commit1 = "C";
        commit2 = "A";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("longer disjoint graphs: same graph 3/6", "A", result);

        commit1 = "C";
        commit2 = "B";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("longer disjoint graphs: same graph 4/6", "B", result);

        commit1 = "C";
        commit2 = "L";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("longer disjoint graphs: same graph 5/6", "L", result);

        commit1 = "K";
        commit2 = "D";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("longer disjoint graphs: same graph 6/6", "K", result);
    }

    @Test
    public void simpleDAGWithTwoAncestorsTest() {

        // C-D
        //  ×
        // A-B

        String[] commits =   {   "D",       "B",    "C",   "A"};
        String[][] parents = {{"A","C"}, {"A","C"}, null, null};
        boolean resultPresent;

        commit1 = "D";
        commit2 = "B";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        if (result.equals("[A, C]") || result.equals("[C, A]")) {
            resultPresent = true;
        } else {
            resultPresent = false;
        }
        assertEquals("DAG with two FCAs 1/8", true, resultPresent);

        commit1 = "B";
        commit2 = "D";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        if (result.equals("[A, C]") || result.equals("[C, A]")) {
            resultPresent = true;
        } else {
            resultPresent = false;
        }
        assertEquals("DAG with two FCAs 2/8", true, resultPresent);

        commit1 = "A";
        commit2 = "C";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("DAG with two FCAs 3/8 (roots)", "", result);

        commit1 = "C";
        commit2 = "A";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("DAG with two FCAs 4/8 (roots)", "", result);

        commit1 = "B";
        commit2 = "A";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("DAG with two FCAs 5/8 (same branch)", "A", result);

        commit1 = "A";
        commit2 = "B";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("DAG with two FCAs 6/8 (same branch)", "A", result);

        commit1 = "C";
        commit2 = "D";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("DAG with two FCAs 7/8 (same branch)", "C", result);

        commit1 = "D";
        commit2 = "C";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("DAG with two FCAs 8/8 (same branch)", "C", result);
    }

    @Test
    public void complexDAGWithManyAncestorsTest() {

        //   B-C
        //  / /
        // A-D-E
        //  ×
        // F-G

        String[] commits =   {   "G",    "F",   "E",     "D",     "C",   "B",  "A" };
        String[][] parents = {{"A","F"}, null, {"D"}, {"A","F"}, {"B"}, {"A"}, null};
        boolean resultPresent;

        commit1 = "F";
        commit2 = "B";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("complex DAG: no FCAs 1/2", "", result);

        commit1 = "A";
        commit2 = "F";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("complex DAG: no FCAs 2/2", "", result);

        commit1 = "D";
        commit2 = "G";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);

        if (result.equals("[A, F]") || result.equals("[F, A]")) {
            resultPresent = true;
        } else {
            resultPresent = false;
        }
        assertEquals("complex DAG: two FCAs 1/2", true, resultPresent);

        commit1 = "G";
        commit2 = "E";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);

        if (result.equals("[A, F]") || result.equals("[F, A]")) {
            resultPresent = true;
        } else {
            resultPresent = false;
        }
        assertEquals("complex DAG: two FCAs 2/2", true, resultPresent);

        commit1 = "A";
        commit2 = "G";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("complex DAG: same branch 1/7", "A", result);

        commit1 = "G";
        commit2 = "F";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("complex DAG: same branch 2/7", "F", result);

        commit1 = "A";
        commit2 = "D";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("complex DAG: same branch 3/7", "A", result);

        commit1 = "D";
        commit2 = "F";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("complex DAG: same branch 4/7", "F", result);

        commit1 = "C";
        commit2 = "F";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("complex DAG: same branch 5/7", "F", result);

        commit1 = "F";
        commit2 = "E";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("complex DAG: same branch 6/7", "F", result);

        commit1 = "A";
        commit2 = "E";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("complex DAG: same branch 7/7", "A", result);

        commit1 = "D";
        commit2 = "D";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("complex DAG: same commit 1/3", "D", result);

        commit1 = "A";
        commit2 = "A";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("complex DAG: same commit 2/3", "A", result);

        commit1 = "F";
        commit2 = "F";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("complex DAG: same commit 3/3", "F", result);

        commit1 = "C";
        commit2 = "G";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("complex DAG: merged commit 1/2", "A", result);

        commit1 = "E";
        commit2 = "C";
        result = fca.findCommmonAncestor(commits, parents, commit1, commit2);
        assertEquals("complex DAG: merged commit 2/2", "D", result);
    }

}