001: /******************************************************************
002: * File: BindingStack.java
003: * Created by: Dave Reynolds
004: * Created on: 28-Apr-03
005: *
006: * (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: BindingStack.java,v 1.12 2008/01/02 12:06:16 andy_seaborne Exp $
009: *****************************************************************/package com.hp.hpl.jena.reasoner.rulesys.impl;
010:
011: import com.hp.hpl.jena.graph.*;
012: import com.hp.hpl.jena.reasoner.TriplePattern;
013: import com.hp.hpl.jena.reasoner.rulesys.BindingEnvironment;
014: import com.hp.hpl.jena.reasoner.rulesys.Functor;
015: import com.hp.hpl.jena.reasoner.rulesys.Node_RuleVariable;
016:
017: import java.util.*;
018:
019: /**
020: * Provides a trail of possible variable bindings for a forward rule.
021: *
022: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
023: * @version $Revision: 1.12 $ on $Date: 2008/01/02 12:06:16 $
024: */
025: public class BindingStack implements BindingEnvironment {
026:
027: // We used to have a strange implmentation that avoided GC overheads
028: // by doing copying up a fixed-width stack. The interface to this object
029: // is weird because of this, though the current implementation is a little
030: // more normal
031:
032: /** The current binding set */
033: protected Node[] environment;
034:
035: /** A stack of prior binding sets */
036: protected ArrayList trail = new ArrayList();
037:
038: /** Index of the current binding set */
039: protected int index = 0;
040:
041: /**
042: * Constructor. The stack isn't ready for use until reset has been called.
043: */
044: public BindingStack() {
045: index = 0;
046: }
047:
048: /**
049: * Save the current environment on an internal stack
050: */
051: public void push() {
052: if (trail.size() > index) {
053: trail.set(index, environment);
054: } else {
055: trail.add(environment);
056: }
057: index++;
058: Node[] newenv = new Node[environment.length];
059: System.arraycopy(environment, 0, newenv, 0, environment.length);
060: environment = newenv;
061: }
062:
063: /**
064: * Forget the current environment and return the previously
065: * pushed state.
066: * @throws IndexOutOfBoundsException if there was not previous push
067: */
068: public void unwind() throws IndexOutOfBoundsException {
069: if (index > 0) {
070: // just point to previous stack entry
071: environment = (Node[]) trail.get(--index);
072: trail.set(index, null); // free the old space for GC
073: } else {
074: throw new IndexOutOfBoundsException(
075: "Underflow of BindingEnvironment");
076: }
077: }
078:
079: /**
080: * Forget the previously pushed state but keep the current environment.
081: * @throws IndexOutOfBoundsException if there was not previous push
082: */
083: public void commit() throws IndexOutOfBoundsException {
084: if (index > 0) {
085: trail.set(index - 1, null);
086: --index;
087: } else {
088: throw new IndexOutOfBoundsException(
089: "Underflow of BindingEnvironment");
090: }
091: }
092:
093: /**
094: * Reset the binding environment to empty.
095: * @param newSize the number of variables needed for processing the new rule
096: */
097: public void reset(int newSize) {
098: index = 0;
099: trail.clear();
100: environment = new Node[newSize];
101: }
102:
103: /**
104: * Return the current array of bindings
105: */
106: public Node[] getEnvironment() {
107: return environment;
108: }
109:
110: /**
111: * If the node is a variable then return the current binding (null if not bound)
112: * otherwise return the node itself.
113: */
114: public Node getBinding(Node node) {
115: if (node instanceof Node_RuleVariable) {
116: return environment[((Node_RuleVariable) node).getIndex()];
117: } else if (node instanceof Node_ANY) {
118: return null;
119: } else if (Functor.isFunctor(node)) {
120: Functor functor = (Functor) node.getLiteralValue();
121: if (functor.isGround())
122: return node;
123: Node[] args = functor.getArgs();
124: ArrayList boundargs = new ArrayList(args.length);
125: for (int i = 0; i < args.length; i++) {
126: Object binding = getBinding(args[i]);
127: if (binding == null) {
128: // Not sufficent bound to instantiate functor yet
129: return null;
130: }
131: boundargs.add(binding);
132: }
133: Functor newf = new Functor(functor.getName(), boundargs);
134: return Functor.makeFunctorNode(newf);
135: } else {
136: return node;
137: }
138: }
139:
140: /**
141: * Return the most ground version of the node. If the node is not a variable
142: * just return it, if it is a varible bound in this enviroment return the binding,
143: * if it is an unbound variable return the variable.
144: */
145: public Node getGroundVersion(Node node) {
146: Node bind = getBinding(node);
147: if (bind == null) {
148: return node;
149: } else {
150: return bind;
151: }
152: }
153:
154: /**
155: * Bind the ith variable in the current envionment to the given value.
156: * Checks that the new binding is compatible with any current binding.
157: * @return false if the binding fails
158: */
159: public boolean bind(int i, Node value) {
160: Node node = environment[i];
161: if (node == null) {
162: environment[i] = value;
163: return true;
164: } else {
165: return node.sameValueAs(value);
166: }
167: }
168:
169: /**
170: * Bind a variable in the current envionment to the given value.
171: * Checks that the new binding is compatible with any current binding.
172: * @param var a Node_RuleVariable defining the variable to bind
173: * @param value the value to bind
174: * @return false if the binding fails
175: */
176: public boolean bind(Node var, Node value) {
177: if (var instanceof Node_RuleVariable) {
178: return bind(((Node_RuleVariable) var).getIndex(), value);
179: } else {
180: return var.sameValueAs(value);
181: }
182: }
183:
184: /**
185: * Bind a variable in the current envionment to the given value.
186: * Overrides and ignores any current binding.
187: * @param var a Node_RuleVariable defining the variable to bind
188: * @param value the value to bind
189: */
190: public void bindNoCheck(Node_RuleVariable var, Node value) {
191: environment[var.getIndex()] = value;
192: }
193:
194: /**
195: * Instantiate a triple pattern against the current environment.
196: * This version handles unbound varibles by turning them into bNodes.
197: * @param clause the triple pattern to match
198: * @param env the current binding environment
199: * @return a new, instantiated triple
200: */
201: public Triple instantiate(TriplePattern pattern) {
202: Node s = getGroundVersion(pattern.getSubject());
203: if (s.isVariable())
204: s = Node.createAnon();
205: Node p = getGroundVersion(pattern.getPredicate());
206: if (p.isVariable())
207: p = Node.createAnon();
208: Node o = getGroundVersion(pattern.getObject());
209: if (o.isVariable())
210: o = Node.createAnon();
211: return new Triple(s, p, o);
212: }
213:
214: }
215:
216: /*
217: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
218: All rights reserved.
219:
220: Redistribution and use in source and binary forms, with or without
221: modification, are permitted provided that the following conditions
222: are met:
223:
224: 1. Redistributions of source code must retain the above copyright
225: notice, this list of conditions and the following disclaimer.
226:
227: 2. Redistributions in binary form must reproduce the above copyright
228: notice, this list of conditions and the following disclaimer in the
229: documentation and/or other materials provided with the distribution.
230:
231: 3. The name of the author may not be used to endorse or promote products
232: derived from this software without specific prior written permission.
233:
234: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
235: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
236: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
237: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
238: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
239: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
240: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
241: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
242: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
243: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
244: */
|