Concept Of Recurrence Relations

Introduction to the Concept

g(n) = g(n-1) + 2n – 1
g(0) = 0
  • this defines function f(n) = n^2, and the recurrence relation:
f(n) = f(n-1) + f(n-2)
f(1) = 1
f(0) = 0

Solving a Recurrence Relation

Advertisements

Function Pointers.2

Concept of Callback Functions

Introduction to the concept

  • Function Pointers provide the concept of Callback Functions.I hope we still remember the Generic sorting algorithm that we have talked about in the previous post .This function  that sorts the items of a field according to a user-specific ranking(qsort). The field can contain items of any type, It’s passed to the sort function using void-pointer.Also the size of an element and the number of elements in the field itself has got to be passed, so if we need to write a prototype to this function will be as follows
Code Snippet
  1. void Qsort(void* field ,size_t nElements, size_t sizeOfElement,
  2. int(*int_sorter)(const void*, const void*));
  • Lets ask !! How can this sort-function sort the elements of the field without any information about the type of an element?
    • The answer is: that the Function receives  the pointer to a comparison-function (int_sorter) which takes void-pointers to two field-items, evaluates their ranking and return the result as an int .So, every time the sort algorithm needs a decision about the ranking of two items, it just calls the comparison-function via Function Pointer.
  • A Callback is done like a normal function call you just use the name of the function pointer instead of a function name.
Code Snippet
  1. void Qsort(void* field ,size_t nElements, size_t sizeOfElement,
  2.          int(*int_sorter)(const void* , const void* ))
  3. {
  4.     /*Item1, item2 are void-pointers*/
  5.     int theBiggestNumber = int_Sorter(item1,item2);
  6.     /*rest of the body*/
  7. }

How to implement a Callback to C++ Member Function?

  • Static Member Functions:
    • Static member functions do not need an object to be invoked.
  • Non-Static Member Functions:
    • In C++,  classes can have Non-Static member functions have an implicit parameter (this pointer), So the type of the object must be included as part of the type function pointer.The method is then used an object of that class by using one of the “pointer-to-member” operators (“*” for an object , “->” for pointer to object)
    • If you want to callback  to a member specific class you just change the code from an ordinary function pointer to  a pointer to a member function.
    • Lets Ask !! What can I do if I want to callback to a Non-Static member of any class?
      • Answer:
        1. We need to write a Static Member Function as a Wrapper function because the function does not know the type of the passed Object.
        2. The wrapper’s signature will be the same as the member function and pass to the function void* pointer to Object as an (Additional Argument || Global Variable ).
        3. The wrapper casts the void* pointer to a pointer to an instance of the correct class and call the member function.
Implementation of Callback to Non-Static C++ Member Function With Additional Argument
  1. #include <iostream>
  2. using namespace std;
  3. class ClassA
  4. {
  5. public:
  6.     // Non-Static Member function
  7.     void Display(const char *text)
  8.     {cout << text << endl;}
  9.     //Static Wrapper function
  10.     static void Wrapper(void* ptrToObject, char* text);
  11.     //For testing Callback
  12.     void doAnything(void* ptrToObject, void(*ptrToFunction)(void* ptrToObject, char* text));
  13. };
  14. void ClassA::Wrapper(void* ptrToObject, char* text)
  15. {
  16.     //Cast to void pointer to ClassA
  17.     ClassA* tempObject = (ClassA*)ptrToObject;
  18.     //Calling a Non-Static Member function
  19.     tempObject->Display(text);
  20. }
  21. void ClassA::doAnything(void* ptrToObject, void(*ptrToFunction)(void* ptrToObject, char* text))
  22. {
  23.     //Callback
  24.     ptrToFunction(ptrToObject,“This Is Callback Using Additional Argument “);
  25. }
  26. int main()
  27. {
  28.     ClassA *object;
  29.     object->doAnything((void*)&object,ClassA::Wrapper);
  30. }
  • You can try to implement Callback to a Non-Static Member functions with Global Variable by yourself.

References:

Special Thanks to: Omar Enayet (C++ Developer at NTP Software).

Function Pointers.1

Introduction To Function Pointers

What are Function Pointers?

  • Function pointers  are pointers – Variables – which point to the address of a function.
  • Actually Function pointers provide some extremely interesting, efficient and elegant programming techniques. You can use them to replace Switch-Statements or to Implement Callbacks.
  • A Function Pointer always points to function with a specific signature  , so all function this pointer will point to must have the same parameters and return type.

