How to iterate over const(RedBlackTree)?

[Cooler]

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?

[monarch_dodra]

Post by Cooler
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".

[Adam D. Ruppe]

Post by monarch_dodra
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..

[monarch_dodra]

On Thursday, 2 January 2014 at 13:30:06 UTC, monarch_dodra

Post by monarch_dodra
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 :(

[John McFarlane via Digitalmars-d]

On Thursday, 2 January 2014 at 14:59:55 UTC, Adam D. Ruppe

On Thursday, 2 January 2014 at 13:30:06 UTC, monarch_dodra

Post by monarch_dodra
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 :(

I'm trying to get to grips with D, coming from a C++ background
and const correctness is tough thing to get comfortable with.
I've got a member variable that's RedBlackTree and I'd like to
examine its contents inside an invariants() block. Is this
possible at all right now? Obviously, this would be trivial to
achieve using std::set::const_iterator so is it the language or
the library that poses the difficulty for me? Thanks.