unit css;
{$DEFINE DebugCSS}
interface
uses classes,types,sysutils,windows{$IFDEF DebugCSS},clipbrd{$ENDIF};

type
  //Werte, die für die Suche nach der Struktur nötig sind.
  TStructureSearchStructure=record
    newSiteNumbers:array of integer;  //Ordnet jeder Teilseite der Website eine Seite
                                      //in der Struktur zu, -1 wenn sie nicht zugeordnet ist.
    renumberedSites:array of boolean; //Gibt für jede Seite der Struktur an, ob ihr eine
                                      //andere Seite zugeordnet wurde
    sites:PSites;                     //Die Website
    structure:TStructure;             //Die gesuchte Struktur
    {$IFDEF DebugCSS}checkedNotes:string;{$ENDIF} //Getestete Zuordnungen
  end;

//Liest alle Seiten, die von einer Startseite aus zu erreichen sind in eine TSites
//Struktur ein
function readSites(const startFileName:string; const bothDirections:boolean):TSites;

//Überprüft, ob die angegebene Struktur in den Seiten enthalten ist
function existsStructure(const Structure:TStructure; const sites:TSites) :boolean;
implementation
//Liest die angegebene Datei in einen String
function readFile(const fileName:string):string;forward;
//Findet die Zieladdressen aller Dateilinks in der angegebenen Datei
procedure findLinksInFile(const filename:string;linkedTo:TStrings);forward;

//Testet rekursiv, ob die bisher festgelegten Knotenzuordnungen einen korrekten
//Weg ergeben können, wenn man weiter Knoten einander zuordnet
function checkOneSite(var search:TStructureSearchStructure; const site:PSiteWay):boolean;forward;


//Liest die angegebene Datei in einen String
function readFile(const fileName:string):string;
var fileStream:TFileStream; //Datei
begin
  //öffnen
  fileStream:=TFileStream.create(fileName,fmOpenRead	or fmShareDenyNone);
  try
    //lesen
    SetLength(result,fileStream.Size);
    fileStream.Read(result[1],fileStream.Size);
  finally
    fileStream.free; //schließen
  end;
end;

//Findet die Zieladdressen aller Dateilinks in der angegebenen Datei
procedure findLinksInFile(const filename:string;   //Dateiname
                                linkedTo:TStrings);//Linkziele
var htmlFile:string; //Die gesamte HTML-Seite
    dir:string;      //Das Verzeichnis in dem die Datei enthalten ist
    linkRef:string;  //Das Ziel eines Linkes
    pos:pchar;  //Die aktuelle Leseposition
    ende:pchar; //Das Dateiende
    temp:pchar; //Eine temporäre Markierung für ein Zeichen in der Seite
    bodyRead:boolean; //Gibt an, ob der Bodytag gelesen wurde
    aRead:boolean; //Wird ein Hyperlink gelesen?
