source: src/Common/FilterCombos.h @ d6089ad

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since d6089ad was 6d6e829, checked in by Aaron Moss <a3moss@…>, 5 years ago

First compiling draft of deferred assertions (build failure)

  • Property mode set to 100644
File size: 3.0 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// FilterCombos.h --
8//
9// Author           : Aaron B. Moss
10// Created On       : Mon Jul 23 16:05:00 2018
11// Last Modified By : Aaron B. Moss
12// Last Modified On : Mon Jul 23 16:05:00 2018
13// Update Count     : 1
14//
15
16#pragma once
17
18#include <vector>
19
20/// Type of index vector for combinations
21typedef std::vector<unsigned> Indices;
22
23/// Combo iterator that simply collects values into a vector, marking all values as valid.
24/// Prefer combos in typeops.h to use of IntoVectorComboIter with filterCombos
25/// @param T    The element type of the vector.
26template<typename T>
27class IntoVectorComboIter {
28        std::vector<T> crnt_combo;
29public:
30        /// Outputs a vector of T
31        using OutType = std::vector<T>;
32
33        /// Adds the element to the current combination, always returning true for valid.
34        bool append( const T& x ) {
35                crnt_combo.push_back( x );
36                return true;
37        }
38
39        /// Removes the last element of the current combination.
40        void backtrack() { crnt_combo.pop_back(); }
41
42        /// Returns a copy of the current combination.
43        OutType finalize() { return crnt_combo; }
44};
45
46/// Filters combinations from qs by the given combo iterator. If the iterator rejects some prefix
47/// of a combination, it will not accept any combination with that prefix.
48/// qs should not be empty
49template<typename Q, typename ComboIter>
50auto filterCombos( const std::vector<Q>& qs, ComboIter&& iter )
51                -> std::vector<typename ComboIter::OutType> {
52    unsigned n = qs.size();  // number of queues to combine
53
54        std::vector<typename ComboIter::OutType> out;  // filtered output
55        for ( auto& q : qs ) if ( q.empty() ) return out;  // return empty if any empty queue
56
57        Indices inds;
58        inds.reserve( n );
59        inds.push_back( 0 );
60
61        while (true) {
62                unsigned i = inds.size() - 1;
63
64                // iterate or keep successful match
65                if ( iter.append( qs[i][inds.back()] ) ) {
66                        if ( i + 1 == n ) {
67                                // keep successful match of entire combination and continue iterating final place
68                                out.push_back( iter.finalize() );
69                                iter.backtrack();
70                        } else {
71                                // try to extend successful prefix
72                                inds.push_back( 0 );
73                                continue;
74                        }
75                }
76
77                // move to next combo
78                ++inds.back();
79                if ( inds.back() < qs[i].size() ) continue;
80               
81                // Otherwise done with the current row.
82                // At this point, an invalid prefix is stored in inds and iter is in a state looking at
83                // all but the final value in inds. Now backtrack to next prefix:
84                inds.pop_back();
85                while ( ! inds.empty() ) {
86                        // try the next value at the previous index
87                        ++inds.back();
88                        iter.backtrack();
89                        if ( inds.back() < qs[inds.size()-1].size() ) break;
90                        // if the previous index is finished, backtrack out
91                        inds.pop_back();
92                }
93
94                // Done if backtracked the entire array
95                if ( inds.empty() ) return out;
96        }
97}
98
99// Local Variables: //
100// tab-width: 4 //
101// mode: c++ //
102// compile-command: "make install" //
103// End: //
Note: See TracBrowser for help on using the repository browser.