// Lösungen zu "Richard Kaiser: C++ mit dem Borland C++Builder 2007", ISBN: 978-3-540-69575-2
// Copyright Richard Kaiser, 2007. http://www.rkaiser.de. All rights reserved.
// Diese Quelltexte dürfen in eigenen Programmen verwendet werden, wenn sie einen Hinweis auf die Quelle (die ersten beiden Zeilen) enthalten. In keinem Fall wird eine Haftung für direkte, indirekte, zufällige oder Folgeschäden übernommen, die sich aus der Nutzung ergeben.
// It is permitted to use this source text in programs of your own, provided that it contains a reference to the source (the first two lines above). All liabilities for use of the code are disclaimed.

#include <vcl.h>
#pragma hdrstop
#include "RecursionU.h"
#pragma package(smart_init)
#pragma resource "*.dfm"

TForm1 *Form1;
//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
AnsiString dir="c:\\test";

// Erzeuge das Verzeichnis, falls es nicht existiert
if (CreateDirectory(dir.c_str(),0))
  ShowMessage("directory '"+dir+"' created");
// Voreinstellungen für Aufgabe 4:
fnMask->Text="*.*";
fnMask->Text="*";
DriveComboBox1->Drive='C';
}

#include "..\..\CppUtils\TestUtils.h"

// --------------- Aufgaben 5.3.1 --------------------------

// --------------- Aufgabe 1 -------------------------------

// Rekursive Funktionen

// a)
int rek_Fak(int n)
{ // Fakultät rekursiv berechnen
if (n<=0) return 1;
else return n*rek_Fak(n-1);
}

// b)
int rek_Fib(int n)
{ // Fibonacci rekursiv berechnen
if (n<=0) return 0;
else if (n==1) return 1;
else return rek_Fib(n-1) + rek_Fib(n-2);
}

// c)
int rek_ggT(int m, int n)
{ // ggT rekursiv berechnen
if (n==0) return m;
else return rek_ggT(n, m%n);
}

// a)
int it_Fak(int n)
{
int f=1;
for (int i=2; i<=n; i++)
  f = f*i;
return f;
}

// b)
int it_Fib(int n)
{ // Fibonacci iterativ berechnen
int fib=0,f0=0,f1=1;
for (int i=0; i<n; i++)
  {
    fib = f0 + f1;
    f1 = f0;
    f0 = fib;
  }
return fib;
}

// c)
int it_ggT(int x, int y)
{
// x=x0, y=y0, ggT(x,y) = ggT(x0,y0)
while (y != 0) //            Ablaufprot. für den Schleifenkörper
  {               //                        x        y        r
   // ggT(x,y)=ggT(x0,y0)                 x0        y0        r0
   int r=x % y;//                                        x0 mod y0    +
   x = y;       //                               y0
   y = r;       //                                x0 mod y0
   // ggT(x,y) = ggT(y0,x0 mod y0) = ggT(x0,y0)
   // ggT(x,y)=ggT(x0,y0)
  }
// ggT(x,y) = ggT(x0,y0) und y=0
return x;
};

void test_rek()
{
//RichEdit1->Lines->Add("No news are good news");

for (int i=1; i<50; i++)
  if (rek_Fak(i)!=it_Fak(i))
    Form1->Memo1->Lines->Add(IntToStr(i));

for (int i=1; i<50; i++)
  for (int j=1; j<50; j++)
    if (rek_ggT(i,j)!=it_ggT(i,j))
      Form1->Memo1->Lines->Add(IntToStr(i)+" "+IntToStr(j));

for (int i=1; i<30; i++)
  if (rek_Fib(i)!=it_Fib(i))
    Form1->Memo1->Lines->Add(IntToStr(i));
}


