source: src/Fragmentation/Summation/SubsetMap.hpp@ 3102010

/*
 * SubsetMap.hpp
 *
 *  Created on: Jul 3, 2012
 *      Author: heber
 */

#ifndef SUBSETMAP_HPP_
#define SUBSETMAP_HPP_


// include config.h
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <boost/shared_ptr.hpp>
#include <map>

#include "CodePatterns/Assert.hpp"

#include "IndexSetContainer.hpp"

class SubsetMapTest;

/** A SubsetMap is a map containing shared_ptr of IndexSet instances that knows
 * about which set is contained in which for fast lookup for SubsetValues.
 */
class SubsetMap
{
  //!> grant unit test access
  friend class SubsetMapTest;
public:
  //!> typedef for wrapping an instance in a shared_ptr
  typedef boost::shared_ptr<SubsetMap> ptr;

  /** Constructor for SubsetMap that creates the internal map from IndexSet to a
   * container with all contained sets.
   *
   * To this end, we first put each IndexSet in a multimap from size to IndexSet.
   * Then we go "level-wise" from low to high through this map and use gatherSubsets()
   * on each set as we are then sure that all contained subsets have already been
   * initialized.
   *
   * @param _container container with IndexSet
   */
  SubsetMap(IndexSetContainer &_container);

  /** Getter for all subsets of set \a ptr.
   *
   * @param ptr IndexSet
   * @return IndexSetContainer with all contained sets
   */
  IndexSetContainer::ptr & getSubsets(const IndexSet_ptr &ptr) {
    Lookup_t::iterator lookupiter = Lookup.find(ptr);
    ASSERT(lookupiter != Lookup.end(),
        "SubsetMap::getSubsets() - the set "+toString(*ptr)+" is not in the Lookup.");
    return lookupiter->second;
  }

  /** Returns the size of the largest \b sub set.
   *
   * This would be \f${\cal O}(n)\f$ if we had to look at each set. However, due
   * to the specific sorting we just have to check the last sets.
   *
   * @return number of indices in largest subset, -1 if SubsetMap contains no IndexSet's
   */
  size_t getMaximumSubsetLevel() const;

  /** Returns the size of the largest set.
   *
   * @return number of indices in largest set
   */
  size_t getMaximumSetLevel() const;

private:
  /** Private function to fill the internal Lookup for a given IndexSet \a ptr.
   *
   * @param ptr IndexSet
   */
  void gatherSubsets(const IndexSet_ptr &ptr);

  /** Returns the index of \a subset in the power subsets of \a ptr.
   *
   * @param ptr set to check
   * @param subset subset whose lexicographical position to find in \a ptr
   * @return index of this subset
   */
  static const size_t getPowerSetIndex(const IndexSet_ptr &ptr, const IndexSet &subset);

  /** Returns the number of power subsets for a given set size.
   *
   * @param SetSize size of the set
   * @return possible number of true subsets
   */
  static size_t getNoPowerSets(const size_t SetSize) {
    return (1 << SetSize);
  }

  /** Returns the subset for a given \a _set by its power set index \a PowerSetNo.
   *
   * The idea is that each bit in \a PowerSetNo encodes whether the Index at the
   * position in the set is to appear in the subset or not. Hence, we use std::bitset
   * to construct the bit representation from \a PowerSetNo and then go through each
   * bit and either insert into the subset or not.
   *
   * @param _set index set
   * @param PowerSetNo subset index
   * @return specific power set subset given by the index
   */
  static IndexSet getSubset(const IndexSet &_set, size_t PowerSetNo);

private:
  //!> enumeration of states whether a subset is contained or not
  enum ContainedState {
    NotContained = 0,
    Contained = 1,
  };

  //!> temporary IndexSet_ptr
  IndexSet_ptr tempset;
  //!> enumeration trick to define a maximum subset size
  enum {MAX_SETSIZE = 32};
  //!> typedef for the specific map from IndexSet to all contained IndexSets
  typedef std::map< IndexSet_ptr, IndexSetContainer::ptr,
      IndexSetContainer::Comparator_t> Lookup_t;
  Lookup_t Lookup;
};

#endif /* SUBSETMAP_HPP_ */