package de.uni_hamburg.fs;

import java.util.Stack;

import collections.CollectionEnumeration;
import collections.HashedMap;
import collections.HashedSet;
import collections.UpdatableMap;
import collections.UpdatableSet;


/**
 * Implements an equivalence relation for nodes in feature structures.
 * This class provides functionality to track and manage relationships between
 * nodes, allowing for unification and tracking of equivalent nodes.
 * It serves as the core mechanism for implementing unification operations
 * on feature structures.
 */
public class EquivRelation {
    // public static org.apache.log4j.Logger logger = 
    //         org.apache.log4j.Logger.getLogger(EquivRelation.class) ;

    /**
     * tie maps Nodes to Unificator Nodes.
     */
    private UpdatableMap _tie = new HashedMap();

    /**
     * eit maps Unificator Nodes to sets of Nodes.
     */
    private UpdatableMap _eit = new HashedMap();

    /**
     * todo is a Stack of ToDoItems, pairs of nodes
     *  which still have to be unified or nodes which
     *  have to be retyped.
     */
    private Stack<ToDoItem> _todo = new Stack<ToDoItem>();

    /**
     * Constructs a new Equivalence Relation.
     * Initializes internal data structures for tracking node relationships.
     */
    public EquivRelation() {}

    /**
     * Returns the unification of two feature structures.
     *
     * @param fs1 the first feature structure to unify
     * @param fs2 the second feature structure to unify
     * @return the root node of the unified feature structure
     * @throws UnificationFailure if the feature structures cannot be unified
     */
    public static Node unify(FeatureStructure fs1, FeatureStructure fs2) throws UnificationFailure {
        // logger.debug("Unifying "+fs1.seqNo+" and "+fs2.seqNo+".");
        EquivRelation er = new EquivRelation();
        Node root = fs1.getRoot();
        er.unify(root, fs2.getRoot());
        er.extensionalize();
        return er.rebuild(root);
    }

    /**
     * Returns the result of unifying fs2 into fs1 at the given path.
     *
     * @param fs1  the feature structure to unify into
     * @param path the path in fs1 where fs2 should be unified
     * @param fs2  the feature structure to unify at the specified path
     * @return the root node of the unified feature structure
     * @throws UnificationFailure if the feature structures cannot be unified at the specified path
     */
    public static Node unify(FeatureStructure fs1, Path path, FeatureStructure fs2)
        throws UnificationFailure
    {
        // logger.debug("Unifying "+fs1.seqNo+" at "+path+" and "+fs2.seqNo+".");
        Node fs1Root = addPath(fs1.getRoot(), path);
        EquivRelation er = new EquivRelation();
        er.unify(fs1Root.delta(path), fs2.getRoot());
        er.extensionalize();
        return er.rebuild(fs1Root);
    }

    /**
     * Returns the result of identifying the sub-feature structures of fs at paths path1 and path2.
     *
     * @param fs    the feature structure containing the paths
     * @param path1 the first path in the feature structure
     * @param path2 the second path in the feature structure
     * @return the root node of the unified feature structure
     * @throws UnificationFailure if the nodes at the specified paths cannot be unified
     */
    public static Node unify(FeatureStructure fs, Path path1, Path path2)
        throws UnificationFailure
    {
        Node fsRoot = addPath(addPath(fs.getRoot(), path1), path2);
        EquivRelation er = new EquivRelation();
        er.unify(fsRoot.delta(path1), fsRoot.delta(path2));
        er.extensionalize();
        return er.rebuild(fsRoot);
    }

    /**
     * Updates the EquivRelation and constructs Unificator Nodes
     * so that fs1 and fs2 are unified.
     * Other nodes may become unified by recursion.
     *
     * @param fs1 the first node to unify
     * @param fs2 the second node to unify
     * @throws UnificationFailure if the nodes cannot be unified
     */
    public void unify(Node fs1, Node fs2) throws UnificationFailure {
        addUnification(fs1, fs2);
        while (!_todo.empty()) {
            ToDoItem tdi = nextToDoItem();


            //try {
            tdi.doIt(this);


            //  } catch (UnificationFailure uff) {
            //    logger.error("UnificationFailure during "+tdi);
            //    throw uff;
            //  }
        }

        //logger.debug("Unification done.");
    }

    private static Node addPath(Node root, Path path) throws UnificationFailure {
        // We have to unify a "most general" path into root:
        Node pathRoot = createPath(false, root, path);
        if (pathRoot == null) {
            // The FS already contains the path!
            return root;
        }

        //logger.debug("Unifying with path "+new FeatureStructure(pathRoot,false));
        EquivRelation pathER = new EquivRelation();
        pathER.unify(root, pathRoot);
        pathER.extensionalize();
        return pathER.rebuild(root);
    }

