GraphMatcher


1   /*
2    *  (c) Copyright 2002, 2002, 2003, 2004, 2005 Hewlett-Packard Development Company, LP
3    *  
4    *  All rights reserved.
5    * 
6    * See end of file.
7    */
8    
9   
10  package com.hp.hpl.jena.graph.impl;
11  import java.util.*;
12  
13  import com.hp.hpl.jena.graph.*;
14  import com.hp.hpl.jena.util.CollectionFactory;
15  import com.hp.hpl.jena.util.iterator.*;
16  import com.hp.hpl.jena.shared.*;
17  
18  /**
19   * An implemantation of graph isomorphism for Graph equality.
20   * The underlying algorithm is exponential but will only enter
21   * a non-deterministic polynomial part when there are a lot of difficult to
22   * distinguish anonymous nodes
23   * connected to each other by statements with the same property(s).
24   * Non-pathological examples, where most nodes have some properties that
25   * help distinguish them from other nodes, will experience nearly linear
26   * performance.
27   *<p>
28   * @author  jjc
29   * @version  Release='$Name:  $' Revision='$Revision: 1.9 $' Date='$Date: 2005/02/21 11:52:10 $'
30   */
31  public class GraphMatcher extends java.lang.Object   {
32      static private Random random = new Random(0);
33   /**
34   * Are the two models isomorphic?
35   * The isomorphism is defined as a bijection between the anonymous
36   * variables such that the statements are identical. 
37   * This is
38       * described in 
39       * <a HREF="http://www.w3.org/TR/rdf-concepts#section-Graph-syntax">
40       * http://www.w3.org/TR/rdf-concepts#section-Graph-syntax
41       * </a>
42   */
43      static public boolean equals(Graph m1,Graph m2)   {
44          if ( m1 == m2 )
45              return true;
46          return match(m1,m2) != null;
47      }  
48      
49      static public int hashCode(Graph g) {
50          ClosableIterator ci = GraphUtil.findAll( g );
51          int hash = 0;
52          GraphMatcher gm = new GraphMatcher(g);
53          while ( ci.hasNext() ) {
54              Triple t = (Triple)ci.next();
55              hash += gm.new AnonStatement(t).myHashCode(null);
56          }
57          return hash;
58      }
59  /**
60   * Return an isomorphism between the two models.
61   * This function is nondeterministic in that it may return a 
62   * different bijection on each call, in cases where there are 
63   * multiple isomorphisms between the models.
64   * @return <code>null</code> on failure or an array of related pairs 
65             (arrays of length 2) of anonymous nodes.
66              <code>match(m1,m2)[i][0]</code>  is from <code>m1</code>, 
67              and <code>match(m1,m2)[i][1]</code> is the corresponding node in
68              <code>m2</code>.
69   */
70      static public Node[][] match(Graph m1,Graph m2)  {
71              return new GraphMatcher(m1).match(new GraphMatcher(m2));
72      }
73      /* NOTE: inner classes
74       *    We use a number of non-static inner classes, these all
75       *    refer to the GraphMatcher for context.
76       *
77       * NOTE: the built-in hashCode() is not modified, so that Set's etc
78       * still work.
79       * This algorithm depends on a hash function, which I call myHashCode()
80       * This has the somewhat perplexing property of changing as we do
81       * the binding.
82       * obj.myHashCode() depends on:
83       *    -  obj and it's non anonymous subcomponents
84       *    - ModelMatcher.myHashLevel (in the enclosing ModelMatcher)
85       *    - for a bound AnonResource b in obj, it depends on a
86       *      random value generated at the time that b got bound
87       *    - for an unbound AnonResource, if myHashLevel>0, then
88       *      it depends on the value of myHashCode() at myHashLevel-1
89       *
90       *
91       *
92       */
93      static final private boolean TRACE = false;
94      private Graph m;
95      private GraphMatcher other;
96      private int myHashLevel = 0; // This is usually 0, but can be any value
97      // less than MAX_HASH_DEPTH
98      
99      
100     static final private int MAX_HASH_DEPTH = 3;
101     // I don't think there's much
102     // mileage in a huge number here
103     // A large number is likely to be unhelpful in typical
104     // cases, but helps in pathological cases.
105     // The pathological cases are the slowest, so perhaps it
106     // is best to optimise for them.!
107     
108     // The rehashable - hash table
109     // A Map from Integer => Bucket
110     // Most of the time the table is a mess,
111     // this is reflected in state=BAD
112     private Map table;
113     
114     // This variable is mainly for sanity checking and
115     // documentation. It has one logical impact in
116     // AnonResource.myHashCodeFromStatement() and
117     // AnonResource.wrapStatements()
118     // AnonResource.myHashCodeFromStatement() requires
119     // either state != HASH_BAD or myHashLevel = 0,
120     // we ensure that one or other is the case in
121     // AnonResource.wrapStatements().
122     private int state;
123     static final private int REHASHING = 1;
124     static final private int HASH_OK = 2;
125     static final private int HASH_BAD = 4;
126     
127     // As the algorithm proceeds we move resources
128     // from one to the other.
129     // At completion unBoundAnonResources is empty.
130     private Set unboundAnonResources = CollectionFactory.createHashedSet();
131     private Set boundAnonResources = CollectionFactory.createHashedSet();
132     
133     
134     
135     private GraphMatcher(Graph m1x) {
136         m = m1x;
137     }
138     private Node[][] match(GraphMatcher oth) {
139         other = oth;
140         oth.other = this;
141         in(HASH_BAD);
142         if ( m.size() != other.m.size() )
143             return null;
144         int myPrep = prepare(other.m);
145         if ( myPrep == -1 || myPrep != other.prepare(m) ) {
146             return null;
147         }
148         if ( bind() ) {
149             if ( !unboundAnonResources.isEmpty() )
150                 impossible();
151             Node rslt[][] = new Node[boundAnonResources.size()][];
152             int ix = 0;
153             Iterator it = boundAnonResources.iterator();
154             while ( it.hasNext() ) {
155                 AnonResource r = (AnonResource)it.next();
156                 rslt[ix++] = new Node[]{r.r,r.bound.r};
157             }
158             return rslt;
159         }
160         else {
161             return null;
162         }
163     }
164     // bind returns true if we have a binding,
165     // false if not, in either case table is screwed.
166     private boolean bind()   {
167         Set locallyBound = obligBindings();
168         if (locallyBound==null)  // Contradiction reached - fail.
169             return false;
170         check(HASH_OK);
171         Bucket bkt = smallestBucket();
172         if ( bkt == null )
173             return true;  // No smallest bucket - we are finished.
174         Bucket otherBkt = other.matchBucket(bkt);
175         if ( otherBkt != null ) {
176             AnonResource v = bkt.aMember();
177             Iterator candidates = otherBkt.members();
178             // System.out.println("Guessing");
179             while ( candidates.hasNext() ) {
180                 check(HASH_OK|HASH_BAD);
181                 AnonResource otherV = (AnonResource)candidates.next();
182                 trace(true,"Guess: ");
183                 if (!bkt.bind(v,otherBkt,otherV))
184                     continue;
185                 if (bind())
186                     return true;
187                 v.unbind();
188             }
189         }
190         unbindAll(locallyBound);
191         return false;
192     }
193     /*
194      * Called with hashing incorrect.
195      * Returns null if situation is unworkable.
196      * Returns non-null with no outstanding obvious bindings,
197      * and with the hashing correct.
198      * The set of obligatorily bound resources is returned.
199      *
200      */
201     private Set obligBindings() {
202         int hashLevel = 0;
203         boolean newBinding;
204         Set rslt = CollectionFactory.createHashedSet();
205         check(HASH_OK|HASH_BAD);
206         do {
207             if ( rehash(hashLevel) != other.rehash(hashLevel) ){
208                 unbindAll(rslt);
209                 return null;
210             }
211             refinableHash = false;
212             newBinding = false;
213             Iterator singles = scanBuckets();
214             while ( singles.hasNext() ) {
215                 newBinding = true;
216                 Bucket bkt = (Bucket)singles.next();
217                 Bucket otherBkt = other.matchBucket(bkt);
218                 if ( otherBkt == null ) {
219                     unbindAll(rslt);
220                     return null;
221                 }
222                 AnonResource bindMe = bkt.aMember();
223                 if (!bkt.bind(otherBkt)) {
224                     unbindAll(rslt);
225                     return null;
226                 }
227                 rslt.add(bindMe);
228             }
229             if ( newBinding )
230                 hashLevel = 0;
231             else
232                 hashLevel++;
233         } while (hashLevel<MAX_HASH_DEPTH && (refinableHash||newBinding));
234         return rslt;
235     }
236     // Communication between obligBindings and scanBuckets
237     private boolean refinableHash;
238     private Iterator scanBuckets() {
239         // Looks through buckets,
240         // if has single member then return in iterator.
241         // Otherwise if some member of the bucket has friends
242         // we can refine the hash, and we set refinableHash.
243         check(HASH_OK);
244         return new FilterIterator(
245         new Filter() {
246             public boolean accept(Object   o) {
247                 Bucket b = (Bucket)o;
248                 if (b.size()==1)
249                     return true;
250                 if (!refinableHash) {
251                     Iterator it = b.members();
252                     while ( it.hasNext() )
253                         if (!((AnonResource)it.next())
254                         .friends.isEmpty()) {
255                             refinableHash = true;
256                             break;
257                         }
258                 }
259                 return false;
260             }
261         },table.values().iterator());
262         
263     }
264     private void unbindAll(Set s)  {
265         Iterator rs = s.iterator();
266         while (rs.hasNext())
267             ((AnonResource)rs.next()).unbind();
268         in(HASH_BAD);
269     }
270     private int prepare(Graph otherm)  {
271         ClosableIterator ss = GraphUtil.findAll( m );
272         myHashLevel = 0;
273         int hash = 0;
274         try {
275             while ( ss.hasNext() ) {
276                 Triple s = (Triple)ss.next();
277                 AnonStatement ass = new AnonStatement(s);
278                 if ( ass.pattern == NOVARS ) {
279                     ClosableIterator ci = otherm.find(s.getSubject(),s.getPredicate(),
280                             s.getObject());
281                     boolean fnd = ci.hasNext();
282                     ci.close();
283                     if ( !fnd ) return -1;
284                 } else {
285                     hash += ass.myHashCode(ass.vars[0]);
286                     for (int i=0;i<ass.vars.length;i++) {
287                         ass.vars[i].occursIn.add(ass);
288                         for (int j=i+1;j<ass.vars.length;j++) {
289                             ass.vars[i].friends.add(ass.vars[j]);
290                             ass.vars[j].friends.add(ass.vars[i]);
291                         }
292                     }
293                 }
294             }
295             return hash==-1?1:hash;
296         }
297         finally {
298             ss.close();
299         }
300     }
301     private Bucket smallestBucket() {
302         check(HASH_OK);
303         Iterator bit = table.values().iterator();
304         Bucket smallB = null;
305         int smallest = Integer.MAX_VALUE;
306         while ( bit.hasNext() ) {
307             Bucket b = (Bucket)bit.next();
308             int sz = b.size();
309             if ( sz < smallest ) {
310                 smallB = b;
311                 smallest = sz;
312             }
313         }
314         return smallB;
315     }
316     private Bucket matchBucket(Bucket key) {
317         check(HASH_OK);
318         Integer   hash = new Integer  (key.aMember().myHash);
319         Bucket rslt = (Bucket)table.get(hash);
320         if ( rslt != null ) {
321             if ( key.size() != rslt.size() )
322                 return null;
323         }
324         return rslt;
325     }
326     
327     
328     /* rehash performance notes:
329      *Uncommenting below gives an easy way of measuring
330      *rehash performance.
331      *On a 480ms job the rehash appeared to take over 200ms.
332      *(Since with the code below uncommented the same 
333      *problem took about 1300ms).
334      *
335      */
336     private int rehash(int lvl) {
337         /*
338         rehash0(lvl);
339         rehash0(lvl);
340         rehash0(lvl);
341         rehash0(lvl);
342          **/
343         return rehash0(lvl);
344     }
345         
346     private int rehash0( int level ) {
347         in(REHASHING);
348         this.table = CollectionFactory.createHashedMap();
349         // Set a global to define the hash of an AnonResource
350         // level = 0 ==> AnonResource.myHashCode() = 0
351         // level = n+1 ==> AnonResource.myHashCode() = hash[n]
352         myHashLevel = level;
353         
354         // Now compute all hashes and stick things in the
355         // right buckets.
356         Iterator anons = unboundAnonResources.iterator();
357         while ( anons.hasNext() ) {
358             AnonResource a = (AnonResource)anons.next();
359             Integer   hash = new Integer  ( a.myHashCode() );
360             Bucket bkt = (Bucket)table.get(hash);
361             if ( bkt == null ) {
362                 bkt = new Bucket();
363                 table.put(hash,bkt);
364             }
365             bkt.add(a);
366         }
367         
368         // Produce a checksum for the table.
369         int rslt = 0;
370         Iterator tit = table.entrySet().iterator();
371         
372         while ( tit.hasNext() ) {
373             Map.Entry pair = (Map.Entry)tit.next();
374             int hash = ((Integer  )pair.getKey()).intValue();
375             Bucket bkt = (Bucket)pair.getValue();
376             int sz = bkt.size();
377             rslt += sz*0x10001 ^ hash;
378         }
379         
380         in(HASH_OK);
381         return rslt;
382         
383     }
384     
385     /* subjects identified by bits 0 and 1,
386      * predicate           by bits 2 and 3,
387      * object              by      4 and 5
388      * If neither bit set then role is bound.
389      * If lower bit is set then role is unbound to
390      * singleton variable in triple.
391      * If higher bit is set then role is unbound
392      * with anonymous variable that is also
393      * unbound to a different role.
394      * It is an error if both bits are set.
395      *
396      *
397      * These funny things are read like this: e.g.
398      *
399      * SXPYOX - the subject is a variable X,
400      *          the predicate is another var Y
401      *          the object is the same var X
402      *
403      */
404     static final private int NOVARS = 0;
405     static final private int SX = 1;
406     static final private int PX = 4;
407     static final private int OX = 16;
408     // SD, PD and OD are illegal values
409     // by themselves, should only
410     // be found in combination with
411     // each other.
412     // D for duplicate.
413     static final private int SD = 2;
414     static final private int PD = 8;
415     static final private int OD = 32;
416     static final private int SXPY = SX|PX;
417     static final private int SXOY = SX|OX;
418     static final private int PXOY = PX|OX;
419     static final private int SXPYOZ = SX|PX|OX;
420     static final private int SXPX = SD|PD;
421     static final private int SXOX = SD|OD;
422     static final private int PXOX = PD|OD;
423     static final private int SXPXOY = SD|PD|OX;
424     static final private int SXPYOX = SD|OD|PX;
425     static final private int SXPYOY = SX|PD|OD;
426     static final private int SXPXOX = SD|PD|OD;
427     static final private int S = SX|SD;
428     static final private int P = PX|PD;
429     static final private int O = OX|OD;
430     
431     static private boolean legalPattern(int mask) {
432         switch (mask) {
433             case NOVARS:
434             case SX:
435             case OX:
436             case PX:
437             case SXPY:
438             case SXOY:
439             case PXOY:
440             case SXPYOZ:
441             case SXPX:
442             case SXOX:
443             case PXOX:
444             case SXPXOY:
445             case SXPYOX:
446             case SXPYOY:
447             case SXPXOX:
448                 return true;
449                 default:
450                     return false;
451         }
452     }
453     // if i = 0 return the X component of pattern
454     // if i = 1 return the Y component of pattern
455     // if i = 2 return the Z component of pattern
456     static private int varPosInPattern(int i,int pattern) {
457         switch (pattern) {
458             case NOVARS:
459                 break;
460             case SX:
461                 if (i==0) return SX;
462                 break;
463             case OX:
464                 if (i==0) return OX;
465                 break;
466             case PX:
467                 if (i==0) return PX;
468                 break;
469             case SXPY:
470                 switch (i) {
471                     case 0:
472                         return SX;
473                     case 1:
474                         return PX;
475                 }
476                 break;
477             case SXOY:
478                 switch (i) {
479                     case 0:
480                         return SX;
481                     case 1:
482                         return OX;
483                 }
484                 break;
485             case PXOY:
486                 switch (i) {
487                     case 0:
488                         return PX;
489                     case 1:
490                         return OX;
491                 }
492                 break;
493             case SXPYOZ:
494                 switch (i) {
495                     case 0:
496                         return SX;
497                     case 1:
498                         return PX;
499                     case 2:
500                         return OX;
501                 }
502                 break;
503             case SXPX:
504                 if (i==0) return SXPX;
505                 break;
506             case SXOX:
507                 if (i==0) return SXOX;
508                 break;
509             case PXOX:
510                 if (i==0) return PXOX;
511                 break;
512             case SXPXOY:
513                 switch (i) {
514                     case 0:
515                         return SXPX;
516                     case 1:
517                         return OX;
518                 }
519                 break;
520             case SXPYOX:
521                 switch (i) {
522                     case 0:
523                         return SXOX;
524                     case 1:
525                         return PX;
526                 }
527                 break;
528             case SXPYOY:
529                 switch (i) {
530                     case 0:
531                         return SX;
532                     case 1:
533                         return PXOX;
534                 }
535                 break;
536             case SXPXOX:
537                 if (i==0) return SXPXOX;
538                 break;
539         }
540         System.out.println("Bad: " + i + " " + pattern);
541         impossible();
542         return 0;
543     }
544     static private interface SomeResource {
545         int myHashCodeFromStatement();
546         boolean mightBeEqual(SomeResource r);
547     }
548     static private class FixedResource implements SomeResource {
549         int hash;
550         Node node;
551         public String   toString() {
552             return "f" + hash;
553         }
554         public int myHashCodeFromStatement() {
555             return hash;
556         }
557         FixedResource(Node n) {
558             hash = n.hashCode();
559             node = n;
560         }
561         public boolean mightBeEqual(SomeResource r) {
562             if (r!=null && (r instanceof FixedResource)) {
563                 FixedResource f = (FixedResource)r;
564                 return hash == f.hash && node.equals(f.node);
565             } else {
566                 return false;
567             }
568         }
569     }
570     
571     // Record the occurence of variable r in bag.
572     static void count(Map bag, SomeResource r,int pos) {
573         if ( r instanceof AnonResource ) {
574             int v[] = (int[])bag.get(r);
575             if (v==null) {
576                 v=new int[]{-1,-1,-1};
577                 bag.put(r,v);
578             }
579             for (int i=0;i<3;i++)
580                 if ( v[i] == -1 ) {
581                     v[i] = pos;
582                     return;
583                 }
584         }
585     }
586     private class AnonStatement {
587         int varCount;
588         AnonResource vars[];
589         SomeResource subj;
590         SomeResource pred;
591         SomeResource obj;
592         int pattern;
593         AnonStatement(Triple s) {
594             Map bag = CollectionFactory.createHashedMap();
595             pattern = NOVARS;
596             subj = convert(s.getSubject());
597             pred = convert(s.getPredicate());
598             obj = convert(s.getObject());
599             count(bag,subj,0);
600             count(bag,pred,2);
601             count(bag,obj,4);
602             varCount = bag.size();
603             vars = new AnonResource[varCount];
604             add(subj);
605             add(pred);
606             add(obj);
607             Iterator it = bag.values().iterator();
608             while ( it.hasNext() ) {
609                 int v[] = (int[])it.next();
610                 int last = 2;
611                 int p;
612                 while ( v[last]== -1)
613                     last--;
614                 if ( last == 0 )
615                     p = SX;
616                 else
617                     p = SD;
618                 for (int i=0;i<=last;i++)
619                     pattern |= p<<v[i];
620             }
621             if (!legalPattern(pattern)) {
622                 System.out.println("s: " + subj + " p: " + pred + " o: " + obj + " pattern: " + pattern);
623                 impossible();
624             }
625         }
626         private void add(SomeResource r) {
627             if ( r instanceof AnonResource ) {
628                 for (int i=0;i<vars.length; i++)
629                     if (vars[i]==null || vars[i]==r ) {
630                         vars[i] = (AnonResource)r;
631                         return;
632                     }
633                 impossible();
634             }
635         }
636         
637         // returns the location of v in this statement.
638         // e.g. PXOX to say that v is both the predicate and object.
639         int varPos(AnonResource v) {
640             if ( v == null)
641               return 0;
642             for (int i=0;i<vars.length;i++)
643                 if ( vars[i] == v )
644                     return varPosInPattern(i,pattern);
645             impossible();
646             return 0;
647         }
648         int myHashCode(AnonResource v) {
649             int vX = varPos(v);
650             int hash = vX;
651             // The multipliers are chosen to be 2 bit numbers.
652             // These muddle up the bits; should be quick in an optimised
653             // compilation or JIT (a shift and an add); and ensure
654             // that positional information (SPO) is encoded in the hash.
655             if ( (vX & S) == 0) {
656                 hash ^= subj.myHashCodeFromStatement() * 0x101;
657             }
658             if ( (vX & P )== 0 ) {
659                 hash ^= pred.myHashCodeFromStatement() * 0x3f;
660             }
661             if ( (vX & O )== 0 ) {
662                 hash ^= obj.myHashCodeFromStatement() * 0x41;
663             }
664             return hash;
665         }
666         boolean contextualEquals(AnonResource v,AnonStatement sB,AnonResource vB) {
667             int vX = varPos(v);
668             if ( vX != sB.varPos(vB) )
669                 return false;
670             return
671             ((vX & S) != 0 || subj.mightBeEqual(sB.subj))
672             && ((vX & P) != 0 || pred.mightBeEqual(sB.pred))
673             && ((vX & O) != 0 || obj.mightBeEqual(sB.obj));
674             
675         }
676     }
677     
678     // Bucket's live longer than the table that they sit in.
679     // If a bucket is matched before the main bind() loop then
680     // we are iterating over it's members while the rest of the
681     // algorithm is proceeding.
682     private class Bucket {
683         Set anonRes = CollectionFactory.createHashedSet();
684         int hash[] = new int[MAX_HASH_DEPTH];
685         boolean bind(Bucket singleton) {
686             return bind(aMember(),singleton,singleton.aMember());
687         }
688         boolean bind(AnonResource mine,Bucket other,AnonResource binding) {
689             if ( mine.checkBinding(binding) ) {
690                  mine.bind(binding);
691                 return true;
692             } else {
693                 return false;
694             }
695         }
696         
697         void add(AnonResource r) {
698             anonRes.add(r);
699         }
700         AnonResource aMember() {
701             return (AnonResource)anonRes.iterator().next();
702         }
703         Iterator members() {
704             return anonRes.iterator();
705         }
706         int size() {
707             return anonRes.size();
708         }
709     }
710     private class AnonResource  implements SomeResource {
711         AnonResource bound;
712         Node r;
713         Set occursIn = CollectionFactory.createHashedSet(); // The AnonStatements containing me.
714         int hash[] = new int[MAX_HASH_DEPTH];
715         int boundHash;
716         Set friends = CollectionFactory.createHashedSet(); // Other vars in AnonStatements containing me.
717         int myHash;
718         
719         public String   toString() {
720             String   rslt = r.toString();
721             if ( bound!=null )
722                 rslt += "[" + bound.r.toString() + "]";
723             return rslt;
724         }
725         
726         AnonResource(Node r) {
727             unboundAnonResources.add(this);
728             this.r = r;
729         }
730         public int myHashCodeFromStatement() {
731             if ( bound != null )
732                 return boundHash;
733             if (myHashLevel==0) {
734                 return 0xcafebabe;
735             }
736             check(REHASHING|HASH_OK);
737             return hash[myHashLevel-1];
738         }
739         // MUST NOT BE CALLED FROM WITHIN THE LOOP
740         // OF OBLIG BINDINGS, use myHash
741         // ONLY INTENDED TO BE CALLED FROM WITHIN rehash
742         int myHashCode() {
743             check(REHASHING);
744             if ( bound!=null )
745                 impossible();
746             myHash = 0;
747             Iterator ss = occursIn.iterator();
748             while (ss.hasNext()) {
749                 AnonStatement ass = (AnonStatement)ss.next();
750                 myHash += ass.myHashCode(this);
751             }
752             hash[myHashLevel] = myHash;
753             return myHash;
754         }
755         void bind(AnonResource pair)  {
756             bound = pair;
757             
758             if (!unboundAnonResources.remove(this))
759                 impossible();
760             boundAnonResources.add(this);
761             
762             if ( pair.bound == null ) {
763                 trace( true, r.getBlankNodeId()+ "=" + pair.r.getBlankNodeId() + ", " );
764                 pair.bind(this);
765                 // choice any arbitary number here
766                 // helps spread the bits.
767                 bound.boundHash= boundHash =random.nextInt();
768                 //  if ( myHash != bound.myHash )
769                 //      impossible();
770                 // Sometimes they are different, after we have
771                 // guessed badly, changed bound.myHash and then
772                 // backtracked.
773             }
774             
775             if ( bound.bound != this )
776                 impossible();
777         }
778         void unbind()  {
779             AnonResource pair = bound;
780             bound = null;
781             
782             if (!boundAnonResources.remove(this))
783                 impossible();
784             
785             unboundAnonResources.add(this);
786             
787             if ( pair.bound != null ) {
788                 trace( false, r.getBlankNodeId() + "!=" + pair.r.getBlankNodeId() + ", " );
789                 if ( pair.bound != this )
790                     impossible();
791                 
792                 pair.unbind();
793             }
794             
795             in(HASH_BAD);
796         }
797         boolean checkBinding( AnonResource pair ) {
798             
799             if ( occursIn.size() != pair.occursIn.size() )
800                 return false;
801             
802             Set ourStatements = wrapStatements();
803             Set otherStatements = pair.wrapStatements();
804             
805             return ourStatements.removeAll(otherStatements)
806             && ourStatements.isEmpty();
807             
808         }
809         private Set wrapStatements() {
810             if ( state == HASH_BAD ) {
811                 // We are already in(HASH_BAD).
812                 // We need to use AnonResource.myHashCodeFromStatement().
813                 // That is OK as long as myHashLevel is 0
814                 myHashLevel = 0;
815             }
816             Set statements = CollectionFactory.createHashedSet();
817             // Add all our statements to the set.
818             Iterator it = occursIn.iterator();
819             while ( it.hasNext() )
820                 statements.add(wrapStatement((AnonStatement)it.next()));
821             return statements;
822         }
823         public boolean mightBeEqual(SomeResource r) {
824             if (r!=null && (r instanceof AnonResource)) {
825                 AnonResource a = (AnonResource)r;
826                 return a==this
827                 || bound == a
828                 || (bound == null && a.bound == null);
829             } else {
830                 return false;
831             }
832         }
833         StatementWrapper wrapStatement(AnonStatement s) {
834             return new StatementWrapper(s);
835         }
836         // inner inner class -- ouch!
837         private class StatementWrapper {
838             int hash;
839             AnonStatement statement;
840             public boolean equals(Object   o) {
841                 if (o == null || (!(o instanceof StatementWrapper)))
842                     return false;
843                 StatementWrapper w = (StatementWrapper)o;
844                 return hash == w.hash &&
845                 statement.contextualEquals(AnonResource.this,w.statement,w.asAnonR());
846             }
847             public int hashCode() {
848                 return hash;
849             }
850             StatementWrapper( AnonStatement s ) {
851                 hash = s.myHashCode(AnonResource.this);
852                 statement = s;
853             }
854             AnonResource asAnonR() {
855                 return AnonResource.this;
856             }
857         }
858     }
859     private Map anonLookup = CollectionFactory.createHashedMap();
860     private SomeResource convert(Node n) {
861         if ( n.isBlank() ) {
862             SomeResource anon = (SomeResource)anonLookup.get(n);
863             if ( anon == null ) {
864                 anon = new AnonResource( n );
865                 anonLookup.put(n,anon);
866             }
867             return anon;
868         } else {
869             return new FixedResource(n);
870         }
871     }
872     
873     private void check(int s) {
874         if (( state & s) == 0 ) 
875             impossible();
876     }
877     
878     private void in(int s) {
879         state = s;
880         other.state = s;
881     }
882     
883     static private void impossible() {
884         throw new JenaException( "Cannot happen!" );
885     }
886     
887     static private int col = 0;
888     static private boolean lastDir = false;
889     
890     static private void trace(boolean dir, String   s) {
891         if (TRACE) {
892             if ( dir != lastDir ) {
893                 traceNL();
894                 lastDir = dir;
895             }
896             int nCol = col + s.length();
897             if ( col != 0 && nCol > 70 ) {
898                 traceNL();
899                 nCol = s.length();
900             }
901             System.out.print(s);
902             System.out.flush();
903             col = nCol;
904         }
905     }
906     static private void traceNL() {
907         if ( TRACE ) {
908             System.out.println();
909             col = 0;
910         }
911     }
912     
913 }
914 /*
915  *  (c) Copyright 2002, 2002, 2003, 2004, 2005 Hewlett-Packard Development Company, LP
916  *  
917  *  All rights reserved.
918  * 
919  *
920  * Redistribution and use in source and binary forms, with or without
921  * modification, are permitted provided that the following conditions
922  * are met:
923  * 1. Redistributions of source code must retain the above copyright
924  *    notice, this list of conditions and the following disclaimer.
925  * 2. Redistributions in binary form must reproduce the above copyright
926  *    notice, this list of conditions and the following disclaimer in the
927  *    documentation and/or other materials provided with the distribution.
928  * 3. The name of the author may not be used to endorse or promote products
929  *    derived from this software without specific prior written permission.
930 
931  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
932  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
933  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
934  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
935  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
936  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
937  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
938  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
939  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
940  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
941  *
942  * $Id: GraphMatcher.java,v 1.9 2005/02/21 11:52:10 andy_seaborne Exp $
943  */
944
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags