FunkinCrew
[BUGFIX] Chart Editor - Fix duplicating selection boxes (fix `fastIndexOf` implementation)
Linked Issues
Closes https://github.com/FunkinCrew/Funkin/issues/5064
Description
The chart editor uses an array, displayedNoteData to dictate whether a rendered note sprite should be created, kept or killed, which would be populated with duplicate notes or be missing notes, which was caused by fastIndexOf not working very well with notes of same time. This would cause multiple selection boxes and apparently multiple note sprites being unnecessarily created, seemingly causing a space leak.
To fix this I had to modify SongNoteDataArrayTools.fastIndexOf, it was either this or replacing the functions with contains. This changes the time complexity from O(log n) to a worst case of ~O(log n) + O(k + l)~ an extra O(k) and O(l) where k is the number of notes sharing the same time towards the left - and l towards the right - of midIndex.
The issue with the original implementation is that if notes are never equal but have the same time, highIndex will keep decreasing until the search stops and never finds the note, even if it actually exists in the array. So I've made it so it does extra checking towards both "directions" of the array while there's notes of equal time.
I've profiled the function via Tracy and saw no noticeable difference in performance, in fact it might even save some since rendered notes are now properly killed only when they need to.
Screenshots/Videos
https://github.com/user-attachments/assets/00ca7799-b0b7-4bbe-809c-3c12dbb2bcc1
Fixes #4277
I cannot reproduce that one even on a 0.5.3 build so maybe not.
Fixes #4277
I cannot reproduce that one even on a 0.5.3 build so maybe not.
oh...
O(log n) + O(k + l)
I'm pretty sure that's not how time complexity works, but it seems like it'll work fine regardless.
I'm pretty sure that's not how time complexity works, but it seems like it'll work fine regardless.
You're most certainly right lol. But the point I wanted to get across is that it comes with a cost, even though it's probably negligible unless we're considering a chart completely filled with notes of equal time (or so I believe would be a worst case scenario)
Note to self: reproduction of this issue requires moving the note to a row which has another note in a different column, it doesn't happen when there's a lone note.