package de.uni_hamburg.fs;

import java.util.Enumeration;
import java.util.Vector;

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


/**
 * Defines all methods needed to construct, access and unify Feature Structures.
 * <p>
 * A FeatureStructure mainly wraps a Node and provides customized access to
 * the Node's type, features, and other properties. Feature structures are
 * directed graphs that represent linguistic and semantic information with
 * attribute-value pairs.
 * </p>
 */
public class FeatureStructure implements java.io.Serializable {
    /**
     * Logger instance for this class, used for debug and error logging.
     */
    public static final org.apache.log4j.Logger LOGGER =
        org.apache.log4j.Logger.getLogger(FeatureStructure.class);

    /**
     * The underlying node that this feature structure wraps.
     * This node represents the root of the feature structure and contains
     * all feature-value pairs and type information.
     */
    private Node _node;

    /**
     * Cached hash code value for this feature structure.
     * This field is protected as subclasses may need to access or modify it
     * during specialized hash code calculations.
     */
    protected int _hashCode;

    /**
     * Constructs a new feature structure wrapping the specified node.
     * This constructor performs node reduction by default.
     *
     * @param node the node to wrap in this feature structure
     */
    public FeatureStructure(Node node) {
        this(node, true);
    }

    /**
     * Constructs a new feature structure wrapping the specified node with control over reduction.
     *
     * @param node             the node to wrap in this feature structure
     * @param mayNeedReduction if true, performs reduction on the node to remove informationless nodes
     */
    public FeatureStructure(Node node, boolean mayNeedReduction) {
        this._node = node;
        if (mayNeedReduction) {
            reduce();
        }
        computeHashCode(node, new HashedSet());
    }

    /**
     * Constructs a new feature structure with a node of the specified type.
     * Creates a new node of the given type and wraps it without reduction.
     *
     * @param type the type to create a node from
     */
    public FeatureStructure(Type type) {
        this(type.newNode(), false);
    }

    private void computeHashCode(Node node, UpdatableSet visited) {
        if (!visited.includes(node)) {
            visited.include(node);
            Type type = node.getType();
            _hashCode += type.hashCode();
            if (!(type instanceof JavaObject)) {
                // features contribute to hashCode:
                CollectionEnumeration featenumeration = node.featureNames();
                while (featenumeration.hasMoreElements()) {
                    Name feature = (Name) featenumeration.nextElement();
                    _hashCode += feature.hashCode();
                    computeHashCode(node.delta(feature), visited);
                }
            }
        }
    }

    /**
     * Returns the Type of this Feature Structure's root node.
     *
     * @return the Type of the root node
     */
    public Type getType() {
        return _node.getType();
    }

    /**
     * Returns the Type of the Feature Structure found at the given path.
     * <p>
     * A path is a sequence of Features starting at the root node.
     * The syntax of a path is feature_1:feature_2:...feature_n.
     * </p>
     *
     * @param path a string representation of the path to follow
     * @return the Type of the Feature Structure at the specified path
     * @throws NoSuchFeatureException if the path contains a feature that doesn't exist
     */
    public Type getType(String path) throws NoSuchFeatureException {
        return _node.delta(new Path(path)).getType();
    }

    /**
     * Returns the root node of this Feature Structure.
     * The root node provides direct access to the underlying representation.
     *
     * @return the root node of this Feature Structure
     */
    public Node getRoot() {
        return _node;
    }

    /**
     * Returns the Java Object contained in this Feature Structure's root node.
     * <p>
     * This method provides access to the Java object underlying the root node's type.
     * </p>
     *
     * @return the Java object contained in this Feature Structure
     * @throws ClassCastException if the root's type is not a JavaType
     */
    public Object getJavaObject() {
        return ((JavaType) _node.getType()).getJavaObject();
    }

    /**
     * Tests whether this Feature Structure subsumes the specified Feature Structure.
     * <p>
     * A Feature Structure subsumes another if it is more general and
     * can encompass the other structure's information.
     * </p>
     *
     * @param that the Feature Structure to test against
     * @return true if this Feature Structure subsumes the specified one, false otherwise
     */
    public boolean subsumes(FeatureStructure that) {
        return Subsumption.subsumes(this, that);
    }

