SubsetEnumerator.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/ArrayBuffer.h>
#include <ogdf/basic/basic.h>
 
#include <algorithm>
#include <functional>
#include <ostream>
#include <string>
 
namespace ogdf {
template<class E>
class List;
 
 
template<typename T>
class SubsetEnumerator {
protected:
    bool m_valid;
    int m_maxCard;
    ArrayBuffer<T> m_subset;
    Array<int> m_index;
 
    void initSubset(int card) {
        if (card >= 0 && card <= m_subset.size()) {
            m_index.init(card);
            for (int i = 0; i < card; ++i) {
                m_index[i] = i;
            }
            m_valid = true;
        }
    }
 
public:
    template<typename ContainerType>
    explicit SubsetEnumerator(const ContainerType& set)
        : m_valid(false), m_maxCard(-1), m_subset(set.size()) {
        for (auto x : set) {
            m_subset.push(x);
        }
    }
 
    void begin(int low, int high) {
        if (high >= low) {
            m_maxCard = high;
            m_maxCard = min(m_maxCard, m_subset.size());
            initSubset(low);
        } else {
            m_valid = false;
        }
    }
 
    void begin(int card) { begin(card, card); }
 
    void begin() { begin(0, m_subset.size()); }
 
    int size() const { return m_index.size(); }
 
    int numberOfMembersAndNonmembers() const { return m_subset.size(); }
 
    bool valid() const { return m_valid; }
 
    bool hasMember(const T& element) const {
        for (int index : m_index) {
            if (element == m_subset[index]) {
                return true;
            }
        }
        return false;
    }
 
    T operator[](int i) const {
        OGDF_ASSERT(i >= 0);
        OGDF_ASSERT(i < m_index.size());
        return m_subset[m_index[i]];
    }
 
    void next() {
        if (m_valid) {
            const int t = m_index.size();
            if (t == 0) { // last (empty) subset has been found
                if (t < m_maxCard) {
                    initSubset(t + 1);
                } else {
                    m_valid = false;
                }
                return;
            }
            const int n = m_subset.size();
            int i;
            for (i = t - 1; m_index[i] == i + n - t; --i) {
                if (i == 0) { // the last subset of this cardinality has been found
                    if (t < m_maxCard) {
                        initSubset(t + 1);
                    } else {
                        m_valid = false;
                    }
                    return;
                }
            }
            for (++m_index[i]; i < t - 1; ++i) {
                m_index[i + 1] = m_index[i] + 1;
            }
        }
    }
 
    void forEachMember(std::function<void(const T&)> func) const {
        for (int index : m_index) {
            func(m_subset[index]);
        }
    }
 
    void list(List<T>& subset) const {
        forEachMember([&](const T& member) { subset.pushBack(member); });
    }
 
    void array(Array<T>& array) const {
        array.init(m_index.size());
        for (int i = 0; i < m_index.size(); ++i) {
            array[i] = m_subset[m_index[i]];
        }
    }
 
    void forEachMemberAndNonmember(std::function<void(const T&)> funcIn,
            std::function<void(const T&)> funcNotIn) const {
        for (int i = 0, j = 0; i < m_subset.size(); ++i) {
            if (j < m_index.size() && m_index[j] == i) {
                funcIn(m_subset[i]);
                ++j;
            } else {
                funcNotIn(m_subset[i]);
            }
        }
    }
 
    template<typename ContainerType>
    void getSubsetAndComplement(ContainerType& subset, ContainerType& complement,
            std::function<void(ContainerType&, T)> func) const {
        forEachMemberAndNonmember([&](const T& member) { func(subset, member); },
                [&](const T& nonmember) { func(complement, nonmember); });
    }
 
    void list(List<T>& subset, List<T>& complement) const {
        getSubsetAndComplement<List<T>>(subset, complement,
                [](List<T>& lc, T element) { lc.pushBack(element); });
    }
 
    bool testForAll(std::function<bool(const T&)> predicate) const {
        for (int index : m_index) {
            if (!predicate(m_subset[index])) {
                return false;
            }
        }
        return true;
    }
 
    void print(std::ostream& os, string delim = " ") const {
        if (valid()) {
            if (size() > 0) {
                os << m_subset[m_index[0]];
                for (int i = 1; i < size(); ++i) {
                    os << delim << m_subset[m_index[i]];
                }
            }
        } else {
            os << "<<invalid subset>>";
        }
    }
};
 
template<class T>
std::ostream& operator<<(std::ostream& os, const SubsetEnumerator<T>& subset) {
    subset.print(os);
    return os;
}
 
}