BLI_offset_indices.hh

Go to the documentation of this file.

/* SPDX-FileCopyrightText: 2023 Blender Authors
 *
 * SPDX-License-Identifier: GPL-2.0-or-later */

 
#pragma once
 
#include <algorithm>
#include <optional>
 
#include "BLI_index_mask_fwd.hh"
#include "BLI_index_range.hh"
#include "BLI_span.hh"
 
namespace blender::offset_indices {

struct NoSortCheck {};

template<typename T> class OffsetIndices {
 private:
  static_assert(std::is_integral_v<T>);
 
  Span<T> offsets_;
 
 public:
  OffsetIndices() = default;
  OffsetIndices(const Span<T> offsets) : offsets_(offsets)
  {
    BLI_assert(offsets_.size() < 2 || std::is_sorted(offsets_.begin(), offsets_.end()));
  }

  OffsetIndices(const Span<T> offsets, NoSortCheck /*no_sort_check*/) : offsets_(offsets) {}

  T total_size() const
  {
    return offsets_.size() > 1 ? offsets_.last() - offsets_.first() : 0;
  }

  int64_t size() const
  {
    return std::max<int64_t>(offsets_.size() - 1, 0);
  }
 
  bool is_empty() const
  {
    return this->size() == 0;
  }
 
  IndexRange index_range() const
  {
    return IndexRange(this->size());
  }
 
  IndexRange operator[](const int64_t index) const
  {
    BLI_assert(index >= 0);
    BLI_assert(index < offsets_.size() - 1);
    const int64_t begin = offsets_[index];
    const int64_t end = offsets_[index + 1];
    return IndexRange::from_begin_end(begin, end);
  }
 
  IndexRange operator[](const IndexRange indices) const
  {
    const int64_t begin = offsets_[indices.start()];
    const int64_t end = offsets_[indices.one_after_last()];
    return IndexRange::from_begin_end(begin, end);
  }

  OffsetIndices slice(const IndexRange range) const
  {
    BLI_assert(range.is_empty() || offsets_.index_range().drop_back(1).contains(range.last()));
    return OffsetIndices(offsets_.slice(range.start(), range.size() + 1));
  }
 
  Span<T> data() const
  {
    return offsets_;
  }
};

template<typename T> struct GroupedSpan {
  OffsetIndices<int> offsets;
  Span<T> data;
 
  GroupedSpan() = default;
  GroupedSpan(OffsetIndices<int> offsets, Span<T> data) : offsets(offsets), data(data)
  {
    BLI_assert(this->offsets.total_size() == this->data.size());
  }
 
  Span<T> operator[](const int64_t index) const
  {
    return this->data.slice(this->offsets[index]);
  }
 
  int64_t size() const
  {
    return this->offsets.size();
  }
 
  IndexRange index_range() const
  {
    return this->offsets.index_range();
  }
 
  bool is_empty() const
  {
    return this->data.size() == 0;
  }
};

OffsetIndices<int> accumulate_counts_to_offsets(MutableSpan<int> counts_to_offsets,
                                                int start_offset = 0);
 
std::optional<OffsetIndices<int>> accumulate_counts_to_offsets_with_overflow_check(
    MutableSpan<int> counts_to_offsets, int start_offset = 0);

void fill_constant_group_size(int size, int start_offset, MutableSpan<int> offsets);

void copy_group_sizes(OffsetIndices<int> offsets, const IndexMask &mask, MutableSpan<int> sizes);

void gather_group_sizes(OffsetIndices<int> offsets, const IndexMask &mask, MutableSpan<int> sizes);
void gather_group_sizes(OffsetIndices<int> offsets, Span<int> indices, MutableSpan<int> sizes);

int sum_group_sizes(OffsetIndices<int> offsets, const IndexMask &mask);
int sum_group_sizes(OffsetIndices<int> offsets, Span<int> indices);

OffsetIndices<int> gather_selected_offsets(OffsetIndices<int> src_offsets,
                                           const IndexMask &selection,
                                           int start_offset,
                                           MutableSpan<int> dst_offsets);
inline OffsetIndices<int> gather_selected_offsets(OffsetIndices<int> src_offsets,
                                                  const IndexMask &selection,
                                                  MutableSpan<int> dst_offsets)
{
  return gather_selected_offsets(src_offsets, selection, 0, dst_offsets);
}

void build_reverse_map(OffsetIndices<int> offsets, MutableSpan<int> r_map);

void build_reverse_offsets(Span<int> indices, MutableSpan<int> offsets);
 
}  // namespace blender::offset_indices
 
namespace blender {
using offset_indices::GroupedSpan;
using offset_indices::OffsetIndices;
}  // namespace blender