Design and Implementation Idea of POLYMORPHISM in C [ non - object oriented language] Part IV

DISCUSSION –

1.A function pointer restricts (via the function prototype) the type of parameters passed to the function it is pointing to. One can use void pointer parameters to allow for varying parameter types, but this decreases the code readability (i.e. function prototypes include void pointer arguments instead of meaningful types) and disables parameter type checking.

2.Code Reuse is largely possible. If some new type comes in we don’t need to modify the original source code.

3.User programming is relatively simpler ... but implementation programming is quite difficult because of the large number of referencing and dereferencing of pointers to function that are highly required here.

4.Polymorphism thus obtained can be used with other data structure objects as well. It can be used with more then one layer of dependence i.e. objects hierarchy.


Another Approach -

Another approach is to introduce a common structure, which will be passed as parameter to the polymorphic function, hiding all type-dependant data in a special field of this structure. This special field is usually a void pointer or a union and is used as private storage space for each implementation of the polymorphic function.


This is all for polymorphism in C for time being. Hope you would benefit from the post. Do write me your suggestions and remarks.

xoxo
aL

Design and Implementation Idea of POLYMORPHISM in C [ non - object oriented language] Part III

Implementation

#include
#include
#include

#define MAX_SIZE_STACK 100

// here for a basic type only two methods are considered i.e. get() and print()
// and their corresponding index in the virtual_table are as
#define COUNT_METHOD 2

#define METHOD_GET 0
#define METHOD_PRINT 1

// defining general type i.e. super class for the different types

/***************** General type ***************************/

struct general_type {
// vtable is a pointer to an array of pointers to functions which takes in pointer to
// a general type and returns int
int (*(*pvtable)[COUNT_METHOD])(struct general_type *);
};

// creating an array of size COUNT_METHOD to pointers of function
typedef int (*vtable_general_type[COUNT_METHOD])(struct general_type *);

/************* methods for general_type *********************/

// constructor for general_type object

int general_type_ctor(struct general_type * this) {
// setting up the virtual table field
this->pvtable = (vtable_general_type *)malloc(sizeof(vtable_general_type));
this->pvtable[0][0] = NULL;
this->pvtable[0][1] = NULL;
return 0;
}


/******************** specific_type1 *************************/

struct specific_type1 {
int (*(*pvtable)[COUNT_METHOD])(struct specific_type1 *);



int data;
};

/************* methods for specific_type1 *********************/
typedef int (*vtable_specific_type1[COUNT_METHOD])(struct general_type *);

// constructor for specific_type1 object
int specific_type1_ctor(struct specific_type1 * this) {
// it's constructor first calls the constructor of the base class
general_type_ctor((struct general_type *) this); // typecasting "this"
this->data = 0;
/* set up vtable field */
this->pvtable = (vtable_specific_type1 *)malloc(sizeof(vtable_specific_type1));
this->pvtable[0][0] = &specific_type1_get;
this->pvtable[0][1] = &specific_type1_print;
}

int specific_type1_get(struct specific_type1 * this) {
/* Implement the input of object this */
}

int specific_type1_print(struct specific_type1 * this) {
/* Implement the output of object this */
}


/******************** specific_type2 *************************/
struct specific_type2 {
int (*(*vtable)[COUNT_METHOD])(struct specific_type2 *);
float data;
};

/************* methods for specific_type2 *********************/

// constructor for specific_type1 object
int specific_type2_ctor(struct specific_type2 * this) {
/* implement it's constructor similarly as the previous one */
}

int specific_type2_get(struct specific_type2 * this) {
/* Implement the input of object this */
}

int specific_type2_print(struct specific_type2 * this) {
/* Implement the output of object this */
}


/***********************************************************************/
/******** stack implementation using general type *********************/
/***********************************************************************/

typedef struct _stack {
// stack has pointer to an array of general type
// and also has the last index
struct general_type *list[MAX_SIZE_STACK];
int top;
} stack;


stack * stack_initialize() {
int i;
stack * s;
s = (stack *)malloc(sizeof(stack));
for(i=0; ilist[i] = (struct general_type *)malloc(sizeof(struct general_type));
}
s->top = -1;
return s;
}

struct general_type * top_of_stack(stack * s) {
struct general_type * temp;
if(s->top<0>list[s->top] == NULL )
temp = NULL;
else
temp = s->list[s->top];

return temp;
}

stack * push(stack * s, struct general_type * new) {
s->top ++;
s->list[s->top] = memcpy(s->list[s->top],new,sizeof(struct general_type));
return s;
}

stack * pop(stack * s) {
// error condition if s->top <= 0 s->top --;
return s;
}

/**********************************************************************/
/****** main program to check the working of heterogeneous stack ******/
/**********************************************************************/

int main() {
stack *s;
struct general_type * gt1, *gt2;
struct specific_type1 * st1a, * st1b; // making instances
struct specific_type2 * st2a, * st2b;

// initializing stack
s = stack_initialize();

// doing some known operations

st1a = (struct specific_type1 *)malloc(sizeof(struct specific_type1)); // allocating memory
specific_type1_ctor(st1a); // calling constructor for setting appropriate vtables

st1b = (struct specific_type1 *)malloc(sizeof(struct specific_type1));
specific_type1_ctor(st1b);

st2a = (struct specific_type2 *)malloc(sizeof(struct specific_type2)); // allocating memory
specific_type2_ctor(st2a); // calling constructor for setting appropriate vtables

// to fetch the input
(*(*st1a->pvtable)[METHOD_GET])(st1a); // to get the data of object
(*(*st2a->pvtable)[METHOD_GET])(st2a); // to get the data of object

// using polymorphism
gt1 = (struct general_type *)st1a; /* typecasting required */
gt2 = (struct general_type *)st2a; /* typecasting required */

s = push(s,gt1);
s = push(s,gt2);

/* similar working rule for other stack operations */

gt1 = top_of_stack(s);

(*(*gt1->pvtable)[METHOD_PRINT])(gt1); // to print the data of object

return 0;
}


