[REVIEW-3-5] MSVC qsort issue

[Muthu Subramanian K]

Hi Eike,

This doesn't seem to be a problem on 3.6+, so we need this workaround 
only on <=3.5. May be we can live that? If so, it would be nice to 
commit this to the 3.5 branch, please?

That said, there could still be cases (in any version) that the order is 
changed by sort() (may be some corner cases). Though insert takes care 
of keeping the array sorted (and the order of the attribs as well).

Thanks & Regards,
Muthu SUbramanian

On 06/18/2012 05:36 PM, Eike Rathke wrote:
> 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 mailing list
> LibreOffice at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/libreoffice