unit dintervaltree;

interface

type
TIntervalTree = object
private
  FCount: LongInt;
  FData: array of LongInt;
public
  procedure Init; inline;
  procedure Done; inline;
  procedure Add(Start, Count, Id: LongInt);
  function Find(Index: LongInt; var Id: LongInt): Boolean;
end;

implementation

procedure TIntervalTree.Init;
begin
  SetLength(FData, 0);
  FCount := 0;
end;

procedure TIntervalTree.Done;
begin
  SetLength(FData, 0);
end;

procedure TIntervalTree.Add(Start, Count, Id: LongInt);
begin
  Inc(FCount);
  if 3 * FCount > Length(FData) then
    SetLength(FData, 3 * (FCount + 15));
  // TODO
end;

function TIntervalTree.Find(Index: LongInt; var Id: LongInt): Boolean;
var
  Pos: LongInt;
begin
  Pos := 0;
  while Pos < FCount do begin
    if Index < FData[Pos] then begin
      Pos := 3 * (2 * Pos + 1);
      continue;
    end;
    if Index > FData[Pos + 1] then begin
      Pos := 3 * (2 * Pos + 2);
      continue;
    end;
    Id := FData[Pos + 2];
    Result := True;
    Exit;
  end;
  Result := False;
end;

end.
