www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - How to iterate over const(RedBlackTree)?

reply "Cooler" <kulkin hotbox.ru> writes:
Example:

const RedBlackTree!int rbt = redBlackTree(1, 2, 3);
foreach(i; rbt[])
   writeln(i);

dmd 2.064 give me error
"mutable method 
std.container.RedBlackTree!int.RedBlackTree.opSlice is not 
callable using a const object"

Without "const" keyword the example compiled and works fine.

How can I iterate over const?
Jan 02 2014
next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 2 January 2014 at 11:23:39 UTC, Cooler wrote:
 Example:

 const RedBlackTree!int rbt = redBlackTree(1, 2, 3);
 foreach(i; rbt[])
   writeln(i);

 dmd 2.064 give me error
 "mutable method 
 std.container.RedBlackTree!int.RedBlackTree.opSlice is not 
 callable using a const object"

 Without "const" keyword the example compiled and works fine.

 How can I iterate over const?

Currently, this is not possible. Or if it was, it would have a *very* high code cost inside RBT. The issue is that *if* opSlice was marked as const, then the returned range would also be const, and you can't iterate over that :/ A solution might be possible, but the current "status quo" is to not use const with ranges. It's one of the "issues" with D-style qualification: It's "apples all the way down".
Jan 02 2014
prev sibling next sibling parent "Adam D. Ruppe" <destructionator gmail.com> writes:
On Thursday, 2 January 2014 at 13:30:06 UTC, monarch_dodra wrote:
 Currently, this is not possible. Or if it was, it would have a
 *very* high code cost inside RBT.

It is possible in theory; RBT returns a separate Range type with opSlice that is implemented in terms of pointers to node. (This is hidden by an alias RBNode!Elem* Node, which gets in the way, but if those were inout(RBNode)* or const()* it'd work). We can have mutable pointers to const data, which would work with the range. So opSlice returns a mutable range that points back to const data. But in this case, none of the functions in rbtree use const nor inout, and there's some caching (e.g. _left and _right) that I'm not sure can work with it at all anyway. In a const node, the left and right properties won't work..
Jan 02 2014
prev sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 2 January 2014 at 14:59:55 UTC, Adam D. Ruppe wrote:
 On Thursday, 2 January 2014 at 13:30:06 UTC, monarch_dodra 
 wrote:
 Currently, this is not possible. Or if it was, it would have a
 *very* high code cost inside RBT.

It is possible in theory; RBT returns a separate Range type with opSlice that is implemented in terms of pointers to node. (This is hidden by an alias RBNode!Elem* Node, which gets in the way, but if those were inout(RBNode)* or const()* it'd work). We can have mutable pointers to const data, which would work with the range. So opSlice returns a mutable range that points back to const data. But in this case, none of the functions in rbtree use const nor inout, and there's some caching (e.g. _left and _right) that I'm not sure can work with it at all anyway. In a const node, the left and right properties won't work..

Right. Doable, but not trivially so :/ Array might be able to pull it off more easily. That said, it would only solve the "const container => Range" issue, but the "const range" problem itself would remain :(
Jan 02 2014