Closed Bug 353091 Opened 16 years ago Closed 16 years ago

Multiday view: calendar order not preserved, randomizing events at same time (need stable sort)

Categories

(Calendar :: Calendar Frontend, defect)

defect
Not set
normal

Tracking

(Not tracked)

RESOLVED FIXED

People

(Reporter: gekacheka, Assigned: gekacheka)

Details

Attachments

(4 files, 1 obsolete file)

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.8.0.7) Gecko/20060909 Firefox/1.5.0.7
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.9a1) Gecko/20060915 Calendar/0.3a2+

When events appear from multiple calendars at the same times, the calendar order o the events is not preserved.

Reproducible: Always

Steps to Reproduce:
0. Create a set of calendars with events at the same times for multiple hours, such as a (conference) schedule with a separate calendar for each track, or class schedules with a separate calendar for each student or teacher.
1. color each calendar a different color
2. View in week view or day view.


Actual Results:  
a random checkerboard: events at the same time are in apparently random order, not in calendar order.

Expected Results:  
colored columns:  events at the same time are in calendar order if schedules are full, so each calendar creates a column of colored events.  (If left calendar is empty at a time, then events to the right will shift left.)
(patch -l -p 2 -i file.patch)

Problem is multiday-view.computeEventMap uses Array.sort to sort events, but Array.sort is an unstable sort (quicksort), so the calendar order is not preserved for equal events.   The fix is to use mergeSort, a stable sort.

Changes:
1. add sortEvents method which sorts using mergeSort.
2. change computeEventMap to call sortEvents instead of Array.sort.

Result of merge sort produced "columns" image.
Attachment #238951 - Flags: second-review?(jminta)
Attachment #238951 - Flags: first-review?(mattwillis)
Comment on attachment 238951 [details] [diff] [review]
v1 patch multiday-view to use merge sort

>+      <method name="sortEvents">
>+        <parameter name="aComparator" />
>+        <body><![CDATA[
>+          /* A *stable* sort for large arrays 
>+             compare: compare(x,y) returns < 0 if x<y, 0 if x=y, >0 if x>y.
>+             optionalStart: start index in array, defaults to 0.
>+             optionalEnd: excusive end index in array, defaults to array.length. **/
Nit: Prevailing style in our XBL appears to be to use // style comments
(instead of C/Javadoc-style). Typo in "exclusive", and "optionalEnd" should be
"optionalEndEx"

r=lilmatt with those fixed
Attachment #238951 - Flags: first-review?(mattwillis) → first-review+
Assignee: nobody → gekacheka
Whiteboard: [patch in hand][needs review jminta]
(patch -l -p 2 -i file.patch)

(see comment #3 for changes)
Attachment #238951 - Attachment is obsolete: true
Attachment #238955 - Flags: second-review?(jminta)
Attachment #238951 - Flags: second-review?(jminta)
I did a small performance test, and found that mergesort takes about 4 to 5 times more time. Not sure if that really is a problem, as sorting doesn't seem to be a bottleneck, but i'm not sure.
Comment on attachment 238955 [details] [diff] [review]
v2 patch multiday-view to use merge sort (nits fixed)

I'm not 100% convinced of the desirability of a perfectly stable sort, at the expense mvl noted.  What about just adding extra conditions to the current .sort() function, comparing calendar and/or event name to reduce the frequency of returning 0?
Attachment #238955 - Flags: second-review?(jminta)
Fixed by checkin at bug 224128, making Array.sort a stable sort.
Status: NEW → RESOLVED
Closed: 16 years ago
Resolution: --- → FIXED
Whiteboard: [patch in hand][needs review jminta]
(In reply to comment #9)
> Fixed by checkin at bug 224128, making Array.sort a stable sort.
> 
More specifically, fixed in Sunbird by check-in to trunk at bug 224128.
May still be an issue for Lightning users until TB3.0 comes out.

You need to log in before you can comment on or make changes to this bug.