diff --git a/src/main/java/models/formulas/InFormula.java b/src/main/java/models/formulas/InFormula.java deleted file mode 100644 index 7b95536..0000000 --- a/src/main/java/models/formulas/InFormula.java +++ /dev/null @@ -1,36 +0,0 @@ -package models.formulas; - -import lombok.Getter; -import models.terms.EvaluatableTerm; - -@Getter -public class InFormula extends Formula { - - private EvaluatableTerm leftSideHand; - private EvaluatableTerm rightSideHand; - - public InFormula(EvaluatableTerm leftSideHand, EvaluatableTerm rightSideHand) { - this.leftSideHand = leftSideHand; - this.rightSideHand = rightSideHand; - } - - @Override - public String toString() { - return leftSideHand.toString() + " in " + rightSideHand.toString(); - } - - @Override - public boolean equals(Object another) { - if (! (another instanceof InFormula)) { - return false; - } - InFormula formula = (InFormula) another; - return leftSideHand.equals(formula.getLeftSideHand()) && rightSideHand.equals(formula.getRightSideHand()); - } - - @Override - public int hashCode() { - return toString().hashCode(); - } - -} diff --git a/src/main/java/models/formulas/meta/MetaDependencyFormula.java b/src/main/java/models/formulas/meta/MetaDependencyFormula.java index d16b9fa..b2397b5 100644 --- a/src/main/java/models/formulas/meta/MetaDependencyFormula.java +++ b/src/main/java/models/formulas/meta/MetaDependencyFormula.java @@ -1,5 +1,6 @@ package models.formulas.meta; +import java.util.HashSet; import java.util.Map; import java.util.Set; @@ -10,9 +11,9 @@ import models.formulas.Formula; import models.terms.Dependency; import models.terms.RDLTerm; +import models.terms.meta.MatchConstraint; import models.terms.meta.MetaDependencyVariable; import models.terms.meta.MetaRDLTerm; -import models.terms.meta.OrderVariableConstraint; @Getter public class MetaDependencyFormula extends MetaFormula { @@ -35,13 +36,12 @@ } @Override - public boolean isMatchedBy(Formula formula, Map binding, - Map orderConstraint) { + public Set isMatchedBy(Formula formula, MatchConstraint constraint) { if (! (formula instanceof DependencyFormula)) { - return false; + return new HashSet<>(); } DependencyFormula dep = (DependencyFormula) formula; - return dependency.isMatchedBy(dep.getDependency(), binding, orderConstraint); + return dependency.isMatchedBy(dep.getDependency(), constraint); } diff --git a/src/main/java/models/formulas/meta/MetaEquationFormula.java b/src/main/java/models/formulas/meta/MetaEquationFormula.java index 7f27ff5..8c07b25 100644 --- a/src/main/java/models/formulas/meta/MetaEquationFormula.java +++ b/src/main/java/models/formulas/meta/MetaEquationFormula.java @@ -1,6 +1,8 @@ package models.formulas.meta; +import java.util.HashSet; import java.util.Map; +import java.util.Set; import exceptions.IllegalTypeException; import lombok.Getter; @@ -9,8 +11,8 @@ import models.formulas.Formula; import models.terms.EvaluatableTerm; import models.terms.RDLTerm; +import models.terms.meta.MatchConstraint; import models.terms.meta.MetaRDLTerm; -import models.terms.meta.OrderVariableConstraint; @Getter public class MetaEquationFormula extends MetaFormula { @@ -31,13 +33,14 @@ } @Override - public boolean isMatchedBy(Formula formula, Map binding, - Map orderConstraint) { + public Set isMatchedBy(Formula formula, MatchConstraint constraint) { + Set result = new HashSet<>(); if (! (formula instanceof EquationFormula)) { - return false; + return result; } EquationFormula eq = (EquationFormula) formula; - return leftSideHand.isMatchedBy(eq.getLeftSideHand(), binding, orderConstraint) && rightSideHand.isMatchedBy(eq.getRightSideHand(), binding, orderConstraint); + result = leftSideHand.isMatchedBy(eq.getLeftSideHand(), constraint); + return rightSideHand.isMatchedBy(eq.getRightSideHand(), result); } @Override diff --git a/src/main/java/models/formulas/meta/MetaFormula.java b/src/main/java/models/formulas/meta/MetaFormula.java index 6115a2b..3ce57fc 100644 --- a/src/main/java/models/formulas/meta/MetaFormula.java +++ b/src/main/java/models/formulas/meta/MetaFormula.java @@ -2,19 +2,20 @@ import java.util.HashMap; import java.util.Map; +import java.util.Set; import models.algebra.Variable; import models.formulas.Formula; import models.terms.RDLTerm; -import models.terms.meta.OrderVariableConstraint; +import models.terms.meta.MatchConstraint; public abstract class MetaFormula { - public boolean isMatchedBy(Formula formula) { - return isMatchedBy(formula, new HashMap<>(), new HashMap<>()); + public Set isMatchedBy(Formula formula) { + return isMatchedBy(formula, new MatchConstraint(new HashMap<>(), new HashMap<>())); } - public abstract boolean isMatchedBy(Formula formula, Map binding, Map orderConstraint); + public abstract Set isMatchedBy(Formula formula, MatchConstraint constraint); public abstract Formula substitution(Map binding); diff --git a/src/main/java/models/formulas/meta/MetaInFormula.java b/src/main/java/models/formulas/meta/MetaInFormula.java deleted file mode 100644 index 900faff..0000000 --- a/src/main/java/models/formulas/meta/MetaInFormula.java +++ /dev/null @@ -1,68 +0,0 @@ -package models.formulas.meta; - -import java.util.Map; - -import exceptions.IllegalTypeException; -import lombok.Getter; -import models.algebra.Variable; -import models.formulas.Formula; -import models.formulas.InFormula; -import models.terms.EvaluatableTerm; -import models.terms.RDLTerm; -import models.terms.meta.MetaRDLTerm; -import models.terms.meta.OrderVariableConstraint; - -@Getter -public class MetaInFormula extends MetaFormula { - - private MetaRDLTerm leftSideHand; - private MetaRDLTerm rightSideHand; - - public MetaInFormula(MetaRDLTerm leftSideHand, MetaRDLTerm rightSideHand) { - if (! leftSideHand.isEvaluatableTerm()) { - throw new IllegalTypeException(); - } - if(! rightSideHand.isEvaluatableTerm()) { - throw new IllegalTypeException(); - } - this.leftSideHand = leftSideHand; - this.rightSideHand = rightSideHand; - } - - @Override - public boolean isMatchedBy(Formula formula, Map binding, - Map orderConstraint) { - if (! (formula instanceof InFormula)) { - return false; - } - InFormula inFormula = (InFormula) formula; - return leftSideHand.isMatchedBy(inFormula.getLeftSideHand(), binding, orderConstraint) - && rightSideHand.isMatchedBy(inFormula.getRightSideHand(), binding, orderConstraint); - } - - @Override - public InFormula substitution(Map binding) { - return new InFormula((EvaluatableTerm) leftSideHand.substitute(binding), (EvaluatableTerm) rightSideHand.substitute(binding)); - } - - - @Override - public String toString() { - return leftSideHand.toString() + " in " + rightSideHand.toString(); - } - - @Override - public boolean equals(Object anohter) { - if (! (anohter instanceof MetaInFormula)) { - return false; - } - MetaInFormula formula = (MetaInFormula) anohter; - return leftSideHand.equals(formula.getLeftSideHand()) && rightSideHand.equals(formula.getRightSideHand()); - } - - @Override - public int hashCode() { - return toString().hashCode(); - } - -} diff --git a/src/main/java/models/terms/meta/MatchConstraint.java b/src/main/java/models/terms/meta/MatchConstraint.java new file mode 100644 index 0000000..bf0061d --- /dev/null +++ b/src/main/java/models/terms/meta/MatchConstraint.java @@ -0,0 +1,27 @@ +package models.terms.meta; +import java.util.HashMap; +import java.util.Map; + +import lombok.EqualsAndHashCode; +import lombok.RequiredArgsConstructor; +import lombok.ToString; +import models.algebra.Variable; +import models.terms.RDLTerm; + +@RequiredArgsConstructor +@EqualsAndHashCode +@ToString +public class MatchConstraint { + + private final Map binding; + private final Map orderConstraint; + + public Map getBinding() { + return new HashMap<>(binding); + } + + public Map getOrderConstraint() { + return new HashMap<>(orderConstraint); + } + +} diff --git a/src/main/java/models/terms/meta/MetaRDLTerm.java b/src/main/java/models/terms/meta/MetaRDLTerm.java index b6de276..ccdb3ea 100644 --- a/src/main/java/models/terms/meta/MetaRDLTerm.java +++ b/src/main/java/models/terms/meta/MetaRDLTerm.java @@ -4,6 +4,7 @@ import java.util.Arrays; import java.util.Collection; import java.util.HashMap; +import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Set; @@ -153,36 +154,46 @@ return false; } - public boolean isMatchedBy(RDLTerm another) { - return isMatchedBy(another, new HashMap<>(), new HashMap<>()); + public Set isMatchedBy(RDLTerm another) { + return isMatchedBy(another, new MatchConstraint(new HashMap<>(), new HashMap<>())); } - public boolean isMatchedBy(RDLTerm another, Map binding, Map orderConstraint) { + public Set isMatchedBy(RDLTerm another, Set constraints) { + Set result = new HashSet<>(); + for (MatchConstraint constraint : constraints) { + result.addAll(isMatchedBy(another, constraint)); + } + return result; + } + + public Set isMatchedBy(RDLTerm another, MatchConstraint constraint) { + Set result = new HashSet<>(); + Map binding = constraint.getBinding(); + Map orderConstraint = constraint.getOrderConstraint(); if (! another.getClass().isAssignableFrom(this.termType.getBaseTermClass())) { - return false; + return result; } if (this.getChildren().size() != another.getChildren().size()) { - return false; + return result; } if (isDependencyTerm() && (! islinearRightNormalizedMatchedBy(another))) { - return false; + return result; } if (isDependencyTerm() && !isVariable()) { RDLTerm dependingChild = (RDLTerm) this.getChild(0); RDLTerm anotherDependingChild = (RDLTerm) another.getChild(0); + Set res = new HashSet<>(); if (dependingChild instanceof MetaRDLTerm) { MetaRDLTerm metaChild = (MetaRDLTerm) dependingChild; - if (! metaChild.isMatchedBy(anotherDependingChild, binding, orderConstraint)) { - return false; - } + res = metaChild.isMatchedBy(anotherDependingChild, constraint); } else { if (!(dependingChild.equals(anotherDependingChild))) { - return false; + return result; } } for (List perm : Permutation.permutation((getChildren().size() - 1) / 2)) { - Map binding2 = new HashMap<>(binding); - Map orderConstraint2 = new HashMap<>(orderConstraint); + MatchConstraint constraint2 = new MatchConstraint(binding, orderConstraint); + Set res2 = new HashSet<>(res); boolean flg = true; for (int i = 0; i < (getChildren().size() - 1) / 2; i++) { int j = perm.get(i); @@ -192,7 +203,8 @@ RDLTerm anotherArgChild = (RDLTerm) another.getChild(i * 2 + 2); if (dependedChild instanceof MetaRDLTerm) { MetaRDLTerm metaChild = (MetaRDLTerm) dependedChild; - if (! metaChild.isMatchedBy(anotherDependedChild, binding2, orderConstraint2)) { + res2 = metaChild.isMatchedBy(anotherDependedChild, res2); + if (res2.isEmpty()) { flg = false; break; } @@ -204,7 +216,8 @@ } if (argChild instanceof MetaRDLTerm) { MetaRDLTerm metaChild = (MetaRDLTerm) argChild; - if (! metaChild.isMatchedBy(anotherArgChild, binding2, orderConstraint2)) { + res2 = metaChild.isMatchedBy(anotherArgChild, res2); + if (res2.isEmpty()) { flg = false; break; } @@ -216,32 +229,28 @@ } } if (flg) { - for (var key: binding2.keySet()) { - binding.put(key, binding2.get(key)); - } - for (var key : orderConstraint2.keySet()) { - orderConstraint.put(key, orderConstraint2.get(key)); - } - return true; + result.addAll(res2); } } - return false; + return result; } else if (isDependency() && !isVariable()) { RDLTerm dependingChild = (RDLTerm) this.getChild(0); RDLTerm anotherDependingChild = (RDLTerm) another.getChild(0); + Set res = new HashSet<>(); if (dependingChild instanceof MetaRDLTerm) { MetaRDLTerm metaChild = (MetaRDLTerm) dependingChild; - if (! metaChild.isMatchedBy(anotherDependingChild, binding, orderConstraint)) { - return false; + res = metaChild.isMatchedBy(anotherDependingChild, constraint); + if (res.isEmpty()) { + return result; } } else { if (!(dependingChild.equals(anotherDependingChild))) { - return false; + return result; } } for (List perm : Permutation.permutation(getChildren().size() - 1)) { - Map binding2 = new HashMap<>(binding); - Map orderConstraint2 = new HashMap<>(orderConstraint); + MatchConstraint constraint2 = new MatchConstraint(binding, orderConstraint); + Set res2 = new HashSet<>(res); boolean flg = true; for (int i = 0; i < getChildren().size() - 1; i++) { int j = perm.get(i); @@ -249,7 +258,8 @@ RDLTerm anotherDependedChild = (RDLTerm) another.getChild(i + 1); if (dependedChild instanceof MetaRDLTerm) { MetaRDLTerm metaChild = (MetaRDLTerm) dependedChild; - if (! metaChild.isMatchedBy(anotherDependedChild, binding2, orderConstraint2)) { + res2 = metaChild.isMatchedBy(anotherDependedChild, res2); + if (res2.isEmpty()) { flg = false; break; } @@ -261,33 +271,29 @@ } } if (flg) { - for (var key: binding2.keySet()) { - binding.put(key, binding2.get(key)); - } - for (var key : orderConstraint2.keySet()) { - orderConstraint.put(key, orderConstraint2.get(key)); - } - return true; + result.addAll(res2); } } - return false; - } else { - for (int i = 0; i < this.getChildren().size(); i++) { - RDLTerm child = (RDLTerm) this.getChild(i); - RDLTerm anotherChild = (RDLTerm) another.getChild(i); - if (child instanceof MetaRDLTerm) { - MetaRDLTerm metaChild = (MetaRDLTerm) child; - if (! metaChild.isMatchedBy(anotherChild, binding, orderConstraint)) { - return false; - } - } else { - if (!(child.equals(anotherChild))) { - return false; - } - } - } - return true; + return result; } +// } else { +// for (int i = 0; i < this.getChildren().size(); i++) { +// RDLTerm child = (RDLTerm) this.getChild(i); +// RDLTerm anotherChild = (RDLTerm) another.getChild(i); +// if (child instanceof MetaRDLTerm) { +// MetaRDLTerm metaChild = (MetaRDLTerm) child; +// if (metaChild.isMatchedBy(anotherChild, constraint).isEmpty()) { +// return result; +// } +// } else { +// if (!(child.equals(anotherChild))) { +// return result; +// } +// } +// } +// return result; +// } + return result; } private boolean dynamicMatchCheck(RDLTerm another, Map binding, Map orderConstraint) { diff --git a/src/main/java/models/terms/meta/MetaResource.java b/src/main/java/models/terms/meta/MetaResource.java index d28b163..6c58980 100644 --- a/src/main/java/models/terms/meta/MetaResource.java +++ b/src/main/java/models/terms/meta/MetaResource.java @@ -1,6 +1,8 @@ package models.terms.meta; +import java.util.HashSet; import java.util.Map; +import java.util.Set; import lombok.Getter; import models.algebra.Constant; @@ -8,8 +10,8 @@ import models.algebra.Symbol; import models.algebra.Variable; import models.terms.RDLTerm; -import models.terms.ResourceConstant; import models.terms.Resource; +import models.terms.ResourceConstant; @Getter public class MetaResource extends MetaVariable { @@ -27,24 +29,29 @@ } @Override - public boolean isMatchedBy(RDLTerm another, Map binding, - Map orderConstraint) { + public Set isMatchedBy(RDLTerm another, MatchConstraint constraint) { + Set result = new HashSet<>(); + Map binding = constraint.getBinding(); + Map orderConstraint = constraint.getOrderConstraint(); if ((! (another instanceof Resource)) && (! (another instanceof ResourceConstant))) { - return false; + return result; } if (! orderConstraintCheck(another, orderConstraint)) { - return false; + return result; } if (! islinearRightNormalizedMatchedBy(another)) { - return false; + return result; } if (! binding.containsKey(this.variableName)) { binding.put(this.variableName, another); - return true; + result.add(new MatchConstraint(binding, orderConstraint)); } - return binding.get(this.variableName).equals(another); + else if (binding.get(this.variableName).equals(another)) { + result.add(new MatchConstraint(binding, orderConstraint)); + } + return result; } } diff --git a/src/main/java/models/terms/meta/MetaVariable.java b/src/main/java/models/terms/meta/MetaVariable.java index 804f1c2..fdad533 100644 --- a/src/main/java/models/terms/meta/MetaVariable.java +++ b/src/main/java/models/terms/meta/MetaVariable.java @@ -1,7 +1,9 @@ package models.terms.meta; import java.util.HashMap; +import java.util.HashSet; import java.util.Map; +import java.util.Set; import exceptions.CoefficientNotOneException; import exceptions.SubstituteFailedException; @@ -74,25 +76,30 @@ } @Override - public boolean isMatchedBy(RDLTerm another, Map binding, - Map orderConstraint) { + public Set isMatchedBy(RDLTerm another, MatchConstraint constraint) { + Set result = new HashSet<>(); + Map binding = constraint.getBinding(); + Map orderConstraint = constraint.getOrderConstraint(); if (! this.termType.getBaseTermClass().isAssignableFrom(another.getClass())) { - return false; + return result; } if (! orderConstraintCheck(another, orderConstraint)) { - return false; + return result; } if (! islinearRightNormalizedMatchedBy(another)) { - return false; + return result; } if (! binding.containsKey(this.variableName)) { binding.put(this.variableName, another); - return true; + result.add(new MatchConstraint(binding, orderConstraint)); } - return binding.get(this.variableName).equals(another); + else if (binding.get(this.variableName).equals(another)) { + result.add(new MatchConstraint(binding, orderConstraint)); + } + return result; } @Override diff --git a/src/test/java/terms/DependencyTermTest.java b/src/test/java/terms/DependencyTermTest.java index 78d9c50..c90f686 100644 --- a/src/test/java/terms/DependencyTermTest.java +++ b/src/test/java/terms/DependencyTermTest.java @@ -6,11 +6,13 @@ import java.util.HashMap; import java.util.Map; +import java.util.Set; import models.algebra.Variable; import models.terms.DependencyTerm; import models.terms.RDLTerm; import models.terms.Resource; +import models.terms.meta.MatchConstraint; import models.terms.meta.MetaRDLTerm; import models.terms.meta.MetaResource; import models.terms.meta.OrderVariableConstraint; @@ -74,12 +76,13 @@ correctBinding.put(w.getVariableName(), b); correctBinding.put(p.getVariableName(), c); mt4.toString(); - assertTrue(mt1.isMatchedBy(t1, binding, orderConstraint)); - assertTrue(mt2.isMatchedBy(t1, binding, orderConstraint)); - assertFalse(mt3.isMatchedBy(t1, binding, orderConstraint)); - assertEquals(correctBinding, binding); - assertTrue(mt4.isMatchedBy(t2, binding, orderConstraint)); - RDLTerm t = mt1.substitute(binding); + Set tmp = mt1.isMatchedBy(t1, new MatchConstraint(binding, orderConstraint)); + assertTrue(! tmp.isEmpty()); + tmp = mt2.isMatchedBy(t1, tmp); + assertTrue(! tmp.isEmpty()); + assertFalse(! mt3.isMatchedBy(t1, tmp).isEmpty()); + assertTrue(! mt4.isMatchedBy(t2, tmp).isEmpty()); + RDLTerm t = mt1.substitute(tmp.iterator().next().getBinding()); assertEquals(t, t1); } @@ -99,8 +102,10 @@ MetaRDLTerm mt2 = new MetaRDLTerm(x, v, w, y, z); Map binding = new HashMap<>(); Map orderConstraint = new HashMap<>(); - assertTrue(mt1.isMatchedBy(t1, binding, orderConstraint)); - assertTrue(mt2.isMatchedBy(mt2, binding, orderConstraint)); + Set tmp = mt1.isMatchedBy(t1, new MatchConstraint(binding, orderConstraint)); + assertTrue(! tmp.isEmpty()); + tmp = mt2.isMatchedBy(t2, tmp); + assertTrue(! tmp.isEmpty()); } @Test diff --git a/src/test/java/terms/DependencyTest.java b/src/test/java/terms/DependencyTest.java index bc2c60e..916c3b1 100644 --- a/src/test/java/terms/DependencyTest.java +++ b/src/test/java/terms/DependencyTest.java @@ -4,6 +4,7 @@ import org.junit.jupiter.api.Test; import java.util.HashMap; +import java.util.HashSet; import java.util.Map; import java.util.Set; @@ -12,6 +13,7 @@ import models.terms.Dependency; import models.terms.RDLTerm; import models.terms.Resource; +import models.terms.meta.MatchConstraint; import models.terms.meta.MetaRDLTerm; import models.terms.meta.MetaResource; import models.terms.meta.OrderVariableConstraint; @@ -91,7 +93,6 @@ MetaRDLTerm mt2 = new MetaRDLTerm(p, Set.of(q, r, s)); MetaRDLTerm mt3 = new MetaRDLTerm(p, Set.of(r, q, s)); MetaRDLTerm mt4 = new MetaRDLTerm(p, Set.of(s, r, q)); - MetaRDLTerm mt5 = new MetaRDLTerm(p, Set.of(s, t, q)); Dependency d1 = new Dependency(a, b); Dependency d2 = new Dependency(a, b, c, f); @@ -102,15 +103,19 @@ Map binding = new HashMap<>(); Map orderConst = new HashMap<>(); - assertTrue(mt1.isMatchedBy(d1, binding, orderConst)); - assertEquals(binding.get(p.getVariableName()), a); - assertEquals(binding.get(q.getVariableName()), b); - binding.clear(); - assertTrue(mt2.isMatchedBy(d2, binding, orderConst)); - assertTrue(mt3.isMatchedBy(d2, binding, orderConst)); - assertTrue(mt4.isMatchedBy(d2, binding, orderConst)); - assertFalse(mt4.isMatchedBy(d5, binding, orderConst)); - + Set tmp = new HashSet<>(); + tmp = mt1.isMatchedBy(d1, new MatchConstraint(binding, orderConst)); + assertTrue(! tmp.isEmpty()); + assertEquals(tmp.iterator().next().getBinding().get(p.getVariableName()), a); + assertEquals(tmp.iterator().next().getBinding().get(q.getVariableName()), b); + tmp = mt2.isMatchedBy(d2, new MatchConstraint(binding, orderConst)); + assertTrue(!tmp.isEmpty()); + tmp = mt3.isMatchedBy(d2, tmp); + assertTrue(!tmp.isEmpty()); + tmp = mt4.isMatchedBy(d2, tmp); + assertTrue(!tmp.isEmpty()); + tmp = mt4.isMatchedBy(d5, tmp); + assertFalse(!tmp.isEmpty()); } }