KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > hp > hpl > jena > reasoner > rulesys > impl > BindingStack


1 /******************************************************************
2  * File: BindingStack.java
3  * Created by: Dave Reynolds
4  * Created on: 28-Apr-03
5  *
6  * (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
7  * [See end of file]
8  * $Id: BindingStack.java,v 1.7 2005/02/21 12:17:39 andy_seaborne Exp $
9  *****************************************************************/
10 package com.hp.hpl.jena.reasoner.rulesys.impl;
11
12 import com.hp.hpl.jena.graph.*;
13 import com.hp.hpl.jena.reasoner.TriplePattern;
14 import com.hp.hpl.jena.reasoner.rulesys.BindingEnvironment;
15 import com.hp.hpl.jena.reasoner.rulesys.Functor;
16 import com.hp.hpl.jena.reasoner.rulesys.Node_RuleVariable;
17
18 import java.util.*;
19
20 /**
21  * Provides a trail of possible variable bindings for a forward rule.
22  *
23  * @author <a HREF="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
24  * @version $Revision: 1.7 $ on $Date: 2005/02/21 12:17:39 $
25  */
26 public class BindingStack implements BindingEnvironment {
27     
28     // Current slightly quirky implementation tries to avoid allocating
29 // store in which will be an inner loop. Does one array copy on
30 // push but handles both versions of pop with point manipulation.
31
32     /** The current binding set */
33     protected Node[] environment;
34     
35     /** A stack of prior binding sets */
36     protected ArrayList trail = new ArrayList();
37     
38     /** Index of the current binding set */
39     protected int index = 0;
40     
41     /** Index of maximum allocated slot in the trail */
42     protected int highWater = 0;
43     
44     /** Maximum number of distinct variables allowed in rules */
45     protected static final int MAX_VAR = 10;
46     
47     /**
48      * Constructor
49      */
50     public BindingStack() {
51         trail.add(new Node[MAX_VAR]);
52         environment = (Node[])trail.get(0);
53         index = highWater = 0;
54     }
55     
56     /**
57      * Save the current environment on an internal stack
58      */
59     public void push() {
60         if (index == highWater) {
61             trail.add(new Node[MAX_VAR]);
62             highWater++;
63         }
64         Node[] newenv = (Node[]) trail.get(++index);
65         System.arraycopy(environment, 0, newenv, 0, MAX_VAR);
66         environment = newenv;
67     }
68     
69     /**
70      * Forget the current environment and return the previously
71      * pushed state.
72      * @throws IndexOutOfBoundsException if there was not previous push
73      */
74     public void unwind() throws IndexOutOfBoundsException JavaDoc {
75         if (index > 0) {
76             // just point to previous stack entry
77 environment = (Node[]) trail.get(--index);
78         } else {
79             throw new IndexOutOfBoundsException JavaDoc("Underflow of BindingEnvironment");
80         }
81     }
82     
83     /**
84      * Forget the previously pushed state but keep the current environment.
85      * @throws IndexOutOfBoundsException if there was not previous push
86      */
87     public void commit() throws IndexOutOfBoundsException JavaDoc {
88         if (index > 0) {
89             // Swap top and previous stack entries and point to previous
90 Node[] newenv = (Node[]) trail.get(index-1);
91             trail.set(index-1, environment);
92             trail.set(index, newenv);
93             --index;
94         } else {
95             throw new IndexOutOfBoundsException JavaDoc("Underflow of BindingEnvironment");
96         }
97     }
98    
99     /**
100      * Reset the binding environment to empty.
101      */
102     public void reset() {
103         index = 0;
104         environment = (Node[]) trail.get(0);
105         Arrays.fill(environment, null);
106     }
107     
108     /**
109      * Return the current array of bindings
110      */
111     public Node[] getEnvironment() {
112         return environment;
113     }
114     
115     /**
116      * If the node is a variable then return the current binding (null if not bound)
117      * otherwise return the node itself.
118      */
119     public Node getBinding(Node node) {
120         if (node instanceof Node_RuleVariable) {
121             return environment[((Node_RuleVariable)node).getIndex()];
122         } else if (node instanceof Node_ANY) {
123             return null;
124         } else if (Functor.isFunctor(node)) {
125             Functor functor = (Functor)node.getLiteral().getValue();
126             if (functor.isGround()) return node;
127             Node[] args = functor.getArgs();
128             ArrayList boundargs = new ArrayList(args.length);
129             for (int i = 0; i < args.length; i++) {
130                 Object JavaDoc binding = getBinding(args[i]);
131                 if (binding == null) {
132                     // Not sufficent bound to instantiate functor yet
133 return null;
134                 }
135                 boundargs.add(binding);
136             }
137             Functor newf = new Functor(functor.getName(), boundargs);
138             return Functor.makeFunctorNode( newf );
139         } else {
140             return node;
141         }
142     }
143     
144     /**
145      * Return the most ground version of the node. If the node is not a variable
146      * just return it, if it is a varible bound in this enviroment return the binding,
147      * if it is an unbound variable return the variable.
148      */
149     public Node getGroundVersion(Node node) {
150         Node bind = getBinding(node);
151         if (bind == null) {
152             return node;
153         } else {
154             return bind;
155         }
156     }
157     
158     /**
159      * Bind the ith variable in the current envionment to the given value.
160      * Checks that the new binding is compatible with any current binding.
161      * @return false if the binding fails
162      */
163     public boolean bind(int i, Node value) {
164         Node node = environment[i];
165         if (node == null) {
166             environment[i] = value;
167             return true;
168         } else {
169             return node.sameValueAs(value);
170         }
171     }
172     
173     /**
174      * Bind a variable in the current envionment to the given value.
175      * Checks that the new binding is compatible with any current binding.
176      * @param var a Node_RuleVariable defining the variable to bind
177      * @param value the value to bind
178      * @return false if the binding fails
179      */
180     public boolean bind(Node var, Node value) {
181         if (var instanceof Node_RuleVariable) {
182             return bind(((Node_RuleVariable)var).getIndex(), value);
183         } else {
184             return var.sameValueAs(value);
185         }
186     }
187     
188     /**
189      * Bind a variable in the current envionment to the given value.
190      * Overrides and ignores any current binding.
191      * @param var a Node_RuleVariable defining the variable to bind
192      * @param value the value to bind
193      */
194     public void bindNoCheck(Node_RuleVariable var, Node value) {
195         environment[var.getIndex()] = value;
196     }
197     
198     /**
199      * Instantiate a triple pattern against the current environment.
200      * This version handles unbound varibles by turning them into bNodes.
201      * @param clause the triple pattern to match
202      * @param env the current binding environment
203      * @return a new, instantiated triple
204      */
205     public Triple instantiate(TriplePattern pattern) {
206         Node s = getGroundVersion(pattern.getSubject());
207         if (s.isVariable()) s = Node.createAnon();
208         Node p = getGroundVersion(pattern.getPredicate());
209         if (p.isVariable()) p = Node.createAnon();
210         Node o = getGroundVersion(pattern.getObject());
211         if (o.isVariable()) o = Node.createAnon();
212         return new Triple(s, p, o);
213     }
214     
215 }
216
217 /*
218     (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
219     All rights reserved.
220
221     Redistribution and use in source and binary forms, with or without
222     modification, are permitted provided that the following conditions
223     are met:
224
225     1. Redistributions of source code must retain the above copyright
226        notice, this list of conditions and the following disclaimer.
227
228     2. Redistributions in binary form must reproduce the above copyright
229        notice, this list of conditions and the following disclaimer in the
230        documentation and/or other materials provided with the distribution.
231
232     3. The name of the author may not be used to endorse or promote products
233        derived from this software without specific prior written permission.
234
235     THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
236     IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
237     OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
238     IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
239     INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
240     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
241     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
242     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
243     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
244     THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
245 */
246
247
Popular Tags