128 lines
2.6 KiB
C++
128 lines
2.6 KiB
C++
|
|
#include <stddef.h>
|
|
#include <assert.h>
|
|
|
|
#include <type_traits>
|
|
#include <utility>
|
|
|
|
template <
|
|
typename T> class quack
|
|
{
|
|
public:
|
|
T* data = NULL;
|
|
size_t i = 0, n = 0, cap = 0;
|
|
|
|
private:
|
|
void helper()
|
|
{
|
|
;
|
|
}
|
|
|
|
template <typename first, typename ...rest>
|
|
void helper(first f, rest... r)
|
|
{
|
|
append(f);
|
|
|
|
helper(r...);
|
|
}
|
|
|
|
public:
|
|
quack()
|
|
{
|
|
;
|
|
}
|
|
|
|
template <typename ...all>
|
|
quack(all... a)
|
|
{
|
|
helper(a...);
|
|
}
|
|
|
|
void append(T item)
|
|
{
|
|
if (n == cap)
|
|
{
|
|
cap = cap << 1 ?: 1;
|
|
|
|
if constexpr (std::is_trivially_copyable_v<T>)
|
|
{
|
|
data = (T*) realloc(data, sizeof(*data) * cap);
|
|
|
|
if (i)
|
|
{
|
|
memmove(
|
|
/* dest: */ data + cap - (n - i),
|
|
/* src: */ data + i,
|
|
/* len: */ (n - i) * sizeof(T));
|
|
|
|
i = cap - (n - i);
|
|
}
|
|
}
|
|
else
|
|
{
|
|
if (i)
|
|
{
|
|
assert(!"TODO");
|
|
}
|
|
else
|
|
{
|
|
T* new_data = new T[cap]();
|
|
|
|
for (size_t i = 0; i < n; i++)
|
|
{
|
|
new_data[i] = std::move(data[i]);
|
|
}
|
|
|
|
delete[] data;
|
|
|
|
data = new_data;
|
|
}
|
|
}
|
|
}
|
|
|
|
data[(i + n++) % cap] = std::move(item);
|
|
}
|
|
|
|
T pop()
|
|
{
|
|
assert(n);
|
|
|
|
assert(i < cap);
|
|
|
|
T retval = data[i];
|
|
|
|
if (i + 1 == cap)
|
|
i = 0;
|
|
else
|
|
i++;
|
|
|
|
n--;
|
|
|
|
return retval;
|
|
}
|
|
|
|
~quack()
|
|
{
|
|
if (std::is_trivially_copyable_v<T>)
|
|
{
|
|
free(data);
|
|
}
|
|
else
|
|
{
|
|
delete[] data;
|
|
}
|
|
}
|
|
};
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|