    /**
     * Tests whether this Feature Structure is subsumed by the specified Feature Structure.
     * <p>
     * This is the inverse of the subsumes relation. A Feature Structure is subsumed by
     * another if it is more specific than the other structure.
     * </p>
     *
     * @param that the Feature Structure to test against
     * @return true if this Feature Structure is subsumed by the specified one, false otherwise
     */
    public boolean subsumedBy(FeatureStructure that) {
        return that.subsumes(this);
    }

    /**
     * Calculates the unification of this Feature Structure with the specified Feature Structure.
     * <p>
     * Unification combines the information from both structures into a single new structure,
     * if the structures are compatible.
     * </p>
     *
     * @param that the Feature Structure to unify with
     * @return a new Feature Structure representing the unification result
     * @throws UnificationFailure if the Feature Structures cannot be unified due to incompatible information
     */
    public FeatureStructure unify(FeatureStructure that) throws UnificationFailure {
        return new FeatureStructure(EquivRelation.unify(this, that));
    }

    /**
     * Calculates the unification of this Feature Structure and the specified Feature Structure
     * at the given path.
     * <p>
     * This unifies the Feature Structure at the specified path in this structure
     * with the entire specified Feature Structure.
     * </p>
     *
     * @param that the Feature Structure to unify with
     * @param path a string representation of the path where unification should occur
     * @return a new Feature Structure representing the unification result
     * @throws UnificationFailure if the Feature Structures cannot be unified due to incompatible information
     */
    public FeatureStructure unify(FeatureStructure that, String path) throws UnificationFailure {
        return unify(that, new Path(path));
    }

    /**
     * Calculates the unification of this Feature Structure and the specified Feature Structure
     * at the given path.
     * <p>
     * This unifies the Feature Structure at the specified path in this structure
     * with the entire specified Feature Structure.
     * </p>
     *
     * @param that the Feature Structure to unify with
     * @param path the Path object specifying where unification should occur
     * @return a new Feature Structure representing the unification result
     * @throws UnificationFailure if the Feature Structures cannot be unified due to incompatible information
     */
    public FeatureStructure unify(FeatureStructure that, Path path) throws UnificationFailure {
        return new FeatureStructure(EquivRelation.unify(this, path, that));
    }

    /**
     * Creates a new Feature Structure by unifying nodes at two specified paths within this structure.
     * <p>
     * This method identifies (makes equal) the nodes at the two given paths.
     * </p>
     *
     * @param path1 a string representation of the first path
     * @param path2 a string representation of the second path
     * @return a new Feature Structure with the nodes at the given paths unified
     * @throws UnificationFailure if the nodes at the specified paths cannot be unified
     */
    public FeatureStructure equate(String path1, String path2) throws UnificationFailure {
        return equate(new Path(path1), new Path(path2));
    }

    /**
     * Creates a new Feature Structure by unifying nodes at two specified paths within this structure.
     * <p>
     * This method identifies (makes equal) the nodes at the two given paths.
     * </p>
     *
     * @param path1 the first Path object
     * @param path2 the second Path object
     * @return a new Feature Structure with the nodes at the given paths unified
     * @throws UnificationFailure if the nodes at the specified paths cannot be unified
     */
    public FeatureStructure equate(Path path1, Path path2) throws UnificationFailure {
        return new FeatureStructure(EquivRelation.unify(this, path1, path2));
    }

    /**
     * Tests whether this Feature Structure can be unified with the specified Feature Structure.
     * <p>
     * This method checks compatibility without actually performing the unification.
     * </p>
     *
     * @param that the Feature Structure to test for unification compatibility
     * @return true if the structures can be unified, false otherwise
     */
    public boolean canUnify(FeatureStructure that) {
        return EquivRelation.canUnify(this, that);
    }

