package de.uni_hamburg.fs;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import collections.CollectionEnumeration;
import collections.HashedSet;
import collections.UpdatableSet;


/**
 * Represents a Concept implementation within a type system.
 * A Concept consists of a name, relationships to other concepts, and a set of features (appropriates).
 */
public class ConceptImpl implements Concept {

    /** Logger instance for this class used for debugging and error reporting. */
    public static final org.apache.log4j.Logger LOGGER =
        org.apache.log4j.Logger.getLogger(ConceptImpl.class);
    /**
     * The fully qualified name of this concept in the format 'namespace::name'.
     */
    private String _name = null;
    /**
     * Flag indicating if this concept should become extensional after next hierarchy recalculation.
     */
    private boolean _newExtensional = false;
    /**
     * Flag indicating if this concept is currently extensional.
     */
    private boolean _extensional = false;
    /**
     * Set of all concepts that are transitively subsumed by this concept.
     */
    private UpdatableSet _subsumes;
    /**
     * Set of all extensional concepts that transitively subsume this concept.
     */
    private UpdatableSet _subsumedBy;

    /**
     * Set of concepts that are direct subconcepts (specializations) of this concept.
     */
    protected ConceptSet _directSubs = new ConceptSet();
    /**
     * Set of concepts that are direct superconcepts (generalizations) of this concept.
     */
    protected ConceptSet _directSupers = new ConceptSet();
    /**
     * Table of feature declarations and their types to be applied after next hierarchy recalculation.
     */
    private OrderedTable _newApprop = new OrderedTable();
    /**
     * Table of currently appropriate features and their types for this concept.
     */
    private OrderedTable _approp = new OrderedTable();
    /**
     * Flag indicating if this concept is a temporary placeholder concept.
     */
    private boolean _isDummy = false;
    /**
     * Contains all {@link Partition}s to which this concept belongs.
     * This <code>Set</code> is maintained by the <code>Partition</code> class.
     **/
    Set<Object> _partitions = new HashSet<Object>();

    /**
     * Default constructor. Creates a concept with an empty name.
     */
    ConceptImpl() {
        _name = "";
        transitiveClosure();
    }

    /**
     * Constructs a concept with the given name and direct super concepts.
     * @param name            the name of the concept
     * @param directSuperList array of direct super concepts
     * @throws TypeException if there is a type conflict in the hierarchy
     */
    public ConceptImpl(String name, ConceptImpl[] directSuperList) throws TypeException {
        this(name);
        for (int i = 0; i < directSuperList.length; ++i) {
            addIsa(directSuperList[i]);
        }
    }

    /**
     * Constructs a concept with the given name and a single super concept.
     * @param name         the name of the concept
     * @param superConcept the direct super concept
     * @throws TypeException if there is a type conflict in the hierarchy
     */
    public ConceptImpl(String name, ConceptImpl superConcept) throws TypeException {
        this(name, new ConceptImpl[] { superConcept });
    }

    /**
     * Constructs a concept with the given name, extensional flag, and dummy status.
     * @param name        the name of the concept
     * @param extensional whether this concept is extensional
     * @param isDummy     whether this concept is a dummy concept
     */
    public ConceptImpl(String name, boolean extensional, boolean isDummy) {
        this._extensional = extensional;
        this._isDummy = isDummy;
        _subsumes = new HashedSet();
        _subsumes.include(this);
        if (!setName(name)) {
            throw new RuntimeException("Concept " + name + " already exists!");
        }
        TypeSystem.instance().transitiveClosure();
    }

    /**
     * Constructs a concept with the given name and extensional flag.
     * @param name        the name of the concept
     * @param extensional whether this concept is extensional
     */
    public ConceptImpl(String name, boolean extensional) {
        this(name, extensional, false);
    }

    /**
     * Constructs an extensional concept with the given name.
     * @param name the name of the concept
     */
    public ConceptImpl(String name) {
        this(name, true);
    }

    /**
     * Return the name of this Concept.
     */
    @Override
    public String getName() {
        int end = _name.indexOf("::");
        if (end == -1) {
            return _name;
        }
        return _name.substring(end + 2);
    }

