BLI_span.hh

Go to the documentation of this file.

/*
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 */
 
#pragma once
 
#include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <vector>
 
#include "BLI_index_range.hh"
#include "BLI_memory_utils.hh"
#include "BLI_utildefines.h"
 
namespace blender {
 
template<typename T> class Span {
 public:
  using value_type = T;
  using pointer = T *;
  using const_pointer = const T *;
  using reference = T &;
  using const_reference = const T &;
  using iterator = const T *;
  using size_type = int64_t;
 
 private:
  const T *data_ = nullptr;
  int64_t size_ = 0;
 
 public:
  constexpr Span() = default;
 
  constexpr Span(const T *start, int64_t size) : data_(start), size_(size)
  {
    BLI_assert(size >= 0);
  }
 
  template<typename U, typename std::enable_if_t<is_span_convertible_pointer_v<U, T>> * = nullptr>
  constexpr Span(const U *start, int64_t size) : data_(static_cast<const T *>(start)), size_(size)
  {
    BLI_assert(size >= 0);
  }
 
  constexpr Span(const std::initializer_list<T> &list)
      : Span(list.begin(), static_cast<int64_t>(list.size()))
  {
  }
 
  constexpr Span(const std::vector<T> &vector)
      : Span(vector.data(), static_cast<int64_t>(vector.size()))
  {
  }
 
  template<std::size_t N> constexpr Span(const std::array<T, N> &array) : Span(array.data(), N)
  {
  }
 
  template<typename U, typename std::enable_if_t<is_span_convertible_pointer_v<U, T>> * = nullptr>
  constexpr Span(Span<U> span) : data_(static_cast<const T *>(span.data())), size_(span.size())
  {
  }
 
  constexpr Span slice(int64_t start, int64_t size) const
  {
    BLI_assert(start >= 0);
    BLI_assert(size >= 0);
    const int64_t new_size = std::max<int64_t>(0, std::min(size, size_ - start));
    return Span(data_ + start, new_size);
  }
 
  constexpr Span slice(IndexRange range) const
  {
    return this->slice(range.start(), range.size());
  }
 
  constexpr Span drop_front(int64_t n) const
  {
    BLI_assert(n >= 0);
    const int64_t new_size = std::max<int64_t>(0, size_ - n);
    return Span(data_ + n, new_size);
  }
 
  constexpr Span drop_back(int64_t n) const
  {
    BLI_assert(n >= 0);
    const int64_t new_size = std::max<int64_t>(0, size_ - n);
    return Span(data_, new_size);
  }
 
  constexpr Span take_front(int64_t n) const
  {
    BLI_assert(n >= 0);
    const int64_t new_size = std::min<int64_t>(size_, n);
    return Span(data_, new_size);
  }
 
  constexpr Span take_back(int64_t n) const
  {
    BLI_assert(n >= 0);
    const int64_t new_size = std::min<int64_t>(size_, n);
    return Span(data_ + size_ - new_size, new_size);
  }
 
  constexpr const T *data() const
  {
    return data_;
  }
 
  constexpr const T *begin() const
  {
    return data_;
  }
  constexpr const T *end() const
  {
    return data_ + size_;
  }
 
  constexpr std::reverse_iterator<const T *> rbegin() const
  {
    return std::reverse_iterator<const T *>(this->end());
  }
  constexpr std::reverse_iterator<const T *> rend() const
  {
    return std::reverse_iterator<const T *>(this->begin());
  }
 
  constexpr const T &operator[](int64_t index) const
  {
    BLI_assert(index >= 0);
    BLI_assert(index < size_);
    return data_[index];
  }
 
  constexpr int64_t size() const
  {
    return size_;
  }
 
  constexpr bool is_empty() const
  {
    return size_ == 0;
  }
 
  constexpr int64_t size_in_bytes() const
  {
    return sizeof(T) * size_;
  }
 
  constexpr bool contains(const T &value) const
  {
    for (const T &element : *this) {
      if (element == value) {
        return true;
      }
    }
    return false;
  }
 
  constexpr bool contains_ptr(const T *ptr) const
  {
    return (this->begin() <= ptr) && (ptr < this->end());
  }
 
  constexpr int64_t count(const T &value) const
  {
    int64_t counter = 0;
    for (const T &element : *this) {
      if (element == value) {
        counter++;
      }
    }
    return counter;
  }
 
  constexpr const T &first() const
  {
    BLI_assert(size_ > 0);
    return data_[0];
  }
 
  constexpr const T &last() const
  {
    BLI_assert(size_ > 0);
    return data_[size_ - 1];
  }
 
  constexpr T get(int64_t index, const T &fallback) const
  {
    if (index < size_ && index >= 0) {
      return data_[index];
    }
    return fallback;
  }
 
  constexpr bool has_duplicates__linear_search() const
  {
    /* The size should really be smaller than that. If it is not, the calling code should be
     * changed. */
    BLI_assert(size_ < 1000);
 
    for (int64_t i = 0; i < size_; i++) {
      const T &value = data_[i];
      for (int64_t j = i + 1; j < size_; j++) {
        if (value == data_[j]) {
          return true;
        }
      }
    }
    return false;
  }
 
  constexpr bool intersects__linear_search(Span other) const
  {
    /* The size should really be smaller than that. If it is not, the calling code should be
     * changed. */
    BLI_assert(size_ < 1000);
 
    for (int64_t i = 0; i < size_; i++) {
      const T &value = data_[i];
      if (other.contains(value)) {
        return true;
      }
    }
    return false;
  }
 
  constexpr int64_t first_index(const T &search_value) const
  {
    const int64_t index = this->first_index_try(search_value);
    BLI_assert(index >= 0);
    return index;
  }
 
  constexpr int64_t first_index_try(const T &search_value) const
  {
    for (int64_t i = 0; i < size_; i++) {
      if (data_[i] == search_value) {
        return i;
      }
    }
    return -1;
  }
 
  constexpr IndexRange index_range() const
  {
    return IndexRange(size_);
  }
 
  template<typename NewT> Span<NewT> constexpr cast() const
  {
    BLI_assert((size_ * sizeof(T)) % sizeof(NewT) == 0);
    int64_t new_size = size_ * sizeof(T) / sizeof(NewT);
    return Span<NewT>(reinterpret_cast<const NewT *>(data_), new_size);
  }
 
  friend bool operator==(const Span<T> a, const Span<T> b)
  {
    if (a.size() != b.size()) {
      return false;
    }
    return std::equal(a.begin(), a.end(), b.begin());
  }
 
  friend bool operator!=(const Span<T> a, const Span<T> b)
  {
    return !(a == b);
  }
 
  template<typename PrintLineF> void print_as_lines(std::string name, PrintLineF print_line) const
  {
    std::cout << "Span: " << name << " \tSize:" << size_ << '\n';
    for (const T &value : *this) {
      std::cout << "  ";
      print_line(value);
      std::cout << '\n';
    }
  }
 
  void print_as_lines(std::string name) const
  {
    this->print_as_lines(name, [](const T &value) { std::cout << value; });
  }
};
 
template<typename T> class MutableSpan {
 public:
  using value_type = T;
  using pointer = T *;
  using const_pointer = const T *;
  using reference = T &;
  using const_reference = const T &;
  using iterator = T *;
  using size_type = int64_t;
 
 private:
  T *data_;
  int64_t size_;
 
 public:
  constexpr MutableSpan() = default;
 
  constexpr MutableSpan(T *start, const int64_t size) : data_(start), size_(size)
  {
  }
 
  constexpr MutableSpan(std::vector<T> &vector) : MutableSpan(vector.data(), vector.size())
  {
  }
 
  template<std::size_t N>
  constexpr MutableSpan(std::array<T, N> &array) : MutableSpan(array.data(), N)
  {
  }
 
  template<typename U, typename std::enable_if_t<is_span_convertible_pointer_v<U, T>> * = nullptr>
  constexpr MutableSpan(MutableSpan<U> span)
      : data_(static_cast<T *>(span.data())), size_(span.size())
  {
  }
 
  constexpr operator Span<T>() const
  {
    return Span<T>(data_, size_);
  }
 
  template<typename U, typename std::enable_if_t<is_span_convertible_pointer_v<T, U>> * = nullptr>
  constexpr operator Span<U>() const
  {
    return Span<U>(static_cast<const U *>(data_), size_);
  }
 
  constexpr int64_t size() const
  {
    return size_;
  }
 
  constexpr bool is_empty() const
  {
    return size_ == 0;
  }
 
  constexpr void fill(const T &value)
  {
    initialized_fill_n(data_, size_, value);
  }
 
  constexpr void fill_indices(Span<int64_t> indices, const T &value)
  {
    for (int64_t i : indices) {
      BLI_assert(i < size_);
      data_[i] = value;
    }
  }
 
  constexpr T *data() const
  {
    return data_;
  }
 
  constexpr T *begin() const
  {
    return data_;
  }
  constexpr T *end() const
  {
    return data_ + size_;
  }
 
  constexpr std::reverse_iterator<T *> rbegin() const
  {
    return std::reverse_iterator<T *>(this->end());
  }
  constexpr std::reverse_iterator<T *> rend() const
  {
    return std::reverse_iterator<T *>(this->begin());
  }
 
  constexpr T &operator[](const int64_t index) const
  {
    BLI_assert(index < this->size());
    return data_[index];
  }
 
  constexpr MutableSpan slice(const int64_t start, const int64_t size) const
  {
    BLI_assert(start >= 0);
    BLI_assert(size >= 0);
    const int64_t new_size = std::max<int64_t>(0, std::min(size, size_ - start));
    return MutableSpan(data_ + start, new_size);
  }
 
  constexpr MutableSpan drop_front(const int64_t n) const
  {
    BLI_assert(n >= 0);
    const int64_t new_size = std::max<int64_t>(0, size_ - n);
    return MutableSpan(data_ + n, new_size);
  }
 
  constexpr MutableSpan drop_back(const int64_t n) const
  {
    BLI_assert(n >= 0);
    const int64_t new_size = std::max<int64_t>(0, size_ - n);
    return MutableSpan(data_, new_size);
  }
 
  constexpr MutableSpan take_front(const int64_t n) const
  {
    BLI_assert(n >= 0);
    const int64_t new_size = std::min<int64_t>(size_, n);
    return MutableSpan(data_, new_size);
  }
 
  constexpr MutableSpan take_back(const int64_t n) const
  {
    BLI_assert(n >= 0);
    const int64_t new_size = std::min<int64_t>(size_, n);
    return MutableSpan(data_ + size_ - new_size, new_size);
  }
 
  constexpr Span<T> as_span() const
  {
    return Span<T>(data_, size_);
  }
 
  constexpr IndexRange index_range() const
  {
    return IndexRange(size_);
  }
 
  constexpr T &last() const
  {
    BLI_assert(size_ > 0);
    return data_[size_ - 1];
  }
 
  constexpr int64_t count(const T &value) const
  {
    int64_t counter = 0;
    for (const T &element : *this) {
      if (element == value) {
        counter++;
      }
    }
    return counter;
  }
 
  constexpr void copy_from(Span<T> values)
  {
    BLI_assert(size_ == values.size());
    initialized_copy_n(values.data(), size_, data_);
  }
 
  template<typename NewT> constexpr MutableSpan<NewT> cast() const
  {
    BLI_assert((size_ * sizeof(T)) % sizeof(NewT) == 0);
    int64_t new_size = size_ * sizeof(T) / sizeof(NewT);
    return MutableSpan<NewT>((NewT *)data_, new_size);
  }
};
 
template<typename T1, typename T2> constexpr void assert_same_size(const T1 &v1, const T2 &v2)
{
  UNUSED_VARS_NDEBUG(v1, v2);
#ifdef DEBUG
  int64_t size = v1.size();
  BLI_assert(size == v1.size());
  BLI_assert(size == v2.size());
#endif
}
 
template<typename T1, typename T2, typename T3>
constexpr void assert_same_size(const T1 &v1, const T2 &v2, const T3 &v3)
{
  UNUSED_VARS_NDEBUG(v1, v2, v3);
#ifdef DEBUG
  int64_t size = v1.size();
  BLI_assert(size == v1.size());
  BLI_assert(size == v2.size());
  BLI_assert(size == v3.size());
#endif
}
 
} /* namespace blender */