Why more linear algorithms implemented as O(N^2)?
example: staticMap, or staticIndex, Erase, EraseAll, and etc..
see hello.d file.
import std.stdio;
import std.typetuple;
import std.random;
template staticMap2(alias F, T...)
{
static if (T.length == 0)
{
alias TypeTuple!() staticMap2;
}
else static if (T.length == 1)
{
alias TypeTuple!(F!(T[0])) staticMap2;
}
else
{
alias TypeTuple!( staticMap2!(F, T[0..$/2]), staticMap2!(F, T[$/2..$])) staticMap2;
}
}
template testF(T)
{
alias T testF;
}
string getTypes(int n)
{
Random gen;
string r;
for(int i = 1; i< n;++i)
{
// Generate an integer in [0, 16]
auto a = uniform(0, 16, gen);
string s;
final switch(a)
{
case 0: s = "int";break;
case 1: s = "uint";break;
case 2: s = "byte";break;
case 3: s = "ubyte";break;
case 4: s = "short";break;
case 5: s = "ushort";break;
case 6: s = "long"; break;
case 7: s = "ulong"; break;
case 8: s = "float"; break;
case 9: s = "double";break;
case 10: s = "char"; break;
case 11: s = "dchar"; break;
case 12: s = "wchar"; break;
case 13: s = "string"; break;
case 14: s = "dstring";break;
case 15: s = "wstring";break;
}
r ~= s;
r ~= ",";
}
return r ~ "int";
}
string makeTest(int n)
{
return "alias staticMap!(testF," ~ getTypes(n) ~ ") testAlias;";
}
/+
template staticIndexOf2(T, U...)
{
static if (U.length == 0)
{
enum int staticIndexOf2 = -1;
}
else static if (U.length == 1)
{
enum int staticIndexOf2 = is(T == U[0]) ? 0 : -1;
}
else
{
enum int leftHalf = staticIndexOf2!(T,U[0..$/2]);
enum int rightHalf = staticIndexOf2!(T,U[$/2..$]);
enum int staticIndexOf2 = (leftHalf == -1 && rightHalf == -1)
? -1
: leftHalf != -1 ? leftHalf : rightHalf + U.length/2;
}
}
string makeTest_staticIndexOf(int n)
{
return "enum int index = staticIndexOf2!(float,"~ getTypes(n) ~ ",float);";
}
template EraseAll(T, U...)
{
static if (U.length == 0)
{
alias TypeTuple!() EraseAll;
}
else static if (U.length == 1 )
{
static if (is(T == U[0]) )
{
alias TypeTuple!() EraseAll;
}
else
{
alias U EraseAll;
}
}
else
{
alias TypeTuple!( EraseAll!(T,U[0..$/2]), EraseAll!(T,U[$/2..$]) ) EraseAll;
}
}
template NoDuplicates(TList...)
{
static if (TList.length == 0)
alias TList NoDuplicates;
else
alias TypeTuple!(TList[0], NoDuplicates!(EraseAll!(TList[0], TList[1 .. $]))) NoDuplicates;
}
string makeTest_NoDuplicates(int n)
{
return "alias NoDuplicates!(" ~ getTypes(n) ~ ") testAlias;";
}+/
int main()
{
immutable string s = makeTest(500);
writeln(s);
mixin (s) ;
/+immutable string s = makeTest_staticIndexOf(34000);
writeln(s);
mixin (s);
writeln(index);
+/
/+
immutable s = makeTest_NoDuplicates(5000);
writeln(s);
mixin (s);
writeln(testAlias.stringof);
+/
return 0;
}
_______________________________________________
phobos mailing list
[email protected]
http://lists.puremagic.com/mailman/listinfo/phobos
