diff --git a/build.gradle b/build.gradle index 8d931ce..ed218e2 100644 --- a/build.gradle +++ b/build.gradle @@ -17,6 +17,8 @@ // JUnit 5 testImplementation 'org.junit.jupiter:junit-jupiter:5.11.3' testRuntimeOnly 'org.junit.platform:junit-platform-launcher' + + implementation 'com.google.guava:guava:33.4.8-jre' } java { diff --git a/src/main/java/Main.java b/src/main/java/Main.java index 44d2f26..e7242df 100644 --- a/src/main/java/Main.java +++ b/src/main/java/Main.java @@ -1,3 +1,5 @@ +import com.google.common.collect.TreeMultimap; + import java.util.HashMap; import java.util.Map; @@ -14,6 +16,7 @@ public static void main(String[] args) { // sandbox(); + sandbox2(); } @@ -31,4 +34,13 @@ System.out.println(b); } + static void sandbox2() { + TreeMultimap tmp = TreeMultimap.create(); + tmp.put(1, 1); + tmp.put(1, 2); + tmp.put(1, 1); + tmp.put(1, 3); + System.out.println(tmp.get(1)); + } + } diff --git a/src/main/java/models/formulas/DependencyFormula.java b/src/main/java/models/formulas/DependencyFormula.java index 6918696..989125c 100644 --- a/src/main/java/models/formulas/DependencyFormula.java +++ b/src/main/java/models/formulas/DependencyFormula.java @@ -1,7 +1,7 @@ package models.formulas; -import java.util.Set; -import java.util.TreeSet; +import java.util.ArrayList; +import java.util.List; import lombok.Getter; import models.terms.Dependency; @@ -17,8 +17,8 @@ this.dependency = dependency; } - public DependencyFormula(RDLTerm dependingTerm, Set dependedTerms) { - this.dependency = new Dependency(dependingTerm, new TreeSet<>(dependedTerms)); + public DependencyFormula(RDLTerm dependingTerm, List dependedTerms) { + this.dependency = new Dependency(dependingTerm, new ArrayList<>(dependedTerms)); } public DependencyFormula(RDLTerm dependingTerm, EvaluatableTerm ...dependedTerms) { diff --git a/src/main/java/models/formulas/meta/MetaDependencyFormula.java b/src/main/java/models/formulas/meta/MetaDependencyFormula.java index 5dee6c4..3dce2a0 100644 --- a/src/main/java/models/formulas/meta/MetaDependencyFormula.java +++ b/src/main/java/models/formulas/meta/MetaDependencyFormula.java @@ -2,6 +2,7 @@ import java.util.Arrays; import java.util.HashSet; +import java.util.List; import java.util.Map; import java.util.Set; @@ -13,6 +14,7 @@ import models.terms.Dependency; import models.terms.RDLTerm; import models.terms.meta.MatchConstraint; +import models.terms.meta.MetaDependency; import models.terms.meta.MetaDependencyVariable; import models.terms.meta.MetaDynamicTerm; import models.terms.meta.MetaRDLTerm; @@ -34,12 +36,12 @@ this.dependency = dependency; } - public MetaDependencyFormula(MetaRDLTerm dependingTerm, Set dependedTerms) { - this.dependency = new MetaRDLTerm(dependingTerm, dependedTerms); + public MetaDependencyFormula(MetaRDLTerm dependingTerm, List dependedTerms) { + this.dependency = new MetaDependency(dependingTerm, dependedTerms); } public MetaDependencyFormula(MetaRDLTerm dependingTerm, MetaRDLTerm ...dependedTerms) { - this(dependingTerm, new HashSet<>(Arrays.asList(dependedTerms))); + this(dependingTerm, Arrays.asList(dependedTerms)); } public MetaDependencyFormula(MetaRDLTerm dependingTerm, MetaTermGenerator generator) { diff --git a/src/main/java/models/terms/Dependency.java b/src/main/java/models/terms/Dependency.java index e4d031f..21307bc 100644 --- a/src/main/java/models/terms/Dependency.java +++ b/src/main/java/models/terms/Dependency.java @@ -1,9 +1,10 @@ package models.terms; +import com.google.common.collect.TreeMultiset; + +import java.util.ArrayList; import java.util.Arrays; import java.util.List; -import java.util.Set; -import java.util.TreeSet; import java.util.stream.Collectors; import exceptions.SyntaxException; @@ -14,12 +15,12 @@ public class Dependency extends RDLTerm{ private RDLTerm dependingTerm; - private TreeSet dependedTerms; + private TreeMultiset dependedTerms; - public Dependency(RDLTerm dependingTerm, Set dependedTerms) { + public Dependency(RDLTerm dependingTerm, List dependedTerms) { super(new Symbol(":", dependedTerms.size() + 1), dependedTerms.iterator().next().getOrder(), dependingTerm.getSize() + dependedTerms.stream().mapToInt(v -> v.size).sum()); this.dependingTerm = dependingTerm; - this.dependedTerms = new TreeSet<>(dependedTerms); + this.dependedTerms = TreeMultiset.create(dependedTerms); this.addChild(dependingTerm); if (dependingTerm.getTermOrder() > getOrder()) { throw new SyntaxException("dependingTerm's order must be less than " + (getOrder() + 1) + ", but " + dependingTerm + "'s order is " + dependingTerm.getOrder()); @@ -33,11 +34,7 @@ } public Dependency(RDLTerm dependingTerm, EvaluatableTerm ...dependedTerms) { - this(dependingTerm, new TreeSet<>(Arrays.asList(dependedTerms))); - } - - public Dependency(RDLTerm dependingTerm, ListdependedTerms) { - this(dependingTerm, new TreeSet<>(dependedTerms)); + this(dependingTerm, Arrays.asList(dependedTerms)); } @Override @@ -89,7 +86,11 @@ @Override public Object clone() { - return new Dependency((RDLTerm) dependingTerm.clone(), new TreeSet<>(dependedTerms)); + List newTerms = new ArrayList<>(); + for (EvaluatableTerm term: this.dependedTerms) { + newTerms.add((EvaluatableTerm) term.clone()); + } + return new Dependency((RDLTerm) dependingTerm.clone(), newTerms); } } diff --git a/src/main/java/models/terms/DependencyTerm.java b/src/main/java/models/terms/DependencyTerm.java index 484b040..5a66e06 100644 --- a/src/main/java/models/terms/DependencyTerm.java +++ b/src/main/java/models/terms/DependencyTerm.java @@ -1,10 +1,11 @@ package models.terms; +import com.google.common.collect.TreeMultiset; + import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.TreeMap; -import java.util.stream.IntStream; import exceptions.SyntaxException; import lombok.Getter; @@ -14,7 +15,7 @@ public class DependencyTerm extends EvaluatableTerm{ private EvaluatableTerm dependingTerm; - private TreeMap termPairs; + private TreeMap> termPairs; public DependencyTerm(EvaluatableTerm dependingTerm, List terms) { @@ -27,27 +28,32 @@ throw new SyntaxException("Args size must be odd."); } this.size = dependingTerm.getSize(); - int maxArgOrder = IntStream.range(0, terms.size()).filter(i -> i % 2 == 1).map(i -> terms.get(i).getOrder()).max().orElse(0); - int maxDependedOrder = IntStream.range(0, terms.size()).filter(i -> i % 2 == 0).map(i -> terms.get(i).getOrder()).max().orElse(0); - boolean argOrderType = maxDependedOrder <= maxArgOrder; - if (argOrderType) { - this.order = maxArgOrder; - } else { - this.order = maxDependedOrder - 1; - } + int dependedOrder = terms.get(0).getOrder(); + int maxArgOrder = 0; this.dependingTerm = dependingTerm; this.termPairs = new TreeMap<>(); addChild(dependingTerm); for (int i = 0; i < terms.size() / 2; i++) { EvaluatableTerm dependedTerm = terms.get(2 * i); EvaluatableTerm argTerm = terms.get(2 * i + 1); - termPairs.put(dependedTerm, argTerm); + if (dependedTerm.getOrder() != dependedOrder) { + throw new SyntaxException("depended term's order not same"); + } + maxArgOrder = Math.max(maxArgOrder, argTerm.getOrder()); + termPairs.computeIfAbsent(dependedTerm, k -> TreeMultiset.create()).add(argTerm); this.size += dependedTerm.getSize(); this.size += argTerm.getSize(); } + if (dependedOrder <= maxArgOrder) { + this.order = maxArgOrder; + } else { + this.order = dependedOrder - 1; + } for (EvaluatableTerm dependedTerm : termPairs.keySet()) { - addChild(dependedTerm); - addChild(termPairs.get(dependedTerm)); + for (EvaluatableTerm argTerm : termPairs.get(dependedTerm)) { + addChild(dependedTerm); + addChild(argTerm); + } } } @@ -80,7 +86,11 @@ } public List getArgumentTerms() { - return new ArrayList<>(termPairs.values()); + List result = new ArrayList<>(); + for (TreeMultiset terms: termPairs.values()) { + result.addAll(terms); + } + return result; } @Override @@ -90,11 +100,12 @@ sb.append(getDependingTerm().toString()); sb.append(" : "); for (EvaluatableTerm dependedTerm: termPairs.keySet()) { - EvaluatableTerm argTerm = termPairs.get(dependedTerm); - sb.append(dependedTerm.toString()); - sb.append(" -> "); - sb.append(argTerm.toString()); - sb.append(", "); + for (EvaluatableTerm argTerm: termPairs.get(dependedTerm)) { + sb.append(dependedTerm.toString()); + sb.append(" -> "); + sb.append(argTerm.toString()); + sb.append(", "); + } } sb.deleteCharAt(sb.length() - 1); sb.deleteCharAt(sb.length() - 1); @@ -109,11 +120,12 @@ sb.append(getDependingTerm().toStringWithOrder()); sb.append(" : "); for (EvaluatableTerm dependedTerm: termPairs.keySet()) { - EvaluatableTerm argTerm = termPairs.get(dependedTerm); - sb.append(dependedTerm.toStringWithOrder()); - sb.append(" -> "); - sb.append(argTerm.toStringWithOrder()); - sb.append(", "); + for (EvaluatableTerm argTerm : termPairs.get(dependedTerm)) { + sb.append(dependedTerm.toStringWithOrder()); + sb.append(" -> "); + sb.append(argTerm.toStringWithOrder()); + sb.append(", "); + } } sb.deleteCharAt(sb.length() - 1); sb.deleteCharAt(sb.length() - 1); @@ -144,8 +156,10 @@ public Object clone() { List termPairs = new ArrayList<>(); for (EvaluatableTerm dependedTerm : this.termPairs.keySet()) { - termPairs.add(dependedTerm); - termPairs.add(this.termPairs.get(dependedTerm)); + for (EvaluatableTerm argTerm: this.termPairs.get(dependedTerm)) { + termPairs.add((EvaluatableTerm) dependedTerm.clone()); + termPairs.add((EvaluatableTerm) argTerm.clone()); + } } return new DependencyTerm( (EvaluatableTerm) dependingTerm.clone(), diff --git a/src/main/java/models/terms/meta/MetaDependency.java b/src/main/java/models/terms/meta/MetaDependency.java new file mode 100644 index 0000000..fba6677 --- /dev/null +++ b/src/main/java/models/terms/meta/MetaDependency.java @@ -0,0 +1,117 @@ +package models.terms.meta; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Set; + +import exceptions.SubstituteFailedException; +import exceptions.SyntaxException; +import models.algebra.Symbol; +import models.algebra.Variable; +import models.terms.Dependency; +import models.terms.EvaluatableTerm; +import models.terms.RDLTerm; +import utils.Permutation; + +public class MetaDependency extends MetaRDLTerm{ + + public MetaDependency(RDLTerm dependingTerm, List dependedTerms) { + super(new Symbol(":", -1), TermType.META_DEPENDENCY, -1); + int size = dependingTerm.getSize(); + addChild(dependingTerm); + for(RDLTerm term : dependedTerms.stream().sorted().toList()) { + addChild(term); + size += term.getSize(); + } + this.size = size; + } + + public MetaDependency(RDLTerm dependingTerm, RDLTerm ...dependedTerms) { + this(dependingTerm, Arrays.asList(dependedTerms)); + } + + @Override + protected Set isMatchedBy(RDLTerm another, MatchConstraint constraint, int depth) { + Set result = new HashSet<>(); + if (! another.getClass().isAssignableFrom(this.termType.getBaseTermClass())) { + return result; + } + if (isDependencyTerm() && (! islinearRightNormalizedMatchedBy(another))) { + return result; + } + result = dependingTermMatch(another, constraint, depth); + return dependedTermsMatch(another, result, depth); + } + + private Set dependingTermMatch(RDLTerm another, MatchConstraint constraint, int depth) { + RDLTerm dependingChild = (RDLTerm) this.getChild(0); + RDLTerm anotherDependingChild = (RDLTerm) another.getChild(0); + if (dependingChild instanceof MetaRDLTerm) { + MetaRDLTerm metaChild = (MetaRDLTerm) dependingChild; + return metaChild.isMatchedBy(anotherDependingChild, constraint, depth + 1); + } else { + if (!(dependingChild.equals(anotherDependingChild))) { + return new HashSet<>(); + } + } + return new HashSet<>(); + } + + private Set dependedTermsMatch(RDLTerm another, Set constraint, int depth) { + Set result = new HashSet<>(); + for (List perm : Permutation.permutation(another.getChildren().size() - 1)) { + Set localResult = new HashSet<>(constraint); + boolean flg = true; + for (int metaTermIndex = 0; metaTermIndex < perm.size(); metaTermIndex++) { + int anotherTermIndex = perm.get(metaTermIndex); + RDLTerm metaDependedTerm = (RDLTerm) getChild(metaTermIndex + 1); + RDLTerm anotherDependedTerm = (RDLTerm) another.getChild(anotherTermIndex + 1); + if (metaDependedTerm instanceof MetaRDLTerm metaTerm) { + localResult = metaTerm.isMatchedBy(anotherDependedTerm, localResult, depth + 1); + if (localResult.isEmpty()) { + flg = false; + break; + } + } else { + if (!(metaDependedTerm.equals(anotherDependedTerm))) { + flg = false; + break; + } + } + } + if (flg) { + result.addAll(localResult); + } + } + return result; + } + + @Override + protected RDLTerm substitute(Map binding, int depth) { + RDLTerm dependingTerm = (RDLTerm) getChild(0); + if (dependingTerm instanceof MetaRDLTerm) { + dependingTerm = ((MetaRDLTerm) dependingTerm).substitute(binding, depth + 1); + } + List dependedTerms = new ArrayList<>(); + for (int i = 1; i < getChildren().size(); i++) { + RDLTerm dependedTerm = (RDLTerm) getChild(i); + if (dependedTerm instanceof MetaRDLTerm metaTerm) { + dependedTerm = metaTerm.substitute(binding, depth + 1); + } + if (dependedTerm instanceof EvaluatableTerm te) { + dependedTerms.add(te); + } else { + throw new SubstituteFailedException("Syntax error"); + } + } + try { + return new Dependency(dependingTerm, dependedTerms); + } catch (SyntaxException e) { + throw new SubstituteFailedException(e.getMessage()); + } + } + +} diff --git a/src/main/java/models/terms/meta/MetaDependencyTerm.java b/src/main/java/models/terms/meta/MetaDependencyTerm.java new file mode 100644 index 0000000..7b3f30e --- /dev/null +++ b/src/main/java/models/terms/meta/MetaDependencyTerm.java @@ -0,0 +1,145 @@ +package models.terms.meta; + +import com.google.common.collect.TreeMultiset; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Set; +import java.util.TreeMap; + +import exceptions.SubstituteFailedException; +import exceptions.SyntaxException; +import models.algebra.Symbol; +import models.algebra.Variable; +import models.terms.DependencyTerm; +import models.terms.EvaluatableTerm; +import models.terms.RDLTerm; +import utils.Permutation; + +public class MetaDependencyTerm extends MetaRDLTerm{ + + public MetaDependencyTerm(RDLTerm dependingTerm, List terms) { + super(new Symbol(":", -1), TermType.META_DEPENDENCY_TERM, -1); + TreeMap> sortedMap = new TreeMap<>(); + addChild(dependingTerm); + int size = dependingTerm.getSize(); + for (int i = 0; i < terms.size() / 2; i++) { + RDLTerm dependedTerm = terms.get(i * 2); + RDLTerm argTerm = terms.get(i * 2 + 1); + sortedMap.computeIfAbsent(dependedTerm, k -> TreeMultiset.create()).add(argTerm); + } + for (RDLTerm dependedTerm: sortedMap.keySet()) { + for (RDLTerm argTerm: sortedMap.get(dependedTerm)) { + addChild(dependedTerm); + addChild(argTerm); + size += dependedTerm.getSize(); + size += argTerm.getSize(); + } + } + this.size = size; + } + + public MetaDependencyTerm(RDLTerm dependingTerm, RDLTerm ...terms) { + this(dependingTerm, Arrays.asList(terms)); + } + + @Override + protected Set isMatchedBy(RDLTerm another, MatchConstraint constraint, int depth) { + Set result = new HashSet<>(); + if (! another.getClass().isAssignableFrom(this.termType.getBaseTermClass())) { + return result; + } + if (isDependencyTerm() && (! islinearRightNormalizedMatchedBy(another))) { + return result; + } + result = dependingTermMatch(another, constraint, depth); + return termPairsMatch(another, result, depth); + } + + private Set dependingTermMatch(RDLTerm another, MatchConstraint constraint, int depth) { + RDLTerm dependingChild = (RDLTerm) this.getChild(0); + RDLTerm anotherDependingChild = (RDLTerm) another.getChild(0); + if (dependingChild instanceof MetaRDLTerm) { + MetaRDLTerm metaChild = (MetaRDLTerm) dependingChild; + return metaChild.isMatchedBy(anotherDependingChild, constraint, depth + 1); + } else { + if (!(dependingChild.equals(anotherDependingChild))) { + return new HashSet<>(); + } + } + return new HashSet<>(); + } + + private Set termPairsMatch(RDLTerm another, Set constraint, int depth) { + Set result = new HashSet<>(); + for (List perm : Permutation.permutation((another.getChildren().size() - 1) / 2)) { + Set localResult = new HashSet<>(constraint); + boolean flg = true; + for (int metaTermIndex = 0; metaTermIndex < perm.size(); metaTermIndex++) { + int anotherTermIndex = perm.get(metaTermIndex); + RDLTerm metaDependedTerm = (RDLTerm) getChild(2 * metaTermIndex + 1); + RDLTerm anotherDependedTerm = (RDLTerm) another.getChild(2 * anotherTermIndex + 1); + RDLTerm metaArgTerm = (RDLTerm) getChild(2 * metaTermIndex + 2); + RDLTerm anotherArgTerm = (RDLTerm) another.getChild(2 * anotherTermIndex + 2); + if (metaDependedTerm instanceof MetaRDLTerm metaTerm) { + localResult = metaTerm.isMatchedBy(anotherDependedTerm, localResult, depth + 1); + if (localResult.isEmpty()) { + flg = false; + break; + } + } else { + if (!(metaDependedTerm.equals(anotherDependedTerm))) { + flg = false; + break; + } + } + if (metaArgTerm instanceof MetaRDLTerm metaTerm) { + localResult = metaTerm.isMatchedBy(anotherArgTerm, localResult, depth + 1); + if (localResult.isEmpty()) { + flg = false; + break; + } + } else { + if (!(metaArgTerm.equals(anotherArgTerm))) { + flg = false; + break; + } + } + } + if (flg) { + result.addAll(localResult); + } + } + return result; + } + + @Override + protected RDLTerm substitute(Map binding, int depth) { + RDLTerm dependingTerm = (RDLTerm) getChild(0); + if (dependingTerm instanceof MetaRDLTerm) { + dependingTerm = ((MetaRDLTerm) dependingTerm).substitute(binding, depth + 1); + } + List termPairs = new ArrayList<>(); + for (int i = 0; i < (getChildren().size() - 1) / 2; i++) { + RDLTerm dependedTerm = (RDLTerm) getChild(i * 2 + 1); + RDLTerm argTerm = (RDLTerm) getChild(i * 2 + 2); + if (dependedTerm instanceof MetaRDLTerm metaTerm) { + dependedTerm = metaTerm.substitute(binding, depth + 1); + } + if (argTerm instanceof MetaRDLTerm metaTerm) { + argTerm = metaTerm.substitute(binding, depth + 1); + } + termPairs.add((EvaluatableTerm) dependedTerm); + termPairs.add((EvaluatableTerm) argTerm); + } + try { + return new DependencyTerm((EvaluatableTerm) dependingTerm, termPairs); + } catch (SyntaxException e) { + throw new SubstituteFailedException(e.getMessage()); + } + } + +} diff --git a/src/main/java/models/terms/meta/MetaDynamicTerm.java b/src/main/java/models/terms/meta/MetaDynamicTerm.java index 2bfa5f1..505beb0 100644 --- a/src/main/java/models/terms/meta/MetaDynamicTerm.java +++ b/src/main/java/models/terms/meta/MetaDynamicTerm.java @@ -1,11 +1,12 @@ package models.terms.meta; +import com.google.common.collect.TreeMultiset; + import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Set; -import java.util.TreeSet; import models.algebra.Symbol; import models.algebra.Variable; @@ -89,7 +90,7 @@ Set result = new HashSet<>(); Set tmpRes = new HashSet<>(); RDLTerm anotherDependingTerm = another.getDependingTerm(); - TreeSet anotherDependedTerms = another.getDependedTerms(); + TreeMultiset anotherDependedTerms = another.getDependedTerms(); boolean isLast = anotherDependingTerm instanceof Resource || anotherDependingTerm instanceof ResourceConstant; MetaRDLTerm metaDependingTerm = dependingTermGenerator.generate(0, depth, isLast); tmpRes = metaDependingTerm.isMatchedBy(anotherDependingTerm, constraint, depth + 1); @@ -162,31 +163,31 @@ MetaRDLTerm dependingTerm = dependingTermGenerator.generate(0, depth, depth == maxRecursion - 1); MetaRDLTerm dependedTerm = dependedTermGenerator.generate(0, depth, depth == maxRecursion - 1); if (depth == maxRecursion - 1) { - return new MetaRDLTerm(dependingTerm, dependedTerm); + return new MetaDependency(dependingTerm, dependedTerm); } if (dependingTerm instanceof MetaDynamicTerm generator) { - return new MetaRDLTerm(generator.dependencyRecursionGenerate(maxRecursion, depth + 1), dependedTerm); + return new MetaDependency(generator.dependencyRecursionGenerate(maxRecursion, depth + 1), dependedTerm); } else if (dependedTerm instanceof MetaDynamicTerm generator) { - return new MetaRDLTerm(dependedTerm, generator.dependencyRecursionGenerate(maxRecursion, depth + 1)); + return new MetaDependency(dependedTerm, generator.dependencyRecursionGenerate(maxRecursion, depth + 1)); } return null; } private MetaRDLTerm dependencyRecursionGenerate(Map binding, int maxRecursion, int depth) { MetaRDLTerm dependingTerm = dependingTermGenerator.generate(0, depth, depth == maxRecursion - 1); - Set dependedTerms = new HashSet<>(); + List dependedTerms = new ArrayList<>(); MetaRDLTerm dependedTerm = dependedTermGenerator.generate(0, depth, depth == maxRecursion - 1); dependedTerms.add(dependedTerm); for (int i = 0; i < searchMaxTermIndex(binding, depth, depth == maxRecursion - 1); i++) { dependedTerms.add(dependedTermGenerator.generate(i + 1, depth, depth == maxRecursion - 1)); } if (depth == maxRecursion - 1) { - return new MetaRDLTerm(dependingTerm, dependedTerms); + return new MetaDependency(dependingTerm, dependedTerms); } if (dependingTerm instanceof MetaDynamicTerm generator) { - return new MetaRDLTerm(generator.dependencyRecursionGenerate(binding, maxRecursion, depth + 1), dependedTerms); + return new MetaDependency(generator.dependencyRecursionGenerate(binding, maxRecursion, depth + 1), dependedTerms); } else if (dependedTerm instanceof MetaDynamicTerm generator) { - return new MetaRDLTerm(dependedTerm, generator.dependencyRecursionGenerate(binding, maxRecursion, depth + 1)); + return new MetaDependency(dependedTerm, generator.dependencyRecursionGenerate(binding, maxRecursion, depth + 1)); } return null; } @@ -197,14 +198,14 @@ MetaRDLTerm dependedTerm = termPair.dependedTerm(); MetaRDLTerm argTerm = termPair.argTerm(); if (depth == maxRecursion - 1) { - return new MetaRDLTerm(dependingTerm, dependedTerm, argTerm); + return new MetaDependencyTerm(dependingTerm, dependedTerm, argTerm); } if (dependingTerm instanceof MetaDynamicTerm generator) { - return new MetaRDLTerm(generator.dependencyTermRecursionGenerate(maxRecursion, depth + 1), dependedTerm, argTerm); + return new MetaDependencyTerm(generator.dependencyTermRecursionGenerate(maxRecursion, depth + 1), dependedTerm, argTerm); } else if (dependedTerm instanceof MetaDynamicTerm generator) { - return new MetaRDLTerm(dependedTerm, generator.dependencyTermRecursionGenerate(maxRecursion, depth + 1), argTerm); + return new MetaDependencyTerm(dependedTerm, generator.dependencyTermRecursionGenerate(maxRecursion, depth + 1), argTerm); } else if (argTerm instanceof MetaDynamicTerm generator) { - return new MetaRDLTerm(dependedTerm, dependedTerm, generator.dependencyTermRecursionGenerate(maxRecursion, depth + 1)); + return new MetaDependencyTerm(dependedTerm, dependedTerm, generator.dependencyTermRecursionGenerate(maxRecursion, depth + 1)); } return null; } @@ -221,7 +222,7 @@ termPairs.add(pair.argTerm()); } if (depth == maxRecursion - 1) { - return new MetaRDLTerm(dependingTerm, termPairs); + return new MetaDependencyTerm(dependingTerm, termPairs); } List resTerms = new ArrayList<>(); for (MetaRDLTerm term : termPairs) { @@ -232,9 +233,9 @@ } } if (dependingTerm instanceof MetaDynamicTerm generator) { - return new MetaRDLTerm(generator.dependencyTermRecursionGenerate(binding, maxRecursion, depth + 1), resTerms); + return new MetaDependencyTerm(generator.dependencyTermRecursionGenerate(binding, maxRecursion, depth + 1), resTerms); } - return new MetaRDLTerm(dependingTerm, resTerms); + return new MetaDependencyTerm(dependingTerm, resTerms); } private int searchMaxTermIndex(Map binding, int depth, boolean isLast) { diff --git a/src/main/java/models/terms/meta/MetaRDLTerm.java b/src/main/java/models/terms/meta/MetaRDLTerm.java index c981362..9ceb9f4 100644 --- a/src/main/java/models/terms/meta/MetaRDLTerm.java +++ b/src/main/java/models/terms/meta/MetaRDLTerm.java @@ -1,20 +1,12 @@ package models.terms.meta; -import java.util.ArrayList; -import java.util.Arrays; import java.util.Collection; import java.util.HashSet; -import java.util.List; import java.util.Map; import java.util.Set; -import java.util.TreeMap; -import java.util.TreeSet; import java.util.stream.Collectors; import java.util.stream.IntStream; -import exceptions.IllegalTypeException; -import exceptions.SubstituteFailedException; -import exceptions.SyntaxException; import lombok.Getter; import models.algebra.Expression; import models.algebra.Symbol; @@ -25,9 +17,8 @@ import models.terms.LinearRightNormalizedType; import models.terms.RDLTerm; import models.terms.Resource; -import utils.Permutation; @Getter -public class MetaRDLTerm extends RDLTerm { +public abstract class MetaRDLTerm extends RDLTerm { protected TermType termType; protected LinearRightNormalizedType linearRightNormalizedType = LinearRightNormalizedType.UNDEFINED; @@ -35,120 +26,11 @@ protected MetaRDLTerm(Symbol symbol, TermType termType, int size) { super(symbol, -1, size); this.termType = termType; - if (isResourceVariable()) { + if (isResource()) { linearRightNormalizedType = LinearRightNormalizedType.LINEAR_RIGHT_NORMALIZED; } } - //dependency - public MetaRDLTerm(MetaRDLTerm dependingTerm, Set dependedTerms) { - super(new Symbol(":", 1 + dependedTerms.size()), -1, -1); - int size = dependingTerm.getSize(); - addChild(dependingTerm); - for (MetaRDLTerm dependedTerm: new TreeSet<>(dependedTerms)) { - addChild(dependedTerm); - size += dependedTerm.getSize(); - } - this.size = size; - this.termType = TermType.META_DEPENDENCY; - } - - public MetaRDLTerm(MetaRDLTerm dependingTerm, MetaRDLTerm dependedTerm) { - this(dependingTerm, new TreeSet<>(Set.of(dependedTerm))); - } - - //dependency term - public MetaRDLTerm(MetaRDLTerm dependingTerm, List terms) { - super(new Symbol(":", terms.size() + 1), -1, -1); - if (! EvaluatableTerm.class.isAssignableFrom(dependingTerm.getTermType().getBaseTermClass())) { - throw new IllegalTypeException(); - } - if (terms.size() % 2 != 0) { - throw new SyntaxException(""); - } - int size = dependingTerm.getSize(); - addChild(dependingTerm); - TreeMap sortedTerms = new TreeMap<>(); - for (int i = 0; i < terms.size() / 2; i++) { - MetaRDLTerm dependedTerm = terms.get(2 * i); - MetaRDLTerm argTerm = terms.get(2 * i + 1); - size += dependedTerm.getSize(); - size += argTerm.getSize(); - if (! EvaluatableTerm.class.isAssignableFrom(dependedTerm.getTermType().getBaseTermClass())) { - throw new IllegalTypeException(); - } - if (! EvaluatableTerm.class.isAssignableFrom(argTerm.getTermType().getBaseTermClass())) { - throw new IllegalTypeException(); - } - sortedTerms.put(dependedTerm, argTerm); - } - this.size = size; - for (MetaRDLTerm dependedTerm: sortedTerms.keySet()) { - MetaRDLTerm argTerm = sortedTerms.get(dependedTerm); - addChild(dependedTerm); - addChild(argTerm); - } - this.termType = TermType.META_DEPENDENCY_TERM; - } - - public MetaRDLTerm(MetaRDLTerm dependingTerm, MetaRDLTerm ...terms) { - this(dependingTerm, Arrays.asList(terms)); - } - - public RDLTerm substitute(Map binding) { - return substitute(binding, 0); - } - - protected RDLTerm substitute(Map binding, int depth) { - RDLTerm dependingTerm = (RDLTerm) getChild(0); - if (dependingTerm instanceof MetaRDLTerm) { - dependingTerm = ((MetaRDLTerm) dependingTerm).substitute(binding, depth + 1); - } - if (isDependency()) { - List dependedTerms = new ArrayList<>(); - for (int i = 1; i < getChildren().size(); i++) { - RDLTerm dependedTerm = (RDLTerm) getChild(i); - if (dependedTerm instanceof MetaRDLTerm metaTerm) { - dependedTerm = metaTerm.substitute(binding, depth + 1); - } - if (dependedTerm instanceof EvaluatableTerm te) { - dependedTerms.add(te); - } else { - throw new SubstituteFailedException("Syntax error"); - } - } - try { - return new Dependency(dependingTerm, dependedTerms); - } catch (SyntaxException e) { - throw new SubstituteFailedException(e.getMessage()); - } - } - else if (isDependencyTerm()) { - List termPairs = new ArrayList<>(); - for (int i = 0; i < (getChildren().size() - 1) / 2; i++) { - RDLTerm dependedTerm = (RDLTerm) getChild(i * 2 + 1); - RDLTerm argTerm = (RDLTerm) getChild(i * 2 + 2); - if (dependedTerm instanceof MetaRDLTerm metaTerm) { - dependedTerm = metaTerm.substitute(binding, depth + 1); - } - if (argTerm instanceof MetaRDLTerm metaTerm) { - argTerm = metaTerm.substitute(binding, depth + 1); - } - termPairs.add((EvaluatableTerm) dependedTerm); - termPairs.add((EvaluatableTerm) argTerm); - } - try { - return new DependencyTerm((EvaluatableTerm) dependingTerm, termPairs); - } catch (SyntaxException e) { - throw new SubstituteFailedException(e.getMessage()); - } - } - throw new SubstituteFailedException(); - } - - public boolean isVariable() { - return false; - } public Set isMatchedBy(RDLTerm another) { return isMatchedBy(another, MatchConstraint.createDefault(), 0); @@ -170,109 +52,24 @@ return result; } - protected Set isMatchedBy(RDLTerm another, MatchConstraint constraint, int depth) { - Set result = new HashSet<>(); - if (! another.getClass().isAssignableFrom(this.termType.getBaseTermClass())) { - return result; - } - if (isDependencyTerm() && (! islinearRightNormalizedMatchedBy(another))) { - return result; - } - RDLTerm dependingChild = (RDLTerm) this.getChild(0); - RDLTerm anotherDependingChild = (RDLTerm) another.getChild(0); - Set res = new HashSet<>(); - if (dependingChild instanceof MetaRDLTerm) { - MetaRDLTerm metaChild = (MetaRDLTerm) dependingChild; - result = metaChild.isMatchedBy(anotherDependingChild, constraint, depth + 1); - } else { - if (!(dependingChild.equals(anotherDependingChild))) { - return result; - } - } - if (isDependencyTerm()) { - return dependencyTermMatch(another, result, depth); - } else if (isDependency()) { - return dependencyMatch(another, result, depth); - } - return result; + abstract protected Set isMatchedBy(RDLTerm another, MatchConstraint constraint, int depth); + + + public RDLTerm substitute(Map binding) { + return substitute(binding, 0); } - private Set dependencyMatch(RDLTerm another, Set constraint, int depth) { - Set result = new HashSet<>(); - for (List perm : Permutation.permutation(another.getChildren().size() - 1)) { - Set localResult = new HashSet<>(constraint); - boolean flg = true; - for (int metaTermIndex = 0; metaTermIndex < perm.size(); metaTermIndex++) { - int anotherTermIndex = perm.get(metaTermIndex); - RDLTerm metaDependedTerm = (RDLTerm) getChild(metaTermIndex + 1); - RDLTerm anotherDependedTerm = (RDLTerm) another.getChild(anotherTermIndex + 1); - if (metaDependedTerm instanceof MetaRDLTerm metaTerm) { - localResult = metaTerm.isMatchedBy(anotherDependedTerm, localResult, depth + 1); - if (localResult.isEmpty()) { - flg = false; - break; - } - } else { - if (!(metaDependedTerm.equals(anotherDependedTerm))) { - flg = false; - break; - } - } - } - if (flg) { - result.addAll(localResult); - } - } - return result; - } + abstract protected RDLTerm substitute(Map binding, int depth); - private Set dependencyTermMatch(RDLTerm another, Set constraint, int depth) { - Set result = new HashSet<>(); - for (List perm : Permutation.permutation((another.getChildren().size() - 1) / 2)) { - Set localResult = new HashSet<>(constraint); - boolean flg = true;; - for (int metaTermIndex = 0; metaTermIndex < perm.size(); metaTermIndex++) { - int anotherTermIndex = perm.get(metaTermIndex); - RDLTerm metaDependedTerm = (RDLTerm) getChild(2 * metaTermIndex + 1); - RDLTerm anotherDependedTerm = (RDLTerm) another.getChild(2 * anotherTermIndex + 1); - RDLTerm metaArgTerm = (RDLTerm) getChild(2 * metaTermIndex + 2); - RDLTerm anotherArgTerm = (RDLTerm) another.getChild(2 * anotherTermIndex + 2); - if (metaDependedTerm instanceof MetaRDLTerm metaTerm) { - localResult = metaTerm.isMatchedBy(anotherDependedTerm, localResult, depth + 1); - if (localResult.isEmpty()) { - flg = false; - break; - } - } else { - if (!(metaDependedTerm.equals(anotherDependedTerm))) { - flg = false; - break; - } - } - if (metaArgTerm instanceof MetaRDLTerm metaTerm) { - localResult = metaTerm.isMatchedBy(anotherArgTerm, localResult, depth + 1); - if (localResult.isEmpty()) { - flg = false; - break; - } - } else { - if (!(metaArgTerm.equals(anotherArgTerm))) { - flg = false; - break; - } - } - } - if (flg) { - result.addAll(localResult); - } - } - return result; - } public boolean checkTermType(Class clazz) { return clazz.isAssignableFrom(termType.getBaseTermClass()); } + public boolean isVariable() { + return false; + } + public boolean isDependency() { return checkTermType(Dependency.class); } @@ -285,7 +82,7 @@ return checkTermType(DependencyTerm.class); } - public boolean isResourceVariable() { + public boolean isResource() { return checkTermType(Resource.class); } diff --git a/src/test/java/formulas/meta/MetaEquationFormulaTest.java b/src/test/java/formulas/meta/MetaEquationFormulaTest.java index 7bb19eb..8dc1890 100644 --- a/src/test/java/formulas/meta/MetaEquationFormulaTest.java +++ b/src/test/java/formulas/meta/MetaEquationFormulaTest.java @@ -14,6 +14,8 @@ import models.terms.DependencyTerm; import models.terms.EvaluatableTerm; import models.terms.Resource; +import models.terms.meta.MetaDependency; +import models.terms.meta.MetaDependencyTerm; import models.terms.meta.MetaEvaluatableTermVariable; import models.terms.meta.MetaRDLTerm; import models.terms.meta.MetaResource; @@ -36,8 +38,8 @@ MetaResource v = new MetaResource(new Variable("v")); MetaEvaluatableTermVariable te = new MetaEvaluatableTermVariable(new Variable("te")); MetaEvaluatableTermVariable ue = new MetaEvaluatableTermVariable(new Variable("ue")); - MetaRDLTerm left = new MetaRDLTerm(se, v, te); - MetaRDLTerm right = new MetaRDLTerm(se, v, ue); + MetaRDLTerm left = new MetaDependencyTerm(se, v, te); + MetaRDLTerm right = new MetaDependencyTerm(se, v, ue); MetaEquationFormula metaFormula = new MetaEquationFormula(left, right); // [a : b -> c] = [a : b -> d] matches [se : v -> te] = [se : v -> ue] @@ -57,7 +59,7 @@ MetaEvaluatableTermVariable te = new MetaEvaluatableTermVariable(new Variable("te")); MetaResource w = new MetaResource(new Variable("w")); - MetaRDLTerm dep = new MetaRDLTerm(te, w); + MetaRDLTerm dep = new MetaDependency(te, w); MetaDependencyFormula metaDepF = new MetaDependencyFormula(dep); //[a : b -> c] : d matches te : w diff --git a/src/test/java/terms/DependencyTermTest.java b/src/test/java/terms/DependencyTermTest.java index e3542e6..7786338 100644 --- a/src/test/java/terms/DependencyTermTest.java +++ b/src/test/java/terms/DependencyTermTest.java @@ -4,21 +4,9 @@ import org.junit.jupiter.api.Test; -import java.util.HashMap; -import java.util.Map; -import java.util.Set; - -import models.algebra.Variable; +import exceptions.SyntaxException; import models.terms.DependencyTerm; -import models.terms.RDLTerm; import models.terms.Resource; -import models.terms.meta.MatchConstraint; -import models.terms.meta.MetaDynamicTerm; -import models.terms.meta.MetaRDLTerm; -import models.terms.meta.MetaResource; -import models.terms.meta.MetaTermPairGenerator; -import models.terms.meta.MetaTermPairGenerator.TermPair; -import models.terms.meta.OrderVariableConstraint; import utils.Utils; public class DependencyTermTest { @@ -30,6 +18,10 @@ Resource e = new Resource("e", Utils.INT, 1); Resource f = new Resource("f", Utils.INT, 1); Resource g = new Resource("g", Utils.INT, 1); + Resource h = new Resource("h", Utils.INT, 2); + Resource i = new Resource("i", Utils.INT, 2); + Resource j = new Resource("j", Utils.INT, 2); + Resource k = new Resource("k", Utils.INT, 2); @Test void EqualsTest() { @@ -37,142 +29,53 @@ DependencyTerm t2 = new DependencyTerm(a, b, c); assertEquals(t1, t2); - DependencyTerm t3 = new DependencyTerm(a, b, c, b, c); - assertEquals(t1, t3); + DependencyTerm t3 = new DependencyTerm(a, b, c, d, e); + assertNotEquals(t1, t3); - DependencyTerm t4 = new DependencyTerm(a, c, b); - assertFalse(t1.equals(t4)); + DependencyTerm t4 = new DependencyTerm(a, d, e, b, c); + assertEquals(t3, t4); - DependencyTerm t5 = new DependencyTerm(a, b, c, d, e); - DependencyTerm t6 = new DependencyTerm(a, d, e, b, c); - DependencyTerm t7 = new DependencyTerm(a, b, e, d, c); - assertEquals(t5, t6); - assertFalse(t5.equals(t7)); + DependencyTerm t5 = new DependencyTerm(a, b, c, b, c); + assertNotEquals(t1, t5); - DependencyTerm t8 = new DependencyTerm(t1, t5, t6); - DependencyTerm t9 = new DependencyTerm(t1, t6, t5); - assertEquals(t8, t9); - - } - - @Test - void MatchTest() { - DependencyTerm t1 = new DependencyTerm(a, b, c, d, e); - DependencyTerm t2 = new DependencyTerm(a, g, f, b, c); - MetaResource x = new MetaResource(new Variable("x")); - MetaResource y = new MetaResource(new Variable("y")); - MetaResource z = new MetaResource(new Variable("z")); - MetaResource w = new MetaResource(new Variable("w")); - MetaResource p = new MetaResource(new Variable("p")); - MetaResource o = new MetaResource(new Variable("o")); - MetaResource n = new MetaResource(new Variable("n")); - MetaRDLTerm mt1 = new MetaRDLTerm(x, y, z, w, p); - MetaRDLTerm mt2 = new MetaRDLTerm(x, w, p, y, z); - MetaRDLTerm mt3 = new MetaRDLTerm(x, p, w, y, z); - MetaRDLTerm mt4 = new MetaRDLTerm(x, n, o, w, p); - Map binding = new HashMap<>(); - Map orderConstraint = new HashMap<>(); - Map correctBinding = new HashMap<>(); - correctBinding.put(x.getVariableName(), a); - correctBinding.put(y.getVariableName(), d); - correctBinding.put(z.getVariableName(), e); - correctBinding.put(w.getVariableName(), b); - correctBinding.put(p.getVariableName(), c); - mt4.toString(); - 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); - } - - @Test - void MatchTest2() { - MetaResource x = new MetaResource(new Variable("x")); - MetaResource y = new MetaResource(new Variable("y")); - MetaResource z = new MetaResource(new Variable("z")); - MetaResource v = new MetaResource(new Variable("v")); - MetaResource w = new MetaResource(new Variable("w")); - MetaResource p = new MetaResource(new Variable("p")); - MetaResource q = new MetaResource(new Variable("q")); - - DependencyTerm t1 = new DependencyTerm(a, b, c, d, e); - DependencyTerm t2 = new DependencyTerm(a, d, e, f, g); - MetaRDLTerm mt1 = new MetaRDLTerm(x, p, q, v, w); - MetaRDLTerm mt2 = new MetaRDLTerm(x, v, w, y, z); - Map binding = new HashMap<>(); - Map orderConstraint = new HashMap<>(); - Set tmp = mt1.isMatchedBy(t1, new MatchConstraint(binding, orderConstraint)); - assertTrue(! tmp.isEmpty()); - tmp = mt2.isMatchedBy(t2, tmp); - assertTrue(! tmp.isEmpty()); - } - - @Test - void MatchTest3() { - DependencyTerm t1 = new DependencyTerm(a, b, c, d, e); - DependencyTerm t2 = new DependencyTerm(c, f, g); - MetaResource o = new MetaResource(new Variable("o")); - MetaResource p = new MetaResource(new Variable("p")); - MetaResource q = new MetaResource(new Variable("q")); - MetaResource r = new MetaResource(new Variable("r")); - MetaResource s = new MetaResource(new Variable("s")); - MetaResource t = new MetaResource(new Variable("t")); - MetaResource u = new MetaResource(new Variable("u")); - MetaRDLTerm mt1 = new MetaRDLTerm(o, p, q, r, s); - MetaRDLTerm mt2 = new MetaRDLTerm(s, t, u); - Set tmp = mt1.isMatchedBy(t1); - assertTrue(! tmp.isEmpty()); - tmp = mt2.isMatchedBy(t2, tmp); - assertTrue(! tmp.isEmpty()); - } - - @Test - void DynamicMatchTest() { - Resource a1 = new Resource("a1", Utils.INT, 3); - Resource a2 = new Resource("a2", Utils.INT, 1); - Resource a3 = new Resource("a3", Utils.INT, 4); - Resource a4 = new Resource("a4", Utils.INT, 2); - Resource a5 = new Resource("a5", Utils.INT, 4); - DependencyTerm t1 = new DependencyTerm(a1, a2, a3, a4, a5); - MetaResource x = new MetaResource(new Variable("x"), new Variable("n")); - MetaDynamicTerm mt1 = new MetaDynamicTerm(x, - (MetaTermPairGenerator) (i, depth, isLast) -> - new TermPair( - new MetaResource(new Variable("x" + (2*i + 1)), Utils.parse("n-1-" + i)), - new MetaResource(new Variable("x" + (2*i + 2)), Utils.parse("n+1")) - ) - ); - Set tmp = mt1.isMatchedBy(t1); - - assertTrue(! tmp.isEmpty()); - } - - @Test - void DynamicMatchTest2() { - MetaResource x = new MetaResource(new Variable("x")); - MetaDynamicTerm mt1 = new MetaDynamicTerm(x, (MetaTermPairGenerator) (i, depth, isLast) -> new TermPair(new MetaResource(new Variable("x" + i)), new MetaResource(new Variable("y"+i)))); - DependencyTerm d1 = new DependencyTerm(a, b, c); - DependencyTerm d2 = new DependencyTerm(a, b, c, d, e); - assertTrue(! mt1.isMatchedBy(d1).isEmpty()); - assertTrue(! mt1.isMatchedBy(d2).isEmpty()); } @Test void OrderTest() { - Resource text = new Resource("text", Utils.INT, 2); - Resource wNo = new Resource("wNo", Utils.INT, 2); - Resource v = new Resource("v", Utils.INT, 1); - Resource scId = new Resource("scId", Utils.INT, 1); - Resource curScId = new Resource("curScId", Utils.INT, 0); - Resource curWNo = new Resource("curWNo", Utils.INT, 1); + DependencyTerm t1 = new DependencyTerm(a, b, c); + assertEquals(t1.getOrder(), 1); - DependencyTerm t1 = new DependencyTerm(text, wNo, v); - DependencyTerm t2 = new DependencyTerm(t1, scId, curScId, v, curWNo); + DependencyTerm t2 = new DependencyTerm(h, i, a); assertEquals(t2.getOrder(), 1); + + DependencyTerm t3 = new DependencyTerm(a, b, c, d, e); + assertEquals(t3.getOrder(), 1); + + DependencyTerm t4 = new DependencyTerm(h, i, a, j , b); + assertEquals(t4.getOrder(), 1); + + DependencyTerm t5 = new DependencyTerm(h, i, a, j, k); + assertEquals(t5.getOrder(), 2); + + assertThrows(SyntaxException.class, () -> { + new DependencyTerm(a, b, c, h, i); + }); + } + + @Test + void StringTest() { + DependencyTerm t1 = new DependencyTerm(a, b, c); + assertEquals(t1.toString(), "[a : b -> c]"); + + DependencyTerm t3 = new DependencyTerm(a, b, c, d, e); + assertEquals(t3.toString(), "[a : b -> c, d -> e]"); + + DependencyTerm t4 = new DependencyTerm(a, d, e, b, c); + assertEquals(t4.toString(), "[a : b -> c, d -> e]"); + + DependencyTerm t5 = new DependencyTerm(a, b, c, b, c); + assertEquals(t5.toString(), "[a : b -> c, b -> c]"); + } } diff --git a/src/test/java/terms/DependencyTest.java b/src/test/java/terms/DependencyTest.java index e296033..ba660ef 100644 --- a/src/test/java/terms/DependencyTest.java +++ b/src/test/java/terms/DependencyTest.java @@ -3,22 +3,9 @@ import org.junit.jupiter.api.Test; -import java.util.HashMap; -import java.util.HashSet; -import java.util.Map; -import java.util.Set; - import exceptions.SyntaxException; -import models.algebra.Variable; import models.terms.Dependency; -import models.terms.RDLTerm; import models.terms.Resource; -import models.terms.meta.MatchConstraint; -import models.terms.meta.MetaDynamicTerm; -import models.terms.meta.MetaRDLTerm; -import models.terms.meta.MetaResource; -import models.terms.meta.MetaTermGenerator; -import models.terms.meta.OrderVariableConstraint; import utils.Utils; public class DependencyTest { @@ -35,7 +22,9 @@ Dependency d1 = new Dependency(a, b); Dependency d2 = new Dependency(a, b, b); - assertEquals(d1, d2); + Dependency d22 = new Dependency(a, b, b); + assertNotEquals(d1, d2); + assertEquals(d2, d22); Dependency d3 = new Dependency(a, c); assertFalse(d1.equals(d3)); @@ -81,66 +70,9 @@ Dependency d3 = new Dependency(a, c, b); assertEquals(d3.toString(), "a : b, c"); - } - - @Test - void MatchTest() { - MetaResource p = new MetaResource(new Variable("p")); - MetaResource q = new MetaResource(new Variable("q")); - MetaResource r = new MetaResource(new Variable("r")); - MetaResource s = new MetaResource(new Variable("s")); - MetaResource t = new MetaResource(new Variable("t")); - MetaRDLTerm mt1 = new MetaRDLTerm(p, q); - 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)); - - Dependency d1 = new Dependency(a, b); - Dependency d2 = new Dependency(a, b, c, f); - Dependency d3 = new Dependency(a, f, c, b); - Dependency d4 = new Dependency(a, b, f, c); - Dependency d5 = new Dependency(a, b, e, f); - - - Map binding = new HashMap<>(); - Map orderConst = new HashMap<>(); - 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()); - } - - @Test - void DynamicMatchTest() { - MetaResource x = new MetaResource(new Variable("x")); - MetaDynamicTerm md1 = new MetaDynamicTerm(x, new MetaTermGenerator() { - @Override - public MetaRDLTerm generate(int index, int depth, boolean isLast) { - if (index != 0) { - return new MetaResource(new Variable("r" + index)); - } else { - return new MetaResource(new Variable("y")); - } - }}); - MetaRDLTerm md2 = new MetaRDLTerm(new MetaResource(new Variable("y")), new MetaResource(new Variable("z"))); - Dependency d1 = new Dependency(a, b, c); - Dependency d2 = new Dependency(c, d); - Dependency d3 = new Dependency(b, d); - - Set tmp = md1.isMatchedBy(d1); - assertTrue(!tmp.isEmpty()); - assertTrue(! md2.isMatchedBy(d2, tmp).isEmpty()); - assertTrue(! md2.isMatchedBy(d3, tmp).isEmpty()); + Dependency d4 = new Dependency(a, b, e, c, b); + assertEquals(d4.toString(), "a : b, b, c, e"); } } diff --git a/src/test/java/terms/meta/MetaDependencyTermTest.java b/src/test/java/terms/meta/MetaDependencyTermTest.java new file mode 100644 index 0000000..e75916b --- /dev/null +++ b/src/test/java/terms/meta/MetaDependencyTermTest.java @@ -0,0 +1,119 @@ +package terms.meta; +import static org.junit.jupiter.api.Assertions.*; + +import org.junit.jupiter.api.Test; + +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.MetaDependencyTerm; +import models.terms.meta.MetaDynamicTerm; +import models.terms.meta.MetaRDLTerm; +import models.terms.meta.MetaResource; +import models.terms.meta.MetaTermPairGenerator; +import models.terms.meta.MetaTermPairGenerator.TermPair; +import models.terms.meta.OrderVariableConstraint; +import utils.Utils; + +public class MetaDependencyTermTest { + + Resource a = new Resource("a", Utils.INT, 1); + Resource b = new Resource("b", Utils.INT, 1); + Resource c = new Resource("c", Utils.INT, 1); + Resource d = new Resource("d", Utils.INT, 1); + Resource e = new Resource("e", Utils.INT, 1); + Resource f = new Resource("f", Utils.INT, 1); + Resource g = new Resource("g", Utils.INT, 1); + + @Test + void MatchTest() { + DependencyTerm t1 = new DependencyTerm(a, b, c, d, e); + DependencyTerm t2 = new DependencyTerm(a, g, f, b, c); + MetaResource x = new MetaResource(new Variable("x")); + MetaResource y = new MetaResource(new Variable("y")); + MetaResource z = new MetaResource(new Variable("z")); + MetaResource w = new MetaResource(new Variable("w")); + MetaResource p = new MetaResource(new Variable("p")); + MetaResource o = new MetaResource(new Variable("o")); + MetaResource n = new MetaResource(new Variable("n")); + MetaRDLTerm mt1 = new MetaDependencyTerm(x, y, z, w, p); + MetaRDLTerm mt2 = new MetaDependencyTerm(x, w, p, y, z); + MetaRDLTerm mt3 = new MetaDependencyTerm(x, p, w, y, z); + MetaRDLTerm mt4 = new MetaDependencyTerm(x, n, o, w, p); + Map binding = new HashMap<>(); + Map orderConstraint = new HashMap<>(); + Map correctBinding = new HashMap<>(); + correctBinding.put(x.getVariableName(), a); + correctBinding.put(y.getVariableName(), d); + correctBinding.put(z.getVariableName(), e); + correctBinding.put(w.getVariableName(), b); + correctBinding.put(p.getVariableName(), c); + mt4.toString(); + 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); + } + + @Test + void MatchTest2() { + MetaResource x = new MetaResource(new Variable("x")); + MetaResource y = new MetaResource(new Variable("y")); + MetaResource z = new MetaResource(new Variable("z")); + MetaResource v = new MetaResource(new Variable("v")); + MetaResource w = new MetaResource(new Variable("w")); + MetaResource p = new MetaResource(new Variable("p")); + MetaResource q = new MetaResource(new Variable("q")); + + DependencyTerm t1 = new DependencyTerm(a, b, c, d, e); + DependencyTerm t2 = new DependencyTerm(a, d, e, f, g); + MetaRDLTerm mt1 = new MetaDependencyTerm(x, p, q, v, w); + MetaRDLTerm mt2 = new MetaDependencyTerm(x, v, w, y, z); + Map binding = new HashMap<>(); + Map orderConstraint = new HashMap<>(); + Set tmp = mt1.isMatchedBy(t1, new MatchConstraint(binding, orderConstraint)); + assertTrue(! tmp.isEmpty()); + tmp = mt2.isMatchedBy(t2, tmp); + assertTrue(! tmp.isEmpty()); + } + + @Test + void MatchTest3() { + DependencyTerm t1 = new DependencyTerm(a, b, c, d, e); + DependencyTerm t2 = new DependencyTerm(c, f, g); + MetaResource o = new MetaResource(new Variable("o")); + MetaResource p = new MetaResource(new Variable("p")); + MetaResource q = new MetaResource(new Variable("q")); + MetaResource r = new MetaResource(new Variable("r")); + MetaResource s = new MetaResource(new Variable("s")); + MetaResource t = new MetaResource(new Variable("t")); + MetaResource u = new MetaResource(new Variable("u")); + MetaRDLTerm mt1 = new MetaDependencyTerm(o, p, q, r, s); + MetaRDLTerm mt2 = new MetaDependencyTerm(s, t, u); + Set tmp = mt1.isMatchedBy(t1); + assertTrue(! tmp.isEmpty()); + tmp = mt2.isMatchedBy(t2, tmp); + assertTrue(! tmp.isEmpty()); + } + + @Test + void DynamicMatchTest2() { + MetaResource x = new MetaResource(new Variable("x")); + MetaDynamicTerm mt1 = new MetaDynamicTerm(x, (MetaTermPairGenerator) (i, depth, isLast) -> new TermPair(new MetaResource(new Variable("x" + i)), new MetaResource(new Variable("y"+i)))); + DependencyTerm d1 = new DependencyTerm(a, b, c); + DependencyTerm d2 = new DependencyTerm(a, b, c, d, e); + assertTrue(! mt1.isMatchedBy(d1).isEmpty()); + assertTrue(! mt1.isMatchedBy(d2).isEmpty()); + } + +} diff --git a/src/test/java/terms/meta/MetaDependencyTest.java b/src/test/java/terms/meta/MetaDependencyTest.java new file mode 100644 index 0000000..912c5fe --- /dev/null +++ b/src/test/java/terms/meta/MetaDependencyTest.java @@ -0,0 +1,180 @@ +package terms.meta; +import static org.junit.jupiter.api.Assertions.*; +import static utils.Utils.*; + +import org.junit.jupiter.api.Test; + +import java.util.HashMap; +import java.util.HashSet; +import java.util.Map; +import java.util.Set; + +import models.algebra.Constant; +import models.algebra.Variable; +import models.terms.Dependency; +import models.terms.DependencyTerm; +import models.terms.RDLTerm; +import models.terms.Resource; +import models.terms.meta.MatchConstraint; +import models.terms.meta.MetaDependency; +import models.terms.meta.MetaDependencyTerm; +import models.terms.meta.MetaDependencyTermVariable; +import models.terms.meta.MetaDynamicTerm; +import models.terms.meta.MetaRDLTerm; +import models.terms.meta.MetaResource; +import models.terms.meta.MetaTermGenerator; +import models.terms.meta.OrderVariableConstraint; +import utils.Utils; + +public class MetaDependencyTest { + + + Resource a = new Resource("a", Utils.INT, 1); + Resource b = new Resource("b", Utils.INT, 1); + Resource c = new Resource("c", Utils.INT, 1); + Resource d = new Resource("d", Utils.INT, 1); + Resource e = new Resource("e", Utils.INT, 1); + Resource f = new Resource("f", Utils.INT, 1); + Resource g = new Resource("g", Utils.INT, 1); + + @Test + void MatchTest() { + MetaResource p = new MetaResource(new Variable("p")); + MetaResource q = new MetaResource(new Variable("q")); + MetaResource r = new MetaResource(new Variable("r")); + MetaResource s = new MetaResource(new Variable("s")); + MetaResource t = new MetaResource(new Variable("t")); + + MetaRDLTerm mt1 = new MetaDependency(p, q); + MetaRDLTerm mt2 = new MetaDependency(p, q, r, s); + MetaRDLTerm mt3 = new MetaDependency(p, r, q, s); + MetaRDLTerm mt4 = new MetaDependency(p, s, r, q); + + Dependency d1 = new Dependency(a, b); + Dependency d2 = new Dependency(a, b, c, f); + Dependency d3 = new Dependency(a, f, c, b); + Dependency d4 = new Dependency(a, b, f, c); + Dependency d5 = new Dependency(a, b, e, f); + + + Map binding = new HashMap<>(); + Map orderConst = new HashMap<>(); + 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()); + } + + @Test + void MetaDependencyMatchingWithoutOrderTest() { + Resource a = new Resource("a", INT, 1); + Resource b = new Resource("b", INT, 1); + Resource c = new Resource("c", INT, 1); + Dependency dep1 = new Dependency(a, b); + DependencyTerm te1 = new DependencyTerm(a, b, c); + Dependency dep2 = new Dependency(te1, b); + + MetaResource v1 = new MetaResource(new Variable("v1")); + MetaResource v2 = new MetaResource(new Variable("v2")); + MetaResource v3 = new MetaResource(new Variable("v3")); + MetaDependencyTermVariable vte = new MetaDependencyTermVariable(new Variable("vte")); + MetaRDLTerm metaDep = new MetaDependency(v1, v2); + MetaRDLTerm metaDep2 = new MetaDependency(vte, v2); + MetaRDLTerm metaTe = new MetaDependencyTerm(v1, v2, v3); + MetaRDLTerm metaDep3 = new MetaDependency(metaTe, v2); + MetaRDLTerm metaDep4 = new MetaDependency(metaTe, v3); + + //[a : b] matches [v1 : v2] + assertTrue(! metaDep.isMatchedBy(dep1).isEmpty()); + //[[a : b -> c] : b] does not match [v1 : v2] + assertFalse(! metaDep.isMatchedBy(dep2).isEmpty()); + //[[a : b -> c] : b] matches [vte : v2] + assertTrue(! metaDep2.isMatchedBy(dep2).isEmpty()); + //[[a : b -> c] : b] matches [[v1 : v2 -> v3] : v2] + assertTrue(! metaDep3.isMatchedBy(dep2).isEmpty()); + //[[a : b -> c] : b] does not match [[v1 : v2 -> v3] : v3] + assertFalse(! metaDep4.isMatchedBy(dep2).isEmpty()); + } + + @Test + void MetaDependencyMatchingWithConstantOrderTest() { + MetaResource v1 = new MetaResource(new Variable("v1"), new Constant("1")); + MetaResource v2 = new MetaResource(new Variable("v2"), new Constant("2")); + MetaRDLTerm vd1 = new MetaDependency(v1, v2); + + Resource a1 = new Resource("a1", INT, 1); + Resource a2 = new Resource("a2", INT, 2); + Dependency d1 = new Dependency(a1, a2); + //[1 : 2] matches [1 : 2] + assertTrue(! vd1.isMatchedBy(d1).isEmpty()); + + Resource b1 = new Resource("b1", INT, 1); + Dependency d2 = new Dependency(a1, b1); + //[1 : 1] does not match [1 : 2] + assertFalse(! vd1.isMatchedBy(d2).isEmpty()); + } + + @Test + void MetaDependencyMatchingWithVariableOrderTest() { + MetaResource v1 = new MetaResource(new Variable("v1"), parse("x")); + MetaResource v2 = new MetaResource(new Variable("v2"), parse("x")); + MetaResource v3 = new MetaResource(new Variable("v3"), parse("y")); + MetaRDLTerm vd1 = new MetaDependency(v1, v2); + MetaRDLTerm vd2 = new MetaDependency(v1, v3); + MetaRDLTerm vd3 = new MetaDependency(new MetaDependency(v3, v1), v2); + + Resource a1 = new Resource("a1", INT, 1); + Resource a2 = new Resource("a2", INT, 2); + Resource b1 = new Resource("b1", INT, 1); + Resource b2 = new Resource("b2", INT, 2); + Dependency d1 = new Dependency(a1, a2); + Dependency d2 = new Dependency(a1, b1); + Dependency d3 = new Dependency(new Dependency(a1, b1), a2); + Dependency d4 = new Dependency(new Dependency(a1, a2), b2); + //[1 : 2] does not match [x : x] + assertFalse(! vd1.isMatchedBy(d1).isEmpty()); + //[1 : 1] matches [x : x] + assertTrue(! vd1.isMatchedBy(d2).isEmpty()); + //[1 : 2] matches [x : y] + assertTrue(! vd2.isMatchedBy(d1).isEmpty()); + //[1 : 1] matches [x : y] + assertTrue(! vd2.isMatchedBy(d2).isEmpty()); + //[[1 : 1] : 2] does not match [[y : x] : x] + assertFalse(! vd3.isMatchedBy(d3).isEmpty()); + //[[1 : 2] : 2] matches [[y : x] : x] + assertTrue(! vd3.isMatchedBy(d4).isEmpty()); + } + + @Test + void DynamicMatchTest() { + MetaResource x = new MetaResource(new Variable("x")); + MetaDynamicTerm md1 = new MetaDynamicTerm(x, new MetaTermGenerator() { + @Override + public MetaRDLTerm generate(int index, int depth, boolean isLast) { + if (index != 0) { + return new MetaResource(new Variable("r" + index)); + } else { + return new MetaResource(new Variable("y")); + } + }}); + MetaRDLTerm md2 = new MetaDependency(new MetaResource(new Variable("y")), new MetaResource(new Variable("z"))); + Dependency d1 = new Dependency(a, b, c); + Dependency d2 = new Dependency(c, d); + Dependency d3 = new Dependency(b, d); + + Set tmp = md1.isMatchedBy(d1); + assertTrue(!tmp.isEmpty()); + assertTrue(! md2.isMatchedBy(d2, tmp).isEmpty()); + assertTrue(! md2.isMatchedBy(d3, tmp).isEmpty()); + } + +} diff --git a/src/test/java/terms/meta/MetaRDLTermTest.java b/src/test/java/terms/meta/MetaRDLTermTest.java deleted file mode 100644 index 9570299..0000000 --- a/src/test/java/terms/meta/MetaRDLTermTest.java +++ /dev/null @@ -1,98 +0,0 @@ -package terms.meta; - -import static org.junit.jupiter.api.Assertions.*; -import static utils.Utils.*; - -import org.junit.jupiter.api.Test; - -import models.algebra.Constant; -import models.algebra.Variable; -import models.terms.Dependency; -import models.terms.DependencyTerm; -import models.terms.Resource; -import models.terms.meta.MetaDependencyTermVariable; -import models.terms.meta.MetaRDLTerm; -import models.terms.meta.MetaResource; -public class MetaRDLTermTest { - - @Test - void MetaDependencyMatchingWithoutOrderTest() { - Resource a = new Resource("a", INT, 1); - Resource b = new Resource("b", INT, 1); - Resource c = new Resource("c", INT, 1); - Dependency dep1 = new Dependency(a, b); - DependencyTerm te1 = new DependencyTerm(a, b, c); - Dependency dep2 = new Dependency(te1, b); - - MetaResource v1 = new MetaResource(new Variable("v1")); - MetaResource v2 = new MetaResource(new Variable("v2")); - MetaResource v3 = new MetaResource(new Variable("v3")); - MetaDependencyTermVariable vte = new MetaDependencyTermVariable(new Variable("vte")); - MetaRDLTerm metaDep = new MetaRDLTerm(v1, v2); - MetaRDLTerm metaDep2 = new MetaRDLTerm(vte, v2); - MetaRDLTerm metaTe = new MetaRDLTerm(v1, v2, v3); - MetaRDLTerm metaDep3 = new MetaRDLTerm(metaTe, v2); - MetaRDLTerm metaDep4 = new MetaRDLTerm(metaTe, v3); - - //[a : b] matches [v1 : v2] - assertTrue(! metaDep.isMatchedBy(dep1).isEmpty()); - //[[a : b -> c] : b] does not match [v1 : v2] - assertFalse(! metaDep.isMatchedBy(dep2).isEmpty()); - //[[a : b -> c] : b] matches [vte : v2] - assertTrue(! metaDep2.isMatchedBy(dep2).isEmpty()); - //[[a : b -> c] : b] matches [[v1 : v2 -> v3] : v2] - assertTrue(! metaDep3.isMatchedBy(dep2).isEmpty()); - //[[a : b -> c] : b] does not match [[v1 : v2 -> v3] : v3] - assertFalse(! metaDep4.isMatchedBy(dep2).isEmpty()); - } - - @Test - void MetaDependencyMatchingWithConstantOrderTest() { - MetaResource v1 = new MetaResource(new Variable("v1"), new Constant("1")); - MetaResource v2 = new MetaResource(new Variable("v2"), new Constant("2")); - MetaRDLTerm vd1 = new MetaRDLTerm(v1, v2); - - Resource a1 = new Resource("a1", INT, 1); - Resource a2 = new Resource("a2", INT, 2); - Dependency d1 = new Dependency(a1, a2); - //[1 : 2] matches [1 : 2] - assertTrue(! vd1.isMatchedBy(d1).isEmpty()); - - Resource b1 = new Resource("b1", INT, 1); - Dependency d2 = new Dependency(a1, b1); - //[1 : 1] does not match [1 : 2] - assertFalse(! vd1.isMatchedBy(d2).isEmpty()); - } - - @Test - void MetaDependencyMatchingWithVariableOrderTest() { - MetaResource v1 = new MetaResource(new Variable("v1"), parse("x")); - MetaResource v2 = new MetaResource(new Variable("v2"), parse("x")); - MetaResource v3 = new MetaResource(new Variable("v3"), parse("y")); - MetaRDLTerm vd1 = new MetaRDLTerm(v1, v2); - MetaRDLTerm vd2 = new MetaRDLTerm(v1, v3); - MetaRDLTerm vd3 = new MetaRDLTerm(new MetaRDLTerm(v3, v1), v2); - - Resource a1 = new Resource("a1", INT, 1); - Resource a2 = new Resource("a2", INT, 2); - Resource b1 = new Resource("b1", INT, 1); - Resource b2 = new Resource("b2", INT, 2); - Dependency d1 = new Dependency(a1, a2); - Dependency d2 = new Dependency(a1, b1); - Dependency d3 = new Dependency(new Dependency(a1, b1), a2); - Dependency d4 = new Dependency(new Dependency(a1, a2), b2); - //[1 : 2] does not match [x : x] - assertFalse(! vd1.isMatchedBy(d1).isEmpty()); - //[1 : 1] matches [x : x] - assertTrue(! vd1.isMatchedBy(d2).isEmpty()); - //[1 : 2] matches [x : y] - assertTrue(! vd2.isMatchedBy(d1).isEmpty()); - //[1 : 1] matches [x : y] - assertTrue(! vd2.isMatchedBy(d2).isEmpty()); - //[[1 : 1] : 2] does not match [[y : x] : x] - assertFalse(! vd3.isMatchedBy(d3).isEmpty()); - //[[1 : 2] : 2] matches [[y : x] : x] - assertTrue(! vd3.isMatchedBy(d4).isEmpty()); - } - -} diff --git a/src/test/java/terms/meta/SubstituteTest.java b/src/test/java/terms/meta/SubstituteTest.java index 65eb5a8..b37da61 100644 --- a/src/test/java/terms/meta/SubstituteTest.java +++ b/src/test/java/terms/meta/SubstituteTest.java @@ -11,6 +11,7 @@ import models.terms.RDLTerm; import models.terms.Resource; import models.terms.meta.MatchConstraint; +import models.terms.meta.MetaDependencyTerm; import models.terms.meta.MetaEvaluatableTermVariable; import models.terms.meta.MetaRDLTerm; import models.terms.meta.MetaResource; @@ -24,7 +25,7 @@ MetaEvaluatableTermVariable z = new MetaEvaluatableTermVariable(new Variable("z")); - MetaRDLTerm metaTerm1 = new MetaRDLTerm(x, y, z); + MetaRDLTerm metaTerm1 = new MetaDependencyTerm(x, y, z); Resource a = new Resource("a", Utils.INT, 1); Resource b = new Resource("b", Utils.INT, 1);