RFC on range design for D2

[Sergey Gromov]

Bill Baxter <wbaxter at gmail.com> wrote:
> Here's another, an insertion sort:
> 
> template<class _BidIt,
> 	class _Ty> inline
> 	void _Insertion_sort1(_BidIt _First, _BidIt _Last, _Ty *)
> 	{	// insertion sort [_First, _Last), using operator<
> 	if (_First != _Last)
> 		for (_BidIt _Next = _First; ++_Next != _Last; )
> 			{	// order next element
> 			_BidIt _Next1 = _Next;
> 			_Ty _Val = *_Next;
> 
> 			if (_DEBUG_LT(_Val, *_First))
> 				{	// found new earliest element, move to front
> 				_STDEXT unchecked_copy_backward(_First, _Next, ++_Next1);
> 				*_First = _Val;
> 				}
> 			else
> 				{	// look for insertion point after first
> 				for (_BidIt _First1 = _Next1;
> 					_DEBUG_LT(_Val, *--_First1);
> 					_Next1 = _First1)
> 					*_Next1 = *_First1;	// move hole down
> 				*_Next1 = _Val;	// insert element in hole
> 				}
> 			}
> 	}

This is a bit more complex.  If only basic operations on ranges are 
allowed, it looks like this:

> void Insertion_sort1(R, T)(R r)
> {
>     if (!r.isEmpty())
>     {
>         R tail = r;
>         do
>         {
>             tail.next();
>             R head = r.before(tail);
>             T _Val = head.last;
>             if (_Val < head.first)
>             {
>                 R from, to;
>                 from = to = head;
>                 from.shrink();
>                 to.next();
>                 copy(retro(from), retro(to));
>                 head.first = _Val;
>             }
>             else
>             {
>                 R head1 = head;
>                 head1.shrink();
>                 for (; _Val < head1.last; head.shrink(), head1.shrink())
>                     head.last = head1.last;
>                 head.last = _Val;
>             }
>         }
>         while (!tail.isEmpty())
>     }
> }

Though it starts to look much better if we employ shrink-on-read/shrink-
on-write AND copy-on-shrink, AKA incremental slicing:

> void Insertion_sort1(R, T)(R r)
> {
>     if (!r.isEmpty())
>     {
>         R tail = r;
>         do
>         {
>             tail.next();
>             R head = r.before(tail);
>             T _Val = head.last;
>             if (_Val < head.first)
>             {
>                 copy(retro(head[0..$-1]), retro(head[1..$]));
>                 head.first = _Val;
>             }
>             else
>             {
>                 for (R head1 = head[0..$-1]; _Val < head1.last;)
>                     head.putBack(head1.getBack());
>                 head.last = _Val;
>             }
>         }
>         while (!tail.isEmpty())
>     }
> }