001: /*
002: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP, all rights reserved.
003: [See end of file]
004: $Id: Expression.java,v 1.29 2008/01/02 12:07:57 andy_seaborne Exp $
005: */
006:
007: package com.hp.hpl.jena.graph.query;
008:
009: import java.util.*;
010:
011: import com.hp.hpl.jena.util.CollectionFactory;
012:
013: /**
014: Expression - the interface for expressions that is expected by Query for
015: constraints. An Expression can be evaluated (given a name->value mapping);
016: it can be prepared into a Valuator (given a name->index mapping); and it can
017: be analysed into its components.
018: <p>
019: An Expression can be a variable, an application, or a literal value. If an access
020: method (eg getName) is applied to an Expression for which it is not appropriate
021: (eg an application), <em>the result is unspecified</em>; an implementation is
022: free to throw an exception, deliver a null result, deliver a misleading value,
023: whatever is convenient.
024: <p>
025: The nested class <code>Util</code> provides some expression utility
026: methods, including a generic version of <code>prepare</code>. The nested
027: abstract class <code>Base</code> and its sub-classes <code>Literal</code>,
028: <code>Variable</code>, and <code>Application</code> provide a framework
029: for developers to implement Expressions over.
030:
031: @author kers
032: */
033: public interface Expression {
034: /**
035: Answer a Valuator which, when run with a set of index-to-value bindings,
036: evaluates this expression in the light of the given variable-to-index bindings
037: [ie as though the variables were bound to the corresponding values]
038: */
039: public Valuator prepare(VariableIndexes vi);
040:
041: /**
042: Answer true iff this Expression represents a variable.
043: */
044: public boolean isVariable();
045:
046: /**
047: If this Expression is a variable, answer a [non-null] String which is its name.
048: Otherwise the behaviour is unspecified.
049: */
050: public String getName();
051:
052: /**
053: Answer true iff this Expression represents a literal [Java object] value.
054: */
055: public boolean isConstant();
056:
057: /**
058: If this Expression is a literal, answer the value of that literal. Otherwise the
059: behaviour is unspecified.
060: */
061: public Object getValue();
062:
063: /**
064: Answer true iff this Expression represents the application of some function
065: [or operator] to some arguments [or operands].
066: */
067: public boolean isApply();
068:
069: /**
070: If this Expression is an application, return the string identifying the function,
071: which should be a URI. Otherwise the behaviour is unspecified.
072: */
073: public String getFun();
074:
075: /**
076: If this Expression is an application, answer the number of arguments that
077: it has. Otherwise the behaviour is unspecified.
078: */
079: public int argCount();
080:
081: /**
082: If this Expression is an application, and 0 <= i < argCount(), answer the
083: <code>i</code>th argument. Otherwise the behaviour is unspecified.
084: */
085: public Expression getArg(int i);
086:
087: /**
088: An Expression which always evaluates to <code>true</code>.
089: */
090: public static Expression TRUE = new BoolConstant(true);
091:
092: /**
093: An Expression which always evaluates to <code>false</code>.
094: */
095: public static Expression FALSE = new BoolConstant(false);
096:
097: /**
098: An abstract base class for Expressions; over-ride as appropriate. The
099: sub-classes may be more useful.
100: */
101: public static abstract class Base implements Expression {
102: public boolean isVariable() {
103: return false;
104: }
105:
106: public boolean isApply() {
107: return false;
108: }
109:
110: public boolean isConstant() {
111: return false;
112: }
113:
114: public String getName() {
115: return null;
116: }
117:
118: public Object getValue() {
119: return null;
120: }
121:
122: public int argCount() {
123: return 0;
124: }
125:
126: public String getFun() {
127: return null;
128: }
129:
130: public Expression getArg(int i) {
131: return null;
132: }
133:
134: public boolean equals(Object other) {
135: return other instanceof Expression
136: && Expression.Util.equals(this , (Expression) other);
137: }
138: }
139:
140: /**
141: An abstract base class for literal nodes; subclasses implement getValue().
142: */
143: public static abstract class Constant extends Base {
144: public boolean isConstant() {
145: return true;
146: }
147:
148: public abstract Object getValue();
149: }
150:
151: /**
152: A concrete class for representing fixed constants; each instance
153: can hold a separate value and its valuator returns that value.
154: */
155: public static class Fixed extends Constant {
156: protected Object value;
157:
158: public Fixed(Object value) {
159: this .value = value;
160: }
161:
162: public Object getValue() {
163: return value;
164: }
165:
166: public Valuator prepare(VariableIndexes vi) {
167: return new FixedValuator(value);
168: }
169:
170: public String toString() {
171: return value.toString();
172: }
173: }
174:
175: /**
176: An abstract base class for variable nodes; subclasses implement getName().
177: */
178: public static abstract class Variable extends Base {
179: public boolean isVariable() {
180: return true;
181: }
182:
183: public abstract String getName();
184: }
185:
186: /**
187: An abstract base class for apply nodes; subclasses implement getFun(),
188: argCount(), and getArg().
189: */
190: public static abstract class Application extends Base {
191: public boolean isApply() {
192: return true;
193: }
194:
195: public abstract int argCount();
196:
197: public abstract String getFun();
198:
199: public abstract Expression getArg(int i);
200: }
201:
202: /**
203: Utility methods for Expressions, captured in a class because they can't be
204: written directly in the interface.
205: */
206: public static class Util {
207: /**
208: Answer a set containing exactly the names of variables within
209: <code>e</code>.
210: */
211: public static Set variablesOf(Expression e) {
212: return addVariablesOf(CollectionFactory.createHashedSet(),
213: e);
214: }
215:
216: /**
217: Add all the variables of <code>e</code> to <code>s</code>, and answer
218: <code>s</code>.
219: */
220: public static Set addVariablesOf(Set s, Expression e) {
221: if (e.isVariable())
222: s.add(e.getName());
223: else if (e.isApply())
224: for (int i = 0; i < e.argCount(); i += 1)
225: addVariablesOf(s, e.getArg(i));
226: return s;
227: }
228:
229: public static boolean containsAllVariablesOf(Set variables,
230: Expression e) {
231: if (e.isConstant())
232: return true;
233: if (e.isVariable())
234: return variables.contains(e.getName());
235: if (e.isApply()) {
236: for (int i = 0; i < e.argCount(); i += 1)
237: if (containsAllVariablesOf(variables, e.getArg(i)) == false)
238: return false;
239: return true;
240: }
241: return false;
242: }
243:
244: public static boolean equals(Expression L, Expression R) {
245: return L.isConstant() ? R.isConstant()
246: && L.getValue().equals(R.getValue()) : L
247: .isVariable() ? R.isVariable()
248: && R.getName().equals(R.getName())
249: : L.isApply() ? R.isApply() && sameApply(L, R)
250: : false;
251: }
252:
253: public static boolean sameApply(Expression L, Expression R) {
254: return L.argCount() == R.argCount()
255: && L.getFun().equals(R.getFun()) && sameArgs(L, R);
256: }
257:
258: public static boolean sameArgs(Expression L, Expression R) {
259: for (int i = 0; i < L.argCount(); i += 1)
260: if (!equals(L.getArg(i), R.getArg(i)))
261: return false;
262: return true;
263: }
264: }
265:
266: /**
267: Valof provides an implementation of VariableValues which composes the
268: "compile-time" VariableIndexes map with the "run-time" IndexValues map
269: to produce a VariableValues map. A Valof has mutable state; the setDomain
270: operation changes the IndexValues mapping of the Valof.
271:
272: @author kers
273: */
274: static class Valof implements VariableValues {
275: private VariableIndexes map;
276: private IndexValues dom;
277:
278: public Valof(VariableIndexes map) {
279: this .map = map;
280: }
281:
282: public final Object get(String name) {
283: return dom.get(map.indexOf(name));
284: }
285:
286: public final Valof setDomain(IndexValues d) {
287: dom = d;
288: return this ;
289: }
290: }
291:
292: /**
293: Base class used to implement <code>TRUE</code> and <code>FALSE</code>.
294: */
295: public static class BoolConstant extends Base implements
296: Expression, Valuator {
297: private boolean value;
298:
299: public BoolConstant(boolean value) {
300: this .value = value;
301: }
302:
303: public boolean isConstant() {
304: return true;
305: }
306:
307: // TODO when moving to Jave 1.4 can use Boolean.valueOf( value )
308: public Object getValue() {
309: return value ? Boolean.TRUE : Boolean.FALSE;
310: }
311:
312: public Valuator prepare(VariableIndexes vi) {
313: return this ;
314: }
315:
316: public boolean evalBool(VariableValues vv) {
317: return value;
318: }
319:
320: public boolean evalBool(IndexValues vv) {
321: return value;
322: }
323:
324: public Object evalObject(IndexValues iv) {
325: return getValue();
326: }
327: }
328: }
329:
330: /*
331: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
332: All rights reserved.
333:
334: Redistribution and use in source and binary forms, with or without
335: modification, are permitted provided that the following conditions
336: are met:
337:
338: 1. Redistributions of source code must retain the above copyright
339: notice, this list of conditions and the following disclaimer.
340:
341: 2. Redistributions in binary form must reproduce the above copyright
342: notice, this list of conditions and the following disclaimer in the
343: documentation and/or other materials provided with the distribution.
344:
345: 3. The name of the author may not be used to endorse or promote products
346: derived from this software without specific prior written permission.
347:
348: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
349: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
350: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
351: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
352: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
353: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
354: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
355: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
356: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
357: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
358: */
|