[REVIEW-3-5] MSVC qsort issue

[Eike Rathke]

Hi Muthu,

On Thursday, 2012-06-14 20:02:38 +0530, Muthu Subramanian K wrote:

> qsort seems to change the order of the elements even if the elements
> are sorted.

Yes, qsort and std::sort are not stable and preexisting relative
ordering is not preserved for equivalent elements.

> (Technically though it is correct), our way of applying
> color attributes goes out of order.
> For the field it should have been _FIELD data followed by
> EE_CHAR_COLOR, but then because of the qsort this gets reversed.

I don't know how that is implemented, but that sounds like _FIELD data
and EE_CHAR_COLOR have the same start value on which the attributes are
sorted, and EE_CHAR_COLOR is expected to follow the corresponding
_FIELD, yes? I wonder how that survived any sort, not just failing on
resort. But maybe I misunderstood.

> Please let me know if there is a better way to solve this problem
> rather than a work-around...

In general if a relative ordering (also partial order) of equivalent
elements needs to be preserved, the original position within the list
needs to be included in the sort as second field, so something like
start,position here. If two or more start values are equivalent then the
original order within those values is kept.

> +static bool isAlreadySorted( CharAttribArray &rAttribs )
> +{
> +	bool bSorted = true;
> +	sal_uInt16 nCount = rAttribs.Count();
> +	for( sal_uInt16 i = 1; i < nCount && bSorted; i++ )
> +			if( rAttribs.GetObject( i - 1 )->GetStart() > rAttribs.GetObject( i )->GetStart() )
> +				 bSorted = false;
> +	return bSorted;
> +}

Depending on the size of the list iterating through all values may be
a bottle neck if the list usually is already sorted. But then again
qsort's worst performance is also if elements are already (nearly)
sorted.. for which one can shuffle the order first.

So, if the _FIELD and EE_CHAR_COLOR situation is indeed as I understood
above, keeping them together using the position would be needed anyway,
I think. Otherwise your workaround may be good enough.

  Eike

-- 
LibreOffice Calc developer. Number formatter stricken i18n transpositionizer.
GnuPG key 0x293C05FD : 997A 4C60 CE41 0149 0DB3  9E96 2F1A D073 293C 05FD
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: not available
URL: <http://lists.freedesktop.org/archives/libreoffice/attachments/20120618/58a00cd7/attachment.pgp>