graphmatcher.java

Jena推理机

                    if (vars[i]==null || vars[i]==r ) {
                        vars[i] = (AnonResource)r;
                        return;
                    }
                impossible();
            }
        }
        
        // returns the location of v in this statement.
        // e.g. PXOX to say that v is both the predicate and object.
        int varPos(AnonResource v) {
        	if ( v == null)
        	  return 0;
            for (int i=0;i<vars.length;i++)
                if ( vars[i] == v )
                    return varPosInPattern(i,pattern);
            impossible();
            return 0;
        }
        int myHashCode(AnonResource v) {
            int vX = varPos(v);
            int hash = vX;
            // The multipliers are chosen to be 2 bit numbers.
            // These muddle up the bits; should be quick in an optimised
            // compilation or JIT (a shift and an add); and ensure
            // that positional information (SPO) is encoded in the hash.
            if ( (vX & S) == 0) {
                hash ^= subj.myHashCodeFromStatement() * 0x101;
            }
            if ( (vX & P )== 0 ) {
                hash ^= pred.myHashCodeFromStatement() * 0x3f;
            }
            if ( (vX & O )== 0 ) {
                hash ^= obj.myHashCodeFromStatement() * 0x41;
            }
            return hash;
        }
        boolean contextualEquals(AnonResource v,AnonStatement sB,AnonResource vB) {
            int vX = varPos(v);
            if ( vX != sB.varPos(vB) )
                return false;
            return
            ((vX & S) != 0 || subj.mightBeEqual(sB.subj))
            && ((vX & P) != 0 || pred.mightBeEqual(sB.pred))
            && ((vX & O) != 0 || obj.mightBeEqual(sB.obj));
            
        }
    }
    
    // Bucket's live longer than the table that they sit in.
    // If a bucket is matched before the main bind() loop then
    // we are iterating over it's members while the rest of the
    // algorithm is proceeding.
    private class Bucket {
        Set anonRes = CollectionFactory.createHashedSet();
        int hash[] = new int[MAX_HASH_DEPTH];
        boolean bind(Bucket singleton) {
            return bind(aMember(),singleton,singleton.aMember());
        }
        boolean bind(AnonResource mine,Bucket other,AnonResource binding) {
            if ( mine.checkBinding(binding) ) {
                 mine.bind(binding);
                return true;
            } else {
                return false;
            }
        }
        
        void add(AnonResource r) {
            anonRes.add(r);
        }
        AnonResource aMember() {
            return (AnonResource)anonRes.iterator().next();
        }
        Iterator members() {
            return anonRes.iterator();
        }
        int size() {
            return anonRes.size();
        }
    }
    private class AnonResource  implements SomeResource {
        AnonResource bound;
        Node r;
        Set occursIn = CollectionFactory.createHashedSet(); // The AnonStatements containing me.
        int hash[] = new int[MAX_HASH_DEPTH];
        int boundHash;
        Set friends = CollectionFactory.createHashedSet(); // Other vars in AnonStatements containing me.
        int myHash;
        
        public String toString() {
            String rslt = r.toString();
            if ( bound!=null )
                rslt += "[" + bound.r.toString() + "]";
            return rslt;
        }
        
        AnonResource(Node r) {
            unboundAnonResources.add(this);
            this.r = r;
        }
        public int myHashCodeFromStatement() {
            if ( bound != null )
                return boundHash;
            if (myHashLevel==0) {
                return 0xcafebabe;
            }
            check(REHASHING|HASH_OK);
            return hash[myHashLevel-1];
        }
        // MUST NOT BE CALLED FROM WITHIN THE LOOP
        // OF OBLIG BINDINGS, use myHash
        // ONLY INTENDED TO BE CALLED FROM WITHIN rehash
        int myHashCode() {
            check(REHASHING);
            if ( bound!=null )
                impossible();
            myHash = 0;
            Iterator ss = occursIn.iterator();
            while (ss.hasNext()) {
                AnonStatement ass = (AnonStatement)ss.next();
                myHash += ass.myHashCode(this);
            }
            hash[myHashLevel] = myHash;
            return myHash;
        }
        void bind(AnonResource pair)  {
            bound = pair;
            
            if (!unboundAnonResources.remove(this))
                impossible();
            boundAnonResources.add(this);
            
            if ( pair.bound == null ) {
                trace( true, r.getBlankNodeId()+ "=" + pair.r.getBlankNodeId() + ", " );
                pair.bind(this);
                // choice any arbitary number here
                // helps spread the bits.
                bound.boundHash= boundHash =random.nextInt();
                //  if ( myHash != bound.myHash )
                //      impossible();
                // Sometimes they are different, after we have
                // guessed badly, changed bound.myHash and then
                // backtracked.
            }
            
            if ( bound.bound != this )
                impossible();
        }
        void unbind()  {
            AnonResource pair = bound;
            bound = null;
            
            if (!boundAnonResources.remove(this))
                impossible();
            
            unboundAnonResources.add(this);
            
            if ( pair.bound != null ) {
                trace( false, r.getBlankNodeId() + "!=" + pair.r.getBlankNodeId() + ", " );
                if ( pair.bound != this )
                    impossible();
                
                pair.unbind();
            }
            
            in(HASH_BAD);
        }
        boolean checkBinding( AnonResource pair ) {
            
            if ( occursIn.size() != pair.occursIn.size() )
                return false;
            
            Set ourStatements = wrapStatements();
            Set otherStatements = pair.wrapStatements();
            
            return ourStatements.removeAll(otherStatements)
            && ourStatements.isEmpty();
            
        }
        private Set wrapStatements() {
            if ( state == HASH_BAD ) {
                // We are already in(HASH_BAD).
                // We need to use AnonResource.myHashCodeFromStatement().
                // That is OK as long as myHashLevel is 0
                myHashLevel = 0;
            }
            Set statements = CollectionFactory.createHashedSet();
            // Add all our statements to the set.
            Iterator it = occursIn.iterator();
            while ( it.hasNext() )
                statements.add(wrapStatement((AnonStatement)it.next()));
            return statements;
        }
        public boolean mightBeEqual(SomeResource r) {
            if (r!=null && (r instanceof AnonResource)) {
                AnonResource a = (AnonResource)r;
                return a==this
                || bound == a
                || (bound == null && a.bound == null);
            } else {
                return false;
            }
        }
        StatementWrapper wrapStatement(AnonStatement s) {
            return new StatementWrapper(s);
        }
        // inner inner class -- ouch!
        private class StatementWrapper {
            int hash;
            AnonStatement statement;
            public boolean equals(Object o) {
                if (o == null || (!(o instanceof StatementWrapper)))
                    return false;
                StatementWrapper w = (StatementWrapper)o;
                return hash == w.hash &&
                statement.contextualEquals(AnonResource.this,w.statement,w.asAnonR());
            }
            public int hashCode() {
                return hash;
            }
            StatementWrapper( AnonStatement s ) {
                hash = s.myHashCode(AnonResource.this);
                statement = s;
            }
            AnonResource asAnonR() {
                return AnonResource.this;
            }
        }
    }
    private Map anonLookup = CollectionFactory.createHashedMap();
    private SomeResource convert(Node n) {
        if ( n.isBlank() ) {
            SomeResource anon = (SomeResource)anonLookup.get(n);
            if ( anon == null ) {
                anon = new AnonResource( n );
                anonLookup.put(n,anon);
            }
            return anon;
        } else {
            return new FixedResource(n);
        }
    }
    
    private void check(int s) {
        if (( state & s) == 0 ) 
            impossible();
    }
    
    private void in(int s) {
        state = s;
        other.state = s;
    }
    
    static private void impossible() {
        throw new JenaException( "Cannot happen!" );
    }
    
    static private int col = 0;
    static private boolean lastDir = false;
    
    static private void trace(boolean dir, String s) {
        if (TRACE) {
            if ( dir != lastDir ) {
                traceNL();
                lastDir = dir;
            }
            int nCol = col + s.length();
            if ( col != 0 && nCol > 70 ) {
                traceNL();
                nCol = s.length();
            }
            System.out.print(s);
            System.out.flush();
            col = nCol;
        }
    }
    static private void traceNL() {
        if ( TRACE ) {
            System.out.println();
            col = 0;
        }
    }
    
}
/*
 *  (c) Copyright 2002, 2002, 2003, 2004, 2005, 2006, 2007 Hewlett-Packard Development Company, LP
 *  
 *  All rights reserved.
 * 
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.

 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * $Id: GraphMatcher.java,v 1.15 2007/01/02 11:48:28 andy_seaborne Exp $
 */