Program Listing for File SetIntersector.hpp¶

/*
 * SetIntersector.hpp
 *
 *  Created on: 14.05.2014
 *      Author: Henning
 */

#ifndef NETWORKIT_AUXILIARY_SET_INTERSECTOR_HPP_
#define NETWORKIT_AUXILIARY_SET_INTERSECTOR_HPP_

#include <cstdint>
#include <set>
#include <vector>

namespace Aux {

template <class T>
class SetIntersector {
public:
    SetIntersector(T upperBound);

    std::set<T> intersect(const std::vector<T> &A, const std::vector<T> &B);

private:
    std::vector<bool> bv;
    uint64_t n;
};

} // namespace Aux

template <class T>
inline Aux::SetIntersector<T>::SetIntersector(T upperBound) : n(upperBound) {
    bv.resize(n, false);
}

template <class T>
inline std::set<T> Aux::SetIntersector<T>::intersect(const std::vector<T> &A,
                                                     const std::vector<T> &B) {
    const std::vector<T> &smaller = (A.size() <= B.size()) ? A : B;
    const std::vector<T> &larger = (A.size() <= B.size()) ? B : A;

    for (auto entry : smaller) {
        bv[entry] = true;
    }

    std::set<T> result;
    for (auto entry : larger) {
        if (bv[entry]) {
            result.insert(entry);
        }
    }

    for (auto entry : smaller) {
        bv[entry] = false;
    }

    return result;
}

#endif // NETWORKIT_AUXILIARY_SET_INTERSECTOR_HPP_