// 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.

// --------------- Aufgaben 3.10.4 -------------------------

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

const int maxElements=5; // Mit einem kleinen Wert von maxElements
                 // kann man auch die Prüfungen auf die Obergrenze
                 // einfach testen.
int nElements=0; // Anzahl der Arrayelemente
                 // belegt im Array: A[0] .. A[nElements-1]
typedef AnsiString T;
T A[maxElements];

// a)
bool pushBack(T data)
{
bool success=true;
if (nElements<maxElements)
  {
    A[nElements]=data;
    nElements++;
  }
else success=false;
return success;
// Nachbedingung: Falls beim Aufruf nElements<maxElements gilt:
//                  nElements=nElements0+1
//                  a[nElements-1]==data
//                  Rückgabewert true
//                und andernfalls Rückgabewert false.
}

void __fastcall TForm1::EinfuegenClick(TObject *Sender)
{
if (!pushBack(Edit1->Text))
  ShowMessage("Alle Plätze belegt");
}

// b)
void showArray()
{
for (int i=0; i<nElements; i++)
  Form1->Memo1->Lines->Add(A[i]);
}

void __fastcall TForm1::AnzeigenClick(TObject *Sender)
{
showArray();
}

// c)

/*
                 nElements  A[0]  A[1]  A[2]    pushBack maxElements
nElements=0          0                                      3
pushBack("10")       1     "10"                   true
pushBack("11")       2           "11"             true
pushBack("12")       3                 "12"       true
pushBack("13")       3                            false

Mit n<maxElements Aufrufen von pushBack werden die Positionen
a[0], …, a[n-1] des Array mit den Argumenten von pushBack gefüllt.
*/

// d)

int findLinear(T x, int Start)
{
int result=nElements;
bool found=false;
for (int i=Start; i<nElements && !found; i++)
  if (x==A[i])
    {
      result=i;
      found=true;
    }
return result;
}

void __fastcall TForm1::LinSuchenClick(TObject *Sender)
{
int i=0;
while (i<nElements)
  {
    i=findLinear(Edit1->Text,i);
    if (i<nElements)
      {
        Memo1->Lines->Add(A[i]);
        i++;
      }
  }
}

// e)

bool eraseElement(int pos)
{
bool result=true;
if ((0<=pos) && (pos<nElements))
  {
    A[pos]=A[nElements-1];
    nElements--;
  }
else result=false;
return result;
}

void __fastcall TForm1::LoeschenClick(TObject *Sender)
{
int p=findLinear(Edit1->Text,0);
if (p!=nElements)
  {
    if (eraseElement(p))
      ShowMessage(Edit1->Text+" gelöscht an Pos."+IntToStr(p));
    else
     ShowMessage(Edit1->Text+" nicht gelöscht");
  }
else
  ShowMessage(Edit1->Text+" existiert nicht");
}

// e)

void Auswahlsort()
{
for (int i=0; i<nElements-1; i++)
  {
    int min = i;
    for (int j=i+1; j<nElements; j++)
      if (A[j]<A[min]) min = j;
    T x = A[i];
    A[i] = A[min];
    A[min] = x;
  }
}

void __fastcall TForm1::SortierenClick(TObject *Sender)
{
Auswahlsort();
}

// g)
int findBinary(T s)
{
int M;
int L = 0;
int R = nElements-1;
bool found = false;
while ((L<=R) && (!found))
  {
     // A sortiert ==> A[L] <= A[R]
     M = (L + R)/2;
     // A[L] <= A[M] <= A[R]
     if (A[M]<s) L = M+1;
     else if (s<A[M]) R = M-1;
     else found = true;
  }
if (found) return M;
else return nElements;
}

void __fastcall TForm1::BinSuchenClick(TObject *Sender)
{
int pos=findBinary(Edit1->Text);
if (pos<nElements)
  Memo1->Lines->Add(A[pos]+" existiert");
else
  Memo1->Lines->Add(A[pos]+" nicht gefunden");
}

// h)
bool insertSorted(T x)
{
bool result=false;
if (nElements<maxElements)
  {
    // Die Position p für das neue Element bestimmen
    int p=0;
    while ((p<nElements) && (A[p]<x)) // Reihenfolge der Bedingungen ist relevant (Short-Circuit-Evaluation)
      p++; // Alle Elemente ab Position p um eine Position nach hinten verschieben
    for (int i=nElements-1; i>=p; i--)
      A[i+1]=A[i];
    A[p]=x;       // Das neue Element in Position p eintragen
    nElements++;  // Anzahl der Elemente aktualisieren
    result=true;
  }
return result;
}

void __fastcall TForm1::SortEinfClick(TObject *Sender)
{
if (!insertSorted(Edit1->Text))
  ShowMessage("Alle Plätze belegt");
}

// i)
// Falls das gesuchte Element mehrfach im Array enthalten ist,
// wird mit einer binären Suche nicht unbedingt das letzte gefunden.