    /**
     * Returns an enumeration of all feature names in this Feature Structure.
     * <p>
     * This method returns the feature names directly from the root node.
     * </p>
     *
     * @return an enumeration of Name objects representing all features in this structure
     */
    public CollectionEnumeration featureNames() {
        return _node.featureNames();
    }

    /**
     * Checks if this Feature Structure has a feature with the specified name.
     *
     * @param feature the name of the feature to check for
     * @return true if the feature exists, false otherwise
     */
    public boolean hasFeature(String feature) {
        return _node.hasFeature(new Name(feature));
    }

    /**
     * Checks if this Feature Structure has a feature with the specified Name object.
     *
     * @param featureName the Name object representing the feature to check for
     * @return true if the feature exists, false otherwise
     */
    public boolean hasFeature(Name featureName) {
        return _node.hasFeature(featureName);
    }

    /**
     * Returns the Feature Structure at the given path.
     * <p>
     * A path is a sequence of features starting at the root node.
     * The syntax of a path is feature_1:feature_2:...feature_n.
     * The empty string returns this Feature Structure itself.
     * </p>
     *
     * @param path a string representation of the path to follow
     * @return the Feature Structure at the specified path
     * @throws NoSuchFeatureException if any feature in the path does not exist
     */
    public FeatureStructure at(String path) throws NoSuchFeatureException {
        return at(new Path(path));
    }

    /**
     * Returns the Feature Structure at the given Path object.
     * <p>
     * This method follows the path from the root node and wraps the resulting node
     * in a new Feature Structure.
     * </p>
     *
     * @param path the Path object to follow
     * @return the Feature Structure at the specified path
     * @throws NoSuchFeatureException if any feature in the path does not exist
     */
    public FeatureStructure at(Path path) throws NoSuchFeatureException {
        return new FeatureStructure(delta(path), true);
    }

    /**
     * Returns either a Java object or a Feature Structure at the specified path.
     * <p>
     * If the node at the path has a JavaType, this method returns the underlying Java object.
     * Otherwise, it returns a new Feature Structure wrapping the node.
     * </p>
     *
     * @param path the Path object to follow
     * @return the Java object if the node at the path has a JavaType, otherwise a Feature Structure
     * @throws NoSuchFeatureException if any feature in the path does not exist
     */
    public Object unpackingAt(Path path) throws NoSuchFeatureException {
        Node subnode = _node.delta(path);
        Type subtype = subnode.getType();
        if (subtype instanceof JavaType) {
            return ((JavaType) subtype).getJavaObject();
        }
        return new FeatureStructure(subnode, true);
    }

    /**
     * Returns the Node at the specified path.
     * <p>
     * This method provides direct access to the Node at the path without wrapping it
     * in a Feature Structure.
     * </p>
     *
     * @param path a string representation of the path to follow
     * @return the Node at the specified path
     * @throws NoSuchFeatureException if any feature in the path does not exist
     */
    public Node delta(String path) throws NoSuchFeatureException {
        return delta(new Path(path));
    }

    /**
     * Returns the Node for the specified feature in the root node.
     * <p>
     * This method provides direct access to the feature value without traversing a path.
     * </p>
     *
     * @param feature the Name object representing the feature to access
     * @return the Node value of the feature
     * @throws NoSuchFeatureException if the feature does not exist
     */
    public Node delta(Name feature) throws NoSuchFeatureException {
        return _node.delta(feature);
    }

    /**
     * Returns the Node at the specified Path.
     * <p>
     * This method follows the path from the root node and returns the Node at that location
     * without wrapping it in a Feature Structure.
     * </p>
     *
     * @param path the Path object to follow
     * @return the Node at the specified path
     * @throws NoSuchFeatureException if any feature in the path does not exist
     */
    public Node delta(Path path) throws NoSuchFeatureException {
        return _node.delta(path);
    }

