KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > hp > hpl > jena > ontology > daml > PropertyIterator


1 /*****************************************************************************
2  * Source code information
3  * -----------------------
4  * Original author Ian Dickinson, HP Labs Bristol
5  * Author email Ian.Dickinson@hp.com
6  * Package Jena
7  * Created 11 Sept 2001
8  * Filename $RCSfile: PropertyIterator.java,v $
9  * Revision $Revision: 1.14 $
10  * Release status Preview-release $State: Exp $
11  *
12  * Last modified on $Date: 2005/02/21 12:05:04 $
13  * by $Author: andy_seaborne $
14  *
15  * (c) Copyright 2002, 2003, 2004, 2005 Hewlett-Packard Development Company, LP
16  * (see footer for full conditions)
17  *****************************************************************************/
18
19 // Package
20 ///////////////
21 package com.hp.hpl.jena.ontology.daml;
22
23
24 // Imports
25 ///////////////
26
27 import java.util.*;
28
29 import com.hp.hpl.jena.rdf.model.*;
30 import com.hp.hpl.jena.util.iterator.*;
31 import com.hp.hpl.jena.vocabulary.DAML_OIL;
32
33
34
35 /**
36  * <p>
37  * Provides a means of traversing the relationships in a DAML model, respecting
38  * some of the extended semantics of DAML+OIL over RDF. In particular, the
39  * PropertyIterator knows about class, property and instance equivalence,
40  * transitive properties, inverse properties, the class hierarchy and the
41  * property hierarchy.
42  * </p>
43  * <p>
44  * Given a property P, and a resource x, iterates over all the y such that
45  * <code>x P y</code>, respecting the fact that P may be transitive (so
46  * <code>x P y</code> and <code>y P z</code> implies <code>x P z</code>), and
47  * symmetric (so <code>x P y</code> implies <code>y P x</code>). The iterator
48  * is lazily evaluated, so changes to the model while iterating could generate
49  * unpredictable results. The iterator does do loop detection, so should always
50  * terminate (assuming the model is finite!). Deletion is not supported.
51  * </p>
52  * <p>
53  * This iterator also supports the setting of a default value. The default value
54  * is an object that will be returned as the last value of the iteration, unless
55  * it has already been returned earlier.
56  * </p>
57  *
58  * @author Ian Dickinson, HP Labs (<a HREF="mailto:Ian.Dickinson@hp.com">email</a>)
59  * @version CVS info: $Id: PropertyIterator.java,v 1.14 2005/02/21 12:05:04 andy_seaborne Exp $
60  * @since Jena 1.3.0 (was previously in package com.hp.hpl.jena.ontology.daml.impl).
61  */
62 public class PropertyIterator
63     implements Iterator
64 {
65     // Constants
66 //////////////////////////////////
67
68
69     // Static variables
70 //////////////////////////////////
71
72
73     // Instance variables
74 //////////////////////////////////
75
76     /** The queue of nodes to be evaluated */
77     protected LinkedList m_nodeQueue = new LinkedList();
78
79     /** The property we're evaluating */
80     protected Property m_pred = null;
81
82     /** The inverse of pred, or null */
83     protected Property m_inverse = null;
84
85     /** Collection of properties equivalent to m_pred */
86     protected HashSet m_predEquivs = new HashSet();
87
88     /** Collection of properties equivalent to m_inverse */
89     protected HashSet m_inverseEquivs = new HashSet();
90
91     /** Flag to say if pred is transitive */
92     protected boolean m_transitive = false;
93
94     /** Set of nodes we've seen on this trip */
95     protected WeakHashMap m_seen = new WeakHashMap();
96
97     /** The resource we started from (if only one) */
98     protected Resource m_root = null;
99
100     /** The resources we started from (if many) */
101     protected List m_roots = null;
102
103     /** The default value for the iterator, or null if no default */
104     protected Object JavaDoc m_defaultValue = null;
105
106     /** A flag to show that the default value has been returned */
107     protected boolean m_defaultValueSeen = false;
108
109     /** A flag to control whether we use equivalent values during the iteration */
110     protected boolean m_useEquivalence = true;
111
112     /** The model we are operating on */
113     protected Model m_model = null;
114
115
116
117     // Constructors
118 //////////////////////////////////
119
120     /**
121      * Construct a property iterator for the given property, starting from the
122      * given resource. The property may be defined to be symmetric by supplying
123      * its inverse (which could be itself), and/or transitive. The property may also
124      * be defined to be reflexive, in which case root itself will be returned as
125      * a member of the iteration.
126      *
127      * @param root The root resource from whence to start iterating over the closure of pred
128      * @param pred The property to iterate over
129      * @param inverse The inverse of pred, or null if pred has no inverse. The inverse is used
130      * to include resource y in the iteration if P' = inverse(P) and y P' x.
131      * @param isTransitive If true, the property is transitive
132      * @param isReflexive If true, the property is reflexive (so, the root resource will be included
133      * in the iteration).
134      */
135     public PropertyIterator( Resource root, Property pred, Property inverse, boolean isTransitive, boolean isReflexive ) {
136         this( root, pred, inverse, isTransitive, isReflexive, true );
137     }
138
139     /**
140      * Construct a property iterator for the given property, starting from the
141      * given resource. The property may be defined to be symmetric by supplying
142      * its inverse (which could be itself), and/or transitive. The property may also
143      * be defined to be reflexive, in which case root itself will be returned as
144      * a member of the iteration.
145      *
146      * @param root The root resource from whence to start iterating over the closure of pred
147      * @param pred The property to iterate over
148      * @param inverse The inverse of pred, or null if pred has no inverse. The inverse is used
149      * to include resource y in the iteration if P' = inverse(P) and y P' x.
150      * @param isTransitive If true, the property is transitive
151      * @param isReflexive If true, the property is reflexive (so, the root resource will be included
152      * in the iteration).
153      * @param useEquivalence If true, equivalence between DAML values will be included in the
154      * iteration (unless the model containing the DAML values
155      * has equivalence switched off via {@link DAMLModel#setUseEquivalence}).
156      */
157     public PropertyIterator( Resource root, Property pred, Property inverse, boolean isTransitive,
158                              boolean isReflexive, boolean useEquivalence ) {
159         m_root = root;
160         m_pred = pred;
161         m_inverse = inverse;
162         m_transitive = isTransitive;
163         m_useEquivalence = useEquivalence;
164         setModel();
165         cachePropertyEquivs();
166
167         // the root only goes on the queue if the relation is reflexive
168 if (isReflexive) {
169            enqueue( root );
170         }
171         else {
172             // otherwise, we'll just start with the relations of the root
173 expandQueue( root );
174         }
175     }
176
177
178     /**
179      * Construct a property iterator for the given property, starting from the
180      * given set of resources. The property may be defined to be symmetric by supplying
181      * its inverse (which could be itself), and/or transitive. The property may also
182      * be defined to be reflexive, in which case all of the given root resources will
183      * be returned as members of the iteration.
184      *
185      * @param roots A set of root resources from whence to start iterating over the closure of pred,
186      * represented as an iterator
187      * @param pred The property to iterate over
188      * @param inverse The inverse of pred, or null if pred has no inverse. The inverse is used
189      * to include resource y in the iteration if P' = inverse(P) and y P' x.
190      * @param isTransitive If true, the property is transitive
191      * @param isReflexive If true, the property is reflexive (so, the root resources will be included
192      * in the iteration).
193      */
194     public PropertyIterator( Iterator roots, Property pred, Property inverse, boolean isTransitive, boolean isReflexive ) {
195         this( roots, pred, inverse, isTransitive, isReflexive, true );
196     }
197
198
199     /**
200      * Construct a property iterator for the given property, starting from the
201      * given set of resources. The property may be defined to be symmetric by supplying
202      * its inverse (which could be itself), and/or transitive. The property may also
203      * be defined to be reflexive, in which case all of the given root resources will
204      * be returned as members of the iteration.
205      *
206      * @param roots A set of root resources from whence to start iterating over the closure of pred,
207      * represented as an iterator
208      * @param pred The property to iterate over
209      * @param inverse The inverse of pred, or null if pred has no inverse. The inverse is used
210      * to include resource y in the iteration if P' = inverse(P) and y P' x.
211      * @param isTransitive If true, the property is transitive
212      * @param isReflexive If true, the property is reflexive (so, the root resources will be included
213      * in the iteration).
214      * @param useEquivalence If true, equivalence between DAML values will be included in the
215      * iteration (unless the model containing the DAML values has equivalence
216      * switched off via {@link DAMLModel#setUseEquivalence}.
217      */
218     public PropertyIterator( Iterator roots, Property pred, Property inverse, boolean isTransitive,
219                              boolean isReflexive, boolean useEquivalence ) {
220         // copy the roots of the traversal
221 m_roots = new ArrayList();
222         m_pred = pred;
223         m_inverse = inverse;
224         m_transitive = isTransitive;
225         m_useEquivalence = useEquivalence;
226         setModel();
227         cachePropertyEquivs();
228
229         // the root only goes on the queue if the relation is reflexive
230 if (isReflexive) {
231             // reflexive, so we queue each root to be expanded (and it will get returned by next())
232 while (roots.hasNext()) {
233                 Resource next = (Resource) roots.next();
234
235                 if (m_model == null && next.getModel() != null) {
236                     // keep a reference to the model if we find one
237 m_model = next.getModel();
238                 }
239
240                 m_roots.add( next );
241                 enqueue( next );
242             }
243         }
244         else {
245             // not reflexive, so we'll just start with the relations of the root on the queue
246 while (roots.hasNext()) {
247                 Resource next = (Resource) roots.next();
248
249                 if (m_model == null && next.getModel() != null) {
250                     // keep a reference to the model if we find one
251 m_model = next.getModel();
252                 }
253
254                 m_roots.add( next );
255                 expandQueue( next );
256             }
257         }
258     }
259
260
261     // External signature methods
262 //////////////////////////////////
263
264     /**
265      * Answer true if the iteration over the closure of the predicate will answer any values that have
266      * not yet been returned.
267      *
268      * @return True if there is at least one more element in the iteration
269      */
270     public boolean hasNext() {
271         // is there at least one more node in the queue?
272 return !m_nodeQueue.isEmpty() || (hasDefaultValue() && !m_defaultValueSeen);
273     }
274
275
276     /**
277      * Answer the next RDFNode in the iteration over the given predicate. Note that each node in the
278      * closure of the predicate will be answered only once, to avoid endless loops.
279      *
280      * @return The next RDFNode in the iteration over the closure of the predicate.
281      * @exception java.util.NoSuchElementException if the iterator has no more elements
282      */
283     public Object JavaDoc next() {
284         if (!m_nodeQueue.isEmpty()) {
285             // get the next node from the queue, this will be the one that we return
286 RDFNode next = (RDFNode) m_nodeQueue.removeFirst();
287
288             // is this the default value?
289 if (hasDefaultValue() && m_defaultValue.equals( next )) {
290                 m_defaultValueSeen = true;
291             }
292
293             // now add the relations of the node to the end of the queue
294 if (next instanceof com.hp.hpl.jena.rdf.model.Resource) {
295                 expandQueue( (Resource) next );
296             }
297
298             // answer the next node in the interation
299 return next;
300         }
301         else if (hasDefaultValue() && !m_defaultValueSeen) {
302             // return the default value for this iterator
303 m_defaultValueSeen = true;
304             return m_defaultValue;
305         }
306         else {
307             // no more nodes, so this is an error
308 throw new NoSuchElementException( "Tried to access next() element from empty property iterator" );
309         }
310     }
311
312
313     /**
314      * Unsupported operation in this iterator.
315      *
316      * @exception java.lang.UnsupportedOperationException
317      */
318     public void remove() {
319         throw new UnsupportedOperationException JavaDoc( "Cannot remove elements from a property iterator" );
320     }
321
322
323     /**
324      * Set the default value for this iteration, which will be a value that
325      * is guaranteed to be returned as a member of the iteration. To guarantee
326      * that the default value is only returned if it has not already been
327      * returned by the iterator, setting the default value should occur before
328      * the first call to {@link #next}.
329      *
330      * @param defaultValue The default value for the iteration, or null for
331      * there to be no default value. The default default
332      * value is null.
333      */
334     public void setDefaultValue( Object JavaDoc defaultValue ) {
335         m_defaultValue = defaultValue;
336     }
337
338
339     /**
340      * Answer true if this iteration has a default value.
341      *
342      * @return true if there is a default value
343      */
344     public boolean hasDefaultValue() {
345         return m_defaultValue != null;
346     }
347
348
349
350     // Internal implementation methods
351 //////////////////////////////////
352
353
354     /**
355      * Queue a node onto the evaluation queue, but only if it has not already been evaluated
356      * (to avoid loops).
357      *
358      * @param node The node to add to the queue
359      */
360     private void enqueue( RDFNode node ) {
361         if (!m_seen.containsKey( node )) {
362             // mark this node as seen
363 m_seen.put( node, Boolean.TRUE );
364
365             // add it to the queue
366 m_nodeQueue.addLast( node );
367
368             // also queue up the equivalens to the node
369 if (getUseEquivalence() && node instanceof DAMLCommon) {
370                 for (Iterator i = ((DAMLCommon) node).getEquivalentValues(); i.hasNext(); ) {
371                     enqueue( (RDFNode) i.next() );
372                 }
373             }
374         }
375     }
376
377
378     /**
379      * Expand the queue with the arcs to/from the given resource
380      *
381      * @param r The resource we're expanding
382      */
383     protected void expandQueue( Resource r ) {
384         // add all outgoing arcs if we're at the root or the predicate is transitive
385 if (m_pred != null && (m_transitive || isRoot( r ))) {
386             // we want all the related items from this node
387 for (Iterator i = getStatementObjects( r );
388                  i.hasNext();
389                  enqueue( (RDFNode) i.next() ));
390         }
391
392         // if we know the inverse, we also add the incoming arcs to this node
393 if (m_inverse != null && (m_transitive || isRoot( r ))) {
394             // find statements whose predicate is m_inverse and object is current node
395 for (Iterator i = getStatementSubjects( r );
396                  i.hasNext();
397                  enqueue( (RDFNode) i.next() ));
398         }
399     }
400
401
402     /**
403      * Answer true if the given resource was one of the starting points.
404      *
405      * @param r A resource
406      * @return True if resource r was one of the roots of this iteration.
407      */
408     protected boolean isRoot( Resource r ) {
409         if (m_roots != null) {
410             // started with a set of roots
411 return m_roots.contains( r );
412         }
413         else {
414             // just the one root - compare this one to it
415 return r == m_root;
416         }
417     }
418
419
420     /**
421      * Answer an iterator over objects of statements with res
422      * as subject, and m_pred or one of its equivalent properties as property,
423      * including all of the equivalent values to the object.
424      *
425      * @param res A resource
426      * @return An iterator over the object of any statements whose subject is res.
427      */
428     protected Iterator getStatementObjects( Resource res )
429     {
430         Iterator i = null;
431
432         if (getUseEquivalence() && res instanceof DAMLCommon) {
433             // consider equivalents for res and for m_pred
434 for (Iterator j = m_predEquivs.iterator(); j.hasNext(); ) {
435                 // get an iterator for the values of the resource with this predicate
436 Iterator pIter = new PropertyIterator( res, (Property) j.next(), null, m_transitive, false, false );
437
438                 // build a joint iterator
439 i = (i == null) ? pIter : new ConcatenatedIterator( pIter, i );
440             }
441         }
442         else {
443             // don't use equivalents
444 if (m_model != null) {
445                 // we have a model to query, so use it to get the object of the triple
446 i = m_model.listObjectsOfProperty( res, m_pred );
447             }
448             else {
449                 // no model (can occur when using built-in constants from vocab)
450 i = new LinkedList().iterator();
451             }
452         }
453
454         return i;
455     }
456
457
458     /**
459      * Answer an iterator over subjects of statements with res (or one of its equivalents)
460      * as object, and m_inverse or one of its equivalent properties as property.
461      *
462      * @param res A resource
463      * @return An iterator over the subject of any statements whose object is res.
464      */
465     protected Iterator getStatementSubjects( Resource res )
466     {
467         Iterator i = null;
468
469         if (getUseEquivalence() && res instanceof DAMLCommon) {
470             // consider equivalents for res and for m_pred
471 for (Iterator j = m_inverseEquivs.iterator(); j.hasNext(); ) {
472                 // get an iterator for the values of the resource with this predicate
473 Iterator pIter = new PropertyIterator( res, null, (Property) j.next(), m_transitive, false, false );
474
475                 // build a joint iterator
476 i = (i == null) ? pIter : new ConcatenatedIterator( pIter, i );
477             }
478         }
479         else {
480             // don't use equivalents
481 if (m_model != null) {
482                 // we have a model to query, so use it to get the subject of the triple
483 i = m_model.listSubjectsWithProperty( m_inverse, res );
484             }
485             else {
486                 // no model (can occur when using built-in constants from vocab)
487 i = new LinkedList().iterator();
488             }
489         }
490
491         return i;
492     }
493
494
495     /**
496      * Cache the equivalent properties to the principal properties and their inverses we
497      * are using
498      */
499     protected void cachePropertyEquivs() {
500         if (getUseEquivalence()) {
501             // store the equivalent properties to m_pred
502 if (m_pred != null) {
503                 if (m_pred instanceof DAMLProperty) {
504                     // daml property - we know about equivalence classes for these
505 for (Iterator i = ((DAMLProperty) m_pred).getEquivalentValues(); i.hasNext(); ) {
506                         cacheProperty( m_predEquivs, (Property) i.next() );
507                     }
508                 }
509                 else {
510                     // normal rdf property, is its own equiv
511 cacheProperty( m_predEquivs, m_pred );
512                 }
513             }
514
515             // store the equivalent properties to m_inverse
516 if (m_inverse != null) {
517                 if (m_inverse instanceof DAMLProperty) {
518                     // daml property - we know about equivalence classes for these
519 for (Iterator i = ((DAMLProperty) m_inverse).getEquivalentValues(); i.hasNext(); ) {
520                         cacheProperty( m_inverseEquivs, (Property) i.next() );
521                     }
522                 }
523                 else {
524                     // normal rdf property, is its own equiv
525 cacheProperty( m_inverseEquivs, m_inverse );
526                 }
527             }
528         }
529     }
530
531
532     /**
533      * Add the given property, and it sub-properties, to the set of cached properties.
534      *
535      * @param s A set
536      * @param p A property to add to the set s.
537      */
538     protected void cacheProperty( HashSet s, Property p ) {
539         s.add( p );
540
541         // also add the sub-properties of this property: if the sub-prop holds,
542 // this property holds also
543 // check for p being 'subPropertyOf' to avoid infinite regress!
544 if (p instanceof DAMLProperty && !p.getLocalName().equals( DAML_OIL.subPropertyOf.getLocalName() )) {
545             for (Iterator i = ((DAMLProperty) p).getSubProperties(); i.hasNext(); ) {
546                 s.add( i.next() );
547             }
548         }
549     }
550
551
552     /**
553      * Attempt to determine which model we are working on
554      */
555     protected void setModel() {
556         // try the root object, if defined
557 if (m_root != null && m_root.getModel() != null) {
558             m_model = m_root.getModel();
559             return;
560         }
561
562         // try the predicate object
563 if (m_pred != null && m_pred.getModel() != null) {
564             m_model = m_pred.getModel();
565             return;
566         }
567
568         // try the predicate inverse
569 if (m_inverse != null && m_inverse.getModel() != null) {
570             m_model = m_inverse.getModel();
571             return;
572         }
573
574         // try the set of roots
575 if (m_roots != null) {
576             for (Iterator i = m_roots.iterator(); i.hasNext(); ) {
577                 RDFNode n = (RDFNode) i.next();
578                 if (n instanceof Resource && ((Resource) n).getModel() != null) {
579                     m_model = ((Resource) n).getModel();
580                     return;
581                 }
582             }
583         }
584     }
585
586
587     /**
588      * Answer true if we are computing with equivalence classes at the moment.
589      *
590      * @return True if equivlance is to be computed.
591      */
592     protected boolean getUseEquivalence() {
593         /*
594         // if we have a model, it must have equivalence switched on
595         // if no model, default to relying on the m_useEquivalence setting
596         boolean modelEquivFlag = m_model == null ||
597                                  !(m_model instanceof DAMLModel) ||
598                                  ((DAMLModel) m_model).getUseEquivalence();
599
600         return m_useEquivalence && modelEquivFlag;
601         */
602         // equivalence processing is now handled by the inference engines
603 return false;
604     }
605
606
607
608     //==============================================================================
609 // Inner class definitions
610 //==============================================================================
611
612 }
613
614 /*
615     (c) Copyright 2002, 2003, 2004, 2005 Hewlett-Packard Development Company, LP
616     All rights reserved.
617
618     Redistribution and use in source and binary forms, with or without
619     modification, are permitted provided that the following conditions
620     are met:
621
622     1. Redistributions of source code must retain the above copyright
623        notice, this list of conditions and the following disclaimer.
624
625     2. Redistributions in binary form must reproduce the above copyright
626        notice, this list of conditions and the following disclaimer in the
627        documentation and/or other materials provided with the distribution.
628
629     3. The name of the author may not be used to endorse or promote products
630        derived from this software without specific prior written permission.
631
632     THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
633     IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
634     OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
635     IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
636     INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
637     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
638     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
639     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
640     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
641     THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
642 */
643
644
Popular Tags