Array object sorted on time, how to deal with.

[Jonas Thörnvall]

When one have objects that are sorted "indexed" by their time and one edit them. They suddenly changed index......

Do i really need to compare with next and previous event, of course i can not have same type of event "notes", go thru same note so that i check.

But is is weird i would have to keep track of other notes start end just because of order "index" changed.

Or should one simply not do any sort until all editing done it is confusing when the note you edit become another note LoL

There must be similar evendriven "time" problems that deal with this type of issues.

I am leaning towards not do any sort until editing stopped, but when has editing really stopped....

Maybe it is better "but harder" to reposition index as notes change place in time.

[Jonas Thörnvall]

But it is just not the actual note that need repositoning but also previous and next event.
Actually it is even more confusing at least if you "move" rather then change position and length.

Because then there is two event "start" "stop" that both have previous and next event to keep track on.
And as these notes change index, previous and next must be updated for both.

[Jonas Thörnvall]

I decided to update on each change, by looking at note rather then keep track of index.

[luserdroog]

I missed this thread until now. I think you need a more powerful data structure
than a simple array. You need something like a Priority Queue or a Heap. That way
you can conveniently (and efficiently) maintain the list on a specified order (like by
.time). These will be able to "update on change" just like you want, and search
for elements in O(log n) time rather than O(n).

[luserdroog]

But the cost is, you have to interface with the data structure through
functions( with, parameters );
It may internally use an array, but you don't futz with it. You use its search()
function. The search() function will find the thing for you faster. But you
gotta let it do its thing without a backseat driver. Abstract data structures
are powerful and useful but they get spooked easily, like horses. If you put
blinders on it, you better not just stick your fingers in the mouth. Gon git bit.

I'd bet a good search() function would eliminate 30% of your for() loops.
50k-100k of code. Yes, I know, it's precious code that you've poured tireless
creative effort into.

There is joy in deleting code. Better, Faster, Stronger, ... Smaller.
Code where you can just read a whole function in 2 seconds and move on.
The problem isn't there. That code is so short and obvious that it's
obviously correct. Done. Released.

That's the gold. Searching for the latest bug becomes closer to O(log n)
instead of O(n), you see! The whole program is built according to
a hierarchy of separate responsibilities that interact harmoniously.

You are the abstraction machine. It makes you stronger.

[Jonas Thörnvall]

What would you suggest to search for it is an incremental addon, and i do a search "for next same note", check if current note "time" is smaller then next "same note time" then go on with buisness.
Else skip out.

[luserdroog]

With a priority queue, at least the ones I looked at, when you create the
queue you pass an ordering function to the constructor. It uses that function
to figure out how to keep your data in order without knowing anything else
about your data. So you can fill it with records and it'll keep everything in
a sorted order, you just have to tell it how to sort 2 of your things.

Off top of head, I'd expect something like (untested):

var note = {
pitch : 'a',
time : 0,
duration : 5,
get end_time(){ return time + duration }
};

const notesQueue = new PriorityQueue({
compare: (e1, e2) => {
if (e1.time > e2.time) return -1; // do not swap
if (e1.time < e2.time) return 1; // swap

// salaries are the same, compare rank
return e1.end_time < e2.end_time ? 1 : -1;
}
});

//then you add a note to it somewhere, like from a click handler

function addNote( pitch, time, duration ){
notesQueue.enqueue({ pitch:'a', time:10, duration:5})
}

//then when you click play, you can get an array of everything
//in order and run through converting each note to midi events.

function getNotesArray(){
return notesQueue.toArray()
}

These examples all copy the examples from
https://github.com/datastructures-js/priority-queue
which seems like a decent one. It has all the functions I'd expect
and seems credible and maintained AFAICT from a cursory glance
(without to be honest actually trying to install and use it myself).

[Ben Bacarisse]

luserdroog <luser...@gmail.com> writes:

> With a priority queue, at least the ones I looked at, when you create the
> queue you pass an ordering function to the constructor. It uses that function
> to figure out how to keep your data in order without knowing anything else
> about your data. So you can fill it with records and it'll keep everything in
> a sorted order, you just have to tell it how to sort 2 of your things.

For an abstract priority queue (in the strictest sense) you don't need
to keep the queue sorted.