    /**
     * Determines whether this Feature Structure can be instantiated as a Java object.
     * <p>
     * This method checks if the structure contains all necessary information
     * for instantiation and if its type system allows instantiation.
     * </p>
     *
     * @return true if this Feature Structure can be instantiated, false otherwise
     */
    public boolean canInstantiate() {
        UpdatableSet toBeInstantiated = new HashedSet();
        int countToBeInstantiated;
        boolean canInstantiate;
        do {
            countToBeInstantiated = toBeInstantiated.size();
            canInstantiate = canInstantiate(_node, new HashedSet(), toBeInstantiated);
        } while (!canInstantiate && toBeInstantiated.size() > countToBeInstantiated);

        // repeat while additional "toBeInstantiated"-nodes were found.
        return canInstantiate;
    }

    private static boolean canInstantiate(
        Node node, UpdatableSet visited, UpdatableSet toBeInstantiated)
    {
        if (isInstantiated(node, toBeInstantiated)) {
            return true;
        }
        Type typ = node.getType();
        if (visited.includes(node)) {
            return !typ.isInstanceType();


            // cyclic reference to a Node in "unknown" state:
            // in that case, we only allow cycles for non-instance types.
        }
        visited.include(node);
        boolean include = false;
        if (typ.isInstanceType()) {
            if (typ instanceof ListType) {
                ListType listType = (ListType) typ;
                if (listType.getSubtype() == ListType.ELIST) {
                    include = true;
                } else if (listType.getSubtype() == ListType.NELIST) {
                    include = isInstantiated(node.delta(ListType.HEAD), toBeInstantiated)
                        && isInstantiated(node.delta(ListType.TAIL), toBeInstantiated);
                }
            } else if (typ instanceof ConjunctiveType) {
                // check if there is exactly one JavaConcept to instantiate:
                JavaConcept onlyConcept = ((ConjunctiveType) typ).getOnlyInstantiableJavaConcept();
                if (onlyConcept != null) {
                    JavaConcept javaConcept = onlyConcept;
                    CollectionEnumeration feats = node.featureNames();
                    include = true;
                    while (feats.hasMoreElements()) {
                        Name feature = (Name) feats.nextElement();
                        if (!javaConcept.getJavaFeature(feature).canSet()
                            || !isInstantiated(node.delta(feature), toBeInstantiated)) {
                            include = false;
                            break;
                        }
                    }
                }
            }
        }
        if (include) {
            toBeInstantiated.include(node);
        }
        boolean canInstantiate = include || !typ.isInstanceType();
        CollectionEnumeration feats = node.featureNames();
        while (feats.hasMoreElements()) {
            Name feature = (Name) feats.nextElement();
            canInstantiate &= canInstantiate(node.delta(feature), visited, toBeInstantiated);
        }
        return canInstantiate;
    }

    private static boolean isInstantiated(Node node, Set toBeInstantiated) {
        if (toBeInstantiated.includes(node)) {
            return true;
        }
        Type typ = node.getType();
        return typ instanceof JavaType || typ instanceof BasicType && ((BasicType) typ).isObject();
    }

    /**
     * Instantiates this Feature Structure, converting appropriate nodes into Java objects.
     * <p>
     * For types that represent Java objects, this method creates actual Java instances.
     * If the structure is already fully instantiated, it returns this structure instead
     * of creating a new one.
     * </p>
     *
     * @return a new Feature Structure with all nodes instantiated as Java objects where possible
     * @throws NotInstantiableException if the Feature Structure cannot be instantiated
     */
    public FeatureStructure instantiate() throws NotInstantiableException {
        // check if no nodes have to be instantiated (may happen quite often):
        UpdatableSet toBeInstantiated = new HashedSet();
        if (canInstantiate(_node, new HashedSet(), toBeInstantiated)
            && toBeInstantiated.size() == 0) {
            return this; // don't rebuild the same FS!
        }
        return new FeatureStructure(instantiate(_node, new HashedMap()), false);
    }

