// (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_CONTEXT_HPP #define BOOST_FCA_BITSET_CONTEXT_HPP #include #include #include namespace boost { namespace fca { // The bitset context provides a high-performance set type (and associated // relation) using bitsets rather than the typical std::set. The reason that // this is a higher performance set implementation is twofold. First, set // intersections on bitsets are simply binary and operations. Second, copies // are extremely cheap since we're just talking about a sequence of bits // rather than distinct objects. // // The drawback to using a bitset context is added cost mapping from user // defined objects to the "objects" employed by the bitset, which are really // just indices into the bitset. As such, the context is responsible for // providing a set of functions that maps the original object and attribute // types to indices and vice-versa. // // Note that the object and attribute type must be copy constructible and // less-than comparable since they're being used as keys to a map. template class bitset_context { public: typedef ObjectType mapped_object_type; typedef std::size_t object_type; typedef dynamic_bitset<> object_set; typedef AttributeType mapped_attribute_type; typedef std::size_t attribute_type; typedef dynamic_bitset<> attribute_set; private: // Associate mapped objects and attributes with their indices typedef std::map object_map; typedef std::map attribute_map; // Given an index, return the mapped object or attribute typedef std::vector object_index; typedef std::vector attribute_index; public: // Default constructor. Use this with care since the only real way // to get data into this object is to assign over it. bitset_context() : m_objs() , m_mapped_objs() , m_indexed_objs() , m_atts() , m_mapped_atts() , m_indexed_atts() { } // Copy constructor bitset_context(const bitset_context& x) : m_objs(x.m_objs) , m_mapped_objs(x.m_mapped_objs) , m_indexed_objs(x.m_indexed_objs) , m_atts(x.m_atts) , m_mapped_atts(x.m_mapped_atts) , m_indexed_atts(x.m_indexed_atts) { } // Iterator constructor template bitset_context(ObjIter oi, ObjIter oend, AttIter ai, AttIter aend) : m_objs() , m_mapped_objs() , m_indexed_objs() , m_atts() , m_mapped_atts() , m_indexed_atts() { initialize(oi, oend, ai, aend); } // Container constructor (for convenience) template bitset_context(ObjectSet& o, AttributeSet& a) : m_objs() , m_mapped_objs() , m_indexed_objs() , m_atts() , m_mapped_atts() , m_indexed_atts() { initialize(o.begin(), o.end(), a.begin(), a.end()); } bitset_context& operator =(const bitset_context& x) { bitset_context tmp(x); tmp.swap(*this); return *this; } // Swap the object and attribute contents of this and the other object. void swap(bitset_context& x) { m_objs.swap(x.m_objs); m_mapped_objs.swap(x.m_mapped_objs); m_indexed_objs.swap(x.m_indexed_objs); m_atts.swap(x.m_atts); m_mapped_atts.swap(x.m_mapped_atts); m_indexed_atts.swap(x.m_indexed_atts); } // Return the number of objects. std::size_t num_objects() const { return m_objs.size(); } // Get the set of all objects. const object_set& objects() const { return m_objs; } // Given a mapped object, return the index. Note that the given object // must be in the context, otherwise, the return will be invalid. object_type object(const mapped_object_type& obj) const { object_type ret = m_objs.size(); typename object_map::const_iterator i = m_mapped_objs.find(obj); if(i != m_mapped_objs.end()) { ret = i->second; } return ret; } // Given an index, return the mapped object. const mapped_object_type& mapped_object(object_type obj) { return m_indexed_objs[obj]; } // Return the number of attributes. std::size_t num_attributes() const { return m_atts.size(); } // Get the set all attributes. const attribute_set& attributes() const { return m_atts; } // Given a mapped attribute, return the index. Note that the given // attribute must be in the context, otherwise, the return will be // invalid. attribute_type attribute(const mapped_attribute_type& att) const { attribute_type ret = m_objs.size(); typename attribute_map::const_iterator i = m_mapped_atts.find(att); if(i != m_mapped_atts.end()) { ret = i->second; } return ret; } // Given an index, return a mapped attribute. const mapped_attribute_type& mapped_attribute(attribute_type att) { return m_indexed_atts[att]; } private: template void initialize(ObjIter oi, ObjIter oend, AttIter ai, AttIter aend) { size_t nobjs = std::distance(oi, oend); size_t natts = std::distance(ai, aend); size_t x; // Make sure that the indices are the right size... m_indexed_objs.resize(nobjs); m_indexed_atts.resize(natts); // Iterate over the set of objects and populate the object map // and object index. Also, count the number of objects. for(x = 0; oi != oend; ++oi, ++x) { m_mapped_objs[*oi] = x; m_indexed_objs[x] = *oi; } // Do the same for attributes. for(x = 0; ai != aend; ++ai, ++x) { m_mapped_atts[*ai] = x; m_indexed_atts[x] = *ai; } // Resize the object and attribute sets to the computed size and // fill them (all 1's). m_objs.resize(nobjs, true); m_atts.resize(natts, true); } private: object_set m_objs; object_map m_mapped_objs; object_index m_indexed_objs; attribute_set m_atts; attribute_map m_mapped_atts; attribute_index m_indexed_atts; }; } /* namespace fca */ } /* namespace boost */ #include #endif