    /**
     * Return the name of the namespace this Concept belongs to.
     */
    @Override
    public String getNamespace() {
        int end = _name.indexOf("::");
        if (end == -1) {
            return "";
        }
        return _name.substring(0, end);
    }

    /**
     * Return the full name of this Concept in the form
     * namespace::name.
     */
    @Override
    public String getFullName() {
        return _name;
    }

    /**
     * Sets the name of this object to the specified value.
     * @param newname The new name to be set. If null, the name change may be rejected
     *                depending on implementation.
     * @return {@code true} if the name was successfully changed,
     * {@code false} if the name change was rejected
     */
    public boolean setName(String newname) {
        if (newname == null || newname.length() == 0) {
            return true;
        }
        if (newname.equals(_name)) {
            return true;
        }
        TypeSystem ts = TypeSystem.instance();
        if (ts.hasConcept(newname)) {
            LOGGER.error("Concept " + newname + " already exists!");
            return false;
        }
        if (_name != null) {
            ts.removeConcept(this);
            LOGGER.debug("Renaming concept " + _name + " to " + newname);
        } else {
            LOGGER.debug("Adding concept " + newname + " to  type system.");
        }
        _name = newname;
        ts.addConcept(this);
        return true;
    }

    /**
     * Returns whether this concept is a dummy concept.
     * @return true if this concept is a dummy concept, false otherwise
     */
    public boolean isDummy() {
        return _isDummy;
    }

    /**
     * Return whether this Concept is extensional.
     */
    @Override
    public boolean isExtensional() {
        return _extensional;
    }

    /**
     * Return whether the feature {@literal <feature>} is appropriate in this Concept.
     */
    @Override
    public boolean isApprop(Name feature) {
        if (_approp == null) {
            LOGGER.debug("Approp is null in " + _name + " (" + hashCode() + ") !!!");
        }
        return _approp.includesKey(feature);
    }

    @Override
    public ParsedType appropParsedType(Name featureName) throws NoSuchFeatureException {
        return (ParsedType) _approp.at(featureName);
    }

    /**
     * Return the required Type of the Value found under the given feature.
     */
    @Override
    public Type appropType(Name featureName) throws NoSuchFeatureException {
        try {
            return appropParsedType(featureName).asType();
        } catch (UnificationFailure uff) {
            throw new RuntimeException(
                "The ConjunctiveType " + appropParsedType(featureName) + " is not defined!");
        }
    }

    /**
     * Return an Enumeration of all appropriate features.
     */
    @Override
    public CollectionEnumeration appropFeatureNames() {
        return _approp.keys();
    }

    /**
     * Propagates features and extensional properties to subconcepts.
     * This method is part of the type inheritance mechanism.
     * @param visited set of visited concepts to prevent infinite recursion
     * @throws UnificationFailure if feature types cannot be unified
     */
    void inherit(UpdatableSet visited) throws UnificationFailure {
        visited.include(this);
        ConceptEnumeration subenumeration = _directSubs.elements();
        while (subenumeration.hasMoreElements()) {
            ConceptImpl sub = (ConceptImpl) subenumeration.nextConcept();
            if (_extensional) {
                if (!sub._extensional) {
                    sub._extensional = true;
                    sub._subsumedBy = new HashedSet();
                    sub._subsumedBy.include(sub);
                }
                sub._subsumedBy.include(this);
            }
            boolean subchanged = false;
            int subcount = 0;
            CollectionEnumeration appropenumeration = _approp.keys();
            while (appropenumeration.hasMoreElements()) {
                Name featureName = (Name) appropenumeration.nextElement();
                ParsedType appropType = appropParsedType(featureName);

                // logger.debug("Concept: "+name+" feature: "+featureName);
                if (sub.isApprop(featureName)) {
                    LOGGER.debug("Overwriting feature in subconcept " + sub.getName());
                    ParsedType oldsubapprop = (ParsedType) sub._approp.at(featureName);
                    ParsedType subapprop = oldsubapprop.unite(appropType);

                    //sub.approp.insertAt(featureName,subcount++,appropType);
                    if (!subchanged && !oldsubapprop.equals(subapprop)) {
                        subchanged = true;
                    }
                } else {
                    sub._approp.insertAt(featureName, subcount++, appropType);
                    subchanged = true;
                }
            }
            if (subchanged || !visited.includes(sub)) {
                sub.inherit(visited);
            }
        }
    }

