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

  • There are many techniques to solve Recurrence Relations, the main techniques are Iteration Method (also known as expansion or unfolding method) and the Master Theorem method. 
  • In this post we’ll talk about Iteration Method Continue reading
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).