Combination.h

//-----------------------------------------------------------------------------
//
// Module:       Combination.h
//
// Author:       Feng Xie -- xief@mcmaster.ca
//
// Discription:  Combination generator.
//
// Note:         Index starts from 0.
//
// Todo:         1) Combination of more than sizeof(long) elements.
//               2) k-combination.
//
// Change log:
//   09-06-03    Created.
//
//-----------------------------------------------------------------------------

#ifndef OMC_COMBINATION_H
#define OMC_COMBINATION_H

#include "Core.h"
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

namespace omc
{
  class Combination
  {
    friend std::ostream & operator<< (std::ostream &, const Combination &);

  public:
    Combination (size_t);                 // constructors
    Combination (const std::string &);

    //std::set<index_t> & operator() (std::set<index_t> &) const;  // combination

    size_t size () const;                 // number of elements

    bool next ();                         // generate the next combination

    bool has (index_t) const;             // test if an element is in the combination

    bool operator== (const Combination &) const; // operator ==

    void add (index_t);                   // add an element into the combination

  protected:
    size_t m_numElements;                 // number of elements

    unsigned long m_Bit;                  // internal representation: bitset
  };

  // Output stream overloading.
  std::ostream & operator<< (std::ostream &, const Combination &);


  inline Combination::Combination (size_t n)
    : m_numElements (n), m_Bit (0)
  {}

  inline Combination::Combination (const std::string & s)
    : m_numElements (s.size()), m_Bit (0)
  {
    for (int i=0; i<m_numElements; i++) 
      if (s[i] == '1')
        m_Bit += (1<<i);
  }

  /*
  inline std::set<index_t> & 
  Combination::operator() (std::set<index_t> & Comb) const {
    Comb.clear ();

    for (index_t i=0; i<m_numElements; i++) 
      if (has (i)) Comb.insert (i);
    
    return Comb;
    } */

  inline size_t Combination::size () const {
    return m_numElements;
  }

  inline bool Combination::next () {
    if (m_Bit == (unsigned long) (1 << m_numElements) - 1)
      return false;
    else {
      m_Bit++;
      return true;
    }
  }

  inline bool Combination::has (index_t i) const {
    return (m_Bit & (1<<i));
  }

  inline bool Combination::operator== (const Combination & comb) const {
    return m_numElements == comb.m_numElements && m_Bit == comb.m_Bit;
  }

  inline void Combination::add (index_t i) {
    m_Bit |= (1<<i);
  }

 
  inline std::ostream & operator<< (std::ostream & os, 
                                    const Combination & comb) 
  {
    bool first = true;

    os << "{";
    for (index_t i=0; i<comb.m_numElements; i++)
      if (comb.has (i)) {
        if (!first) os << ",";
        else first = false;
        os << i;
      }
    os << "}";
    return os;
  }

} // namespace omc

#endif // OMC_COMBINATION_H

---