// 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 "AlgoU.h"
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;

__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}

#include <vector>
using std::vector;
#include <fstream>
#include <algorithm>

// --------------- Aufgaben 9.5.5 --------------------------

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

// a)
template<typename Container1, typename Container2>
bool Equal(Container1 c1, Container2 c2)
{
return (c1.size()==c2.size())
         && std::equal(c1.begin(),c1.end(),c2.begin());
/* Das ist wegen der short-circuit Auswertung im Wesentlichen
   gleichwertig zu

    if (c1.size()!=c2.size())
      return false;
    else
      return equal(c1.begin(),c1.end(),c2.begin());
*/
}

// b)
template<typename Container>
int Count(Container c, typename Container::value_type x)
{
return std::count(c.begin(),c.end(),x);
};

// c)
#include <iterator>
template<typename T>
int CountFileElements(const char* fn, T y)
{ // Anzahl der Dateielemente mit dem Wert y
std::ifstream fi(fn);
return std::count(std::istream_iterator<T>(fi),
                                 std::istream_iterator<T>(),y);
}

#include <set>
void Aufg1()
{
int a[5]={1,2,3,4,5};
vector<int> v(a,a+5);
std::set<char> s(a,a+5);
bool b1=Equal(s,v);
int i1=Count(v,1);
int i2=CountFileElements("c:\\test\\u.txt",1); // u.txt von Aufgabe 10.4
}

void __fastcall TForm1::Button_5_5_1Click(TObject *Sender)
{
Aufg1();
}


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

// a)
template<typename T> T MinValue(char* fn)
{
std::ifstream fi(fn);
return *min_element(std::istream_iterator<T>(fi),std::istream_iterator<T>());
}

// b)
template<typename C, typename T> T MinValue(const C& a)
{
return *min_element(a.begin(),a.end());
}

// c)
template<typename T> T MinValue(T* a, int n)
{
return *std::min_element(a,a+n);
}

void Aufg2()
{
int i=MinValue<int>("c:\\test\\u.txt"); // u.txt von Aufgabe 10.4
int a[3]={3,2,5};
int ai=MinValue(a,3);
vector<int> v(a,a+3);
int vi=MinValue<vector<int>,int >(v);
}

void __fastcall TForm1::Button_5_5_2Click(TObject *Sender)
{
Aufg2();
}

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

/* Zur Orientierung die Algorithmen aus stl.zip

template <class InputIterator, class Function>
Function for_each (InputIterator first,
InputIterator last, Function f)
{
    while (first != last) f(*first++);
    return f;
}

template <class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator
last, Predicate pred)
{
while (first != last && !pred(*first)) ++first;
    return first;
}

string s="123 und 123";
string::iterator p=find(s.begin(),s.end(),'2');
while (p!=s.end())
  {
    Form1->Memo1->Lines->Add(*p);
    p=find(p+1,s.end(),'2');
  }
*/


// a)
template<typename Container, typename Predicate, typename Function>
void for_each_if(Container c, Predicate pred, Function f)
{
Container::iterator i=find_if(c.begin(),c.end(),pred);
while (i!=c.end())
  {
    f(*i);
    i=find_if(++i,c.end(),pred);
  }
}

// b)
template<typename T, typename Predicate, typename Function>
void for_each_if(T* a, int n, Predicate pred, Function f)
{
T* i=std::find_if(a,a+n,pred);
while (i!=a+n)
  {
    f(*i);
    i=std::find_if(++i,a+n,pred);
  }
}

// c)
template<typename T, typename Predicate, typename Function>
void for_each_if(char* fn, Predicate pred, Function f)
{
std::ifstream fi(fn);
const std::istream_iterator<T> end=std::istream_iterator<T>();
std::istream_iterator<T> i=std::find_if(std::istream_iterator<T>(fi),end,pred);
while (i!=end)
  {
    f(*i);
    i=find_if(++i,end,pred);
  }
}

bool all(int i)
{
return true;
}

bool odd(int i)
{
return i%2==1;
}

void print(int i)
{
Form1->Memo1->Lines->Add(i);
}

bool first_odd(std::pair<int,int> i)
{
return i.first%2==1;
}

void print_pair(std::pair<int,int> i)
{
Form1->Memo1->Lines->Add(IntToStr(i.first)+": "+IntToStr(i.second));
}

// Auch diese Lösungsvarianten sind möglich:
template<typename Container, typename Predicate, typename Function>
void for_each_if_1(Container c, Predicate pred, Function f)
{
for (Container::iterator i=c.begin();i!=c.end();i++)
  if (pred(*i)) f(*i);
}

template<typename T, typename Predicate, typename Function>
void for_each_if_1(T* a, int n, Predicate pred, Function f)
{
for (int i=0;i<n;i++)
  if (pred(*(a+i))) f(*(a+i));
}