    private static Node createPath(boolean infoAdded, Node fs, Path path)
        throws UnificationFailure
    {
        Type type = fs.getType();
        if (type instanceof JavaObject) {
            type = new ConjunctiveType(((JavaObject) type)._concept);
        }
        Node copy = type.newNode();
        if (path.isEmpty()) {
            if (!infoAdded) {
                copy = null;
            }
        } else {
            Name feature = path.first();
            if (!infoAdded && !fs.hasFeature(feature)) {
                infoAdded = true;
            }
            try {
                Node nextCopy = createPath(infoAdded, fs.delta(feature), path.butFirst());
                if (nextCopy == null) {
                    return null;
                }
                copy.setFeature(feature, nextCopy);
            } catch (NoSuchFeatureException nsf) {
                //logger.error("During createPath: "+nsf);
                throw new UnificationFailure();
            }
        }
        return copy;
    }

    /**
     * Returns whether fs1 and fs2 can be unified.
     *
     * @param fs1 the first feature structure to check
     * @param fs2 the second feature structure to check
     * @return true if the feature structures can be unified, false otherwise
     */
    public static boolean canUnify(FeatureStructure fs1, FeatureStructure fs2) {
        EquivRelation er = new EquivRelation();
        try {
            er.unify(fs1.getRoot(), fs2.getRoot());
            er.extensionalize();
            return true;
        } catch (UnificationFailure uff) {
            return false;
        }
    }

    /**
     * Creates a deep copy of the graph structure starting from the given root node.
     *
     * @param root the root node to copy
     * @return a new deep copy of the node and its substructure
     */
    public static Node deepCopy(Node root) {
        return new EquivRelation().rebuild(root);
    }

    private void addUnification(Node node1, Node node2) {
        _todo.push(new UnifyItem(node1, node2));
    }

    private void addRetyping(Node node, Type type) {
        _todo.push(new RetypeItem(node, type));
    }

    private ToDoItem nextToDoItem() {
        return _todo.pop();
    }

    private void map(Node fs, Node uni) {
        //logger.debug("mapping node "+fs.seqNo+" to node "+uni.seqNo);
        if (fs.equals(uni)) {
            return;
        }
        if (_eit.includesKey(fs)) { // fs is itself an equivClass
            // map all of fs's elements to uni:
            CollectionEnumeration equivClassElems = ((UpdatableSet) _eit.at(fs)).elements();
            while (equivClassElems.hasMoreElements()) {
                Node memberFS = (Node) equivClassElems.nextElement();
                map(memberFS, uni);
            }
            _eit.removeAt(fs);
        }

        _tie.putAt(fs, uni);
        UpdatableSet equivClass;
        if (_eit.includesKey(uni)) { // uni has been established before
            equivClass = (UpdatableSet) _eit.at(uni);
        } else { // uni is a new equivClass
            equivClass = new HashedSet();
            _eit.putAt(uni, equivClass);
        }
        equivClass.include(fs);
    }

    /**
     * Returns the unificator node for the given feature structure node.
     * If the node is not mapped to a unificator, returns the node itself.
     *
     * @param fs the node to find the unificator for
     * @return the unificator node, or the input node if no unificator exists
     */
    public Node getUnificator(Node fs) {
        if (_tie.includesKey(fs)) {
            return (Node) _tie.at(fs);
        } else {
            return fs;
        }
    }

    /**
     * Unifies two nodes by creating a unificator node and mapping both nodes to it.
     * The unificator combines the types and features of both input nodes.
     *
     * @param fs1 the first node to unify
     * @param fs2 the second node to unify
     * @throws UnificationFailure if the nodes cannot be unified due to type constraints
     */
    void unifyOne(Node fs1, Node fs2) throws UnificationFailure {
        //logger.debug("unifying nodes of type "+fs1.getType()+" and "+fs2.getType());
        if (fs1.equals(fs2)) {
            return;
        }
        Type unitype = fs1.getType().unify(fs2.getType());
        Node uni;
        if (_eit.includesKey(fs2) && unitype.equals(fs2.getType())) {
            uni = fs2;
        } else if (_eit.includesKey(fs1) && unitype.equals(fs1.getType())) {
            uni = fs1;
        } else {
            uni = unitype.newNode();
        }
        addAllFeatures(uni, fs1);
        addAllFeatures(uni, fs2);
        addRetypings(uni);

        // Update the relation:
        // both Nodes are mapped to their unificator.
        map(fs1, uni);
        map(fs2, uni);

    }

