MyFindCommonAncestor.java

package findcommonancestor;

import java.util.HashSet;
import java.util.Set;

/*
 *       / E - F \
 * A - B - C - D - G
 *
 */
 
public class MyFindCommonAncestor implements FindCommonAncestor
{
    public String findCommmonAncestor(
            String[] commitHashes, String[][] parentHashes,
            String commitHash1, String commitHash2)
    {
        int i1 = -1;
        int i2 = -1;
        boolean hashesFound = false;
        for(int i = 0; i < commitHashes.length; i++) {
            String ch = commitHashes[i];
            if(ch.equals(commitHash1)) {
                i1 = i;
            } else if(ch.equals(commitHash2)) {
                i2 = i;
            }

            if(i1 != -1 && i2 != -1) {
                hashesFound = true;
                break;
            }
        }

        if(hashesFound) {
            int firstIdx, lastIdx;
            if(i1 < i2) {
                firstIdx = i1;
                lastIdx = i2;
            } else {
                firstIdx = i2;
                lastIdx = i1;
            }

            Set<String> firstAncestors = collectAncestors(firstIdx, commitHashes, parentHashes);

            if(firstAncestors.contains(commitHashes[lastIdx])) {
                return commitHashes[lastIdx];
            }

            Set<String> lastAncestors = collectAncestors(lastIdx, commitHashes, parentHashes);

            for(int i = lastIdx + 1; i < commitHashes.length; i++) {
                String ch = commitHashes[i];
                if(firstAncestors.contains(ch) && lastAncestors.contains(ch)) {
                    return ch;
                }
            }
        }

        throw new IllegalArgumentException("Unable to find common ancestor for given args.");

    }

    private Set<String> collectAncestors(int idx, String[] chs, String[][] phs) {
        String[] parents = phs[idx];
        Set<String> collected = new HashSet<String>();

        if(parents == null) {
            return collected;
        }

        String ph1 = parents[0];
        collected.add(ph1);
        collected.addAll(collectAncestors(commitIndex(idx + 1, ph1, chs), chs, phs));

        if(parents.length == 2) {
            String ph2 = parents[1];
            collected.add(ph2);
            collected.addAll(collectAncestors(commitIndex(idx + 1, ph2, chs), chs, phs));
        }

        return collected;
    }

    private int commitIndex(int from, String hash, String[] chs) {
        for (int i = from; i < chs.length; i++) {
            String ch = chs[i];
            if (ch.equals(hash)) {
                return i;
            }
        }
        return -1;
    }

}