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.
