Date: prev next · Thread: first prev next last
2012 Archives by date, by thread · List index


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


Context


Privacy Policy | Impressum (Legal Info) | Copyright information: Unless otherwise specified, all text and images on this website are licensed under the Creative Commons Attribution-Share Alike 3.0 License. This does not include the source code of LibreOffice, which is licensed under the Mozilla Public License (MPLv2). "LibreOffice" and "The Document Foundation" are registered trademarks of their corresponding registered owners or are in actual use as trademarks in one or more countries. Their respective logos and icons are also subject to international copyright laws. Use thereof is explained in our trademark policy.