Zaawansowane CPP/Ćwiczenia 11: Funktory

Ćwiczenie 1

Zaimplementuj adapter compose_f_gx_hy realizujący złożenie dwuargumentowe $f(g(x),h(y))$.

Ćwiczenie 2

Korzystając z klasy functor_traits zaimplementuj adpter bind1st, który bedzie działał zarówno dla funktorów jedno-, jak i dwuargumentowych.

Ćwiczenie 3

Zaimplementuj funktor implementujący, składanie funkcji poprzez wykonywanie ich po kolei np.:

macro(f1,f2)(x)

powinno wykonać

f1(x);f2(x);

Wartości zwracane przez te funkcje są ignorowane. Funkcja macro powinna zwracać funktor odpowiedniego typu (posiadający odpowiednie typy stowarzyszone) tak, aby możliwe było dalsze składanie np.:

macro(macro(f1,f2),f3)(x)

powinno wywołać:

f1(x);f2(x);f3(x);

Ćwiczenie 4

Zmodyfikuj powyższy szablon tak aby można było mieszać funkcje o różnej liczbie agrgumentów np.:

int f();
void g(double);
void h(double,int);

macro(f,g)(x);

powinno wywołać

f();g(x)}

a

macro(g,h)(3.14,0);

powinno wywołać

g(3.14);h(3.14,0)

Podpowiedź

Można zacząć od zaimplementowania pomocniczego adaptera call, który wywołuje funkcje dopasowując liczbę argumentów:

int f();
void g(double);
void h(double,int);

call<double>(f)(x); /* woła f();*/
call<double>(g)(x); /* woła g();*/
call<double,double>(f)(x,y); /* woła f();*/
call<double,int>(g)(x,i); /* woła g(x);*/
call<double,int>(h)(x,i); /* woła h(x,i);*/

Argumenty szablonu określają typy argumentów funktora zwracanego przez call<>().

Rozwiązanie

Nierekurencyjna funkcja przechodząca drzewo wgłąb może wyglądać następująco:

std::deque<node *> nodes;
nodes.push_back(_root);

while(!nodes.empty()) {
  node *nd  =    nodes.back();
  nodes.pop_back();

  if(node->right) nodes.push_back(node->right);
  if(node->left)  nodes.push_back(node->left);
}

Iterator będzie wykonywał ten algorytm krok po kroku. W każdym kroku węzeł nd będzie wezłem wskazywanym przez ten iterator. Jako oznaczenie końca iteracji wykorzystamy iterator wskazujący na węzeł pusty.

Definujemy klasę zagnieżdżoną wewnątrz binary_tree:

class iterator {
std::deque<node *> _nodes;
node *_current;

iterator(node *ptr  =    0):_current(ptr) {
  if(_current) {
    if(_current->right) 
       _nodes.push_back(_current->right);
    if(_current->left) 
       _nodes.push_back(_current->left);
}

iterator &operator++() {
  _current =   _nodes.back();
  _nodes.pop_back();

  if(_current) {
    if(_current->right) 
       _nodes.push_back(_current->right);
    if(_current->left) 
       _nodes.push_back(_current->left);
   }
   else
   _current =   0;
}

Żeby ta klasa zachowywała się jak wskaźnik dodajemy operatory:

public:
   T &operator*()  {return _ptr->_val;};
   T *operator->() {return &(_ptr->_val);};

Potrzebny jest też operator porównania:

 bool operator =    =   (const trivial_iterator&lhs) const {
   return this->_ptr =    =   lhs._ptr;
 } 
 bool operator! =   (const trivial_iterator&lhs) const {
   return !operator =    =   (lhs);
 }

Potrzebna jest jeszcze deklaracja:

friend class binary_tree;    

żeby klasa binary_tree mogła korzystać z konstruktora iterator(node *ptr).

W klasie binary_tree definiujemy funkcje:

 iterator begin() {return iterator(_root);}
 iterator end(){return iterator(0);}