Introductory Example:

How To Replace Switch-Statement??
  1. #include <iostream>
  2. using namespace std;
  3. //#Definiation and declaration of Function pointers
  4. float Plus (float a, float b) { return a+b; }
  5. float Minus (float a, float b) { return a-b; }
  6. float Multiply(float a, float b) { return a*b; }
  7. float Divide (float a, float b) { return a/b; }
  8. void Switch(float a, float b, char opCode)
  9. {
  10.     float result;
  11.     switch(opCode)
  12.     {
  13.     case ‘+’ : result = Plus (a, b); break;
  14.     case ‘-‘ : result = Minus (a, b); break;
  15.     case ‘*’ : result = Multiply (a, b); break;
  16.     case ‘/’ : result = Divide (a, b); break;
  17.     }
  18.     cout << “Switch: 2+5=” << result << endl;
  19. }
  20. void Switch_With_Function_Pointer(float a, float b, float (*op)(float, float))
  21. {
  22.     float result = op(a, b); // call using function pointer
  23.     cout << “Switch replaced by function pointer: 2-5=”; // display result
  24.     cout << result << endl;
  25. }
  26. void Replace_A_Switch()
  27. {
  28.     cout << endl << “Executing function ’Replace_A_Switch’” << endl;
  29.     Switch(2, 5, ‘+’);
  30.     Switch_With_Function_Pointer(2, 5, Minus);
  31. }
  32. //#end Definiation and declaration of Function pointers
  33. int main()
  34. {
  35.     Replace_A_Switch();
  36.     return 0;
  37. }

The syntax of C++  Function Pointer:

  • There are two different types of Function Pointers :
    1. Pointers to static C++ member functions.
    2. Pointers to non-static C++ member functions.
  • The basic difference is that all pointers to non-static member functions need a hidden argument (“this.”pointer to an instance of the class).

Define a Function Pointer:

  • Function Pointer is nothing else than variable ,so it must be defined as usual.
  1. int (MyClass::*ptrMember)(float, char, char) = NULL;
  2. int (MyClass::*ptrConstMember)(float, char, char) const = NULL;

Initializing Function Pointer:

  • To initialize function pointer ,you must give it the address of the function in your program
  1. #include <iostream>
  2. using namespace std;
  3. void coutFunction(int x)
  4. {
  5.     printf( “%d\n”, x );
  6. }
  7. int main()
  8. {
  9.     void (*COUT)(int);
  10.     // the ampersand is optional 
  11.     COUT = &coutFunction;
  12.     return 0;
  13. }

Using Function Pointer:

  • To call the function pointed to by a function pointer, you treat the function pointer as though it was the name of the function you wish to call. The act of calling it performs dereferencing operation,  there’s no need to do it yourself:
  1. /* call coutFunction(note that you do not need to write (*COUT)(2) ) */
  2. COUT( 2 );
  3. /* but if you want to, you may */
  4. (*COUT)( 2 );

Generic Sorting Routine:

  • If you were to write a sort routine, you might want to allow the function’s caller to choose the order in which the data is sorted; some might need to sort the data in ascending order, others might prefer descending order . The much nicer way of allowing the user to choose how to sort the data is simply to let the user pass in a function to the sort function. This function might take two pieces of data and perform a comparison on them.
  1. #include <iostream>
  2. using namespace std;
  3. int int_sorter( const void *first_arg, const void *second_arg )
  4. {
  5.     int first = *(int*)first_arg;
  6.     int second = *(int*)second_arg;
  7.     if ( first < second )
  8.     {
  9.         return -1;
  10.     }
  11.     else if ( first == second )
  12.     {
  13.         return 0;
  14.     }
  15.     else
  16.     {
  17.         return 1;
  18.     }
  19. }
  20. int main()
  21. {
  22.     int array[10];
  23.     int i;
  24.     /* fill array */
  25.     for ( i = 0; i < 10; ++i )
  26.     {
  27.         array[ i ] = 10 – i;
  28.     }
  29.     qsort( array, 10 , sizeof( int ), int_sorter );
  30.     for ( i = 0; i < 10; ++i )
  31.     {
  32.         printf ( “%d\n” ,array[ i ] );
  33.     }
  34. return 0;
  35. }

Benefits of Function Pointers:

  •  Function pointers provide a way of passing around instructions for how to do something.
  •  You can write flexible functions and libraries that allow the programmer to choose behavior by passing function pointers as arguments.
  • This flexibility can also be achieved by using classes with virtual functions.