bool test_rek_1()
{
bool result=true;
//RichEdit1->Lines->Add("No news are good news");
for (int i=1; i<50; i++)
  for (int j=1; j<50; j++)
    if (!assertEqual(rek_ggT(i,j),it_ggT(i,j),
                      "ggT("+IntToStr(i)+","+IntToStr(j)+")" ))
      Form1->Memo1->Lines->Add(IntToStr(i)+" "+IntToStr(j));

for (int i=1; i<50; i++)
  if (rek_Fak(i)!=it_Fak(i))
    Form1->Memo1->Lines->Add(IntToStr(i));

for (int i=1; i<30; i++)
  if (rek_Fib(i)!=it_Fib(i))
    Form1->Memo1->Lines->Add(IntToStr(i));
}


void __fastcall TForm1::Aufg1Click(TObject *Sender)
{
test_rek();
}


// --------------- Aufgabe 2 -------------------------------

int ack(int n, int m)
{
if (n==0) return m+1;
else if (m==0) return ack(n-1,1);
else return ack(n-1,ack(n,m-1));
}

#include <cmath>
void __fastcall TForm1::Aufg2Click(TObject *Sender)
{
/*
    ack(0,m) = m+1
    ack(1,m) = m+2
    ack(2,m) = 2*m+3
    ack(3,m) = 2m+3+1
*/
RichEdit1->Lines->Add("No news are good news");

for (int m=0; m<50; m++)
  if (ack(0,m)!=m+1)
    RichEdit1->Lines->Add(m);

for (int m=0; m<50; m++)
  if (ack(1,m)!=m+2)
    RichEdit1->Lines->Add(m);

for (int m=0; m<50; m++)
  if (ack(2,m)!=2*m+3)
    RichEdit1->Lines->Add(m);

// für m>10 dauert das recht lange:
for (int m=0; m<10; m++)
  {
    int a=ack(3,m);
    int e=std::pow(double(2),m+3)-3;
    if (a!=e)
      RichEdit1->Lines->Add(IntToStr(a)+" "+e);
  }
}


//-----------   Koch'sche Kurven -----------------------------------------------
int round(double x)
{
return int(x+0.5);
}

#include <cmath>
void Koch(TCanvas* C, int n, double leftx, double lefty,
                             double rightx, double righty)
{
const double r = std::sqrt(3.0)/6;//ca. r=0.29;
if (n<=1)
  {
    C->MoveTo(round(leftx), round(lefty));
    C->LineTo(round(rightx), round(righty));
  }
else
  {
    Koch(C, n-1, leftx, lefty,
          (rightx + 2.0*leftx)/3.0,(righty + 2.0*lefty)/3.0);
    Koch(C,n-1,
           (rightx + 2.0*leftx)/3.0,(righty + 2.0*lefty)/3.0,
           0.5*(rightx+leftx) - r*(lefty-righty),
           0.5*(righty + lefty) + r*(leftx-rightx));
    Koch(C,n-1,
           0.5*(rightx + leftx) - r*(lefty-righty),
           0.5*(righty + lefty) + r*(leftx-rightx),
          (2.0*rightx + leftx)/3.0,(2.0*righty + lefty)/3.0);
    Koch(C,n-1,
          (2.0*rightx + leftx)/3.0,(2.0*righty + lefty)/3.0,
          rightx, righty);
  }
}

void ClearImages(int W, int H)
{
Form1->Image1->Canvas->Brush->Color=clWhite;// FillRect(TRect(0,H,W,H));
Form1->Image2->Canvas->Brush->Color=clWhite;// FillRect(TRect(0,H,W,H));
Form1->Image3->Canvas->Brush->Color=clWhite;// FillRect(TRect(0,H,W,H));
Form1->Image4->Canvas->Brush->Color=clWhite;// FillRect(TRect(0,H,W,H));
Form1->Image1->Canvas->FillRect(TRect(0,0,W,H));
Form1->Image2->Canvas->FillRect(TRect(0,0,W,H));
Form1->Image3->Canvas->FillRect(TRect(0,0,W,H));
Form1->Image4->Canvas->FillRect(TRect(0,0,W,H));
}

int level=1;

