// (C) Copyright 2008-2009 SDML (www.sdml.info)
//
// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

// Copyright Andrew Sutton 2007
//
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0. (See accompanying file
// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_FCA_CONCEPT_HPP
#define BOOST_FCA_CONCEPT_HPP

#include <set>
#include <iterator>
#include <algorithm>

// Can I get rid of this?
#include <ext/algorithm>

namespace boost {
namespace fca {

    // A concept is a generic with respect to a relation. All of the types
    // used by the concept are defined by the relation parameter.

    // A (formal) concept is essentially a pair of sets - a set of objects and
    // a set of attributes such that the two are "maximally" matched. In other
    // words, there are no other objects in the context that share the same
    // set of attributes, and there are no other attributes posessed possessed
    // in common by these objects. Or something like that.
    template <typename Relation>
    class concept
    {
    public:
        typedef Relation relation_type;

        typedef typename relation_type::object_type object_type;
        typedef typename relation_type::object_set object_set;

        typedef typename relation_type::attribute_type attribute_type;
        typedef typename relation_type::attribute_set attribute_set;

        concept()
            : m_objs()
            , m_atts()
        { }

        concept(const concept& x)
            : m_objs(x.m_objs)
            , m_atts(x.m_atts)
        { }

        concept(const object_set& objs, const attribute_set& atts)
            : m_objs(objs)
            , m_atts(atts)
        { }

        concept& operator =(const concept& x)
        {
            concept tmp(x);
            tmp.swap(*this);
            return *this;
        }

        // Return the set of objects in this concept.
        const object_set& objects() const
        { return m_objs; }

        // Return the set of attributes in this concept.
        const attribute_set& attributes() const
        { return m_atts; }

        // Swap this concept with another.
        void swap(concept& x)
        {
            m_objs.swap(x.m_objs);
            m_atts.swap(x.m_atts);
        }

    private:
        object_set      m_objs;
        attribute_set   m_atts;
    };

    template <typename Relation>
    bool operator ==(const concept<Relation>& l, const concept<Relation>& r)
    { return l.objects() == r.objects() && l.attributes() == r.attributes(); }

    template <typename Relation>
    bool operator !=(const concept<Relation>& l, const concept<Relation>& r)
    { return !(l == r); }

    template <typename Relation>
    bool operator <(const concept<Relation>& l, const concept<Relation>& r)
    {
        // Start by comparing the sets of objects. If the left set of objects is
        // either strictly greater or strictly less than the right, then we
        // can simply return that result. If the two sets are the same, we have
        // to delegate the comparison to the sets of attributes.
        //
        // Note that it is very unlikely that we'll ever see the attributes be
        // compared due to the definition of a concept. If two concepts have the
        // same set of objects, then they also have the same set of attributes.
        //
        // TODO: Find a way to get rid of the 3way compare. It's GCC-specific.
        // Does Boost have one?
        int comp = __gnu_cxx::lexicographical_compare_3way(
                begin(l.objects()), end(l.objects()),
                begin(r.objects()), end(r.objects()));
        if(comp < 0 ) return true;
        else if(comp > 0) return false;
        else return l.attributes() < r.attributes();
    }

    // Create a concept given a set of objects. This uses the given relation to
    // find attributes possessed in common by these objects, and then reduces
    // the input set to only those objects that share the given attributes.
    template <typename Relation, typename ObjIter>
    concept<Relation>
    make_concept_from_objects(const Relation& rel, ObjIter i, ObjIter iend)
    {
        typename Relation::attribute_set atts = rel.attributes(i, iend);
        typename Relation::object_set objs = rel.objects(begin(atts), end(atts));
        return concept<Relation>(objs, atts);
    }

    // Create a concept given a set of attributes. This uses the given relation
    // to find objects that share those attributes, and then turns around and
    // finds only those attributes shared by those objects.
    template <typename Relation, typename AttIter>
    concept<Relation>
    make_concept_from_attributes(const Relation& rel, AttIter i, AttIter iend)
    {
        typename Relation::object_set objs = rel.objects(i, iend);
        typename Relation::attribute_set atts = rel.attributes(begin(objs), end(objs));
        return concept<Relation>(objs, atts);
    }

    // Compute the least upper bound of a set of concepts. The result of this
    // operation is a concept that contains only objects and attributes shared
    // in common by the attributes of the given concepts.
    template <typename Relation, typename ConIter>
    concept<Relation>
    join(const Relation& rel, ConIter i, ConIter end)
    {
        typedef typename Relation::object_set object_set;
        typedef typename Relation::attribute_set attribute_set;

        // Starting with all attributes, compute the intersection of the
        // attributes of each concept in the given input.
        attribute_set atts = rel.context().attributes();
        for( ; i != end; ++i) {
            const attribute_set& x = i->attributes();
            intersection_inplace(atts, x);
        }

        return make_concept_from_attributes(atts);
    }

    // Compute the greatest lower bound of a set of concepts. The result of
    // this operation is a concept that contains only objects and attributes
    // shared in common by the objects of the given concepts.
    template <typename Relation, typename ConIter>
    concept<Relation>
    meet(const Relation& rel, ConIter i, ConIter end)
    {
        typedef typename Relation::object_set object_set;
        typedef typename Relation::attribute_set attribute_set;

        // Starting with all attributes, compute the intersection of the
        // attributes of each concept in the given input.
        object_set objs = rel.context().objects();
        for( ; i != end; ++i) {
            const object_set& x = i->objects();
            intersection_inplace(objs, x);
        }

        return make_concept_from_objects(objs);
    }

    template <typename Relation>
    std::ostream& operator <<(std::ostream& os, const concept<Relation>& con)
    {
        typedef typename Relation::object_type object_type;
        typedef typename Relation::attribute_type attribute_type;

        const typename Relation::object_set& objs = con.objects();
        const typename Relation::attribute_set& atts = con.attributes();
        std::cout << "objects { ";
        std::copy(begin(objs), end(objs),
                  std::ostream_iterator<object_type>(std::cout, " "));
        std::cout << "} attributes { ";
        std::copy(begin(atts), end(atts),
                  std::ostream_iterator<attribute_type>(std::cout, " "));
        std::cout << "}";
        return os;
    }

} /* namespace fca */
} /* namespace boost */

#endif