Re: 2D (or higher) equivalent of ranges?
On Wed, May 16, 2012 at 11:20 PM, Tobias Pankrath tob...@pankrath.net wrote: More exotic: http://svn.dsource.org/projects/dranges/trunk/dranges/docs/recursive.html That looks like a compile time composite pattern and I'd say it's a natural way to iterate over every form of graph. To be a equivalent to ranges in the std.algorithm sense, they must also be a good vehicle to implement graph algorithms effectively. I'd question this for the recursive ranges. How would you implement Dijkstra with r-ranges? I don't remember how I did Dijkstra in D. That was 2 years ago (see https://github.com/PhilippeSigaud/dranges/blob/master/graphalgorithm.d ). IIRC That was an algorithm directly acting on the graph, not on a r-range. I have a module to present a graph as a (linear, standard) range, either exploring the graph in a deph-first or breadth-first manner, see: https://github.com/PhilippeSigaud/dranges/blob/master/graphrange.d As for recursive ranges, even two years afterwards I still don't know if exposing a r-range is a good idea or not. The thing is, a r-range preserves the global topology (shape) and as such is awfully near a container. And, as you said, some algorithm do not translate easily into a range function. I haven't think much about it though. I'm still waiting for a definitive word on allocators and seeing the AA implementation to go back to graphs.
2D (or higher) equivalent of ranges?
Lately I've been considering how to generalize multi-dimensional arrays along the same lines as std.range. The motivation for this is that I'm designing a generic interface for manipulating n-dimensional data, and it seems too implementation- specific to impose a particular representation of an n-dimensional array (specifically, a particular ordering of dimensions, say column major or row major). I'd like to be able to take arbitrary n-dimensional slices (subarrays) of a larger array and be able to pass it to the same code as though it were an independent n-dimensional array, for example. I also want to be able to take existing data structures, say a linked list of arrays, or an array of linked lists, and be able to treat it as though it were a 2D array. Better yet, the generic code should be able to handle arrays in which some of the dimensions are infinite (e.g., a finite list of infinite ranges, or an infinite range of finite lists, or an infinite list of infinite lists -- programmatically generated, of course). Also, it should be possible to transpose the array along any pair of dimensions (e.g., traverse an array of linked-lists in breadth-first order, i.e., return the first elements of each linked list, then the second elements, etc.). How would one go about designing a generic interface that encapsulates this functionality? Is it possible with the current range definition, or is something more needed? (Note that I used 2D examples above for simplicity's sake, but this needs to handle an arbitrary number of dimensions.) Any ideas? T -- Gone Chopin. Bach in a minuet.
Re: 2D (or higher) equivalent of ranges?
On Wed, May 16, 2012 at 8:09 PM, H. S. Teoh hst...@quickfur.ath.cx wrote: Lately I've been considering how to generalize multi-dimensional arrays along the same lines as std.range. Maybe that could interest you: http://svn.dsource.org/projects/dranges/trunk/dranges/docs/rangeofranges.html (code is easier to see here: https://github.com/PhilippeSigaud/dranges/blob/master/rangeofranges.d ) More exotic: http://svn.dsource.org/projects/dranges/trunk/dranges/docs/recursive.html
Re: 2D (or higher) equivalent of ranges?
On Wed, May 16, 2012 at 10:32:24PM +0200, Philippe Sigaud wrote: On Wed, May 16, 2012 at 8:09 PM, H. S. Teoh hst...@quickfur.ath.cx wrote: Lately I've been considering how to generalize multi-dimensional arrays along the same lines as std.range. Maybe that could interest you: http://svn.dsource.org/projects/dranges/trunk/dranges/docs/rangeofranges.html (code is easier to see here: https://github.com/PhilippeSigaud/dranges/blob/master/rangeofranges.d ) Cool!! This is exactly what I have in mind. Thanks!! More exotic: http://svn.dsource.org/projects/dranges/trunk/dranges/docs/recursive.html This is even better. Could this become the basis of generic tree processing algorithms? I also envisioned a similar generalization of ranges for graphs and digraphs, although in that case the meaning of 'range' may be questionable. T -- You know, maybe we don't *need* enemies. Yeah, best friends are about all I can take. -- Calvin Hobbes
Re: 2D (or higher) equivalent of ranges?
More exotic: http://svn.dsource.org/projects/dranges/trunk/dranges/docs/recursive.html That looks like a compile time composite pattern and I'd say it's a natural way to iterate over every form of graph. To be a equivalent to ranges in the std.algorithm sense, they must also be a good vehicle to implement graph algorithms effectively. I'd question this for the recursive ranges. How would you implement Dijkstra with r-ranges?
