source/blender/blenlib/BLI_array_utils.hh

   1 /* SPDX-FileCopyrightText: 2023 Blender Authors
   2  *
   3  * SPDX-License-Identifier: GPL-2.0-or-later */
   4
   5 #pragma once
   6
   7 #include <numeric>
   8
   9 #include "BLI_generic_span.hh"
  10 #include "BLI_generic_virtual_array.hh"
  11 #include "BLI_index_mask.hh"
  12 #include "BLI_offset_indices.hh"
  13 #include "BLI_task.hh"
  14 #include "BLI_virtual_array.hh"
  15
  16 namespace blender::array_utils {
  17
  18 /**
  19  * Fill the destination span by copying all values from the `src` array. Threaded based on
  20  * grain-size.
  21  */
  22 void copy(const GVArray &src, GMutableSpan dst, int64_t grain_size = 4096);
  23 template<typename T>
  24 inline void copy(const VArray<T> &src, MutableSpan<T> dst, const int64_t grain_size = 4096)
  25 {
  26   BLI_assert(src.size() == dst.size());
  27   threading::parallel_for(src.index_range(), grain_size, [&](const IndexRange range) {
  28     src.materialize_to_uninitialized(range, dst);
  29   });
  30 }
  31
  32 /**
  33  * Fill the destination span by copying all values from the `src` array. Threaded based on
  34  * grain-size.
  35  */
  36 template<typename T>
  37 inline void copy(const Span<T> src, MutableSpan<T> dst, const int64_t grain_size = 4096)
  38 {
  39   BLI_assert(src.size() == dst.size());
  40   threading::parallel_for(src.index_range(), grain_size, [&](const IndexRange range) {
  41     dst.slice(range).copy_from(src.slice(range));
  42   });
  43 }
  44
  45 /**
  46  * Fill the destination span by copying masked values from the `src` array. Threaded based on
  47  * grain-size.
  48  */
  49 void copy(const GVArray &src,
  50           const IndexMask &selection,
  51           GMutableSpan dst,
  52           int64_t grain_size = 4096);
  53
  54 /**
  55  * Fill the destination span by copying values from the `src` array. Threaded based on
  56  * grain-size.
  57  */
  58 template<typename T>
  59 inline void copy(const Span<T> src,
  60                  const IndexMask &selection,
  61                  MutableSpan<T> dst,
  62                  const int64_t grain_size = 4096)
  63 {
  64   BLI_assert(src.size() == dst.size());
  65   selection.foreach_index_optimized<int64_t>(GrainSize(grain_size),
  66                                              [&](const int64_t i) { dst[i] = src[i]; });
  67 }
  68
  69 /**
  70  * Fill the specified indices of the destination with the values in the source span.
  71  */
  72 template<typename T, typename IndexT>
  73 inline void scatter(const Span<T> src,
  74                     const Span<IndexT> indices,
  75                     MutableSpan<T> dst,
  76                     const int64_t grain_size = 4096)
  77 {
  78   BLI_assert(indices.size() == src.size());
  79   threading::parallel_for(indices.index_range(), grain_size, [&](const IndexRange range) {
  80     for (const int64_t i : range) {
  81       dst[indices[i]] = src[i];
  82     }
  83   });
  84 }
  85
  86 template<typename T>
  87 inline void scatter(const Span<T> src,
  88                     const IndexMask &indices,
  89                     MutableSpan<T> dst,
  90                     const int64_t grain_size = 4096)
  91 {
  92   BLI_assert(indices.size() == src.size());
  93   BLI_assert(indices.min_array_size() <= dst.size());
  94   indices.foreach_index_optimized<int64_t>(
  95       GrainSize(grain_size),
  96       [&](const int64_t index, const int64_t pos) { dst[index] = src[pos]; });
  97 }
  98
  99 /**
 100  * Fill the destination span by gathering indexed values from the `src` array.
 101  */
 102 void gather(const GVArray &src,
 103             const IndexMask &indices,
 104             GMutableSpan dst,
 105             int64_t grain_size = 4096);
 106
 107 /**
 108  * Fill the destination span by gathering indexed values from the `src` array.
 109  */
 110 void gather(GSpan src, const IndexMask &indices, GMutableSpan dst, int64_t grain_size = 4096);
 111
 112 /**
 113  * Fill the destination span by gathering indexed values from the `src` array.
 114  */
 115 template<typename T>
 116 inline void gather(const VArray<T> &src,
 117                    const IndexMask &indices,
 118                    MutableSpan<T> dst,
 119                    const int64_t grain_size = 4096)
 120 {
 121   BLI_assert(indices.size() == dst.size());
 122   threading::parallel_for(indices.index_range(), grain_size, [&](const IndexRange range) {
 123     src.materialize_compressed_to_uninitialized(indices.slice(range), dst.slice(range));
 124   });
 125 }
 126
 127 /**
 128  * Fill the destination span by gathering indexed values from the `src` array.
 129  */
 130 template<typename T, typename IndexT>
 131 inline void gather(const Span<T> src,
 132                    const IndexMask &indices,
 133                    MutableSpan<T> dst,
 134                    const int64_t grain_size = 4096)
 135 {
 136   BLI_assert(indices.size() == dst.size());
 137   indices.foreach_segment(GrainSize(grain_size),
 138                           [&](const IndexMaskSegment segment, const int64_t segment_pos) {
 139                             for (const int64_t i : segment.index_range()) {
 140                               dst[segment_pos + i] = src[segment[i]];
 141                             }
 142                           });
 143 }
 144
 145 /**
 146  * Fill the destination span by gathering indexed values from the `src` array.
 147  */
 148 template<typename T, typename IndexT>
 149 inline void gather(const Span<T> src,
 150                    const Span<IndexT> indices,
 151                    MutableSpan<T> dst,
 152                    const int64_t grain_size = 4096)
 153 {
 154   BLI_assert(indices.size() == dst.size());
 155   threading::parallel_for(indices.index_range(), grain_size, [&](const IndexRange range) {
 156     for (const int64_t i : range) {
 157       dst[i] = src[indices[i]];
 158     }
 159   });
 160 }
 161
 162 /**
 163  * Fill the destination span by gathering indexed values from the `src` array.
 164  */
 165 template<typename T, typename IndexT>
 166 inline void gather(const VArray<T> &src,
 167                    const Span<IndexT> indices,
 168                    MutableSpan<T> dst,
 169                    const int64_t grain_size = 4096)
 170 {
 171   BLI_assert(indices.size() == dst.size());
 172   devirtualize_varray(src, [&](const auto &src) {
 173     threading::parallel_for(indices.index_range(), grain_size, [&](const IndexRange range) {
 174       for (const int64_t i : range) {
 175         dst[i] = src[indices[i]];
 176       }
 177     });
 178   });
 179 }
 180
 181 template<typename T>
 182 inline void gather_group_to_group(const OffsetIndices<int> src_offsets,
 183                                   const OffsetIndices<int> dst_offsets,
 184                                   const IndexMask &selection,
 185                                   const Span<T> src,
 186                                   MutableSpan<T> dst)
 187 {
 188   selection.foreach_index(GrainSize(512), [&](const int64_t src_i, const int64_t dst_i) {
 189     dst.slice(dst_offsets[dst_i]).copy_from(src.slice(src_offsets[src_i]));
 190   });
 191 }
 192
 193 template<typename T>
 194 inline void gather_group_to_group(const OffsetIndices<int> src_offsets,
 195                                   const OffsetIndices<int> dst_offsets,
 196                                   const IndexMask &selection,
 197                                   const VArray<T> src,
 198                                   MutableSpan<T> dst)
 199 {
 200   selection.foreach_index(GrainSize(512), [&](const int64_t src_i, const int64_t dst_i) {
 201     src.materialize_compressed(src_offsets[src_i], dst.slice(dst_offsets[dst_i]));
 202   });
 203 }
 204
 205 template<typename T>
 206 inline void gather_to_groups(const OffsetIndices<int> dst_offsets,
 207                              const IndexMask &src_selection,
 208                              const Span<T> src,
 209                              MutableSpan<T> dst)
 210 {
 211   src_selection.foreach_index(GrainSize(1024), [&](const int src_i, const int dst_i) {
 212     dst.slice(dst_offsets[dst_i]).fill(src[src_i]);
 213   });
 214 }
 215
 216 /**
 217  * Copy the \a src data from the groups defined by \a src_offsets to the groups in \a dst defined
 218  * by \a dst_offsets. Groups to use are masked by \a selection, and it is assumed that the
 219  * corresponding groups have the same size.
 220  */
 221 void copy_group_to_group(OffsetIndices<int> src_offsets,
 222                          OffsetIndices<int> dst_offsets,
 223                          const IndexMask &selection,
 224                          GSpan src,
 225                          GMutableSpan dst);
 226 template<typename T>
 227 void copy_group_to_group(OffsetIndices<int> src_offsets,
 228                          OffsetIndices<int> dst_offsets,
 229                          const IndexMask &selection,
 230                          Span<T> src,
 231                          MutableSpan<T> dst)
 232 {
 233   copy_group_to_group(src_offsets, dst_offsets, selection, GSpan(src), GMutableSpan(dst));
 234 }
 235
 236 /**
 237  * Count the number of occurrences of each index.
 238  * \param indices: The indices to count.
 239  * \param counts: The number of occurrences of each index. Typically initialized to zero.
 240  * Must be large enough to contain the maximum index.
 241  *
 242  * \note The memory referenced by the two spans must not overlap.
 243  */
 244 void count_indices(Span<int> indices, MutableSpan<int> counts);
 245
 246 void invert_booleans(MutableSpan<bool> span);
 247 void invert_booleans(MutableSpan<bool> span, const IndexMask &mask);
 248
 249 int64_t count_booleans(const VArray<bool> &varray);
 250 int64_t count_booleans(const VArray<bool> &varray, const IndexMask &mask);
 251
 252 enum class BooleanMix {
 253   None,
 254   AllFalse,
 255   AllTrue,
 256   Mixed,
 257 };
 258 BooleanMix booleans_mix_calc(const VArray<bool> &varray, IndexRange range_to_check);
 259 inline BooleanMix booleans_mix_calc(const VArray<bool> &varray)
 260 {
 261   return booleans_mix_calc(varray, varray.index_range());
 262 }
 263
 264 /**
 265  * Finds all the index ranges for which consecutive values in \a span equal \a value.
 266  */
 267 template<typename T> inline Vector<IndexRange> find_all_ranges(const Span<T> span, const T &value)
 268 {
 269   if (span.is_empty()) {
 270     return Vector<IndexRange>();
 271   }
 272   Vector<IndexRange> ranges;
 273   int64_t length = (span.first() == value) ? 1 : 0;
 274   for (const int64_t i : span.index_range().drop_front(1)) {
 275     if (span[i - 1] == value && span[i] != value) {
 276       ranges.append(IndexRange::from_end_size(i, length));
 277       length = 0;
 278     }
 279     else if (span[i] == value) {
 280       length++;
 281     }
 282   }
 283   if (length > 0) {
 284     ranges.append(IndexRange::from_end_size(span.size(), length));
 285   }
 286   return ranges;
 287 }
 288
 289 /**
 290  * Fill the span with increasing indices: 0, 1, 2, ...
 291  * Optionally, the start value can be provided.
 292  */
 293 template<typename T> inline void fill_index_range(MutableSpan<T> span, const T start = 0)
 294 {
 295   std::iota(span.begin(), span.end(), start);
 296 }
 297
 298 template<typename T>
 299 bool indexed_data_equal(const Span<T> all_values, const Span<int> indices, const Span<T> values)
 300 {
 301   for (const int i : indices.index_range()) {
 302     if (all_values[indices[i]] != values[i]) {
 303       return false;
 304     }
 305   }
 306   return true;
 307 }
 308
 309 bool indices_are_range(Span<int> indices, IndexRange range);
 310
 311 }  // namespace blender::array_utils