Skip to content

Instantly share code, notes, and snippets.

@schveiguy
Created February 21, 2020 17:49
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save schveiguy/962e36cea6a979a47b708cb4335f9f82 to your computer and use it in GitHub Desktop.
Save schveiguy/962e36cea6a979a47b708cb4335f9f82 to your computer and use it in GitHub Desktop.
Another recursive range possibility, using simple linked-list stack.
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