    private static Node instantiate(Node node, UpdatableMap objMap)
        throws NotInstantiableException
    {
        if (objMap.includesKey(node)) {
            return (Node) objMap.at(node);
        }
        Type typ = node.getType();
        Node newNode = null;
        boolean mapFeatures = true;
        if (typ.isInstanceType()) {
            if (typ instanceof JavaType) {
                newNode = node;
                mapFeatures = false;
            } else if (typ instanceof ListType) {
                // copy list elements to Vector:
                Node current = node;
                Vector<Object> elements = new Vector<Object>();
                while (current != null
                    && ((ListType) current.getType()).getSubtype() == ListType.NELIST) {
                    Node objNode = instantiate(current.delta(ListType.HEAD), objMap);
                    elements.addElement(((JavaType) objNode.getType()).getJavaObject());
                    current = current.delta(ListType.TAIL);
                }
                Object[] elemArray = new Object[elements.size()];
                elements.copyInto(elemArray);
                Object array = JavaArrayType.makeArray(elemArray);
                newNode = new JavaArrayType(array).newNode();
                mapFeatures = false;
            } else {
                // there has to be exactly one JavaConcept to instantiate:
                try {
                    JavaConcept javaConcept =
                        (JavaConcept) ((ConjunctiveType) typ)._concepts.elements().nextConcept();
                    Object object = javaConcept.getJavaClass().newInstance();
                    newNode = new JavaObject(object);
                } catch (Exception e) {
                    LOGGER.error("Cannot instantiate: " + e);
                    // logger.error(e.getMessage(), e);
                    throw new NotInstantiableException(new FeatureStructure(node, false));
                    // should not fail if canInstantiate() has been called before!
                }
            }
        } else {
            // copy old Node with new feature values:
            newNode = typ.newNode();
        }
        objMap.putAt(node, newNode);
        if (mapFeatures) {
            CollectionEnumeration feats = node.featureNames();
            while (feats.hasMoreElements()) {
                Name feature = (Name) feats.nextElement();
                newNode.setFeature(feature, instantiate(node.delta(feature), objMap));
            }
        }
        return newNode;
    }

    /**
     * Creates a new Feature Structure with a modified feature value.
     * <p>
     * This method creates a shallow copy of this structure and replaces the value of the
     * specified feature with the new value.
     * </p>
     *
     * @param feature  the name of the feature to change
     * @param newValue the new Feature Structure to set as the feature's value
     * @return a new Feature Structure with the modified feature
     */
    public FeatureStructure change(String feature, FeatureStructure newValue) {
        Name featureName = new Name(feature);
        FSNode newNode = (FSNode) _node.duplicate();
        newNode.setFeature(featureName, newValue._node);
        return new FeatureStructure(newNode);
    }

    /**
     * Returns an enumeration of all nodes in this Feature Structure.
     * <p>
     * This method traverses the entire structure and collects all nodes,
     * excluding JavaObject nodes. Each node is included only once, even if
     * referenced multiple times in the structure.
     * </p>
     *
     * @return an Enumeration containing all unique nodes in the structure
     */
    public Enumeration<Node> getNodes() {
        return addNodes(new HashedSet(), _node).elements();
    }

    private static UpdatableSet addNodes(UpdatableSet nodes, Node fs) {
        if (!(fs instanceof JavaObject) && !nodes.includes(fs)) {
            nodes.include(fs);
            CollectionEnumeration featenumeration = fs.featureNames();
            while (featenumeration.hasMoreElements()) {
                Name feature = (Name) featenumeration.nextElement();
                addNodes(nodes, fs.delta(feature));
            }
        }
        return nodes;
    }

    /**
     * Finds one possible path from the root node to a target node.
     * <p>
     * This method searches through the feature structure to find any path
     * that leads to the specified target node. If multiple paths exist,
     * only one is returned.
     * </p>
     *
     * @param target the Node to find a path to
     * @return a Path object representing the path to the target node, or null if no path exists
     */
    public Path onePathTo(Node target) {
        return onePathTo(new HashedSet(), _node, Path.EPSILON, target);
    }

    private static Path onePathTo(UpdatableSet nodes, Node fs, Path path, Node target) {
        if (fs.equals(target)) {
            return path;
        }
        if (!nodes.includes(fs)) {
            nodes.include(fs);
            CollectionEnumeration featenumeration = fs.featureNames();
            while (featenumeration.hasMoreElements()) {
                Name feature = (Name) featenumeration.nextElement();
                Path found = onePathTo(nodes, fs.delta(feature), path.append(feature), target);
                if (found != null) {
                    return found;
                }
            }
        }
        return null;
    }

