| 111 | */ |
| 112 | template<class View> |
| 113 | inline bool |
| 114 | revglover(ViewArray<View>& x, ViewArray<View>& y, |
| 115 | int tau[], int phiprime[], OfflineMinItem sequence[], |
| 116 | int vertices[]) { |
| 117 | |
| 118 | int xs = x.size(); |
| 119 | OfflineMin seq(sequence, vertices, xs); |
| 120 | int s = xs - 1; |
| 121 | seq.makeset(); |
| 122 | |
| 123 | int miny = 0; |
| 124 | for (int z = xs; z--; ) { // forall y nodes |
| 125 | miny = y[z].min(); |
| 126 | // creating the sequence of inserts and extractions from the queue |
| 127 | for ( ; s > -1 && x[tau[s]].max() >= miny; s--) { |
| 128 | seq[tau[s]].iset = z; |
| 129 | seq[z].rank++; |
| 130 | } |
| 131 | } |
| 132 | |
| 133 | // offline-min-procedure |
| 134 | for (int i = xs; i--; ) { |
| 135 | int perm = i; |
| 136 | int iter = seq[perm].iset; |
| 137 | if (iter < 0) |
| 138 | return false; |
| 139 | int j = 0; |
| 140 | j = seq.find_pc(iter); |
| 141 | if (j <= -1) |
| 142 | return false; |
| 143 | // if there is no intersection between the matching candidate |
| 144 | // and the y node then there exists NO perfect matching |
| 145 | if (x[perm].min() > y[j].max()) |
| 146 | return false; |
| 147 | phiprime[j] = perm; |
| 148 | seq[perm].iset = -5; |
| 149 | int sqjsucc = seq[j].pred; |
| 150 | if (sqjsucc >= 0) { |
| 151 | seq.unite(j, sqjsucc, sqjsucc); |
| 152 | } else { |
| 153 | seq[seq[j].root].name = sqjsucc; // end of sequence achieved |
| 154 | } |
| 155 | |
| 156 | // adjust tree list |
| 157 | int pr = seq[j].succ; |
| 158 | if (pr != xs) |
| 159 | seq[pr].pred = sqjsucc; |
| 160 | if (sqjsucc != -1) |
| 161 | seq[sqjsucc].succ = pr; |
| 162 | } |
| 163 | return true; |
| 164 | } |
| 165 | |
| 166 | }}} |
| 167 | |