Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[4004] branches/QUADS_QUERY_BRANCH/bigdata/src
|
From: <tho...@us...> - 2010-12-12 22:22:09
|
Revision: 4004
http://bigdata.svn.sourceforge.net/bigdata/?rev=4004&view=rev
Author: thompsonbry
Date: 2010-12-12 22:22:01 +0000 (Sun, 12 Dec 2010)
Log Message:
-----------
Added the concept of stackable symbol tables to IBindingSet (push(),pop()) to support optional join groups.
Added a new ListBindingSet implementation which should be more efficient than the HashBindingSet, which is our current mutable implementation of choice.
Added Serialization tests to the IBindingSet implementations.
Modified DistinctBindingSetOp, which used a constructor which is no longer public.
Modified Paths:
--------------
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/IBindingSet.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/bindingSet/ArrayBindingSet.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/bindingSet/EmptyBindingSet.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/bindingSet/HashBindingSet.java
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/solutions/DistinctBindingSetOp.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/bindingSet/TestAll.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/bindingSet/TestArrayBindingSet.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/bindingSet/TestIBindingSet.java
Added Paths:
-----------
branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/bindingSet/ListBindingSet.java
branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/bindingSet/TestListBindingSet.java
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/IBindingSet.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/IBindingSet.java 2010-12-11 16:04:20 UTC (rev 4003)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/IBindingSet.java 2010-12-12 22:22:01 UTC (rev 4004)
@@ -103,14 +103,22 @@
* The #of bound variables.
*/
public int size();
-
- /**
- * Visits the bindings.
- */
+
+ /**
+ * Visits the bindings.
+ *
+ * @todo The unit tests verify that the implementations do not permit
+ * mutation using the iterator, but that is not actually specified by
+ * the API as forbidden.
+ */
public Iterator<Map.Entry<IVariable,IConstant>> iterator();
/**
* Visits the bound variables.
+ *
+ * @todo The unit tests verify that the implementations do not permit
+ * mutation using the iterator, but that is not actually specified by
+ * the API as forbidden.
*/
public Iterator<IVariable> vars();
@@ -118,13 +126,17 @@
* Return a shallow copy of the binding set.
*/
public IBindingSet clone();
-
- /**
- * Return a shallow copy of the binding set, eliminating unnecessary
- * variables.
- */
+
+ /**
+ * Return a shallow copy of the binding set, eliminating unnecessary
+ * variables.
+ *
+ * @param variablesToKeep
+ * When non-<code>null</code>, only the listed variables are
+ * retained.
+ */
public IBindingSet copy(IVariable[] variablesToKeep);
-
+
/**
* True iff the variables and their bound values are the same
* for the two binding sets.
@@ -134,15 +146,49 @@
*/
public boolean equals(Object o);
- /**
- * The hash code of a binding is defined as the bit-wise XOR of the hash
- * codes of the {@link IConstant}s for its bound variables. Unbound
- * variables are ignored when computing the hash code. Binding sets are
- * unordered collections, therefore the calculated hash code intentionally
- * does not dependent on the order in which the bindings are iterated over.
- * The hash code reflects the current state of the bindings and must be
- * recomputed if the bindings are changed.
- */
+ /**
+ * The hash code of a binding is defined as the bit-wise XOR of the hash
+ * codes of the {@link IConstant}s for its bound variables. Unbound
+ * variables are ignored when computing the hash code. Binding sets are
+ * unordered collections, therefore the calculated hash code intentionally
+ * does not depend on the order in which the bindings are visited. The hash
+ * code reflects the current state of the bindings and must be recomputed if
+ * the bindings are changed.
+ */
public int hashCode();
-
+
+ /**
+ * Make a copy of the current symbol table (aka current variable bindings)
+ * and push it onto onto the stack. Variable bindings will be made against
+ * the current symbol table. The symbol table stack is propagated by
+ * {@link #clone()} and {@link #copy(IVariable[])}. Symbols tables may be
+ * used to propagate conditional bindings through a data flow until a
+ * decision point is reached, at which point they may be either discarded or
+ * committed. This mechanism may be used to support SPARQL style optional
+ * join groups.
+ *
+ * @throws UnsupportedOperationException
+ * if the {@link IBindingSet} is not mutable.
+ *
+ * @see #pop(boolean)
+ */
+ public void push();
+
+ /**
+ * Pop the current symbol table off of the stack.
+ *
+ * @param save
+ * When <code>true</code>, the bindings on the current symbol
+ * table are copied to the parent symbol table before the current
+ * symbol table is popped off of the stack. If <code>false</code>
+ * , any bindings associated with that symbol table are
+ * discarded.
+ *
+ * @throws IllegalStateException
+ * if there is no nested symbol table.
+ *
+ * @see #push()
+ */
+ public void pop(boolean save);
+
}
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/bindingSet/ArrayBindingSet.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/bindingSet/ArrayBindingSet.java 2010-12-11 16:04:20 UTC (rev 4003)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/bindingSet/ArrayBindingSet.java 2010-12-12 22:22:01 UTC (rev 4004)
@@ -28,14 +28,14 @@
package com.bigdata.bop.bindingSet;
+import java.io.Serializable;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.Map;
+import java.util.Stack;
import java.util.Map.Entry;
-import org.apache.log4j.Logger;
-
import com.bigdata.bop.IBindingSet;
import com.bigdata.bop.IConstant;
import com.bigdata.bop.IVariable;
@@ -54,36 +54,389 @@
private static final long serialVersionUID = -6468905602211956490L;
- private static final Logger log = Logger.getLogger(ArrayBindingSet.class);
+// private static final Logger log = Logger.getLogger(ArrayBindingSet.class);
/**
- * A dense array of the bound variables.
+ * A symbol table implemented by two correlated arrays.
*/
- private final IVariable[] vars;
+ private static class ST implements Serializable {
+
+ /**
+ *
+ */
+ private static final long serialVersionUID = 1L;
+
+ /**
+ * A dense array of the bound variables.
+ */
+ private final IVariable[] vars;
+
+ /**
+ * A dense array of the values bound to the variables (correlated with
+ * {@link #vars}).
+ */
+ private final IConstant[] vals;
+
+ /**
+ * The #of entries in the arrays which have defined values.
+ */
+ private int nbound = 0;
+
+ private ST(final int nbound,final IVariable[] vars, final IConstant[] vals) {
+ this.nbound = nbound;
+ this.vars = vars;
+ this.vals = vals;
+ }
+
+ public IConstant get(final IVariable var) {
+
+ if (var == null)
+ throw new IllegalArgumentException();
+
+ for (int i = 0; i < nbound; i++) {
+
+ if (vars[i] == var) {
+
+ return vals[i];
+
+ }
+
+ }
+
+ return null;
+
+ }
+
+ void set(final IVariable var, final IConstant val) {
+
+ if (var == null)
+ throw new IllegalArgumentException();
+
+ if (val == null)
+ throw new IllegalArgumentException();
+
+ for (int i = 0; i < nbound; i++) {
+
+ if (vars[i] == var) {
+
+ vals[i] = val;
+
+ return;
+
+ }
+
+ }
+
+ vars[nbound] = var;
+
+ vals[nbound] = val;
+
+ nbound++;
+
+ }
+
+ void clearAll() {
+
+ for (int i = nbound - 1; nbound > 0; i--, nbound--) {
+
+ vars[i] = null;
+
+ vals[i] = null;
+
+ }
+
+ assert nbound == 0;
+
+ }
+
+ /**
+ * Since the array is dense (no gaps), {@link #clear(IVariable)}
+ * requires that we copy down any remaining elements in the array by one
+ * position.
+ *
+ * @return <code>true</code> if the data structure was modified by the
+ * operation.
+ */
+ boolean clear(final IVariable var) {
+
+ if (var == null)
+ throw new IllegalArgumentException();
+
+ for (int i = 0; i < nbound; i++) {
+
+ if (vars[i] == var) {
+
+ final int nremaining = nbound-(i+1);
+
+ if (nremaining >= 0) {
+
+ // Copy down to close up the gap!
+ System.arraycopy(vars, i+1, vars, i, nremaining);
+
+ System.arraycopy(vals, i+1, vals, i, nremaining);
+
+ } else {
+
+ // Just clear the reference.
+
+ vars[i] = null;
+
+ vals[i] = null;
+
+ }
+
+ nbound--;
+
+ return true;
+
+ }
+
+ }
+
+ return false;
+
+ }
+
+ }
+
+ /**
+ * The stack of symbol tables. Each symbol table is a mapping from an
+ * {@link IVariable} onto its non-<code>null</code> bound {@link IConstant}.
+ * The stack is initialized with an empty symbol table. Symbol tables may be
+ * pushed onto the stack or popped off of the stack, but the stack MAY NOT
+ * become empty.
+ */
+ private final Stack<ST> stack;
+
+ /**
+ * Return the symbol table on the top of the stack.
+ */
+ private ST current() {
+
+ return stack.peek();
+
+ }
+
+ public void push() {
+
+ // The current symbol table.
+ final ST cur = current();
+
+ // Create a new symbol table.
+ final ST tmp = new ST(cur.nbound, cur.vars.clone(), cur.vals.clone());
+
+ // Push the new symbol table onto the stack.
+ stack.push(tmp);
+
+ }
+
+ public void pop(final boolean save) {
+
+ if (stack.size() < 2) {
+ /*
+ * The stack may never become empty. Therefore there must be at
+ * least two symbol tables on the stack for a pop() request.
+ */
+ throw new IllegalArgumentException();
+ }
+
+ // Pop the symbol table off of the top of the stack.
+ final ST old = stack.pop();
+
+ if (save) {
+
+ // discard the current symbol table.
+ stack.pop();
+
+ // replacing it with the symbol table which we popped off the stack.
+ stack.push(old);
+
+ } else {
+
+ // clear the hash code.
+ hash = 0;
+
+ }
+
+ }
+
/**
- * A dense array of the values bound to the variables (correlated with
- * {@link #vars}).
- */
- private final IConstant[] vals;
+ * Copy constructor (used by clone, copy).
+ *
+ * @param src
+ * The source to be copied.
+ * @param variablesToKeep
+ * The variables to be retained for the symbol table on the top
+ * of the stack (optional).
+ */
+ protected ArrayBindingSet(final ArrayBindingSet src,
+ final IVariable[] variablesToKeep) {
- private int nbound = 0;
+ stack = new Stack<ST>();
- /**
- * Copy constructor.
- */
- protected ArrayBindingSet(final ArrayBindingSet bindingSet) {
+ final int stackSize = src.stack.size();
+
+ int depth = 1;
+
+ for (ST srcLst : src.stack) {
+
+ /*
+ * Copy the source bindings.
+ *
+ * Note: If a restriction exists on the variables to be copied, then
+ * it is applied onto the the top level of the stack. If the symbol
+ * table is saved when it is pop()'d, then the modified bindings
+ * will replace the parent symbol table on the stack.
+ */
+ final ST tmp = copy(srcLst,
+ depth == stackSize ? variablesToKeep : null);
+
+ // Push onto the stack.
+ stack.push(tmp);
+
+ }
+
+ }
+
+ /**
+ * Return a copy of the source list.
+ *
+ * @param src
+ * The source list.
+ * @param variablesToKeep
+ * When non-<code>null</code>, only the bindings for the
+ * variables listed in this array will copied.
+ *
+ * @return The copy.
+ */
+ private ST copy(final ST src, final IVariable[] variablesToKeep) {
+
+ if (variablesToKeep == null) {
+
+ return new ST(src.nbound, src.vars, src.vals);
+
+ }
+
+ final ST dst = new ST(0/* nbound */, new IVariable[src.vars.length],
+ new IConstant[src.vals.length]);
+
+ // bitflag for the old binding set
+ final boolean[] keep = new boolean[src.nbound];
- if (bindingSet == null)
- throw new IllegalArgumentException();
+ // for each var in the old binding set, see if we need to keep it
+ for (int i = 0; i < src.nbound; i++) {
+
+ final IVariable v = src.vars[i];
+
+ keep[i] = false;
+ for (IVariable k : variablesToKeep) {
+ if (v == k) {
+ keep[i] = true;
+ break;
+ }
+ }
+
+ }
- nbound = bindingSet.nbound;
+ // fill in the new binding set based on the keep bitflag
+ for (int i = 0; i < src.nbound; i++) {
+ if (keep[i]) {
+ dst.vars[dst.nbound] = src.vars[i];
+ dst.vals[dst.nbound] = src.vals[i];
+ dst.nbound++;
+ }
+ }
- vars = bindingSet.vars.clone();
+// final Iterator<E> itr = src.iterator();
+//
+// while (itr.hasNext()) {
+//
+// final E e = itr.next();
+//
+// boolean keep = true;
+//
+// if (variablesToKeep != null) {
+//
+// keep = false;
+//
+// for (IVariable<?> x : variablesToKeep) {
+//
+// if (x == e.var) {
+//
+// keep = true;
+//
+// break;
+//
+// }
+//
+// }
+//
+// }
+//
+// if (keep)
+// dst.add(new E(e.var, e.val));
+//
+// }
- vals = bindingSet.vals.clone();
+ return dst;
+
+ }
+
+// public ArrayBindingSet XXcopy(final IVariable[] variablesToKeep) {
+//
+// // bitflag for the old binding set
+// final boolean[] keep = new boolean[nbound];
+//
+// // for each var in the old binding set, see if we need to keep it
+// for (int i = 0; i < nbound; i++) {
+//
+// final IVariable v = vars[i];
+//
+// keep[i] = false;
+// for (IVariable k : variablesToKeep) {
+// if (v == k) {
+// keep[i] = true;
+// break;
+// }
+// }
+//
+// }
+//
+// // allocate the new vars
+// final IVariable[] newVars = new IVariable[vars.length];
+//
+// // allocate the new vals
+// final IConstant[] newVals = new IConstant[vals.length];
+//
+// // fill in the new binding set based on the keep bitflag
+// int newbound = 0;
+// for (int i = 0; i < nbound; i++) {
+// if (keep[i]) {
+// newVars[newbound] = vars[i];
+// newVals[newbound] = vals[i];
+// newbound++;
+// }
+// }
+//
+// ArrayBindingSet bs = new ArrayBindingSet(newVars, newVals);
+// bs.nbound = newbound;
+//
+// return bs;
+//
+// }
+
+ public ArrayBindingSet clone() {
+
+ return new ArrayBindingSet(this, null/* variablesToKeep */);
}
-
+
+ public ArrayBindingSet copy(final IVariable[] variablesToKeep) {
+
+ return new ArrayBindingSet(this, variablesToKeep);
+
+ }
+
/**
* Initialized with the given bindings (assumes for efficiency that all
* elements of bound arrays are non-<code>null</code> and that no
@@ -105,21 +458,9 @@
if(vars.length != vals.length)
throw new IllegalArgumentException();
- // for (int i = 0; i < vars.length; i++) {
- //
- // if (vars[i] == null)
- // throw new IllegalArgumentException();
- //
- // if (vals[i] == null)
- // throw new IllegalArgumentException();
- //
- // }
-
- this.vars = vars;
-
- this.vals = vals;
+ stack = new Stack<ST>();
- this.nbound = vars.length;
+ stack.push(new ST(vars.length, vars, vals));
}
@@ -134,22 +475,32 @@
*/
public ArrayBindingSet(final int capacity) {
- if (capacity < 0)
- throw new IllegalArgumentException();
+ if (capacity < 0)
+ throw new IllegalArgumentException();
- vars = new IVariable[capacity];
+ stack = new Stack<ST>();
- vals = new IConstant[capacity];
+ stack.push(new ST(0/* nbound */, new IVariable[capacity],
+ new IConstant[capacity]));
}
- public Iterator<IVariable> vars() {
+ /**
+ * {@inheritDoc}
+ * <p>
+ * Iterator does not support either removal or concurrent modification of
+ * the binding set.
+ */
+ public Iterator<IVariable> vars() {
- return Collections.unmodifiableList(Arrays.asList(vars)).iterator();
-
+ return Collections.unmodifiableList(Arrays.asList(current().vars))
+ .iterator();
+
}
/**
+ * {@inheritDoc}
+ * <p>
* Iterator does not support either removal or concurrent modification of
* the binding set.
*/
@@ -163,9 +514,11 @@
private int i = 0;
+ private ST cur = current();
+
public boolean hasNext() {
- return i < nbound;
+ return i < cur.nbound;
}
@@ -178,13 +531,13 @@
public IVariable getKey() {
- return vars[index];
+ return cur.vars[index];
}
public IConstant getValue() {
- return vals[index];
+ return cur.vals[index];
}
@@ -193,9 +546,9 @@
if (value == null)
throw new IllegalArgumentException();
- final IConstant t = vals[index];
+ final IConstant t = cur.vals[index];
- vals[index] = value;
+ cur.vals[index] = value;
return t;
@@ -215,89 +568,34 @@
public int size() {
- return nbound;
+ return current().nbound;
}
public void clearAll() {
- for (int i = nbound - 1; nbound > 0; i--, nbound--) {
-
- vars[i] = null;
-
- vals[i] = null;
-
- }
-
+ current().clearAll();
+
// clear the hash code.
hash = 0;
- assert nbound == 0;
-
}
- /**
- * Since the array is dense (no gaps), {@link #clear(IVariable)} requires
- * that we copy down any remaining elements in the array by one position.
- */
- public void clear(final IVariable var) {
+ public void clear(final IVariable var) {
- if (var == null)
- throw new IllegalArgumentException();
+ if (current().clear(var)) {
- for (int i = 0; i < nbound; i++) {
+ // clear the hash code.
+ hash = 0;
- if (vars[i] == var) {
+ }
- final int nremaining = nbound-(i+1);
-
- if (nremaining >= 0) {
-
- // Copy down to close up the gap!
- System.arraycopy(vars, i+1, vars, i, nremaining);
+ }
- System.arraycopy(vals, i+1, vals, i, nremaining);
-
- } else {
-
- // Just clear the reference.
-
- vars[i] = null;
-
- vals[i] = null;
-
- }
-
- // clear the hash code.
- hash = 0;
-
- nbound--;
-
- break;
-
- }
-
- }
-
- }
-
public IConstant get(final IVariable var) {
- if (var == null)
- throw new IllegalArgumentException();
-
- for (int i = 0; i < nbound; i++) {
-
- if (vars[i] == var) {
+ return current().get(var);
- return vals[i];
-
- }
-
- }
-
- return null;
-
}
public boolean isBound(final IVariable var) {
@@ -308,122 +606,40 @@
public void set(final IVariable var, final IConstant val) {
- if (var == null)
- throw new IllegalArgumentException();
+ current().set(var, val);
- if (val == null)
- throw new IllegalArgumentException();
-
- if (log.isTraceEnabled()) {
-
- log.trace("var=" + var + ", val=" + val + ", nbound=" + nbound
- + ", capacity=" + vars.length);
-
- }
-
- for (int i = 0; i < nbound; i++) {
-
- if (vars[i] == var) {
-
- vals[i] = val;
-
- // clear the hash code.
- hash = 0;
-
- return;
-
- }
-
- }
-
- vars[nbound] = var;
-
- vals[nbound] = val;
-
// clear the hash code.
hash = 0;
- nbound++;
-
}
public String toString() {
- final StringBuilder sb = new StringBuilder();
-
- sb.append("{");
+ final ST cur = current();
+
+ final StringBuilder sb = new StringBuilder();
- for(int i=0; i<nbound; i++) {
-
- if(i>0) sb.append(", ");
-
- sb.append(vars[i]);
-
- sb.append("=");
-
- sb.append(vals[i]);
-
- }
-
- sb.append("}");
-
- return sb.toString();
-
- }
-
- public ArrayBindingSet clone() {
+ sb.append("{");
- return new ArrayBindingSet(this);
-
- }
+ for (int i = 0; i < cur.nbound; i++) {
- /**
- * Return a shallow copy of the binding set, eliminating unecessary
- * variables.
- */
- public ArrayBindingSet copy(final IVariable[] variablesToKeep) {
+ if (i > 0)
+ sb.append(", ");
- // bitflag for the old binding set
- final boolean[] keep = new boolean[nbound];
-
- // for each var in the old binding set, see if we need to keep it
- for (int i = 0; i < nbound; i++) {
-
- final IVariable v = vars[i];
+ sb.append(cur.vars[i]);
- keep[i] = false;
- for (IVariable k : variablesToKeep) {
- if (v == k) {
- keep[i] = true;
- break;
- }
- }
-
+ sb.append("=");
+
+ sb.append(cur.vals[i]);
+
}
- // allocate the new vars
- final IVariable[] newVars = new IVariable[vars.length];
+ sb.append("}");
- // allocate the new vals
- final IConstant[] newVals = new IConstant[vals.length];
+ return sb.toString();
- // fill in the new binding set based on the keep bitflag
- int newbound = 0;
- for (int i = 0; i < nbound; i++) {
- if (keep[i]) {
- newVars[newbound] = vars[i];
- newVals[newbound] = vals[i];
- newbound++;
- }
- }
-
- ArrayBindingSet bs = new ArrayBindingSet(newVars, newVals);
- bs.nbound = newbound;
-
- return bs;
-
}
-
+
public boolean equals(final Object t) {
if (this == t)
@@ -433,14 +649,16 @@
return false;
final IBindingSet o = (IBindingSet)t;
-
- if (nbound != o.size())
+
+ final ST cur = current();
+
+ if (cur.nbound != o.size())
return false;
- for(int i=0; i<nbound; i++) {
+ for(int i=0; i<cur.nbound; i++) {
- IConstant<?> o_val = o.get ( vars [ i ] ) ;
- if ( null == o_val || !vals[i].equals( o_val ))
+ final IConstant<?> o_val = o.get ( cur.vars [ i ] ) ;
+ if ( null == o_val || !cur.vals[i].equals( o_val ))
return false;
}
@@ -455,12 +673,14 @@
int result = 0;
- for (int i = 0; i < nbound; i++) {
+ final ST cur = current();
+
+ for (int i = 0; i < cur.nbound; i++) {
- if (vals[i] == null)
+ if (cur.vals[i] == null)
continue;
- result ^= vals[i].hashCode();
+ result ^= cur.vals[i].hashCode();
}
@@ -471,5 +691,5 @@
}
private int hash;
-
+
}
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/bindingSet/EmptyBindingSet.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/bindingSet/EmptyBindingSet.java 2010-12-11 16:04:20 UTC (rev 4003)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/bindingSet/EmptyBindingSet.java 2010-12-12 22:22:01 UTC (rev 4004)
@@ -44,6 +44,8 @@
*
* @author <a href="mailto:tho...@us...">Bryan Thompson</a>
* @version $Id$
+ *
+ * @todo test suite?
*/
final public class EmptyBindingSet implements IBindingSet, Serializable {
@@ -158,5 +160,13 @@
return EmptyIterator.DEFAULT;
}
+
+ public void push() {
+ throw new IllegalStateException();
+ }
+ public void pop(boolean save) {
+ throw new UnsupportedOperationException();
+ }
+
}
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/bindingSet/HashBindingSet.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/bindingSet/HashBindingSet.java 2010-12-11 16:04:20 UTC (rev 4003)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/bindingSet/HashBindingSet.java 2010-12-12 22:22:01 UTC (rev 4004)
@@ -29,82 +29,242 @@
package com.bigdata.bop.bindingSet;
import java.util.Collections;
-import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
-import java.util.LinkedList;
import java.util.Map;
+import java.util.Stack;
import java.util.Map.Entry;
import com.bigdata.bop.IBindingSet;
import com.bigdata.bop.IConstant;
import com.bigdata.bop.IVariable;
-import com.bigdata.bop.Var;
/**
- * {@link IBindingSet} backed by a {@link HashMap}.
+ * {@link IBindingSet} backed by a {@link LinkedHashMap}.
+ * <p>
+ * Note: A {@link LinkedHashMap} provides a fast iterator, which we use a bunch.
+ * However, {@link IBindingSet}s are inherently unordered collections of
+ * bindings so the order preservation aspect of the {@link LinkedHashMap} is not
+ * relied upon.
*
* @author <a href="mailto:tho...@us...">Bryan Thompson</a>
* @version $Id$
- *
- * @todo Since {@link Var}s allow reference testing, a faster implementation
- * could be written based on a {@link LinkedList}. Just scan the list
- * until the entry is found with the desired {@link Var} reference and
- * then return it.
*/
public class HashBindingSet implements IBindingSet {
private static final long serialVersionUID = -2989802566387532422L;
- /**
- * Note: A {@link LinkedHashMap} provides a fast iterator, which we use a
- * bunch.
- */
- private LinkedHashMap<IVariable, IConstant> map;
+// /**
+// * Note: A {@link LinkedHashMap} provides a fast iterator, which we use a
+// * bunch.
+// */
+// private final LinkedHashMap<IVariable, IConstant> map;
+ /**
+ * The stack of symbol tables. Each symbol table is a mapping from an
+ * {@link IVariable} onto its non-<code>null</code> bound {@link IConstant}.
+ * The stack is initialized with an empty symbol table. Symbol tables may be
+ * pushed onto the stack or popped off of the stack, but the stack MAY NOT
+ * become empty.
+ */
+ private final Stack<LinkedHashMap<IVariable, IConstant>> stack;
+
+ /**
+ * Return the symbol table on the top of the stack.
+ */
+ private LinkedHashMap<IVariable, IConstant> current() {
+
+ return stack.peek();
+
+ }
+
+ public void push() {
+
+ // The current symbol table.
+ final LinkedHashMap<IVariable, IConstant> cur = current();
+
+ // Create a new symbol table.
+ final LinkedHashMap<IVariable, IConstant> tmp = new LinkedHashMap<IVariable, IConstant>(
+ cur.size());
+
+ // Push the new symbol table onto the stack.
+ stack.push(tmp);
+
+ /*
+ * Make a copy of each entry in the symbol table which was on the top of
+ * the stack when we entered this method, inserting the entries into the
+ * new symbol table as we go. This avoids side effects of mutation on
+ * the nested symbol tables and also ensures that we do not need to read
+ * through to the nested symbol tables when answering a query about the
+ * current symbol table. The only down side of this is that naive
+ * serialization is that much less compact.
+ */
+ for (Map.Entry<IVariable, IConstant> e : cur.entrySet()) {
+
+ tmp.put(e.getKey(), e.getValue());
+
+ }
+
+ }
+
+ public void pop(final boolean save) {
+
+ if (stack.size() < 2) {
+ /*
+ * The stack may never become empty. Therefore there must be at
+ * least two symbol tables on the stack for a pop() request.
+ */
+ throw new IllegalArgumentException();
+ }
+
+ // Pop the symbol table off of the top of the stack.
+ final LinkedHashMap<IVariable,IConstant> old = stack.pop();
+
+ if (save) {
+
+ // discard the current symbol table.
+ stack.pop();
+
+ // replacing it with the symbol table which we popped off the stack.
+ stack.push(old);
+
+ } else {
+
+ // clear the hash code.
+ hash = 0;
+
+ }
+
+ }
+
/**
* New empty binding set.
*/
public HashBindingSet() {
+
+ stack = new Stack<LinkedHashMap<IVariable, IConstant>>();
+
+ stack.push(new LinkedHashMap<IVariable, IConstant>());
- map = new LinkedHashMap<IVariable, IConstant>();
-
}
/**
- * Copy constructor.
+ * Copy constructor (used by clone, copy).
*
* @param src
*/
- protected HashBindingSet(final HashBindingSet src) {
+ protected HashBindingSet(final HashBindingSet src, final IVariable[] variablesToKeep) {
- map = new LinkedHashMap<IVariable, IConstant>(src.map);
-
- }
+ stack = new Stack<LinkedHashMap<IVariable,IConstant>>();
+ final int stackSize = src.stack.size();
+
+ int depth = 1;
+
+ for (LinkedHashMap<IVariable, IConstant> srcLst : src.stack) {
+
+ /*
+ * Copy the source bindings.
+ *
+ * Note: If a restriction exists on the variables to be copied, then
+ * it is applied onto the the top level of the stack. If the symbol
+ * table is saved when it is pop()'d, then the modified bindings
+ * will replace the parent symbol table on the stack.
+ */
+ final LinkedHashMap<IVariable,IConstant> tmp = copy(srcLst,
+ depth == stackSize ? variablesToKeep : null);
+
+ // Push onto the stack.
+ stack.push(tmp);
+
+ }
+
+ }
+
+ /**
+ * Return a copy of the source list.
+ *
+ * @param src
+ * The source list.
+ * @param variablesToKeep
+ * When non-<code>null</code>, only the bindings for the
+ * variables listed in this array will copied.
+ *
+ * @return The copy.
+ */
+ private LinkedHashMap<IVariable, IConstant> copy(
+ final LinkedHashMap<IVariable, IConstant> src,
+ final IVariable[] variablesToKeep) {
+
+ final LinkedHashMap<IVariable, IConstant> dst = new LinkedHashMap<IVariable, IConstant>(
+ variablesToKeep != null ? variablesToKeep.length : src.size());
+
+ final Iterator<Map.Entry<IVariable, IConstant>> itr = src.entrySet()
+ .iterator();
+
+ while (itr.hasNext()) {
+
+ final Map.Entry<IVariable, IConstant> e = itr.next();
+
+ boolean keep = true;
+
+ if (variablesToKeep != null) {
+
+ keep = false;
+
+ for (IVariable<?> x : variablesToKeep) {
+
+ if (x == e.getKey()) {
+
+ keep = true;
+
+ break;
+
+ }
+
+ }
+
+ }
+
+ if (keep)
+ dst.put(e.getKey(), e.getValue());
+
+ }
+
+ return dst;
+
+ }
+
/**
- * Copy constructor.
+ * Package private constructor used by the unit tests.
*
* @param src
*/
- public HashBindingSet(final IBindingSet src) {
+ HashBindingSet(final IBindingSet src) {
- map = new LinkedHashMap<IVariable, IConstant>(src.size());
-
+ this();
+
final Iterator<Map.Entry<IVariable, IConstant>> itr = src.iterator();
while (itr.hasNext()) {
final Map.Entry<IVariable, IConstant> e = itr.next();
- map.put(e.getKey(), e.getValue());
+ set(e.getKey(), e.getValue());
}
}
- public HashBindingSet(final IVariable[] vars, final IConstant[] vals) {
+ /**
+ * Package private constructor used by the unit tests.
+ * @param vars
+ * @param vals
+ */
+ HashBindingSet(final IVariable[] vars, final IConstant[] vals) {
+ this();
+
if (vars == null)
throw new IllegalArgumentException();
@@ -114,22 +274,32 @@
if (vars.length != vals.length)
throw new IllegalArgumentException();
- map = new LinkedHashMap<IVariable, IConstant>(vars.length);
-
for (int i = 0; i < vars.length; i++) {
- map.put(vars[i], vals[i]);
+ set(vars[i], vals[i]);
}
}
+ public HashBindingSet clone() {
+
+ return new HashBindingSet(this, null /* variablesToKeep */);
+
+ }
+
+ public HashBindingSet copy(final IVariable[] variablesToKeep) {
+
+ return new HashBindingSet(this/* src */, variablesToKeep);
+
+ }
+
public boolean isBound(final IVariable var) {
if (var == null)
throw new IllegalArgumentException();
- return map.containsKey(var);
+ return current().containsKey(var);
}
@@ -138,7 +308,7 @@
if (var == null)
throw new IllegalArgumentException();
- return map.get(var);
+ return current().get(var);
}
@@ -150,7 +320,7 @@
if (val == null)
throw new IllegalArgumentException();
- map.put(var,val);
+ current().put(var,val);
// clear the hash code.
hash = 0;
@@ -162,7 +332,7 @@
if (var == null)
throw new IllegalArgumentException();
- map.remove(var);
+ current().remove(var);
// clear the hash code.
hash = 0;
@@ -171,7 +341,7 @@
public void clearAll() {
- map.clear();
+ current().clear();
// clear the hash code.
hash = 0;
@@ -186,7 +356,7 @@
int i = 0;
- final Iterator<Map.Entry<IVariable, IConstant>> itr = map.entrySet()
+ final Iterator<Map.Entry<IVariable, IConstant>> itr = current().entrySet()
.iterator();
while (itr.hasNext()) {
@@ -217,52 +387,22 @@
*/
public Iterator<Entry<IVariable, IConstant>> iterator() {
- return Collections.unmodifiableMap(map).entrySet().iterator();
+ return Collections.unmodifiableMap(current()).entrySet().iterator();
}
public Iterator<IVariable> vars() {
- return Collections.unmodifiableSet(map.keySet()).iterator();
+ return Collections.unmodifiableSet(current().keySet()).iterator();
}
public int size() {
- return map.size();
+ return current().size();
}
- public HashBindingSet clone() {
-
- return new HashBindingSet( this );
-
- }
-
- /**
- * Return a shallow copy of the binding set, eliminating unecessary
- * variables.
- */
- public HashBindingSet copy(final IVariable[] variablesToKeep) {
-
- final HashBindingSet bs = new HashBindingSet();
-
- for (IVariable<?> var : variablesToKeep) {
-
- final IConstant<?> val = map.get(var);
-
- if (val != null) {
-
- bs.map.put(var, val);
-
- }
-
- }
-
- return bs;
-
- }
-
public boolean equals(final Object t) {
if (this == t)
@@ -276,7 +416,7 @@
if (size() != o.size())
return false;
- final Iterator<Map.Entry<IVariable,IConstant>> itr = map.entrySet().iterator();
+ final Iterator<Map.Entry<IVariable,IConstant>> itr = current().entrySet().iterator();
while(itr.hasNext()) {
@@ -288,7 +428,7 @@
// if (!o.isBound(vars[i]))
// return false;
- IConstant<?> o_val = o.get ( var ) ;
+ final IConstant<?> o_val = o.get ( var ) ;
if (null == o_val || !val.equals(o_val))
return false;
@@ -304,7 +444,7 @@
int result = 0;
- for(IConstant<?> c : map.values()) {
+ for(IConstant<?> c : current().values()) {
if (c == null)
continue;
Added: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/bindingSet/ListBindingSet.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/bindingSet/ListBindingSet.java (rev 0)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/bindingSet/ListBindingSet.java 2010-12-12 22:22:01 UTC (rev 4004)
@@ -0,0 +1,527 @@
+package com.bigdata.bop.bindingSet;
+
+import java.io.Serializable;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Stack;
+
+import com.bigdata.bop.IBindingSet;
+import com.bigdata.bop.IConstant;
+import com.bigdata.bop.IVariable;
+import com.bigdata.bop.Var;
+
+import cutthecrap.utils.striterators.Resolver;
+import cutthecrap.utils.striterators.Striterator;
+
+/**
+ * <p>An {@link IBindingSet} based on a {@link LinkedList}. Since {@link Var}s may
+ * be compared using <code>==</code> this should be faster than a hash map for
+ * most operations unless the binding set has a large number of entries.
+ * </p><p>
+ * Note: {@link #push()} and {@link #pop(boolean)} are implemented by making a
+ * copy of the current symbol table with distinct {@link Map.Entry} objects. If
+ * the symbol table is saved when it is {@link #pop(boolean) popped), then it
+ * simply replaces the pre-existing symbol table which was uncovered when it
+ * was popped off of the stack. This design has several advantages, including:
+ * <ul>
+ * <li>Methods such as {@link #get(IVariable)}, {@link #set(IVariable, IConstant)},
+ * and {@link #size()} can be written solely in terms of the current symbol table.</li>
+ * <li>{@link #clear(IVariable)} removes the {@link Map.Entry} from the
+ * current symbol table rather than introducing <code>null</code> values or
+ * delete markers.</li>
+ * </ul>
+ * </p>
+ * The only down side to this approach is that the serialized representation of
+ * the {@link IBindingSet} is more complex. However, java default serialization
+ * will do a good job by providing back references for the object graph.
+ *
+ * @version $Id: HashBindingSet.java 3836 2010-10-22 11:59:15Z thompsonbry $
+ */
+public class ListBindingSet implements IBindingSet {
+
+ private static final long serialVersionUID = 1L;
+
+ /**
+ * A (var,val) entry.
+ */
+ private static class E implements Map.Entry<IVariable<?>, IConstant<?>>, Serializable {
+
+ /**
+ *
+ */
+ private static final long serialVersionUID = 1L;
+
+ private final IVariable<?> var;
+
+ private IConstant<?> val;
+
+ E(final IVariable<?> var, final IConstant<?> val) {
+ this.var = var;
+ this.val = val;
+ }
+
+ public IVariable<?> getKey() {
+ return var;
+ }
+
+ public IConstant<?> getValue() {
+ return val;
+ }
+
+ public IConstant<?> setValue(final IConstant<?> value) {
+ if (value == null) {
+ // Null bindings are not permitted.
+ throw new IllegalArgumentException();
+ }
+ final IConstant<?> tmp = this.val;
+ this.val = value;
+ return tmp;
+ }
+ };
+
+ /**
+ * The stack of symbol tables. Each symbol table is a mapping from an
+ * {@link IVariable} onto its non-<code>null</code> bound {@link IConstant}.
+ * The stack is initialized with an empty symbol table. Symbol tables may be
+ * pushed onto the stack or popped off of the stack, but the stack MAY NOT
+ * become empty.
+ */
+ private final Stack<List<E>> stack;
+
+ /**
+ * Return the symbol table on the top of the stack.
+ */
+ private List<E> current() {
+
+ return stack.peek();
+
+ }
+
+ public void push() {
+
+ // The current symbol table.
+ final List<E> cur = current();
+
+ // Create a new symbol table.
+ final List<E> tmp = new LinkedList<E>();
+
+ // Push the new symbol table onto the stack.
+ stack.push(tmp);
+
+ /*
+ * Make a copy of each entry in the symbol table which was on the top of
+ * the stack when we entered this method, inserting the entries into the
+ * new symbol table as we go. This avoids side effects of mutation on
+ * the nested symbol tables and also ensures that we do not need to read
+ * through to the nested symbol tables when answering a query about the
+ * current symbol table. The only down side of this is that naive
+ * serialization is that much less compact.
+ */
+ for (E e : cur) {
+
+ tmp.add(new E(e.var, e.val));
+
+ }
+
+ }
+
+ public void pop(final boolean save) {
+
+ if (stack.size() < 2) {
+ /*
+ * The stack may never become empty. Therefore there must be at
+ * least two symbol tables on the stack for a pop() request.
+ */
+ throw new IllegalArgumentException();
+ }
+
+ // Pop the symbol table off of the top of the stack.
+ final List<E> old = stack.pop();
+
+ if (save) {
+
+ // discard the current symbol table.
+ stack.pop();
+
+ // replacing it with the symbol table which we popped off the stack.
+ stack.push(old);
+
+ } else {
+
+ // clear the hash code.
+ hash = 0;
+
+ }
+
+ }
+
+ /**
+ * Create an empty binding set.
+ */
+ public ListBindingSet() {
+
+ stack = new Stack<List<E>>();
+
+ stack.push(new LinkedList<E>());
+
+ }
+
+ /**
+ * Package private constructor used by the unit tests.
+ * @param vars
+ * @param vals
+ */
+ ListBindingSet(final IVariable[] vars, final IConstant[] vals) {
+
+ this();
+
+ if (vars == null)
+ throw new IllegalArgumentException();
+
+ if (vals == null)
+ throw new IllegalArgumentException();
+
+ if (vars.length != vals.length)
+ throw new IllegalArgumentException();
+
+ for (int i = 0; i < vars.length; i++) {
+
+ set(vars[i], vals[i]);
+
+ }
+
+ }
+
+ /**
+ * Copy constructor (used by clone, copy).
+ *
+ * @param src
+ * The source to be copied.
+ * @param variablesToKeep
+ * The variables to be retained for the symbol table on the top
+ * of the stack (optional).
+ */
+ protected ListBindingSet(final ListBindingSet src,
+ final IVariable[] variablesToKeep) {
+
+ stack = new Stack<List<E>>();
+
+ final int stackSize = src.stack.size();
+
+ int depth = 1;
+
+ for (List<E> srcLst : src.stack) {
+
+ /*
+ * Copy the source bindings.
+ *
+ * Note: If a restriction exists on the variables to be copied, then
+ * it is applied onto the the top level of the stack. If the symbol
+ * table is saved when it is pop()'d, then the modified bindings
+ * will replace the parent symbol table on the stack.
+ */
+ final List<E> tmp = copy(srcLst,
+ depth == stackSize ? variablesToKeep : null);
+
+ // Push onto the stack.
+ stack.push(tmp);
+
+ }
+
+ }
+
+ /**
+ * Return a copy of the source list. The copy will use new {@link E}s to
+ * represent the bindings so changes to the copy will not effect the source.
+ *
+ * @param src
+ * The source list.
+ * @param variablesToKeep
+ * When non-<code>null</code>, only the bindings for the
+ * variables listed in this array will copied.
+ *
+ * @return The copy.
+ */
+ private List<E> copy(final List<E> src, final IVariable[] variablesToKeep) {
+
+ final List<E> dst = new LinkedList<E>();
+
+ final Iterator<E> itr = src.iterator();
+
+ while (itr.hasNext()) {
+
+ final E e = itr.next();
+
+ boolean keep = true;
+
+ if (variablesToKeep != null) {
+
+ keep = false;
+
+ for (IVariable<?> x : variablesToKeep) {
+
+ if (x == e.var) {
+
+ keep = true;
+
+ break;
+
+ }
+
+ }
+
+ }
+
+ if (keep)
+ dst.add(new E(e.var, e.val));
+
+ }
+
+ return dst;
+
+ }
+
+ public ListBindingSet clone() {
+
+ return new ListBindingSet(this, null /* variablesToKeep */);
+
+ }
+
+ public IBindingSet copy(final IVariable[] variablesToKeep) {
+
+ return new ListBindingSet(this/*src*/, variablesToKeep);
+
+ }
+
+ public void clear(final IVariable var) {
+
+ if (var == null)
+ throw new IllegalArgumentException();
+
+ final List<E> cur = current();
+
+ for(E e : cur) {
+
+ if(e.var == var) {
+
+ cur.remove(e);
+
+ // clear the hash code.
+ hash = 0;
+
+ return;
+
+ }
+
+ }
+
+ }
+
+ public void clearAll() {
+
+ current().clear();
+
+ // clear the hash code.
+ hash = 0;
+
+ }
+
+ public IConstant get(final IVariable var) {
+
+ if (var == null)
+ throw new IllegalArgumentException();
+
+ final List<E> cur = current();
+
+ for(E e : cur) {
+
+ if(e.var == var) {
+
+ return e.val;
+
+ }
+
+ }
+
+ return null;
+
+ }
+
+ public boolean isBound(IVariable var) {
+
+ if (var == null)
+ throw new IllegalArgumentException();
+
+ final List<E> cur = current();
+
+ for(E e : cur) {
+
+ if(e.var == var) {
+
+ return true;
+
+ }
+
+ }
+
+ return false;
+
+ }
+
+ @SuppressWarnings("unchecked")
+ public Iterator<Map.Entry<IVariable, IConstant>> iterator() {
+
+ return (Iterator<Map.Entry<IVariable, IConstant>>) ((List) Collections
+ .unmodifiableList(current())).iterator();
+
+ }
+
+ public void set(final IVariable var, final IConstant val) {
+
+ if (var == null)
+ throw new IllegalArgumentException();
+
+ if (val == null)
+ throw new IllegalArgumentException();
+
+ final List<E> cur = current();
+
+ for (E e : cur) {
+
+ if (e.var == var) {
+
+ e.val = val;
+
+ // clear the hash code.
+ hash = 0;
+
+ return;
+
+ }
+
+ }
+
+ cur.add(new E(var, val));
+
+ // clear the hash code.
+ hash = 0;
+
+ }
+
+ public int size() {
+
+ return current().size();
+
+ }
+
+ @SuppressWarnings("unchecked")
+ public Iterator<IVariable> vars() {
+ return (Iterator<IVariable>) new Striterator(Collections
+ .unmodifiableList(current()).iterator())
+ .addFilter(new Resolver() {
+ private static final long serialVersionUID = 1L;
+
+ @Override
+ protected Object resolve(Object obj) {
+ return ((E) obj).var;
+ }
+ });
+ }
+
+ public String toString() {
+
+ final StringBuilder sb = new StringBuilder();
+
+ sb.append("{ ");
+
+ int i = 0;
+
+ final Iterator<E> itr = current().iterator();
+
+ while (itr.hasNext()) {
+
+ if (i > 0)
+ sb.append(", ");
+
+ final E entry = itr.next();
+
+ sb.append(entry.getKey());
+
+ sb.append("=");
+
+ sb.append(entry.getValue());
+
+ i++;
+
+ }
+
+ sb.append(" }");
+
+ return sb.toString();
+
+ }
+
+ public boolean equals(final Object t) {
+
+ if (this == t)
+ return true;
+
+ if(!(t instanceof IBindingSet))
+ return false;
+
+ final IBindingSet o = (IBindingSet) t;
+
+ if (size() != o.size())
+ return false;
+
+ final Iterator<E> itr = current().iterator();
+
+ while(itr.hasNext()) {
+
+ final E entry = itr.next();
+
+ final IVariable<?> var = entry.getKey();
+
+ final IConstant<?> val = entry.getValue();
+
+// if (!o.isBound(vars[i]))
+// return false;
+ final IConstant<?> o_val = o.get ( var ) ;
+ if (null == o_val || !val.equals(o_val))
+ return false;
+
+ }
+
+ return true;
+
+ }
+
+ public int hashCode() {
+
+ if (hash == 0) {
+
+ int result = 0;
+
+ final List<E> cur = current();
+
+ for(E e : cur) {
+
+ if (e.val == null)
+ continue;
+
+ result ^= e.val.hashCode();
+
+ }
+
+ hash = result;
+
+ }
+ return hash;
+
+ }
+ private int hash;
+
+}
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/solutions/DistinctBindingSetOp.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/solutions/DistinctBindingSetOp.java 2010-12-11 16:04:20 UTC (rev 4003)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/bop/solutions/DistinctBindingSetOp.java 2010-12-12 22:22:01 UTC (rev 4004)
@@ -250,8 +250,16 @@
// System.err.println("accepted: "
// + Arrays.toString(vals));
- accepted.add(new HashBindingSet(vars, vals));
+ final HashBindingSet tmp = new HashBindingSet();
+
+ for (int i = 0; i < vars.length; i++) {
+ tmp.set(vars[i], vals[i]);
+
+ }
+
+ accepted.add(tmp);
+
naccepted++;
}
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/bindingSet/TestAll.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/bindingSet/TestAll.java 2010-12-11 16:04:20 UTC (rev 4003)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/bindingSet/TestAll.java 2010-12-12 22:22:01 UTC (rev 4004)
@@ -60,9 +60,12 @@
final TestSuite suite = new TestSuite("binding sets");
+ // @todo test EmptyBindingSet
+
// test binding set impls.
suite.addTestSuite(TestArrayBindingSet.class);
suite.addTestSuite(TestHashBindingSet.class);
+ suite.addTestSuite(TestListBindingSet.class);
return suite;
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/bindingSet/TestArrayBindingSet.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/bindingSet/TestArrayBindingSet.java 2010-12-11 16:04:20 UTC (rev 4003)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/bindingSet/TestArrayBindingSet.java 2010-12-12 22:22:01 UTC (rev 4004)
@@ -59,24 +59,24 @@
*/
public TestArrayBindingSet ( String name ) { super ( name ) ; }
- /**
- * Unit test for {@link ArrayBindingSet#ArrayBindingSet(ArrayBindingSet)}
- */
- public void testConstructorArrayBindingSet ()
- {
- try { assertTrue ( null != new ArrayBindingSet ( null ) ) ; fail ( "IllegalArgumentException expected, copy from was null" ) ; }
- catch ( IllegalArgumentException e ) {}
+// /**
+// * Unit test for {@link ArrayBindingSet#ArrayBindingSet(ArrayBindingSet)}
+// */
+// public void testConstructorArrayBindingSet ()
+// {
+// try { assertTrue ( null != new ArrayBindingSet ( null ) ) ; fail ( "IllegalArgumentException expected, copy from was null" ) ; }
+// catch ( IllegalArgumentException e ) {}
+//
+// Var<?> var1 = Var.var ( "a" ) ;
+// Var<?> var2 = Var.var ( "b" ) ;
+// Constant<Integer> val1 = new Constant<Integer> ( 1 ) ;
+// Constant<Integer> val2 = new Constant<Integer> ( 2 ) ;
+// IVariable<?> vars [] = new IVariable [] { var1, var2 } ;
+// IConstant<?> vals [] = new IConstant [] { val1, val2 } ;
+//
+// assertEqual ( new ArrayBindingSet ( new ArrayBindingSet ( vars, vals ) ), vars, vals ) ;
+// }
- Var<?> var1 = Var.var ( "a" ) ;
- Var<?> var2 = Var.var ( "b" ) ;
- Constant<Integer> val1 = new Constant<Integer> ( 1 ) ;
- Constant<Integer> val2 = new Constant<Integer> ( 2 ) ;
- IVariable<?> vars [] = new IVariable [] { var1, var2 } ;
- IConstant<?> vals [] = new IConstant [] { val1, val2 } ;
-
- assertEqual ( new ArrayBindingSet ( new ArrayBindingSet ( vars, vals ) ), vars, vals ) ;
- }
-
/**
* Unit test for {@link ArrayBindingSet#ArrayBindingSet(IVariable[],IConstant[])}
*/
Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/bindingSet/TestIBindingSet.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/bindingSet/TestIBindingSet.java 2010-12-11 16:04:20 UTC (rev 4003)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/test/com/bigdata/bop/bindingSet/TestIBindingSet.java 2010-12-12 22:22:01 UTC (rev 4004)
@@ -31,23 +31,29 @@
import java.util.Iterator;
import java.util.Map;
+import junit.framework.TestCase2;
+
import com.bigdata.bop.Constant;
import com.bigdata.bop.IBindingSet;
import com.bigdata.bop.IConstant;
import com.bigdata.bop.IVariable;
import com.bigdata.bop.Var;
+import com.bigdata.io.SerializerUtil;
-import junit.framework.TestCase2;
-
/**
* Unit tests for {@link IBindingSet}.
- *
+ * <p>
* Note:
- * a) these tests assume that the values held for a given key are not cloned,
- * i.e. comparison is done by '==' and not '.equals'
- * b) keys with the same 'name' are a unique object.
+ * <ul>
+ * <li>a) these tests assume that the values held for a given key are not
+ * cloned, i.e. comparison is done by '==' and not '.equals' (this is true
+ * except for the Serializatoin tests, where the {@link Var} references will be
+ * preserved but the {@link IConstant}s will be distinct).</li>
+ * <li>b) keys with the same 'name' are a unique object.</li>
+ * </ul>
*
* @author <a href="mailto:dm...@us...">David MacMillan</a>
+ * @author <a href="mailto:tho...@us...">Bryan Thompson</a>
* @version $Id$
*/
public abstract class TestIBindingSet extends TestCase2 {
@@ -259,7 +265,13 @@
IBindingSet bs = newBindingSet ( new IVariable [] { var1, var2, var3, var4, var5 }
, new IConstant [] { val1, val2, val3, val4, val5 }
) ;
-
+
+ assertEqual(
+ bs.copy(null/* variablesToKeep */), //
+ new IVariable[] { var1, var2, var3, var4, var5 },
+ new IConstant[] { val1, val2, val3, val4, val5 }//
+ );
+
IBindingSet bs2 = bs.copy ( new IVariable [] { var1, var3, var5 } ) ;
assertTrue ( 3 == bs2.size () ) ;
@@ -321,13 +333,141 @@
assertTrue ( "expected equal: same bindings after mutation", bs1.hashCode () == bs4.hashCode () ) ;
}
+ /*
+ * push()/pop() tests.
+ *
+ * Note: In addition to testing push() and pop(save:boolean), we have to
+ * test that copy() and clone() operate correctly in the presence of nested
+ * symbol tables, and that the visitation patterns for the bindings operate
+ * correctly when there are nested symbol tables. For example, if there "y"
+ * is bound at level zero, a push() is executed, and then "x" is bound at
+ * level one. The visitation pattern must visit both "x" and "y".
+ */
+
+ public void test_nestedSymbolTables() {
+
+ final Var<?> var1 = Var.var ( "a" ) ;
+ final Var<?> var2 = Var.var ( "b" ) ;
+ final Constant<Integer> val1 = new Constant<Integer> ( 1 ) ;
+ final Constant<Integer> val2 = new Constant<Integer> ( 2 ) ;
+
+ final IBindingSet bs1 = newBindingSet(2/* size */);
+
+ bs1.set(var1,val1);
+
+ /*
+ * push a symbol table onto the stack
+ */
+ bs1.push();
+
+ bs1.set(var2, val2);
+
+ bs1.pop(false/* save */);
+
+ // verify the modified bindings were discarded.
+ assertEqual(bs1, new IVariable[] { var1 }, new IConstant[] { val1 });
+
+ /*
+ * push a symbol table onto the stack
+ */
+ bs1.push();
+
+ bs1.set(var2, val2);
+
+ bs1.pop(true/* save */);
+
+ // verify the modified bindings were saved.
+ assertEqual(bs1, new IVariable[] { var1, var2 }, new IConstant[] {
+ val1, val2 });
+ }
+
+ public void test_serialization() {
+
+ final Var<?> var1 = Var.var ( "a" ) ;
+ final Var<?> var2 = Var.var ( "b" ) ;
+ final Constant<Integer> val1 = new Constant<Integer> ( 1 ) ;
+ final Constant<Integer> val2 = new Constant<Integer> ( 2 ) ;
+
+ final IBindingSet bs1 = newBindingSet(2/* size */);
+
+ bs1.set(var1, val1);
+
+ bs1.set(var2, val2);
+
+ assertEqual(bs1, new IVariable[] { var1, var2 }, new IConstant[] {
+ val1, val2 });
+
+ final IBindingSet bs2 = (IBindingSet) SerializerUtil
+ .deserialize(SerializerUtil.serialize(bs1));
+
+ assertEquals(bs1, bs1);
+
+ }
+
+ /*
+ * Hooks for testing specific implementations.
+ */
+
protected abstract IBindingSet newBindingSet ( IVariable<?> vars [], IConstant<?> vals [] ) ;
protected abstract IBindingSet newBindingSet ( int size ) ;
+ /**
+ * Compare actual and expected, where the latter is expressed using
+ * (vars,vals).
+ * <p>
+ * Note: This does not follow the junit pattern for asserts, which puts the
+ * expected data first.
+ *
+ * @param actual
+ * @param vars
+ * @param vals
+ */
protected void assertEqual ( IBindingSet actual, IVariable<?> vars [], IConstant<?> vals [] )
{
assertTrue ( "wrong size", actual.size () == vars.length ) ;
for ( int i = 0; i < vars.length; i++ )
assertTrue ( "wrong value", vals [ i ] == actual.get ( vars [ i ] ) ) ;
}
-}
\ No newline at end of file
+
+ protected void assertEquals(IBindingSet expected, IBindingSet actual) {
+
+ // expected variables in some order.
+ final Iterator<IVariable> evars = expected.vars();
+
+ // actual variables in some order (the order MAY be different).
+ final Iterator<IVariable> avars = actual.vars();
+
+ while(evars.hasNext()) {
+
+ // Some variable for which we expect a binding.
+ f...
[truncated message content] |
