ej_java_pact/src/com/pact/Node.java

package com.pact;

import java.util.*;

public class Node {
    static int ID = 0;

    Node parent;
    private String venn;
    private List<Node> children;
    List<Node> linkNodes;
    private Node linkNode;

    private final int id = ++ID;  // Unique Identifier for all created nodes

    private int hash;

    public Node(Node p, String s) {
        this.linkNode = null;
        this.linkNodes = new ArrayList<>();
        this.venn = s;
        this.parent = p;
        this.hash = 0;

        this.children = new ArrayList<>();
        if (s.length() > 1)
            setChildren(s);
        if (children.isEmpty()) {
            hash = (venn.hashCode()*1073676287) ^ (venn.hashCode()*97);
        } else {
            for (Node child : children) {
                hash = hash ^ child.hash;
            }
            hash *= 33;
        }
    }

    public Node(Node p, char s) {
        this(p, ""+s);
    }


    public boolean isRoot() {
        return parent == null;
    }

    public boolean isLeaf() {
        return children.isEmpty();
    }

    public int nSiblings() {
        if (isRoot()) return 0;
        else return parent.children.size() - 1;
    }

    private void setChildren(String s) {
        try {
            String vennChildren = s.substring(1, s.length() - 1);
            int count = 0;
            while (count < vennChildren.length())
                if (vennChildren.charAt(count) == '(') {
                    int start = count;
                    count++;
                    int end;
                    int brackets = 1;
                    while (true)
                    {
                        if (vennChildren.charAt(count) == '(') {
                            brackets++;
                        }
                        if (vennChildren.charAt(count) == ')') {
                            brackets--;
                            if (brackets == 0) {
                                count++;
                                break;
                            }
                        }
                        count++;
                    }
                    end = count;
                    Node child = new Node(this, vennChildren.substring(start, end));

                    this.children.add(child);
                } else {
                    Node child = new Node(this, vennChildren.charAt(count));

                    this.children.add(child);
                    count++;
                }
        }
        catch (StringIndexOutOfBoundsException se) {
            throw new BracketException();
        }
    }

    String getVenn()
    {
        return this.venn;
    }

    public String toString()
    {
        return this.venn;
    }

    List<Node> getSiblings() {
        if (this.parent != null) {
            List<Node> sibs = new ArrayList<>(parent.children);
            sibs.remove(this);
            return sibs;
        }
        return new ArrayList<>();
    }

    public boolean equals(Object obj) {
        if (this == obj) return true;  // Literally the same object
        if (!(obj instanceof Node)) return false; // Wrong type

        Node node = (Node) obj;
        if (hash != node.hash) return false; // equal object have equal hash codes

        // If above checks fall through, we need to actually look at the structure
        // Of the Node.

        String nodeVenn = node.getVenn();
        // Case for leaf nodes
        if ((nodeVenn.length() == 1) && (this.venn.length() == 1)) {
            return nodeVenn.equals(this.venn);
        }

        if (children.size() != node.children.size()){
            return false;
        }

        // Check to make sure all of my children exist in node's children
        for (Node theirChild : node.children) {
            boolean foundMatch = false;
            for (Node myChild : this.children) {
                if (myChild.equals(theirChild)) {
                    foundMatch = true;
                    break;
                }
            }
            if(!foundMatch) return false;
        }
        return true;
    }

//    @Override
//    public int hashCode(){
//        return hash;
//    }

    public static List<NodePair> deepSearch(Node nodeA, Node nodeB) {
        List<NodePair> result = new ArrayList<>();

        Stack<Node> searchNodes = new Stack<>();
        searchNodes.push(nodeB);
        while (!searchNodes.isEmpty()) {
            Node curr = searchNodes.pop();

            // res1: Occurrences of node in this tree
            List<NodePair> res1 = nodeA.search(curr);

            // res2: Occurrences of this tree in node
            List<NodePair> res2 = curr.search(nodeA);

            assert(res1.size() == 0 || res2.size() == 0 || res1.equals(res2));

            if(!res1.isEmpty()){
                result.addAll(res1);
            } else if(!res2.isEmpty()){
                result.addAll(res2);
            }

            searchNodes.addAll(curr.children);
        }
        return result;
    }

