401 lines
8.0 KiB
C++
401 lines
8.0 KiB
C++
#pragma once
|
|
|
|
#include <cstddef>
|
|
#include <iterator>
|
|
#include <utility.h>
|
|
|
|
namespace container
|
|
{
|
|
|
|
using CapacityType = index_t;
|
|
using BoolArrayType = u8;
|
|
|
|
template<typename T, CapacityType capacity>
|
|
class StackArray
|
|
{
|
|
public:
|
|
using data_type = T;
|
|
using pointer = data_type*;
|
|
using reference = data_type&;
|
|
using const_pointer = const data_type*;
|
|
using const_reference = const data_type&;
|
|
|
|
|
|
public:
|
|
class iterator
|
|
{
|
|
public:
|
|
using value_type = data_type;
|
|
using reference = value_type&;
|
|
using difference_type = std::ptrdiff_t;
|
|
using iterator_category = std::forward_iterator_tag;
|
|
|
|
iterator(data_type* input)
|
|
: m_ptr(input)
|
|
{ }
|
|
|
|
iterator& operator++()
|
|
{ m_ptr++; return *this; }
|
|
|
|
iterator operator++(int)
|
|
{ auto it = *this; m_ptr++; return it; }
|
|
|
|
iterator& operator--()
|
|
{ m_ptr--; return *this; }
|
|
|
|
iterator operator--(int)
|
|
{ auto it = *this; m_ptr--; return it; }
|
|
|
|
|
|
pointer operator->() const { return m_ptr; }
|
|
reference operator*() const { return *m_ptr; }
|
|
reference operator[](CapacityType index) const { return m_ptr[index]; }
|
|
|
|
bool operator==(iterator other) const { return m_ptr == other.m_ptr; }
|
|
bool operator!=(iterator other) const { return m_ptr != other.m_ptr; }
|
|
private:
|
|
pointer m_ptr;
|
|
};
|
|
|
|
class const_iterator
|
|
{
|
|
public:
|
|
using value_type = data_type;
|
|
using reference = value_type&;
|
|
using difference_type = std::ptrdiff_t;
|
|
using iterator_category = std::forward_iterator_tag;
|
|
|
|
const_iterator(const_pointer input)
|
|
: m_ptr(input)
|
|
{ }
|
|
|
|
const_iterator& operator++()
|
|
{ m_ptr++; return *this; }
|
|
|
|
const_iterator operator++(int)
|
|
{ auto it = *this; m_ptr++; return it; }
|
|
|
|
const_iterator& operator--()
|
|
{ m_ptr--; return *this; }
|
|
|
|
const_iterator operator--(int)
|
|
{ auto it = *this; m_ptr--; return it; }
|
|
|
|
const_pointer operator->() const { return m_ptr; }
|
|
const_reference operator*() const { return *m_ptr; }
|
|
const_reference operator[](CapacityType index) const { return m_ptr[index]; }
|
|
|
|
bool operator==(const_iterator other) const { return m_ptr == other.m_ptr; }
|
|
bool operator!=(const_iterator other) const { return m_ptr != other.m_ptr; }
|
|
|
|
private:
|
|
const_pointer m_ptr;
|
|
};
|
|
|
|
public:
|
|
StackArray() = default;
|
|
|
|
pointer data() { return &m_data[0]; }
|
|
|
|
pointer operator->() { return m_data; }
|
|
reference operator*() { return *m_data; }
|
|
reference operator[](CapacityType index) { return m_data[index]; }
|
|
|
|
const_pointer data() const {return &m_data[0]; }
|
|
|
|
const_pointer operator->() const { return m_data; }
|
|
const_reference operator*() const { return *m_data; }
|
|
const_reference operator[](CapacityType index) const { return m_data[index]; }
|
|
|
|
inline constexpr CapacityType size() const { return capacity; }
|
|
|
|
void swap(index_t first, index_t second)
|
|
{
|
|
auto temp = m_data[first];
|
|
m_data[first] = m_data[second];
|
|
m_data[second] = temp;
|
|
}
|
|
|
|
iterator begin() { return iterator(data()); }
|
|
iterator end() { return iterator(data() + capacity); }
|
|
|
|
const_iterator begin() const { return const_iterator(data()); }
|
|
const_iterator end() const { return const_iterator(data() + capacity); }
|
|
|
|
private:
|
|
data_type m_data[capacity]{};
|
|
|
|
};
|
|
|
|
|
|
template <CapacityType capacity>
|
|
class StackArray<bool, capacity>
|
|
{
|
|
public:
|
|
class reference;
|
|
using pointer = reference;
|
|
using const_reference = bool;
|
|
using data_type = BoolArrayType;
|
|
using iterator_category = std::forward_iterator_tag;
|
|
using difference_type = std::ptrdiff_t;
|
|
|
|
public:
|
|
class reference
|
|
{
|
|
public:
|
|
reference(data_type* ptr_in, data_type mask_in)
|
|
: m_ptr(ptr_in)
|
|
, m_mask(mask_in)
|
|
{ }
|
|
|
|
reference(reference&) = default;
|
|
|
|
operator bool () const
|
|
{ return !!(*m_ptr & m_mask); }
|
|
|
|
reference& operator=(bool input)
|
|
{
|
|
if (input == true)
|
|
{
|
|
*m_ptr |= m_mask;
|
|
}
|
|
else
|
|
{
|
|
*m_ptr &= ~m_mask;
|
|
}
|
|
|
|
return *this;
|
|
}
|
|
|
|
reference& operator=(const reference& other) { return *this = bool(other); }
|
|
|
|
void flip() { *m_ptr ^= m_mask; }
|
|
|
|
void setTrue() { *m_ptr |= m_mask; }
|
|
|
|
void setFalse() { *m_ptr &= ~m_mask; }
|
|
|
|
private:
|
|
data_type* const m_ptr;
|
|
const data_type m_mask;
|
|
};
|
|
|
|
class iterator
|
|
{
|
|
public:
|
|
iterator(data_type* input, data_type index)
|
|
: m_ptr(input)
|
|
, m_bitIndex(index)
|
|
{ }
|
|
|
|
iterator& operator++()
|
|
{
|
|
switch (m_bitIndex++)
|
|
{
|
|
case 7:
|
|
m_bitIndex = 0;
|
|
m_ptr++;
|
|
return *this;
|
|
break;
|
|
|
|
default:
|
|
return *this;
|
|
}
|
|
}
|
|
|
|
iterator operator++(int)
|
|
{
|
|
auto it = *this;
|
|
switch (m_bitIndex++)
|
|
{
|
|
case 7:
|
|
m_bitIndex = 0;
|
|
m_ptr++;
|
|
return it;
|
|
break;
|
|
|
|
default:
|
|
return it;
|
|
}
|
|
}
|
|
|
|
iterator& operator--()
|
|
{
|
|
switch (m_bitIndex--)
|
|
{
|
|
case 0:
|
|
m_bitIndex = 7;
|
|
m_ptr--;
|
|
return *this;
|
|
break;
|
|
|
|
default:
|
|
return *this;
|
|
}
|
|
}
|
|
|
|
iterator operator--(int)
|
|
{
|
|
auto it = *this;
|
|
switch (m_bitIndex--)
|
|
{
|
|
case 0:
|
|
m_bitIndex = 7;
|
|
m_ptr--;
|
|
return it;
|
|
break;
|
|
|
|
default:
|
|
return it;
|
|
}
|
|
}
|
|
|
|
reference operator[](CapacityType index) const
|
|
{ return reference(m_ptr + (index / 7), m_bitIndex + (index % 8)); }
|
|
|
|
reference operator*() const
|
|
{ return reference(m_ptr, 1 << m_bitIndex); }
|
|
|
|
bool operator==(const iterator& other) const
|
|
{ return (m_ptr == other.m_ptr) && (m_bitIndex == other.m_bitIndex); }
|
|
|
|
bool operator!=(const iterator& other) const
|
|
{ return (m_ptr != other.m_ptr) || (m_bitIndex != other.m_bitIndex); }
|
|
|
|
private:
|
|
data_type* m_ptr;
|
|
data_type m_bitIndex{};
|
|
};
|
|
|
|
class const_iterator
|
|
{
|
|
public:
|
|
const_iterator(const data_type* input, data_type index)
|
|
: m_ptr(input)
|
|
, m_bitIndex(index)
|
|
{ }
|
|
|
|
const_iterator& operator++()
|
|
{
|
|
switch (m_bitIndex++)
|
|
{
|
|
case 7:
|
|
m_bitIndex = 0;
|
|
m_ptr++;
|
|
return *this;
|
|
break;
|
|
|
|
default:
|
|
return *this;
|
|
}
|
|
}
|
|
|
|
const_iterator operator++(int)
|
|
{
|
|
auto it = *this;
|
|
switch (m_bitIndex++)
|
|
{
|
|
case 7:
|
|
m_bitIndex = 0;
|
|
m_ptr++;
|
|
return it;
|
|
break;
|
|
|
|
default:
|
|
return it;
|
|
}
|
|
}
|
|
|
|
const_iterator& operator--()
|
|
{
|
|
switch (m_bitIndex--)
|
|
{
|
|
case 0:
|
|
m_bitIndex = 7;
|
|
m_ptr--;
|
|
return *this;
|
|
break;
|
|
|
|
default:
|
|
return *this;
|
|
}
|
|
}
|
|
|
|
const_iterator operator--(int)
|
|
{
|
|
auto it = *this;
|
|
switch (m_bitIndex--)
|
|
{
|
|
case 0:
|
|
m_bitIndex = 7;
|
|
m_ptr--;
|
|
return it;
|
|
break;
|
|
|
|
default:
|
|
return it;
|
|
}
|
|
}
|
|
|
|
const_reference operator[](CapacityType index) const
|
|
{ return (*m_ptr + (index / 8)) & (1 << (index % 8)); }
|
|
|
|
const_reference operator*() const
|
|
{ return *m_ptr & (1 << m_bitIndex); }
|
|
|
|
bool operator==(const const_iterator& other) const
|
|
{ return (m_ptr == other.m_ptr) && (m_bitIndex == other.m_bitIndex); }
|
|
|
|
|
|
bool operator!=(const const_iterator& other) const
|
|
{ return (m_ptr != other.m_ptr) || (m_bitIndex != other.m_bitIndex); }
|
|
|
|
private:
|
|
const data_type* m_ptr;
|
|
data_type m_bitIndex{};
|
|
};
|
|
|
|
public:
|
|
StackArray() = default;
|
|
|
|
reference operator[](CapacityType index)
|
|
{ return reference(m_data + (index / 8), 1 << (index % 8)); }
|
|
|
|
const_reference operator[](CapacityType index) const
|
|
{ return m_data[index / 8] & (1 << (index % 8)); }
|
|
|
|
data_type* data() { return &m_data[0]; }
|
|
|
|
const data_type* data() const { return &m_data[0]; }
|
|
|
|
inline constexpr CapacityType size() { return capacity; }
|
|
|
|
const_reference readAt(CapacityType index) const
|
|
{ return m_data[index / 8] & (1 << (index % 8)); }
|
|
|
|
void setTrueAt(CapacityType index)
|
|
{ m_data[index / 8] |= (1 << (index % 8)); }
|
|
|
|
void setFalseAt(CapacityType index)
|
|
{ m_data[index / 8] &= ~(1 << (index % 8)); }
|
|
|
|
void swap(index_t first, index_t second)
|
|
{
|
|
auto firstElem = reference(m_data + (first / 8), 1 << (first % 8));
|
|
auto secondElem = reference(m_data + (second / 8), 1 << (second % 8));
|
|
bool temp = firstElem;
|
|
firstElem = secondElem;
|
|
secondElem = temp;
|
|
}
|
|
|
|
iterator begin() { return iterator(data(), 0); }
|
|
iterator end() { return iterator(data() + (capacity / 8), capacity % 8); }
|
|
|
|
const_iterator begin() const { return const_iterator(data(), 0); }
|
|
const_iterator end() const { return const_iterator(data() + (capacity / 8), capacity % 8); }
|
|
|
|
private:
|
|
data_type m_data[(capacity / 9) + 1]{};
|
|
};
|
|
|
|
}//namespace
|