unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, xmldom, XMLIntf, Menus, msxmldom, XMLDoc, StdCtrls;

type
        TOperation = (oAND,oNOT,oXOR,oOR,oNone);
        TriePtr = ^TTrie;
        TTrie = record
                id:longint;
                next:array ['A'..'z'] of TriePtr;
        end;
        HradloPtr = ^THradlo;
        THradlo = record
                pocetVstupu:integer;    //pracovní hodnota - pro typologicke serazeni grafu
                entryValue:byte;
                outpID:longint;
                op:TOperation;
        end;
  TForm1 = class(TForm)
    XMLDocument1: TXMLDocument;
    MainMenu1: TMainMenu;
    sOU1: TMenuItem;
    Ot1: TMenuItem;
    OpenDialog1: TOpenDialog;
    Edit1: TEdit;
    Label1: TLabel;
    Label2: TLabel;
    Edit2: TEdit;
    Button1: TButton;
    Button2: TButton;
    Button3: TButton;
    function GetID(s:String):longint;
    procedure initTrieNode(var trie:TriePtr);   //Inicializace jednoho uzlu trie
    procedure DestroyTrie(var root:TriePtr);    //Zniceni stare trie
    procedure initHradlo(var hradlo:HradloPtr;op:TOperation;outpID:longint);    //zinicializuje nove hradlo
    procedure DestroyHradla;    //Uvolneni starych hradel
    procedure initStructure(var node:IXMLnode);         
    procedure sortHradla;         //Usporada graf typologicky
    procedure FormCreate(Sender: TObject);
    procedure CleanUp;  //Nastavi hradla do vychozich poloh
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure Button3Click(Sender: TObject);
    procedure RunSimulation;    //Spusti simulaci hradlove site
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
  trie:TriePtr;
  ids:longint;
  sorted,tmp,inp,outp:TList;    //sorted - hradla serazena typologicky, tmp-hradla serazena ze vstupu, inp-vstupni porty, outp-vystupni porty
  draty:TList;  //z vystupniho portu - do n vstupnich portu
  node:IXMLnode;
//  std:TextFile;
implementation

{$R *.dfm}

procedure TForm1.initTrieNode(var trie:TriePtr);
var i:char;
begin
        new(trie);
        for i:='A' to 'z' do trie^.next[i]:=nil;
        trie^.id:=0;
end;

function TForm1.GetID(s:String):longint;
var
        tmp:TriePtr;
        i:integer;
        list:TList;
begin
        tmp:=trie;
//        ShowMessage(s);
        for i:=1 to (length(s)) do begin
                if tmp^.next[s[i]]=nil
                        then initTrieNode(tmp^.next[s[i]]);
                tmp:=tmp^.next[s[i]];
        end;
        if tmp^.id=0 then begin
                ids:=ids+1;
                tmp^.id:=ids;
                list:=TList.Create as TList;
                draty.Add(list);
        end;
//        showMessage(IntToStr(tmp^.id));        
        GetID:=tmp^.id;
end;

procedure TForm1.DestroyTrie(var root:TriePtr);
var
        i:char;
begin
        for i:='A' to 'z' do
                if (root^.next[i]<>nil) then begin
                        DestroyTrie(root^.next[i]);
                        Dispose(root^.next[i]);
                        root^.next[i]:=nil;
                end;
end;

procedure TForm1.initHradlo(var hradlo:HradloPtr;op:TOperation;outpID:longint);
begin
        new(hradlo);
        hradlo^.op:=op;
        hradlo^.outpID:=outpID;
        hradlo^.entryValue:=2;
        hradlo^.pocetVstupu:=0;
end;

procedure TForm1.initStructure(var node:IXMLNode);
var
        i,j:integer;
        id:longint;
        hradlo:HradloPtr;
        op:TOperation;
        s:String;
begin
        i:=0;
        while node.ChildNodes[i].NodeName='input' do begin //Predpoklad, ze existuji hradla a vystupy
//                showMessage(node.ChildNodes[i].Attributes['id']);
                id:=GetID(node.ChildNodes[i].Attributes['id']);
                initHradlo(hradlo,oNone,id);
                inp.Add(hradlo);
                tmp.Add(hradlo);
                i:=i+1;
        end;
        while node.ChildNodes[i].NodeName='gate' do begin
                if not(node.ChildNodes[i].HasAttribute('type')) then begin //Predpoklad, ze existuji vystupy


                end else begin
                        s:=LowerCase(node.ChildNodes[i].Attributes['type']);
                        if s='and' then op:=oAND
                        else if s='or' then op:=oOR
                        else if s='xor' then op:=oXor
                        else op:=oNot;
                        id:=GetID(node.ChildNodes[i].ChildNodes[node.ChildNodes[i].ChildNodes.Count-1].Attributes['id']);
                        initHradlo(hradlo,op,id);
                        for j:=0 to node.ChildNodes[i].ChildNodes.Count-2 do begin
                                id:=getID(node.ChildNodes[i].ChildNodes[j].Attributes['id']);
                                TList(draty.Items[id-1]).Add(hradlo);
                        end;
                        hradlo^.pocetVstupu:=node.ChildNodes[i].ChildNodes.Count-1;
                        tmp.Add(hradlo);
                end;
                i:=i+1;
        end;
        while i<node.ChildNodes.Count do begin
                id:=GetID(node.ChildNodes[i].Attributes['id']);                
                initHradlo(hradlo,oNone,id);
                hradlo.pocetVstupu:=1;
                TList(draty.Items[id-1]).Add(hradlo);
                outp.Add(hradlo);
                tmp.Add(hradlo);
                i:=i+1;
        end;
