K-d tree: Difference between revisions

Line 438:

This version performs less lookups. Compiled with DMD this version is two times slower than the C version. Compiled with ldc2 it's a little faster than the C version compiled with gcc.

<lang d>import std.stdio, std.algorithm, std.math, std.random, std.~~typetuple~~;

<lang d>import std.stdio, std.algorithm, std.math, std.random, std.typecons;

enum maxDim = 3;

template Iota(int stop) {

static if (stop <= 0)

alias Iota = TypeTuple!();

else

alias Iota = TypeTuple!(Iota!(stop - 1), stop - 1);

}

struct KdNode {

Line 512:

Line 505:

ref const(KdNode)* best,

ref double bestDist,

ref size_t nVisited) pure nothrow @nogc {

ref size_t nVisited) pure nothrow @safe @nogc {

static double dist(in ref KdNode a, in ref KdNode b)

pure nothrow @nogc {

typeof(KdNode.x[0]) result = 0;

foreach (i; ~~Iota~~!dim)

foreach (immutable i; staticIota!(0, dim))

result += (a.x[i] - b.x[i]) ^^ 2;

return result;

Line 549:

Line 542:

void randPt(size_t dim=3)(ref KdNode v, ref Xorshift rng)

nothrow @nogc {

pure nothrow @safe @nogc {

foreach (immutable i; ~~Iota~~!dim)

foreach (immutable i; staticIota!(0, dim))

v.x[i] = rng.uniform01;

}

Line 576:

Line 569:

auto bigTree = new KdNode[N];

auto rng = ~~Xorshift(~~1);

auto rng = 1.Xorshift;

foreach (ref node; bigTree)

randPt(node, rng);