Sorting
Table of contents
- 1. Introduction
- 2. Improve Sorting by Introducing Additional Rules
- 2.1.1. Rule #1: Implement a General Sorting Order
- 2.1.2. Rule #2: Ignore leading definite and indefinite articles
- 2.1.3. Rule #3: Ignore leading symbols and punctuation
- 2.1.4. Rule #4: Sort digits leading a string in numeric order
- 2.1.5. Rule #5: Ignore leading white space
- 2.1.6. Stories
- 2.1.7. Engineering Tasks
- 3. Applying Sorting Rules
- 4. Secondary Sort Column Rules
- 5. Additional Sorting Rules for Metadata Editor Sorting Fields
- 6. Known Risks
- 7. Interdependencies
- 8. Future
Note: The only things that have been implemented thus far are in purple.
Introduction
The goal of this update is to improve the rules Songbird uses to sort metadata fields exposed in media list types.
Currently, Songbird has minimal rules for handling sorting of the metadata associated with media that has been imported (causing users to grow frustrated with how their data appears.)
Purpose of This Document
The purpose of this document is to scope the work necessary to implement a basic set of metadata sorting features intended to satisfy a consumer media player audience.
What this document covers:
- A set of basic sorting rules the media list types should implement.
- Specifically what columns these rules should be applied against.
What this document doesn't cover:
- Implementing locale specific sorting
Improve Sorting by Introducing Additional Rules
The following sort order rules are requested to be implemented in the following priority:
Rule #1: Implement a General Sorting Order
For columns supporting fields with strings of mixed types the following rules should be followed. Exceptions to columns will be documented in another section.
First, strings should be sorted by Letters and Unicode characters.
In order of the Latin alphabet A-Z and implementing the Unicode collation algorithm. Order should continue to be case insensitive.
Note: this applies only to names, words or strings of text and doesn't include digits.
Example:
| Un-collated | Collated |
|---|---|
| bad | bad |
| Bad | Bad |
| Bat | bäd |
| bat | Bäd |
| bäd | bat |
| Bäd | Bat |
| bät | bät |
| Bät | Bät |
| côté | black-bird |
| coté | black-birds |
| côte | blackbird |
| cote | blackbirds |
| black-bird | cote |
| blackbird | coté |
| black-birds | côte |
| blackbirds | côté |
Second, strings should be sorted by misc 'other' characters
For example, implement radical-and-stroke sorting for non-alphabetic writing systems. Such as Chinese hanzi and Japanese kanj.
Example:
| Un-collated | Collated |
|---|---|
| アウトキャスト | 보통 빠르기/느리기 |
| 보통 빠르기/느리기 | アウトキャスト |
| アルタネイティヴ・サン | あさがお |
| エル・スール(南) | アルタネイティヴ・サン |
| あさがお | エル・スール(南) |
Third, sort by Digits.
Example:
| Un-collated | Collated |
|---|---|
| 10 | 0.720 |
| 38 | 1 |
| 0.720 | 5 |
| 41 | 10 |
| 5 | 38 |
| 1 | 41 |
Fourth, for null fields (or for fields that have been stripped to null) sort using field data in other columns.
Example:
| Un-collated title:artist:track number | Collated title:artist:track number |
|---|---|
| + : Kazumasa Hashimoto : 2 | !"£$%^&*(()) : Aphex Twin : 1 |
| !"£$%^&*(()) : Aphex Twin : 1 | .......... : Caroline Martin : 8 |
| .......... : Caroline Martin : 8 | + : Kazumasa Hashimoto : 2 |
| ? : Low : null | ++ : Kazumasa Hashimoto : 6 |
| ? : My Morning Jacket : null | +++ : Kazumasa Hashimoto : 8 |
| +++ : Kazumasa Hashimoto : 8 | ? : Low : null |
| ++ : Kazumasa Hashimoto : 8 | ? : My Morning Jacket : null |
Rule #2: Ignore leading definite and indefinite articles
Note: In English definite articles are "A ", "An ", and "The "
Note: In addition we should ignore the localized equivalents for spanish, french, german, portuguese, and italian.
Example: "The Rolling Stones" sorts as "Rolling Stones" "A Love Supreme" sorts as "Love Supreme"
Rule #3: Ignore leading symbols and punctuation
Note: Unless we tackle this differently, this rule implies that negative digits would be sorted minus the punctuation.
Example: "¢50" should sorts as "50" " ' Aight, Dog " should sort as "Aight, Dog"
Rule #4: Sort digits leading a string in numeric order
Example: The songs "1 track", "2 track", "10 track" should sort as "1 track", "2 track", "10 track".
Rule #5: Ignore leading white space
Any number of spaces entered at the beginning of the title should be ignored when sorting.
Stories
| ID | Title | Story | Testcase |
| | Implement General Sorting Rules | Songbird should introduce a set of prioritized rules for sorting default columns. (Main Tracking bug) | n/a |
| | Sort by letters and unicode characters | Strings should be sorted by Letters and Unicode characters. | 2247 |
| | Handle radical-and-stroke sort | Strings should be sorted by misc 'other' characters using radical-and-stroke sorting (for non-alphabetic writing systems) | 2472 |
| | Sort leading digits in numeric order | Strings should be sorted by Digits, if any. | 2473 |
| | Sort null fields with other columns | For null fields (or for fields that have been stripped to null) sort using field data in other columns. (Exact rules TBD and posted above) | 2474 |
| | Ignore leading definite and indefinite articles | Ignore leading definite and indefinite articles for english, spanish, french, german, portuguese, italian (as described in bug 8996) | 2476 2507 2509 2511 2513 2515 |
| | Ignore leading symbols, punctuation and whitespaces | Leading symbols, punctuation and whitespaces should not have any impact on sorting. | 2478 2479 2480 |
| | Sort old databases with new sorting rules | Old databases should be migrated so that the new sorting rules take effect on them too. | 2481 2482 2483 2484 2485 2486 2487 2488 2508 2510 2512 2514 2516 |
Engineering Tasks
| ID | Cost | Title | Task | Testcase |
| | 3 | Implement unicode collation for sort columns | Turn current "sortable" column into "searchable", fix usage, implement new "sortable" column using unicode collation data. | |
| | 3 | Ignore articles based on dictionnary and position in string | Implement a dictionnary of articles which should be ignored when found first or last in the string | 2476 |
| | 1 | Ignore leading symbols, punctuation and whitespaces | Ignore leading symbols, punctuation and whitespaces | 2478 2479 2480 |
| | 3 | Sort digits leading a string in numeric order | Sort digits leading a string in numeric order | 2473 |
| | 2 | Migrate database | Write db migration step for new sorting columns | 2481 2482 2483 2484 2485 2486 2487 2488 2508 2510 2512 2514 2516 |
| | 2 | Fix collate for osx | Fix collation sort on osx, possibly move collate into sqlite custom collation (ADDED 05/01/2009) | All testcases above WILL be executed on OS X 10.5.6 |
Applying Sorting Rules
After implementation of the above 5 rules/stories if I were to sort each of the above examples together by title (in ascending order, taking no other secondary rules into order) the following should be the results:
bad
Bad
bäd
Bäd
bat
Bat
bät
Bät
black-bird
black-birds
blackbird
blackbirds
cote
coté
côte
côté
보통 빠르기/느리기
アウトキャスト
あさがお
アルタネイティヴ・サン
エル・スール(南)
0.720
1
5
10
38
41
!"£$%^&*(()) : Aphex Twin : 1
.......... : Caroline Martin : 8
+ : Kazumasa Hashimoto : 2
++ : Kazumasa Hashimoto : 6
+++ : Kazumasa Hashimoto : 8
? : Low : null
? : My Morning Jacket : null
Secondary Sort Column Rules
Expected results in order of secondary sort priority
Album
Album Title => Disc Number => Track Number => Track Name
(note: need to decide if we want to support selecting secondary sort orders ie by artists and by year on the column name)
Artist
Artist Name => Album Name => Disc Number => Track Number => Track Name
Album Artist
Beats Per Minute
BPM => Artist Name => Album Name => Disc Number => Track Number => Track Name
Bit Rate
BPM (no bitrate appears first since it effectively = 0) => Artist Name => Album Name => Disc Number => Track Number => Track Name
Comment
Comment => Artist Name => Album Name => Disc Number => Track Number => Track Name
Composer
Composer => Artist Name => Album Name => Disc Number => Track Number => Track Name
Date Added
Date Added (since this is not editable by a user it should be a part of every single media item and thus there is no secondary sortable data set)
Date Modified
Date Modified (since this is not editable by a user it should be a part of every single media item and thus there is no secondary sortable data set. note: if we don't write date modified at every single import session then we need to fallback to date added)
Disc Number
Disc Number => Artist Name => Album Name => Track Number => Track Name
File Location
No secondary sort, un-necessary - sort alphabetically
Genre
Genre => Artist Name => Album Name => Disc Number => Track Number => Track Name
Last Played
Last Played (most recently played appears first) => Artist Name => Album Name => Disc Number => Track Number => Track Name
Last Skipped
Last Skipped (most recently played appears first) => Artist Name => Album Name => Disc Number => Track Number => Track Name
Play Count
Play Count (most recently played appears first) => Artist Name => Album Name => Disc Number => Track Number => Track Name
Rating
Rating => Artist Name => Album Name => Disc Number => Track Number
Sample Rate
Sample Rate => Artist Name => Album Name => Disc Number => Track Number => Track Name
Size
Size => Artist Name => Album Name => Disc Number => Track Number => Track Name
Skip Count
Skip Count => Artist Name => Album Name => Disc Number => Track Number => Track Name
Time
Duration => Artist Name => Album Name => Disc Number => Track Number => Track Name
Title
Track Name => Artist Name => Album Name => Disc Number => Track Number => Track Name
Track Number
Track Number => Artist Name => Album Name => Disc Number
Year
Year => Artist Name => Album Name => Disc Number => Track Number => Track Name
Additional Sorting Rules for Metadata Editor Sorting Fields
| ID | Cost | Title | Story | Testcase |
|---|---|---|---|---|
| bug 14169 | 2 | Sorting by a column should apply secondary sort rules where necessary | When a column heading is sorted additional secondary sort rules should be applied. For instance sorting by Album would sort the tracks associated with it first by Album Title then Disc Number then Track Number then Track Name. See above table. |
Known Risks
Interdependencies
Future
Implement a mechanism to sort by alternate fields (UI and metadata fields). Implement support for sorting international indefinite/definite articles. Implement support for sorting downloads based on queue order.
* Sortable will become a binary weight
* Filter lists will need changes, but should be minimal
* Unit tests (generic text file for confirmation)
* Only handle leading numbers (pad appropriately)
Album Artist => Album => Disc No => Track No.
or similar.
currently sorting on album artist has the track number all messed up, so is unusable.
IMHO, a much better idea would be to implement stable sort where the user can quickly and easily obtain any order he desires using just few clicks.