Interval-tree-less interval search on sorted array of linked MIDI events

MIDIEventIntervalSearch.pas

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;