    Node root() {
        if (isRoot()) return this;
        else return this.parent.root();
    }

    private int getNumAreas() {
        int count = 0;
        for (int i = 0; i < this.venn.length(); i++) {
            if ((this.venn.charAt(i) != ')') && (this.venn.charAt(i) != '(')) {
                count++;
            }
        }
        return count;
    }

    /**
     * Search this tree for the subtree with given root
     * @param targetNode the root of the subtree to search for
     */
    private List<NodePair> search(Node targetNode) {
        List<NodePair> result = new ArrayList<>();
        // Use stack to avoid recursion here
        Stack<Node> searchNodes = new Stack<>();
        searchNodes.push(this);
        while (!searchNodes.isEmpty()) {
            Node curr = searchNodes.pop();
            if (curr.equals(targetNode)) {
                curr.linkNodes.add(targetNode);
                targetNode.linkNodes.add(curr);
                result.add(new NodePair(curr, targetNode));
            } else {
                searchNodes.addAll(curr.children);
            }
        }
        return result;
    }

    /**
     * Searches in this tree for the presence of the Node node.
     * @param node
     * @return
     */
    private boolean isIn(Node node) {
        if (this == node) {
            return true;
        }
        for (Node child : this.children) {
            if (child.isIn(node)) {
                return true;
            }
        }
        return false;
    }

    /**
     * Looks through this Node's siblings and returns the first one that has linkNodes. If no sibling
     * has linkNodes, returns null.
     * @return
     */
    private Node hasLink() {
        for (Node curr : getSiblings()) {
            if (!curr.linkNodes.isEmpty()) {
                return curr;
            }
        }
        return null;
    }

    private boolean unshared() {
        if (this.linkNodes.isEmpty()) {
            if(this.children.isEmpty()) {
                return true;
            } else {
                for (Node node : this.children) {
                    if (!node.unshared()) {
                        return false;
                    }
                }
            }
            return true;
        } else {
            return false;
        }
    }

    private void resetSearch() {
        this.linkNodes.clear();
        this.linkNode = null;

        for (Node child : this.children) {
            child.resetSearch();
        }
    }

    /**
     * Searches in h for all NodePairs that contain this object as either node1 or node2
     * @param h
     * @return
     */
    private List<Node> getDuplicates(List<NodePair> h) {
        List<Node> result = new ArrayList<>();
        for (NodePair curr : h) {
            if (curr.node1 == this)
                result.add(curr.node2);
            else if (curr.node2 == this) {
                result.add(curr.node1);
            }
        }
        return result;
    }

    /**
     * Produces a reduced version of unreduced where any duplicate children have been removed. Note that this doesn't
     * look for duplicate sub-trees at lower levels. (ie duplicate grandchildren)
     * @param unreduced
     * @return
     */
    private static Node reduce(Node unreduced) {
        List<Node> uniqueChildren = new ArrayList<>();
        for (Node child : unreduced.children) {
            if (!child.inSet(uniqueChildren)) {
                uniqueChildren.add(child);
            }
        }
        if (uniqueChildren.size() == unreduced.children.size() || (unreduced.venn.length() == 1)) {
            return unreduced;
        }
        Iterator<Node> uIt = uniqueChildren.iterator();
        String result = uIt.next().getVenn();
        if (uIt.hasNext()) {
            while (uIt.hasNext()) {
                result += uIt.next().getVenn();
            }
            result = "(" + result + ")";
        }
        Node reduced = new Node(null, result);
        return reduced;
    }

    private boolean inSet(List<Node> h) {
        return h.contains(this);
    }

    /**
     * Traverses tree and collects all unshared nodes.
     * @return
     */
    private List<Node> collectUnshared() {
        Stack<Node> stack = new Stack<>();
        List<Node> unshared = new ArrayList();
        stack.push(this);
        while (!stack.isEmpty()){
            Node n = stack.pop();
            if (n.unshared()) {
                unshared.add(n);
            }
            stack.addAll(n.children);
        }
        return unshared;
    }

    static List<Node> combine(Node node1, Node node2) {
        System.out.println("Combining: " + node1 + ", " + node2);
        List<Node> result = _combine(node1, node2);
        System.out.println("Combining Result: " + result);
        return result;
    }

