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