icldualtraversal.java

SRI international 发布的OAA框架软件

// $CALOLSI$
/*
 * #=========================================================================
 * # Copyright 2004 SRI International.  All rights reserved.
 * #
 * # The material contained in this file is confidential and proprietary to SRI
 * # International and may not be reproduced, published, or disclosed to others
 * # without authorization from SRI International.
 * #
 * # DISCLAIMER OF WARRANTIES
 * #
 * # SRI International MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE
 * # SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT
 * # LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
 * # PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SRI International SHALL NOT BE
 * # LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING
 * # OR DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES
 * #=========================================================================
 * Author : evans
 * Date: May 12, 2004
 * Time: 3:26:31 PM
 */
package com.sri.oaa2.mapper;


import java.util.LinkedList;
import java.util.List;

import com.sri.oaa2.icl.IclStruct;
import com.sri.oaa2.icl.IclTerm;

import org.apache.log4j.Logger;

/**
 * Traverses an ICL template, comparing it to a specified ICL tree and allowing substitution of variables.
 */
public class IclDualTraversal
{
    protected Logger logger = Logger.getLogger(super.getClass());
    private IclTerm templateRoot;
    private IclTerm iclRoot;

    private IclTerm iclParent;
    private int iclIndex = -1;

    private IclTerm templateParent;
    private int templateIndex = -1;

    private boolean matchFailed = false;
    private String reasonFailed;

    protected boolean visit(IclTerm template, IclTerm icl)
            throws MappingException
    {
        return true;
    }

    public final void traverse(IclTerm template, IclTerm icl)
            throws MappingException
    {
        try
        {
            templateRoot = template;
            iclRoot = icl;

            templateParent = null;
            iclParent = null;
            templateIndex = -1;
            iclIndex = -1;
            matchFailed = false;
            if(!compare(template, icl))
            {
                matchFailed("Template " + template + " doesn't match " + icl);
            }
            else if(visit(template, icl) && !template.isVar() && !isMatchFailed()) traverseChildren(template, icl);
        }
        finally
        {
            templateRoot = null;
            iclRoot = null;
        }
    }

    public boolean isMatchFailed()
    {
        return matchFailed;
    }

    public String getReasonFailed()
    {
        return reasonFailed;
    }

    protected void matchFailed(String reasonFailed)
    {
        matchFailed = true;
        this.reasonFailed = reasonFailed;
    }

    /**
     * Replaces the currently visited node.
     *
     * @param icl
     */
    protected final void replace(IclTerm icl)
            throws MappingException
    {
        if(iclParent != null)
            iclParent.replaceElement(iclIndex, icl);
        else
            throw new MappingException("Cannot replace root element of " + iclRoot.toString() + " with " + icl);
    }

    /**
     * Remove the currently visited node.
     */
    protected final void remove()
            throws MappingException
    {
        if(iclParent != null)
        {
            iclParent.removeElement(iclIndex);
            iclIndex--;
        }
        throw new MappingException("Cannot remove root element of " + iclRoot.toString());
    }

    ///////////////////////////////////////////////////////

    private void traverseChildren(IclTerm template, IclTerm icl)
            throws MappingException
    {
        List templateTraversalQueue = new LinkedList();
        templateTraversalQueue.add(template);
        List iclTraversalQueue = new LinkedList();
        iclTraversalQueue.add(icl);

        while(templateTraversalQueue.size() > 0 && !isMatchFailed())
        {
            templateParent = (IclTerm)templateTraversalQueue.remove(0);
            iclParent = (IclTerm)iclTraversalQueue.remove(0);
            if(templateParent.getNumChildren() != iclParent.getNumChildren())
            {
                matchFailed("Template children" + templateParent + " don't match children of " + iclParent);
            }

            // walk through both sets of children at the same time:
            for(templateIndex = 0, iclIndex = 0; templateIndex < templateParent.getNumChildren() &&
                    iclIndex < iclParent.getNumChildren() && !matchFailed; templateIndex++, iclIndex++)
            {
                IclTerm templateChild = templateParent.getTerm(templateIndex);
                IclTerm iclChild = iclParent.getTerm(iclIndex);
                if(!compare(templateChild, iclChild))
                {
                    matchFailed("Template " + templateChild + " doesn't match " + iclChild);
                }
                else if(visit(templateChild, iclChild) && !templateChild.isVar())
                {
                    templateTraversalQueue.add(templateChild);
                    iclTraversalQueue.add(iclChild);
                }
            }
        }
    }

    /**
     * Compares a template term to an ICL term for purposes of comparison during traversal.
     * If the template is an IclVar, this returns true.
     */
    private boolean compare(IclTerm template, IclTerm icl)
    {
        if(template.isVar()) return true;
        if((template.isStruct() || template.isList() || template.isAtomic()) && template.getType() != icl.getType())
            return false;
        if(!template.isVar() && !template.isList() && template.getNumChildren() != icl.getNumChildren()) return false;
        if(template.isStruct() && !((IclStruct)template).getFunctor().equals(((IclStruct)icl).getFunctor()))
            return false;
        if(template.isAtomic() && !template.toString().equals(icl.toString())) return false;
        return true;
    }
}