From df5e1031d7f54c26695264a06cc72fbe769ab1ec Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Sun, 24 May 2009 20:11:40 +0000 Subject: Perform full filter reduction, regardless of sub filtering ordering. --- .../java/com/amazon/carbonado/filter/Group.java | 166 +++++++++++++++------ 1 file changed, 119 insertions(+), 47 deletions(-) diff --git a/src/main/java/com/amazon/carbonado/filter/Group.java b/src/main/java/com/amazon/carbonado/filter/Group.java index 1138567..70cfd3e 100644 --- a/src/main/java/com/amazon/carbonado/filter/Group.java +++ b/src/main/java/com/amazon/carbonado/filter/Group.java @@ -31,34 +31,43 @@ import com.amazon.carbonado.Storable; */ class Group { final boolean mForAnd; - Set> mChildren; + Set> mElements; Group(boolean forAnd) { mForAnd = forAnd; } - boolean add(Filter child) { - if (mChildren == null) { - mChildren = new LinkedHashSet>(20); + boolean add(Filter element) { + if (mElements == null) { + // Use LinkedHashSet to best preserve original ordering of + // elements. It also tends to be faster when performing complex + // dnf/cnf transformations because the reduction step doesn't have + // to work as hard rearranging elements. + mElements = new LinkedHashSet>(20); } - return mChildren.add(child); + return mElements.add(element); } /** - * Reduce the group set by eliminating redundant children. The + * Reduce the group set by eliminating redundant elements. These * transformations applied are: * * ((a & b) | b) => b * ((a | b) & b) => b */ void reduce() { - Iterator> it = mChildren.iterator(); + // Note that the scanner choice is opposite of our type. This is + // because a group of 'and's has children which are 'or's and vice + // versa. + Scanner scanner = mForAnd ? OrChildScanner.THE : AndChildScanner.THE; + + Iterator> it = mElements.iterator(); aLoop: while (it.hasNext()) { Filter a = it.next(); - for (Filter b : mChildren) { + for (Filter b : mElements) { if (a != b) { - if (a.accept(new Scanner(!mForAnd), b)) { + if (a.accept(scanner, b)) { it.remove(); continue aLoop; } @@ -69,14 +78,14 @@ class Group { Filter merge() { Filter filter = null; - if (mChildren != null) { - for (Filter child : mChildren) { + if (mElements != null) { + for (Filter element : mElements) { if (filter == null) { - filter = child; + filter = element; } else if (mForAnd) { - filter = filter.and(child); + filter = filter.and(element); } else { - filter = filter.or(child); + filter = filter.or(element); } } } @@ -84,59 +93,122 @@ class Group { } /** - * Does the work of reducing a group + * Base class for finding filters inside other filters. */ - private static class Scanner extends Visitor>{ - private final boolean mForAnd; + private static abstract class Scanner + extends Visitor> + { + @Override + public Boolean visit(PropertyFilter filter, Filter search) { + return filter == search; + } - Scanner(boolean forAnd) { - mForAnd = forAnd; + @Override + public Boolean visit(ExistsFilter filter, Filter search) { + return filter == search; } + } + + /** + * Searches for the existence of a child filter composed of 'or's as a + * sub-filter of another filter composed of 'or's, returning true if found. + */ + private static class OrChildScanner extends Scanner { + static final OrChildScanner THE = new OrChildScanner(); - /** - * @return TRUE if overlap was found - */ @Override - public Boolean visit(OrFilter filter, Filter child) { - if (mForAnd) { - return false; + public Boolean visit(OrFilter parent, Filter child) { + if (parent == child) { + return true; } - if (filter == child) { + if (parent.getLeftFilter().accept(this, child) || + parent.getRightFilter().accept(this, child)) + { return true; } - return filter.getLeftFilter().accept(this, child) || - filter.getRightFilter().accept(this, child); + Scanner scanner = OrParentScanner.THE; + return child.accept(scanner, parent); + } + + @Override + public Boolean visit(AndFilter parent, Filter child) { + return false; + } + } + + /** + * Searches for the existence of a child filter composed of 'and's as a + * sub-filter of another filter composed of 'and's, returning true if + * found. + */ + private static class AndChildScanner extends Scanner { + static final AndChildScanner THE = new AndChildScanner(); + + @Override + public Boolean visit(OrFilter parent, Filter child) { + return false; } - /** - * @return TRUE if overlap was found - */ @Override - public Boolean visit(AndFilter filter, Filter child) { - if (!mForAnd) { - return false; + public Boolean visit(AndFilter parent, Filter child) { + if (parent == child) { + return true; } - if (filter == child) { + if (parent.getLeftFilter().accept(this, child) || + parent.getRightFilter().accept(this, child)) + { return true; } - return filter.getLeftFilter().accept(this, child) || - filter.getRightFilter().accept(this, child); + Scanner scanner = AndParentScanner.THE; + return child.accept(scanner, parent); + } + } + + /** + * Searches for the existence of a parent filter composed of 'or's as a + * super-filter of another filter composed of 'or's, returning true if + * found. + */ + private static class OrParentScanner extends Scanner { + static final OrParentScanner THE = new OrParentScanner(); + + @Override + public Boolean visit(AndFilter child, Filter parent) { + return false; } - /** - * @return TRUE if overlap was found - */ @Override - public Boolean visit(PropertyFilter filter, Filter child) { - return filter == child; + public Boolean visit(OrFilter child, Filter parent) { + if (child == parent) { + return true; + } + Scanner scanner = OrChildScanner.THE; + return parent.accept(scanner, child.getLeftFilter()) && + parent.accept(scanner, child.getRightFilter()); + } + } + + /** + * Searches for the existence of a parent filter composed of 'and's as a + * super-filter of another filter composed of 'and's, returning true if + * found. + */ + private static class AndParentScanner extends Scanner { + static final AndParentScanner THE = new AndParentScanner(); + + @Override + public Boolean visit(AndFilter child, Filter parent) { + if (child == parent) { + return true; + } + Scanner scanner = AndChildScanner.THE; + return parent.accept(scanner, child.getLeftFilter()) && + parent.accept(scanner, child.getRightFilter()); } - /** - * @return TRUE if overlap was found - */ @Override - public Boolean visit(ExistsFilter filter, Filter child) { - return filter == child; + public Boolean visit(OrFilter child, Filter parent) { + return false; } } } -- cgit v1.2.3