    /**
     * Returns all nodes that can reach the specified target node.
     * <p>
     * This method finds all nodes in the feature structure that have
     * a path leading to the specified target node. It effectively
     * reverses the graph and collects nodes that can reach the target.
     * </p>
     *
     * @param target the Node to find backwards reachable nodes for
     * @return an Enumeration of nodes that can reach the target node
     */
    public Enumeration<Node> backwardsReachableNodes(Node target) {
        UpdatableMap map = new HashedMap();
        UpdatableMap pam = new HashedMap();
        reverse(_node, new HashedSet(), 0, map, pam);
        if (!map.includesKey(target)) {
            // target is not reachable at all!
            // logger.debug("Target node "+target+" was not found!");
            return EmptyEnumeration.INSTANCE;
        }
        Node newRoot = (Node) map.at(target);
        FeatureStructure reverseFS = new FeatureStructure(newRoot, false);


        //        logger.debug("FS: "+this+"reversed at "+onePathTo(target)+": "
        //               +reverseFS);
        //  logger.debug("Map:");
        //  Enumeration keys=map.keys();
        //  while (keys.hasMoreElements()) {
        //    Node key=(Node)keys.nextElement();
        //    logger.debug(onePathTo(key)+" mapped to "+reverseFS.onePathTo((Node)map.at(key))+":"+map.at(key).hashCode());
        //  }
        Enumeration<Node> reachenumeration = reverseFS.getNodes();
        UpdatableSet backwardsReachableNodes = new HashedSet();

        //      logger.debug("Backwards Reachable nodes:");
        while (reachenumeration.hasMoreElements()) {
            Node bnode = (Node) pam.at(reachenumeration.nextElement());
            backwardsReachableNodes.include(bnode);
            //  logger.debug(bnode+", ");
        }

        return backwardsReachableNodes.elements();
    }

    private static Node getReverse(UpdatableMap map, UpdatableMap pam, Node fs) {
        Node rev;
        if (map.includesKey(fs)) {
            rev = (Node) map.at(fs);
        } else {
            rev = Type.ANY.newNode();
            map.putAt(fs, rev);


            // logger.debug("Mapping "+fs.hashCode()+" to "+rev.hashCode());
            pam.putAt(rev, fs);
        }
        return rev;
    }

    private int reverse(
        Node fs, UpdatableSet visited, int featureCnt, UpdatableMap map, UpdatableMap pam)
    {
        if (visited.includes(fs) || fs instanceof JavaObject) {
            return featureCnt;
        }
        visited.include(fs);
        Node fsRev = getReverse(map, pam, fs);

        // logger.debug("Visiting "+onePathTo(fs)+":"+fs.hashCode());
        CollectionEnumeration featenumeration = fs.featureNames();
        while (featenumeration.hasMoreElements()) {
            Name feature = (Name) featenumeration.nextElement();
            Node next = fs.delta(feature);
            Node nextRev = getReverse(map, pam, next);
            nextRev.setFeature(new Name("f" + featureCnt), fsRev);


            // logger.debug("Setting reverse feature "+feature+" (f"+featureCnt+") in "+nextRev.hashCode()+" to "+fsRev.hashCode());
            featureCnt = reverse(next, visited, ++featureCnt, map, pam);
        }
        return featureCnt;
    }

    /**
     * Remove all informationless nodes from this FS.
     */
    public void reduce() {
        UpdatableSet infoNodes = new HashedSet();
        infoNodes.include(_node);
        // the root is always regared as "infoful"
        // findInfo until no more infoNodes are added:


        //int cnt = 0;
        int lastNoInfoNodes;
        int noInfoNodes = 1;
        do {
            //++cnt;
            UpdatableSet allNodes = new HashedSet();
            lastNoInfoNodes = noInfoNodes;
            findInfo(_node, allNodes, infoNodes);
            noInfoNodes = infoNodes.size();


            // Often, FSs are already reduced. Then, all nodes are
            // declared as "infoful".
            if (noInfoNodes == allNodes.size()) {
                // logger.debug("Discovered that fs was already reduced after "+cnt+" turns.");
                return;
            }
        } while (noInfoNodes > lastNoInfoNodes);


        // logger.debug("Reduction took "+cnt+" turns.");
        // make a deep copy of the whole object graph, leaving out
        // infoless nodes:
        _node = copyInfoNodes(_node, new HashedMap(), infoNodes);
    }

