forked from MartinNowak/dranges
-
Notifications
You must be signed in to change notification settings - Fork 1
/
eager.d
112 lines (100 loc) · 3.33 KB
/
eager.d
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
// Written in the D programming language
/**
To Be Documented.
This module is a test to code eager versions of some lazy functions
seen elsewhere, and eager algorithm, acting only on finite ranges.
License: <a href="http://www.boost.org/LICENSE_1_0.txt">Boost License 1.0</a>.
Authors: Philippe Sigaud
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
*/
module dranges.eager;
import std.algorithm,
std.array,
std.functional,
std.range;
/// An eager version of map.
template eagerMap(alias fun)
{
typeof(unaryFun!fun(ElementType!R.init))[] eagerMap(R)(R r) if (isInputRange!R && !isInfinite!R)
{
typeof(unaryFun!fun(ElementType!R.init))[] mapped;
static if (hasLength!R)
{
mapped.length = r.length;
foreach(i, elem; r) mapped[i] = unaryFun!fun(elem);
}
else
{
foreach(elem; r) mapped ~= unaryFun!fun(elem);
}
return mapped;
}
}
/// An eager version of filter.
template eagerFilter(alias pred)
{
typeof(unaryFun!pred(ElementType!R.init))[] filter(R)(R r) if (isInputRange!R)
{
typeof(unaryFun!pred(ElementType!R.init))[] filtered;
foreach(elem; r) if (unaryFun!pred(elem)) mapped ~= elem;
return mapped;
}
}
/// All the ways to cut an array in two parts.
T[][][] bipartitions(T)(T[] array)
{
T[][][] biparts;
biparts.length = array.length+1;
foreach(i; 0..array.length+1) {
biparts[i] = [array[0..i], array[i..$]][];}
return biparts;
}
/// All the way to cut an array into k parts.
T[][][] kpartitions(T)(uint k, T[] array)
{
assert(k <= array.length, "kpartitions error: trying to partition an array of length " ~ to!string(array.length) ~ " into " ~ to!string(k) ~ " parts.");
T[][][] parts;
T[][][] mergePrefixSuffixes(T[] prefix, T[][][] suffixes){
T[][][] merged = new T[][][suffixes.length];
foreach(i,elem; suffixes) merged[i] = prefix ~ suffixes[i];
return merged;
}
switch (k) {
case 0:
return parts;
case 1:
return [[array]];
default:
// I could probably calculate parts.length in advance. It's something like ((k n))
foreach(i; 1..array.length-k+2) {
auto subparts = kpartitions(k-1, array[i..$]);
parts ~= mergePrefixSuffixes(array[0..i], subparts);
}
}
return parts;
}
/// All the way to cut an n-elements array into 1-to-n parts. I mean, just for the fun of writing T[][][][].
T[][][][] allPartitions(T)(T[] array)
{
T[][][][] allParts = new T[][][][array.length]; // From partition!1 to partition!(array.length)
foreach(i, ref elem; allParts) elem = kpartitions(i+1, array);
return allParts;
}
///
T[] addOneToSorted(T)(T[] sorted, T element)
{
if (!sorted.empty)
{
if (element < sorted[0]) return element ~ sorted;
if (element > sorted[$-1]) return sorted ~ element;
if (element == sorted[$/2]) return sorted[0..$/2] ~ element ~ sorted[$/2..$];
return (element < sorted[$/2]) ?
addOneToSorted(sorted[0..$/2], element) ~ sorted[$/2..$] :
sorted[0..$/2] ~ addOneToSorted(sorted[$/2..$], element);
}
else
{
return [element];
}
}