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