Bidirectional range dilemma

Peter Alexander peter.alexander.au at gmail.com
Sun Jan 13 04:05:25 PST 2013


I'm repeatedly hitting a range API problem in my combinatorics 
library. Many of the ranges require (potentially sizeable) 
internal buffers to maintain their current state (permutations, 
set partitions, power sets etc.) Also, many of these ranges are 
bidirectional. What this means is they have to store *two* 
buffers, one for the front, and one for the back.

This is a problem because 90% of the time you'll only iterate 
forward, and of the remaining 10%, 9% is just iterating 
backwards, and maybe 1% of the time you want to iterate from both 
the front and back in the same iteration. This means that 99% of 
the time, having two buffers is just wasted memory. Of course, 
I'm plucking these numbers from the air, but you get the idea.

To make matters worse, thanks to the lack of logical const 
there's no way the buffers can be lazily allocated on first use.

The only (ugly) solution I can come up with is to create three 
different ranges, e.g.

ForwardPermutations
ReversePermutations
BidirectionalPermutations

(or equivalently, one range with an iteration policy).

I'd rather not do that. Any ideas on how to resolve this?


More information about the Digitalmars-d mailing list