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
Attachment:
pgpxofIHNWWCm.pgp
Description: PGP signature