package com.pact;

import java.io.PrintStream;
import java.util.HashSet;
import java.util.Iterator;

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

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

        this.children = new HashSet<Node>();
        if (s.length() > 1)
            setChildren(s);
    }

    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 = 0;
                    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 sibs = (HashSet)this.parent.children.clone();
            sibs.remove(this);
            return sibs;
        }
        return new HashSet();
    }

    public boolean equals(Node node)
    {
        String nodeVenn = node.getVenn();
        if ((nodeVenn.length() == 1) && (this.venn.length() == nodeVenn.length())) {
            return nodeVenn.equals(this.venn);
        }

        int itCount = 0;
        int eqCount = 0;
        for (Node theirChild : node.children) {
            itCount++;
            for (Node myChild : this.children) {
                if (myChild.equals(theirChild)) {
                    eqCount++;
                    break;
                }
            }
        }

        if (itCount != eqCount) {
            return false;
        }
        itCount = 0;
        eqCount = 0;
        Iterator it = this.children.iterator();
        while (it.hasNext()) {
            Iterator nIt = node.children.iterator();
            Node toCheck = (Node)it.next();
            itCount++;
            while (nIt.hasNext()) {
                if (toCheck.equals((Node)nIt.next())) {
                    eqCount++;
                    break;
                }

            }

        }

        return itCount == eqCount;
    }

    public boolean equals(Object o)
    {
        Node n = (Node)o;
        return equals(n);
    }

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

    public HashSet<Node> reducedCombine(Node node) {
        HashSet result = new HashSet();

        if (oneAreaShared(this, node)) {
            result.add(combineAtRoot(node));
            return result;
        }
        HashSet compCombine = combine(node);
        Iterator it = compCombine.iterator();

        if (!it.hasNext()) {
            return result;
        }
        Node curr = (Node)it.next();
        int smallest = curr.getNumAreas();
        result.add(curr);

        while (it.hasNext()) {
            Node curr1 = (Node)it.next();
            int currAreas = curr1.getNumAreas();
            if (currAreas < smallest) {
                smallest = currAreas;
                result.clear();
                result.add(curr1);
            } else if (currAreas == smallest) {
                result.add(curr1);
            }
        }
        return removeDuplicates(result);
    }

    private HashSet<Node> removeDuplicates(HashSet<Node> h) {
        Iterator it = h.iterator();
        HashSet result = new HashSet();
        while (it.hasNext()) {
            Node curr = (Node)it.next();
            if (!contains(curr, result)) {
                result.add(curr);
            }
        }
        return result;
    }

    private boolean oneAreaShared(Node node1, Node node2)
    {
        HashSet result = new HashSet();
        node2.deepSearch(node1, result);
        HashSet largest = getLNodes(result);
        if (largest.isEmpty()) {
            return false;
        }
        return (Nodes.setNodesSize(largest) == 1) && (largest.size() == 1);
    }

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

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

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

        HashSet sResult = new HashSet();
        node2.deepSearch(node1, sResult);

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

        HashSet largest = getLNodes(sResult);

        HashSet unsharedNodes = new HashSet();
        node2.collectUnshared(unsharedNodes);
        node1.collectUnshared(unsharedNodes);

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

        }

        if (largest.size() > 0)
        {
            Iterator itLargest = largest.iterator();

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

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

            HashSet newSibs = new HashSet();
            HashSet otherSibs1 = new HashSet();
            HashSet otherSibs2 = new HashSet();

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

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

            Iterator nsIt = newSibs.iterator();

            if ((otherSibs1.isEmpty()) && (otherSibs2.isEmpty())) {
                while (nsIt.hasNext()) {
                    unsharedNodes.add((Node)nsIt.next());
                }

            }

        }

        HashSet newLinkedNodes = getLinkedNodes(unsharedNodes);

        HashSet polys = reviewPolys(newLinkedNodes);
        if (!polys.isEmpty())
        {
            Iterator polyIt = polys.iterator();
            if (polyIt.hasNext()) {
                HashSet polyresult = addPolys((HashSet)polyIt.next());
                Iterator prIt = polyresult.iterator();
                if (prIt.hasNext()) {
                    Nodes curr = (Nodes)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 polyresults = polyOne.combine(polyTwo);
                        Iterator prsIt = polyresults.iterator();
                        while (prsIt.hasNext())
                            result.add((Node)prsIt.next());
                    }
                    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 = newLinkedNodes.iterator();
        if (nLNit.hasNext()) {
            HashSet combined = ((Nodes)nLNit.next()).combineNew();
            Iterator cIt = combined.iterator();
            while (cIt.hasNext()) {
                Nodes curr = (Nodes)cIt.next();
                HashSet newResults = curr.node1.combine(curr.node2);
                Iterator nRit = newResults.iterator();
                while (nRit.hasNext())
                {
                    result.add((Node)nRit.next());
                }
            }

            return result;
        }

        if (Nodes.setNodesSize(largest) == 1)
        {
            HashSet unique = getUniqueNodes(sResult);
            Iterator uIt = unique.iterator();

            while (uIt.hasNext()) {
                Node curr = (Node)uIt.next();
                HashSet dupres = curr.getDuplicates(sResult);
                if (dupres.size() > 1) {
                    HashSet newDupNodes = getLinkedNodes(dupres);
                    Iterator ndIt = newDupNodes.iterator();
                    while (ndIt.hasNext()) {
                        HashSet combined = ((Nodes)ndIt.next()).combineNew();
                        Iterator cIt = combined.iterator();
                        while (cIt.hasNext()) {
                            Nodes curr2 = (Nodes)cIt.next();
                            HashSet newResults = curr2.node1.combine(curr2.node2);
                            Iterator nRit = newResults.iterator();
                            while (nRit.hasNext())
                            {
                                result.add((Node)nRit.next());
                            }
                        }
                    }
                }
                else {
                    result.add(node2.combineAtRoot(node1));
                }
            }
            return result;
        }

        if (Nodes.setNodesSize(largest) > 1)
        {
            for (Object aLargest : largest) {
                Nodes currL = (Nodes) aLargest;
                HashSet largeResult = subTrees(currL);
                Iterator lrIt = largeResult.iterator();
                while (lrIt.hasNext()) {
                    result.add((Node) lrIt.next());
                }
            }
            return result;
        }

        return result;
    }

    private void sortLargestSibs(Iterator<Node> lgsibs, Node lg, HashSet<Node> ns, HashSet<Node> os) {
        while (lgsibs.hasNext()) {
            Node curr = (Node)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);
        }
    }

    public HashSet<Node> subTrees(Nodes 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 newresult = newone.combine(newtwo);
                Iterator newit = newresult.iterator();
                while (newit.hasNext()) {
                    result.add((Node) newit.next());
                }
                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;
    }

    private void search(Node node, HashSet<Nodes> h)
    {
        if (equals(node)) {
            this.linkNodes.add(node);
            node.linkNodes.add(this);

            h.add(new Nodes(this, node));
        } else {
            Iterator it = this.children.iterator();
            while (it.hasNext())
                ((Node)(Node)it.next()).search(node, h);
        }
    }

    private HashSet<Nodes> searchBothNodes(Node node)
    {
        HashSet<Nodes> sResult = new HashSet();
        search(node, sResult);

        HashSet<Nodes> nsResult = new HashSet();
        node.search(this, nsResult);

        for (Nodes curr : nsResult) {
            boolean inSet = inSet(curr, sResult);
            if (!inSet) {
                sResult.add(curr);
            }
        }
        return sResult;
    }

    public void deepSearch(Node node, HashSet<Nodes> h)
    {
        HashSet<Nodes> first_result = searchBothNodes(node);
        for(Nodes res : first_result) {
            h.add(res);
        }

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

    private boolean inSet(Nodes n, Iterable<Nodes> it)
    {
        for (Nodes nodes : it) {
            if (n.equals(nodes)) {
                return true;
            }
        }
        return false;
    }

    private void resetSearch() {
        this.linkNodes = new HashSet<Node>();
        this.linkNode = null;

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

    private HashSet<Nodes> getLNodes(HashSet<Nodes> h)
    {
        HashSet result = new HashSet();
        int size = 0;

        Iterator it = h.iterator();
        if (it.hasNext()) {
            Nodes curr = (Nodes)it.next();
            size = curr.nodesSize();
            result.add(curr);
        }
        while (it.hasNext()) {
            Nodes curr = (Nodes)it.next();
            if (size < curr.nodesSize()) {
                size = curr.nodesSize();
                result.clear();
                result.add(curr);
            } else if (size == curr.nodesSize()) {
                result.add(curr);
            }
        }
        return result;
    }

    private Node combineAtRoot(Node node)
    {
        HashSet uniqueNodes = new HashSet();
        Iterator thisIt = this.children.iterator();
        Iterator nodeIt = node.children.iterator();
        boolean reduced = false;
        while (thisIt.hasNext()) {
            Node curr = (Node)thisIt.next();
            if (!contains(curr, uniqueNodes))
                uniqueNodes.add(curr);
            else {
                reduced = true;
            }
        }
        while (nodeIt.hasNext()) {
            Node curr = (Node)nodeIt.next();
            if (!contains(curr, uniqueNodes))
                uniqueNodes.add(curr);
            else {
                reduced = true;
            }
        }
        Iterator unIt = uniqueNodes.iterator();
        String result = "(";
        while (unIt.hasNext()) {
            result = result + unIt.next();
        }
        result = result + ")";

        if (!reduced) {
            return new Node(null, "(" + this.venn + node.getVenn() + ")");
        }
        return new Node(null, result);
    }

    private boolean unshared()
    {
        if (this.linkNodes.isEmpty())
        {
            Iterator it = this.children.iterator();
            if (!it.hasNext()) {
                return true;
            }
            while (it.hasNext()) {
                if (!((Node)it.next()).unshared()) {
                    return false;
                }
            }
            return true;
        }
        return false;
    }

    private void collectUnshared(HashSet<Node> h) {
        if (unshared()) {
            h.add(this);
        }
        Iterator it = this.children.iterator();
        while (it.hasNext())
            ((Node)it.next()).collectUnshared(h);
    }

    private HashSet<Nodes> getLinkedNodes(HashSet<Node> h)
    {
        HashSet result = new HashSet();
        Iterator hit = h.iterator();
        while (hit.hasNext()) {
            Node curr = (Node)hit.next();
            if (curr.hasLink() != null)
                result.add(new Nodes(curr, curr.hasLink()));
        }
        return result;
    }

    private Node hasLink() {
        HashSet sibs = getSiblings();
        Iterator it = sibs.iterator();
        while (it.hasNext()) {
            Node curr = (Node)it.next();

            if (!curr.linkNodes.isEmpty()) {
                return curr;
            }
        }
        return null;
    }

    public Node root() {
        if (getSiblings().isEmpty()) {
            return this;
        }
        return this.parent.root();
    }

    private String buildUp(Node n, String s) {
        if (n.parent == null) {
            return s;
        }
        String result = "(" + s;
        if (n.parent != null) {
            HashSet sibs = n.getSiblings();
            Iterator it = sibs.iterator();
            while (it.hasNext()) {
                result = result + ((Node)it.next()).getVenn();
            }
        }
        result = result + ")";
        return buildUp(n.parent, result);
    }

    private HashSet<HashSet<Nodes>> reviewPolys(HashSet<Nodes> h)
    {
        HashSet result = new HashSet();
        Iterator it = h.iterator();
        while (it.hasNext()) {
            HashSet curresult = new HashSet();
            Nodes curr = (Nodes)it.next();
            Iterator currIt = h.iterator();
            while (currIt.hasNext()) {
                Nodes inCurr = (Nodes)currIt.next();
                if (inCurr == curr) {
                    continue;
                }
                HashSet linkedNodes = inCurr.node2.linkNodes;
                Iterator lnIt = linkedNodes.iterator();
                boolean found = false;
                while (lnIt.hasNext()) {
                    Node currln = (Node)lnIt.next();
                    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 HashSet<Nodes> addPolys(HashSet<Nodes> h) {
        HashSet setresult = new HashSet();
        Iterator it = h.iterator();
        Nodes first = (Nodes)it.next();
        String result = first.node2.getVenn();
        result = result + first.node1.getVenn();
        while (it.hasNext()) {
            result = result + ((Nodes)it.next()).node1.getVenn();
        }
        Iterator itr = h.iterator();
        while (itr.hasNext()) {
            Nodes toAdd = new Nodes(((Nodes)itr.next()).node2, new Node(null, "(" + result + ")"));
            setresult.add(toAdd);
        }
        return setresult;
    }

    private boolean isIn(Node node) {
        if (this == node) {
            return true;
        }
        Iterator it = this.children.iterator();
        while (it.hasNext()) {
            if (((Node)it.next()).isIn(node)) {
                return true;
            }
        }

        return false;
    }

    private HashSet<Node> getUniqueNodes(HashSet<Nodes> h)
    {
        HashSet result = new HashSet();
        Iterator it = h.iterator();
        while (it.hasNext()) {
            Nodes curr = (Nodes)it.next();
            if (!result.contains(curr.node1)) {
                result.add(curr.node1);
            }
            if (!result.contains(curr.node2)) {
                result.add(curr.node2);
            }
        }
        return result;
    }

    private HashSet<Node> getDuplicates(HashSet<Nodes> h) {
        HashSet result = new HashSet();
        Iterator it = h.iterator();
        while (it.hasNext()) {
            Nodes curr = (Nodes)it.next();
            if (curr.node1 == this)
                result.add(curr.node2);
            else if (curr.node2 == this) {
                result.add(curr.node1);
            }
        }
        return result;
    }

    protected Node reduce()
    {
        HashSet c = this.children;
        HashSet uniqueC = new HashSet();
        HashSet dupC = new HashSet();
        Iterator it = c.iterator();
        while (it.hasNext()) {
            Node curr = (Node)it.next();
            if (contains(curr, uniqueC))
                dupC.add(curr);
            else {
                uniqueC.add(curr);
            }
        }
        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 contains(Node n, HashSet<Node> h)
    {
        Iterator it = h.iterator();
        while (it.hasNext()) {
            Node curr = (Node)it.next();
            if (curr.equals(n)) {
                return true;
            }
        }
        return false;
    }
}