Forward Difference Compression
"Nordlöw"
per.nordlow at gmail.com
Sat Mar 22 15:32:46 PDT 2014
I'm working on a range-based generic codec that uses
forwardDifference (and its reverse not yet implemented) in
combination with msgpack to pack arrays of 64-bit timestamps for
compacter storage.
My solution so far looks like can be found here
https://github.com/nordlow/justd/blob/master/algorithm_ex.d
Exert:
auto forwardDifference(R)(R r)
pure nothrow if (isInputRange!R)
{
import std.range: front, empty, popFront;
struct ForwardDifference
{
R _range;
alias E = ElementType!R; // Input
ElementType
alias D = typeof(_range.front - _range.front); // Element
Difference Type
D _front;
bool _initialized = false;
this(R range) pure {
this._range = range;
}
@property:
auto ref front() {
if (!_initialized) { popFront(); }
return _front;
}
auto ref moveFront() {
popFront();
return _front;
}
void popFront() {
if (empty is false) {
_initialized = true;
E rf = _range.front;
_range.popFront();
if (_range.empty is false)
{
_front = _range.front - rf;
}
}
}
bool empty() { return _range.empty; }
}
return ForwardDifference(r);
}
auto packForwardDifference(R)(R r) if (isInputRange!R)
{
import std.range: front, empty;
if (r.empty)
return tuple(r.front, forwardDifference(r));
else
return tuple(r.front, forwardDifference(r));
}
unittest {
import std.range: front;
dln([1].packForwardDifference);
dln([1, 22].packForwardDifference);
dln([1, 22, 333].packForwardDifference);
}
gives the output
algorithm_ex.d:753:debug: Tuple!(int, ForwardDifference)(1, [0])
algorithm_ex.d:754:debug: Tuple!(int, ForwardDifference)(1, [21])
algorithm_ex.d:755:debug: Tuple!(int, ForwardDifference)(1, [21,
311])
the corner cases
- input []: throws exception on front and
- input [1]: outputs [0] which is incorrect and should give
output [].
How can I efficiently treat these special cases without using
.length property?
I want this to work for InputRanges, not just arrays.
More information about the Digitalmars-d
mailing list