void __fastcall TForm1::Koch_Click(TObject *Sender)
{
Form1->Caption="Koch'sche Kurven, n=2, 3, 4, 5";
int W=Image1->ClientWidth-1;
int H=Image1->ClientHeight-3;
ClearImages(W, H+2);
Koch(Image1->Canvas,2,0,H,W,H);
Koch(Image2->Canvas,3,0,H,W,H);
Koch(Image3->Canvas,4,0,H,W,H);
Koch(Image4->Canvas,5,0,H,W,H);
}

// --------------- Aufgabe 5.3.4 ---------------------------

void Dreieck(TCanvas* C, int n, double x, double y, double L)
{
const double r = std::sqrt(3.0);
if (n<=1)
  { // zeichnet ein gleichseitiges Dreieck im Punkt (x,y)
    // mit der Seitenlänge L
    TPoint Eckpunkte[4];
    Eckpunkte[0]=Point(x,y);
    Eckpunkte[1]=Point(x+L,y);
    Eckpunkte[2]=Point(x+L/2,y-L*r/2);
    Eckpunkte[3]=Point(x,y);
    C->Brush->Color = clBlack;
    C->Polygon(Eckpunkte, 3);
  }
else
  {
    Dreieck(C, n-1, x, y, L/2);
    Dreieck(C, n-1, x+L/2, y, L/2);
    Dreieck(C, n-1, x+L/4, y-L*r/4, L/2);
  }
}

void __fastcall TForm1::rekDreiecke_Click(TObject *Sender)
{
Form1->Caption = "Rekursive Dreiecke , n=1, 2, 5, 9";
int W=Image1->ClientWidth-1;
int H=Image1->ClientHeight-3;
ClearImages(W,H+2);
Dreieck(Form1->Image1->Canvas,1,0,H,H);
Dreieck(Form1->Image2->Canvas,2,0,H,H);
Dreieck(Form1->Image3->Canvas,5,0,H,H);
Dreieck(Form1->Image4->Canvas,9,0,H,H);
}


// --------------- Aufgaben 5.3.6 --------------------------

// --------------- Aufgabe 1 -------------------------------

typedef AnsiString dataType ; // Datentyp der Listendaten
typedef AnsiString keyType ; // Datentyp der Schlüsselwerte

#include "..\..\kap_3\3.12\TreeDefs.h"

// a)
void insertBinTreenode_rec(Treenode*& n, keyType key, dataType data)
{
if (n==0) n = newTreenode(key,data,0,0);
else if (key < n->key) insertBinTreenode_rec(n->left,key,data);
else insertBinTreenode_rec(n->right,key,data);
}

// b)
void processTreenode(Treenode* n)
{
Form1->Memo2->Lines->Add("key:"+n->key+" data:"+n->data);
};

void traverseTree_rec(Treenode* n)
{
if (n!=0)
  {
    traverseTree_rec(n->left);
    processTreenode(n);
    traverseTree_rec(n->right);
  }
}

// c)
Treenode* searchBinTree_rec(Treenode* n, const dataType& x) 
{
if (n==0) return 0;
else if (x==n->key) return n;
else if (x<n->key) return searchBinTree_rec(n->left,x);
else return searchBinTree_rec(n->right,x);
}

Treenode* t=0;

void __fastcall TForm1::TreeInsertClick(TObject *Sender)
{
insertBinTreenode_rec(t, Edit1->Text, Edit2->Text);
}

void __fastcall TForm1::ShowTreeClick(TObject *Sender)
{
traverseTree_rec(t);
}

void __fastcall TForm1::SearchTreeClick(TObject *Sender)
{
Treenode* n=searchBinTree_rec(t,Edit1->Text);
if (n!=0)
  Form1->Memo2->Lines->Add(n->key+" gefunden, Daten: "+n->data);
else
  Form1->Memo2->Lines->Add(Edit1->Text+" nicht gefunden");
}

// --------------- Aufgabe 2 -------------------------------

