#include <cassert>
#include <array>
#include <stdexcept>
#include <vector>
#include <iostream>
namespace meta_array
{
template<typename type_t, std::size_t N> class meta_array_t;
// template internal class not for public use.
namespace details
{
// a block contains the meta information on a subarray within the meta_array
template<typename type_t, std::size_t N>
class meta_array_block_t
{
public:
// the iterator within a block is of the same type as that of the containing array
using iterator_t = typename std::array<type_t, N>::iterator;
/// <summary>
///
/// </summary>
/// <param name="parent">parent, this link is needed if blocks need to move within the parent array</param>
/// <param name="begin">begin iterator of the block</param>
/// <param name="end">end iterator of the block (one past last)</param>
/// <param name="size">cached size (to not have to calculate it from iterator differences)</param>
meta_array_block_t(meta_array_t<type_t, N>& parent, const iterator_t& begin, const iterator_t& end, std::size_t size) :
m_parent{ parent },
m_begin{ begin },
m_end{ end },
m_size{ size }
{
}
// the begin and end methods allow a block to be used in a range based for loop
iterator_t begin() const noexcept
{
return m_begin;
}
iterator_t end() const noexcept
{
return m_end;
}
// operation to shrink the size of the last free block in the meta-array
void move_begin(std::size_t n) noexcept
{
assert(n <= m_size);
m_size -= n;
m_begin += n;
}
// operation to move a block n items back in the meta array
void move_to_back(std::size_t n) noexcept
{
m_begin += n;
m_end += n;
}
std::size_t size() const noexcept
{
return m_size;
}
// assign a new array to the sub array
// if the new array is bigger then the array that is already there
// then move the blocks after it toward the end of the meta-array
template<std::size_t M>
meta_array_block_t& operator=(const type_t(&values)[M])
{
// move all other sub-arrays back if the new sub-array is bigger
// if it is smaller then adjusting the end iterator of the block is fine
if (M > m_size)
{
m_parent.move_back(m_end, M - m_size);
}
m_size = M;
// copy will do the right thing (copy from back to front) if needed
std::copy(std::begin(values), std::end(values), m_begin);
m_end = m_begin + m_size;
return *this;
}
private:
meta_array_t<type_t, N>& m_parent;
std::size_t m_index;
iterator_t m_begin;
iterator_t m_end;
std::size_t m_size;
};
} // details
//---------------------------------------------------------------------------------------------------------------------
//
template<typename type_t, std::size_t N>
class meta_array_t final
{
public:
meta_array_t() :
m_free_size{ N },
m_size{ 0ul },
m_last_free_block{ *this, m_buffer.begin(), m_buffer.end(), N }
{
}
~meta_array_t() = default;
// meta_array is non copyable & non moveable
meta_array_t(const meta_array_t&) = delete;
meta_array_t operator=(const meta_array_t&) = delete;
meta_array_t(meta_array_t&&) = delete;
meta_array_t operator=(meta_array_t&&) = delete;
// return the number of subarrays
std::size_t array_count() const noexcept
{
return m_size;
}
// return number of items that can still be allocated
std::size_t free_size() const noexcept
{
return m_free_size;
}
template<std::size_t M>
std::size_t push_back(const type_t(&values)[M])
{
auto block = allocate(M);
std::copy(std::begin(values), std::end(values), block.begin());
return m_blocks.size();
}
auto begin()
{
return m_blocks.begin();
}
auto end()
{
return m_blocks.end();
}
auto& operator[](const std::size_t index)
{
assert(index < m_size);
return m_blocks[index];
}
private:
friend class details::meta_array_block_t<type_t, N>;
void move_back(std::array<type_t,N>::iterator begin, std::size_t offset)
{
std::copy(begin, m_buffer.end() - offset - 1, begin + offset);
// update block administation
for (auto& block : m_blocks)
{
if (block.begin() >= begin )
{
block.move_to_back(offset);
}
}
}
auto allocate(std::size_t size)
{
if ((size == 0ul) || (size > m_free_size)) throw std::bad_alloc();
if (m_last_free_block.size() < size)
{
compact();
}
m_blocks.push_back({ *this, m_last_free_block.begin(), m_last_free_block.begin() + size, size });
m_last_free_block.move_begin(size);
m_free_size -= size;
m_size++;
return m_blocks.back();
}
void compact()
{
assert(false); // not implemented yet
// todo when a gap is found between 2 sub-arrays (compare begin/end iterators) then move
// the next array to the front
// the array after that will move to the front by the sum of the gaps ... etc...
}
std::array<type_t, N> m_buffer;
std::vector<details::meta_array_block_t<type_t,N>> m_blocks;
details::meta_array_block_t<type_t,N> m_last_free_block;
std::size_t m_size;
std::size_t m_free_size;
};
} // meta_array
//---------------------------------------------------------------------------------------------------------------------
#define ASSERT_TRUE(x) assert(x);
#define ASSERT_FALSE(x) assert(!x);
#define ASSERT_EQ(x,y) assert(x==y);
static constexpr std::size_t test_buffer_size = 16;
template<typename type_t, std::size_t N>
void show_arrays(meta_array::meta_array_t<type_t, N>& meta_array)
{
std::cout << "\n--- meta_array ---\n";
for (const auto& sub_array : meta_array)
{
std::cout << "sub array = ";
auto comma = false;
for (const auto& value : sub_array)
{
if (comma) std::cout << ", ";
std::cout << value;
comma = true;
}
std::cout << "\n";
}
}
void test_construction()
{
meta_array::meta_array_t<int, test_buffer_size> meta_array;
ASSERT_EQ(meta_array.array_count(),0ul);
ASSERT_EQ(meta_array.free_size(),test_buffer_size);
}
void test_push_back_success()
{
meta_array::meta_array_t<int, test_buffer_size> meta_array;
meta_array.push_back({ 1,2,3 });
meta_array.push_back({ 14,15 });
meta_array.push_back({ 26,27,28,29 });
ASSERT_EQ(meta_array.array_count(),3ul); // cont
ASSERT_EQ(meta_array.free_size(),(test_buffer_size-9ul));
}
void test_range_based_for()
{
meta_array::meta_array_t<int, test_buffer_size> meta_array;
meta_array.push_back({ 1,2,3 });
meta_array.push_back({ 14,15 });
meta_array.push_back({ 26,27,28,29 });
show_arrays(meta_array);
}
void test_assignment()
{
meta_array::meta_array_t<int, test_buffer_size> meta_array;
meta_array.push_back({ 1,2,3 });
meta_array.push_back({ 4,5,6 });
meta_array.push_back({ 7,8,9 });
meta_array[0] = { 11,12 }; // replace with a smaller array then what there was
meta_array[1] = { 21,22,23,24 }; // replace with a bigger array then there was
show_arrays(meta_array);
}
//---------------------------------------------------------------------------------------------------------------------
int main()
{
test_construction();
test_push_back_success();
test_range_based_for();
test_assignment();
return 0;
}
