KickJava   Java API By Example, From Geeks To Geeks.

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


1 /******************************************************************
2  * File: BindingVector.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: BindingVector.java,v 1.21 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.*;
14 import com.hp.hpl.jena.reasoner.rulesys.*;
15 import com.hp.hpl.jena.util.PrintUtil;
16
17 import java.util.*;
18
19 /**
20  * An implementation of a binding environment that maintains
21  * a single array of bound values for the variables in a rule.
22  * Stack management is done externally. This is intended for use in
23  * the Brule system and so also supports variable-variable bindings by
24  * use of reference chains.
25  *
26  * @author <a HREF="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
27  * @version $Revision: 1.21 $ on $Date: 2005/02/21 12:17:39 $
28  */
29 public class BindingVector implements BindingEnvironment {
30     
31     /** The current binding set */
32     protected Node[] environment;
33     
34     /**
35      * Constructor - create an empty binding environment
36      */
37     public BindingVector() {
38         environment = new Node[BindingStack.MAX_VAR];
39     }
40     
41     /**
42      * Constructor - create a binding environment from a vector of bindings
43      */
44     public BindingVector(Node [] env) {
45         environment = env;
46     }
47     
48     /**
49      * Constructor - create a binding environment which is a copy
50      * of the given environment
51      */
52     public BindingVector(BindingVector clone) {
53         Node[] orig = clone.environment;
54         environment = new Node[orig.length];
55         System.arraycopy(orig, 0, environment, 0, orig.length);
56     }
57     
58     /**
59      * Return the current array of bindings. Useful for fast access to
60      * serveral bindings, not useful for doing updates.
61      */
62     public Node[] getEnvironment() {
63         return environment;
64     }
65         
66     /**
67      * If the node is a variable then return the current binding (null if not bound)
68      * otherwise return the node itself.
69      */
70     public Node getBinding(Node node) {
71         if (node instanceof Node_RuleVariable) {
72             Node val = environment[((Node_RuleVariable)node).getIndex()];
73             if (val instanceof Node_RuleVariable) {
74                 return getBinding(val);
75             } else {
76                 return val;
77             }
78         } else if (node instanceof Node_ANY) {
79             return null;
80         } else if (Functor.isFunctor(node)) {
81             Functor functor = (Functor)node.getLiteral().getValue();
82             if (functor.isGround()) return node;
83             Node[] args = functor.getArgs();
84             ArrayList boundargs = new ArrayList(args.length);
85             for (int i = 0; i < args.length; i++) {
86                 Object JavaDoc binding = getBinding(args[i]);
87                 if (binding == null) {
88                     // Not sufficently bound to instantiate functor yet
89 return null;
90                 }
91                 boundargs.add(binding);
92             }
93             Functor newf = new Functor( functor.getName(), boundargs );
94             return Functor.makeFunctorNode( newf );
95         } else {
96             return node;
97         }
98     }
99     
100     /**
101      * Return the most ground version of the node. If the node is not a variable
102      * just return it, if it is a varible bound in this enviroment return the binding,
103      * if it is an unbound variable return the variable.
104      */
105     public Node getGroundVersion(Node node) {
106         Node bind = getBinding(node);
107         if (bind == null) {
108             return node;
109         } else {
110             return bind;
111         }
112     }
113     
114     /**
115      * Bind the ith variable in the current envionment to the given value.
116      * Checks that the new binding is compatible with any current binding.
117      * Handles aliased variables.
118      * @return false if the binding fails
119      */
120     public boolean bind(int i, Node value) {
121         Node node = environment[i];
122         if (node == null) {
123             environment[i] = value;
124             return true;
125         } else if (node instanceof Node_RuleVariable) {
126             environment[i] = value;
127             return bind(((Node_RuleVariable)node).getIndex(), value);
128         } else {
129             return node.sameValueAs(value);
130         }
131     }
132     
133     /**
134      * Bind a variable in the current envionment to the given value.
135      * Checks that the new binding is compatible with any current binding.
136      * @param var a Node_RuleVariable defining the variable to bind
137      * @param value the value to bind
138      * @return false if the binding fails
139      */
140     public boolean bind(Node var, Node value) {
141         if (var instanceof Node_RuleVariable) {
142             return bind(((Node_RuleVariable)var).getIndex(), value);
143         } else {
144             return var.sameValueAs(value);
145         }
146     }
147    
148     /**
149      * Bind the variables in a goal pattern using the binding environment, to
150      * generate a more specialized goal
151      * @param goal the TriplePattern to be instantiated
152      * @return a TriplePattern obtained from the goal by substituting current bindinds
153      */
154     public TriplePattern partInstantiate(TriplePattern goal) {
155         return new TriplePattern(
156                 getGroundVersion(goal.getSubject()),
157                 getGroundVersion(goal.getPredicate()),
158                 getGroundVersion(goal.getObject())
159         );
160     }
161     
162 // Replaced by version below for consistency with stack variant
163 // /**
164 // * Instatiate a goal pattern using the binding environment
165 // * @param goal the TriplePattern to be instantiated
166 // * @return an instantiated Triple
167 // */
168 // public Triple instantiate(TriplePattern goal) {
169 // return new Triple(
170 // getGroundVersion(goal.getSubject()),
171 // getGroundVersion(goal.getPredicate()),
172 // getGroundVersion(goal.getObject())
173 // );
174 // }
175
176     /**
177      * Instantiate a triple pattern against the current environment.
178      * This version handles unbound varibles by turning them into bNodes.
179      * @param clause the triple pattern to match
180      * @param env the current binding environment
181      * @return a new, instantiated triple
182      */
183     public Triple instantiate(TriplePattern pattern) {
184         Node s = getGroundVersion(pattern.getSubject());
185         if (s.isVariable()) s = Node.createAnon();
186         Node p = getGroundVersion(pattern.getPredicate());
187         if (p.isVariable()) p = Node.createAnon();
188         Node o = getGroundVersion(pattern.getObject());
189         if (o.isVariable()) o = Node.createAnon();
190         return new Triple(s, p, o);
191     }
192     
193     /**
194      * Printable form
195      */
196     public String JavaDoc toString() {
197         StringBuffer JavaDoc buffer = new StringBuffer JavaDoc();
198         for (int i = 0; i < environment.length; i++) {
199             if (environment[i] == null) {
200                 buffer.append("-");
201             } else {
202                 buffer.append(PrintUtil.print(environment[i]));
203             }
204             buffer.append(" ");
205         }
206         return buffer.toString();
207     }
208     
209     /**
210      * Unify a goal with the head of a rule.
211      * @param goal the goal pattern which it being matched to a rule
212      * @param head the head pattern of the rule which is being instantiated
213      * @return An initialized binding environment for the rule variables
214      * or null if the unificatin fails. If a variable in the environment becomes
215      * aliased to another variable through the unification this is represented
216      * by having its value in the environment be the variable to which it is aliased.
217      */
218     public static BindingVector unify(TriplePattern goal, TriplePattern head) {
219         return unify(goal, head, BindingStack.MAX_VAR);
220     }
221         
222     /**
223      * Unify a goal with the head of a rule. This is a poor-man's unification,
224      * we should try swtiching to a more conventional global-variables-with-trail
225      * implementation in the future.
226      * @param goal the goal pattern which it being matched to a rule
227      * @param head the head pattern of the rule which is being instantiated
228      * @param numRuleVars the length of the environment to allocate.
229      * @return An initialized binding environment for the rule variables
230      * or null if the unification fails. If a variable in the environment becomes
231      * aliased to another variable through the unification this is represented
232      * by having its value in the environment be the variable to which it is aliased.
233      */
234     public static BindingVector unify(TriplePattern goal, TriplePattern head, int numRuleVars) {
235         Node[] gEnv = new Node[BindingStack.MAX_VAR];
236         Node[] hEnv = new Node[numRuleVars];
237         
238         if (!unify(goal.getSubject(), head.getSubject(), gEnv, hEnv)) {
239             return null;
240         }
241         if (!unify(goal.getPredicate(), head.getPredicate(), gEnv, hEnv)) {
242             return null;
243         }
244         
245         Node gObj = goal.getObject();
246         Node hObj = head.getObject();
247         if (Functor.isFunctor(gObj)) {
248             Functor gFunctor = (Functor)gObj.getLiteral().getValue();
249             if (Functor.isFunctor(hObj)) {
250                 Functor hFunctor = (Functor)hObj.getLiteral().getValue();
251                 if ( ! gFunctor.getName().equals(hFunctor.getName()) ) {
252                     return null;
253                 }
254                 Node[] gArgs = gFunctor.getArgs();
255                 Node[] hArgs = hFunctor.getArgs();
256                 if ( gArgs.length != hArgs.length ) return null;
257                 for (int i = 0; i < gArgs.length; i++) {
258                     if (! unify(gArgs[i], hArgs[i], gEnv, hEnv) ) {
259                         return null;
260                     }
261                 }
262             } else if (hObj instanceof Node_RuleVariable) {
263                 // temp debug ...
264 // Check the goal functor is fully ground
265 if (gFunctor.isGround(new BindingVector(gEnv))) {
266                     if (!unify(gObj, hObj, gEnv, hEnv)) return null;
267                 }
268                 // ... end debug
269 } else {
270                 // unifying simple ground object with functor, failure
271 return null;
272             }
273         } else {
274             if (!unify(gObj, hObj, gEnv, hEnv)) return null;
275         }
276         // Successful bind if we get here
277 return new BindingVector(hEnv);
278     }
279     
280     /**
281      * Unify a single pair of goal/head nodes. Unification of a head var to
282      * a goal var is recorded using an Integer in the head env to point to a
283      * goal env and storing the head var in the goal env slot.
284      * @return true if they are unifiable, side effects the environments
285      */
286     private static boolean unify(Node gNode, Node hNode, Node[] gEnv, Node[] hEnv) {
287         if (hNode instanceof Node_RuleVariable) {
288             int hIndex = ((Node_RuleVariable)hNode).getIndex();
289             if (gNode instanceof Node_RuleVariable) {
290                 // Record variable bind between head and goal to detect aliases
291 int gIndex = ((Node_RuleVariable)gNode).getIndex();
292                 if (gIndex < 0) return true;
293                 if (gEnv[gIndex] == null) {
294                     // First time bind so record link
295 gEnv[gIndex] = hNode;
296                 } else {
297                     // aliased var so follow trail to alias
298 // but ignore self-aliases
299 Node gVal = gEnv[gIndex];
300                     if (hIndex != gIndex || ! (gVal instanceof Node_RuleVariable)) {
301                         hEnv[hIndex] = gVal;
302                     }
303                 }
304             } else {
305                 Node hVal = hEnv[hIndex];
306                 if (hVal == null) {
307                     hEnv[hIndex] = gNode;
308                 } else {
309                     // Already bound
310 if (hVal instanceof Node_RuleVariable) {
311                         // Already an aliased variable, so bind both this an the alias
312 hEnv[((Node_RuleVariable)hVal).getIndex()] = gNode;
313                         hEnv[hIndex] = gNode;
314                     } else {
315                         // Already bound to a ground node
316 return hVal.sameValueAs(gNode);
317                     }
318                 }
319             }
320             return true;
321         } else {
322             if (gNode instanceof Node_RuleVariable) {
323                 int gIndex = ((Node_RuleVariable)gNode).getIndex();
324                 if (gIndex < 0) return true;
325                 Node gVal = gEnv[gIndex];
326                 if (gVal == null) {
327                     //. No variable alias so just record binding
328 gEnv[gIndex] = hNode;
329                 } else if (gVal instanceof Node_RuleVariable) {
330                     // Already an alias
331 hEnv[((Node_RuleVariable)gVal).getIndex()] = hNode;
332                     gEnv[gIndex] = hNode;
333                 } else {
334                     return gVal.sameValueAs(hNode);
335                 }
336                 return true;
337             } else {
338                 return hNode.sameValueAs(gNode);
339             }
340         }
341     }
342   
343     /** Equality override */
344     public boolean equals(Object JavaDoc o) {
345         // Pass 1 - just check basic shape
346 if (! (o instanceof BindingVector) ) return false;
347         Node[] other = ((BindingVector)o).environment;
348         if (environment.length != other.length) return false;
349         for (int i = 0; i < environment.length; i++) {
350             Node n = environment[i];
351             Node no = other[i];
352             if (n == null) {
353                 if (no != null) return false;
354             } else {
355                 if (! n.sameValueAs(no)) return false;
356             }
357         }
358         return true;
359     }
360         
361     /** hash function override */
362     public int hashCode() {
363         int hash = 0;
364         for (int i = 0; i < environment.length; i++) {
365             Node n = environment[i];
366             hash = (hash << 1) ^ (n == null ? 0x537c: n.hashCode());
367         }
368         return hash;
369     }
370     
371
372 }
373
374
375
376 /*
377     (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
378     All rights reserved.
379
380     Redistribution and use in source and binary forms, with or without
381     modification, are permitted provided that the following conditions
382     are met:
383
384     1. Redistributions of source code must retain the above copyright
385        notice, this list of conditions and the following disclaimer.
386
387     2. Redistributions in binary form must reproduce the above copyright
388        notice, this list of conditions and the following disclaimer in the
389        documentation and/or other materials provided with the distribution.
390
391     3. The name of the author may not be used to endorse or promote products
392        derived from this software without specific prior written permission.
393
394     THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
395     IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
396     OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
397     IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
398     INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
399     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
400     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
401     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
402     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
403     THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
404 */
405
Popular Tags