    static List<Node> _combine(Node node1, Node node2) {
        node1 = reduce(node1);
        node2 = reduce(node2);

        node2.resetSearch();
        node1.resetSearch();
        List<Node> result = new ArrayList<>();

        if (node1.equals(node2)) {
            result.add(node2);
            return result;
        }

        List<NodePair> sResult = deepSearch(node2, node1);

        if (sResult.isEmpty()) {
            result.add(combineAtRoot(node2, node1));
            return result;
        }


        List<Node> unsharedNodes = new ArrayList<>();
        unsharedNodes.addAll(node2.collectUnshared());
        unsharedNodes.addAll(node1.collectUnshared());

        if ((unsharedNodes.isEmpty()) && (node1.getNumAreas() == node2.getNumAreas())) {
            if (node1.children.size() < node2.children.size()) {
                Node toAdd = new Node(null, node1.getVenn());
                result.add(toAdd);
                return result;
            } if (node2.children.size() < node1.children.size()) {
                Node toAdd = new Node(null, node2.getVenn());
                result.add(toAdd);
                return result;
            }

        }

        List<NodePair> largest = getLargestNodePairs(sResult);
        if (!largest.isEmpty()) {
            Iterator itLargest = largest.iterator();

            NodePair flargest = (NodePair)itLargest.next();

            List<Node> lg1sibs = flargest.node1.getSiblings();
            List<Node> lg2sibs = flargest.node2.getSiblings();

            List<Node> newSibs = new ArrayList<>();
            List<Node> otherSibs1 = new ArrayList<>();
            List<Node> otherSibs2 = new ArrayList<>();

            sortLargestSibs(lg1sibs, flargest.node2, newSibs, otherSibs1);
            sortLargestSibs(lg2sibs, flargest.node1, newSibs, otherSibs2);


            if ((otherSibs1.isEmpty()) && (otherSibs2.isEmpty())) {
                unsharedNodes.addAll(newSibs);
            }

        }

        List<NodePair> newLinkedNodePair = getLinkedNodePair(unsharedNodes);

        List<List<NodePair>> polys = reviewPolys(newLinkedNodePair);
        if (!polys.isEmpty()) {
            Iterator<List<NodePair>> polyIt = polys.iterator();
            if (polyIt.hasNext()) {
                List<NodePair> polyresult = addPolys(polyIt.next());
                Iterator prIt = polyresult.iterator();
                if (prIt.hasNext()) {
                    NodePair curr = (NodePair)prIt.next();
                    if ((curr.node1.parent != null) && (curr.node1.linkNode.parent != null)) {
                        String polyString1 = buildUp(curr.node1.parent, curr.node2.getVenn());
                        String polyString2 = buildUp(curr.node1.linkNode.parent, curr.node2.getVenn());
                        Node polyOne = new Node(null, polyString1);
                        Node polyTwo = new Node(null, polyString2);
                        List<Node> polyresults = combine(polyOne, polyTwo);
                        for (Node polyResult : polyresults)
                            result.add(polyResult);
                    } else if (!curr.node1.isRoot()) {
                        String polyString1 = buildUp(curr.node1.parent, curr.node2.getVenn());
                        Node polyOne = new Node(null, polyString1);
                        result.add(polyOne);
                    } else if (!curr.node1.linkNode.isRoot()) {
                        String polyString2 = buildUp(curr.node1.linkNode.parent, curr.node2.getVenn());
                        Node polyTwo = new Node(null, polyString2);
                        result.add(polyTwo);
                    } else {
                        System.out.println("What's up Houston?");
                    }
                }
            }
            return result;
        }

        if (!newLinkedNodePair.isEmpty()) {
            List<NodePair> combined = newLinkedNodePair.get(0).combineNew();
            for (NodePair curr : combined) {
                result.addAll(combine(curr.node1, curr.node2));
            }
            return result;
        }

        if (largest.get(0).nodesSize() == 1) { // Shares only leaves
            List<Node> unique = getUniqueNodes(sResult);

            for (Node curr : unique) {
                List<Node> dupres = curr.getDuplicates(sResult);
                if (dupres.size() > 1) {
                    List<NodePair> newDupNodePair = getLinkedNodePair(dupres);
                    Iterator<NodePair> ndIt = newDupNodePair.iterator();
                    while (ndIt.hasNext()) {
                        List<NodePair> combined = ndIt.next().combineNew();
                        Iterator cIt = combined.iterator();
                        while (cIt.hasNext()) {
                            NodePair curr2 = (NodePair)cIt.next();
                            List<Node> newResults = combine(curr2.node1, curr2.node2);
                            result.addAll(newResults);
                        }
                    }
                }
                else {
                    result.add(combineAtRoot(node2, node1));
                }
            }
            return result;
        }
        else {  // shares sub-trees
            for (NodePair largest_ : largest) {
                result.addAll(subTrees(largest_));
            }
            return result;
        }
    }

