On Monday, 13 May 2024 at 15:07:39 UTC, Andy Valencia wrote:
Representing the FIFO as a linked list clearly has its cost,
but I found the increased system time interesting. OS memory
allocations maybe?
I know you want FIFO, I usually keep this on hand for fixed size
LIFO; It can easily convert to FIFO and doesn't use LinkedList:
```d
class LIFO(T)
{
T * element;
size_t length, size;
this(size_t s) {
element = cast(T*)new T[s];
length = s;
}
auto rewind() => size = length;
bool empty() => !size;
auto front() => element[size - 1];
auto popFront() => --size;
auto pop() => empty ? T(0) : element[--size];
alias push = insertFront;
auto insertFront(T value)
in(size < length, "Stack is overflow!")
=> element[size++] = value;
auto ref opDollar() => length;
auto ref opIndex(size_t i) => element[i];
auto ref opSlice(size_t first, size_t last)
=> element[first..last];
} unittest {
enum test = 7;
auto stack = new LIFO!size_t(test);
assert(!stack.size);
foreach (prime; 1..test + 1)
{
stack.insertFront(prime);
}
assert(stack.size == test); // == 7
stack.writeln(": ", stack.length); // [7, 6, 5, 4, 3, 2, 1]: 7
stack[$/2].writeln("-", stack[0]); // 4-1
stack.rewind();
stack.size.write(": ["); // 10:
while (auto next = stack.pop)
{
if (next == 1) next.writeln("]");
else next.write(", ");
}
stack.size.writeln; // 0
stack.rewind();
assert(stack.size == test);
}
SDB@79