    /**
     * Refines the type of a node by unifying its current type with the given type.
     * If the types differ, creates a new node with the unified type and maps the original node to it.
     *
     * @param fs   the node to retype
     * @param type the type to unify with the node's current type
     * @throws UnificationFailure if the types cannot be unified
     */
    void retypeOne(Node fs, Type type) throws UnificationFailure {
        //logger.debug("Refining node of type "+fs.getType()+" with "+type);
        Type fstype = fs.getType();

        //logger.debug("Refining node of type "+fs.getType()+" with "+type);
        Type unitype = fstype.unify(type);

        //logger.debug("Succeeded with result "+unitype);
        if (!unitype.equals(fstype)) {
            //logger.debug("Retyping "+unitype+"...");
            Node retyped = unitype.newNode();


            //logger.debug("Adding Features...");
            addAllFeatures(retyped, fs);
            map(fs, retyped);


            //logger.debug("Adding Retypings...");
            addRetypings(retyped);
        }

        //logger.debug("Done.");
    }

    private void addAllFeatures(Node uni, Node fs) {
        if (!(fs instanceof JavaObject) && !uni.equals(fs)) {
            CollectionEnumeration featenumeration = fs.featureNames();
            while (featenumeration.hasMoreElements()) {
                Name featureName = (Name) featenumeration.nextElement();
                Node fspost = fs.delta(featureName);

                //logger.debug("Adding feature "+featureName+" value "+fspost.getType());
                if (uni.hasFeature(featureName)) {
                    Node unipost = uni.delta(featureName);
                    addUnification(fspost, unipost);
                } else {
                    if (uni instanceof JavaObject) {
                        throw new RuntimeException(
                            "Trying to set feature " + featureName + " in " + uni + " to "
                                + fspost);
                    }
                    uni.setFeature(featureName, fspost);
                }

                //logger.debug("Node feature "+featureName+" value "+uni.delta(featureName).getType());
            }
        }
    }

    private void addRetypings(Node uni) {
        Type unitype = uni.getType();
        if (!(unitype instanceof JavaObject)) {
            CollectionEnumeration feats = uni.featureNames();
            while (feats.hasMoreElements()) {
                Name feat = (Name) feats.nextElement();
                addRetyping(uni.delta(feat), unitype.appropType(feat));

                //  if (uni.delta(feat)==null)
                //        logger.debug("UNI: "+unitype+".appropType("+feat+"): "
                //                 +unitype.appropType(feat));
            }
        }
    }

    /**
     * Unifies all nodes in this EquivRelation according to the extensionability rule.
     */
    public void extensionalize() {}

    /**
     * Rebuilds a new graph which is the unificator.
     * Creates a new node structure that represents the unified result.
     *
     * @param fs one of the nodes that have been unified, which serves as the starting point
     * @return the root node of the rebuilt unified structure
     */
    public Node rebuild(Node fs) {
        //logger.debug("converting node "+fs.hashCode()+" of type "+fs.getType());
        Node uni;
        boolean expand;
        if (_tie.includesKey(fs)) {
            //logger.debug("node found in relation.");
            uni = (Node) _tie.at(fs);
            expand = _eit.includesKey(uni);
            if (expand) {
                _eit.removeAt(uni);
            }
        } else {
            //logger.debug("node not found in relation. Creating Copy ");
            //        if (eit.includesKey(fs)) {
            //logger.debug("Using unificator as new node.");
            //           uni = fs;
            //           eit.removeAt(uni);
            //        } else {
            //logger.debug("Creating copy.");
            uni = fs.duplicate();
            _tie.putAt(fs, uni);


            //        } /* endif */
            expand = true;
        }

        //logger.debug("node is now mapped to node "+uni.hashCode()+" of type "+uni.getType());
        if (expand && !(uni instanceof JavaObject)) {
            //logger.debug("Expanding node...");
            CollectionEnumeration featenumeration = uni.featureNames();
            while (featenumeration.hasMoreElements()) {
                Name featureName = (Name) featenumeration.nextElement();


                //logger.debug("Expanding feature "+featureName+" of node "+uni.hashCode()+"...");
                uni.setFeature(featureName, rebuild(uni.delta(featureName)));
            }
        }


        //else {
        // logger.debug("Already expanded.");
        //}
        return uni;
    }
}