    public static List<Node> reducedCombine(Node node1, Node node2) {
        List<Node> result = new ArrayList<>();

        if (oneLeafShared(node1, node2)) {
            result.add(combineAtRoot(node1, node2));
            return result;
        }
        List<Node> compCombine = combine(node1, node2);

        int smallest = Integer.MAX_VALUE;
        for (Node curr : compCombine) {
            int currAreas = curr.getNumAreas();
            if (currAreas < smallest) {
                smallest = currAreas;
                result.clear();
                result.add(curr);
            } else if (currAreas == smallest) {
                result.add(curr);
            }
        }
        return removeDuplicates(result);
    }

    /**
     * Removes any duplicate nodes. Guarantees that
     * forall A, B in result, A.equals(B) == false
     * @param all
     * @return
     */
    private static List<Node> removeDuplicates(List<Node> all) {
        // TODO: Speed up w/ sets as soon as hash problems are sorted
        List<Node> result = new ArrayList<>();
        for (Node curr : all) {
            boolean foundDup = false;
            for (Node resNode : result) {
                if (resNode.equals(curr)) {
                    foundDup = true;
                    break;
                }
            }
            if (!foundDup) {
                result.add(curr);
            }
        }
        return result;
    }

    /**
     * Returns true if the trees with roots node1 and node1 share exactly one leaf node
     * @param node1
     * @param node2
     * @return
     */
    private static boolean oneLeafShared(Node node1, Node node2) {
        List<NodePair> result = deepSearch(node2, node1);
        if (result.isEmpty()) {
            return false;
        }
        List<NodePair> largest = getLargestNodePairs(result);
        return largest.size() == 1 && largest.get(0).nodesSize() == 1;
    }

    private static void sortLargestSibs(List<Node> lgsibs, Node lg, List<Node> newSibs, List<Node> os) {
        for (Node curr : lgsibs) {
            Iterator linkIt = curr.linkNodes.iterator();
            boolean linkFlargest = false;
            if (linkIt.hasNext()) {
                linkFlargest = true;
            }
            while (linkIt.hasNext()) {
                Node currLink = (Node)linkIt.next();

                if (!lg.isIn(currLink)) {
                    linkFlargest = false;
                }
            }
            if (linkFlargest) {
                newSibs.add(curr);
            }
            else if (!curr.linkNodes.isEmpty())
                os.add(curr);
        }
    }

    private static List<Node> subTrees(NodePair largest) {
        if (largest.node1.isRoot() && largest.node2.isRoot())
            throw new IllegalArgumentException("Cannot calculate subtrees with two roots.");

        List<Node> result = new ArrayList();
        List<Node> combined = largest.combineSubTrees();

        for (Node node : combined) {
            String curr = node.getVenn();

            if ((!node.isLeaf()) && ((largest.node1.nSiblings() != 1) || (largest.node2.nSiblings() != 1))) {
                curr = curr.substring(1, curr.length() - 1);
            }

            String curr1 = "(" + largest.node1.getVenn() + curr + ")";
            String curr2 = "(" + largest.node2.getVenn() + curr + ")";
            Node newOne = new Node(null, buildUp(largest.node1.parent, curr1));
            Node newTwo = new Node(null, buildUp(largest.node2.parent, curr2));

            if ((!largest.node1.isRoot()) && (!largest.node2.isRoot())) {
                List<Node> newResult = combine(newOne, newTwo);
                result.addAll(newResult);
            }
            else if (!largest.node1.isRoot()) {
                result.add(newOne);
            }
            else if (!largest.node2.isRoot()) {
                result.add(newTwo);
            }
            return result;
        }
        return result;
    }

