// (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_BITSET_RELATION_HPP
#define BOOST_FCA_BITSET_RELATION_HPP

#include <map>
#include <boost/sets.hpp>
#include <boost/fca/set_relation.hpp>

namespace boost {
namespace fca {

    // This is a specialization of the relation type to work with bitset
    // contexts. Specifically, this provides a couple of overloads for the
    // set and test functions that map from the original object types to the
    // indices used by the implementation.
    //
    // Note that this may be problematic if either the object type or attribute
    // type is size_t. We can end up with ambiguous overloads.
    //
    // This class is nearly identical to the generic version except that it
    // provides a couple of extra functions for mapping between the mapped
    // obejct types and the indices of the bitsets. It also redefines how the
    // sets are associated with objects and attributes (vectors, not maps).
    template <typename ObjectType, typename AttributeType>
    class relation< bitset_context<ObjectType, AttributeType> >
    {
    public:
        typedef bitset_context<ObjectType, AttributeType> context_type;

        typedef typename context_type::object_type object_type;
        typedef typename context_type::object_set object_set;
        typedef ObjectType mapped_object_type;

        typedef typename context_type::attribute_type attribute_type;
        typedef typename context_type::attribute_set attribute_set;
        typedef AttributeType mapped_attribute_type;

        typedef std::vector<object_set> object_map;
        typedef std::vector<attribute_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(cxt.num_objects(), object_set(cxt.num_attributes()))
            , m_atts(cxt.num_attributes(), attribute_set(cxt.num_objects()))
        { }

        // Construct a relation over the given context and initialize it with
        // a sequence of pairs, which determines the contents of the relation.
        // Note that *i must be a pair of either indices or mapped object types.
        template <typename RelIter>
        relation(const context_type& cxt, RelIter i, RelIter end)
            : m_cxt(&cxt)
            , m_objs(cxt.num_objects(), object_set(cxt.num_attributes()))
            , m_atts(cxt.num_attributes(), attribute_set(cxt.num_objects()))
        {
            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(object_type obj, attribute_type att)
        {
            m_objs[obj].set(att);
            m_atts[att].set(obj);
        }

        // Associate the the object with the attribute and vice versa. Note that
        // this overload requires a lookup to map from object to index.
        void set(const mapped_object_type& obj, const mapped_attribute_type& att)
        {
            object_type oi = m_cxt->object(obj);
            attribute_type ai = m_cxt->attribute(att);
            set(oi, ai);
        }


        // 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(object_type obj, attribute_type att) const
        { return m_objs[obj].test(att); }

        // Like above, but requires a lookup to find the right indices.
        bool test(const mapped_object_type& obj, const mapped_attribute_type& att) const
        {
            object_type oi = m_cxt->object(obj);
            attribute_type ai = m_cxt->attribute(att);
            return test(oi, ai);
        }

        // Return an empty set of attributes. This is a bitset with all bits
        // set to false.
        attribute_set empty_attributes() const
        { return attribute_set(m_atts.size(), false); }

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

        // Return the set attributes associated with the given object. Note that
        // this copies the set.
        attribute_set attributes(object_type obj) const
        { return m_objs[obj]; }

        // Like above, but perform a lookup on the mapped object type.
        attribute_set attributes(const mapped_object_type& obj) const
        { return m_objs[m_cxt->object(obj)]; }

        // 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
        {
            // Starting with all attributes, progressively intersect each object
            // the result with the attributes posessed by each of the objects.
            attribute_set ret = attributes();
            for( ; i != end; ++i) {
                ret &= attributes(*i);
            }

            return ret;
        }

        // Return an empty set of objects. This is a bitset all bits set to
        // false.
        object_set empty_objects() const
        { return object_set(m_objs.size(), false); }

        // 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(attribute_type att) const
        { return m_atts[att]; }

        // Like above but perform a lookup on the mapeed attribute type.
        object_set objects(const mapped_attribute_type& att) const
        { return m_atts[m_cxt->attribute(att)]; }

        // 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) {
                ret &= objects(*i);
            }
            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