I went on the write "In fact, one common implementation uses a heap, as
in heap sort" but then I looked at your link and that uses a heap! I
would not say that the data in a heap are in sorted order, though it's
almost a philosophical point.

However, if you need this:

> //then when you click play, you can get an array of everything
> //in order and run through converting each note to midi events.
>
> function getNotesArray(){
> return notesQueue.toArray()
> }

Then it might pay (depending on how the notes are generated) to maintain
a sorted array. But why is a sorted array needed? Can't whatever uses
this queue simply pull the notes off one at a time?

--
Ben.

[The Natural Philosopher]

Haven't been following this, but when I want a sorted queue I use a
linked list.
add the new record wherever the allocation scheme puts it, walk te array
until you find the last element that goes before it, change that
elements link to pint at it and the new elements link to point where
that one used to go.

Of all the things I vaguely read up on when studying 'books on compSci'
this is one of the very few techniques I ended up using.



--
Renewable energy: Expensive solutions that don't work to a problem that
doesn't exist instituted by self legalising protection rackets that
don't protect, masquerading as public servants who don't serve the public.

[luserdroog]

Agreed that there might be other data structures that are even better suited
to the task. But I hope I can safely say we all agree that it is a good idea
to abstract this stuff off and make the data structure reasonably self-contained
and isolated from the business logic of the application. Ie. you'd still
interface with the linked list through *functions*, right?

My only qualm about recommending a linked list is that it's simple enough
to present a strong temptation to inline all the functionality and then that
would undermine my whole crusade here.

So, as long as I can spin it to mean that you agree with me on this more
fundamental point, hell yes! vary it up and pick an even better data structure!
But functions.

Everybody must use functions.

You will obey the call of the functions. Do not plug your ears, do not tie
yourself to the mast. Their call must be heeded.

[luserdroog]

The way I understand the application (but I could be wrong) is that there's
a display of a "piano-roll" grid showing midi notes and when the user
clicks in the grid, we need to locate an existing note by its x coordinate
on screen or create a new note if there isn't one there already. (Dealing
with the x-coordinate here has me thinking there needs to be a scolling
sub-View control that can adjust the x-coordinate to be "global" for the list
rather than just trying to work with the on-screen coordinate.)

Then when the user clicks the 'play' button, a sorted stream of midi on/off
events needs to be sent to the midi player. So we need to maintain a sorted
list or a search tree to locate and manipulate the Model data. (I'm trying to
nudge towards an MVC design "from the other side", if possible). And then
we'll need to iterate through the data structure to create midi events.

But I think there also needs to be another sorting step later on if the midi on/off events
are generated by just running through the list because some notes can be held longer
so in general the on/off events will not automatically come out in time order.

But IMO this part should be isolated to the View code. Unless/until performance
analysis shows it to be a problem, just generate midi on request and throw it away
afterward.

[Richard Damon]

I think the key here is that a Note is actual TWO events, a start and a
stop, so you actually want to put TWO (related) items into your search
tree.

This also will have impact into the UI, as a note is not a 'dot' but a
bar, with duration.

Now, it might make sense to have two different representations, one for
the UI and a second for playing, if they need the data enough
differently for the two uses.

[luserdroog]

Yes, I think the separation into two representation would offer benefits
later on. In particular, there could be an "articulation" control to add gaps
between successive notes, ranging from "tenuto" with just enough
separation so repeating the same note sounds distinct up through
"staccato" to "marcato" or some fun extreme term.

Having a conversion step makes a natural place to add effects like
this or even more mundane stuff like globally transposing all the notes.

It also helps (I hope) encapsulate the "master data structure" and
abstract away other data that can be easily generated as needed.
Because OP already has code, a mostly working program AIUI.
To be enticing to him, it should ... hmm. Maybe I shouldn't pretend
to know the answer to that.

But yes, the midi stream is organized as a stream of events that can
be "Note On", "Note Off", or "Control Change ..." (for stuff like the
position of the bender if it's moving, or selecting a GM sound on a
channel). All of these are prefixed with a relative time-offset IIRC
in a variable-length integer format where the 7th bit On indicates
the last byte. I'm note sure how much of this is needed by the midi
player. It probably can process the integer for you.

