// (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_SET_RELATION_HPP
#define BOOST_FCA_SET_RELATION_HPP

#include <map>

#include <boost/sets.hpp>

namespace boost {
namespace fca {

    // A relation is basically a bidirectional mapping of objects to attributes
    // and vice-versa. The primary interface used in the FCA algorithms returns
    // a set of objects or attributes corresponding to a selection of the
    // opposite.

    namespace detail
    {
        // A helper function that abstracts the insertion of keys into
        // a map. This works for both object and attribute maps.
        template <typename Set, typename Key, typename Value, typename Map>
        void insert(const Key& k, const Value& v, Map& map)
        {
            std::pair<typename Map::iterator, bool> p =
                    map.insert(std::make_pair(k, Set()));
            p.first->second.insert(v);
        }

        // Return the object or attribute set associated with a key, and given.
        // a map
        template <typename Set, typename Key, typename Map>
        Set get(const Key& k, const Map& map)
        {
            Set ret;
            typename Map::const_iterator i = map.find(k);
            if(i != map.end()) {
                ret = i->second;
            }
            return ret;
        }
    }

    // The generic relation type uses maps (dictionaries) to associate an
    // object with a set of attributes, or an attribute with a set of objects.
    // The definition of the set type and object type is taken from context
    // over which the relation is built.
    template <typename Context>
    class relation
    {
    public:
        typedef Context context_type;

        typedef typename Context::object_type object_type;
        typedef typename Context::object_set object_set;

        typedef typename Context::attribute_type attribute_type;
        typedef typename Context::attribute_set attribute_set;

        typedef std::map<object_type, attribute_set> object_map;
        typedef std::map<attribute_type, object_set> attribute_map;

        // Default constructor. Be very careful using this since it MUST be
        // assigned from another context before use. Otherwise, there's no way
        // to reseat the context.
        relation()
            : m_cxt(0)
            , m_objs()
            , m_atts()
        { }

        relation(const relation& rel)
            : m_cxt(rel.m_cxt)
            , m_objs(rel.m_objs)
            , m_atts(rel.m_atts)
        { }

        // Construct a relation over the given context.
        relation(const context_type& cxt)
            : m_cxt(&cxt)
            , m_objs()
            , m_atts()
        { }

        // Construct a relation over the given context and initialize it with
        // a sequence of pairs, which determines the contents of the relation.
        template <typename RelIter>
        relation(const context_type& cxt, RelIter i, RelIter end)
            : m_cxt(&cxt)
            , m_objs()
            , m_atts()
        {
            for( ; i != end; ++i) {
                set(i->first, i->second);
            }
        }

        // Construct a relation over the given context and initialize it with
        // a sequence of pairs. Like above, but this is meant to take an entire
        // sequence rather than simply the iterators.
        template <typename RelSet>
        relation(const context_type& cxt, const RelSet& r)
            : m_cxt(&cxt)
            , m_objs()
            , m_atts()
        {
            typename RelSet::const_iterator i = r.begin(), end = r.end();
            for( ; i != end; ++i) {
                set(i->first, i->second);
            }
        }

        // Get the context over which the relation is built.
        const context_type& context() const
        { return *m_cxt; }


        // Associate the object with the attribute and conversely the attribute
        // with the object. The object and attribute must be in the context.
        void set(const object_type& obj, const attribute_type& att)
        {
            detail::insert<attribute_set>(obj, att, m_objs);
            detail::insert<object_set>(att, obj, m_atts);
        }

        // Determine if the the given object contains the given attribute. Note
        // that this will work for an arbitrary object or attribute in the
        // context.
        bool test(const object_type& obj, const attribute_type& att) const
        {
            bool ret = false;
            typename object_map::const_iterator i = m_objs.find(obj);
            if(i != m_objs.end()) {
                ret = i->second.find(att) != i->second.end();
            }
            return ret;
        }


        // Return an empty set of attributes.
        attribute_set empty_attributes() const
        { return attribute_set(); }

        // Return a set of all attributes in the relation.
        const attribute_set& attributes() const
        { return m_cxt->attributes(); }

        // Return the set attribtes associated with the given object. Note that
        // this copies the set.
        attribute_set attributes(const object_type& obj) const
        { return detail::get<attribute_set>(obj, m_objs); }

        // Return the set of attributes shared by the given objects. Note that
        // if given an empty range of objects, this will return all attributes.
        template <typename ObjIter>
        attribute_set attributes(ObjIter i, ObjIter end) const
        {
            // Initially set the resulting set to all objects. The result set
            // is intersected with the attributes of each object. The final
            // set will contain only those attributes shared by each object.
            attribute_set ret = attributes();
            for( ; i != end; ++i) {
                attribute_set atts = attributes(*i);
                sets::intersection_inplace(ret, atts);
            }

            return ret;
        }

        // Return an empty set of objects.
        object_set empty_objects() const
        { return object_set(); }

        // Return all objects in the relation.
        const object_set& objects() const
        { return m_cxt->objects(); }

        // Get the set of objects that share the given attribute. Note that this
        // operation copies the resulting set.
        object_set objects(const attribute_type& att) const
        { return detail::get<object_set>(att, m_atts); }

        // Return the set of objects that possess the given set of attributes.
        // Note that if given an empty range of attributes, this will return
        // all objects.
        template <typename AttIter>
        object_set objects(AttIter i, AttIter end) const
        {
            // Initially set the resulting to all objects, and narrow it by
            // intersecting with individual queries.
            object_set ret = objects();
            for( ; i != end; ++i) {
                object_set objs = objects(*i);
                sets::intersection_inplace(ret, objs);
            }
            return ret;
        }

    private:
        const context_type* m_cxt;  // The context
        object_map          m_objs; // Maps objects to attributes
        attribute_map       m_atts; // Maps attributes to objects
    };

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

#endif