java_pact/Node.java

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

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

    Iterator nodeIt = node.children.iterator();
    int itCount = 0;
    int eqCount = 0;
    while (nodeIt.hasNext()) {
      Iterator it = this.children.iterator();
      Node toCheck = (Node)nodeIt.next();
      itCount++;
      while (it.hasNext()) {
        if (((Node)it.next()).equals(toCheck)) {
          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 curr = (Node)it.next();
      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 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)
    {
      Iterator largeIt = largest.iterator();
      while (largeIt.hasNext()) {
        Nodes currL = (Nodes)largeIt.next();
        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 result = new HashSet();
    HashSet n = largest.combineSubTrees();

    Iterator nit = n.iterator();

    while (nit.hasNext()) {
      String curr = ((Node)nit.next()).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 sResult = new HashSet();
    search(node, sResult);

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

    Iterator it = nsResult.iterator();
    while (it.hasNext()) {
      Nodes curr = (Nodes)it.next();

      Iterator currIt = sResult.iterator();
      boolean inSet = inSet(curr, currIt);
      if (!inSet) {
        sResult.add(curr);
      }
    }
    return sResult;
  }

  public void deepSearch(Node node, HashSet<Nodes> h)
  {
    HashSet first_result = searchBothNodes(node);
    Iterator first_it = first_result.iterator();
    while (first_it.hasNext()) {
      h.add((Nodes)first_it.next());
    }

    Iterator it = node.children.iterator();
    while (it.hasNext())
      deepSearch((Node)it.next(), h);
  }

  private boolean inSet(Nodes n, Iterator<Nodes> it)
  {
    boolean inSet = false;
    while (it.hasNext()) {
      if (n.equals(it.next())) {
        inSet = true;
        break;
      }
    }
    return inSet;
  }

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

    Iterator it = this.children.iterator();
    while (it.hasNext())
      ((Node)it.next()).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;
  }
}