76 lines
1.9 KiB
D
76 lines
1.9 KiB
D
module queue_usage2;
|
|
|
|
import std.traits: hasIndirections;
|
|
|
|
struct GrowableCircularQueue(T) {
|
|
public size_t length;
|
|
private size_t first, last;
|
|
private T[] A = [T.init];
|
|
|
|
this(T[] items...) pure nothrow @safe {
|
|
foreach (x; items)
|
|
push(x);
|
|
}
|
|
|
|
@property bool empty() const pure nothrow @safe @nogc {
|
|
return length == 0;
|
|
}
|
|
|
|
@property T front() pure nothrow @safe @nogc {
|
|
assert(length != 0);
|
|
return A[first];
|
|
}
|
|
|
|
T opIndex(in size_t i) pure nothrow @safe @nogc {
|
|
assert(i < length);
|
|
return A[(first + i) & (A.length - 1)];
|
|
}
|
|
|
|
void push(T item) pure nothrow @safe {
|
|
if (length >= A.length) { // Double the queue.
|
|
immutable oldALen = A.length;
|
|
A.length *= 2;
|
|
if (last < first) {
|
|
A[oldALen .. oldALen + last + 1] = A[0 .. last + 1];
|
|
static if (hasIndirections!T)
|
|
A[0 .. last + 1] = T.init; // Help for the GC.
|
|
last += oldALen;
|
|
}
|
|
}
|
|
last = (last + 1) & (A.length - 1);
|
|
A[last] = item;
|
|
length++;
|
|
}
|
|
|
|
@property T pop() pure nothrow @safe @nogc {
|
|
assert(length != 0);
|
|
auto saved = A[first];
|
|
static if (hasIndirections!T)
|
|
A[first] = T.init; // Help for the GC.
|
|
first = (first + 1) & (A.length - 1);
|
|
length--;
|
|
return saved;
|
|
}
|
|
}
|
|
|
|
version (queue_usage2_main) {
|
|
void main() {
|
|
GrowableCircularQueue!int q;
|
|
q.push(10);
|
|
q.push(20);
|
|
q.push(30);
|
|
assert(q.pop == 10);
|
|
assert(q.pop == 20);
|
|
assert(q.pop == 30);
|
|
assert(q.empty);
|
|
|
|
uint count = 0;
|
|
foreach (immutable i; 1 .. 1_000) {
|
|
foreach (immutable j; 0 .. i)
|
|
q.push(count++);
|
|
foreach (immutable j; 0 .. i)
|
|
q.pop;
|
|
}
|
|
}
|
|
}
|