source: src/Common/FilterCombos.h @ b9e2b87

//
// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// FilterCombos.h --
//
// Author           : Aaron B. Moss
// Created On       : Mon Jul 23 16:05:00 2018
// Last Modified By : Aaron B. Moss
// Last Modified On : Mon Jul 23 16:05:00 2018
// Update Count     : 1
//

#pragma once

#include <vector>

/// Type of index vector for combinations
typedef std::vector<unsigned> Indices;

/// Combo iterator that simply collects values into a vector, marking all values as valid.
/// Prefer combos in typeops.h to use of IntoVectorComboIter with filterCombos
/// @param T    The element type of the vector.
template<typename T>
class IntoVectorComboIter {
        std::vector<T> crnt_combo;
public:
        /// Outputs a vector of T
        using OutType = std::vector<T>;

        /// Adds the element to the current combination, always returning true for valid.
        bool append( const T& x ) {
                crnt_combo.push_back( x );
                return true;
        }

        /// Removes the last element of the current combination.
        void backtrack() { crnt_combo.pop_back(); }

        /// Returns a copy of the current combination.
        OutType finalize() { return crnt_combo; }
};

/// Filters combinations from qs by the given combo iterator. If the iterator rejects some prefix 
/// of a combination, it will not accept any combination with that prefix.
/// qs should not be empty
template<typename Q, typename ComboIter>
auto filterCombos( const std::vector<Q>& qs, ComboIter&& iter )
                -> std::vector<typename ComboIter::OutType> {
    unsigned n = qs.size();  // number of queues to combine

        std::vector<typename ComboIter::OutType> out;  // filtered output
        for ( auto& q : qs ) if ( q.empty() ) return out;  // return empty if any empty queue

        Indices inds;
        inds.reserve( n );
        inds.push_back( 0 );

        while (true) {
                unsigned i = inds.size() - 1;

                // iterate or keep successful match
                if ( iter.append( qs[i][inds.back()] ) ) {
                        if ( i + 1 == n ) {
                                // keep successful match of entire combination and continue iterating final place
                                out.push_back( iter.finalize() );
                                iter.backtrack();
                        } else {
                                // try to extend successful prefix
                                inds.push_back( 0 );
                                continue;
                        }
                }

                // move to next combo
                ++inds.back();
                if ( inds.back() < qs[i].size() ) continue;
                
                // Otherwise done with the current row.
                // At this point, an invalid prefix is stored in inds and iter is in a state looking at 
                // all but the final value in inds. Now backtrack to next prefix:
                inds.pop_back();
                while ( ! inds.empty() ) {
                        // try the next value at the previous index
                        ++inds.back();
                        iter.backtrack();
                        if ( inds.back() < qs[inds.size()-1].size() ) break;
                        // if the previous index is finished, backtrack out
                        inds.pop_back();
                }

                // Done if backtracked the entire array
                if ( inds.empty() ) return out;
        }
}

// Local Variables: //
// tab-width: 4 //
// mode: c++ //
// compile-command: "make install" //
// End: //