I wrote a program years ago that created midi files using a
line oriented input format (it even required an "END" line at the
end or it wouldn't work). It read in data for several channels
separately and then had sort the list of events because even
though each channel was sequential, the several channels
together were supposed to be interleaved.

[Jonas Thörnvall]

Depending on "note duration ***time***", "BPM" and "number of BARS" the presented note have a dimension. So basicly UI note is just a length calculated using those three factors.
But one can not forget that it is one more factor to consider It all take place within a range, that range have the length of "number of bars visible" but the start and end must be used to know where to draw note.

[Jonas Thörnvall]

I am not sure what you mean with interleaved, the tracks are separate entities holding a full song if you so want "using all/any channels".
Midi is a bit confusing because channel is just a 7 bit "within a 4 bit range" that also signify note on and off depending which 4 bit range 0-127 you use.
So having an interleaved? structure for playup is not meaningful, you downmix "all events" to a track i use ZERO and then just que them.
The separation is just value interpretation by the module.

It is a varialble length format that is decided on the first "byte" 7-bit value. So i think hardware wise is rather complex to implement, i really hate the format LoL
So i use tone.js that make some json objects that is easier to read out "partse" import from, but the sequenser use my own format to store sequensing data.

The bitfiddling making original midi implementation would be endless... will not do that again.

[Jonas Thörnvall]

fredag 26 november 2021 kl. 04:27:22 UTC+1 skrev Richard Damon:

Well i generate UI data during playback, so there is no UI structure to store it either in "view/edit, play or record" it is generated as needed from the recorded file data.
You could say it is a data view with a range.

[John Harris]

On 26/11/2021 02:05, luserdroog wrote:

<snip>> Agreed that there might be other data structures that are

even better suited
> to the task. But I hope I can safely say we all agree that it is a good idea
> to abstract this stuff off and make the data structure reasonably self-contained
> and isolated from the business logic of the application. Ie. you'd still
> interface with the linked list through *functions*, right?

<snip>

It's an object, so when you say *functions* you really mean *method
function*, right?

John

[luserdroog]

They could certainly be method functions. And if we're borrowing the
implementation from somewhere on the web then it's almost certain
to be built with method functions. But I don't consider it a hard line.
If Jonas finds it easier to do with normal (global) functions, then that
still fits with my programme.

Either using methods or just plain functions, both should have the
benefit of eliminating code duplication and reducing the size of
existing functions.

I think this all falls under the DRY (Don't Repeat Yourself) principle.

If you have the same (or similar) code in more than one place,
then sooner or later you're going to forget to change one spot
when it needs to change.

But if the code is in one place, one function, and everything calls
that function instead of using inline code, then you have just
one place to change. Doing this consistently can eliminate a
whole class of bugs that just waste your time (and rob the world
of the results of your creativity).

[luserdroog]

Yeah. My program wasn't great. It was the first "big" program
I tried to write on my own over the summer after my first college
programming course. I think I had recently discover wotsit.org

https://web.archive.org/web/20080220223430/http://www.wotsit.org/

So getting into some binary data formatting, and saving myself the
$200 price tag for a drum machine were my motivations. It was more
like a midi Assembler with mnemonics for adjusting stuff (ppp, pp, p, f, ff, fff, ffff).
So to actually make "loops" or patterns, I made a separate macro expander
program that could repeat phrases multiple times.
And that's what led to the multiple sequences getting interleaved.
If I made a macro for an 8 beat bassline riff, then expanding that
would put me at some non-zero offset from the start of the song.
If I wanted a 2-bar melody riff to go over the top of the bassline, then
I would use a mnemonic that reset the time for subsequent notes.
So, they're more like multiple "voices" and not channels. I could
select which channel the notes would be assigned to but they
were usually just 1, 2 (,maybe 3), and 10 (the General Midi drum channel).

> It is a varialble length format that is decided on the first "byte" 7-bit value. So i think hardware wise is rather complex to implement, i really hate the format LoL
> So i use tone.js that make some json objects that is easier to read out "partse" import from, but the sequenser use my own format to store sequensing data.
>
> The bitfiddling making original midi implementation would be endless... will not do that again.

Good deal. So you've already got a tool that handles the integer business.
I was hoping that was the case.