Created
February 21, 2020 17:49
-
-
Save schveiguy/962e36cea6a979a47b708cb4335f9f82 to your computer and use it in GitHub Desktop.
Another recursive range possibility, using simple linked-list stack.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import std.range; | |
struct StackFrame(T) | |
{ | |
StackFrame* prev; | |
T range; | |
} | |
struct StackRange(T, alias recurse) if (isInputRange!(typeof(recurse(T.init)))) | |
{ | |
alias Range = typeof(recurse(T.init)); | |
StackFrame!Range* cur; | |
T front() { return cur.range.front; } | |
bool empty() { return cur is null; } | |
void popFront() | |
{ | |
assert(cur !is null); | |
auto r = recurse(cur.range.front); | |
cur.range.popFront; | |
if (!r.empty) | |
{ | |
cur = new StackFrame!Range(cur, r); | |
} | |
else | |
{ | |
// "return" up the stack frame until we find a non-empty range | |
while (cur && cur.range.empty) | |
cur = cur.prev; | |
} | |
} | |
} | |
auto getRecursive(alias fn, T)(T root) | |
{ | |
StackRange!(T, fn) sr; | |
auto range = fn(root); | |
if (!range.empty) | |
sr.cur = new StackFrame!(sr.Range)(null, range); | |
return chain(only(root), sr); | |
} | |
/// create some deeply nested nodes | |
private Node getNode() | |
{ | |
Node node1; | |
node1.name = "Node A"; | |
node1.numbers = [1]; | |
Node node2; | |
node2.name = "Node B"; | |
node2.numbers = [2]; | |
Node node3; | |
node3.name = "Node C"; | |
node3.numbers = [3]; | |
Node node4; | |
node4.name = "Node D"; | |
node4.numbers = [4]; | |
Node node5; | |
node5.name = "Node E"; | |
node5.numbers = [5]; | |
Node node6; | |
node6.name = "Node F"; | |
node6.numbers = [6]; | |
Node node7; | |
node7.name = "Node G"; | |
node7.numbers = [7]; | |
node3.nodes = [node6, node7]; | |
node2.nodes = [node4, node5]; | |
node1.nodes = [node2, node3]; | |
return node1; | |
} | |
struct Node | |
{ | |
string name; | |
int[] numbers; | |
Node[] nodes; | |
} | |
void main() | |
{ | |
import std.algorithm; | |
import std.stdio; | |
auto node = getNode(); | |
auto r = node.getRecursive!(n => n.nodes) | |
.map!(n => n.numbers); | |
r.each!(numbers => writeln(numbers)); | |
auto r2 = node.getRecursive!(n => n.nodes) | |
.map!(n => n.name); | |
r2.each!(name => writeln(name)); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment