package de.uni_hamburg.fs;

import collections.CollectionEnumeration;
import collections.HashedMap;
import collections.UpdatableMap;


/**
 * Implements subsumption checking between feature structures.
 * Subsumption is a relationship where one feature structure is more general
 * than another, containing all the information of the more specific structure.
 * This class provides functionality to check if one feature structure subsumes another.
 */
public class Subsumption {
    private UpdatableMap _h = new HashedMap();

    private Subsumption() {}

    /**
     * Checks if one feature structure subsumes another.
     * A feature structure subsumes another if it is more general and contains
     * all the information present in the more specific structure.
     *
     * @param thiz the potentially more general feature structure
     * @param that the potentially more specific feature structure
     * @return true if thiz subsumes that, false otherwise
     */
    public static boolean subsumes(FeatureStructure thiz, FeatureStructure that) {
        return new Subsumption().subsumes(thiz.getRoot(), that.getRoot());
    }

    private boolean subsumes(Node thiz, Node that) {
        if (_h.includesKey(thiz)) {
            return _h.at(thiz).equals(that);
        }
        if (!thiz.getType().subsumes(that.getType())) {
            return false;
        }
        if (thiz instanceof JavaObject) {
            // if this java object subsumes that, that must in fact be
            // an equal java object: no need to proceed.
            return true;
        }

        _h.putAt(thiz, that);
        CollectionEnumeration features = thiz.featureNames();
        while (features.hasMoreElements()) {
            Name featureName = (Name) features.nextElement();
            Node thispost = thiz.delta(featureName);
            if (that.hasFeature(featureName)) {
                Node thatpost = that.delta(featureName);
                if (!subsumes(thispost, thatpost)) {
                    return false;
                }
            } else {
                return false;
            }
        }
        return true;
    }
}