/* Eigentlich wäre hier der Datentyp int für die Listendaten
   angemessen:

    typedef int dataType ; // Datentyp der Listendaten
    typedef AnsiString keyType ; // Datentyp der Schlüsselwerte

  Damit die Definitionen von Aufgabe 3.12 verwendet werden
  können, wird der Datentyp AnsiString verwendet.
*/

#define VCL_H  // Das ist für assertEqual in
               // StringUt.h notwendig. 

struct Listnode {
  dataType data;
  Listnode* next;
};

struct TreenodeWithList {
  keyType key;
  Listnode *first,
           *last;
  TreenodeWithList *left,
           *right;
};

Listnode* newListnode(const dataType& data, Listnode* next)
{ // Wie in Abschnitt 3.12.12
Listnode* n=new Listnode;
n->data = data;
n->next = next;
return n;
}

void insertLastListnode(Listnode*& first, Listnode*& last, const dataType& data)
{ // Wie in Abschnitt 3.12.12
Listnode* n=newListnode(data,0);
if (last==0) first=n;
else last->next=n;
last=n;
}

void insertTreenode(TreenodeWithList*& n, keyType key,dataType data)
{
if (n==0)
  {
    n = new TreenodeWithList;
    n->key   = key;
    n->left  = 0;
    n->right = 0;
    n->first = 0;
    n->last  = 0;
    // Erzeuge einen neuen Listenknoten, auf den n->first und
    // n->last anschließend zeigen:
    insertLastListnode(n->first, n->last,data);
  }
else if (key < n->key) insertTreenode(n->left,key,data);
else if (key > n->key) insertTreenode(n->right,key,data);
else     insertLastListnode(n->first, n->last,data);
}

TreenodeWithList* W=0;
#include "..\..\CppUtils\StringUt.h"
#include <fstream>

void readFile(char* ifn)
{
ifstream fin(ifn);
int LineNr=0;
string z; // string und nicht AnsiString, da getline einen String
          // als Parameter hat
while (getline(fin,z))
  {
    LineNr++;
    vector<string> v=tokenize(z);
    for (vector<string>::iterator i=v.begin(); i!=v.end(); i++)
      insertTreenode(W, i->c_str(), LineNr);
}
fin.close(); // überflüssig
}

void printNode(TreenodeWithList* n)
{
AnsiString s=n->key+": ";
for (Listnode* i=n->first; i!=0; i=i->next)
  s += i->data+"  ";
Form1->Memo2->Lines->Add(s);
};

void printTree(TreenodeWithList* n)
{ // wie traverse_tree
if (n!=0)
  {
    printTree(n->left);
    printNode(n);
    printTree(n->right);
  }
}

void GenerateConcordanceList(AnsiString infn)
{
readFile(infn.c_str());
printTree(W);
}

void __fastcall TForm1::KonkordanzClick(TObject *Sender)
{
OpenDialog1->Filter = "Textdateien|*.TXT";
OpenDialog1->InitialDir = "..\\..\\..\\text";
if (OpenDialog1->Execute())
  GenerateConcordanceList(OpenDialog1->FileName);
}


// --------------- Aufgabe 5.3.7 ---------------------------

// --------------- Aufgabe 1 -------------------------------

// a)
void show(AnsiString s)
{
static int i=0; // sehr einfach, funktioniert nur beim ersten Aufruf
i++;
Form1->RichEdit1->Lines->Add(IntToStr(i)+" "+s);
}

int searchSubdirs_all(const AnsiString& Path)
{
int n=0;
AnsiString Mask="*";
AnsiString FileName=Path+Mask;
WIN32_FIND_DATA FindFileData;
HANDLE h=FindFirstFile(
             FileName.c_str(), // Zeiger auf den Dateinamen
             &FindFileData);   // Zeiger auf struct
if (h!=INVALID_HANDLE_VALUE)
  {
    int found=1;
    while (found )
      {
        if ((FindFileData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)!=0)
          { // Unterverzeichnis
            if (strcmp(FindFileData.cFileName,".")==0)
              ; // "." ignorieren
            else if (strcmp(FindFileData.cFileName,"..")==0)
              ; // ".." ignorieren
            else // Verzeichnis, rekursiv durchsuchen
              {
                show(Path+FindFileData.cFileName);
                n +=searchSubdirs_all(Path+FindFileData.cFileName+"\\");
              }
          }
        else
          {
            show(Path+FindFileData.cFileName);
            n++;
          }
        found=FindNextFile(h,&FindFileData);
      }
    FindClose(h);
  }
return n;
};