    private static void findInfo(Node fs, UpdatableSet visited, UpdatableSet infoNodes) {
        if (visited.includes(fs)) {
            // found co-reference:
            infoNodes.include(fs);
        } else {
            visited.include(fs);
            if (fs instanceof JavaObject) {
                infoNodes.include(fs); // java objects are always infoful
            } else {
                CollectionEnumeration featenumeration = fs.featureNames();
                Type fstype = fs.getType();
                boolean hasInfo = infoNodes.includes(fs);
                while (featenumeration.hasMoreElements()) {
                    Name feature = (Name) featenumeration.nextElement();
                    Node next = fs.delta(feature);
                    boolean nextHasInfo = infoNodes.includes(next);
                    if (!nextHasInfo && !next.getType().equals(fstype.appropType(feature))) {
                        // found more special type in feature value
                        // logger.debug("Found specialised node type "+next.getType());
                        infoNodes.include(next);
                        nextHasInfo = true;
                    }
                    if (!hasInfo && nextHasInfo) {
                        infoNodes.include(fs);
                        hasInfo = true;
                    }
                    findInfo(next, visited, infoNodes);
                }
            }
        }
    }

    private static Node copyInfoNodes(Node fs, UpdatableMap map, Set infoNodes) {
        if (fs instanceof JavaObject) {
            return fs;
        }
        if (map.includesKey(fs)) {
            return (Node) map.at(fs);
        }
        Node copy = fs.duplicate();
        map.putAt(fs, copy);
        CollectionEnumeration featenumeration = fs.featureNames();
        while (featenumeration.hasMoreElements()) {
            Name feature = (Name) featenumeration.nextElement();
            Node next = copy.delta(feature);
            if (infoNodes.includes(next)) {
                copy.setFeature(feature, copyInfoNodes(next, map, infoNodes));
            } else {
                // remove feature to infoless node:
                copy.setFeature(feature, null);
            }
        }
        return copy;
    }

    /**
     * Finds the first missing required association in this Feature Structure.
     * <p>
     * This method checks for missing features that are appropriate for the
     * structure's type but haven't been set. It only considers features
     * that can be set according to the Java concept constraints.
     * </p>
     *
     * @return a Feature object representing the first missing association,
     * or null if all required associations are present
     */
    public Feature getFirstMissingAssociation() {
        Type type = _node.getType();
        CollectionEnumeration feats = type.appropFeatureNames();
        JavaConcept jc = null;
        if (type instanceof ConjunctiveType) {
            jc = ((ConjunctiveType) type).getOnlyInstantiableJavaConcept();
        }
        while (feats.hasMoreElements()) {
            Name feature = (Name) feats.nextElement();
            if (!_node.hasFeature(feature)) {
                Type approp = type.appropType(feature);
                if (!(approp instanceof BasicType)
                    && (jc == null || jc.getJavaFeature(feature).canSet())) {
                    return new Feature(feature, approp);
                }
            }
        }
        return null;
    }

    @Override
    public boolean equals(Object that) {
        if (that instanceof FeatureStructure) {
            // works, but is *very* inefficient:
            //return this.subsumes((FeatureStructure)that) && ((FeatureStructure)that).subsumes(this);
            // FSs have to have exactly the same types, features & co-references
            return Equality.equals(this, (FeatureStructure) that);
        }
        return false;
    }

    @Override
    public int hashCode() {
        return _hashCode;
    }

    @Override
    public String toString() {
        return PrettyPrinter.toString(this);
    }
}