| 124 | /// |
| 125 | template<class InputIterator1, class InputIterator2, class OutputIterator> |
| 126 | inline OutputIterator set_difference(InputIterator1 first1, |
| 127 | InputIterator1 last1, |
| 128 | InputIterator2 first2, |
| 129 | InputIterator2 last2, |
| 130 | OutputIterator result, |
| 131 | command_queue &queue = system::default_queue()) |
| 132 | { |
| 133 | typedef typename std::iterator_traits<InputIterator1>::value_type value_type; |
| 134 | |
| 135 | int tile_size = 1024; |
| 136 | |
| 137 | int count1 = detail::iterator_range_size(first1, last1); |
| 138 | int count2 = detail::iterator_range_size(first2, last2); |
| 139 | |
| 140 | vector<uint_> tile_a((count1+count2+tile_size-1)/tile_size+1, queue.get_context()); |
| 141 | vector<uint_> tile_b((count1+count2+tile_size-1)/tile_size+1, queue.get_context()); |
| 142 | |
| 143 | // Tile the sets |
| 144 | detail::balanced_path_kernel tiling_kernel; |
| 145 | tiling_kernel.tile_size = tile_size; |
| 146 | tiling_kernel.set_range(first1, last1, first2, last2, |
| 147 | tile_a.begin()+1, tile_b.begin()+1); |
| 148 | fill_n(tile_a.begin(), 1, 0, queue); |
| 149 | fill_n(tile_b.begin(), 1, 0, queue); |
| 150 | tiling_kernel.exec(queue); |
| 151 | |
| 152 | fill_n(tile_a.end()-1, 1, count1, queue); |
| 153 | fill_n(tile_b.end()-1, 1, count2, queue); |
| 154 | |
| 155 | vector<value_type> temp_result(count1+count2, queue.get_context()); |
| 156 | vector<uint_> counts((count1+count2+tile_size-1)/tile_size + 1, queue.get_context()); |
| 157 | fill_n(counts.end()-1, 1, 0, queue); |
| 158 | |
| 159 | // Find individual differences |
| 160 | detail::serial_set_difference_kernel difference_kernel; |
| 161 | difference_kernel.tile_size = tile_size; |
| 162 | difference_kernel.set_range(first1, first2, tile_a.begin(), tile_a.end(), |
| 163 | tile_b.begin(), temp_result.begin(), counts.begin()); |
| 164 | |
| 165 | difference_kernel.exec(queue); |
| 166 | |
| 167 | exclusive_scan(counts.begin(), counts.end(), counts.begin(), queue); |
| 168 | |
| 169 | // Compact the results |
| 170 | detail::compact_kernel compact_kernel; |
| 171 | compact_kernel.tile_size = tile_size; |
| 172 | compact_kernel.set_range(temp_result.begin(), counts.begin(), counts.end(), result); |
| 173 | |
| 174 | compact_kernel.exec(queue); |
| 175 | |
| 176 | return result + (counts.end() - 1).read(queue); |
| 177 | } |
| 178 | |
| 179 | } //end compute namespace |
| 180 | } //end boost namespace |