| 100 | |
| 101 | template<class VA, class VB, bool tiebreak> |
| 102 | ExecStatus |
| 103 | ArgMax<VA,VB,tiebreak>::propagate(Space& home, const ModEventDelta&) { |
| 104 | /* |
| 105 | * A key invariant is as follows: for each value i in the domain |
| 106 | * of y there is an index-value pair with index i in x. |
| 107 | */ |
| 108 | |
| 109 | // Compute lower and upper bounds for the maximum and its first position. |
| 110 | int p = x[0].idx; |
| 111 | int l = x[0].view.min(); |
| 112 | int u = x[0].view.max(); |
| 113 | for (int i=1; i<x.size(); i++) { |
| 114 | if (l < x[i].view.min()) { |
| 115 | p = x[i].idx; l = x[i].view.min(); |
| 116 | } |
| 117 | if (u < x[i].view.max()) |
| 118 | u = x[i].view.max(); |
| 119 | } |
| 120 | |
| 121 | // Eliminate elements from x and y that are too small |
| 122 | { |
| 123 | Region r; |
| 124 | |
| 125 | // Values to delete from y |
| 126 | int* d=r.alloc<int>(y.size()); |
| 127 | // Number of values to delete |
| 128 | int n = 0; |
| 129 | |
| 130 | int i=0, j=0; |
| 131 | ViewValues<VB> iy(y); |
| 132 | |
| 133 | while ((i < x.size()) && iy()) { |
| 134 | if (x[i].idx == iy.val()) { |
| 135 | if (x[i].view.max() < l) { |
| 136 | x[i].view.cancel(home,*this,PC_INT_BND); |
| 137 | d[n++]=x[i].idx; |
| 138 | } else { |
| 139 | x[j++]=x[i]; |
| 140 | } |
| 141 | ++iy; |
| 142 | } else { |
| 143 | assert(x[i].idx < iy.val()); |
| 144 | if (x[i].view.max() < l) { |
| 145 | x[i].view.cancel(home,*this,PC_INT_BND); |
| 146 | } else { |
| 147 | x[j++]=x[i]; |
| 148 | } |
| 149 | } |
| 150 | i++; |
| 151 | } |
| 152 | while (i < x.size()) |
| 153 | if (x[i].view.max() < l) { |
| 154 | x[i].view.cancel(home,*this,PC_INT_BND); i++; |
| 155 | } else { |
| 156 | x[j++]=x[i++]; |
| 157 | } |
| 158 | x.size(j); |
| 159 | |