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

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.

Object Oriented Programming Project

C++ Emulator :

Team Members:

  1. Islam Ibrahim
  2. Anas Awad
  3. Ahmed Sakr

Project Idea:

  • Project idea based on emulating C++ language and implement features of text editors(Syntax highlighting ,word wrapping ..etc)

Project Features :

  1. Text Editor Features
    • C++ syntax Highlighter
    • Basic features ( create  project , Open , Remove ,…..etc)
  2. Emulator Features
  • this C++ Emulator can run C++ Code till recursive functions (loops , nested loops , if  & switch statements  ,nested if , arrays , functions ,

    recursive functions)

  • some libraries such as and are involved ,that support built in functions.

Implementation :

  • Programming language : Java, You can find the source code (here)
  • about syntax  highlighter : after implementing lexical analyzer for using programming language , I’ve implemented a syntax highlighter that  highlights each token based on its type if keyword or string literal……. etc.
  • about concepts of emulating you can find them Here  

Problems:

  1. if your written code contains “cin” and you opened the console and didn’t enter the required data ,  the console will crash if you try to open it again.
  2. If your code contains error and you run it for another time the console will not be editable.

all if these problems just in first version.

Recommendations:

  •  We Hope in next version we finish implement of some features of text editor such as indentation.

Project Experience Acquired:

  • learn more about Compilers “How to build compiler or interpreter”.
  • I’ve implemented lexical analyzer and Parse tree.
  • Make me interested in new area which is programming languages Industry and Engineering compilers.
  • How to apply OOP , OOA and OOD concepts.

Certifications : this project is certified from Dr.Gahada Nasr and got 2nd place with another project implemented by (Bassem Modar , Karim Magdy , Noran abo Doma , Hagar el Fiky) rest of our team members.

Thank You :

  • Dr.Ghada Nasr .. OOP course instructor ..
  • Dr.Mohammed Samy .. Teacher Assistant in my college .. His videos about interpreters were really helpful.
  • Mohammed Hesham .. (acmASCIS) president .. he directed me to the starting point.
  • Noran , Bassem , Hagar, karim … The rest of team members they were working on  (connect4 with 3D) graphics.

Thanks all of you, You were really helpful.

Why did I release a blog?

_This is my first post on my blog . I released it in 30/6/2011 “2nd year vacation”

_Why did I release this blog?

  • I’m interested in sharing knowledge , Science inspiring me , and I love research … so, I decided to do this to help people and share knowledge as I can.
  • I’ll be happy if people share me my future plans and suggest me what  can I do in my future steps?!
  • I have my own thoughts need to be shared.