    /**
     * Computes the transitive closure of the subsumption relation.
     * This method populates the _subsumes set with all concepts that are subsumed by this concept.
     */
    protected void transitiveClosure() {
        _subsumes = new HashedSet();
        _subsumes.include(this);
        ConceptEnumeration subenumeration = _directSubs.elements();
        while (subenumeration.hasMoreElements()) {
            ConceptImpl sub = (ConceptImpl) subenumeration.nextConcept();
            sub.transitiveClosure();
            _subsumes.includeElements(sub._subsumes.elements());
        }
    }

    /**
     * Recalculates the direct is-a relationships in the concept hierarchy.
     * This method is called when the concept hierarchy changes.
     * @param visited set of visited concepts to prevent infinite recursion
     * @throws TypeException if there's a type conflict in the hierarchy
     */
    void recalcDirectIsa(UpdatableSet visited) throws TypeException {
        if (!visited.includes(this)) {
            visited.include(this);
            try {
                _directSupers.join();
            } catch (UnificationFailure uff) {
                TypeException tex = new TypeException(this);
                throw tex;
            }
            _directSubs.meet();

            _extensional = _newExtensional;
            if (_extensional) {
                _subsumedBy = new HashedSet();
                _subsumedBy.include(this);
            } else {
                _subsumedBy = null;
            }
            _approp = (OrderedTable) _newApprop.duplicate();

            CollectionEnumeration subenumeration = _directSubs.elements();
            while (subenumeration.hasMoreElements()) {
                ((ConceptImpl) subenumeration.nextElement()).recalcDirectIsa(visited);
            }
        }
    }

    /**
     * Adds a direct is-a relationship to a super concept without checking for cycles.
     * This is an internal method used by addIsa.
     * @param superconcept the super concept to add to the hierarchy
     */
    void basicAddIsa(ConceptImpl superconcept) {
        _directSupers.addConcept(superconcept);
        superconcept._directSubs.addConcept(this);
        LOGGER.debug("Adding " + this + " isa " + superconcept);
    }

    /**
     * Adds a direct is-a relationship to a super concept, checking for cycles.
     * This establishes a subtype relationship between this concept and the super concept.
     * @param superconcept the super concept to add to the hierarchy
     * @throws CyclicHierarchyException if adding the relationship would create a cycle
     * @throws TypeException            if there's a type conflict in the hierarchy
     */
    public void addIsa(ConceptImpl superconcept) throws CyclicHierarchyException, TypeException {
        if (superconcept.isa(this)) {
            throw new CyclicHierarchyException();
        }
        if (isa(superconcept)) {
            return;
        }
        basicAddIsa(superconcept);
        TypeSystem.instance().recalcDirectIsa();
    }

    /**
     * Adds an appropriate feature with the given name and type to this concept.
     * @param feature the string name of the feature
     * @param type    the parsed type of the feature
     */
    public void addApprop(String feature, ParsedType type) {
        addApprop(new Name(feature), type);
    }

    /**
     * Adds an appropriate feature with the given name and type to this concept.
     * @param featureName the name object representing the feature
     * @param type        the parsed type of the feature
     */
    public void addApprop(Name featureName, ParsedType type) {
        LOGGER.debug("Feature " + featureName + " defined in " + getName());
        _newApprop.putAt(featureName, type);
    }

    /**
     * Sets all appropriate features for this concept at once.
     * @param approps the ordered table of feature names and their types
     */
    public void setApprops(OrderedTable approps) {
        _newApprop = (OrderedTable) approps.duplicate();
    }

