From 1205ea08cc9e53de40b71447a79daf378cb0a205 Mon Sep 17 00:00:00 2001
From: "Brian S. O'Neill" <bronee@gmail.com>
Date: Wed, 30 Aug 2006 01:56:35 +0000
Subject: Add filter implementation
---
.../com/amazon/carbonado/filter/AndFilter.java | 128 +++++
.../amazon/carbonado/filter/BinaryOpFilter.java | 116 ++++
.../java/com/amazon/carbonado/filter/Binder.java | 93 +++
.../com/amazon/carbonado/filter/ClosedFilter.java | 127 +++++
.../com/amazon/carbonado/filter/Distributer.java | 78 +++
.../java/com/amazon/carbonado/filter/Filter.java | 505 +++++++++++++++++
.../com/amazon/carbonado/filter/FilterParser.java | 316 +++++++++++
.../com/amazon/carbonado/filter/FilterValues.java | 623 +++++++++++++++++++++
.../java/com/amazon/carbonado/filter/Group.java | 134 +++++
.../com/amazon/carbonado/filter/OpenFilter.java | 127 +++++
.../java/com/amazon/carbonado/filter/OrFilter.java | 128 +++++
.../amazon/carbonado/filter/PropertyFilter.java | 472 ++++++++++++++++
.../carbonado/filter/PropertyFilterList.java | 186 ++++++
.../java/com/amazon/carbonado/filter/Reducer.java | 103 ++++
.../java/com/amazon/carbonado/filter/RelOp.java | 78 +++
.../java/com/amazon/carbonado/filter/Visitor.java | 55 ++
.../com/amazon/carbonado/filter/package-info.java | 24 +
17 files changed, 3293 insertions(+)
create mode 100644 src/main/java/com/amazon/carbonado/filter/AndFilter.java
create mode 100644 src/main/java/com/amazon/carbonado/filter/BinaryOpFilter.java
create mode 100644 src/main/java/com/amazon/carbonado/filter/Binder.java
create mode 100644 src/main/java/com/amazon/carbonado/filter/ClosedFilter.java
create mode 100644 src/main/java/com/amazon/carbonado/filter/Distributer.java
create mode 100644 src/main/java/com/amazon/carbonado/filter/Filter.java
create mode 100644 src/main/java/com/amazon/carbonado/filter/FilterParser.java
create mode 100644 src/main/java/com/amazon/carbonado/filter/FilterValues.java
create mode 100644 src/main/java/com/amazon/carbonado/filter/Group.java
create mode 100644 src/main/java/com/amazon/carbonado/filter/OpenFilter.java
create mode 100644 src/main/java/com/amazon/carbonado/filter/OrFilter.java
create mode 100644 src/main/java/com/amazon/carbonado/filter/PropertyFilter.java
create mode 100644 src/main/java/com/amazon/carbonado/filter/PropertyFilterList.java
create mode 100644 src/main/java/com/amazon/carbonado/filter/Reducer.java
create mode 100644 src/main/java/com/amazon/carbonado/filter/RelOp.java
create mode 100644 src/main/java/com/amazon/carbonado/filter/Visitor.java
create mode 100644 src/main/java/com/amazon/carbonado/filter/package-info.java
(limited to 'src/main')
diff --git a/src/main/java/com/amazon/carbonado/filter/AndFilter.java b/src/main/java/com/amazon/carbonado/filter/AndFilter.java
new file mode 100644
index 0000000..92c3937
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/filter/AndFilter.java
@@ -0,0 +1,128 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.filter;
+
+import java.io.IOException;
+
+import com.amazon.carbonado.Storable;
+
+/**
+ * Filter tree node that performs a logical 'and' test.
+ *
+ * @author Brian S O'Neill
+ */
+public class AndFilter<S extends Storable> extends BinaryOpFilter<S> {
+ /**
+ * Returns a canonical instance.
+ *
+ * @throws IllegalArgumentException if either filter is null
+ */
+ @SuppressWarnings("unchecked")
+ static <S extends Storable> AndFilter<S> getCanonical(Filter<S> left, Filter<S> right) {
+ return (AndFilter<S>) cCanonical.put(new AndFilter<S>(left, right));
+ }
+
+ /**
+ * @throws IllegalArgumentException if either filter is null
+ */
+ private AndFilter(Filter<S> left, Filter<S> right) {
+ super(left, right);
+ }
+
+ public Filter<S> not() {
+ return mLeft.not().or(mRight.not());
+ }
+
+ public <R, P> R accept(Visitor<S, R, P> visitor, P param) {
+ return visitor.visit(this, param);
+ }
+
+ Filter<S> buildDisjunctiveNormalForm() {
+ Filter<S> left = mLeft.reduce().dnf();
+ Filter<S> right = mRight.reduce().dnf();
+ if (left instanceof OrFilter) {
+ return left.accept(new Distributer<S>(true, true), right).reduce().dnf();
+ }
+ if (right instanceof OrFilter) {
+ return right.accept(new Distributer<S>(false, true), left).reduce().dnf();
+ }
+ return left.and(right).reduce();
+ }
+
+ Filter<S> buildConjunctiveNormalForm() {
+ return mLeft.cnf().and(mRight.cnf()).reduce();
+ }
+
+ boolean checkIsDisjunctiveNormalForm() {
+ return (!(mLeft instanceof OrFilter))
+ && (!(mRight instanceof OrFilter))
+ && mLeft.isDisjunctiveNormalForm()
+ && mRight.isDisjunctiveNormalForm();
+ }
+
+ boolean checkIsConjunctiveNormalForm() {
+ return mLeft.isConjunctiveNormalForm() && mRight.isConjunctiveNormalForm();
+ }
+
+ @Override
+ public int hashCode() {
+ return mLeft.hashCode() * 31 + mRight.hashCode();
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj instanceof AndFilter) {
+ AndFilter<?> other = (AndFilter<?>) obj;
+ return getStorableType() == other.getStorableType()
+ && mLeft.equals(other.mLeft) && mRight.equals(other.mRight);
+ }
+ return false;
+ }
+
+ public void appendTo(Appendable app, FilterValues<S> values) throws IOException {
+ if (mLeft instanceof OrFilter) {
+ app.append('(');
+ mLeft.appendTo(app, values);
+ app.append(')');
+ } else {
+ mLeft.appendTo(app, values);
+ }
+ app.append(" & ");
+ if (mRight instanceof OrFilter) {
+ app.append('(');
+ mRight.appendTo(app, values);
+ app.append(')');
+ } else {
+ mRight.appendTo(app, values);
+ }
+ }
+
+ void dumpTree(Appendable app, int indentLevel) throws IOException {
+ mRight.dumpTree(app, indentLevel + 1);
+ for (int i=0; i<indentLevel; i++) {
+ app.append(" ");
+ }
+ app.append("and");
+ app.append('\n');
+ mLeft.dumpTree(app, indentLevel + 1);
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/filter/BinaryOpFilter.java b/src/main/java/com/amazon/carbonado/filter/BinaryOpFilter.java
new file mode 100644
index 0000000..c95f493
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/filter/BinaryOpFilter.java
@@ -0,0 +1,116 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.filter;
+
+import com.amazon.carbonado.Storable;
+
+/**
+ * Base class for filter tree nodes that have a left and right child.
+ *
+ * @author Brian S O'Neill
+ */
+public abstract class BinaryOpFilter<S extends Storable> extends Filter<S> {
+ // Bits used in mState.
+ private static final byte REDUCED = 0x1 << 0; // tree is reduced
+ private static final byte DNF_KNOWN = 0x1 << 1; // disjunctive normal form state is known
+ private static final byte DNF = 0x1 << 2; // is disjunctive normal form if set
+ private static final byte CNF_KNOWN = 0x1 << 3; // conjunctive normal form state is known
+ private static final byte CNF = 0x1 << 4; // is conjunctive normal form if set
+ private static final byte BOUND = 0x1 << 5; // properties are bound when set
+
+ final Filter<S> mLeft;
+ final Filter<S> mRight;
+
+ byte mState;
+
+ BinaryOpFilter(Filter<S> left, Filter<S> right) {
+ super(left == null ? null : left.getStorableType());
+ if (right == null) {
+ throw new IllegalArgumentException();
+ }
+ if (left.getStorableType() != right.getStorableType()) {
+ throw new IllegalArgumentException("Type mismatch");
+ }
+ mLeft = left;
+ mRight = right;
+ }
+
+ public Filter<S> getLeftFilter() {
+ return mLeft;
+ }
+
+ public Filter<S> getRightFilter() {
+ return mRight;
+ }
+
+ public Filter<S> bind() {
+ if (isBound()) {
+ return this;
+ }
+ return accept(new Binder<S>(), null);
+ }
+
+ public boolean isBound() {
+ return (mState & BOUND) != 0;
+ }
+
+ void markBound() {
+ mState |= BOUND;
+ }
+
+ final synchronized boolean isDisjunctiveNormalForm() {
+ if ((mState & DNF_KNOWN) != 0) { // if dnf state is known...
+ return (mState & DNF) != 0; // return true if dnf
+ }
+ if (checkIsDisjunctiveNormalForm()) {
+ mState |= (DNF_KNOWN | DNF); // dnf state is now known, and is dnf
+ return true;
+ } else {
+ mState |= DNF_KNOWN; // dnf state is now known, and is not dnf
+ mState &= ~DNF;
+ return false;
+ }
+ }
+
+ abstract boolean checkIsDisjunctiveNormalForm();
+
+ final synchronized boolean isConjunctiveNormalForm() {
+ if ((mState & CNF_KNOWN) != 0) { // if cnf state is known...
+ return (mState & CNF) != 0; // return true if cnf
+ }
+ if (checkIsConjunctiveNormalForm()) {
+ mState |= (CNF_KNOWN | CNF); // cnf state is now known, and is cnf
+ return true;
+ } else {
+ mState |= CNF_KNOWN; // cnf state is now known, and is not cnf
+ mState &= ~CNF;
+ return false;
+ }
+ }
+
+ abstract boolean checkIsConjunctiveNormalForm();
+
+ synchronized boolean isReduced() {
+ return (mState & REDUCED) != 0;
+ }
+
+ synchronized void markReduced() {
+ mState |= REDUCED;
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/filter/Binder.java b/src/main/java/com/amazon/carbonado/filter/Binder.java
new file mode 100644
index 0000000..7a854f1
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/filter/Binder.java
@@ -0,0 +1,93 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.filter;
+
+import java.util.IdentityHashMap;
+import java.util.Map;
+
+import com.amazon.carbonado.Storable;
+
+/**
+ * Used by bind operation - assigns bind IDs to property filters. This allows
+ * operations like dnf to not lose track of variable assignments even after
+ * more nodes are added to the filter tree.
+ *
+ * @author Brian S O'Neill
+ */
+class Binder<S extends Storable> extends Visitor<S, Filter<S>, Object> {
+ // Maps PropertyFilter with bind ID zero to PropertyFilter with highest
+ // bind ID.
+ private final Map<PropertyFilter<S>, PropertyFilter<S>> mBindMap;
+
+ Binder() {
+ mBindMap = new IdentityHashMap<PropertyFilter<S>, PropertyFilter<S>>();
+ }
+
+ @Override
+ public Filter<S> visit(OrFilter<S> filter, Object param) {
+ Filter<S> left = filter.getLeftFilter();
+ Filter<S> newLeft = left.accept(this, null);
+ Filter<S> right = filter.getRightFilter();
+ Filter<S> newRight = right.accept(this, null);
+
+ Filter<S> newFilter;
+ if (left != newLeft || right != newRight) {
+ newFilter = newLeft.or(newRight);
+ } else {
+ newFilter = filter;
+ }
+
+ newFilter.markBound();
+ return newFilter;
+ }
+
+ @Override
+ public Filter<S> visit(AndFilter<S> filter, Object param) {
+ Filter<S> left = filter.getLeftFilter();
+ Filter<S> newLeft = left.accept(this, null);
+ Filter<S> right = filter.getRightFilter();
+ Filter<S> newRight = right.accept(this, null);
+
+ Filter<S> newFilter;
+ if (left != newLeft || right != newRight) {
+ newFilter = newLeft.and(newRight);
+ } else {
+ newFilter = filter;
+ }
+
+ newFilter.markBound();
+ return newFilter;
+ }
+
+ @Override
+ public Filter<S> visit(PropertyFilter<S> filter, Object param) {
+ if (filter.getBindID() != 0) {
+ return filter;
+ }
+ filter = PropertyFilter.getCanonical(filter, 1);
+ PropertyFilter<S> highest = mBindMap.get(filter);
+ if (highest == null) {
+ highest = filter;
+ } else {
+ highest = PropertyFilter.getCanonical(filter, highest.getBindID() + 1);
+ }
+ mBindMap.put(filter, highest);
+ return highest;
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/filter/ClosedFilter.java b/src/main/java/com/amazon/carbonado/filter/ClosedFilter.java
new file mode 100644
index 0000000..4584109
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/filter/ClosedFilter.java
@@ -0,0 +1,127 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.filter;
+
+import java.io.IOException;
+
+import com.amazon.carbonado.Storable;
+
+/**
+ * Filter which blocks any results from passing through.
+ *
+ * @author Brian S O'Neill
+ */
+public class ClosedFilter<S extends Storable> extends Filter<S> {
+ ClosedFilter(Class<S> type) {
+ super(type);
+ }
+
+ public Filter<S> and(Filter<S> filter) {
+ return this;
+ }
+
+ public Filter<S> or(Filter<S> filter) {
+ return filter;
+ }
+
+ public Filter<S> not() {
+ return getOpenFilter(getStorableType());
+ }
+
+ @Override
+ public FilterValues<S> initialFilterValues() {
+ return null;
+ }
+
+ @Override
+ PropertyFilterList<S> getTailPropertyFilterList() {
+ return null;
+ }
+
+ public <R, P> R accept(Visitor<S, R, P> visitor, P param) {
+ return visitor.visit(this, param);
+ }
+
+ public Filter<S> bind() {
+ return this;
+ }
+
+ public boolean isBound() {
+ return true;
+ }
+
+ void markBound() {
+ }
+
+ Filter<S> buildDisjunctiveNormalForm() {
+ return this;
+ }
+
+ Filter<S> buildConjunctiveNormalForm() {
+ return this;
+ }
+
+ boolean isDisjunctiveNormalForm() {
+ return true;
+ }
+
+ boolean isConjunctiveNormalForm() {
+ return true;
+ }
+
+ boolean isReduced() {
+ return true;
+ }
+
+ void markReduced() {
+ }
+
+ @Override
+ public int hashCode() {
+ return getStorableType().hashCode();
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj instanceof ClosedFilter) {
+ ClosedFilter<?> other = (ClosedFilter<?>) obj;
+ return getStorableType() == other.getStorableType();
+ }
+ return false;
+ }
+
+ @Override
+ public String toString() {
+ return "closed";
+ }
+
+ public void appendTo(Appendable app, FilterValues<S> values) throws IOException {
+ app.append("closed");
+ }
+
+ void dumpTree(Appendable app, int indentLevel) throws IOException {
+ for (int i=0; i<indentLevel; i++) {
+ app.append(" ");
+ }
+ app.append("closed");
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/filter/Distributer.java b/src/main/java/com/amazon/carbonado/filter/Distributer.java
new file mode 100644
index 0000000..e47e842
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/filter/Distributer.java
@@ -0,0 +1,78 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.filter;
+
+import com.amazon.carbonado.Storable;
+
+/**
+ * Algebraically distributes a tree into each node of the visted tree.
+ *
+ * @author Brian S O'Neill
+ */
+class Distributer<S extends Storable> extends Visitor<S, Filter<S>, Filter<S>> {
+ private final boolean mDoRight;
+ private final boolean mDoAnd;
+
+ /**
+ * @param doRight when true, distribute to the right, otherwise,
+ * distribute to the left.
+ * @param doAnd when true, distribute 'and' operations, otherwise
+ * distribute 'or' operations.
+ */
+ Distributer(boolean doRight, boolean doAnd) {
+ mDoRight = doRight;
+ mDoAnd = doAnd;
+ }
+
+ /**
+ * @param filter candidate node to potentially replace
+ * @param distribute node to distribute into candidate node
+ * @return original candidate or replacement
+ */
+ @Override
+ public Filter<S> visit(OrFilter<S> filter, Filter<S> distribute) {
+ return OrFilter.getCanonical(filter.getLeftFilter().accept(this, distribute),
+ filter.getRightFilter().accept(this, distribute));
+ }
+
+ /**
+ * @param filter candidate node to potentially replace
+ * @param distribute node to distribute into candidate node
+ * @return original candidate or replacement
+ */
+ @Override
+ public Filter<S> visit(AndFilter<S> filter, Filter<S> distribute) {
+ return AndFilter.getCanonical(filter.getLeftFilter().accept(this, distribute),
+ filter.getRightFilter().accept(this, distribute));
+ }
+
+ /**
+ * @param filter candidate node to potentially replace
+ * @param distribute node to distribute into candidate node
+ * @return original candidate or replacement
+ */
+ @Override
+ public Filter<S> visit(PropertyFilter<S> filter, Filter<S> distribute) {
+ if (mDoRight) {
+ return mDoAnd ? filter.and(distribute) : filter.or(distribute);
+ } else {
+ return mDoAnd ? distribute.and(filter) : distribute.or(filter);
+ }
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/filter/Filter.java b/src/main/java/com/amazon/carbonado/filter/Filter.java
new file mode 100644
index 0000000..f688d60
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/filter/Filter.java
@@ -0,0 +1,505 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.filter;
+
+import java.io.IOException;
+import java.util.Map;
+import org.cojen.util.SoftValuedHashMap;
+import org.cojen.util.WeakCanonicalSet;
+import org.cojen.util.WeakIdentityMap;
+
+import com.amazon.carbonado.MalformedFilterException;
+import com.amazon.carbonado.Storable;
+
+import com.amazon.carbonado.info.ChainedProperty;
+
+import com.amazon.carbonado.util.Appender;
+
+/**
+ * An immutable tree structure representing a query result filter. Filters can
+ * be created using a builder pattern, by expression parsing, or by a
+ * combination of techniques. Filter instances are canonical, which means that
+ * equivalent instances can be compared for equality using the '==' operator.
+ *
+ * <p>Any method that accepts a filter expression parses against the following
+ * syntax:
+ *
+ * <pre>
+ * Filter = OrFilter
+ * OrFilter = AndFilter { "|" AndFilter }
+ * AndFilter = NotFilter { "&" NotFilter }
+ * NotFilter = [ "!" ] EntityFilter
+ * EntityFilter = PropertyFilter
+ * | "(" Filter ")"
+ * PropertyFilter = ChainedProperty RelOp "?"
+ * RelOp = "=" | "!=" | "<" | ">=" | ">" | "<="
+ * ChainedProperty = Identifier { "." Identifier }
+ * </pre>
+ *
+ * @author Brian S O'Neill
+ */
+public abstract class Filter<S extends Storable> implements Appender {
+
+ private static final Object OPEN_KEY = new Object();
+ private static final Object CLOSED_KEY = new Object();
+
+ // Collection of canonical filters.
+ static WeakCanonicalSet cCanonical = new WeakCanonicalSet();
+
+ // Map<(weak)Class<S>, Map<Object, (soft)Filter<S>>>
+ private static Map cCache = new WeakIdentityMap();
+
+ /**
+ * Returns a cached filter instance that operates on the given type and
+ * filter expression.
+ *
+ * @param type type of Storable that query is made against
+ * @param expression query filter expression to parse
+ * @return canonical Filter instance
+ * @throws IllegalArgumentException if type or filter expression is null
+ * @throws MalformedFilterException if filter expression is malformed
+ */
+ public static <S extends Storable> Filter<S> filterFor(Class<S> type, String expression) {
+ Map<Object, Filter<S>> filterCache = getFilterCache(type);
+ synchronized (filterCache) {
+ Filter<S> filter = filterCache.get(expression);
+ if (filter == null) {
+ filter = new FilterParser<S>(type, expression).parseRoot();
+ filterCache.put(expression, filter);
+ }
+ return filter;
+ }
+ }
+
+ /**
+ * Returns a cached filter instance that operates on the given type, which
+ * allows all results to pass through.
+ *
+ * @param type type of Storable that query is made against
+ * @return canonical Filter instance
+ * @see OpenFilter
+ */
+ public static <S extends Storable> Filter<S> getOpenFilter(Class<S> type) {
+ Map<Object, Filter<S>> filterCache = getFilterCache(type);
+ synchronized (filterCache) {
+ Filter<S> filter = filterCache.get(OPEN_KEY);
+ if (filter == null) {
+ filter = new OpenFilter<S>(type);
+ filterCache.put(OPEN_KEY, filter);
+ }
+ return filter;
+ }
+ }
+
+ /**
+ * Returns a cached filter instance that operates on the given type, which
+ * prevents any results from passing through.
+ *
+ * @param type type of Storable that query is made against
+ * @return canonical Filter instance
+ * @see ClosedFilter
+ */
+ public static <S extends Storable> Filter<S> getClosedFilter(Class<S> type) {
+ Map<Object, Filter<S>> filterCache = getFilterCache(type);
+ synchronized (filterCache) {
+ Filter<S> filter = filterCache.get(CLOSED_KEY);
+ if (filter == null) {
+ filter = new ClosedFilter<S>(type);
+ filterCache.put(CLOSED_KEY, filter);
+ }
+ return filter;
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ private static <S extends Storable> Map<Object, Filter<S>> getFilterCache(Class<S> type) {
+ synchronized (cCache) {
+ Map<Object, Filter<S>> filterCache = (Map<Object, Filter<S>>) cCache.get(type);
+ if (filterCache == null) {
+ filterCache = new SoftValuedHashMap(7);
+ cCache.put(type, filterCache);
+ }
+ return filterCache;
+ }
+ }
+
+ private final Class<S> mType;
+
+ // Root FilterValues, built on demand, which is immutable.
+ private transient volatile FilterValues<S> mFilterValues;
+
+ // Tail of PropertyFilterList used by mFilterValues. mFilterValues
+ // references the head.
+ private transient volatile PropertyFilterList<S> mTailPropertyFilterList;
+
+ /**
+ * Package-private constructor to prevent subclassing outside this package.
+ */
+ Filter(Class<S> type) {
+ mType = type;
+ }
+
+ /**
+ * Returns the storable type that this filter operates on.
+ */
+ public Class<S> getStorableType() {
+ return mType;
+ }
+
+ /**
+ * Returns a FilterValues instance for assigning values to a
+ * Filter. Returns null if Filter has no parameters.
+ *
+ * <p>Note: The returned FilterValues instance may reference a different
+ * filter instance than this one. Call getFilter to retrieve it. The
+ * difference is caused by the filter property values being {@link #bind bound}.
+ */
+ public FilterValues<S> initialFilterValues() {
+ if (mFilterValues == null) {
+ Filter<S> boundFilter = bind();
+
+ if (boundFilter != this) {
+ return boundFilter.initialFilterValues();
+ }
+
+ buildFilterValues();
+ }
+
+ return mFilterValues;
+ }
+
+ /**
+ * Returns tail of linked list, and so it can only be traversed by getting
+ * previous nodes.
+ *
+ * @return tail of PropertyFilterList, or null if no parameters
+ */
+ PropertyFilterList<S> getTailPropertyFilterList() {
+ if (mTailPropertyFilterList == null) {
+ buildFilterValues();
+ }
+
+ return mTailPropertyFilterList;
+ }
+
+ private void buildFilterValues() {
+ PropertyFilterList<S> list = accept(new PropertyFilterList.Builder<S>(), null);
+
+ // List should never be null since only OpenFilter and ClosedFilter
+ // have no properties, and they override initialFilterValues and
+ // getTailPropertyFilterList.
+ assert(list != null);
+
+ // Since FilterValues instances are immutable, save this for re-use.
+ mFilterValues = FilterValues.create(this, list);
+
+ // PropertyFilterList can be saved for re-use because it too is
+ // immutable (after PropertyFilterListBuilder has run).
+ mTailPropertyFilterList = list.get(-1);
+ }
+
+ /**
+ * Returns a combined filter instance that accepts records which are only
+ * accepted by this filter and the one given.
+ *
+ * @param expression query filter expression to parse
+ * @return canonical Filter instance
+ * @throws IllegalArgumentException if filter is null
+ */
+ public final Filter<S> and(String expression) {
+ return and(new FilterParser<S>(mType, expression).parseRoot());
+ }
+
+ /**
+ * Returns a combined filter instance that accepts records which are only
+ * accepted by this filter and the one given.
+ *
+ * @return canonical Filter instance
+ * @throws IllegalArgumentException if filter is null
+ */
+ public Filter<S> and(Filter<S> filter) {
+ if (filter instanceof OpenFilter) {
+ return this;
+ }
+ if (filter instanceof ClosedFilter) {
+ return filter;
+ }
+ return AndFilter.getCanonical(this, filter);
+ }
+
+ /**
+ * Returns a combined filter instance that accepts records which are only
+ * accepted by this filter and the one given.
+ *
+ * @param propertyName property name to match on, which may be a chained property
+ * @param operator relational operator
+ * @return canonical Filter instance
+ * @throws IllegalArgumentException if property is not found
+ */
+ public final Filter<S> and(String propertyName, RelOp operator) {
+ ChainedProperty<S> prop = new FilterParser<S>(mType, propertyName).parseChainedProperty();
+ return and(PropertyFilter.getCanonical(prop, operator, 0));
+ }
+
+ /**
+ * Returns a combined filter instance that accepts records which are only
+ * accepted by this filter and the one given.
+ *
+ * @param propertyName property name to match on, which may be a chained property
+ * @param operator relational operator
+ * @param constantValue constant value to match
+ * @return canonical Filter instance
+ * @throws IllegalArgumentException if property is not found
+ */
+ public final Filter<S> and(String propertyName, RelOp operator, Object constantValue) {
+ ChainedProperty<S> prop = new FilterParser<S>(mType, propertyName).parseChainedProperty();
+ return and(PropertyFilter.getCanonical(prop, operator, 0).constant(constantValue));
+ }
+
+ /**
+ * Returns a combined filter instance that accepts records which are
+ * accepted either by this filter or the one given.
+ *
+ * @param expression query filter expression to parse
+ * @return canonical Filter instance
+ * @throws IllegalArgumentException if filter is null
+ */
+ public final Filter<S> or(String expression) {
+ return or(new FilterParser<S>(mType, expression).parseRoot());
+ }
+
+ /**
+ * Returns a combined filter instance that accepts records which are
+ * accepted either by this filter or the one given.
+ *
+ * @return canonical Filter instance
+ * @throws IllegalArgumentException if filter is null
+ */
+ public Filter<S> or(Filter<S> filter) {
+ if (filter instanceof OpenFilter) {
+ return filter;
+ }
+ if (filter instanceof ClosedFilter) {
+ return this;
+ }
+ return OrFilter.getCanonical(this, filter);
+ }
+
+ /**
+ * Returns a combined filter instance that accepts records which are
+ * accepted either by this filter or the one given.
+ *
+ * @param propertyName property name to match on, which may be a chained property
+ * @param operator relational operator
+ * @return canonical Filter instance
+ * @throws IllegalArgumentException if property is not found
+ */
+ public final Filter<S> or(String propertyName, RelOp operator) {
+ ChainedProperty<S> prop = new FilterParser<S>(mType, propertyName).parseChainedProperty();
+ return or(PropertyFilter.getCanonical(prop, operator, 0));
+ }
+
+ /**
+ * Returns a combined filter instance that accepts records which are
+ * accepted either by this filter or the one given.
+ *
+ * @param propertyName property name to match on, which may be a chained property
+ * @param operator relational operator
+ * @param constantValue constant value to match
+ * @return canonical Filter instance
+ * @throws IllegalArgumentException if property is not found
+ */
+ public final Filter<S> or(String propertyName, RelOp operator, Object constantValue) {
+ ChainedProperty<S> prop = new FilterParser<S>(mType, propertyName).parseChainedProperty();
+ return or(PropertyFilter.getCanonical(prop, operator, 0).constant(constantValue));
+ }
+
+ /**
+ * Returns the logical negation of this filter.
+ *
+ * @return canonical Filter instance
+ */
+ public abstract Filter<S> not();
+
+ /**
+ * Returns an equivalent filter that is in disjunctive normal form. In this
+ * form, all logical 'and' operations are performed before all logical 'or'
+ * operations. This method often returns a filter with more terms than
+ * before.
+ *
+ * <p>The tree is also normalized such that all terms in a common logical
+ * operation are ordered left to right. For example, expressions of the
+ * form {@code "(a = ? & b = ?) & (c = ? & d = ?)"} are converted to
+ * {@code "(((a = ?) & (b = ?)) & c = ?) & d = ?"}.
+ *
+ * <p>Although the disjunctive normal filter may have more terms, it can be
+ * used to extract values from a FilterValues instance created from this
+ * filter. This works because the disjunctive normal filter is composed of
+ * the same set of PropertyFilter instances.
+ *
+ * @return canonical Filter instance
+ */
+ public final Filter<S> disjunctiveNormalForm() {
+ return bind().dnf();
+ }
+
+ final Filter<S> dnf() {
+ Filter<S> filter = this;
+ if (!filter.isDisjunctiveNormalForm()) {
+ filter = filter.buildDisjunctiveNormalForm();
+ }
+ return filter.reduce();
+ }
+
+ /**
+ * Returns an equivalent filter that is in conjunctive normal form. In this
+ * form, all logical 'or' operations are performed before all logical 'and'
+ * operations. This method often returns a filter with more terms than
+ * before.
+ *
+ * <p>The tree is also normalized such that all terms in a common logical
+ * operation are ordered left to right. For example, expressions of the
+ * form {@code "(a = ? | b = ?) | (c = ? | d = ?)"} are converted to
+ * {@code "(((a = ?) | (b = ?)) | c = ?) | d = ?"}.
+ *
+ * <p>Although the conjunctive normal filter may have more terms, it can be
+ * used to extract values from a FilterValues instance created from this
+ * filter. This works because the conjunctive normal filter is composed of
+ * the same set of PropertyFilter instances.
+ *
+ * @return canonical Filter instance
+ */
+ public final Filter<S> conjunctiveNormalForm() {
+ return bind().cnf();
+ }
+
+ final Filter<S> cnf() {
+ Filter<S> filter = this;
+ if (!filter.isConjunctiveNormalForm()) {
+ filter = filter.buildConjunctiveNormalForm();
+ }
+ return filter.reduce();
+ }
+
+ /**
+ * Accept the given visitor subclass to traverse the filter tree.
+ *
+ * @param visitor visitor to traverse through the tree
+ * @param param generic input parameter passed to visit methods
+ * @return generic return value passed from visit methods
+ */
+ public abstract <R, P> R accept(Visitor<S, R, P> visitor, P param);
+
+ /**
+ * Walks through each property filter, assigning a bind ID to it. This step
+ * is automatically performed for proper dnf/cnf conversion, and for
+ * building FilterValues.
+ *
+ * @return canonical Filter instance with bound property filters
+ */
+ public abstract Filter<S> bind();
+
+ /**
+ * Returns true if all property filters are known to be properly
+ * bound. This is a side effect of calling {@link #bind}, {@link
+ * #initialFilterValues}, {@link #disjunctiveNormalForm} or {@link
+ * #conjunctiveNormalForm}.
+ */
+ public abstract boolean isBound();
+
+ /**
+ * Identify this filter node as bound. Should only be called by Binder.
+ */
+ abstract void markBound();
+
+ /**
+ * Returns an equivalent filter with redundant terms eliminated. The tree
+ * is also normalized such that all terms in a common logical operation are
+ * ordered left to right. For example, expressions of the form
+ * {@code "(a = ? & b = ?) & (c = ? & d = ?)"} are converted to
+ * {@code "(((a = ?) & (b = ?)) & c = ?) & d = ?"}.
+ *
+ * @return canonical Filter instance
+ */
+ public final Filter<S> reduce() {
+ return isReduced() ? this : accept(new Reducer<S>(), null);
+ }
+
+ abstract Filter<S> buildDisjunctiveNormalForm();
+
+ abstract Filter<S> buildConjunctiveNormalForm();
+
+ abstract boolean isDisjunctiveNormalForm();
+
+ abstract boolean isConjunctiveNormalForm();
+
+ /**
+ * Returns true if filter node is in a reduced form.
+ */
+ abstract boolean isReduced();
+
+ /**
+ * Identify this filter node as reduced. Should only be called by Reducer.
+ */
+ abstract void markReduced();
+
+ @Override
+ public abstract int hashCode();
+
+ @Override
+ public abstract boolean equals(Object obj);
+
+ /**
+ * Returns the string value of this filter, which is also parsable.
+ */
+ @Override
+ public String toString() {
+ StringBuilder buf = new StringBuilder();
+ try {
+ appendTo(buf);
+ } catch (IOException e) {
+ // Not gonna happen.
+ }
+ return buf.toString();
+ }
+
+ /**
+ * Appends the string value of this filter into the given Appendable.
+ */
+ public void appendTo(Appendable app) throws IOException {
+ appendTo(app, null);
+ }
+
+ /**
+ * Appends the string value of this filter into the given Appendable.
+ *
+ * @param values optionally supply filter values
+ */
+ public abstract void appendTo(Appendable app, FilterValues<S> values)
+ throws IOException;
+
+ /**
+ * Prints a tree representation of the filter to the given Appendable.
+ */
+ public void dumpTree(Appendable app) throws IOException {
+ dumpTree(app, 0);
+ }
+
+ abstract void dumpTree(Appendable app, int indentLevel) throws IOException;
+}
diff --git a/src/main/java/com/amazon/carbonado/filter/FilterParser.java b/src/main/java/com/amazon/carbonado/filter/FilterParser.java
new file mode 100644
index 0000000..5c483e0
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/filter/FilterParser.java
@@ -0,0 +1,316 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.filter;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+
+import com.amazon.carbonado.Storable;
+import com.amazon.carbonado.MalformedFilterException;
+
+import com.amazon.carbonado.info.ChainedProperty;
+import com.amazon.carbonado.info.StorableInfo;
+import com.amazon.carbonado.info.StorableIntrospector;
+import com.amazon.carbonado.info.StorableProperty;
+
+/**
+ *
+ *
+ * @author Brian S O'Neill
+ */
+class FilterParser<S extends Storable> {
+ private final Class<S> mType;
+ private final String mFilter;
+ private int mPos;
+
+ FilterParser(Class<S> type, String filter) {
+ if (type == null) {
+ throw new IllegalArgumentException();
+ }
+ if (filter == null) {
+ throw new IllegalArgumentException("Query filter must not be null");
+ }
+ mType = type;
+ mFilter = filter;
+ }
+
+ // Design note: This parser is actually a scanner, parser, and type checker
+ // all rolled into one. This is okay since the grammar is so simple.
+
+ Filter<S> parseRoot() {
+ Filter<S> filter = parseFilter();
+ int c = nextCharIgnoreWhitespace();
+ if (c >= 0) {
+ mPos--;
+ throw error("Unexpected trailing characters");
+ }
+ return filter;
+ }
+
+ private Filter<S> parseFilter() {
+ return parseOrFilter();
+ }
+
+ private Filter<S> parseOrFilter() {
+ Filter<S> filter = parseAndFilter();
+ while (true) {
+ int c = nextCharIgnoreWhitespace();
+ if (c == '|') {
+ operatorCheck();
+ filter = filter.or(parseAndFilter());
+ } else {
+ mPos--;
+ break;
+ }
+ }
+ return filter;
+ }
+
+ private Filter<S> parseAndFilter() {
+ Filter<S> filter = parseNotFilter();
+ while (true) {
+ int c = nextCharIgnoreWhitespace();
+ if (c == '&') {
+ operatorCheck();
+ filter = filter.and(parseNotFilter());
+ } else {
+ mPos--;
+ break;
+ }
+ }
+ return filter;
+ }
+
+ private Filter<S> parseNotFilter() {
+ int c = nextCharIgnoreWhitespace();
+ if (c == '!') {
+ return parseEntityFilter().not();
+ } else {
+ mPos--;
+ return parseEntityFilter();
+ }
+ }
+
+ private Filter<S> parseEntityFilter() {
+ int c = nextCharIgnoreWhitespace();
+ if (c == '(') {
+ Filter<S> test = parseFilter();
+ c = nextCharIgnoreWhitespace();
+ if (c != ')') {
+ mPos--;
+ throw error("Right paren expected");
+ }
+ return test;
+ } else {
+ mPos--;
+ return parsePropertyFilter();
+ }
+ }
+
+ private PropertyFilter<S> parsePropertyFilter() {
+ ChainedProperty<S> chained = parseChainedProperty();
+ int c = nextCharIgnoreWhitespace();
+
+ RelOp op;
+ switch (c) {
+ case '=':
+ op = RelOp.EQ;
+ operatorCheck();
+ break;
+ case '!':
+ c = nextChar();
+ if (c == '=') {
+ op = RelOp.NE;
+ } else {
+ mPos--;
+ throw error("Inequality operator must be specified as '!='");
+ }
+ operatorCheck();
+ break;
+ case '<':
+ c = nextChar();
+ if (c == '=') {
+ op = RelOp.LE;
+ } else {
+ mPos--;
+ op = RelOp.LT;
+ }
+ operatorCheck();
+ break;
+ case '>':
+ c = nextChar();
+ if (c == '=') {
+ op = RelOp.GE;
+ } else {
+ mPos--;
+ op = RelOp.GT;
+ }
+ operatorCheck();
+ break;
+ case '?': case ':':
+ mPos--;
+ throw error("Relational operator missing");
+ case -1:
+ throw error("Relational operator expected");
+ default:
+ mPos--;
+ throw error("Unexpected operator character: '" + (char)c + '\'');
+ }
+
+ c = nextCharIgnoreWhitespace();
+
+ if (c != '?') {
+ mPos--;
+ throw error("Parameter placeholder '?' required");
+ }
+
+ return PropertyFilter.getCanonical(chained, op, 0);
+ }
+
+ private void operatorCheck() {
+ int c = nextChar();
+ mPos--;
+ switch (c) {
+ case -1:
+ case '?': case ':':
+ case '(': case ')':
+ case ' ': case '\r': case '\n': case '\t': case '\0':
+ return;
+ default:
+ if (Character.isWhitespace(c)) {
+ return;
+ }
+ }
+ if (!Character.isJavaIdentifierStart(c)) {
+ throw error("Unknown operator");
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ ChainedProperty<S> parseChainedProperty() {
+ String ident = parseIdentifier();
+ StorableProperty<S> prime =
+ StorableIntrospector.examine(mType).getAllProperties().get(ident);
+ if (prime == null) {
+ mPos -= ident.length();
+ throw error("Property \"" + ident + "\" not found for type: \"" +
+ mType.getName() + '"');
+ }
+
+ if (nextCharIgnoreWhitespace() != '.') {
+ mPos--;
+ return ChainedProperty.get(prime);
+ }
+
+ List<StorableProperty<?>> chain = new ArrayList<StorableProperty<?>>(4);
+ Class<?> type = prime.isJoin() ? prime.getJoinedType() : prime.getType();
+
+ while (true) {
+ ident = parseIdentifier();
+ if (Storable.class.isAssignableFrom(type)) {
+ StorableInfo<?> info =
+ StorableIntrospector.examine((Class<? extends Storable>) type);
+ Map<String, ? extends StorableProperty<?>> props = info.getAllProperties();
+ StorableProperty<?> prop = props.get(ident);
+ if (prop == null) {
+ mPos -= ident.length();
+ throw error("Property \"" + ident + "\" not found for type: \"" +
+ type.getName() + '"');
+ }
+ chain.add(prop);
+ type = prop.isJoin() ? prop.getJoinedType() : prop.getType();
+ } else {
+ throw error("Property \"" + ident + "\" not found for type \"" +
+ type.getName() + "\" because type has no properties");
+ }
+ if (nextCharIgnoreWhitespace() != '.') {
+ mPos--;
+ break;
+ }
+ }
+
+ return ChainedProperty.get(prime, (StorableProperty<?>[]) chain.toArray(new StorableProperty[chain.size()]));
+ }
+
+ private String parseIdentifier() {
+ int start = mPos;
+ int c = nextChar();
+ if (c < 0) {
+ throw error("Identifier expected");
+ }
+ if (!Character.isJavaIdentifierStart(c)) {
+ mPos--;
+ throw error("Not a valid character for start of identifier: '" + (char)c + '\'');
+ }
+ do {
+ c = nextChar();
+ } while (Character.isJavaIdentifierPart(c));
+
+ return mFilter.substring(start, --mPos);
+ }
+
+ /**
+ * Returns -1 if no more characters.
+ */
+ private int nextChar() {
+ String filter = mFilter;
+ int pos = mPos;
+ int c = (pos >= filter.length()) ? -1 : mFilter.charAt(pos);
+ mPos = pos + 1;
+ return c;
+ }
+
+ private int nextCharIgnoreWhitespace() {
+ int c;
+ while ((c = nextChar()) >= 0) {
+ switch (c) {
+ case ' ': case '\r': case '\n': case '\t': case '\0':
+ break;
+ default:
+ if (Character.isWhitespace(c)) {
+ break;
+ }
+ return c;
+ }
+ }
+ return c;
+ }
+
+ private MalformedFilterException error(String message) {
+ return error(message, mPos);
+ }
+
+ private MalformedFilterException error(String message, int pos) {
+ if (pos <= 0 || mFilter.length() == 0) {
+ message += " (at start of filter expession)";
+ } else if (pos >= mFilter.length()) {
+ message += " (at end of filter expression)";
+ } else {
+ // Show the next 20 characters, or show 17 + ellipsis if more than 20.
+ int remaining = mFilter.length() - pos;
+ if (remaining <= 20) {
+ message = message + " (at \"" + mFilter.substring(pos) + "\")";
+ } else {
+ message = message + " (at \"" + mFilter.substring(pos, pos + 17) + "...\")";
+ }
+ }
+ return new MalformedFilterException(mFilter, message, pos);
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/filter/FilterValues.java b/src/main/java/com/amazon/carbonado/filter/FilterValues.java
new file mode 100644
index 0000000..162194c
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/filter/FilterValues.java
@@ -0,0 +1,623 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.filter;
+
+import java.io.IOException;
+import java.util.IdentityHashMap;
+import java.util.Map;
+
+import com.amazon.carbonado.Storable;
+import com.amazon.carbonado.util.Appender;
+
+/**
+ * Assigns values to {@link Filter} placeholders. FilterValues instances are
+ * immutable.
+ *
+ * @author Brian S O'Neill
+ */
+public class FilterValues<S extends Storable> implements Appender {
+ private static final Object[] NO_VALUES = new Object[0];
+
+ static <S extends Storable> FilterValues<S>
+ create(Filter<S> filter, PropertyFilterList<S> propFilterList)
+ {
+ return create(filter, propFilterList, null, null);
+ }
+
+ private static <S extends Storable> FilterValues<S>
+ create(Filter<S> filter, PropertyFilterList<S> propFilterList,
+ FilterValues<S> prevValues, Object prevValue)
+ {
+ FilterValues<S> fv = new FilterValues<S>(filter, propFilterList, prevValues, prevValue);
+ PropertyFilter<S> propFilter;
+ while (propFilterList != null
+ && (propFilter = propFilterList.getPropertyFilter()).isConstant())
+ {
+ propFilterList = propFilterList.getNext();
+ fv = new FilterValues<S>(filter, propFilterList, fv, propFilter.constant());
+ }
+ return fv;
+ }
+
+ private final Filter<S> mFilter;
+ private final PropertyFilterList<S> mCurrentProperty;
+ private final FilterValues<S> mPrevValues;
+ private final Object mPrevValue;
+
+ private transient volatile Map<PropertyFilter<S>, Object> mValueMap;
+
+ private FilterValues(Filter<S> filter,
+ PropertyFilterList<S> propFilterList,
+ FilterValues<S> prevValues,
+ Object prevValue)
+ {
+ mFilter = filter;
+ mCurrentProperty = propFilterList;
+ mPrevValues = prevValues;
+ mPrevValue = prevValue;
+ }
+
+ /**
+ * Returns the Filter that this FilterValues instance applies to.
+ */
+ public Filter<S> getFilter() {
+ return mFilter;
+ }
+
+ /**
+ * Returns a new FilterValues instance with the next blank parameter filled in.
+ *
+ * @param value parameter value to fill in
+ * @throws IllegalStateException if no blank parameters
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ public FilterValues<S> with(int value) {
+ PropertyFilterList<S> current = currentProperty();
+ Object obj;
+ try {
+ obj = current.getPropertyFilter().adaptValue(value);
+ } catch (IllegalArgumentException e) {
+ throw mismatch(int.class, value);
+ }
+ return with(current, obj);
+ }
+
+ /**
+ * Returns a new FilterValues instance with the next blank parameter filled in.
+ *
+ * @param value parameter value to fill in
+ * @throws IllegalStateException if no blank parameters
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ public FilterValues<S> with(long value) {
+ PropertyFilterList<S> current = currentProperty();
+ Object obj;
+ try {
+ obj = current.getPropertyFilter().adaptValue(value);
+ } catch (IllegalArgumentException e) {
+ throw mismatch(long.class, value);
+ }
+ return with(current, obj);
+ }
+
+ /**
+ * Returns a new FilterValues instance with the next blank parameter filled in.
+ *
+ * @param value parameter value to fill in
+ * @throws IllegalStateException if no blank parameters
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ public FilterValues<S> with(float value) {
+ PropertyFilterList<S> current = currentProperty();
+ Object obj;
+ try {
+ obj = current.getPropertyFilter().adaptValue(value);
+ } catch (IllegalArgumentException e) {
+ throw mismatch(float.class, value);
+ }
+ return with(current, obj);
+ }
+
+ /**
+ * Returns a new FilterValues instance with the next blank parameter filled in.
+ *
+ * @param value parameter value to fill in
+ * @throws IllegalStateException if no blank parameters
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ public FilterValues<S> with(double value) {
+ PropertyFilterList<S> current = currentProperty();
+ Object obj;
+ try {
+ obj = current.getPropertyFilter().adaptValue(value);
+ } catch (IllegalArgumentException e) {
+ throw mismatch(double.class, value);
+ }
+ return with(current, obj);
+ }
+
+ /**
+ * Returns a new FilterValues instance with the next blank parameter filled in.
+ *
+ * @param value parameter value to fill in
+ * @throws IllegalStateException if no blank parameters
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ public FilterValues<S> with(boolean value) {
+ PropertyFilterList<S> current = currentProperty();
+ Object obj;
+ try {
+ obj = current.getPropertyFilter().adaptValue(value);
+ } catch (IllegalArgumentException e) {
+ throw mismatch(boolean.class, value);
+ }
+ return with(current, obj);
+ }
+
+ /**
+ * Returns a new FilterValues instance with the next blank parameter filled in.
+ *
+ * @param value parameter value to fill in
+ * @throws IllegalStateException if no blank parameters
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ public FilterValues<S> with(char value) {
+ PropertyFilterList<S> current = currentProperty();
+ Object obj;
+ try {
+ obj = current.getPropertyFilter().adaptValue(value);
+ } catch (IllegalArgumentException e) {
+ throw mismatch(char.class, value);
+ }
+ return with(current, obj);
+ }
+
+ /**
+ * Returns a new FilterValues instance with the next blank parameter filled in.
+ *
+ * @param value parameter value to fill in
+ * @throws IllegalStateException if no blank parameters
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ public FilterValues<S> with(byte value) {
+ PropertyFilterList<S> current = currentProperty();
+ Object obj;
+ try {
+ obj = current.getPropertyFilter().adaptValue(value);
+ } catch (IllegalArgumentException e) {
+ throw mismatch(byte.class, value);
+ }
+ return with(current, obj);
+ }
+
+ /**
+ * Returns a new FilterValues instance with the next blank parameter filled in.
+ *
+ * @param value parameter value to fill in
+ * @throws IllegalStateException if no blank parameters
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ public FilterValues<S> with(short value) {
+ PropertyFilterList<S> current = currentProperty();
+ Object obj;
+ try {
+ obj = current.getPropertyFilter().adaptValue(value);
+ } catch (IllegalArgumentException e) {
+ throw mismatch(short.class, value);
+ }
+ return with(current, obj);
+ }
+
+ /**
+ * Returns a new FilterValues instance with the next blank parameter filled in.
+ *
+ * @param value parameter value to fill in
+ * @throws IllegalStateException if no blank parameters
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ public FilterValues<S> with(Object value) {
+ PropertyFilterList<S> current = currentProperty();
+ Object obj;
+ try {
+ obj = current.getPropertyFilter().adaptValue(value);
+ } catch (IllegalArgumentException e) {
+ throw mismatch(value == null ? null : value.getClass(), value);
+ }
+ return with(current, obj);
+ }
+
+ /**
+ * Returns a new FilterValues instance with the next blank parameters filled in.
+ *
+ * @param values parameter values to fill in; if null or empty, this
+ * FilterValues instance is returned
+ * @throws IllegalStateException if no blank parameters or if too many
+ * parameter values supplied
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ public FilterValues<S> withValues(Object... values) {
+ if (values == null) {
+ return this;
+ }
+ if (values.length > getBlankParameterCount()) {
+ throw new IllegalStateException("Too many values supplied");
+ }
+ FilterValues<S> filterValues = this;
+ for (Object value : values) {
+ filterValues = filterValues.with(value);
+ }
+ return filterValues;
+ }
+
+ private FilterValues<S> with(PropertyFilterList<S> current, Object value) {
+ return create(mFilter, current.getNext(), this, value);
+ }
+
+ /**
+ * Returns the amount of values yet to be assigned.
+ *
+ */
+ public int getBlankParameterCount() {
+ return mCurrentProperty == null ? 0 : (mCurrentProperty.getNextBlankRemaining() + 1);
+ }
+
+ /**
+ * Returns the value assigned to the given PropertyFilter. If null, value
+ * may be unassigned. Call getAssignedValue to have an exception thrown
+ * instead.
+ */
+ public Object getValue(PropertyFilter<S> propFilter) {
+ return getValue(propFilter, false);
+ }
+
+ /**
+ * Returns the value assigned to the given PropertyFilter, throwing an
+ * exception if not assigned. Call getValue to have null returned instead.
+ *
+ * @throws IllegalStateException if value is blank
+ */
+ public Object getAssignedValue(PropertyFilter<S> propFilter) throws IllegalStateException {
+ return getValue(propFilter, true);
+ }
+
+ private Object getValue(PropertyFilter<S> propFilter, boolean mustBeAssigned) {
+ if (propFilter.isConstant()) {
+ return propFilter.constant();
+ }
+
+ Map<PropertyFilter<S>, Object> map = mValueMap;
+
+ if (map == null) {
+ FilterValues<S> prevValues = mPrevValues;
+ if (prevValues == null) {
+ if (mustBeAssigned) {
+ throw valueNotFound(propFilter);
+ }
+ return null;
+ }
+
+ if (prevValues.mCurrentProperty.getPreviousRemaining() < 3) {
+ // Map would have few values in it, so don't bother building it.
+
+ FilterValues<S> filterValues = this;
+ do {
+ if (propFilter == prevValues.mCurrentProperty.getPropertyFilter()) {
+ return filterValues.mPrevValue;
+ }
+ filterValues = prevValues;
+ prevValues = prevValues.mPrevValues;
+ } while (prevValues != null);
+
+ if (mustBeAssigned) {
+ throw valueNotFound(propFilter);
+ }
+ return null;
+ }
+
+ map = buildValueMap();
+ }
+
+ Object value = map.get(propFilter);
+ if (value == null && mustBeAssigned && !map.containsKey(propFilter)) {
+ throw valueNotFound(propFilter);
+ }
+
+ return value;
+ }
+
+ /**
+ * Returns true if a value is assigned to the given PropertyFilter.
+ */
+ public boolean isAssigned(PropertyFilter<S> propFilter) {
+ if (propFilter.isConstant()) {
+ return true;
+ }
+
+ Map<PropertyFilter<S>, Object> map = mValueMap;
+
+ if (map == null) {
+ FilterValues<S> prevValues = mPrevValues;
+ if (prevValues == null) {
+ return false;
+ }
+
+ if (prevValues.mCurrentProperty.getPreviousRemaining() < 3) {
+ // Map would have few values in it, so don't bother building it.
+
+ do {
+ if (propFilter == prevValues.mCurrentProperty.getPropertyFilter()) {
+ return true;
+ }
+ prevValues = prevValues.mPrevValues;
+ } while (prevValues != null);
+
+ return false;
+ }
+
+ map = buildValueMap();
+ }
+
+ return map.containsKey(propFilter);
+ }
+
+ private Map<PropertyFilter<S>, Object> buildValueMap() {
+ Map<PropertyFilter<S>, Object> map =
+ new IdentityHashMap<PropertyFilter<S>, Object>();
+
+ FilterValues<S> filterValues = this;
+ FilterValues<S> prevValues = mPrevValues;
+
+ do {
+ map.put(prevValues.mCurrentProperty.getPropertyFilter(), filterValues.mPrevValue);
+ filterValues = prevValues;
+ prevValues = prevValues.mPrevValues;
+ } while (prevValues != null);
+
+ mValueMap = map;
+ return map;
+ }
+
+ /**
+ * Returns all values in this object, including those provided by filter
+ * constants. An IllegalStateException will result if any values are blank.
+ *
+ * @return new object array
+ * @throws IllegalStateException if any values are blank
+ */
+ public Object[] getValues() throws IllegalStateException {
+ return getValuesFor(mFilter);
+ }
+
+ /**
+ * Returns all supplied values in this object. Constant filter values are
+ * not included.
+ *
+ * @return new object array
+ */
+ public Object[] getSuppliedValues() {
+ FilterValues<S> prevValues = mPrevValues;
+ if (prevValues == null) {
+ return NO_VALUES;
+ }
+
+ int i = prevValues.mCurrentProperty.getBlankCount();
+ if (i == 0) {
+ return NO_VALUES;
+ }
+ Object[] values = new Object[i];
+ FilterValues filterValues = this;
+
+ while (true) {
+ if (!filterValues.mPrevValues.mCurrentProperty.getPropertyFilter().isConstant()) {
+ values[--i] = filterValues.mPrevValue;
+ if (i <= 0) {
+ break;
+ }
+ }
+ filterValues = prevValues;
+ prevValues = prevValues.mPrevValues;
+ }
+
+ return values;
+ }
+
+ /**
+ * Returns all values in this object, as required by the given Filter. The
+ * given Filter must be composed only of the same PropertyFilter instances
+ * as used to construct this object. An IllegalStateException will result
+ * otherwise.
+ *
+ * @return new object array
+ * @throws IllegalStateException if any values are blank
+ */
+ public Object[] getValuesFor(Filter<S> filter) throws IllegalStateException {
+ // Traverse filter properties in reverse, since the filter likely was
+ // used to create this FilterValues instance. If so, then no value map
+ // needs to be constructed.
+ PropertyFilterList<S> list = filter.getTailPropertyFilterList();
+ if (list == null) {
+ return NO_VALUES;
+ }
+
+ int i = list.getPreviousRemaining() + 1;
+ Object[] values = new Object[i];
+
+ FilterValues filterValues = this;
+ FilterValues<S> prevValues = mPrevValues;
+
+ for (; --i >= 0; list = list.getPrevious()) {
+ PropertyFilter<S> propFilter = list.getPropertyFilter();
+
+ Object value;
+
+ if (prevValues != null
+ && propFilter == prevValues.mCurrentProperty.getPropertyFilter()) {
+
+ value = filterValues.mPrevValue;
+
+ filterValues = prevValues;
+ prevValues = prevValues.mPrevValues;
+ } else {
+ if (i > 0 || mValueMap != null) {
+ value = getAssignedValue(propFilter);
+ } else {
+ // No need to force value map to be created since this is
+ // the last property to be processed. Do the same scan operation
+ // as performed by buildValueMap, except don't save the results.
+
+ filterValues = this;
+ prevValues = mPrevValues;
+
+ findValue: {
+ while (prevValues != null) {
+ if (propFilter == prevValues.mCurrentProperty.getPropertyFilter()) {
+ value = filterValues.mPrevValue;
+ break findValue;
+ }
+ filterValues = prevValues;
+ prevValues = prevValues.mPrevValues;
+ }
+
+ throw valueNotFound(propFilter);
+ }
+ }
+ }
+
+ values[i] = value;
+ }
+
+ return values;
+ }
+
+ private IllegalStateException valueNotFound(PropertyFilter<S> propFilter) {
+ return new IllegalStateException
+ ("Property value not found for: \"" + propFilter + "\" in filter \"" + this + '"');
+ }
+
+ @Override
+ public int hashCode() {
+ int hash = mFilter.hashCode();
+ if (mPrevValue != null) {
+ hash += mPrevValue.hashCode();
+ }
+ if (mPrevValues != null) {
+ hash += mPrevValues.hashCode();
+ }
+ return hash;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj instanceof FilterValues) {
+ FilterValues<?> other = (FilterValues<?>) obj;
+ return mFilter.equals(other.mFilter)
+ && mCurrentProperty == other.mCurrentProperty
+ && (mPrevValues == null ? other.mPrevValues == null
+ : mPrevValues.equals(other.mPrevValues))
+ && (mPrevValue == null ? other.mPrevValue == null
+ : mPrevValue.equals(other.mPrevValue));
+ }
+ return false;
+ }
+
+ /**
+ * Returns the string value of the filter with any values substituted.
+ */
+ @Override
+ public String toString() {
+ StringBuilder buf = new StringBuilder();
+ try {
+ appendTo(buf);
+ } catch (java.io.IOException e) {
+ // Not gonna happen.
+ }
+ return buf.toString();
+ }
+
+ public void appendTo(Appendable app) throws IOException {
+ mFilter.appendTo(app, this);
+ }
+
+ private PropertyFilterList<S> currentProperty() {
+ PropertyFilterList<S> current = mCurrentProperty;
+ if (current == null) {
+ throw new IllegalStateException("No blank parameters");
+ }
+ return current;
+ }
+
+ private IllegalArgumentException mismatch(Class<?> actualType, Object actualValue) {
+ PropertyFilterList<S> current = currentProperty();
+ PropertyFilter<S> propFilter = current.getPropertyFilter();
+
+ StringBuilder b = new StringBuilder();
+
+ try {
+ propFilter.appendMismatchMessage(b, actualType, actualValue);
+ } catch (IOException e) {
+ // Not gonna happen
+ }
+
+ int subFilterCount = current.getPreviousRemaining() + current.getNextRemaining() + 1;
+
+ if (subFilterCount <= 1) {
+ b.append(" for filter \"");
+ b.append(propFilter);
+ b.append('"');
+ } else {
+ b.append(" for ");
+ appendOrdinal(b, current.getPreviousRemaining() + 1);
+ b.append(" sub filter in \"");
+ try {
+ appendTo(b);
+ } catch (IOException e) {
+ // Not gonna happen
+ }
+ b.append('"');
+ }
+
+ return new IllegalArgumentException(b.toString());
+ }
+
+ private void appendOrdinal(StringBuilder b, int value) {
+ b.append(value);
+
+ if (value != 11 && value != 12 && value != 13) {
+ value = value % 10;
+ switch (value) {
+ default:
+ break;
+ case 1:
+ b.append("st");
+ return;
+ case 2:
+ b.append("nd");
+ return;
+ case 3:
+ b.append("rd");
+ return;
+ }
+ }
+
+ b.append("th");
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/filter/Group.java b/src/main/java/com/amazon/carbonado/filter/Group.java
new file mode 100644
index 0000000..6805bf4
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/filter/Group.java
@@ -0,0 +1,134 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.filter;
+
+import java.util.Iterator;
+import java.util.LinkedHashSet;
+import java.util.Set;
+
+import com.amazon.carbonado.Storable;
+
+/**
+ * Group of filter nodes that are all 'or'ed or 'and'ed together.
+ *
+ * @author Brian S O'Neill
+ */
+class Group<S extends Storable> {
+ final boolean mForAnd;
+ Set<Filter<S>> mChildren;
+
+ Group(boolean forAnd) {
+ mForAnd = forAnd;
+ }
+
+ boolean add(Filter<S> child) {
+ if (mChildren == null) {
+ mChildren = new LinkedHashSet<Filter<S>>(20);
+ }
+ return mChildren.add(child);
+ }
+
+ /**
+ * Reduce the group set by eliminating redundant children. The
+ * transformations applied are:
+ *
+ * ((a & b) | b) => b
+ * ((a | b) & b) => b
+ */
+ void reduce() {
+ Iterator<Filter<S>> it = mChildren.iterator();
+ aLoop:
+ while (it.hasNext()) {
+ Filter<S> a = it.next();
+ for (Filter<S> b : mChildren) {
+ if (a != b) {
+ if (a.accept(new Scanner<S>(!mForAnd), b)) {
+ it.remove();
+ continue aLoop;
+ }
+ }
+ }
+ }
+ }
+
+ Filter<S> merge() {
+ Filter<S> filter = null;
+ if (mChildren != null) {
+ for (Filter<S> child : mChildren) {
+ if (filter == null) {
+ filter = child;
+ } else if (mForAnd) {
+ filter = filter.and(child);
+ } else {
+ filter = filter.or(child);
+ }
+ }
+ }
+ return filter;
+ }
+
+ /**
+ * Does the work of reducing a group
+ */
+ private static class Scanner<S extends Storable> extends Visitor<S, Boolean, Filter<S>>{
+ private final boolean mForAnd;
+
+ Scanner(boolean forAnd) {
+ mForAnd = forAnd;
+ }
+
+ /**
+ * @return TRUE if overlap was found
+ */
+ @Override
+ public Boolean visit(OrFilter<S> filter, Filter<S> child) {
+ if (mForAnd) {
+ return false;
+ }
+ if (filter == child) {
+ return true;
+ }
+ return filter.getLeftFilter().accept(this, child) ||
+ filter.getRightFilter().accept(this, child);
+ }
+
+ /**
+ * @return TRUE if overlap was found
+ */
+ @Override
+ public Boolean visit(AndFilter<S> filter, Filter<S> child) {
+ if (!mForAnd) {
+ return false;
+ }
+ if (filter == child) {
+ return true;
+ }
+ return filter.getLeftFilter().accept(this, child) ||
+ filter.getRightFilter().accept(this, child);
+ }
+
+ /**
+ * @return TRUE if overlap was found
+ */
+ @Override
+ public Boolean visit(PropertyFilter<S> filter, Filter<S> child) {
+ return filter == child;
+ }
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/filter/OpenFilter.java b/src/main/java/com/amazon/carbonado/filter/OpenFilter.java
new file mode 100644
index 0000000..407aed0
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/filter/OpenFilter.java
@@ -0,0 +1,127 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.filter;
+
+import java.io.IOException;
+
+import com.amazon.carbonado.Storable;
+
+/**
+ * Filter which lets all results pass through.
+ *
+ * @author Brian S O'Neill
+ */
+public class OpenFilter<S extends Storable> extends Filter<S> {
+ OpenFilter(Class<S> type) {
+ super(type);
+ }
+
+ public Filter<S> and(Filter<S> filter) {
+ return filter;
+ }
+
+ public Filter<S> or(Filter<S> filter) {
+ return this;
+ }
+
+ public Filter<S> not() {
+ return getClosedFilter(getStorableType());
+ }
+
+ @Override
+ public FilterValues<S> initialFilterValues() {
+ return null;
+ }
+
+ @Override
+ PropertyFilterList<S> getTailPropertyFilterList() {
+ return null;
+ }
+
+ public <R, P> R accept(Visitor<S, R, P> visitor, P param) {
+ return visitor.visit(this, param);
+ }
+
+ public Filter<S> bind() {
+ return this;
+ }
+
+ public boolean isBound() {
+ return true;
+ }
+
+ void markBound() {
+ }
+
+ Filter<S> buildDisjunctiveNormalForm() {
+ return this;
+ }
+
+ Filter<S> buildConjunctiveNormalForm() {
+ return this;
+ }
+
+ boolean isDisjunctiveNormalForm() {
+ return true;
+ }
+
+ boolean isConjunctiveNormalForm() {
+ return true;
+ }
+
+ boolean isReduced() {
+ return true;
+ }
+
+ void markReduced() {
+ }
+
+ @Override
+ public int hashCode() {
+ return getStorableType().hashCode();
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj instanceof OpenFilter) {
+ OpenFilter<?> other = (OpenFilter<?>) obj;
+ return getStorableType() == other.getStorableType();
+ }
+ return false;
+ }
+
+ @Override
+ public String toString() {
+ return "open";
+ }
+
+ public void appendTo(Appendable app, FilterValues<S> values) throws IOException {
+ app.append("open");
+ }
+
+ void dumpTree(Appendable app, int indentLevel) throws IOException {
+ for (int i=0; i<indentLevel; i++) {
+ app.append(" ");
+ }
+ app.append("open");
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/filter/OrFilter.java b/src/main/java/com/amazon/carbonado/filter/OrFilter.java
new file mode 100644
index 0000000..027ea21
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/filter/OrFilter.java
@@ -0,0 +1,128 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.filter;
+
+import java.io.IOException;
+
+import com.amazon.carbonado.Storable;
+
+/**
+ * Filter tree node that performs a logical 'or' test.
+ *
+ * @author Brian S O'Neill
+ */
+public class OrFilter<S extends Storable> extends BinaryOpFilter<S> {
+ /**
+ * Returns a canonical instance.
+ *
+ * @throws IllegalArgumentException if either filter is null
+ */
+ @SuppressWarnings("unchecked")
+ static <S extends Storable> OrFilter<S> getCanonical(Filter<S> left, Filter<S> right) {
+ return (OrFilter<S>) cCanonical.put(new OrFilter<S>(left, right));
+ }
+
+ /**
+ * @throws IllegalArgumentException if either filter is null
+ */
+ private OrFilter(Filter<S> left, Filter<S> right) {
+ super(left, right);
+ }
+
+ public Filter<S> not() {
+ return mLeft.not().and(mRight.not());
+ }
+
+ public <R, P> R accept(Visitor<S, R, P> visitor, P param) {
+ return visitor.visit(this, param);
+ }
+
+ Filter<S> buildDisjunctiveNormalForm() {
+ return mLeft.dnf().or(mRight.dnf()).reduce();
+ }
+
+ Filter<S> buildConjunctiveNormalForm() {
+ Filter<S> left = mLeft.reduce().cnf();
+ Filter<S> right = mRight.reduce().cnf();
+ if (left instanceof AndFilter) {
+ return left.accept(new Distributer<S>(true, false), right).reduce().cnf();
+ }
+ if (right instanceof AndFilter) {
+ return right.accept(new Distributer<S>(false, false), left).reduce().cnf();
+ }
+ return left.or(right).reduce();
+ }
+
+ boolean checkIsDisjunctiveNormalForm() {
+ return mLeft.isDisjunctiveNormalForm() && mRight.isDisjunctiveNormalForm();
+ }
+
+ boolean checkIsConjunctiveNormalForm() {
+ return (!(mLeft instanceof AndFilter))
+ && (!(mRight instanceof AndFilter))
+ && mLeft.isConjunctiveNormalForm()
+ && mRight.isConjunctiveNormalForm();
+ }
+
+ @Override
+ public int hashCode() {
+ return mLeft.hashCode() * 31 + mRight.hashCode();
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj instanceof OrFilter) {
+ OrFilter<?> other = (OrFilter<?>) obj;
+ return getStorableType() == other.getStorableType()
+ && mLeft.equals(other.mLeft) && mRight.equals(other.mRight);
+ }
+ return false;
+ }
+
+ public void appendTo(Appendable app, FilterValues<S> values) throws IOException {
+ if (mLeft instanceof AndFilter) {
+ app.append('(');
+ mLeft.appendTo(app, values);
+ app.append(')');
+ } else {
+ mLeft.appendTo(app, values);
+ }
+ app.append(" | ");
+ if (mRight instanceof AndFilter) {
+ app.append('(');
+ mRight.appendTo(app, values);
+ app.append(')');
+ } else {
+ mRight.appendTo(app, values);
+ }
+ }
+
+ void dumpTree(Appendable app, int indentLevel) throws IOException {
+ mRight.dumpTree(app, indentLevel + 1);
+ for (int i=0; i<indentLevel; i++) {
+ app.append(" ");
+ }
+ app.append("or");
+ app.append('\n');
+ mLeft.dumpTree(app, indentLevel + 1);
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/filter/PropertyFilter.java b/src/main/java/com/amazon/carbonado/filter/PropertyFilter.java
new file mode 100644
index 0000000..8fe03d6
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/filter/PropertyFilter.java
@@ -0,0 +1,472 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.filter;
+
+import java.io.IOException;
+
+import org.cojen.classfile.TypeDesc;
+
+import com.amazon.carbonado.Storable;
+import com.amazon.carbonado.info.ChainedProperty;
+
+/**
+ * Filter tree node that performs a relational test against a specific property
+ * value.
+ *
+ * @author Brian S O'Neill
+ */
+public class PropertyFilter<S extends Storable> extends Filter<S> {
+ // Indicates property has been bound to a constant value.
+ private static int BOUND_CONSTANT = -1;
+
+ /**
+ * Returns a canonical instance, creating a new one if there isn't one
+ * already in the cache.
+ *
+ * @throws IllegalArgumentException if property or operator is null
+ */
+ @SuppressWarnings("unchecked")
+ static <S extends Storable> PropertyFilter<S> getCanonical(ChainedProperty<S> property,
+ RelOp op,
+ int bindID)
+ {
+ return (PropertyFilter<S>) cCanonical
+ .put(new PropertyFilter<S>(property, op, bindID, null));
+ }
+
+ /**
+ * Returns a canonical instance, creating a new one if there isn't one
+ * already in the cache.
+ *
+ * @throws IllegalArgumentException if property or operator is null
+ */
+ @SuppressWarnings("unchecked")
+ static <S extends Storable> PropertyFilter<S> getCanonical(ChainedProperty<S> property,
+ RelOp op,
+ Object constant)
+ {
+ return (PropertyFilter<S>) cCanonical
+ .put(new PropertyFilter<S>(property, op, BOUND_CONSTANT, constant));
+ }
+
+ /**
+ * Returns a canonical instance, creating a new one if there isn't one
+ * already in the cache.
+ */
+ @SuppressWarnings("unchecked")
+ static <S extends Storable> PropertyFilter<S> getCanonical(PropertyFilter<S> filter,
+ int bindID)
+ {
+ if (filter.mBindID == bindID) {
+ return filter;
+ }
+ return (PropertyFilter<S>) cCanonical
+ .put(new PropertyFilter<S>(filter.getChainedProperty(),
+ filter.getOperator(), bindID, filter.mConstant));
+ }
+
+ private final ChainedProperty<S> mProperty;
+ private final RelOp mOp;
+
+ private final int mBindID;
+
+ private final Object mConstant;
+
+ private transient volatile Class<?> mBoxedType;
+
+ /**
+ * @throws IllegalArgumentException if property or operator is null
+ */
+ private PropertyFilter(ChainedProperty<S> property, RelOp op, int bindID, Object constant) {
+ super(property == null ? null : property.getPrimeProperty().getEnclosingType());
+ if (op == null) {
+ throw new IllegalArgumentException();
+ }
+ mProperty = property;
+ mOp = op;
+ mBindID = bindID;
+ mConstant = constant;
+ }
+
+ @Override
+ public Filter<S> not() {
+ if (mBindID == BOUND_CONSTANT) {
+ return getCanonical(mProperty, mOp.reverse(), mConstant);
+ } else {
+ return getCanonical(mProperty, mOp.reverse(), mBindID);
+ }
+ }
+
+ public <R, P> R accept(Visitor<S, R, P> visitor, P param) {
+ return visitor.visit(this, param);
+ }
+
+ public ChainedProperty<S> getChainedProperty() {
+ return mProperty;
+ }
+
+ /**
+ * Returns the type of the ChainedProperty.
+ */
+ public Class<?> getType() {
+ return mProperty.getType();
+ }
+
+ /**
+ * Returns the type of the ChainedProperty property, boxed into an object
+ * if primitive.
+ */
+ public Class<?> getBoxedType() {
+ if (mBoxedType == null) {
+ mBoxedType = TypeDesc.forClass(getType()).toObjectType().toClass();
+ }
+ return mBoxedType;
+ }
+
+ public RelOp getOperator() {
+ return mOp;
+ }
+
+ /**
+ * Bind ID is used to distinguish this PropertyFilter instance from another
+ * against the same property. For example, the filter "a = ? | a = ?"
+ * references the property 'a' twice. Each '?' parameter is bound to a
+ * different value, and so the bind ID for each property filter is
+ * different. "a = ?[1] | a = ?[2]".
+ *
+ * @return assigned bind ID, or 0 if unbound
+ */
+ public int getBindID() {
+ return mBindID;
+ }
+
+ public Filter<S> bind() {
+ return mBindID == 0 ? getCanonical(this, 1) : this;
+ }
+
+ public boolean isBound() {
+ return mBindID != 0;
+ }
+
+ /**
+ * Returns another PropertyFilter instance which is bound to the given constant value.
+ *
+ * @throws IllegalArgumentException if value is not compatible with property type
+ */
+ public PropertyFilter<S> constant(Object value) {
+ if (mBindID == BOUND_CONSTANT) {
+ if (mConstant == null && value == null || mConstant.equals(value)) {
+ return this;
+ }
+ }
+ return getCanonical(mProperty, mOp, adaptValue(value));
+ }
+
+ /**
+ * Returns the constant value of this PropertyFilter, which is valid only
+ * if isConstant returns true.
+ */
+ public Object constant() {
+ return mConstant;
+ }
+
+ /**
+ * Returns true if this PropertyFilter has a constant value.
+ */
+ public boolean isConstant() {
+ return mBindID == BOUND_CONSTANT;
+ }
+
+ void markBound() {
+ }
+
+ Filter<S> buildDisjunctiveNormalForm() {
+ return this;
+ }
+
+ Filter<S> buildConjunctiveNormalForm() {
+ return this;
+ }
+
+ boolean isDisjunctiveNormalForm() {
+ return true;
+ }
+
+ boolean isConjunctiveNormalForm() {
+ return true;
+ }
+
+ boolean isReduced() {
+ return true;
+ }
+
+ void markReduced() {
+ }
+
+ /**
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ Object adaptValue(int value) {
+ Class<?> type = getBoxedType();
+ if (type == Integer.class) {
+ return Integer.valueOf(value);
+ } else if (type == Long.class) {
+ return Long.valueOf(value);
+ } else if (type == Double.class) {
+ return Double.valueOf(value);
+ } else if (type == Number.class || type == Object.class) {
+ return Integer.valueOf(value);
+ }
+ throw mismatch(int.class, value);
+ }
+
+ /**
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ Object adaptValue(long value) {
+ Class<?> type = getBoxedType();
+ if (type == Long.class) {
+ return Long.valueOf(value);
+ } else if (type == Number.class || type == Object.class) {
+ return Long.valueOf(value);
+ }
+ throw mismatch(long.class, value);
+ }
+
+ /**
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ Object adaptValue(float value) {
+ Class<?> type = getBoxedType();
+ if (type == Float.class) {
+ return Float.valueOf(value);
+ } else if (type == Double.class) {
+ return Double.valueOf(value);
+ } else if (type == Number.class || type == Object.class) {
+ return Float.valueOf(value);
+ }
+ throw mismatch(float.class, value);
+ }
+
+ /**
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ Object adaptValue(double value) {
+ Class<?> type = getBoxedType();
+ if (type == Double.class) {
+ return Double.valueOf(value);
+ } else if (type == Number.class || type == Object.class) {
+ return Double.valueOf(value);
+ }
+ throw mismatch(float.class, value);
+ }
+
+ /**
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ Object adaptValue(boolean value) {
+ Class<?> type = getBoxedType();
+ if (type == Boolean.class || type == Object.class) {
+ return Boolean.valueOf(value);
+ }
+ throw mismatch(boolean.class, value);
+ }
+
+ /**
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ Object adaptValue(char value) {
+ Class<?> type = getBoxedType();
+ if (type == Character.class || type == Object.class) {
+ return Character.valueOf(value);
+ } else if (type == String.class || type == CharSequence.class) {
+ return String.valueOf(value);
+ }
+ throw mismatch(char.class, value);
+ }
+
+ /**
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ Object adaptValue(byte value) {
+ Class<?> type = getBoxedType();
+ if (type == Byte.class) {
+ return Byte.valueOf(value);
+ } else if (type == Short.class) {
+ return Short.valueOf(value);
+ } else if (type == Integer.class) {
+ return Integer.valueOf(value);
+ } else if (type == Long.class) {
+ return Long.valueOf(value);
+ } else if (type == Double.class) {
+ return Double.valueOf(value);
+ } else if (type == Float.class) {
+ return Float.valueOf(value);
+ } else if (type == Number.class || type == Object.class) {
+ return Byte.valueOf(value);
+ }
+ throw mismatch(byte.class, value);
+ }
+
+ /**
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ Object adaptValue(short value) {
+ Class<?> type = getBoxedType();
+ if (type == Short.class) {
+ return Short.valueOf(value);
+ } else if (type == Integer.class) {
+ return Integer.valueOf(value);
+ } else if (type == Long.class) {
+ return Long.valueOf(value);
+ } else if (type == Double.class) {
+ return Double.valueOf(value);
+ } else if (type == Float.class) {
+ return Float.valueOf(value);
+ } else if (type == Number.class || type == Object.class) {
+ return Short.valueOf(value);
+ }
+ throw mismatch(short.class, value);
+ }
+
+ /**
+ * @throws IllegalArgumentException if type doesn't match
+ */
+ Object adaptValue(Object value) {
+ if (getBoxedType().isInstance(value)) {
+ return value;
+ }
+
+ Class<?> type = getType();
+
+ if (value == null) {
+ if (!type.isPrimitive()) {
+ return value;
+ }
+ } else if (type.isPrimitive()) {
+ TypeDesc actualPrim = TypeDesc.forClass(value.getClass()).toPrimitiveType();
+ if (actualPrim != null) {
+ if (type == actualPrim.toClass()) {
+ return value;
+ }
+ // Unbox and rebox.
+ switch (actualPrim.getTypeCode()) {
+ case TypeDesc.BYTE_CODE:
+ return adaptValue(((Number) value).byteValue());
+ case TypeDesc.SHORT_CODE:
+ return adaptValue(((Number) value).shortValue());
+ case TypeDesc.INT_CODE:
+ return adaptValue(((Number) value).intValue());
+ case TypeDesc.LONG_CODE:
+ return adaptValue(((Number) value).longValue());
+ case TypeDesc.FLOAT_CODE:
+ return adaptValue(((Number) value).floatValue());
+ case TypeDesc.DOUBLE_CODE:
+ return adaptValue(((Number) value).doubleValue());
+ case TypeDesc.BOOLEAN_CODE:
+ return adaptValue(((Boolean) value).booleanValue());
+ case TypeDesc.CHAR_CODE:
+ return adaptValue(((Character) value).charValue());
+ }
+ }
+ }
+
+ throw mismatch(value == null ? null : value.getClass(), value);
+ }
+
+ @Override
+ public int hashCode() {
+ return mProperty.hashCode() * 31 + mOp.hashCode() + mBindID;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj instanceof PropertyFilter) {
+ PropertyFilter<?> other = (PropertyFilter<?>) obj;
+ return getStorableType() == other.getStorableType()
+ && mProperty.equals(other.mProperty) && mOp.equals(other.mOp)
+ && mBindID == other.mBindID
+ && (mConstant == null
+ ? (other.mConstant == null)
+ : mConstant.equals(other.mConstant));
+ }
+ return false;
+ }
+
+ public void appendTo(Appendable app, FilterValues<S> values) throws IOException {
+ mProperty.appendTo(app);
+ app.append(' ');
+ app.append(mOp.toString());
+ app.append(' ');
+ if (values != null) {
+ Object value = values.getValue(this);
+ if (value != null || values.isAssigned(this)) {
+ app.append(String.valueOf(value));
+ return;
+ }
+ }
+ if (mBindID == BOUND_CONSTANT) {
+ app.append(String.valueOf(mConstant));
+ } else {
+ app.append('?');
+ /* Uncomment for testing
+ if (mBindID != 0) {
+ app.append('[').append(String.valueOf(mBindID)).append(']');
+ }
+ */
+ }
+ }
+
+ void appendMismatchMessage(Appendable a, Class<?> actualType, Object actualValue)
+ throws IOException
+ {
+ if (actualType == null || actualValue == null) {
+ a.append("Actual value is null, which cannot be assigned to type \"");
+ } else {
+ a.append("Actual value \"");
+ a.append(String.valueOf(actualValue));
+ a.append("\", of type \"");
+ a.append(TypeDesc.forClass(actualType).getFullName());
+ a.append("\", is incompatible with expected type of \"");
+ }
+ a.append(TypeDesc.forClass(getType()).getFullName());
+ a.append('"');
+ }
+
+ private IllegalArgumentException mismatch(Class<?> actualType, Object actualValue) {
+ StringBuilder b = new StringBuilder();
+ try {
+ appendMismatchMessage(b, actualType, actualValue);
+ } catch (IOException e) {
+ // Not gonna happen
+ }
+ return new IllegalArgumentException(b.toString());
+ }
+
+ void dumpTree(Appendable app, int indentLevel) throws IOException {
+ for (int i=0; i<indentLevel; i++) {
+ app.append(" ");
+ }
+ appendTo(app);
+ app.append('\n');
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/filter/PropertyFilterList.java b/src/main/java/com/amazon/carbonado/filter/PropertyFilterList.java
new file mode 100644
index 0000000..447edef
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/filter/PropertyFilterList.java
@@ -0,0 +1,186 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.filter;
+
+import com.amazon.carbonado.Storable;
+
+/**
+ * Double linked list of leaf PropertyFilters in a Filter. The list order
+ * matches the left-to-right order of the PropertyFilters.
+ *
+ * @author Brian S O'Neill
+ */
+class PropertyFilterList<S extends Storable> {
+ private final PropertyFilter<S> mPropFilter;
+ private final PropertyFilterList<S> mNext;
+ private final int mNextRemaining;
+ private final int mNextBlankRemaining;
+
+ private PropertyFilterList<S> mPrev;
+ private int mPrevRemaining = -1;
+ private int mBlankCount = -1;
+
+ /**
+ * @param next pass null for tail of list
+ */
+ PropertyFilterList(PropertyFilter<S> propFilter, PropertyFilterList<S> next) {
+ mPropFilter = propFilter;
+ mNext = next;
+ mNextRemaining = next == null ? 0 : next.mNextRemaining + 1;
+ mNextBlankRemaining = next == null ? 0
+ : (next.mNextBlankRemaining + (next.mPropFilter.isConstant() ? 0 : 1));
+ }
+
+ public PropertyFilter<S> getPropertyFilter() {
+ return mPropFilter;
+ }
+
+ public Class<?> getNaturalPropertyType() {
+ return mPropFilter.getType();
+ }
+
+ /**
+ * Returns the property filter type, always represented as an object
+ * type. Primitive types are represented by a wrapper class.
+ */
+ public Class<?> getObjectPropertyType() {
+ return mPropFilter.getBoxedType();
+ }
+
+ /**
+ * Returns null if the next remaining is zero.
+ */
+ public PropertyFilterList<S> getNext() {
+ return mNext;
+ }
+
+ /**
+ * Returns the amount of next remaining list nodes.
+ */
+ public int getNextRemaining() {
+ return mNextRemaining;
+ }
+
+ /**
+ * Returns the amount of next remaining non-constant list nodes.
+ */
+ public int getNextBlankRemaining() {
+ return mNextBlankRemaining;
+ }
+
+ /**
+ * Returns null if no previous node.
+ */
+ public PropertyFilterList<S> getPrevious() {
+ return mPrev;
+ }
+
+ /**
+ * Returns the amount of previous remaining list nodes.
+ */
+ public int getPreviousRemaining() {
+ int remaining = mPrevRemaining;
+ if (remaining < 0) {
+ mPrevRemaining = remaining =
+ ((mPrev == null) ? 0 : (mPrev.getPreviousRemaining() + 1));
+ }
+ return remaining;
+ }
+
+ /**
+ * Returns the amount of non-constant list nodes up to this node.
+ */
+ public int getBlankCount() {
+ int count = mBlankCount;
+ if (count < 0) {
+ mBlankCount = count = (mPropFilter.isConstant() ? 0 : 1)
+ + ((mPrev == null) ? 0 : mPrev.getBlankCount());
+ }
+ return count;
+ }
+
+ /**
+ * @param index if zero, returns this, if one, returns next, etc. If
+ * negative, gets from last. -1 returns last, -2 returns next to last, etc.
+ * @return null if index too high or too low
+ */
+ public PropertyFilterList<S> get(int index) {
+ if (index <= 0) {
+ if (index == 0) {
+ return this;
+ }
+ if ((index = mNextRemaining + index + 1) <= 0) {
+ if (index == 0) {
+ return this;
+ }
+ return null;
+ }
+ }
+ if (mNext == null) {
+ return null;
+ }
+ // Tail recursion.
+ return mNext.get(index - 1);
+ }
+
+ /**
+ * Searches list for given PropertyFilter.
+ */
+ public boolean contains(PropertyFilter<S> propFilter) {
+ if (mPropFilter == propFilter) {
+ return true;
+ }
+ if (mNext == null) {
+ return false;
+ }
+ // Tail recursion.
+ return mNext.contains(propFilter);
+ }
+
+ /**
+ * Prepend a node to the head of the list.
+ */
+ PropertyFilterList<S> prepend(PropertyFilter<S> propFilter) {
+ PropertyFilterList<S> head = new PropertyFilterList<S>(propFilter, this);
+ mPrev = head;
+ return head;
+ }
+
+ static class Builder<S extends Storable>
+ extends Visitor<S, PropertyFilterList<S>, PropertyFilterList<S>>
+ {
+ public PropertyFilterList<S> visit(OrFilter<S> filter, PropertyFilterList<S> list) {
+ // Traverse right-to-left since list must be built in this order.
+ list = filter.getRightFilter().accept(this, list);
+ list = filter.getLeftFilter().accept(this, list);
+ return list;
+ }
+
+ public PropertyFilterList<S> visit(AndFilter<S> filter, PropertyFilterList<S> list) {
+ // Traverse right-to-left since list must be built in this order.
+ list = filter.getRightFilter().accept(this, list);
+ list = filter.getLeftFilter().accept(this, list);
+ return list;
+ }
+
+ public PropertyFilterList<S> visit(PropertyFilter<S> filter, PropertyFilterList<S> list) {
+ return list == null ? new PropertyFilterList<S>(filter, null) : list.prepend(filter);
+ }
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/filter/Reducer.java b/src/main/java/com/amazon/carbonado/filter/Reducer.java
new file mode 100644
index 0000000..6e2acc1
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/filter/Reducer.java
@@ -0,0 +1,103 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.filter;
+
+import com.amazon.carbonado.Storable;
+
+/**
+ * Reduces a tree by eliminating redundant 'and' or 'or' terms. As a desired
+ * side-effect, the tree is also unbalanced to the left.
+ *
+ * @author Brian S O'Neill
+ */
+class Reducer<S extends Storable> extends Visitor<S, Filter<S>, Group<S>> {
+ Reducer() {
+ }
+
+ /**
+ * @param filter candidate node to potentially replace
+ * @param group gathered children
+ * @return original candidate or replacement
+ */
+ @Override
+ public Filter<S> visit(OrFilter<S> filter, Group<S> group) {
+ final Group<S> parentGroup = group;
+
+ boolean groupRoot;
+ if (groupRoot = (group == null || group.mForAnd)) {
+ group = new Group<S>(false);
+ }
+
+ filter.getLeftFilter().accept(this, group);
+ filter.getRightFilter().accept(this, group);
+
+ if (groupRoot) {
+ group.reduce();
+ Filter<S> result = group.merge();
+ result.markReduced();
+ if (parentGroup != null) {
+ parentGroup.add(result);
+ }
+ return result;
+ }
+
+ return null;
+ }
+
+ /**
+ * @param filter candidate node to potentially replace
+ * @param group gathered children
+ * @return original candidate or replacement
+ */
+ @Override
+ public Filter<S> visit(AndFilter<S> filter, Group<S> group) {
+ final Group<S> parentGroup = group;
+
+ boolean groupRoot;
+ if (groupRoot = (group == null || !group.mForAnd)) {
+ group = new Group<S>(true);
+ }
+
+ filter.getLeftFilter().accept(this, group);
+ filter.getRightFilter().accept(this, group);
+
+ if (groupRoot) {
+ group.reduce();
+ Filter<S> result = group.merge();
+ result.markReduced();
+ if (parentGroup != null) {
+ parentGroup.add(result);
+ }
+ return result;
+ }
+
+ return null;
+ }
+
+ /**
+ * @param filter candidate node to potentially replace
+ * @param group gathered children
+ * @return original candidate or replacement
+ */
+ @Override
+ public Filter<S> visit(PropertyFilter<S> filter, Group<S> group) {
+ group.add(filter);
+ return null;
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/filter/RelOp.java b/src/main/java/com/amazon/carbonado/filter/RelOp.java
new file mode 100644
index 0000000..f74d21e
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/filter/RelOp.java
@@ -0,0 +1,78 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.filter;
+
+/**
+ * Relational operator enumeration.
+ *
+ * @author Brian S O'Neill
+ */
+public enum RelOp {
+ /** Equals */
+ EQ,
+ /** Not Equals */
+ NE,
+ /** Less Than */
+ LT,
+ /** Greator than or Equal */
+ GE,
+ /** Greator Than */
+ GT,
+ /** Less than or Equal */
+ LE;
+
+ /**
+ * Returns one of "=", "!=", "<", ">=", ">", or "<=".
+ */
+ public String toString() {
+ switch (this) {
+ case EQ:
+ return "=";
+ case NE:
+ return "!=";
+ case LT:
+ return "<";
+ case GE:
+ return ">=";
+ case GT:
+ return ">";
+ case LE:
+ return "<=";
+ default:
+ return super.toString();
+ }
+ }
+
+ public RelOp reverse() {
+ switch (this) {
+ case EQ: default:
+ return NE;
+ case NE:
+ return EQ;
+ case LT:
+ return GE;
+ case GE:
+ return LT;
+ case GT:
+ return LE;
+ case LE:
+ return GT;
+ }
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/filter/Visitor.java b/src/main/java/com/amazon/carbonado/filter/Visitor.java
new file mode 100644
index 0000000..77ca07f
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/filter/Visitor.java
@@ -0,0 +1,55 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.amazon.carbonado.filter;
+
+import com.amazon.carbonado.Storable;
+
+/**
+ * Traverses a filter tree in its canonical order. By overriding a visit
+ * method, individual nodes can be captured and processed based on their
+ * type. Call super.visit inside the overridden visit method to ensure that the
+ * node's children are properly traversed.
+ *
+ * @author Brian S O'Neill
+ */
+public abstract class Visitor<S extends Storable, R, P> {
+ public R visit(OrFilter<S> filter, P param) {
+ filter.getLeftFilter().accept(this, param);
+ filter.getRightFilter().accept(this, param);
+ return null;
+ }
+
+ public R visit(AndFilter<S> filter, P param) {
+ filter.getLeftFilter().accept(this, param);
+ filter.getRightFilter().accept(this, param);
+ return null;
+ }
+
+ public R visit(PropertyFilter<S> filter, P param) {
+ return null;
+ }
+
+ public R visit(OpenFilter<S> filter, P param) {
+ return null;
+ }
+
+ public R visit(ClosedFilter<S> filter, P param) {
+ return null;
+ }
+}
diff --git a/src/main/java/com/amazon/carbonado/filter/package-info.java b/src/main/java/com/amazon/carbonado/filter/package-info.java
new file mode 100644
index 0000000..b52a049
--- /dev/null
+++ b/src/main/java/com/amazon/carbonado/filter/package-info.java
@@ -0,0 +1,24 @@
+/*
+ * Copyright 2006 Amazon Technologies, Inc. or its affiliates.
+ * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks
+ * of Amazon Technologies, Inc. or its affiliates. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/**
+ * Contains classes for representing query filters.
+ *
+ * @see com.amazon.carbonado.filter.Filter
+ */
+package com.amazon.carbonado.filter;
--
cgit v1.2.3