tpl_dynArray.H

Go to the documentation of this file.

/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
#ifndef TPL_DYNARRAY_H
#define TPL_DYNARRAY_H
 
#include <cmath>
 
#include <string>
#include <concepts>
#include <type_traits>
#include <aleph.H>
#include <ahIterator.H>
#include <array_utils.H>
#include <ahDry.H>
#include <tpl_dynDlist.H>
#include <ah-args-ctor.H>
#include <htlist.H>
#include <ah-dry.H>
#include <ah-errors.H>
#include <tpl_array.H>
 
namespace Aleph {
class BitArray;  // forward needed
 
template <typename T>
class DynArray : public LocateFunctions<DynArray<T>, T>,
                 public FunctionalMethods<DynArray<T>, T>,
                 public GenericKeys<DynArray<T>, T>,
                 public EqualSequenceMethod<DynArray<T>>,
                 public StlAlephIterator<DynArray<T>>
{
  friend class BitArray;  // for access to __traversal() method
 
  // look at the end of this file for seeing the values
public:
  using Item_Type = T;  
  using Key_Type = T;   
 
  static const size_t Default_Pow_Dir;    
  static const size_t Default_Pow_Seg;    
  static const size_t Default_Pow_Block;  
 
private:
  static const size_t Max_Bits_Allowed;
 
public:
  static const unsigned long long Max_Dim_Allowed;
 
private:
  static const size_t Max_Pow_Block;
 
  mutable size_t pow_dir = Default_Pow_Dir;
  mutable size_t pow_seg = Default_Pow_Seg;
  mutable size_t pow_block = std::min(Default_Pow_Block, Max_Pow_Block);
  mutable size_t seg_plus_block_pow = pow_seg + pow_block;
  mutable size_t mask_seg_plus_block = two_raised(seg_plus_block_pow) - 1;
  mutable size_t dir_size = two_raised(pow_dir);      // = 2^pow_dir
  mutable size_t seg_size = two_raised(pow_seg);      // = 2^pow_seg
  mutable size_t block_size = two_raised(pow_block);  // = 2^pow_block
 
  // 2^(pow_dir + pow_seg + pow_block) - 1
  unsigned long long max_dim = two_raised(seg_plus_block_pow + pow_dir);
 
  static size_t two_raised(const size_t n) noexcept
  {
    ah_overflow_error_if(n >= Max_Bits_Allowed) << "two_raised: exponent " << n << " is too large";
    return static_cast<size_t>(1) << n;
  }
 
  static size_t compute_dim(size_t d, size_t s, size_t b) noexcept
  {
    return two_raised(d) * two_raised(s) * two_raised(b);
  }
 
public:
  static void compute_sizes(const size_t n, size_t &d, size_t &s, size_t &b) noexcept
  {
    d = Default_Pow_Dir;
    s = Default_Pow_Seg;
    b = Default_Pow_Block;
    if (compute_dim(d, s, b) >= n)
      return;
 
    while (true)
      {
        if (compute_dim(++d, s, b) >= n)
          break;
 
        if (compute_dim(d, ++s, b) >= n)
          break;
 
        if (compute_dim(d, s, ++b) >= n)
          break;
      }
  }
 
  static std::tuple<size_t, size_t, size_t> compute_sizes(const size_t n) noexcept
  {
    size_t d, s, b;
    compute_sizes(n, d, s, b);
    return std::make_tuple(d, s, b);
  }
 
private:
  size_t mask_seg = seg_size - 1;
  size_t mask_block = block_size - 1;
 
  size_t index_in_dir(const size_t i) const noexcept
  {
    assert((pow_block + pow_seg) == seg_plus_block_pow);
    assert(seg_size * block_size == two_raised(seg_plus_block_pow));
    assert(i >> seg_plus_block_pow == i / (seg_size * block_size));
 
    return i >> seg_plus_block_pow;
  }
 
  size_t modulus_from_index_in_dir(const size_t i) const noexcept
  {
    assert(mask_seg_plus_block == seg_size * block_size - 1);
    assert((i & mask_seg_plus_block) == i % (seg_size * block_size));
 
    return (i & mask_seg_plus_block);
  }
 
  size_t index_in_seg(const size_t &i) const noexcept
  {
    assert(two_raised(pow_block) == block_size);
    assert((modulus_from_index_in_dir(i) >> pow_block) == (i % (seg_size * block_size)) / block_size);
 
    return modulus_from_index_in_dir(i) >> pow_block;
  }
 
  size_t index_in_block(const size_t i) const noexcept
  {
    assert(mask_block == block_size - 1);
    assert((modulus_from_index_in_dir(i) & mask_block) ==
           ((i % (seg_size * block_size)) % block_size));
 
    return modulus_from_index_in_dir(i) & mask_block;
  }
 
  size_t current_dim;
  size_t num_segs = 0;
  size_t num_blocks = 0;
  T ***dir = nullptr;
 
  void fill_dir_to_null() noexcept
  {
    assert(dir != nullptr);
 
    for (size_t i = 0; i < dir_size; ++i)
      dir[i] = nullptr;
  }
 
  void fill_seg_to_null(T **seg) noexcept
  {
    assert(seg != nullptr);
 
    for (size_t i = 0; i < seg_size; ++i)
      seg[i] = nullptr;
  }
 
  void allocate_dir()
  {
    dir = static_cast<T ***>(malloc(dir_size * sizeof(T **)));
    ah_bad_alloc_unless(dir != nullptr);
 
    fill_dir_to_null();
  }
 
  void resize_dir(const size_t i)  // resize dir to fit index i
  {
    assert(i >= max_dim);
 
    size_t new_pow_dir = pow_dir + 1;
    while (compute_dim(new_pow_dir, pow_seg, pow_block) <= i)
      ++new_pow_dir;
 
    const size_t new_dir_sz = two_raised(new_pow_dir);
    T ***new_dir = static_cast<T ***>(realloc(dir, new_dir_sz * sizeof(T **)));
    ah_bad_alloc_unless(new_dir != nullptr);
 
    dir = new_dir;
    for (size_t k = dir_size; k < new_dir_sz; ++k)
      dir[k] = nullptr;
 
    pow_dir = new_pow_dir;
    dir_size = new_dir_sz;
 
    max_dim = compute_dim(pow_dir, pow_seg, pow_block);
  }
 
  void allocate_segment(T **&seg)
  {
    assert(seg == nullptr);
 
    seg = new T *[seg_size];
    fill_seg_to_null(seg);
    ++num_segs;
  }
 
  T default_initial_value = T();
  T *default_initial_value_ptr = &default_initial_value;
 
  void allocate_block(T *&block)
  {
    assert(block == nullptr);
 
    block = new T[block_size];
    ++num_blocks;
 
    if (default_initial_value_ptr == nullptr)
      return;
 
    for (size_t i = 0; i < block_size; ++i)
      block[i] = *default_initial_value_ptr;
  }
 
  void release_segment(T **&seg) noexcept
  {
    assert(seg != nullptr);
 
    delete[] seg;
    seg = nullptr;
    --num_segs;
  }
 
  void release_block(T *&block) noexcept
  {
    assert(block != nullptr);
 
    delete[] block;
    block = nullptr;
    --num_blocks;
  }
 
  void release_blocks_and_segment(T **&seg) noexcept
  {
    assert(seg != nullptr);
 
    for (size_t i = 0; i < seg_size; ++i)
      if (seg[i] != nullptr)
        release_block(seg[i]);
 
    release_segment(seg);
  }
 
  void ensure_not_empty(const char *context) const
  {
    ah_underflow_error_if(is_empty()) << context;
  }
 
  void release_all_segments_and_blocks() noexcept
  {
    assert(dir != nullptr);
 
    for (size_t i = 0; i < dir_size; ++i)
      if (dir[i] != nullptr)
        release_blocks_and_segment(dir[i]);
 
    current_dim = 0;
  }
 
  void release_dir() noexcept
  {
    if (dir == nullptr)
      return;
 
    release_all_segments_and_blocks();
    if (dir != nullptr)
      free(dir);
 
    dir = nullptr;
    current_dim = 0;
  }
 
  static size_t next2Pow(const size_t number) noexcept
  {
    return static_cast<size_t>(ceil(log(static_cast<float>(number)) / log(2.0)));
  }
 
  size_t divide_by_block_size(const size_t number) const noexcept
  {
    assert(number / block_size == number >> pow_block);
 
    return number >> pow_block;
  }
 
  size_t modulus_by_block_size(const size_t number) const noexcept
  {
    assert((number % block_size) == (number & mask_block));
 
    return number & mask_block;
  }
 
  void allocate_block(T *&block, T *src_block)
  {
    allocate_block(block);
    for (size_t i = 0; i < block_size; i++)
      block[i] = src_block[i];
  }
 
  void allocate_segment(T **&seg, T **src_seg)
  {
    allocate_segment(seg);
    for (size_t i = 0; i < seg_size; i++)
      if (src_seg[i] != nullptr)
        allocate_block(seg[i], src_seg[i]);
  }
 
  void allocate_dir(T ***src_dir)
  {
    allocate_dir();
    for (size_t i = 0; i < dir_size; i++)
      if (src_dir[i] != nullptr)
        allocate_segment(dir[i], src_dir[i]);
  }
 
  class Proxy
  {
    size_t index;
    size_t pos_in_dir;
    size_t pos_in_seg;
    size_t pos_in_block;
    T **&ref_seg;
    T *block;
    DynArray &array;
 
  public:
    Proxy(DynArray<T> &_array, const size_t i) noexcept
      : index(i), pos_in_dir(_array.index_in_dir(index)), pos_in_seg(_array.index_in_seg(index)),
        pos_in_block(_array.index_in_block(index)), ref_seg(_array.dir[pos_in_dir]), block(nullptr),
        array(_array)
    {
      if (ref_seg != nullptr)
        block = ref_seg[pos_in_seg];  // Entry block already exists
    }
 
    operator T &()
    {
      ah_invalid_argument_if(block == nullptr) << "accessed entry not been still written";
      return block[pos_in_block];
    }
 
    T *operator ->()
    {
      bool seg_was_allocated_in_current_call = false;
 
      if (ref_seg == nullptr)  // Is there a segment?
        {                      // No ==> allocate it!
          array.allocate_segment(ref_seg);
          seg_was_allocated_in_current_call = true;
        }
 
      if (block == nullptr)  // test if block is allocated
        {
          try
            {
              array.allocate_block(block);
              ref_seg[pos_in_seg] = block;
 
              assert(array.dir[pos_in_dir] == ref_seg);
            }
          catch (...)
            {
              if (seg_was_allocated_in_current_call)
                array.release_segment(ref_seg);
 
              throw;
            }
        }
 
      if (index >= array.current_dim)
        array.current_dim = index + 1;
 
      return &block[pos_in_block];
    }
 
    Proxy &operator = (const T &data)
    {
      bool seg_was_allocated_in_current_call = false;
      if (ref_seg == nullptr)  // Is there a segment?
        {                      // No ==> allocate ii!
          array.allocate_segment(ref_seg);
          seg_was_allocated_in_current_call = true;
        }
 
      if (block == nullptr)  // test if block is allocated
        {
          try
            {
              array.allocate_block(block);
              ref_seg[pos_in_seg] = block;
 
              assert(array.dir[pos_in_dir] == ref_seg);
            }
          catch (...)
            {
              if (seg_was_allocated_in_current_call)
                array.release_segment(ref_seg);
 
              throw;
            }
        }
 
      if (index >= array.current_dim)
        array.current_dim = index + 1;
 
      block[pos_in_block] = data;
 
      return *this;
    }
 
    Proxy &operator = (const Proxy &proxy)
    {
      ah_domain_error_if(proxy.block == nullptr) << "right entry has not been still written";
 
      if (&proxy == this)
        return *this;
 
      bool seg_was_allocated_in_current_call = false;
      if (ref_seg == nullptr)  // Is there a segment?
        {                      // No ==> allocate it!
          array.allocate_segment(ref_seg);
          seg_was_allocated_in_current_call = true;
        }
 
      if (block == nullptr)  // test if block is allocated
        {
          try
            {
              array.allocate_block(block);
              ref_seg[pos_in_seg] = block;
 
              assert(array.dir[pos_in_dir] == ref_seg);
            }
          catch (...)
            {
              if (seg_was_allocated_in_current_call)
                array.release_segment(ref_seg);
 
              throw;
            }
        }
 
      if (index >= array.current_dim)
        array.current_dim = index + 1;
 
      block[pos_in_block] = proxy.block[proxy.pos_in_block];
 
      return *this;
    }
  };
 
public:
  size_t get_dir_size() const noexcept
  {
    return dir_size;
  }
 
  size_t get_seg_size() const noexcept
  {
    return seg_size;
  }
 
  size_t get_block_size() const noexcept
  {
    return block_size;
  }
 
  size_t size() const noexcept
  {
    return current_dim;
  }
 
  size_t max_size() const noexcept
  {
    return max_dim;
  }
 
  size_t get_num_blocks() const noexcept
  {
    return num_blocks;
  }
 
  void set_default_initial_value(const T &value) noexcept
  {
    default_initial_value = value;
    default_initial_value_ptr = &default_initial_value;
  }
 
  void set_default_initial_value(T &&value = T())
  {
    std::swap(default_initial_value, value);
    default_initial_value_ptr = &default_initial_value;
  }
 
  DynArray(const size_t _pow_dir, const size_t _pow_seg, const size_t _pow_block)
    : pow_dir(_pow_dir), pow_seg(_pow_seg), pow_block(_pow_block),
      seg_plus_block_pow(_pow_seg + _pow_block),
      mask_seg_plus_block(two_raised(seg_plus_block_pow) - 1), dir_size(two_raised(pow_dir)),
      seg_size(two_raised(pow_seg)), block_size(two_raised(pow_block)),
      max_dim(two_raised(seg_plus_block_pow + pow_dir)), mask_seg(seg_size - 1),
      mask_block(block_size - 1), current_dim(0), num_segs(0), num_blocks(0)
  {
    static_assert(std::is_copy_constructible_v<T>, "No copy constructor for T");
    static_assert(std::is_move_constructible_v<T>, "No move constructor for T");
    static_assert(std::is_copy_assignable_v<T>, "No copy assign for T");
    static_assert(std::is_move_assignable_v<T>, "No move assign for T");
    assert(Max_Dim_Allowed > 0);
 
    ah_length_error_if(max_dim > Max_Dim_Allowed) << "Dimension too large";
 
    allocate_dir();
  }
 
  DynArray(const size_t dim = 0) : current_dim(dim)
  {
    static_assert(std::is_default_constructible_v<T>, "No default constructor for T");
    static_assert(std::is_copy_constructible_v<T>, "No copy constructor for T");
    static_assert(std::is_move_constructible_v<T>, "No move constructor for T");
    static_assert(std::is_copy_assignable_v<T>, "No copy assign for T");
    static_assert(std::is_move_assignable_v<T>, "No move assign for T");
    assert(Max_Dim_Allowed > 0);
 
    ah_length_error_if(max_dim > Max_Dim_Allowed) << "Dimension too large";
 
    allocate_dir();
  }
 
  Special_Ctors(DynArray, T);
 
  ~DynArray()
  {
    release_dir();
  }
 
  void copy_array(const DynArray<T> &src_array)
  {
    for (size_t i = 0; i < src_array.current_dim; ++i)
      if (src_array.exist(i))
        (*this)[i] = src_array.access(i);
  }
 
  DynArray(const DynArray<T> &array)
    : pow_dir(array.pow_dir), pow_seg(array.pow_seg), pow_block(array.pow_block),
      seg_plus_block_pow(array.seg_plus_block_pow), mask_seg_plus_block(array.mask_seg_plus_block),
      dir_size(array.dir_size), seg_size(array.seg_size), block_size(array.block_size),
      max_dim(array.max_dim), mask_seg(array.mask_seg), mask_block(array.mask_block), current_dim(0),
      num_segs(0), num_blocks(0), dir(nullptr), default_initial_value(array.default_initial_value),
      default_initial_value_ptr(array.default_initial_value_ptr)
  {
    allocate_dir(array.dir);
    copy_array(array);
  }
 
  DynArray<T> &operator = (const DynArray<T> &array)
  {
    if (this == &array)
      return *this;
 
    copy_array(array);
 
    if (array.current_dim < current_dim)
      cut(array.current_dim);
 
    current_dim = array.current_dim;
 
    return *this;
  }
 
  void swap(DynArray<T> &array) noexcept
  {
    std::swap(dir, array.dir);
    std::swap(pow_dir, array.pow_dir);
    std::swap(pow_seg, array.pow_seg);
    std::swap(pow_block, array.pow_block);
    std::swap(seg_plus_block_pow, array.seg_plus_block_pow);
    std::swap(mask_seg_plus_block, array.mask_seg_plus_block);
    std::swap(dir_size, array.dir_size);
    std::swap(seg_size, array.seg_size);
    std::swap(block_size, array.block_size);
    std::swap(mask_seg, array.mask_seg);
    std::swap(mask_block, array.mask_block);
    std::swap(max_dim, array.max_dim);
    std::swap(current_dim, array.current_dim);
    std::swap(num_segs, array.num_segs);
    std::swap(num_blocks, array.num_blocks);
 
    std::swap(default_initial_value, array.default_initial_value);
 
    default_initial_value_ptr = &default_initial_value;
    array.default_initial_value_ptr = &array.default_initial_value;
  }
 
  DynArray(DynArray &&other) noexcept
    : pow_dir(Default_Pow_Dir), pow_seg(Default_Pow_Seg),
      pow_block(std::min(Default_Pow_Block, Max_Pow_Block)), seg_plus_block_pow(pow_seg + pow_block),
      mask_seg_plus_block(two_raised(seg_plus_block_pow) - 1), dir_size(two_raised(pow_dir)),
      seg_size(two_raised(pow_seg)), block_size(two_raised(pow_block)),
      max_dim(two_raised(seg_plus_block_pow + pow_dir)), mask_seg(seg_size - 1),
      mask_block(block_size - 1), current_dim(0), num_segs(0), num_blocks(0), dir(nullptr)
  {
    default_initial_value_ptr = &default_initial_value;
    swap(other);
  }
 
  DynArray &operator = (DynArray &&other) noexcept
  {
    swap(other);
    return *this;
  }
 
  T &access(const size_t i) const noexcept
  {
    assert(dir[index_in_dir(i)] != nullptr);
    assert(dir[index_in_dir(i)][index_in_seg(i)] != nullptr);
 
    return dir[index_in_dir(i)][index_in_seg(i)][index_in_block(i)];
  }
 
  T &operator () (const size_t i) const noexcept
  {
    return access(i);
  }
 
  bool exist(const size_t i) const
  {
    if (i >= max_dim)
      return false;
 
    const size_t pos_in_dir = index_in_dir(i);
 
    assert(pos_in_dir < dir_size);
 
    if (dir[pos_in_dir] == nullptr)
      return false;
 
    const size_t pos_in_seg = index_in_seg(i);
 
    assert(pos_in_seg < seg_size);
 
    if (dir[pos_in_dir][pos_in_seg] == nullptr)
      return false;
 
    return true;
  }
 
  T *test(const size_t i) const noexcept
  {
    if (i >= max_dim)
      return nullptr;
 
    const size_t pos_in_dir = index_in_dir(i);
    if (dir[pos_in_dir] == nullptr)
      return nullptr;
 
    const size_t pos_in_seg = index_in_seg(i);
    if (dir[pos_in_dir][pos_in_seg] == nullptr)
      return nullptr;
 
    return &dir[index_in_dir(i)][index_in_seg(i)][index_in_block(i)];
  }
 
  T &touch(const size_t i)
  {
    if (i >= max_dim)
      resize_dir(i);
 
    const size_t pos_in_dir = index_in_dir(i);
    bool new_segment = false;
    if (dir[pos_in_dir] == nullptr)
      {
        allocate_segment(dir[pos_in_dir]);
        new_segment = true;
      }
 
    const size_t pos_in_seg = index_in_seg(i);
    if (dir[pos_in_dir][pos_in_seg] == nullptr)
      {
        try
          {
            allocate_block(dir[pos_in_dir][pos_in_seg]);
          }
        catch (...)
          {
            if (new_segment && dir[pos_in_dir] != nullptr)
              release_segment(dir[pos_in_dir]);
            throw;
          }
      }
 
    if (i >= current_dim)
      current_dim = i + 1;
 
    return dir[pos_in_dir][pos_in_seg][index_in_block(i)];
  }
 
  void reserve(const size_t l, const size_t r)
  {
    ah_domain_error_if(l > r) << "invalid range";
 
    if (r >= max_dim)
      resize_dir(r);
 
    const size_t first_seg = index_in_dir(l);
    const size_t last_seg = index_in_dir(r);
    const size_t first_block = index_in_seg(l);
    const size_t last_block = index_in_seg(r);
 
    // First pass: count the segments and blocks this call must allocate.
    // It keeps the common case, where the whole range already exists, free
    // of heap allocations, and it lets the rollback bookkeeping be sized
    // before anything is allocated. Recording an allocation then never
    // allocates, so it cannot fail and leave an allocation out of the
    // rollback.
    size_t missing_segs = 0;
    size_t missing_blocks = 0;
    for (size_t seg_idx = first_seg; seg_idx <= last_seg; ++seg_idx)
      {
        const size_t lo = (seg_idx == first_seg) ? first_block : 0;
        const size_t hi = (seg_idx == last_seg) ? last_block : seg_size - 1;
        if (dir[seg_idx] == nullptr)
          {
            ++missing_segs;
            missing_blocks += hi - lo + 1;
          }
        else
          for (size_t block_idx = lo; block_idx <= hi; ++block_idx)
            if (dir[seg_idx][block_idx] == nullptr)
              ++missing_blocks;
      }
 
    if (missing_blocks == 0)  // a missing segment always implies missing blocks
      {
        if (r + 1 > current_dim)
          current_dim = r + 1;
        return;
      }
 
    Array<size_t> new_segments;
    new_segments.reserve(missing_segs);
    Array<std::pair<size_t, size_t>> new_blocks;
    new_blocks.reserve(missing_blocks);
 
    try
      {
        for (size_t seg_idx = first_seg; seg_idx <= last_seg; ++seg_idx)
          {
            if (dir[seg_idx] == nullptr)
              {
                allocate_segment(dir[seg_idx]);
                new_segments.append(seg_idx);
              }
 
            size_t block_idx = (seg_idx == first_seg) ? first_block : 0;
            const size_t final_block = (seg_idx == last_seg) ? last_block : seg_size - 1;
 
            while (block_idx <= final_block)
              {
                if (dir[seg_idx][block_idx] == nullptr)
                  {
                    allocate_block(dir[seg_idx][block_idx]);
                    new_blocks.append(std::make_pair(seg_idx, block_idx));
                  }
 
                ++block_idx;
              }
          }  // end for (...)
      }
    catch (...)
      {
        for (size_t k = new_blocks.size(); k > 0; --k)
          {
            const auto [seg_idx, block_idx] = new_blocks(k - 1);
            if (dir[seg_idx] != nullptr and dir[seg_idx][block_idx] != nullptr)
              release_block(dir[seg_idx][block_idx]);
          }
 
        for (size_t k = new_segments.size(); k > 0; --k)
          if (const size_t seg_idx = new_segments(k - 1); dir[seg_idx] != nullptr)
            release_segment(dir[seg_idx]);
 
        throw;
      }
 
    if (r + 1 > current_dim)
      current_dim = r + 1;
  }
 
  void reserve(const size_t dim)
  {
    if (dim > 0)
      reserve(0, dim - 1);
  }
 
  void cut_ne(const size_t new_dim = 0)
  {
    if (new_dim == 0)
      {
        release_all_segments_and_blocks();
        current_dim = 0;
        return;
      }
 
    const size_t old_dim = current_dim;  // old dimension
 
    // segment and block first indexes
    const long idx_first_seg = index_in_dir(old_dim - 1);
    const long idx_first_block = index_in_seg(old_dim - 1);
 
    // segment and block last indexes
    const long idx_last_seg = index_in_dir(new_dim - 1);
    const long idx_last_block = index_in_seg(new_dim - 1);
    for (long idx_seg = index_in_dir(old_dim - 1); idx_seg >= idx_last_seg;
         --idx_seg)  // recorre descendentemente los segmentos
      {
        if (dir[idx_seg] == nullptr)  // ¿hay un segmento?
          continue;                   // no ==> Advance to the next
 
        long idx_block =  // First block to be released
          idx_seg == idx_first_seg ? idx_first_block : seg_size - 1;
 
        // Libera descendentemente los bloques reservados del segmento
        while ((idx_seg > idx_last_seg and idx_block >= 0) or
               (idx_seg == idx_last_seg and idx_block > idx_last_block))
          {
            if (dir[idx_seg][idx_block] != nullptr)  // ¿Hay un bloque aquí?
              release_block(dir[idx_seg][idx_block]);
 
            --idx_block;
          }
 
        if (idx_block < 0)
          release_segment(dir[idx_seg]);
      }
 
    current_dim = new_dim;  // Updates New Dimension
  }
 
  void cut(const size_t new_dim = 0)
  {
    // Only shrinking is allowed; growing must be done via adjust().
    // If new_dim equals current_dim, this is a no-op and we return early.
    ah_length_error_if(new_dim > current_dim) << "new dimension greater than current dimension";
 
    if (new_dim == current_dim)
      return;
 
    cut_ne(new_dim);
  }
 
  void adjust(const size_t dim)
  {
    if (dim > current_dim)
      reserve(dim);
    else
      cut(dim);
  }
 
  void empty() noexcept
  {
    cut(0);
  }
 
  void clear() noexcept
  {
    empty();
  }
 
  Proxy operator [] (const size_t i) const
  {
    ah_out_of_range_error_if(i >= max_dim) << "index out of maximum range";
 
    return Proxy(const_cast<DynArray<T> &>(*this), i);
  }
 
  Proxy operator [] (const size_t i)
  {
    if (i >= max_dim)
      resize_dir(i);
 
    return Proxy(const_cast<DynArray<T> &>(*this), i);
  }
 
  T &append()
  {
    return touch(this->size());
  }
 
  T &append(const T &data)
  {
    T &ref = this->append();
    ref = data;
    return ref;
  }
 
  T &append(T &&data)
  {
    T &ref = this->append();
    ref = std::move(data);
    return ref;
  }
 
  T &insert(const T &item)
  {
    this->append();
    open_gap(*this, current_dim);
    T &ret = access(0);
    ret = item;
    return ret;
  }
 
  T &insert(T &&item)
  {
    this->append();
    open_gap(*this, current_dim);
    T &ret = access(0);
    ret = std::forward<T>(item);
    return ret;
  }
 
  void push(const T &data)
  {
    this->append(data);
  }
 
  T &push(T &&data)
  {
    return this->append(std::forward<T>(data));
  }
 
  void put(const T &data)
  {
    this->append(data);
  }
 
  T &put(T &&data)
  {
    return this->append(std::forward<T>(data));
  }
 
  void remove(T &item)
  {
    ensure_not_empty("DynArray::remove(): empty array");
    std::swap(item, this->access(this->size() - 1));
    this->cut_ne(this->size() - 1);
  }
 
  void erase(T &item)
  {
    remove(item);
  }
 
  bool is_empty() const noexcept
  {
    return this->size() == 0;
  }
 
  Array<T> to_array() const
    requires std::copy_constructible<T>
  {
    Array<T> ret;
    ret.reserve(this->size());
    for (size_t i = 0; i < this->size(); ++i)
      ret.append(this->access(i));
    return ret;
  }
 
  DynArray &reverse()
  {
    if (current_dim < 2)
      return *this;
 
    for (size_t i = 0, j = current_dim - 1; i < j; ++i, --j)
      std::swap(touch(i), touch(j));
 
    return *this;
  }
 
  T pop()
  {
    ensure_not_empty("DynArray::pop(): empty array");
    T ret_val = std::move(this->access(this->size() - 1));
    cut(size() - 1);
 
    return ret_val;
  }
 
  T &top() const
  {
    ensure_not_empty("DynArray::top(): empty array");
    return (*this)[size() - 1];
  }
 
  T &get_first() const
  {
    ensure_not_empty("DynArray::get_first(): empty array");
    return (*this)[0];
  }
 
  T &get_last() const
  {
    ensure_not_empty("DynArray::get_last(): empty array");
    return (*this)[size() - 1];
  }
 
  class Iterator
  {
  protected:
    DynArray *array_ptr = nullptr;
    long curr_idx = 0;
 
  public:
    using Set_Type = DynArray;
 
    using aleph_random_access_iterator = Iterator;
 
    Iterator() noexcept = default;
 
    Iterator(const DynArray &array) noexcept : array_ptr(const_cast<DynArray *>(&array))
    {
      // empty
    }
 
    [[nodiscard]] bool has_curr() const noexcept
    {
      return array_ptr != nullptr and curr_idx >= 0 and
             static_cast<size_t>(curr_idx) < array_ptr->size();
    }
 
    [[nodiscard]] bool is_last() const noexcept
    {
      const long n = array_ptr == nullptr ? 0 : static_cast<long>(array_ptr->size());
      return has_curr() and curr_idx == n - 1;
    }
 
    T &get_curr_ne() const noexcept
    {
      return array_ptr->access(curr_idx);
    }
 
    T &get_curr() const
    {
      ah_underflow_error_if(curr_idx < 0) << "not current item in iterator";
      ah_overflow_error_if(array_ptr == nullptr or
                           static_cast<size_t>(curr_idx) >= array_ptr->size())
        << "not current item in iterator";
      return get_curr_ne();
    }
 
    [[nodiscard]] long get_pos() const noexcept
    {
      return curr_idx;
    }
 
    void next_ne() noexcept
    {
      ++curr_idx;
    }
 
    void next()
    {
      ah_overflow_error_if(array_ptr == nullptr or
                           (curr_idx >= 0 and
                            static_cast<size_t>(curr_idx) >= array_ptr->size()))
        << "not current item in iterator";
      next_ne();
    }
 
    // Move the iterator one position backward guaranteeing no
    void prev_ne() noexcept
    {
      --curr_idx;
    }
 
    void prev()
    {
      ah_underflow_error_if(curr_idx == -1) << "not current item in iterator";
      prev_ne();
    }
 
    void reset_last() noexcept
    {
      curr_idx = array_ptr == nullptr ? -1 : static_cast<long>(array_ptr->size()) - 1;
    }
 
    void end() noexcept
    {
      curr_idx = array_ptr == nullptr ? 0 : static_cast<long>(array_ptr->size());
    }
 
    void reset_first() noexcept
    {
      curr_idx = 0;
    }
 
    void set_pos(const long pos) noexcept
    {
      curr_idx = pos;
    }
  };
 
  Iterator get_it()
  {
    return Iterator(*this);
  }
 
  Iterator get_it() const
  {
    return Iterator(*this);
  }
 
  Iterator get_it(const size_t pos)
  {
    ah_out_of_range_error_if(pos >= size()) << "DynArray::get_it(pos): pos >= size()";
    Iterator it(*this);
    it.set_pos(static_cast<long>(pos));
    return it;
  }
 
  Iterator get_it(const size_t pos) const
  {
    return const_cast<DynArray *>(this)->get_it(pos);
  }
 
private:
  // superfast array traversal
  template <class Operation>
  bool __traverse(Operation &operation)
  {
    size_t dir_idx = 0, seg_idx = 0, block_idx = 0;
    for (size_t i = 0; i < current_dim; ++i)
      {
        if (not operation(dir[dir_idx][seg_idx][block_idx]))
          return false;
 
        if (++block_idx == block_size)
          {
            block_idx = 0;
            if (++seg_idx == seg_size)
              {
                seg_idx = 0;
                ++dir_idx;
              }
          }
      }
    return true;
  }
 
public:
  template <class Operation>
  bool traverse(Operation &operation) const
  {
    return const_cast<DynArray &>(*this).__traverse(operation);
  }
 
  template <class Operation>
  bool traverse(Operation &operation)
  {
    return __traverse(operation);
  }
 
  template <class Operation>
  bool traverse(Operation &&operation) const
  {
    return traverse<Operation>(operation);
  }
 
  template <class Operation>
  bool traverse(Operation &&operation)
  {
    return traverse<Operation>(operation);
  }
};
 
template <typename T>
const size_t DynArray<T>::Default_Pow_Dir = 6; /* 64   */
 
template <typename T>
const size_t DynArray<T>::Default_Pow_Seg = 8; /* 256   */
 
template <typename T>
const size_t DynArray<T>::Default_Pow_Block = 12; /* 4096 */
 
template <typename T>
const size_t DynArray<T>::Max_Bits_Allowed = 8 * sizeof(size_t);
 
template <typename T>
const unsigned long long DynArray<T>::Max_Dim_Allowed = 256 * 1024 * 1024 * 1024ull;  // 256 Gb
 
template <typename T>
const size_t DynArray<T>::Max_Pow_Block = (Max_Bits_Allowed - Default_Pow_Dir - Default_Pow_Seg - 1);
}  // end namespace Aleph
 
#endif /* TPL_DYNARRAY_H */