void __fastcall TForm1::Button_aClick(TObject *Sender)
{ 
RichEdit1->Lines->BeginUpdate();
int n=searchSubdirs_all("\\Loesungen_CB2006\\");
// oder ein anderes Verzeichnis auf ihrem Rechner
Form1->RichEdit1->Lines->Add("Anzahl gefundener Dateien: "+IntToStr(n));
RichEdit1->Lines->EndUpdate();
}

// b)

int searchSubdirs(const AnsiString& Path,const AnsiString& Mask)
{
int n=0;

// Erster Schritt: Suche nach allen Unterverzeichnissen (mit Mask="*")
WIN32_FIND_DATA FindFileData;
AnsiString MaskForAllFiles="*";
AnsiString FileName=Path+MaskForAllFiles;
HANDLE h=FindFirstFile(
             FileName.c_str(), // Zeiger auf den Dateinamen
             &FindFileData);   // Zeiger auf struct
if (h!=INVALID_HANDLE_VALUE)
  {
    int found=1;
    while (found)
      {
        if ((FindFileData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)!=0)
          { // Unterverzeichnis
            if (strcmp(FindFileData.cFileName,".")==0)
              ; // "." ignorieren
            else if (strcmp(FindFileData.cFileName,"..")==0)
              ; // ".." ignorieren
            else // Verzeichnis, rekursiv durchsuchen
              {
                // Rekursion:
                n +=searchSubdirs(Path+FindFileData.cFileName+"\\",Mask);
              }
          }
        else
          {
            // Im ersten Schritt nur Unterverzeichnisse gesucht
          }
        found=FindNextFile(h,&FindFileData);
      }
    FindClose(h);
  }

// Zweiter Schritt: Suche nach allen Dateien mit der als Parameter
//                  übergebenen Maske
FileName=Path+Mask;

h=FindFirstFile(
             FileName.c_str(), // Zeiger auf den Dateinamen
             &FindFileData);   // Zeiger auf struct
if (h!=INVALID_HANDLE_VALUE)
  {
    int found=1;
    while (found)
      {
        if ((FindFileData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)!=0)
          { // Unterverzeichnis
            // Im zweiten Schritt Unterverzeichnisse ignorieren
            // und nur Dateien bearbeiten.
          }
        else
          {
            show(Path+FindFileData.cFileName);
            n++;
          }
        found=FindNextFile(h,&FindFileData);
      }
    FindClose(h);
  }
return n;
};

void __fastcall TForm1::Button_bClick(TObject *Sender)
{
AnsiString Path="\\Loesungen_CB2006\\"; // oder ein anderes 
                           // Verzeichnis auf ihrem Rechner
AnsiString Mask="*.cpp";
RichEdit1->Lines->BeginUpdate();
int n=searchSubdirs(Path,Mask);
Form1->RichEdit1->Lines->Add("Anzahl gefundener Dateien: "+IntToStr(n));
RichEdit1->Lines->EndUpdate();
}

// c)
void __fastcall TForm1::RecurseDirClick(TObject *Sender)
{
AnsiString Path=AnsiString(DriveComboBox1->Drive)+":\\";
AnsiString Mask=fnMask->Text;
RichEdit1->Lines->BeginUpdate();
int n=searchSubdirs(Path,Mask);
Form1->RichEdit1->Lines->Add("Anzahl gefundener Dateien: "+IntToStr(n));
RichEdit1->Lines->EndUpdate();
}

// --------------- Aufgabe 2 -------------------------------

// Die Lösung ist das Projekt DupFiles