xoxo
aL

Design and Implementation Idea of POLYMORPHISM in C [ non - object oriented language] Part II

Design Document -

Here we are required to create a stack which can have element of different types.

Important notes -

In order to apply Objected Oriented Programming concepts to C code, classes are mapped to structs and attributes to struct members and methods to function pointers.
C language has the ability to store pointers for functions as a basic data type, and the ability to call a function from such a function pointer. We can associate with each instance (objects of structures) a table of functions. When a method call on a particular instance is executed, the function table for that instance (actually these tables are shared among the instances of a class), is used to find the proper function to execute.

Define objects –

Here I have defined some Structures “general type”, “specific type 1”,” specific type 2”, etc. General type is like the super class from which other specific type classes are formed i.e. like sub classes. Each object has the appropriate data fields. Here is no type field associated with a structure and it is substituted by (at struct offset 0--the first field) with a vtable "pointer to an array of pointers to functions returning int."

There are only two functions associated with each object. Those are get () method and print () method. Get () is used to take input of the data fields of object and print is used for outputting those data fields.


Define vtables - actual polymorphism implementation

1.Virtual tables "general type vtable", "specific type 1 vtable", "specific type 2 vtable" and others are designed. Since there are no defined methods on General type object, that vtable is empty. I have just put a null pointer in the table.

2.The various constructors *_ctor() methods of objects are implemented such that they set the vtable pointer of the appropriate object.

3.#define constants are set up to identify offsets within the vtables. For example, the get() method will always be first in "specific type 1 vtable", "specific type 2 vtable" and others since it is the first (and only) method in those objects.
a.Example : #define METHOD_GET 0

4.The size of a class’s vtable is the maximum number of methods in its interface.



The pattern for invoking a method is:

(*(*object->vtable)[method-index])(object);


xoxo
aL

Design and Implementation Idea of POLYMORPHISM in C [ non - object oriented language] Part I

Here we were required to design a polymorphic container (say, a stack) using the features provided by a procedural/modular programming language supporting ADT implementation. (Do not use polymorphic features of the language, and do not use a kind of tag i.e. any sort of type field).


Design document and Implementation provided in subsequent posts.


xoxo
aL

Lehman Brothers FTA Technical and HR interview Experience

Technical (for about 50 min)

It started with some puzzles,

1. Given 7 gold bars connected with ropes, you have to give a labour his payment for the day with one gold bar. You have to minimize the number of cuts (i.e. of ropes) so that you pay the labour for 7 days. He can never be under or over paid. <2>
2. The next was the 4 persons crossing the bridge who take different times (10s, 5s, 2s, 1s)... they have to carry a lamp ..... only 2 persons can travel the bridge at a time. Optimize the total time required. You may wanna propose a general strategy to deal with n people all with different times.

Project related questions.

Internship related questions.

Computer Organization and Architecture related - how many functions did you implement in your 4 - bit CPU, name them. How many functions can be implemented, why the need for 0000 one. What is max bit size CPU available.

Cryptography - They asked about elliptic cryptography.

Sorting Related

Given two list of very large size (say 10 MB), how would you check that each element of one is present in the other. Start from the Brute force method, state its complexity. From here on start optimizing this check one step at a time, on the basis of Space and Time.

Knowledge of Sorting methods, their complexities, when and where will they be used.

Link List related

Reverse a single link list. Use minimum pointers. Do iteratively and also recursively, from front end and/or back end.

Given a pointer to an intermediate node of a link list whose head pointer we do not have, how would you delete it.

There were few other questions on linked list

Binary Tree Related

Questions related to tree heights , whats is the maximum and minimum height
of the tree. Write Mathematical expression for the height.

Write code to find the average height of the of the tree. Write code for finding maximum and minimum height of the tree.

Asked about other Search algorithms, other than binary Search.

There were some questions in between from other fields as well which I could no remember now. All these questions pretty much sums up the technical part.

Now the HR part .... (huff puff) (for about 20-25 min)

1. Tell something about yourself.
2. Tell about your family.
3. Why not microsoft or google.
4. Why Mumbai when you can work in Bangalore where your brother is.
5. Where do you see yourself in 5 years.
6. Why not research.
7. What if you get a call from IIM A, B, C.
8. What if you get a call from IIM L, K, I.
9. Any Idea about firms like us (competitors).
10. What do you expect from the company.
11. How our Job profile different from others.
12. Hows our company different from others.
    

There were other questions as well( i will post them when i remember ;-) ].

xoxo
aL

How to display a percentage-done indication on the screen?

The character '\r' is a carriage return without the usual line feed, this helps to overwrite the current line. The character '\b' acts as a backspace, and will move the cursor one position to the left.

XOXO
aL


Sudoku verifier using bit fields

char VerifySudoku(char grid[81])
{
unsigned int bitFlags = 0;
unsigned short buffer; // to speed up things
char r, c;

for (r = 0; r < bitflags =" 0,">
{
for (c = 0; c <>
{
buffer = r/3*3+c/3;

// check horizontally
bitFlags |= 1 << (27-grid[(r<<3)+r+c])>
// check vertically
| 1 << (18-grid[(c<<3)+c+r])
// check subgrids
| 1 << (9-grid[(buffer<<3)+buffer+r%3*3+c%3]);
}
if (bitFlags != 0x7ffffff)
return 0;
}
return 1;
}