If you think a bug might affect users in the 57 release, please set the correct tracking and status flags for Release Management.

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

RESOLVED FIXED

Status

Calendar
Calendar Views
RESOLVED FIXED
11 years ago
11 years ago

People

(Reporter: gekacheka, Assigned: gekacheka)

Tracking

Details

Attachments

(4 attachments, 1 obsolete attachment)

(Assignee)

Description

11 years ago
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.)
(Assignee)

Comment 1

11 years ago
Created attachment 238947 [details]
Image of "random checkerboard" problem
(Assignee)

Comment 2

11 years ago
Created attachment 238948 [details]
Image of desired "columns" from preserving calendar order
(Assignee)

Comment 3

11 years ago
Created attachment 238951 [details] [diff] [review]
v1 patch multiday-view to use merge sort

(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]
(Assignee)

Comment 5

11 years ago
Created attachment 238952 [details]
Zip of sample ics files
(Assignee)

Comment 6

11 years ago
Created attachment 238955 [details] [diff] [review]
v2 patch multiday-view to use merge sort (nits fixed)

(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 8

11 years ago
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?
(Assignee)

Updated

11 years ago
Attachment #238955 - Flags: second-review?(jminta)
(Assignee)

Comment 9

11 years ago
Fixed by checkin at bug 224128, making Array.sort a stable sort.
Status: NEW → RESOLVED
Last Resolved: 11 years ago
Resolution: --- → FIXED
Whiteboard: [patch in hand][needs review jminta]
(Assignee)

Comment 10

11 years ago
(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.