template<typename T, typename Predicate, typename Function>
void for_each_if_1(char* fn, Predicate pred, Function f)
{
ifstream fi(fn);
T i;
while (!(fi>>i))
  {
    if (pred(i))
      f(i);
  }
}

#include <map>
void Aufg3()
{
int a[5]={1,2,3,4,5};
vector<int> vi(a,a+5);
Form1->Memo1->Lines->Add("1-5:");
for_each_if(vi,all,print);
for_each_if_1(vi,all,print);

for_each_if(a, 5, all, print);
for_each_if_1(a, 5, all, print);
Form1->Memo1->Lines->Add("u:");
for_each_if<int>("c:\\test\\u.txt",all,print);
for_each_if_1<int>("c:\\test\\u.txt",all,print);

Form1->Memo1->Lines->Add("odd:");
for_each_if(vi,odd,print);
for_each_if_1(vi,odd,print);

for_each_if(a, 5, odd, print);
for_each_if_1(a, 5, odd, print);
// return;
Form1->Memo1->Lines->Add("odd-2:");
for_each_if<int>("c:\\test\\u.txt",odd,print);

for_each_if_1(vi,all,print);

std::map<int,int> m;
m.insert(std::make_pair(1,1));
m.insert(std::make_pair(2,4));
m.insert(std::make_pair(3,9));
for_each_if(m,first_odd,print_pair);
}

void __fastcall TForm1::Button_5_5_3Click(TObject *Sender)
{
Aufg3();
}


// --------------- Aufgabe 4 -------------------------------

namespace my_STL {

/*
In algo.h aus "ftp://butler.hpl.hp.com/stl/stl.zip" sind
nur ältere Versionen von count und count_if enthalten, die
nicht mehr zum aktuellen C++-Standard gehören.

In der STL von SGI (http://www.sgi.com/tech/stl/download.html)
sind diese Algorithmen folgendermaßen implementiert:
*/

using namespace std;

template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count(InputIterator first, InputIterator last, const T& value)
{
  typename iterator_traits<InputIterator>::difference_type n = 0;
  for ( ; first != last; ++first)
    if (*first == value)
      ++n;
  return n;
}

template <class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator first, InputIterator last, Predicate pred)
{
  typename iterator_traits<InputIterator>::difference_type n = 0;
  for ( ; first != last; ++first)
    if (pred(*first))
      ++n;
  return n;
}

/* **** alte Versionen (nicht mehr im C++-Standard, aber aus STL.zip
template <class InputIterator, class T, class Size>
void count(InputIterator first, InputIterator last, const T& value,
       Size& n) {
    while (first != last)
    if (*first++ == value) ++n;
}

template <class InputIterator, class Predicate, class Size>
void count_if(InputIterator first, InputIterator last, Predicate pred,
          Size& n) {
    while (first != last)
    if (pred(*first++)) ++n;
}
*/

// In algo.h aus "ftp://butler.hpl.hp.com/stl/stl.zip" sind
// die Algorithmen min_element usw. folgendermaßen implementiert:

template <class ForwardIterator>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last)
{
    if (first == last) return first;
    ForwardIterator result = first;
    while (++first != last)
    if (*first < *result) result = first;
    return result;
}

template <class ForwardIterator, class Compare>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
                Compare comp)
{
    if (first == last) return first;
    ForwardIterator result = first;
    while (++first != last)
    if (comp(*first, *result)) result = first;
    return result;
}

template <class ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last)
{
    if (first == last) return last;
    ForwardIterator next = first;
    while(++next != last) {
    if (*first == *next) return first;
    first = next;
    }
    return last;
}

template <class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last,
                  BinaryPredicate binary_pred)
{
    if (first == last) return last;
    ForwardIterator next = first;
    while(++next != last) {
    if (binary_pred(*first, *next)) return first;
    first = next;
    }
    return last;
}


template<typename Container, typename Function>
void for_each(Container c, Function f)
{
std::for_each(c.begin(),c.end(),f);
}

template<typename T, typename Function>
void for_each(char* fn, Function f)
{
ifstream fi(fn);
std::for_each(istream_iterator<T>(fi),istream_iterator<T>(),f);
}

template<typename T, typename Function>
void for_each(T* a, int n, Function f)
{
std::for_each(a, a+n, f);
}

} // end of namespace my_STL


