D graph library -- update

[Joseph Rushton Wakeling]

On 07/12/2013 03:12 PM, Joseph Rushton Wakeling wrote:
> I'm a little bothered that the insertion implies potentially many re-allocs, and
> I wonder if it might be even better if the length of _indexHead and _indexTail
> can be increased in one go, and the "insertion" of the new edge index happen
> without risking a reallocation.

An attempt at an alternative:

        immutable size_t l = _indexHead.length;
        _indexHead.length = _head.length;
        _indexTail.length = _tail.length;
        foreach(e; iota(l, _head.length))
        {
            size_t i, j;
            i = _indexHead[0 .. e].map!(a =>
_head[a]).assumeSorted.lowerBound(_head[e]).length;
            for(j = e; j > i; --j)
                _indexHead[j] = _indexHead[j - 1];
            _indexHead[i] = e;
            i = _indexTail[0 .. e].map!(a =>
_tail[a]).assumeSorted.lowerBound(_tail[e]).length;
            for(j = e; j > i; --j)
                _indexTail[j] = _indexTail[j - 1];
            _indexTail[i] = e;
        }

It doesn't seem to make any difference in speed or memory consumption to the
current code (OK, perhaps a tiny speed increase, but very tiny).

It might have some relevance in the case where multiple edges are added in one
go.  I'll keep it in mind for that.