std.string.reverse() for mutable array of chars

[Jonathan M Davis]

On Friday, December 09, 2011 13:27:01 Jonathan M Davis wrote:
> On Friday, December 09, 2011 12:44:37 bearophile wrote:
> > Jonathan M Davis:
> > > It sounded like you were,
> > 
> > Right, I was :-) But you have changed my mind when you have explained me
> > that nothing in std.algorithm is grapheme-aware. So I have reduced the
> > amount of what I am asking for.
> 
> So, now you're asking that char and wchar arrays be reversible with reverse
> such that their code points are reversed (i.e. the result is the same as if
> you reversed an array of dchar). Well, I'm not sure that you can actually do
> that with the same efficiency. I'd have to think about it more. Regardless,
> the implementation would be _really_ complicated in comparison to how
> reverse works right now. char[] and wchar[] don't work with reverse,
> because their elements aren't swappable. So, you can't just swap elements
> as you iterate in from both ends. You'd have to be moving stuff off into
> temporaries as you swapped them, because the code point on one side
> wouldn't necessarily fit where the code point on the other side was, and in
> the worst case (i.e. all of the code points on one half of the string are
> multiple code units and all of those on the other side are single code
> units), you'd pretty much end up having to copy half the array while you
> waited for enough space to open up on one side to fit the characters from
> the other side. So, regardless of whether it has the same computational
> complexity as the current reverse, its memory requirements would be far
> more.
> 
> I don't think that the request is completely unreasonable, but also I'm not
> sure it's acceptable for reverse to change its performance characteristics
> as much as would be required for it to work with arrays of char or wchar -
> particularly with regards to how much memory would be required. In general,
> the performance characteristics of the algorithms in Phobos don't vary much
> with regards to the type that that's used. I'm pretty sure that in terms of
> big-o notation, the memory complexity wouldn't match (though I don't recall
> exactly how big-o notation works with memory rather than computational
> complexity).

Well, it looks like Andrei had some free time this morning and figured it out. 
He has a pull request for it:

https://github.com/D-Programming-Language/phobos/pull/359

- Jonathan M Davis