123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709 |
- package com.pact;
- 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<>();
- this.venn = s;
- this.parent = p;
- this.children = new HashSet<>();
- 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<Node> sibs = (HashSet)this.parent.children.clone();
- sibs.remove(this);
- return sibs;
- }
- return new HashSet<>();
- }
- public boolean equals(Object obj) {
- if (!(obj instanceof Node)) return false;
- Node node = (Node) obj;
- 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, HashSet<NodePair> h) {
- HashSet<NodePair> first_result = searchBothNodePair(node);
- for(NodePair res : first_result) {
- h.add(res);
- }
- for(Node child : node.children) {
- deepSearch(child, h);
- }
- }
- 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;
- }
- private void search(Node node, HashSet<NodePair> h) {
- if (equals(node)) {
- this.linkNodes.add(node);
- node.linkNodes.add(this);
- h.add(new NodePair(this, node));
- } else {
- for(Node child : children) {
- child.search(node, h);
- }
- }
- }
- private HashSet<NodePair> searchBothNodePair(Node node) {
- HashSet<NodePair> sResult = new HashSet<>();
- search(node, sResult);
- HashSet<NodePair> nsResult = new HashSet<>();
- node.search(this, nsResult);
- for (NodePair curr : nsResult) {
- boolean inSet = inSet(curr, sResult);
- if (!inSet) {
- sResult.add(curr);
- }
- }
- return sResult;
- }
- private boolean inSet(NodePair n, Iterable<NodePair> it) {
- for (NodePair nodes : it) {
- if (n.equals(nodes)) {
- return true;
- }
- }
- return false;
- }
- 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(HashSet<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() {
- HashSet<Node> uniqueC = new HashSet<>();
- HashSet<Node> dupC = new HashSet<>();
- 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(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;
- }
- HashSet sResult = new HashSet();
- node2.deepSearch(node1, sResult);
- if (sResult.isEmpty()) {
- result.add(combineAtRoot(node2, node1));
- return result;
- }
- HashSet<NodePair> largest = getLNodePair(sResult);
- 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;
- }
- }
- 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 (NodePair.getNodesSize(largest) == 1) {
- 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;
- }
- if (NodePair.getNodesSize(largest) > 1) {
- 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;
- }
- return result;
- }
- public static HashSet<Node> reducedCombine(Node node1, Node node2) {
- HashSet<Node> result = new HashSet<>();
- 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 HashSet<Node> removeDuplicates(HashSet<Node> h) {
- Iterator it = h.iterator();
- HashSet result = new HashSet();
- while (it.hasNext()) {
- Node curr = (Node)it.next();
- if (!curr.inSet(result)) {
- result.add(curr);
- }
- }
- return result;
- }
- private static boolean oneAreaShared(Node node1, Node node2) {
- HashSet<NodePair> result = new HashSet<>();
- node2.deepSearch(node1, result);
- HashSet<NodePair> largest = getLNodePair(result);
- if (largest.isEmpty()) {
- return false;
- }
- 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 HashSet<NodePair> getLNodePair(HashSet<NodePair> h) {
- HashSet<NodePair> result = new HashSet<>();
- 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> uniqueNodePair = new HashSet<>();
- boolean reduced = false;
- for(Node curr : node1.children) {
- if (!curr.inSet(uniqueNodePair))
- uniqueNodePair.add(curr);
- else {
- reduced = true;
- }
- }
- for(Node curr : node2.children) {
- if (!curr.inSet(uniqueNodePair))
- uniqueNodePair.add(curr);
- else {
- reduced = true;
- }
- }
- if (!reduced) {
- return new Node(null, "(" + node1.venn + node2.getVenn() + ")");
- } else {
- String result_venn = "(";
- for (Node unique : uniqueNodePair) {
- result_venn = result_venn + unique;
- }
- result_venn = result_venn + ")";
- return new Node(null, result_venn);
- }
- }
- 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(HashSet<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;
- }
- }
|