void __fastcall TForm1::Button_5_5_5Click(TObject *Sender)
{
int a[5]={1,5,2,4,4};
vector<int> v(a,a+5);
std::set<double> s(a,a+5);
my_STL::for_each(v,print);
my_STL::for_each(s,print);
my_STL::for_each<int>("c:\\test\\u.txt",print);
my_STL::for_each(a,5,print);
int i=my_STL::count(v.begin(),v.end(),1);
int j=my_STL::count_if(v.begin(),v.end(),odd);
int k=*my_STL::min_element(v.begin(),v.end());
bool found=my_STL::adjacent_find(v.begin(),v.end())!=v.end();
}


//------ Aufgabe 9.5.19 --------------------------------------------

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

template <typename Container>
typename Container::value_type Median(Container c)
{
nth_element(c.begin(),c.begin()+c.size()/2,c.end());
return *(c.begin()+c.size()/2);
}

void test_Median()
{
vector<double> v;
double md=Median(v);
}

void __fastcall TForm1::Button_5_19_1Click(TObject *Sender)
{
test_Median();
}


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

template <typename Container1, typename Container2>
void MaxElements(Container1 src, int n, Container2& dest)
{
partial_sort(src.begin(),src.begin()+n,src.end(),
             std::greater<typename Container1::value_type>());
copy(src.begin(),src.begin()+n,back_inserter(dest));
}

template <typename T, typename Container>
void MaxElements(char* fn, int n, Container& dest)
{
ifstream f(fn);
vector<T> v;
std::copy(std::istream_iterator<T>(f),std::istream_iterator<T>(),std::back_inserter(v));
MaxElements(v,n,dest);
}

template <typename T, typename Container2>
void MaxElements(T* src, int n, int m, Container2& dest)
{
std::partial_sort(src,src+n,src+m,std::greater<T>());
copy(src,src+n,back_inserter(dest));
}


void test_MaxElements()
{
int a[6]={1,2,3,4,5,6};
vector<int> v(a,a+6);
vector<int> s;
MaxElements(v,3,s);
MaxElements(a,2,6,s);
my_STL::for_each(s,print);
MaxElements<int>("c:\\test\\u.txt",2,s);
my_STL::for_each(a,6,print);
my_STL::for_each(s,print);
}

void __fastcall TForm1::Button_5_19_2Click(TObject *Sender)
{
test_MaxElements();
}


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

template <typename Container>
void Remove(Container& c, typename Container::value_type x)
{
c.erase(remove(c.begin(), c.end(),x),c.end());
}

void test_Remove()
{
int a[4]={1,2,3,4};
vector<int> v(a,a+4);
Remove (v,2);
my_STL::for_each(v,print);
}

void __fastcall TForm1::Button_5_19_3Click(TObject *Sender)
{
test_Remove();
}


// --------------- Aufgabe 4 -------------------------------

template <typename T>
void merge_files(char* in1fn, char* in2fn, char* outfn)
{
using namespace std;
ifstream in1(in1fn);
ifstream in2(in2fn);
ofstream out(outfn);
merge(istream_iterator<T>(in1),
      istream_iterator<T>(),
      istream_iterator<T>(in2),
      istream_iterator<T>(),
      ostream_iterator<T>(out,"\n"));
}

void make_file(char* fn, int n)
{
ofstream f(fn);
for (int i=0; i<n; i++)
  f<<i<<std::endl;
}


void test_merge_files()
{
using std::string;
string s1="125", s2="126", s;
bool b1=binary_search(s1.begin(),s1.end(),'2'); // b=true
bool b2=binary_search(s1.begin(),s1.end(),'3'); // b=false
merge(s1.begin(),s1.end(),s2.begin(),s2.end(),back_inserter(s));  // s="112256"

char* in1fn="int1.dat";
char* in2fn="int2.dat";
char* outfn="int.dat";
make_file(in1fn, 100);
make_file(in2fn, 100);

merge_files<int>(in1fn,in2fn, outfn);
}

void __fastcall TForm1::Button_5_19_4Click(TObject *Sender)
{
test_merge_files();
}

// --------------- Aufgabe 5 -------------------------------

void write_call(vector<int> p, ofstream& f)
{
  f<<"f(";
  for (vector<int>::iterator i=p.begin();i!=p.end()-1;i++)
    f<<*i<<",";
  f<<*(p.end()-1)<<");"<<std::endl;
}

void make_calls()
{
ofstream f("calls.cpp");
int args[4]={1,2,3,4};
vector<int> p(args,args+4);
write_call(p,f);
while (next_permutation(p.begin(),p.end()))
  write_call(p,f);
}

void __fastcall TForm1::Button_5_19_5Click(TObject *Sender)
{
using namespace std;
string s1="1544256", s2=s1;
partition(s1.begin(),s1.end(), bind1st(greater<char>
  (),'4' )); // s=1244556
stable_partition(s2.begin(),s2.end(),
 bind1st(greater<char>(),'4' )); // s=1254456 
make_calls();
}

