import std.stdio;
void forward(const DList!int l) {
if (l.empty()) return;
writeln(l.front);
forward(l.popFront());
}
void backward(const DList!int l) {
if (l.empty()) return;
writeln(l.back);
backward(l.popBack());
}
void forwardBackward(const DList!int l) {
forward(l);
backward(l.popBack());
}
void backwardForward(const DList!int l) {
backward(l);
forward(l.popFront());
}
void main() {
const list = DList!int().append(1, 2, 3, 4);
writeln("forwardBackward");
forwardBackward(list);
writeln("backwardForward");
backwardForward(list);
}
struct DList(T) {
struct Node {
T delegate() payload;
Node* prev, next;
}
private Node* m_first, m_last;
bool empty() const { return m_first == null; }
T front() const { assert(!empty); return m_first.payload(); }
T back() const { assert(!empty); return m_last.payload(); }
const(DList) popFront() const {
assert(!empty);
return m_first == m_last ? const DList() : const DList(m_first.next, m_last);
}
const(DList) popBack() const {
assert(!empty);
return m_first == m_last ? const DList() : const DList(m_first, m_last.prev);
}
const(DList) append(ARGS...)(lazy ARGS args) const {
auto list = dup();
static foreach(arg; args) {
if(list.empty) {
list.m_first = list.m_last = new Node(&arg);
} else {
list.m_last.next = new Node(&arg, list.m_last);
list.m_last = list.m_last.next;
}
}
return list;
}
private DList dup() const {
auto list = DList();
if(!empty) {
auto prev = new Node(m_first.payload);
list.m_first = prev;
const(Node)* cur = m_first.next;
while(cur != null && cur != m_last) {
auto node = new Node(cur.payload, prev);
prev.next = node;
prev = node;
cur = cur.next;
}
list.m_last = prev;
}
return list;
}
}
