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