    /**
     * Converts all parsed types of features to actual types.
     * This method verifies that all feature types are well-formed.
     * @param visited set of visited concepts to prevent infinite recursion
     * @throws TypeException if a feature type cannot be converted to a real type
     */
    void buildFeatureTypes(UpdatableSet visited) throws TypeException {
        if (!visited.includes(this)) {
            visited.include(this);
            LOGGER.debug("Converting feature types for concept " + toDetailedString());
            CollectionEnumeration featenumeration = _approp.keys();
            while (featenumeration.hasMoreElements()) {
                Name feature = (Name) featenumeration.nextElement();

                LOGGER.debug("Converting feature " + feature);
                ParsedType pt = (ParsedType) _approp.at(feature);
                try {
                    pt.asType();
                } catch (UnificationFailure uff) {
                    throw new TypeException(this, feature);
                }
            }
            CollectionEnumeration subenumeration = _directSubs.elements();
            while (subenumeration.hasMoreElements()) {
                ((ConceptImpl) subenumeration.nextElement()).buildFeatureTypes(visited);
            }
        }
    }

    /**
     * Return whether this Concept is-a {@literal <that>} Concept.
     * In other words, return whether this Concept is more special than {@literal <that>}
     * Concept.
     */
    @Override
    public boolean isa(Concept that) {
        if (that instanceof ConceptImpl) {
            return ((ConceptImpl) that)._subsumes.includes(this);
        } else {
            return false;
        }
    }

    /**
     * Return the Partitions this ConceptImpl belongs to.
     * @return an iterator over the partitions this concept belongs to
     */
    public Iterator<Object> getPartitions() {
        return _partitions.iterator();
    }

    /**
     * Return whether this Concept is-not-a {@literal <that>} Concept.
     * In other words, return whether this Concept is incompatible with {@literal <that>}
     * Concept.
     */
    @Override
    public boolean isNotA(Concept that) {
        if (this == that) {
            return false;
        }
        if (that instanceof ConceptImpl) {
            ConceptImpl thatCon = (ConceptImpl) that;
            if (intersects(_partitions, thatCon._partitions)) {
                return true;
            }
            return superIsNotA(thatCon) || thatCon.superIsNotA(this);


            // TODO: this isNotA that is also true if some appropType
            // of this is incompatible with the corresponding appropType
            // of that. Caution: recursive definition!!!
        }
        return true;
    }

    /**
     * Checks if two sets have any elements in common.
     * @param a the first set
     * @param b the second set
     * @return true if the sets have at least one element in common, false otherwise
     */
    private boolean intersects(Set<?> a, Set<?> b) {
        if (a.size() > b.size()) {
            return intersects(b, a);
        }
        for (Iterator<?> as = a.iterator(); as.hasNext();) {
            if (b.contains(as.next())) {
                return true;
            }
        }
        return false;
    }

    /**
     * Checks if any direct super concept of this concept is not-a the given concept.
     * @param that the concept to check against
     * @return true if any super concept is incompatible with the given concept, false otherwise
     */
    private boolean superIsNotA(ConceptImpl that) {
        ConceptEnumeration superenumeration = _directSupers.elements();
        while (superenumeration.hasMoreElements()) {
            Concept superCon = superenumeration.nextConcept();
            if (superCon.isNotA(that)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public ConceptEnumeration extensionalSuperconcepts() {
        return new ConceptEnumeration(_subsumedBy.elements());
    }

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

    /**
     * Returns a detailed string representation of this concept.
     * The representation includes the concept name, extensional status,
     * features with their types, and direct super and sub concepts.
     * @return a detailed string representation of this concept
     */
    public String toDetailedString() {
        StringBuffer output = new StringBuffer(_name);
        if (_extensional) {
            output.append(" (extensional)");
        }
        if (_approp == null) {
            LOGGER.warn("Approp is null in " + _name + " (" + hashCode() + ") !!!");
        } else {
            CollectionEnumeration appropenum = _approp.keys();
            while (appropenum.hasMoreElements()) {
                Name featureName = (Name) appropenum.nextElement();
                Object appropTypeGuess = _approp.at(featureName);
                if (appropTypeGuess instanceof Type) {
                    Type appropType = (Type) appropTypeGuess;
                    output.append("\n ").append(featureName.toString()).append(":")
                        .append(appropType.getName());
                } else {
                    output.append("\n ").append(featureName.toString()).append(":")
                        .append(appropTypeGuess.toString());
                }
            }
        }
        output.append("\nDirect Supers: ").append(_directSupers.toString());
        output.append("\nDirect Subs: ").append(_directSubs.toString());
        return output.toString();
    }
}