// (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_LATTICE_HPP
#define BOOST_FCA_LATTICE_HPP

#include <map>

#include <boost/graph/adjacency_list.hpp>
#include <boost/sets.hpp>
#include <boost/fca/concept.hpp>

namespace boost {
namespace fca {

    namespace detail
    {
        template <typename Set, typename Value>
        bool is_lower(const Set& null, const Set& cand, const Set& min, const Value& x)
        {
            // This is a little weird, but I'm creating a temporary set with
            // one element so I can compare with it below.
            Set tmp = null;
            sets::add(tmp, x);

            // Compute the intersection of the candidate and minimal sets.
            Set inter = sets::intersection(cand, min);

            // The candidate is less than the minimal set if they are disjoint
            // or they intersect on the given element.
            return sets::empty(inter) || inter == tmp;
        }
    }

    // A lattice (given a relation) is a structure that contains related formal
    // concepts. Lattices are generated as the result of formal concept
    // analysis.
    template <typename Relation>
    class lattice
    {
        typedef lattice<Relation> this_type;

    public:
        typedef Relation relation_type;
        typedef concept<Relation> concept_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;

        // This type is used to store information about vertices in the lattice.
        // Specifically, this stores pointers to concepts. Each vertex in the
        // lattice actually points at a concept in the concept map.
        struct vertex_property
        {
            concept_type* value;
        };

        typedef boost::adjacency_list<
                boost::vecS,
                boost::vecS,
                boost::bidirectionalS,
                vertex_property
            > graph_type;
        typedef typename boost::graph_traits<graph_type>::vertex_descriptor vertex_type;
        typedef typename boost::graph_traits<graph_type>::edge_descriptor edge_type;

        typedef std::map<concept_type, vertex_type> concept_map;
        typedef std::set< std::pair<vertex_type, vertex_type> > edge_set;
    public:

        // Construct the lattice over the given relation, but do not actually
        // build it (fill it with inter-connected concepts).
        lattice(const relation_type& rel)
            : m_rel(rel)
            , m_lattice()
            , m_top(0)
            , m_bottom(0)
            , m_concepts()
            , m_edges()
        { initialize(); }

        // Copy constructor.
        lattice(const lattice& x)
            : m_rel(x.m_rel)
            , m_lattice(x.m_lattice)
            , m_top(x.m_top)
            , m_concepts(x.m_concepts)
            , m_edges(x.m_edges)
        { }

        // Construct the lattice over the relation and build it. If top is true,
        // start at the top.
        lattice(const relation_type& rel, bool top)
            : m_rel(rel)
            , m_lattice()
            , m_top(0)
            , m_bottom(0)
            , m_concepts()
            , m_edges()
        {
            initialize();
            if(top) {
                build_top_down();
            }
            else {
                build_bottom_up();
            }
        }

        // Return the top concept in the lattice.
        const concept_type& top_concept() const
        { return *m_lattice[m_top].value; }

        // Return the bottom concept in the lattice.
        const concept_type& bottom_concept() const
        { return *m_lattice[m_bottom].value; }

        // Get the concept corresponding to the given vertex.
        const concept_type& get_concept(vertex_type v) const
        { return *m_lattice[v].value; }


        // Get the underlying graph
        const graph_type& graph() const
        { return m_lattice; }

        // Get the top vertex in the lattice.
        vertex_type top_vertex() const
        { return m_top; }

        // Get the bottom vertex in the lattice.
        vertex_type bottom_vertex() const
        { return m_bottom; }


        // Build the lattice from the relation starting with the top concept,
        // and recursing towards the bottom.
        void build_top_down()
        { lower_neighbors(top_concept(), m_top); }

        // Build the lattice from the relation starting with the bottom concept
        // and recursing towards the top.
        void build_bottom_up()
        { upper_neighbors(bottom_concept(), m_bottom); }

    private:
        // Compute the set of neighbors of the given concept. The lower
        // neigbbors of a concept are those that... I don't know how to explain
        // this...
        //
        // Note that the given concept must already exist within the lattice.
        void lower_neighbors(const concept_type& con, vertex_type upper)
        {
            typedef typename concept_map::iterator concept_iterator;
            typedef std::pair<concept_iterator, bool> concept_result;
            typedef typename edge_set::iterator edges_iterator;
            typedef std::pair<edges_iterator, bool> edges_result;

            // Starting with all attributes, compute a set that contains only
            // those attributes that are not in the concept. This operation
            // is basically min = all \ catts (in set notation).
            const attribute_set& all_atts = m_rel.attributes();
            const attribute_set& con_atts = con.attributes();
            attribute_set min = sets::difference(all_atts, con_atts);
            attribute_set empty = m_rel.empty_attributes();

            // Iterate over ever attribute not in the set of all attributes.
            // Note that the Colibri/Java code iterates over all attributes and
            // tests for inclusion in the concept. Weird.
            typename range_iterator<attribute_set>::type i, iend = end(min);
            for(i = begin(min); i != iend; ++i) {
                const attribute_type& att = *i;

                // Compute a candidate concept and determine if this is a lower
                // neighbor. It is a lower neighbor under the condition that
                // a) the candidate attributes are disjoint with the min set
                // OR b) the intersection contains only the current attribute.
                concept_type cand = make_lower_candidate(con, att);
                if(detail::is_lower(empty, cand.attributes(), min, att)) {
                    // Add this concept to the lattice (maybe) and get a
                    // reference to the added (or existing concept).
                    concept_result result = add_concept(cand);
                    const concept_type& actual = result.first->first;

                    // Using the returned vertex, connect this candidate to
                    // its upper context. Note that edges flow from lower to
                    // upper.
                    vertex_type lower = result.first->second;
                    edges_result er = m_edges.insert(make_pair(lower, upper));
                    if(er.second) {
                        add_edge(lower, upper, m_lattice);
                    }

                    // If the insertion succeeds, we need to recurse. Note that
                    // if it didn't succeed, we've already computed the lower
                    // neighbors of it.
                    if(result.second) {
                        // The insertion succeeded, so we know that we have a
                        // new concept to work with. We should recurse.
                        lower_neighbors(actual, lower);
                    }
                }
                else {
                    // Otherwise, remove the attribute from the minimal set so
                    // we don't consider it again.
                    // min.erase(i);
                    sets::remove(min, i);
                }
            }
        }