// j)
bool eraseSorted(const T& x)
{
bool result=false;
int p=findLinear(x, 0);
if ((0<=p) && (p<nElements))
  { // Alle Elemente ab Position p um eine Position nach vorne
    for (int i=p; i<nElements-1; i++)
      A[i]=A[i+1];
    nElements--; // Anzahl der Elemente aktualisieren
    result=true;
  }
return result;
}

void __fastcall TForm1::SortLoeschenClick(TObject *Sender)
{
if (!eraseSorted(Edit1->Text))
  ShowMessage(Edit1->Text+" existiert nicht");
}

// k)

#include "..\..\CppUtils\testutils.h"

bool test_1()
{
// teste pushBack, findLinear und eraseElement
bool result = true;
nElements=0;
if (!assertEqual(findLinear("1",0),0,"findLinear(\"1\",0) - a")) result=false;
pushBack("1");
if (!assertEqual(findLinear("1",0),0,"findLinear(\"1\",0) - b")) result=false;
pushBack("2");
if (!assertEqual(findLinear("2",0),1,"findLinear(\"2\",0)")) result=false;
pushBack("3");
if (!assertEqual(findLinear("3",0),2,"findLinear(\"3\",0) - a")) result=false;
// Ist das gefundene Element auch wirklich das erste?
pushBack("3");
if (!assertEqual(findLinear("3",0),2,"findLinear(\"3\",0) - b")) result=false;
// teste eraseElement
eraseElement(0);
if (!assertEqual(findLinear("0",0),nElements,"nach eraseElement(\"2\",0)")) result=false;

return result;
}

void testSetAndSort2Elements(T e1, T e2)
{
nElements=0;
pushBack(e1);
pushBack(e2);
Auswahlsort();
}

void testSetAndSort3Elements(T e1, T e2, T e3)
{
nElements=0;
pushBack(e1);
pushBack(e2);
pushBack(e3);
Auswahlsort();
}

bool test_Auswahlsort_0123()
{ // teste Auswahlsort mit 0, 1, 2 und 3 Elementen
bool result = true;
nElements=0;
Auswahlsort(); // Auswahlsort sollte bei einem leeren Array nicht abstürzen
pushBack("1");
Auswahlsort(); // Array mit einem Element
if (!assertEqual(findLinear("1",0),0,"S(\"1\",0)")) result=false;

testSetAndSort2Elements("1","2"); // bereits sortiert
if (!assertEqual(findLinear("1",0),0,"sort 2, 1a")) result=false;
if (!assertEqual(findLinear("2",0),1,"sort 2, 1b")) result=false;
testSetAndSort2Elements("2","1"); // umgekehrte Reihenfolge
if (!assertEqual(findLinear("1",0),0,"sort 2, 2a")) result=false;
if (!assertEqual(findLinear("2",0),1,"sort 2, 2b")) result=false;

testSetAndSort3Elements("1","2","3"); // testen alle Permutationen
if (!assertEqual(findLinear("1",0),0,"sort 3, 1a")) result=false;
if (!assertEqual(findLinear("2",0),1,"sort 3, 1b")) result=false;
if (!assertEqual(findLinear("3",0),2,"sort 3, 1c")) result=false;
testSetAndSort3Elements("1","3","2");
if (!assertEqual(findLinear("1",0),0,"sort 3, 1a")) result=false;
if (!assertEqual(findLinear("2",0),1,"sort 3, 1b")) result=false;
if (!assertEqual(findLinear("3",0),2,"sort 3, 1c")) result=false;
testSetAndSort3Elements("2","1","3");
if (!assertEqual(findLinear("1",0),0,"sort 3, 1a")) result=false;
if (!assertEqual(findLinear("2",0),1,"sort 3, 1b")) result=false;
if (!assertEqual(findLinear("3",0),2,"sort 3, 1c")) result=false;
testSetAndSort3Elements("2","3","1");
if (!assertEqual(findLinear("1",0),0,"sort 3, 1a")) result=false;
if (!assertEqual(findLinear("2",0),1,"sort 3, 1b")) result=false;
if (!assertEqual(findLinear("3",0),2,"sort 3, 1c")) result=false;
testSetAndSort3Elements("3","1","2");
if (!assertEqual(findLinear("1",0),0,"sort 3, 1a")) result=false;
if (!assertEqual(findLinear("2",0),1,"sort 3, 1b")) result=false;
if (!assertEqual(findLinear("3",0),2,"sort 3, 1c")) result=false;
testSetAndSort3Elements("3","2","1");
if (!assertEqual(findLinear("1",0),0,"sort 3, 1a")) result=false;
if (!assertEqual(findLinear("2",0),1,"sort 3, 1b")) result=false;
if (!assertEqual(findLinear("3",0),2,"sort 3, 1c")) result=false;
return result;
}

bool isSorted()
{
bool result=true;
for (int i=0;i<nElements-1 ;i++ )
    if (A[i] > A[i+1]) result=false;
return result;
}

#include <cstdlib>
bool test_Auswahlsort_n(int n)
{ // teste Auswahlsort mit n Zufallszahlen
bool result = true;
nElements=0;
for (int i=0; i<n; i++)
  pushBack(IntToStr(std::rand()));
Auswahlsort();
if (!assertEqual(isSorted(),true,"sort n")) result=false;
return result;
}