end;

procedure TForm1.sortHradla;
var
        vrcholu:longint;
        i,j,k,id:longint;
begin
        j:=0;
        vrcholu:=tmp.Count;
        for i:=0 to tmp.Count-1 do begin
                if HradloPtr(tmp.Items[i]).pocetVstupu=0 then begin
                        vrcholu:=vrcholu-1;
                        sorted.Add(tmp.Items[i]);
                end;
        end;
        while vrcholu>0 do begin
                if j=(tmp.Count-vrcholu) then begin showMessage('hradla obsahuji cyklus'); close;    //Hradla obsahuji cyklus
                end else begin
                        id:=HradloPtr(sorted[j]).outpID-1;
                        for k:=0 to TList(draty.Items[id]).Count-1 do begin
                                HradloPtr(TList(draty.Items[id]).Items[k]).pocetVstupu:=HradloPtr(TList(draty.Items[id]).Items[k]).pocetVstupu-1;
                                if HradloPtr(TList(draty.Items[id]).Items[k]).pocetVstupu=0 then begin
                                        vrcholu:=vrcholu-1;
                                        sorted.Add(TList(draty.Items[id]).Items[k]);
                                end;
                        end;
                end;
                j:=j+1;
        end;
end;



procedure TForm1.FormCreate(Sender: TObject);
begin
        initTrieNode(trie);
        sorted:=TList.Create as TList;
        tmp:=TList.Create as TList;
        inp:=TList.Create as TList;
        outp:=TList.Create as TList;
        draty:=TList.Create as TList;
end;

procedure TForm1.CleanUp;
var
        i:longint;
begin
        for i:=0 to (sorted.Count-1) do
                HradloPtr(sorted.Items[i]).entryValue:=2;
end;

procedure TForm1.DestroyHradla;
var
        i:longint;
begin
        for i:=0 to (sorted.Count-1) do Dispose(sorted.Items[i]);
        for i:=0 to draty.Count-1 do TList(draty.Items[i]).Destroy;
        sorted.Clear;
        tmp.Clear;
        inp.Clear;
        outp.Clear;
        draty.Clear;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
        if not(OpenDialog1.Execute) then exit;
        Edit1.Text:=OpenDialog1.FileName;
end;

procedure TForm1.Button2Click(Sender: TObject);
begin
        if not(OpenDialog1.Execute) then exit;
        Edit2.Text:=OpenDialog1.FileName;
end;

procedure TForm1.Button3Click(Sender: TObject);
var
        f:TextFile;
        i:longint;
        c:char;
begin
        destroyHradla;
        DestroyTrie(trie);
//        Memo1.Clear;
        ids:=0;
        XMLDocument1.FileName:=Edit1.Text;
        XMLDocument1.Active:=true;
        node:=XMLDocument1.DocumentElement;
        initStructure(node);
        sortHradla;

        assignFile(f,Edit2.Text);
        reset(f);         
        while not(eof(f)) do begin
                CleanUp;
                for i:=0 to inp.Count-1 do begin
                        read(f,c);
                        if c='0' then HradloPtr(inp.Items[i]).entryValue:=0
                        else HradloPtr(inp.Items[i]).entryValue:=1;
                end;
                readln(f);
                RunSimulation;
        end;
        closeFile(f);
        XMLDocument1.Active:=false;
end;

procedure TForm1.RunSimulation;
var
        i,j:longint;
        hradlo,hradlob:HradloPtr;
        naslednici:TList;
        s:String;
begin
        for i:=0 to sorted.Count-1 do begin
                hradlo:=HradloPtr(sorted.Items[i]);
                naslednici:=TList(draty.Items[hradlo.outpID-1]);
                for j:=0 to naslednici.Count-1 do begin
                        hradlob:=HradloPtr(naslednici.Items[j]);
                        if hradlob.entryValue=2 then begin
                                if hradlob.op=oNOT then begin
                                        if hradlo.entryValue=1 then hradlob.entryValue:=0
                                        else hradlob.entryValue:=1;
                                end else
                                        hradlob.entryValue:=hradlo.entryValue;
                        end else begin
                                case hradlob.op of
                                  oAND:hradlob.entryValue:=hradlob.entryValue and hradlo.entryValue;
                                  oOR:hradlob.entryValue:=hradlob.entryValue or hradlo.entryValue;
                                  oXOR:hradlob.entryValue:=hradlob.entryValue xor hradlo.entryValue;
                                end;
                        end;
                end;
        end;
        s:='';
        for i:=0 to outp.Count-1 do s:=s+IntToStr(HradloPtr(Outp.Items[i]).entryValue);
        writeln(output,s);
//        Memo1.Lines.Add(s);
end;
end.