BLI_index_ranges_builder.hh

Go to the documentation of this file.

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

 
#pragma once
 
#include <array>
 
#include "BLI_index_range.hh"
#include "BLI_index_ranges_builder_fwd.hh"
#include "BLI_span.hh"
#include "BLI_utility_mixins.hh"
 
namespace blender {

template<typename T> class IndexRangesBuilder : NonCopyable, NonMovable {
 private:
  T *c_;
  MutableSpan<T> data_;
 
 public:
  IndexRangesBuilder(MutableSpan<T> data) : data_(data)
  {
    static_assert(std::is_signed_v<T>);
    /* Set the first value to -1 so that when the first index is added, it is detected as the start
     * of a new range. */
    data_[0] = -1;
    c_ = data_.data();
  }

  bool add(const T index)
  {
    return this->add_range(index, index + 1);
  }

  bool add_range(const T start, const T end)
  {
    /* Indices have to be added in ascending order. */
    BLI_assert(start >= *c_);
    BLI_assert(start >= 0);
    BLI_assert(start < end);
 
    const bool is_new_range = start > *c_;
 
    /* Check that the capacity is not overflown. */
    BLI_assert(!is_new_range || this->size() < this->capacity());
 
    /* This is designed to either append to the last range or start a new range.
     * It is intentionally branchless for more predictable performance on unpredictable data. */
    c_ += is_new_range;
    *c_ = start;
    c_ += is_new_range;
    *c_ = end;
 
    return is_new_range;
  }

  int64_t size() const
  {
    return (c_ - data_.data()) / 2;
  }

  int64_t capacity() const
  {
    return data_.size() / 2;
  }

  bool is_empty() const
  {
    return c_ == data_.data();
  }
 
  IndexRange index_range() const
  {
    return IndexRange(this->size());
  }

  IndexRange operator[](const int64_t i) const
  {
    const T start = data_[size_t(1) + 2 * size_t(i)];
    const T end = data_[size_t(2) + 2 * size_t(i)];
    return IndexRange::from_begin_end(start, end);
  }
 
  static constexpr int64_t buffer_size_for_ranges_num(const int64_t ranges_num)
  {
    /* Two values for each range (start, end) and the dummy prefix value. */
    return ranges_num * 2 + 1;
  }
};
 
template<typename T, int64_t MaxRangesNum> struct IndexRangesBuilderBuffer {
  std::array<T, size_t(IndexRangesBuilder<T>::buffer_size_for_ranges_num(MaxRangesNum))> data;
 
  operator MutableSpan<T>()
  {
    return this->data;
  }
};
 
}  // namespace blender