package de.uni_hamburg.fs;

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


/**
 * A utility class for determining equality between feature structures.
 * This class implements an algorithm to check if two feature structures
 * are equal by comparing their nodes and maintaining references.
 */
public class Equality {
    /**
     * Maps nodes from the left structure to nodes from the right structure.
     */
    private UpdatableMap _lr = new HashedMap();

    /**
     * Maps nodes from the right structure to nodes from the left structure.
     */
    private UpdatableMap _rl = new HashedMap();

    /**
     * Private constructor to prevent direct instantiation.
     * Instances are created internally by the static equals method.
     */
    private Equality() {}

    /**
     * Compares two feature structures for equality.
     * Two feature structures are considered equal if their root nodes
     * and all reachable substructures are equal.
     *
     * @param thiz the first feature structure to compare
     * @param that the second feature structure to compare
     * @return true if the feature structures are equal, false otherwise
     */
    public static boolean equals(FeatureStructure thiz, FeatureStructure that) {
        return new Equality().equals(thiz.getRoot(), that.getRoot());
    }

    private boolean equals(Node thiz, Node that) {
        if (thiz.equals(that)) {
            return true;
        }

        // same type?
        if (!thiz.getType().equals(that.getType())) {
            return false;
        }

        // same co-references?
        if (_lr.includesKey(thiz)) {
            return _lr.at(thiz).equals(that);
        }
        if (_rl.includesKey(that)) {
            return _rl.at(that).equals(thiz);
        }
        _lr.putAt(thiz, that);
        _rl.putAt(that, thiz);
        CollectionEnumeration features = thiz.featureNames();

        // same number of features?
        if (that.featureNames().numberOfRemainingElements() != features
            .numberOfRemainingElements()) {
            return false;
        }
        while (features.hasMoreElements()) {
            Name featureName = (Name) features.nextElement();
            Node thispost = thiz.delta(featureName);

            // same feature?
            if (that.hasFeature(featureName)) {
                Node thatpost = that.delta(featureName);

                // same values for feature?
                if (!equals(thispost, thatpost)) {
                    return false;
                }
            } else {
                return false;
            }
        }
        return true;
    }
}