    /**
     *
     * @param  h HashSet
     * @return The largest NodePair in h, based on the length of n1's Venn diagram
     */
    private static List<NodePair> getLargestNodePairs(List<NodePair> h) {
        List<NodePair> result = new ArrayList<>();
        int size = -1;

        for(NodePair curr : h){
            if (curr.nodesSize() > size) {
                size = curr.nodesSize();
                result.clear();
                result.add(curr);
            } else if (curr.nodesSize() == size) {
                result.add(curr);
            }
        }
        return result;
    }

    private static Node combineAtRoot(Node node1, Node node2) { // CONVERTED
        List<Node> uniqueNodes = new ArrayList<>();
        for(Node curr : node1.children) {
            if (!curr.inSet(uniqueNodes))
                uniqueNodes.add(curr);
        }
        for(Node curr : node2.children) {
            if (!curr.inSet(uniqueNodes))
                uniqueNodes.add(curr);
        }
        if (uniqueNodes.size() < (node1.children.size() + node2.children.size())) {
            String result_venn = "(";
            for (Node unique : uniqueNodes) {
                result_venn = result_venn + unique;
            }
            result_venn = result_venn + ")";
            return new Node(null, result_venn);
        } else {
            return new Node(null, "(" + node1.venn + node2.getVenn() + ")");
        }
    }

    private static List<NodePair> getLinkedNodePair(List<Node> h) {
        List<NodePair> result = new ArrayList<>();
        for (Node curr : h) {
            if (curr.hasLink() != null)
                result.add(new NodePair(curr, curr.hasLink()));
        }
        return result;
    }

    private static String buildUp(Node n, String s) { // CONVERTED
        System.out.println("buildUp: " + s);
        if (n.parent == null) {
            return s;
        }
        String result = "(" + s;
        List<Node> sibs = n.getSiblings();
        for (Node sib : sibs) {
            result += sib.getVenn();
        }
        result += ")";
        return buildUp(n.parent, result);
    }

    private static List<List<NodePair>> reviewPolys(List<NodePair> h) {
        List<List<NodePair>> result = new ArrayList<>();
        for (NodePair curr : h) {
            List<NodePair> curresult = new ArrayList<>();
            for (NodePair inCurr : h) {
                if (inCurr == curr) {
                    continue;
                }
                List<Node> linkedNodePair = inCurr.node2.linkNodes;
                boolean found = false;
                for (Node currln : linkedNodePair) {
                    if (currln == curr.node2) {
                        found = true;
                        inCurr.node2.linkNode = currln;
                        break;
                    }
                }
                if (found) {
                    curresult.add(inCurr);
                }
            }
            if (!curresult.isEmpty()) {
                curresult.add(curr);
                result.add(curresult);
            }
        }
        return result;
    }

    private static List<NodePair> addPolys(List<NodePair> h) {
        List<NodePair> setResult = new ArrayList<>();
        NodePair first = null;
        String result = "";
        for (NodePair nodes : h) {
            if (first == null) {
                first = nodes;
                result = first.node2.getVenn();
            }
            result += nodes.node1.getVenn();
        }
        for (NodePair nodes : h) {
            NodePair toAdd = new NodePair((nodes).node2, new Node(null, "(" + result + ")"));
            setResult.add(toAdd);
        }
        return setResult;
    }

    private static List<Node> getUniqueNodes(List<NodePair> nodePairs) { // CONVERTED
        HashSet<Node> result = new HashSet<>();
        for (NodePair curr : nodePairs) {
            if (!result.contains(curr.node1)) {
                result.add(curr.node1);
            }
            if (!result.contains(curr.node2)) {
                result.add(curr.node2);
            }
        }
        System.out.println("result: " + result);
        List<Node> result_list = new ArrayList<>();
        for (NodePair curr : nodePairs) {
            result_list.add(curr.node1);
            result_list.add(curr.node2);
        }
        System.out.println("result_list: " + result_list);
        return result_list;
    }
}