online compiler and debugger for c/c++

#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; }