bool test_2()
{// teste findBinary, insertSorted und eraseSorted
bool result = true;
nElements=0;
if (!assertEqual(findBinary("1"),0,"findBinary(\"1\",0)")) result=false;
pushBack("1");
if (!assertEqual(findLinear("1",0),0,"findLinear(\"1\",0)")) result=false;
pushBack("2");
if (!assertEqual(findLinear("2",0),1,"findLinear(\"2\",0)")) result=false;
pushBack("3");
if (!assertEqual(findLinear("3",0),2,"findLinear(\"2\",0)")) result=false;
// teste eraseElement
eraseElement(0);
if (!assertEqual(findLinear("0",0),nElements,"nach eraseElement(\"2\",0)")) result=false;

return result;
}

bool test_All_3_4()
{
bool result = true;
if (!test_1()) result=false;
if (!test_Auswahlsort_0123()) result=false;
for (int i=0;i<100 ; i++)
  test_Auswahlsort_n(i);
if (!test_2()) result=false;
return result;
}

void __fastcall TForm1::testAllClick(TObject *Sender)
{
if (MessageDlg ("Die Daten im Array werden gelöscht - weiter?",
    mtConfirmation, TMsgDlgButtons()<<mbYes<<mbNo, 0)==mrYes)
  {
    initTestUtils();
    testUtilsSummary(Memo1, test_All_3_4());
  }
}


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

typedef AnsiString StackElementType;

const int MaxS=5;
StackElementType Stack[MaxS];
int StackPtr=-1;

void enableButtons()
{
Form1->StackPop->Enabled=StackPtr!=-1;
Form1->StackTop->Enabled=StackPtr>-1;
Form1->StackPush->Enabled=StackPtr<MaxS-1;
}

void initStack()
{
StackPtr=-1;
enableButtons();
}

void pushStack(StackElementType e)
{
if (StackPtr<MaxS)
  {
    StackPtr++;
    Stack[StackPtr]=e;
  }
}

StackElementType topStack()
{
if ((0<=StackPtr) && (StackPtr<MaxS))
  return Stack[StackPtr];
else
  return "no data on stack "; 
}

void popStack()
{
if (StackPtr>=0)
  {
    StackPtr--;
  }
}


//----- Aufgabe 3 ------------------------------------------------

AnsiString TroepfelPi()
{
const int Stellen = 1000,
      Max = 10*(Stellen/3);

int Q[Max+1],U[Max+1],A[Max+1];
AnsiString pistr = "pi=";

for (int i=0; i<=Max; i++) A[i] = 2;

int S;
int qi=0;
for (int n=1; n<=Stellen; n++)
  {
    U[Max] = 0;
    for (int i=Max; i>=1; i--)
      {
        S = U[i]*i+10*A[i];
        A[i]   = S % (2*i-1);
        U[i-1] = S / (2*i-1);
      }
    S = U[0];
    A[1] = S % 10;
    S    = S / 10;
    if (S== 9)
      {
        Q[qi] = S;
        qi++;
      }
    else if (S==10)
      {
        for (int j=0; j<=qi-1;j++)
        if (Q[j] < 9) Q[j]++;
          else Q[j] = 0;
        for (int j=0;j<=qi-1;j++)
          pistr = pistr+IntToStr(Q[j]);
        qi = 1;
        Q[0] = 0;
      }
    else
      {
        for (int j=0;j<=qi-1;j++)
          pistr = pistr+IntToStr(Q[j]);
        qi = 1;
        Q[0] = S;
      }
  }
return pistr;
}

void testPi()
{
const
AnsiString pi1000 = "pi=3"  // die ersten 1000 Stellen von pi
       "141592653589793238462643383279502884197169399375105820974944"
       "592307816406286208998628034825342117067982148086513282306647"
       "093844609550582231725359408128481117450284102701938521105559"
       "644622948954930381964428810975665933446128475648233786783165"
       "271201909145648566923460348610454326648213393607260249141273"
       "724587006606315588174881520920962829254091715364367892590360"
       "011330530548820466521384146951941511609433057270365759591953"
       "092186117381932611793105118548074462379962749567351885752724"
       "891227938183011949129833673362440656643086021394946395224737"
       "190702179860943702770539217176293176752384674818467669405132"
       "000568127145263560827785771342757789609173637178721468440901"
       "224953430146549585371050792279689258923542019956112129021960"
       "864034418159813629774771309960518707211349999998372978049951"
       "059731732816096318595024459455346908302642522308253344685035"
       "261931188171010003137838752886587533208381420617177669147303"
       "598253490428755468731159562863882353787593751957781857780532"
       "1712268066130019278766111959092164201989";

AnsiString piStr=TroepfelPi();
int Stellen=0; // Vergleiche die beiden Strings zum Test

int j=1;
while ((j < piStr.Length()) &&  (j < pi1000.Length()))
  {
    if(piStr[j]==pi1000[j]) Stellen++;
    j++;
  }

Form1->Memo1->Lines->Add(piStr);
Form1->Memo1->Lines->Add("n="+IntToStr(Stellen)+" gleich ");
}

