www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Bitwise ranges

reply Stanislav Blinov <stanislav.blinov gmail.com> writes:
Hello,

I'm working on range adapters that should allow reading and writing 
individual bits from/to other ranges. Right now for simplicity I only 
allow that for ranges that have numerics as ElementType.

Making an input bitwise range is pretty straightforward: popFront on 
original range is called as soon as all bits from it's 'front' have been 
read.

What I'm stuck with is an output bitwise range. If the adapted output 
range works via mutable front/popFront mechanism, implementing bitwise 
output is almost identical to bitwise input. But when adapted range 
provides output interface via put() method, I have no possible way to 
output data bit-by-bit. What I can do is a deferred put(), e.g. store a 
buffer in the bitwise range which I would fill with bits and put() it 
into adapted range as soon as all its bits have been written.
This may expose additional interface for clients: when bitwise range is 
'done' with adapted range, there may be a remaining partially filled 
buffer, which must also be put() into adapted range. This, in turn, may 
be done either implicitly (via destructor) or explicitly (via, e.g. 
complete() method of bitwise range).

Now I have a feeling that this somewhat falls out from standard range 
mechanisms. Consider:

ubyte[] input = [ 1, 2, 3 ];
uint[] output = new uint[1];

copy(bitwiseRead(input), bitwiseWrite(output));

Let's assume that output would only allow put() method. Now what copy() 
does is call popFront() on bitwiseRead and put() on bitwiseWrite. But no 
data would actually be written into output during copy(). Instead, there 
would be bits accumulated inside bitwise adapter when copy() returns, 
and they would be put() into output 'silently', without copy() 
explicitly asking for it.

Are such 'deferred popFront/deferred put' approaches a 'good' way to go 
with ranges? Or should bitwise adapter's popFront()/put() method always 
call popFront()/put() on adapted range?
Sep 06 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
Stanislav Blinov:

 What I'm stuck with is an output bitwise range. If the adapted output 
 range works via mutable front/popFront mechanism, implementing bitwise 
 output is almost identical to bitwise input. But when adapted range 
 provides output interface via put() method, I have no possible way to 
 output data bit-by-bit. What I can do is a deferred put(), e.g. store a 
 buffer in the bitwise range which I would fill with bits and put() it 
 into adapted range as soon as all its bits have been written.
 This may expose additional interface for clients: when bitwise range is 
 'done' with adapted range, there may be a remaining partially filled 
 buffer, which must also be put() into adapted range. This, in turn, may 
 be done either implicitly (via destructor) or explicitly (via, e.g. 
 complete() method of bitwise range).


I am not sure, but this looks related to the idea of "Vectorized Lazines" that
I have shown time ago (from MonetDB/X100), and that later has partially
appeared in the Clojure language as Chunked Sequences:
http://digitalmars.com/d/archives/digitalmars/D/Re_Vectorized_Laziness_100676.html
http://blog.fogus.me/2010/01/22/de-chunkifying-sequences-in-clojure/
http://www.reddit.com/r/programming/comments/afyav/clojure_11_rc1_out_cuts_some_overhead_of/
http://www.infoq.com/news/2009/12/clojure-11-rc1-transients

I think the Range protocol needs some standard way to face the need of chunked
or buffered lazynes.

Bye,
bearophile
Sep 06 2010
parent Stanislav Blinov <blinov loniir.ru> writes:
  06.09.2010 15:37, bearophile wrote:

 I am not sure, but this looks related to the idea of "Vectorized Lazines" that
I have shown time ago (from MonetDB/X100), and that later has partially
appeared in the Clojure language as Chunked Sequences:
 http://digitalmars.com/d/archives/digitalmars/D/Re_Vectorized_Laziness_100676.html
 http://blog.fogus.me/2010/01/22/de-chunkifying-sequences-in-clojure/
 http://www.reddit.com/r/programming/comments/afyav/clojure_11_rc1_out_cuts_some_overhead_of/
 http://www.infoq.com/news/2009/12/clojure-11-rc1-transients

 I think the Range protocol needs some standard way to face the need of chunked
or buffered lazynes.


Thanks, I'll look at that when home.
Sep 06 2010