program NFA;

{$MODE OBJFPC}

// <http://swtch.com/~rsc/regexp/regexp1.html>

type
  TInputCharacterP = ^TInputCharacter;
  TInputCharacter = Char;

  TStateP = ^TState;
  TTransitionP = ^TTransition;
  TTransition = object
    HasInput : Boolean;
    Input : TInputCharacter;
    ThenState : TStateP;

    Next : TTransitionP;
    constructor Init;
  end;

  TState = object
  end;

  TOutState = object(TState)
    Input : TInputCharacter;
  end;

  TSplitStateP = ^TSplitState;
  TSplitState = object(TState)
  end;

  TMatchStateP = ^TMatchState;
  TMatchState = object(TState)
  end;

  TFragmentP = ^TFragment;
  TFragment = object
    Start : TStateP;
    DanglingOuts : array of TStateP;
    constructor Init;
  end;

  TNFA = object
    CurrentStates : array of TStateP; // worst case: be in all existing states simultaneously.
    //AllStates : array of TStateP;
  end;


constructor TTransition.Init;
begin
  HasInput := False;
  ThenState := nil;
  Next := nil;
end;

constructor TFragment.Init;
begin
end;

constructor TState.Init;
begin
  Self.ResetTransitions;
end;

procedure TState.AddTransition(aInput : TInputCharacter; aThenState : TStateP);
begin
  AddTransition(@aInput, aThenState);
end;

procedure TState.AddTransition(aInput : TInputCharacterP; aThenState : TStateP); overload;
var
  vTransition : TTransitionP;
begin
  New(vTransition, Init);
  vTransition^.HasInput := Assigned(aInput);
  if Assigned(aInput) then
    vTransition^.Input := aInput^;

  vTransition^.ThenState := aThenState;

  if Assigned(Self.LastTransition) then
    Self.LastTransition^.Next := vTransition;

  Self.LastTransition := vTransition;
  if not Assigned(Self.FirstTransition) then
    Self.FirstTransition := vTransition;
end;

procedure TState.ResetTransitions; inline;
begin
  Self.FirstTransition := nil;
  Self.LastTransition := nil;
end;

function MatchSingleCharacter(aInput : TInputCharacter) : TState;
begin
  Result.ResetTransitions;
  Result.AddTransition(aInput, nil);
end;

function Alternate(aFragment1, aFragment2 : TFragmentP) : TFragmentP;
begin
  New(Result, Init);
  Result^.Start := New(TSplitStateP);
  Result^.DanglingOuts := aFragment1^.DanglingOuts + aFragment2^.DanglingOuts;
end;

{
  WARNING! mutates #"aFragment1".
}
function Concatenate(aFragment1, aFragment2 : TFragmentP) : TFragmentP;
begin
  patch(aFragment1.DanglingOuts, aFragment2.Start);
  New(Result, Init);
  Result^.Start := aFragment1^.Start;
  Result^.DanglingOuts := aFragment2.DanglingOuts;
end;

function Optional(aState : TStateP) : TStateP;
begin
  New(Result, Init);
  Result^.AddTransition(nil, aState);
  Result^.AddTransition(nil, nil); // empty path.
end;

function Wildcard0(aState : TStateP) : TStateP;
begin
  New(Result, Init);
  Result^.AddTransition(nil, aState);
  // TODO loop a matching e machine back to the start.
  Result^.AddTransition(nil, nil); // empty path.
end;

function OneOrMore(aState : TStateP) : TStateP;
begin
  New(Result, Init);
  aState....AddTransition(nil, Result);
  Result^.AddTransition(nil, aState);
end;

begin
end.