Skip to content

Instantly share code, notes, and snippets.

@BeRo1985
Created September 3, 2020 10:30
Show Gist options
  • Save BeRo1985/3c50be6480c77dfb320c23f4d88d2f10 to your computer and use it in GitHub Desktop.
Save BeRo1985/3c50be6480c77dfb320c23f4d88d2f10 to your computer and use it in GitHub Desktop.
Interval-tree-less interval search on sorted array of linked MIDI events
procedure TEngineMIDIEventList.FindInterval(const aResultList:TEngineMIDIEventDynamicArrayList;const aFromTime,aToTime:TEngineTime);
var Lower,Upper,Mid,Index,StartIndex,MinIndex,MaxIndex,
EventFromIndex,EventToIndex,NextStartIndex,TryIndex:SizeInt;
Event,TemporaryEvent:TEngineMIDIEvent;
FromTime,NextFromTime,EventFromTime,EventToTime,
MinEventTime,MaxEventTime:TEngineTime;
DoAdd:boolean;
begin
if fCount>0 then begin
FromTime:=aFromTime;
StartIndex:=-1;
Lower:=0;
Upper:=fCount-1;
while Lower<=Upper do begin
Mid:=Lower+{$if defined(cpu64)}SARInt64{$else}SARLongint{$ifend}(Upper-Lower,1);
case Sign(FromTime-fItems[Mid].Time) of
-1:begin
Upper:=Mid-1;
end;
1:begin
Lower:=Mid+1;
end;
else begin
StartIndex:=Mid;
break;
end;
end;
end;
if StartIndex<0 then begin
StartIndex:=Lower;
end;
for TryIndex:=0 to 1 do begin
DoAdd:=true;
if StartIndex<0 then begin
StartIndex:=0;
end else if StartIndex>=fCount then begin
StartIndex:=fCount-1;
end;
while (StartIndex>0) and (fItems[StartIndex].Time>=FromTime) do begin
dec(StartIndex);
end;
NextFromTime:=FromTime;
NextStartIndex:=StartIndex;
for Index:=StartIndex to fCount-1 do begin
Event:=fItems[Index];
if (Event.Time<=aToTime) or (aFromTime<=Event.GetEndTime) then begin
EventFromTime:=Event.Time;
EventToTime:=Event.Time;
EventFromIndex:=Index;
EventToIndex:=Index;
TemporaryEvent:=Event.fPreviousLinkedEvent;
if assigned(TemporaryEvent) and (TemporaryEvent.Time<EventFromTime) then begin
EventFromTime:=TemporaryEvent.Time;
EventFromIndex:=TemporaryEvent.Index;
end;
TemporaryEvent:=Event.fNextLinkedEvent;
if assigned(TemporaryEvent) and (TemporaryEvent.Time>EventToTime) then begin
EventToTime:=TemporaryEvent.Time;
EventToIndex:=TemporaryEvent.Index;
end;
if (EventFromTime<=aToTime) and (FromTime<=EventToTime) then begin
if (TryIndex=0) and ((EventFromTime<NextFromTime) or (EventFromIndex<NextStartIndex)) then begin
NextFromTime:=EventFromTime;
NextStartIndex:=EventFromIndex;
DoAdd:=false;
end;
if DoAdd and ((EventFromTime<=aToTime) and (aFromTime<=EventToTime)) then begin
aResultList.Add(Event);
end;
end;
end else begin
break;
end;
end;
if not DoAdd then begin
aResultList.SoftClear;
FromTime:=NextFromTime;
StartIndex:=NextStartIndex;
end else begin
break;
end;
end;
end;
end;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment