30 // Google Mock - a framework for writing C++ mock classes.
35 #include "gmock/gmock-matchers.h"
42 #include <vector>
48 // macro where the user-supplied description string is "", if
51 // that are the print-out of the matcher's parameters.
54     const std::vector<const char*>& param_names, const Strings& param_values) {  in FormatMatcherDescription()
64 // Uses the well-known Ford-Fulkerson max flow method to find a maximum
72 // a vector<int> called 'left_' whose elements are initialized to the
76 //   - An edge from source to each left_ node
77 //   - An edge from each right_ node to sink
78 //   - An edge from each left_ node to each right_ node, if the
83 //   - The edges (source, l), (l, r), and (r, sink) are added to the
85 //   - The same three edges are removed from the residual flow graph.
86 //   - The reverse edges (l, source), (r, l), and (sink, r) are added
98 // As an optimization, there is a second vector<int> called right_ which
100 // efficient queries about edges entering or leaving the right-side nodes
110 // .   ||\--> left[0]=1  ---\    right[0]=-1 ----\     .
112 // .   |\---> left[1]=-1    \--> right[1]=0  ---\|     .
114 // .   \----> left[2]=2  ------> right[2]=2  --\||     .
120 //   [1] Cormen, et al (2001). "Section 26.2: The Ford-Fulkerson method".
121 //       "Introduction to Algorithms (Second ed.)", pp. 651-664.
122 //   [2] "Ford-Fulkerson algorithm", Wikipedia,
128         left_(graph_->LhsSize(), kUnused),  in MaxBipartiteMatchState()
129         right_(graph_->RhsSize(), kUnused) {}  in MaxBipartiteMatchState()
134     ::std::vector<char> seen;  in Compute()
138     // edge from the implicit source node to each previously-visited left  in Compute()
142     // Since the source-to-left edge can only carry one flow unit (or,  in Compute()
147     for (size_t ilhs = 0; ilhs < graph_->LhsSize(); ++ilhs) {  in Compute()
148       // Reset the path-marking vector and try to find a path from  in Compute()
152       // 'seen' initialized to 'graph_->RhsSize()' copies of 0.  in Compute()
153       seen.assign(graph_->RhsSize(), 0);  in Compute()
166   static const size_t kUnused = static_cast<size_t>(-1);
168   // Perform a depth-first search from left node ilhs to the sink.  If a
170   // right vector elements corresponding each segment of the path.
172   // flow was added to the network. The 'seen' vector elements correspond
184   bool TryAugment(size_t ilhs, ::std::vector<char>* seen) {  in TryAugment()
185     for (size_t irhs = 0; irhs < graph_->RhsSize(); ++irhs) {  in TryAugment()
187       if (!graph_->HasEdge(ilhs, irhs)) continue;  in TryAugment()
211   // Each element of the left_ vector represents a left hand side node
213   // node (i.e. a matcher). The values in the left_ vector indicate
218   // be redundantly represented in the right_ vector as right_[1] == 3.
222   ::std::vector<size_t> left_;
223   ::std::vector<size_t> right_;
240        << "element #" << it->first << ", "  in LogElementMatcherPairVec()
241        << "matcher #" << it->second << ")";  in LogElementMatcherPairVec()
293         matcher_describers_[0]->DescribeTo(os);  in DescribeToImpl()
311       *os << " - element #" << i << " ";  in DescribeToImpl()
313       *os << " - an element ";  in DescribeToImpl()
315     matcher_describers_[i]->DescribeTo(os);  in DescribeToImpl()
335         matcher_describers_[0]->DescribeNegationTo(os);  in DescribeNegationToImpl()
352       *os << " - element #" << i << " ";  in DescribeNegationToImpl()
354       *os << " - an element ";  in DescribeNegationToImpl()
356     matcher_describers_[i]->DescribeTo(os);  in DescribeNegationToImpl()
371     const ::std::vector<std::string>& element_printouts,  in VerifyMatchMatrix()
372     const MatchMatrix& matrix, MatchResultListener* listener) const {  in VerifyMatchMatrix()  argument
373   if (matrix.LhsSize() == 0 && matrix.RhsSize() == 0) {  in VerifyMatchMatrix()
378     if (matrix.LhsSize() != matrix.RhsSize()) {  in VerifyMatchMatrix()
383       if (matrix.LhsSize() != 0 && listener->IsInterested()) {  in VerifyMatchMatrix()
384         *listener << "which has " << Elements(matrix.LhsSize());  in VerifyMatchMatrix()
391   ::std::vector<char> element_matched(matrix.LhsSize(), 0);  in VerifyMatchMatrix()
392   ::std::vector<char> matcher_matched(matrix.RhsSize(), 0);  in VerifyMatchMatrix()
394   for (size_t ilhs = 0; ilhs < matrix.LhsSize(); ilhs++) {  in VerifyMatchMatrix()
395     for (size_t irhs = 0; irhs < matrix.RhsSize(); irhs++) {  in VerifyMatchMatrix()
396       char matched = matrix.HasEdge(ilhs, irhs);  in VerifyMatchMatrix()
408       if (listener->IsInterested()) {  in VerifyMatchMatrix()
410         matcher_describers_[mi]->DescribeTo(listener->stream());  in VerifyMatchMatrix()
426       if (listener->IsInterested()) {  in VerifyMatchMatrix()
438     const MatchMatrix& matrix, MatchResultListener* listener) const {  in FindPairing()  argument
439   ElementMatcherPairs matches = FindMaxBipartiteMatching(matrix);  in FindPairing()
443       max_flow < matrix.RhsSize()) {  in FindPairing()
444     if (listener->IsInterested()) {  in FindPairing()
447                 << max_flow << " of " << matrix.RhsSize()  in FindPairing()
449       LogElementMatcherPairVec(matches, listener->stream());  in FindPairing()
454       max_flow < matrix.LhsSize()) {  in FindPairing()
455     if (listener->IsInterested()) {  in FindPairing()
458           << max_flow << " of " << matrix.RhsSize()  in FindPairing()
460       LogElementMatcherPairVec(matches, listener->stream());  in FindPairing()
466     if (listener->IsInterested()) {  in FindPairing()
469         *listener << sep << " - element #" << matches[mi].first  in FindPairing()