前回のdranges.algorithmの続きとして、dranges.rangeについて書きます。
ただ、めちゃくちゃ長いので2回くらいに分けます。
今回はその1番目です。
drangesについてはdranges.algorithmを見てください。
ちなみにdrangesについてはすべてのunittestがコンパイルできるようになり、
かつ、unittestもすべて通るようになりました。
dranges.range.minLength
size_t minLength(R...)(R ranges) if (allSatisfy!(isForwardRange, R) && allHaveLength!R && !allAreInfinite!R)
受け取ったレンジの最小の長さを返します。受け取るレンジはすべて前進レンジで、長さを持っているか無限レンジである必要があります。
auto s = ["a", "b", "c", "d", "e", "f"];
int[] r = [0, 1, 2, 3];
auto c = repeat(5); //無限
auto ml = minLength(s, r, c);
assert(ml == 4); //rの長さ
dranges.range.slice
Take!R slice(R)(R range, int begin, int end)
hasSlicing!Rがtrueでないものに対してもスライスするための関数です。
dranges.range.dropLast
R dropLast(R)(R range, size_t n) if (isBidirectionalRange!R)
双方向レンジを受け取り、レンジの後からn要素をけしたレンジを返します。
auto r1 = [0, 1, 2, 3, 4, 5];
auto d = dropLast(r1, 3);
assert(equal(d, [0,1,2][]));
assert(equal(dropLast(r1, 0), r1));
assert(dropLast(r1, 6).empty);
assert(dropLast(r1, 100).empty);
dranges.range.templateFunctionAnalysis
template templateFunctionAnalysis(alias templateFun, alias ParameterGenerator, size_t startN = 0, size_t limittedN = 10){
enum endN;
alias ... ArgumentTypes;
enum arity;
alias ... ReturnType;
}
このテンプレートは私が作ったものですが、そのうちdranges.traitsにいれようかと思います。
各パラメータを説明すると、
・templateFun : 解析したいテンプレート関数
・ParameterGenerator : [startN ~ limittedN]までの非負の整数を取り、templateFunの引数の型を生成するテンプレート
・startN : ParameterGeneratorを最初にインスタンス化する数
・limittedN : ParameterGeneratorをインスタンス化する場合の最終の数
となります。このとき、次のコードがコンパイル可能になるまでNをstartNからlimittedNまで増加させていきます。
templateFun(ParameterGenerator!(N).init)
使い方の例を挙げてくと、
template Generator(size_t N){alias TypeNuple!(int, N) Generator;}
alias templateFunctionAnalysis!(( (a, b, c) => a) , Generator) Result0;
static assert(Result0.arity == 3);
static assert(Result0.endN == 3);
static assert(is(Result0.ArgumentTypes == Generator!3));
static assert(is(Result0.ReturnType == int));
というようになります。
このテンプレートは、特殊な場面で使われ、naryFun!"a+b+c"などの引数の数を解析したりするのに使います。
dranges.range.dropWhile
template dropWhile(alias pred, size_t step = 1){
template dropWhile(R, T...)if(isForwardRange!R){
R dropWhile(R r, auto ref T subParam)
}
}
predがtrueの間だけ要素を削除したレンジを返します。stepは1回に進める量です。
predは0以上の引数の個数に対応します。
string s = " , abcd efg";
auto d1 = dropWhile!(isOneOf!" ,")(s); //' ' か ','をスキップ
assert(d1 == "abcd efg");
auto r1 = [0, 1, 2, 3, 3, 4, 5];
auto d2 = dropWhile!"a<4"(r1); //4未満の要素をスキップ
assert(equal(d2, [4, 5]));
auto d3 = dropWhile!"a<b"(r1); //増加している部分を削除
assert(equal(d3, [3, 3, 4, 5])); //(3,3)は増加していない
auto d4 = dropWhile!("a<b",2)(r1); //[(0, 1),(2, 3),(3, 4)]
assert(equal(d4, [5])); //"a<b"を満たし消される
auto d5 = dropWhile!("a<b && b<c")(r1); //[(0, 1, 2), (1, 2, 3), (2, 3, 3), ...]
assert(equal(d5, [2, 3, 3, 4, 5])); //(2, 3, 3)はpredを満たさない
auto d7 = dropWhile!"true"(r1); //常にtrueなpred
assert(d7.empty); //もちろんempty
auto d7_d = dropWhile!("true", 2)(r1); //stepが2でも
assert(d7_d.empty); //[5]が余るわけではない。
//[5]が余らない理由は、step=2でpredは0個の引数であるから、[0, 1, 2, 3, 3, 4, 5]の場合には
//[0, 2, 3, 5]が検査に使われ、すべての要素でtrueとなるから[5]まですべて消される。
auto r2 = [1];
auto d8 = dropWhile!"a<b"(r2);
//最初から1要素しかないのにbinary関数である場合には、そもそもpredを呼べないので検査できない
assert(equal(d8, [1][]));
auto d9 = dropWhile!"a < b"(r1, 4); //bには4が入る。よってレンジからは1つずつ検査されていく
assert(equal(d9, [4, 5])); //a < 4を満たす間drop
auto d10 = dropWhile!"a == b-c"(r1, 1); //cには1が入るため a == b-1が満たされるまでdrop
assert(equal(d10, [3, 3, 4, 5]));
auto d12 = dropWhile!((a, b, c) => a < b, 2)(r1, 1);
//実際にはcに1が入るが、検査にはa,bしか関わっておらず、これはd4と同じ結果[5]となる
assert(equal(d12, [5][]));
size_t cnt;
bool counter(){return cnt++ < 3;} //0引数で3回目まではtrue
auto d16 = dropWhile!(counter)(r1);
assert(equal(d16, [3, 3, 4, 5])); //3回目までtrueなので最初の3要素がなくなる
dranges.range.popFrontWhile
template popFrontWhile(alias pred, size_t step = 1){
template popFrontWhile(R, T...){
size_t popFrontWhile(ref R r, T subArgs)
}
}
dropWhileのpopFrontバージョンです。
dranges.range.takeWhile
template takeWhile(alias pred){
template takeWhile(R, T...)if(isForwardRange!R){
TakeWhile takeWhile(R range, T args)
}
}
dropWhileやpopFrontWhileのtakeバージョンです。
dranges.range.takeUntil
dranges.range.rotateWhile
実装されてない…？
dranges.range.tail
R tail(R)(R range) if (isInputRange!R)
Haskellのtailと同じです。が、emptyな場合にはそのまま返します。
Haskellの場合は空リストを渡すと例外が出るはずです。
dranges.range.tails
Tails!R tails(R)(R range) if (isForwardRange!R)
Haskellのtailsとすこし違いますが、ほとんど同じです。
auto r = [0,1,2,3];
auto t = tails(r);
assert(equal(t, [[1,2,3], [2,3], [3], [] ]));
dranges.range.heads
Heads!R heads(R)(R range) if (isForwardRange!R)
tailsのheadバージョンです。
auto r = [0,1,2,3];
auto h = heads(r);
auto witness = [ [], [0], [0,1], [0,1,2], [0,1,2,3] ][];
foreach(elem; h) {
assert(equal(elem, witness.front));
witness.popFront;
}
dranges.range.insertAt
auto insertAt(R1, R2)(size_t n, R1 range1, R2 range2) if (allSatisfy!(isForwardRange, R1, R2))
//または
auto insertAt(R, E)(size_t n, R range, E element) if (isForwardRange!R && is(ElementType!R == E))
次を返します。
return chain(take(range1, n), range2, drop(range1, n));
//または
return chain(take(range, n), [element][], drop(range, n));
例として、
auto r1 = [0,1,2,3];
auto m = map!"a*a"(r1);
auto ia0 = insertAt(0, r1, m);
auto ia2 = insertAt(2, r1, m);
auto ia10 = insertAt(10, r1, m);
assert(equal(ia0, [0,1,4,9, 0,1,2,3][]));
assert(equal(ia2, [0,1, 0,1,4,9, 2,3][]));
assert(equal(ia10,[0,1,2,3, 0,1,4,9][]));
auto ia1 = insertAt(1, r1, 99);
assert(equal(ia1, [0,99,1,2,3][]));
dranges.range.cutAt
Tuple!(R, R) cutAt(R)(size_t index, R range) if (isForwardRange!R && hasSlicing!R && hasLength!R)
Tuple!(ElementType!R[], R) cutAt(R)(size_t index, R range) if (isForwardRange!R && (!hasSlicing!(R) || !hasLength!(R)))
[0, index)までの要素(index個)を返り値の最初の要素に、残りを2番目に格納したものを返します。
auto r1 = [0,1,2,3,4,5];
auto c1 = cutAt(3, r1);
assert(first(c1) == [0,1,2][]);
assert(second(c1) == [3,4,5][]);
dranges.range.cutWhen
Tuple!(ElementType!(R)[], R) cutWhen(alias pred, R)(R range) if (isForwardRange!R)
predはunary関数です。
predがtrueな間だけのものを集めたのを先頭要素に、のこりを次の要素に入れ込みます。
auto r1 = [0, 1, 2, 3, 4, 1, 2];
auto cut = cutWhen!"a<3"(r1);
assert(equal(cut.field[0], [0, 1, 2]));
assert(equal(cut.field[1], [3, 4]));
dranges.range.knit
Knit!(R) knit(R...)(R ranges) if (allSatisfy!(isInputRange, R))
std.range.zipの弱いバージョンです。std.range.zipのほうがいいので、deprecatedになってもいいと思う。
dranges.range.stitch
StitchType!R stitch(R...)(R ranges) if (allSatisfy!(isTupleRange, R))
要素がtupleなレンジを複数個受け取り、tuple(a.field, b.field, ...)としたようなレンジを返します。
auto r1 = [0, 1, 2, 3, 4, 5];
auto r2 = [0.1, 0.2, 0.3, 0.4];
auto r3 = ["abc", "def", "", "g"];
auto r4 = ["a", "b", "c", "d", "e", "f"];
auto k1 = knit(r1, r2); // returns Tuple!(int, double)
auto k2 = knit(r3,r4); // returns Tuple!(string, char)
auto tf = tfilter!"b<2"(r3,r1); // returns Tuple!(string, int)
auto s = stitch(k1,k2,tf); // returns Tuple!(int,double,string,char,string,int)
assert(s.front == tuple(0, 0.1, "abc", "a", "abc", 0));
s.popFront;
assert(s.front == tuple(1, 0.2, "def", "b", "def", 1));
s.popFront;
assert(s.empty); //tfがemptyとなる。
dranges.range.twist
auto twist(int n, R)(R range) if (isTupleRange!R)
要素がtupleなレンジを受け取り、左方向にn要素回したようなレンジを返します。
auto r1 = [0, 1, 2, 3, 4];
auto r2 = [3.14, 2.78, 1.414];
auto s = ["a", "b", "c", "d","e","f"];
auto k = knit(r1,r2,s);
assert(is(ElementType!(typeof(k)) == Tuple!(int,double,string)));
assert(equal(k, [tuple(0,3.14,"a"), tuple(1,2.78,"b"), tuple(2,1.414,"c")][]));
auto rot1 = twist!1(k);
assert(is(ElementType!(typeof(rot1)) == Tuple!(double,string,int)));
assert(equal(rot1, [tuple(3.14,"a",0), tuple(2.78,"b",1), tuple(1.414,"c",2)][]));
auto rot_1 = twist!(-1)(k);
assert(is(ElementType!(typeof(rot_1)) == Tuple!(string,int,double)));
assert(equal(rot_1, [tuple("a",0,3.14), tuple("b",1,2.78), tuple("c",2,1.414)][]));
dranges.range.reverse
auto reverse(R)(R range) if (isTupleRange!R)
要素がtupleなレンジを受け取り、その順序を逆転させます。
つまり、tuple(a[n-1], a[n-2], ..., a[1], a[0])を作ります。
auto r1 = [0, 1, 2,3, 4];
auto r2 = [3.14, 2.78, 1.414];
auto s = ["a", "b", "c", "d", "e", "f"];
auto k = knit(r1, r2, s);
assert(is(ElementType!(typeof(k)) == Tuple!(int,double,string)));
assert(equal(k, [tuple(0, 3.14, "a"), tuple(1, 2.78, "b"), tuple(2, 1.414, "c")]));
auto rev = reverse(k);
assert(is(ElementType!(typeof(rev)) == Tuple!(string,double,int)));
assert(equal(rev, [tuple("a", 3.14, 0), tuple("b", 2.78, 1), tuple("c", 1.414, 2)]));
dranges.range.splice
auto splice(size_t n, R1, R2)(R1 range1, R2 range2)
if (allSatisfy!(isForwardRange, R1, R2) && is(ElementType!R1.Types) && (n <= ElementType!R1.Types.length))
range1は要素がtupleなレンジでなくてはいけず、
range1のn要素にrange2を割り込ませます。
auto r1 = [0, 1, 2, 3, 4];
auto s = ["a","b","c","d","e","f"];
auto k = knit(r1, s);
auto r2 = [-2.1, 0.0, 3.14];
auto spl = splice!1(k, r2); //tuple(k.front[0], r2.front, k.front[1])
assert(is(ElementType!(typeof(spl)) == Tuple!(int, double, string)));
assert(equal(spl, [tuple(0, -2.1, "a"), tuple(1, 0.0, "b"), tuple(2, 3.14, "c")]));
auto spl2 = splice!0(spl,k); //tuple(k.front, spl.front[0], spl.front[1])
assert(is(ElementType!(typeof(spl2)) == Tuple!(Tuple!(int,string), int,double,string)));
assert(equal(spl2, [tuple(tuple(0, "a"), 0, -2.1, "a"), tuple(tuple(1, "b"), 1, 0.0, "b"), tuple(tuple(2,"c"),2, 3.14, "c")]));
dranges.range.shred
template shred(idx...){
auto shred(R)(R range)if(isTupleRange!R)
}
要素がtupleなレンジを受け取って、idxの順番に並べ替えます。
auto r1 = [0, 1, 2, 3, 4];
auto r2 = [3.14, 2.78, 1.414];
auto s = ["a", "b", "c", "d", "e", "f"];
auto k = knit(r1, r2, s);
auto shr1 = shred!(1,0)(k); //反転
assert(equal(shr1, [tuple(3.14, 0), tuple(2.78, 1), tuple(1.414, 2)]));
auto shr2 = shred!(1)(k); //e[1]のみを取得
assert(equal(shr2, [3.14, 2.78, 1.414]));
auto shr3 = shred!(2,0,1,1)(k); //重複もOK
assert(equal(shr3, [tuple("a", 0, 3.14, 3.14),
tuple("b", 1, 2.78, 2.78),
tuple("c", 2, 1.414, 1.414)]));
dranges.range.untuplify
TMapType!("a", R) untuplify(R)(R range) if (isTupleRange!R && ElementType!R.Types.length == 1)
要素が1要素からなるtupleなレンジを受け取って、tupleでなくします。
auto r1 = [0,1,2,3,4];
auto k = knit(r1); //Tuple!(int)
assert(equal(k, [tuple(0), tuple(1), tuple(2), tuple(3), tuple(4)]));
auto u = untuplify(k); //int[]
assert(equal(u, r1));
dranges.range.transverse
Transverse!R transverse(R...)(R ranges)
複数のレンジを順番にたどっていきます。
auto r1 = [0,1,2,3,4];
auto r2 = repeat(5);
auto r3 = [-2.0, -1.0, 0.0, 1.0];
auto t = transverse(r1, r2, r3);
assert(is(ElementType!(typeof(t)) == double)); //全要素はdoubleに暗黙変換される
assert(equal(t, [0.0, 5, -2, 1, 5, -1, 2, 5, 0, 3, 5, 1, 4, 5])); //r3がemptyになり終わる
auto t2 = transverse(r1, emptyRange!double, emptyRange!short);
assert(is(ElementType!(typeof(t2)) == double));
assert(equal(t2, [0][])); //emptyRange!doubleにより[0]だけで終わる
dranges.range.interleave
Transverse!(B,Cycle!S) interleave(B, S)(B bigRange, S smallRange)
bigRangeとsmallRangeを受け取り、
[b[0], s[0], b[1], s[1], ... , b[n], s[n % s.length]]
というようなレンジを返します。
auto i = interleave("abcdef", ",");
assert(asString(i) == "a,b,c,d,e,f,");
auto i2 = interleave("abcdef", ",;.");
assert(asString(i2) == "a,b;c.d,e;f.");
auto r1 = [0, 1, 2, 3, 4];
auto i3 = interleave(r1, r1);
assert(equal(i3, [0, 0, 1, 1, 2, 2, 3, 3, 4, 4]));
dranges.range.segment
template segment(size_t N : 1, Range)
if(isInputRange!(Unqual!Range))
{
Segment segment(Range range)
}
template segment(size_t N, Range)
if (isInputRange!(Unqual!Range)
&& (isForwardRange!(Unqual!Range) ? (!isBidirectionalRange!(Unqual!Range)
&& !isRandomAccessRange!(Unqual!Range)) : true))
{
Segment segment(Range range)
}
template segment(size_t N, Range)
if(isRandomAccessRange!(Unqual!Range)
&& isBidirectionalRange!(Unqual!Range)
&& hasLength!(Unqual!Range))
{
Segment segment(Range range)
}
template segment(size_t N, Range)
if(isRandomAccessRange!(Unqual!Range)
&& !isBidirectionalRange!(Unqual!Range)
&& isInfinite!(Unqual!Range))
{
Segment segment(Range range)
}
template segment(size_t N, Range)
if(isBidirectionalRange!(Unqual!Range)
&& (isRandomAccessRange!(Unqual!Range) ? (!hasLength!(Unqual!Range) && isInfinite!(Unqual!Range)) : true))
{
Segment segment(Range range)
}
segmentは、drangesの至る所で使われているレンジです。
重要であるにもかかわらず、実装が貧弱で、InputRangeにも対応していなかったために私が書き直しました。
簡単な例を示しましょう。
int[] a = [0, 1, 2, 3, 4, 5];
auto s1 = segment!1(r1);
assert(equal(s1, [tuple(0), tuple(1), tuple(2), tuple(3), tuple(4), tuple(5)]));
auto s2 = segment!2(r1);
assert(equal(s2, [tuple(0, 1), tuple(1, 2), tuple(2, 3), tuple(3, 4), tuple(4, 5)]));
auto s3 = segment!3(r2);
assert(equal(s3, [tuple(0, 1, 2), tuple(1, 2, 3), tuple(2, 3, 4), tuple(3, 4, 5)]));
s3[1] = tuple(-1, -2, -3);
assert(equal(s3, [tuple(0, -1, -2), tuple(-1, -2, -3), tuple(-2, -3, 4), tuple(-3, 4, 5)]));
dranges.range.delay
template delay(alias array)if(isArray!(typeof(array)) && array.length != 0)
{
auto delay(R)(R range)if(isInputRange!R)
}
delayはarrayが[a, a, ...]の場合には、popFrontNと後に説明するparallelによって実装されています。
上記以外の場合にはsegmentとshredを用いています。
delayはsegmentに似ていますが、segmentとは少し違います。
返り値がtupleな要素なレンジであることは同じですが、
要素eのさらに要素であるe[i]はレンジrangeをpopFrontN(range, array[i])の要素となります。
auto r1 = [0, 1, 2, 3, 4, 5];
auto d = delay!([4,1,3,2])(r1);
assert(d.front == tuple(4,1,3,2));
assert(d.length == 2); //[(4,1,3,2), (5,2,4,3)]
dranges.range.parallel
auto parallel(size_t n, R)(R range)if(n > 0 && isInputRange!R)
parallelはレンジをn個並列にtupleに入れ込んだものを返します。
auto r1 = [0, 1, 2, 3, 4, 5];
auto p = parallel!4(r1);
assert(equal(p, [tuple(0,0,0,0), tuple(1,1,1,1), tuple(2,2,2,2), tuple(3,3,3,3), tuple(4,4,4,4), tuple(5,5,5,5)][]));