001: /******************************************************************
002: * File: Trail.java
003: * Created by: Dave Reynolds
004: * Created on: 20-May-2003
005: *
006: * (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: Trail.java,v 1.9 2008/01/02 12:09:45 andy_seaborne Exp $
009: *****************************************************************/package com.hp.hpl.jena.reasoner.rulesys.impl.oldCode;
010:
011: import com.hp.hpl.jena.reasoner.rulesys.*;
012: import com.hp.hpl.jena.reasoner.*;
013: import com.hp.hpl.jena.graph.*;
014:
015: import java.util.*;
016:
017: /**
018: * Representation of a trail of variable bindings. Each rule state has its
019: * own trail segment which is an instance of this class.
020: *
021: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
022: * @version $Revision: 1.9 $ on $Date: 2008/01/02 12:09:45 $
023: */
024: public class Trail implements BindingEnvironment {
025:
026: /** A trail of variable bindings made during the processing of this state */
027: protected ArrayList trail = new ArrayList();
028:
029: /**
030: * Unwind all the bindings on the trail.
031: */
032: public void unwindBindings() {
033: for (int i = trail.size() - 1; i >= 0; i--) {
034: TrailEntry entry = (TrailEntry) trail.get(i);
035: entry.var.unbind();
036: }
037: }
038:
039: /**
040: * Unwind all the bindings on the trail the forget them all.
041: */
042: public void unwindAndClear() {
043: for (int i = trail.size() - 1; i >= 0; i--) {
044: TrailEntry entry = (TrailEntry) trail.get(i);
045: entry.var.unbind();
046: }
047: trail.clear();
048: }
049:
050: /**
051: * Restore the set of trail bindings.
052: */
053: public void activate() {
054: for (Iterator i = trail.iterator(); i.hasNext();) {
055: TrailEntry entry = (TrailEntry) i.next();
056: entry.var.simpleBind(entry.value);
057: }
058: }
059:
060: /**
061: * Unify two triple patterns recording all of the bindings on the trail.
062: * If the unification fails returns false and the trail is left unchanged.
063: */
064: public boolean unify(TriplePattern t, TriplePattern tp) {
065: int watermark = trail.size();
066: boolean ok = unify(t.getSubject(), tp.getSubject())
067: && unify(t.getPredicate(), tp.getPredicate())
068: && unifyObj(t.getObject(), tp.getObject());
069: if (!ok) {
070: for (int i = trail.size() - 1; i >= watermark; i--) {
071: TrailEntry entry = (TrailEntry) trail.get(i);
072: entry.var.unbind();
073: trail.remove(i);
074: }
075: }
076: return ok;
077: }
078:
079: /**
080: * Unify a triple against a triple pattern recording all of the bindings on the trail.
081: * If the unification fails returns false and the trail is left unchanged.
082: */
083: public boolean unify(Triple t, TriplePattern tp) {
084: int watermark = trail.size();
085: boolean ok = unify(t.getSubject(), tp.getSubject())
086: && unify(t.getPredicate(), tp.getPredicate())
087: && unifyObj(t.getObject(), tp.getObject());
088: if (!ok) {
089: for (int i = trail.size() - 1; i >= watermark; i--) {
090: TrailEntry entry = (TrailEntry) trail.get(i);
091: entry.var.unbind();
092: trail.remove(i);
093: }
094: }
095: return ok;
096: }
097:
098: /**
099: * Unify two nodes, neither can be a literal.
100: */
101: public boolean unify(Node n1, Node n2) {
102: Node dn1 = getGroundVersion(n1);
103: Node dn2 = getGroundVersion(n2);
104: if (dn1 instanceof Node_RuleVariable) {
105: bind(dn1, dn2);
106: return true;
107: } else if (dn2 instanceof Node_RuleVariable) {
108: bind(dn2, dn1);
109: return true;
110: } else {
111: return dn1.sameValueAs(dn2);
112: }
113: }
114:
115: /**
116: * Unify two nodes, can be a literals.
117: */
118: public boolean unifyObj(Node n1, Node n2) {
119: Node dn1 = getGroundVersion(n1);
120: Node dn2 = getGroundVersion(n2);
121: if (dn1 instanceof Node_RuleVariable) {
122: bind(dn1, dn2);
123: return true;
124: } else if (dn2 instanceof Node_RuleVariable) {
125: bind(dn2, dn1);
126: return true;
127: } else {
128: // Both are ground, either functors or literals
129: if (Functor.isFunctor(dn1)) {
130: if (Functor.isFunctor(dn2)) {
131: // Unify functors
132: Functor f1 = (Functor) dn1.getLiteralValue();
133: Functor f2 = (Functor) dn2.getLiteralValue();
134: if (!f1.getName().equals(f2.getName()))
135: return false;
136: Node[] args1 = f1.getArgs();
137: Node[] args2 = f2.getArgs();
138: if (args1.length != args2.length)
139: return false;
140: for (int i = 0; i < args1.length; i++) {
141: if (!unify(args1[i], args2[i]))
142: return false;
143: }
144: return true;
145: } else {
146: return false;
147: }
148: } else {
149: return dn1.sameValueAs(dn2);
150: }
151: }
152: }
153:
154: /**
155: * Return the most ground version of the node. If the node is not a variable
156: * just return it, if it is a varible bound in this environment return the binding,
157: * if it is an unbound variable return the variable.
158: */
159: public Node getGroundVersion(Node node) {
160: if (node instanceof Node_RuleVariable) {
161: return ((Node_RuleVariable) node).deref();
162: } else {
163: return node;
164: }
165: }
166:
167: /**
168: * Return the most ground version of the node. This extends getGroundVersion by
169: * also grounding any embedded functors.
170: */
171: public Node getMostGroundVersion(Node node) {
172: if (node instanceof Node_RuleVariable) {
173: node = ((Node_RuleVariable) node).deref();
174: }
175: if (Functor.isFunctor(node)) {
176: Functor f = (Functor) node.getLiteralValue();
177: Node[] args = f.getArgs();
178: Node[] cargs = new Node[args.length];
179: for (int i = 0; i < args.length; i++) {
180: cargs[i] = getGroundVersion(args[i]);
181: }
182: return Functor.makeFunctorNode(f.getName(), cargs);
183: } else {
184: return node;
185: }
186: }
187:
188: /**
189: * Return the most ground version of the functor. Only used for pretty printing.
190: */
191: public Functor getMostGroundVersion(Functor f) {
192: Node[] args = f.getArgs();
193: Node[] cargs = new Node[args.length];
194: for (int i = 0; i < args.length; i++) {
195: cargs[i] = getGroundVersion(args[i]);
196: }
197: return new Functor(f.getName(), cargs);
198: }
199:
200: /**
201: * Bind a variable in the current envionment to the given value.
202: * Checks that the new binding is compatible with any current binding.
203: * @param var a Node_RuleVariable defining the variable to bind
204: * @param value the value to bind
205: * @return false if the binding fails
206: */
207: public boolean bind(Node var, Node value) {
208: if (var == Node_RuleVariable.WILD
209: || value == Node_RuleVariable.WILD)
210: return true;
211: // if (var == Node.ANY || value == Node.ANY) return true;
212: Node dvar = getGroundVersion(var);
213: if (dvar instanceof Node_RuleVariable) {
214: trail.add(new TrailEntry((Node_RuleVariable) dvar, value));
215: ((Node_RuleVariable) dvar).simpleBind(value);
216: return true;
217: } else {
218: return dvar.sameValueAs(value);
219: }
220: }
221:
222: /**
223: * Bind the variables in a goal pattern using the binding environment, to
224: * generate a more specialized goal
225: * @param goal the TriplePattern to be instantiated
226: * @return a TriplePattern obtained from the goal by substituting current bindinds
227: */
228: public TriplePattern partInstantiate(TriplePattern goal) {
229: return new TriplePattern(
230: getMostGroundVersion(goal.getSubject()),
231: getMostGroundVersion(goal.getPredicate()),
232: getMostGroundVersion(goal.getObject()));
233: }
234:
235: /**
236: * Instatiate a goal pattern using the binding environment
237: * @param goal the TriplePattern to be instantiated
238: * @return an instantiated Triple
239: */
240: public Triple instantiate(TriplePattern goal) {
241: return new Triple(getMostGroundVersion(goal.getSubject()),
242: getMostGroundVersion(goal.getPredicate()),
243: getMostGroundVersion(goal.getObject()));
244: }
245:
246: /**
247: * Inner class used to represent an entry on the binding trail.
248: */
249: static class TrailEntry {
250: /** The deferenced var which was bound */
251: protected Node_RuleVariable var;
252:
253: /** The value to which it was bound */
254: protected Node value;
255:
256: /** constructor */
257: TrailEntry(Node_RuleVariable var, Node value) {
258: this .var = var;
259: this .value = value;
260: }
261: }
262:
263: }
264:
265: /*
266: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
267: All rights reserved.
268:
269: Redistribution and use in source and binary forms, with or without
270: modification, are permitted provided that the following conditions
271: are met:
272:
273: 1. Redistributions of source code must retain the above copyright
274: notice, this list of conditions and the following disclaimer.
275:
276: 2. Redistributions in binary form must reproduce the above copyright
277: notice, this list of conditions and the following disclaimer in the
278: documentation and/or other materials provided with the distribution.
279:
280: 3. The name of the author may not be used to endorse or promote products
281: derived from this software without specific prior written permission.
282:
283: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
284: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
285: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
286: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
287: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
288: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
289: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
290: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
291: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
292: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
293: */
|