ej_java_pact/src/com/pact/Node.java

package com.pact;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

public class Node {
    Node parent;
    private String venn;
    private List<Node> children;
    HashSet<Node> linkNodes;
    private Node linkNode;

    private int hash;

    public Node(Node p, String s) {
        this.linkNode = null;
        this.linkNodes = new HashSet<>();
        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);
    }

    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();
        }
    }

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

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

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

    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() {
//        if (children.isEmpty()) {
//            return venn.hashCode();
//        } else {
//            int h = 0;
//            for (Node child : children) {
//                h += child.hashCode();
//            }
//            return Integer.hashCode(h);
//        }
//
//    }

    public void _deepSearch(Node node, List<NodePair> h) {
        // res1: Occurrences of node in this tree
        List<NodePair> res1 = this.search(node);

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

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

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

        for(Node child : node.children) {
            _deepSearch(child, h);
        }
    }

    public List<NodePair> deepSearch(Node node) {
        List<NodePair> result = new ArrayList<>();
        _deepSearch(node, result);
        return result;
    }

    public Node root() {
        if (getSiblings().isEmpty()) {
            return this;
        }
        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 node the root of the subtree to search for
     * @param l
     */
    private void _search(Node node, List<NodePair> l) {
        if (equals(node)) {
            this.linkNodes.add(node);
            node.linkNodes.add(this);
            l.add(new NodePair(this, node));
        } else {
            for(Node child : children) {
                child._search(node, l);
            }
        }
    }

    private List<NodePair> search(Node node) {
        List<NodePair> result = new ArrayList<>();
        _search(node, result);
        return result;
    }

    private boolean isIn(Node node) {
        if (this == node) {
            return true;
        }
        for (Node child : this.children) {
            if (child.isIn(node)) {
                return true;
            }
        }
        return false;
    }

    private Node hasLink() {
        HashSet<Node> sibs = getSiblings();
        for (Node curr : sibs) {
            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 = new HashSet<>();
        this.linkNode = null;

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

    private HashSet<Node> getDuplicates(List<NodePair> h) {
        HashSet<Node> result = new HashSet<>();
        for (NodePair curr : h) {
            if (curr.node1 == this)
                result.add(curr.node2);
            else if (curr.node2 == this) {
                result.add(curr.node1);
            }
        }
        return result;
    }

    private Node reduce() {
        List<Node> uniqueC = new ArrayList<>();
        List<Node> dupC = new ArrayList<>();
        for (Node child : this.children) {
            if (child.inSet(uniqueC))
                dupC.add(child);
            else {
                uniqueC.add(child);
            }
        }
        if ((dupC.isEmpty()) || (this.venn.length() == 1)) {
            return this;
        }
        Iterator uIt = uniqueC.iterator();
        String result = "";
        if (uIt.hasNext()) {
            result = result + ((Node)uIt.next()).getVenn();
        }
        if (uIt.hasNext()) {
            result = result + "(" + result;
            while (uIt.hasNext()) {
                result = result + ((Node)uIt.next()).getVenn();
            }
            result = result + ")";
        }
        return new Node(null, result);
    }

    private boolean inSet(List<Node> h) {
        for (Node curr : h) {
            if (curr.equals(this)) {
                return true;
            }
        }
        return false;
    }

    private boolean inSet(HashSet<Node> h) {
        for (Node curr : h) {
            if (curr.equals(this)) {
                return true;
            }
        }
        return false;
    }

    private void collectUnshared(HashSet<Node> h) {
        if (unshared()) {
            h.add(this);
        }
        for (Node child : children) {
            child.collectUnshared(h);
        }
    }

    public static HashSet<Node> combine(Node node1, Node node2) {
        node1 = node1.reduce();
        node2 = node2.reduce();

        node2.resetSearch();
        node1.resetSearch();
        HashSet result = new HashSet();

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

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

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


        HashSet<Node> unsharedNodePair = new HashSet<>();
        node2.collectUnshared(unsharedNodePair);
        node1.collectUnshared(unsharedNodePair);

        if ((unsharedNodePair.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();

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

            HashSet<Node> newSibs = new HashSet<>();
            HashSet<Node> otherSibs1 = new HashSet<>();
            HashSet<Node> otherSibs2 = new HashSet<>();

            Iterator lg1It = lg1sibs.iterator();
            Iterator lg2It = lg2sibs.iterator();

            sortLargestSibs(lg1It, flargest.node2, newSibs, otherSibs1);
            sortLargestSibs(lg2It, flargest.node1, newSibs, otherSibs2);


            if ((otherSibs1.isEmpty()) && (otherSibs2.isEmpty())) {
                for (Node newSib : newSibs) {
                    unsharedNodePair.add(newSib);
                }

            }

        }

        HashSet<NodePair> newLinkedNodePair = getLinkedNodePair(unsharedNodePair);

        HashSet<HashSet<NodePair>> polys = reviewPolys(newLinkedNodePair);
        if (!polys.isEmpty()) {
            Iterator polyIt = polys.iterator();
            if (polyIt.hasNext()) {
                HashSet polyresult = addPolys((HashSet)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);
                        HashSet<Node> polyresults = combine(polyOne, polyTwo);
                        for (Node polyResult : polyresults)
                            result.add(polyResult);
                    } else if (curr.node1.parent != null) {
                        String polyString1 = buildUp(curr.node1.parent, curr.node2.getVenn());
                        Node polyOne = new Node(null, polyString1);
                        result.add(polyOne);
                    } else if (curr.node1.linkNode.parent != null) {
                        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;
        }

        Iterator nLNit = newLinkedNodePair.iterator();
        if (nLNit.hasNext()) {
            HashSet combined = ((NodePair)nLNit.next()).combineNew();
            Iterator cIt = combined.iterator();
            while (cIt.hasNext()) {
                NodePair curr = (NodePair)cIt.next();
                HashSet newResults = combine(curr.node1, curr.node2);
                Iterator nRit = newResults.iterator();
                while (nRit.hasNext()) {
                    result.add(nRit.next());
                }
            }

            return result;
        }

        if (largest.get(0).nodesSize() == 1) { // Shares only leaves
            HashSet unique = getUniqueNodePair(sResult);
            Iterator uIt = unique.iterator();

            while (uIt.hasNext()) {
                Node curr = (Node)uIt.next();
                HashSet dupres = curr.getDuplicates(sResult);
                if (dupres.size() > 1) {
                    HashSet newDupNodePair = getLinkedNodePair(dupres);
                    Iterator ndIt = newDupNodePair.iterator();
                    while (ndIt.hasNext()) {
                        HashSet combined = ((NodePair)ndIt.next()).combineNew();
                        Iterator cIt = combined.iterator();
                        while (cIt.hasNext()) {
                            NodePair curr2 = (NodePair)cIt.next();
                            HashSet newResults = combine(curr2.node1, curr2.node2);
                            Iterator nRit = newResults.iterator();
                            while (nRit.hasNext()) {
                                result.add(nRit.next());
                            }
                        }
                    }
                }
                else {
                    result.add(combineAtRoot(node2, node1));
                }
            }
            return result;
        }
        else {  // shares sub-trees
            for (Object aLargest : largest) {
                NodePair currL = (NodePair) aLargest;
                HashSet largeResult = subTrees(currL);
                Iterator lrIt = largeResult.iterator();
                while (lrIt.hasNext()) {
                    result.add(lrIt.next());
                }
            }
            return result;
        }
    }

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

        if (oneAreaShared(node1, node2)) {
            result.add(combineAtRoot(node1, node2));
            return result;
        }
        HashSet<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);
    }

    private static List<Node> removeDuplicates(List<Node> h) {
        HashSet<Node> result = new HashSet<>();
        for (Node curr : h) {
            if (!curr.inSet(result)) {
                result.add(curr);
            }
        }
        return new ArrayList(result);
    }

    private static boolean oneAreaShared(Node node1, Node node2) {
        List<NodePair> result = node2.deepSearch(node1);
        if (result.isEmpty()) {
            return false;
        }
        List<NodePair> largest = getLargestNodePairs(result);
        return largest.size() == 1 && largest.get(0).nodesSize() == 1;
//        return (NodePair.getNodesSize(largest) == 1) && (largest.size() == 1);
    }

    private static void sortLargestSibs(Iterator<Node> lgsibs, Node lg, HashSet<Node> ns, HashSet<Node> os) {
        while (lgsibs.hasNext()) {
            Node curr = lgsibs.next();
            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) {
                ns.add(curr);
            }
            else if (!curr.linkNodes.isEmpty())
                os.add(curr);
        }
    }

    private static HashSet<Node> subTrees(NodePair largest) {
        HashSet<Node> result = new HashSet();
        HashSet<Node> n = largest.combineSubTrees();

        for (Node aN : n) {
            String curr = aN.getVenn();

            if ((curr.length() > 1) && (
                    (largest.node1.getSiblings().size() != 1) ||
                            (largest.node2.getSiblings().size() != 1))) {
                curr = curr.substring(1, curr.length() - 1);
            }

            String curr1 = "(" + largest.node1.getVenn() + curr + ")";
            String curr2 = "(" + largest.node2.getVenn() + curr + ")";
            if ((largest.node1.parent != null) &&
                    (largest.node2.parent != null)) {
                String one = buildUp(largest.node1.parent, curr1);
                String two = buildUp(largest.node2.parent, curr2);
                Node newOne = new Node(null, one);
                Node newTwo = new Node(null, two);
                HashSet<Node> newResult = combine(newOne, newTwo);
                result.addAll(newResult);
                return result;
            }
            if (largest.node1.parent != null) {
                String one = buildUp(largest.node1.parent, curr1);
                Node newOne = new Node(null, one);
                result.add(newOne);
                return result;
            }
            if (largest.node2.parent != null) {
                String two = buildUp(largest.node2.parent, curr2);
                Node newTwo = new Node(null, two);
                result.add(newTwo);
                return result;
            }
            System.out.println("Houston we have a problem.");
        }
        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) {
        HashSet<Node> uniqueNodes = new HashSet<>();
        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 HashSet<NodePair> getLinkedNodePair(HashSet<Node> h) {
        HashSet<NodePair> result = new HashSet<>();
        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) {
        if (n.parent == null) {
            return s;
        }
        String result = "(" + s;
        if (n.parent != null) {
            HashSet<Node> sibs = n.getSiblings();
            for (Node sib : sibs) {
                result = result + sib.getVenn();
            }
        }
        result = result + ")";
        return buildUp(n.parent, result);
    }

    private static HashSet<HashSet<NodePair>> reviewPolys(HashSet<NodePair> h) {
        HashSet<HashSet<NodePair>> result = new HashSet<>();
        for (NodePair curr : h) {
            HashSet<NodePair> curresult = new HashSet<>();
            for (NodePair inCurr : h) {
                if (inCurr == curr) {
                    continue;
                }
                HashSet<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 HashSet<NodePair> addPolys(HashSet<NodePair> h) {
        HashSet<NodePair> setResult = new HashSet<>();
        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 HashSet<Node> getUniqueNodePair(List<NodePair> h) {
        HashSet<Node> result = new HashSet<>();
        for (NodePair curr : h) {
            if (!result.contains(curr.node1)) {
                result.add(curr.node1);
            }
            if (!result.contains(curr.node2)) {
                result.add(curr.node2);
            }
        }
        return result;
    }
}