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