        void upper_neighbors(const concept_type& con, vertex_type lower)
        {
            typedef typename concept_map::iterator concept_iterator;
            typedef std::pair<concept_iterator, bool> concept_result;
            typedef typename edge_set::iterator edges_iterator;
            typedef std::pair<edges_iterator, bool> edges_result;

            // Starting with all objects, compute a set that contains only
            // those objects that are not in the concept. This operation
            // is basically min = all \ objs (in set notation).
            const object_set& all = m_rel.objects();
            const object_set& objs = con.objects();
            object_set min = sets::difference(all, objs);
            object_set empty = m_rel.empty_objects();

            // Iterate over ever attribute not in the set of all objects.
            // Note that the Colibri/Java code iterates over all objects and
            // tests for inclusion in the concept. Weird.
            typename range_iterator<object_set>::type i, iend = end(min);
            for(i = begin(min); i != iend; ++i) {
                const object_type& obj = *i;

                // Compute a candidate concept and determine if this is a lower
                // neighbor. It is a lower neighbor under the condition that
                // a) the candidate objects are disjoint with the min set
                // OR b) the intersection contains only the current object.
                concept_type cand = make_upper_candidate(con, obj);
                if(detail::is_lower(empty, cand.objects(), min, obj)) {
                    // Add this concept to the lattice (maybe) and get the
                    // added concept.
                    concept_result result = add_concept(cand);
                    const concept_type& actual = result.first->first;

                    // Using the returned vertex, connect this candidate to
                    // its upper context. Note that edges flow from lower to
                    // upper.
                    vertex_type upper = result.first->second;
                    edges_result er = m_edges.insert(make_pair(lower, upper));
                    if(er.second) {
                        add_edge(lower, upper, m_lattice);
                    }

                    // If the insertion succeeds, we need to recurse. Note that
                    // if it didn't succeed, we've already computed the lower
                    // neighbors of it.
                    if(result.second) {
                        // The insertion succeeded, so we know that we have a
                        // new concept to work with. We should recurse.
                        upper_neighbors(actual, upper);
                    }
                }
                else {
                    // Otherwise, remove the object from the minimal set so
                    // we don't consider it again.
                    sets::remove(min, i);
                }
            }
        }

        std::pair<typename concept_map::iterator, bool>
        add_concept(const concept_type& con)
        {
            // Try to insert the concept into the map.
            std::pair<typename concept_map::iterator, bool> p =
                    m_concepts.insert(std::make_pair(con, vertex_type()));
            if(p.second) {
                // Create a vertex that models this concept and associate the
                // _newly added concept_ (not the old one!) with the vertex.
                // I'm not sure why this is returning a const pointer... It's
                // kind of annoying.
                vertex_type v = add_vertex(m_lattice);
                m_lattice[v].value = const_cast<concept_type*>(&p.first->first);

                // Also, make sure that this concept is associated with the
                // the vertex (for fast lookup later).
                p.first->second = v;
            }
            else {
                // I don't think we need to do anything in this case...
            }

            return p;
        }

        void initialize()
        {
            // Compute the top concept, which starts from an empty set
            // of attributes, and swap it to the top concept.
            attribute_set atts = m_rel.empty_attributes();
            concept_type top =
                    make_concept_from_attributes(m_rel, begin(atts), end(atts));
            m_top = add_concept(top).first->second;

            // Compute the bottom concept, which starts with an empty set of
            // objects, and swap it to the bottom concept.
            object_set objs = m_rel.empty_objects();
            concept_type bot =
                    make_concept_from_objects(m_rel, begin(objs), end(objs));
            m_bottom = add_concept(bot).first->second;
        }

        concept_type
        make_lower_candidate(const concept_type& con, const attribute_type& att)
        {
            // Get the all the objects that possess this attribute and intersect
            // that with the objects in the given concept.
            concept_type ret;
            object_set objs = sets::intersection(m_rel.objects(att), con.objects());
            if(objs.empty()) {
                ret = bottom_concept();
            }
            else {
                attribute_set atts = m_rel.attributes(begin(objs), end(objs));
                ret = concept_type(objs, atts);
            }
            return ret;
        }

        concept_type
        make_upper_candidate(const concept_type& con, const object_type& obj)
        {
            // Get the all the objects that possess this attribute and intersect
            // that with the objects in the given concept.
            concept_type ret;
            attribute_set atts = sets::intersection(m_rel.attributes(obj), con.attributes());
            if(atts.empty()) {
                ret = top_concept();
            }
            else {
                object_set objs = m_rel.objects(begin(atts), end(atts));
                ret = concept_type(objs, atts);
            }
            return ret;
        }

    private:
        const relation_type&    m_rel;
        graph_type              m_lattice;
        vertex_type             m_top;
        vertex_type             m_bottom;
        concept_map             m_concepts;

        // TODO: This member shouldn't be here. It's only used to transimit
        // information between successive calls to the lower/upper neighbor
        // functions. Refector this out into a parameter.
        edge_set                m_edges;
    };

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

#endif