Ready for review: new std.uni

[Jonathan M Davis]

On Sunday, January 13, 2013 11:00:50 Dmitry Olshansky wrote:
> 13-Jan-2013 03:39, Walter Bright пишет:
> > On 1/11/2013 11:31 AM, Dmitry Olshansky wrote:
> >> And documentation:
> >> http://blackwhale.github.com/phobos/uni.html
> > 
> > struct InversionList:
> > 
> > 
> > length() returns "number of characters", while "empty()" returns true if
> > there are no codepoints.
> > 
> > Aren't the two redundant?
> 
> Containers commonly have both. But maybe I should kill length on
> different grounds because it's computed by walking the array of
> intervals [a, b) and summing up (b-a) lengths. It's O(N).... ouch.
> 
> The only problem is that then it's not at all obvious that length is
> better calculated via:
> reduce!"a + (b[1] - b[0])"(set.byInterval, 0);
> vs
> walkLength(set.byChar);
> 
> where the latter may take enormous time to finish on common sets.
> 
> (damn it should by DChar at least)

According to std.container, length should never be defined unless it's at worst 
O(log n) (though I would have expected it to require O(1); I don't know of any 
container that can calculate its lengeth in O(log n) but not O(1) - it's 
always O(1) or O(n) in my experience). So, don't define length if it's not that 
efficient, even if it's not in std.container.

It _may_ be valuable to add a function which does the same (e.g. 
calculateLength or calcLength or calcLen or something liket that), especially 
if walkLength isn't going to be the most efficient.

And yes, providing both empty and length is common and expected. And since 
empty is _required_ to be O(1), it's still guaranteed to be efficient, whereas 
length isn't.

I really should ask Andrei why he made length require O(log n) instead O(1)...

- Jonathan M Davis