begin
  //Verzeichnis auslesen
  dir:=ExtractFilePath(fileName);
  //Datei öffnen
  htmlFile:=readFile(filename);
  //Dateizeiger setzen
  pos:=@htmlFile[1];
  ende:=@htmlFile[length(htmlFile)];

  bodyRead:=false;
  //Allgemeines durchlaufen (Inhalts-Ebene)
  while pos<=ende do begin
    if pos^='<' then begin //Beginn eines Tags => TAG-Ebene
      inc(pos); //Nächstes Zeichen
      aRead:=false;
      if pos^<>'/' then //Kein Schließungstag
        if bodyRead then //Wurde <body> gelesen?
          aRead:=StrLIComp(pos,'a ',2)=0 //Ein Hyperlink?
         else //<body> wurde noch nicht gelesen, feststellen, ob er jetzt kommt
          bodyRead:=(StrLIComp(pos,'body',4)=0) and ((pos[4]='>')or(pos[4]=' '));

      //Tag durchlaufen
      while (pos^<>'>')and(pos<=ende) do begin
        if (pos^='"')or(pos^='''') then begin //=> Eigenschaft-Eebene
          temp:=pos; //Position merken
          //überspringen
          inc(pos);
          while (pos^<>'"') and (pos<=ende) do inc(pos);

          //Ist diese Eigenschaft ein gültiges Linkziel?
          if aRead and //Gab es überhaupt einen Hyperlink?
             (StrLIComp(temp-5,'href=',5)=0) and //href-Eigenschaft gelesen
             (StrLIComp(temp+1,'http://',7)<>0) and //kein externer Link
             ((StrLIComp(pos-5,'.html',5)=0)or //zeigt auf eine HTML-Seite
               (StrLIComp(pos-4,'.htm',4)=0)) then begin
            //Linksziel berechnen
            linkRef:=dir+copy(temp+1,1,pos-temp-1);
            //Ist es kein Wiederholungslink und existiert die Datei?
            if (linkedTo.IndexOf(linkRef)=-1) and FileExists(linkRef) then
              linkedTo.Add(linkRef); //Link speichern
                end;
        end;
        inc(pos); //TAG durchlaufen
      end;
    end;
    inc(pos); //Weiter auf der Inhalts-Ebene laufen
  end;
end;

//Liest alle Seiten, die von einer Startseite aus zu erreichen sind in eine TSites
//Struktur ein (O(Knoten*(Knoten+Kanten))
function readSites(const startFileName:string; const bothDirections:boolean):TSites;
var toRead,newFiles:TStringList; //Gelesene und neue Dateinamen
    i,j,                         //Schleifenvariablen
    arrayNumber,                 //Nummer einer neuen Seite im Array
    count,                       //Anzahl der Links in einer bestimmten Matrixzeile
    index:integer;               //Index im Linkszielarray der Knotenliste
begin
  //Stringlisten erzeugen
  Result.fileNames:=TStringList.create;
  toRead:=TStringList.create;
  newFiles:=TStringList.create;
  //Eine Datei steht schon in der Knotenliste (die Startseite)
  SetLength(result.links,1);
  //---------------Alle Dateilinks lesen(O(Knoten*(Knoten+Kanten))--------------
  try
    //Startseite in die Dateiliste einfügen
    Result.fileNames.Add(startFileName);
    toRead.Add(startFileName);
    while toRead.count>0 do begin //Solange nicht alle Seiten gelesen wurden
      newFiles.Clear; //Neue Dateiliste zurücksetzen
      //Links in der aktuell markierten Datei auslesen
      findLinksInFile(toRead[toRead.count-1],newFiles);
      //Nummer der aktuellen Seite suchen (O(Knoten))
      arrayNumber:=Result.fileNames.IndexOf(toRead[toRead.count-1]);
      //Linkliste setzen
      SetLength(result.links[arrayNumber],newFiles.count);
      //Dateinamen entfernen
      toRead.Delete(toRead.count-1);
      //Alle neuen Linkziele durchlaufen (O(Kanten), aber erst alle Durchläufe zusammen)
      for i:=0 to newFiles.count-1 do begin
        //Seitennummer des Linkszieles suchen (O(Knoten))
        index:=Result.fileNames.indexOf(newFiles[i]);
        if (index=-1) then begin //Wenn nicht gefunden, in die Dateiliste einfügen
          index:=Result.fileNames.count;
          toRead.add(newFiles[i]);
          Result.fileNames.add(newFiles[i]);
        end;
        //Linkziel in Nummer in das Array schreiben 
        Result.links[arrayNumber][i]:=index;
      end;
      //Gibt es mehr Dateien, als Knoten in der Knotenliste? => erweitern
      if Result.fileNames.count>length(result.links) then
        SetLength(result.links,Result.fileNames.count);
    end;
  finally
    toRead.free;
    newFiles.free;
  end;
  setlength(result.inDegrees,length(result.links)); //Array für den hinzeigenden Kantengrad

  //--------Graph zusätzlich als Adjazenzmatrix speichern (O(Knoten^2))---------
  result.AdjazenzMatLen:=length(Result.links);
  //Speicher reservieren: (O(Knoten * Knoten ))
  SetLength(result.linksAdjazenzMat,sqr(result.AdjazenzMatLen));
  ZeroMemory(@result.linksAdjazenzMat[0], sqr(result.AdjazenzMatLen)*sizeof(boolean));
  //Links speichern (O(Knoten + Kanten))
  for i:=0 to high(Result.links) do
    for j:=0 to high(Result.links[i]) do begin
      //Gibt es den Links schon?
      if not result.linksAdjazenzMat[i*result.AdjazenzMatLen+Result.links[i][j]] then begin
        //Wenn nicht einfügen, und endenden Knotengrad erhögen
        result.linksAdjazenzMat[i*result.AdjazenzMatLen+Result.links[i][j]]:=true;
        inc(result.inDegrees[Result.links[i][j]]);
      end;
      if bothDirections then //Soll ein Link in die umgekehrte Richtung eingefügt werden?
        //Wenn noch nicht vorhanden
        if not result.linksAdjazenzMat[i+Result.links[i][j]*result.AdjazenzMatLen] then begin
          //Wenn nicht einfügen, und endenden Knotengrad erhögen
          result.linksAdjazenzMat[i+Result.links[i][j]*result.AdjazenzMatLen]:=true;
          inc(result.inDegrees[i]);
        end;
    end;

  //-------------Graph wieder zurück verwandeln (O(Knoten^2))-------------------
  if bothDirections then begin
    //Wenn die Links in beide Richtungen zeigen sollen, wird der Graph wieder
    //aus der Adjazenzmatrix Form, in der das der Fall ist, in die Knotenform,
    //in der es nicht der Fall ist konvertiert
    for i:=0 to high(Result.links) do begin
      //Linkanzahl in dieser Zeile
      count:=0;
      for j:=0 to result.AdjazenzMatLen-1 do
        if Result.linksAdjazenzMat[i*result.AdjazenzMatLen+j] then inc(count);
      //Array entsprechend setzen
      SetLength(result.links[i],count);
      index:=0;
      //Zeile durchlaufen
      for j:=0 to result.AdjazenzMatLen-1 do
        //Gibt es einen Link
        if Result.linksAdjazenzMat[i*result.AdjazenzMatLen+j] then begin
          //Link speichern
          Result.links[i][index]:=j;
          inc(index);
        end;
    end;
  end;
end;


//Testet rekursiv, ob die bisher festgelegten Knotenzuordnungen einen korrekten
//Weg ergeben können, wenn man weiter Knoten einander zuordnet
function checkOneSite(var search:TStructureSearchStructure; //Suchinformationen
                      const site:PSiteWay //Aktueller Knoten im Strukturgraph
         ):boolean;
var i,aimNode:integer; //Schleifenvariable und möglicher Index eines Zielknotens
    nextSite:PSiteWay; //Nächstes Wegstück
    SiteNumber,nextSiteNumber:integer; //Hummer des Knotens im Seitengraph der dem
                                       //aktuellen und nächsten Knoten des Strukturgraphen
                                       //entspricht
  {$IFDEF DebugCSS}tempDebug:string;{$ENDIF}
begin
  //Wenn alle Wege zu Ende sind, sind die festgelegten Knotenzuordnungen ok
  if (site=nil) then begin
    result:=true;
    exit;
  end;
  nextSite:=site.nextSite;
  if (nextSite=nil) then begin
    result:=true;
    exit;
  end;

  Result:=false;
  //Nummern der Knoten im Seitengraph, die den aktuellen und nächsten Knoten
  //des Strukturgraphen entsprechen, auslesen
  SiteNumber:=search.newSiteNumbers[site.number];
  nextSiteNumber:=search.newSiteNumbers[nextSite.number];

  {$IFDEF DebugCSS}
    //Debuginformationen
    //Dateiname des ersten Knotens ohne Verzeichnis und .html ermitteln
    if search.newSiteNumbers[0]<>-1 then begin
      tempDebug:=ExtractFileName(search.sites.fileNames[search.newSiteNumbers[0]]);
      delete(tempDebug,pos('.',tempDebug),length(tempDebug));
    end else tempDebug:='-1';
    //Neue Zeile und Dateinamen anhägen
    search.checkedNotes:=search.checkedNotes+#13#10+tempDebug;
    for i:=1 to high(search.newSiteNumbers) do begin
      //Dateinamen für jeden folgenden Knoten anhängen
      if search.newSiteNumbers[i]<>-1 then begin
        tempDebug:=ExtractFileName(search.sites.fileNames[search.newSiteNumbers[i]]);
        delete(tempDebug,pos('.',tempDebug),length(tempDebug));
      end else tempDebug:='-1';
      search.checkedNotes:=search.checkedNotes+', '+tempDebug;
    end;
    //Nummern der Eckknoten der aktuellen Kante
    search.checkedNotes:=search.checkedNotes+' ('+IntToStr(site.Number)+'->'+IntToStr(nextSite.Number)+')'#9;
    if nextSite.notLinked then //Neuer Weg beginnt?
      search.checkedNotes:=search.checkedNotes+' ( Neuer Weg)';
  {$ENDIF} //Getestete Zuordnungen

  //Ist bereits festgelegt, welche Seite dem nächsten Knoten entspricht?
  if nextSiteNumber<>-1 then begin
    //Kann man auch von der aktuellen Seite dorthin kommen, oder muss man es nicht?
    if (not search.sites.linksAdjazenzMat[
               SiteNumber*search.sites.AdjazenzMatLen+
               nextSiteNumber]) and not nextSite^.notLinked then
      exit; //Wenn nicht, ist die aktuelle Zuordnung ungültig, und es kann kein
            //Weg mit ihr entstehen
    //Ansonsten: teste von der nächsten Seite aus weiter
    result:=checkOneSite(search,nextSite);
  end else begin //Ist die Seite noch nicht festgelegt?
    if nextSite.notLinked then begin //Beginnt ein neuer Weg?
      //Da er überall beginnen kann, werden alle Seiten als mögliche Startknoten
      //betrachtet
      for i:=0 to high(search.sites.links) do begin
        if search.renumberedSites[i] then //Die Seite wurde bereits einem anderen
          continue;                       //Knoten zugeordnet => überspring sie
        //Hat diese Seite einen geringeren Kantengrad als der Knoten?
        if (search.sites.inDegrees[i]<search.structure.InDegrees[nextSite.number]) or
           (length(search.sites.links[i])<search.structure.OutDegrees[nextSite.number]) then
          continue; //Überspring sie auch dann

        //Speichern, dass die Seite jetzt zugeordnet wird
        search.renumberedSites[i]:=true;
        //An dem Knoten speichern, welche Seite ihm zugeordnet wird
        search.newSiteNumbers[nextSite.number]:=i;

        //Kann man mit den jetzt feststehenden Zuordnungen alle Wege durch laufem?
        result:=checkOneSite(search,nextSite);
        if Result then exit; //Wenn ja, geht es auch mit denen, die bereits vorher
                             //bekannt waren, da man die neuen anhängen kann

        //Wenn nicht wird die Zuordnung der Seite aufgehoben
        search.renumberedSites[i]:=false;
        //Und es geht weiter mit der nächst möglichen
      end;
    end else //Beginnt kein neuer Weg?
      //Da er nur mit von hier aus erreichbaren Knoten weiter gehen kann, werden
      //alle erreichbaren Seiten als mögliche Startknoten betrachtet
      for i:=0 to high(search.sites.links[SiteNumber]) do begin
        aimNode:=search.sites.links[SiteNumber][i]; //Aktuelle Seitennummer zwischen speichern 
        if search.renumberedSites[aimNode] then //Die Seite wurde bereits einem anderen
          continue;                             //Knoten zugeordnet => überspring sie

        //Hat diese Seite einen geringeren Kantengrad als der Knoten?
        if (search.sites.inDegrees[aimNode]<search.structure.InDegrees[nextSite.number]) or
           (length(search.sites.links[aimNode])<search.structure.OutDegrees[nextSite.number]) then
          continue; //Überspring sie auch dann
        //Speichern, dass die Seite jetzt zugeordnet wird
        search.renumberedSites[aimNode]:=true;
        //An dem Knoten speichern, welche Seite ihm zugeordnet wird
        search.newSiteNumbers[nextSite.number]:=aimNode;
        //weitertesten

        //Kann man mit den jetzt feststehenden Zuordnungen alle Wege durch laufem?
        result:=checkOneSite(search,nextSite);
        if Result then exit; //Wenn ja, geht es auch mit denen, die bereits vorher
                             //bekannt waren, da man die neuen anhängen kann

        //Wenn nicht wird die Zuordnung der Seite aufgehoben
        search.renumberedSites[aimNode]:=false;
        //Und es geht weiter mit der nächst möglichen
      end;

    //Egal ob ein neuer Weg getestet wurde, oder nicht, die Zuordnung einer Seite
    //zu dem aktuellen Knoten aufheben, wenn kein Weg gefunden wurde
    search.newSiteNumbers[nextSite.number]:=-1;
  end;

end;

//Überprüft, ob die angegebene Struktur in den Seiten enthalten ist
function existsStructure(const Structure:TStructure; const sites:TSites) :boolean;
var i:integer; //Schleifenvariable
    search:TStructureSearchStructure; //Suchinformationen
begin
  //-Suchinformationen speichern-

  //Struktur in den record übernehmen
  search.structure:=Structure;
  //Seiten übernehmen
  search.sites:=@sites;

  //Array für die Zuordnung von Knoten zu Seiten erzeugen
  setlength(search.newSiteNumbers,Structure.siteCount);
  //Alle Einträge mit $FFFFFFFF (=-1 bei integer) füllen.
  FillChar(search.newSiteNumbers[0],
           Structure.siteCount*sizeof(search.newSiteNumbers[0]),$FF);

  //Array für die Speicherung, welche Seiten zugeordnet sind, erzeugen
  setlength(search.renumberedSites,length(sites.links));
  ZeroMemory(@search.renumberedSites[0],
             length(sites.links)*sizeof(search.renumberedSites[0]));

  {$IFDEF DebugCSS}search.checkedNotes:='';{$ENDIF}

  //-Suche starten-
  //Alle vorhandenen Seiten einmal als Startknoten für die Struktursuche
  //nehemen
  for i:=0 to high(sites.links) do begin
    search.renumberedSites[i]:=true; //Seite ist jetzt zugeordnet
    search.newSiteNumbers[Structure.siteWay.number]:=i; //Der Knoten hat eine Seite
    //Kann mit diesen Startbedingungen ein Weg beginnen?
    result:=checkOneSite(search,Structure.siteWay);
    if Result then begin
      {$IFDEF DebugCSS} Clipboard.AsText:=search.checkedNotes; {$ENDIF}
      exit; //Wenn ja, gibt es einen Weg
    end;
    search.renumberedSites[i]:=false; //Wenn nicht, Zuordung aufheben
    //und zum nächster Seite gehen
  end;
  result:=false;
  {$IFDEF DebugCSS} Clipboard.AsText:=search.checkedNotes; {$ENDIF}
end;

end.
