Wednesday, June 30, 2010
Turbo C
Principles of Compiler Design
OVERVIEW
A compiler or interptreter for a programminning language is often decomposed into two parts:
1. Read the source program and discover its structure.
2. Process this structure, e.g. to generate the target program.
Why to learn it?
To enhance understanding of programming languages
• To have an in-depths knowledge of low-level machine executables
• To write compilers and interpreters for various programming languages and domain-specific languages
Examples: Java, JavaScript, C, C++, C#, Modula-3, Scheme, ML, Tcl/Tk, Database Query Lang., Mathematica, Matlab, Shell-Command-Languages, Awk, Perl, your .mailrc file, HTML, TeX, PostScript, Kermit scripts, .....
• To learn various system-building tools : Lex, Yacc, ...
• To learn interesting compiler theory and algorithms.
• To learn the beauty of programming in modern programming lang.
Sunday, April 25, 2010
Index Sequential Search
#define MAX 24
void createIndex(int index[],int isize,int arr[],int asize)
{
int i,j;
for(i=0,j=0;i
{
index[j]= arr[i];
}
index[j] = arr[asize-1];
}
int indexSeqSearch(int val, int index[], int isize, int arr[], int asize)
{
int i=0,j=0,pos=0;
int high=0,low=0;
if(val > index[isize-1] && val < index[0])
return -1;
while(i
{
if(val == index[i])
{
pos = 8 * i;
return pos;
}
if(val < index[i])
{
low = 8 * (i-1);
high = 8 * i;
break;
}
else
{
low = 8 * i;
high = 8 * (i+1);
}
i++;
}
while(low < high)
{
if(val == arr[low])
return low;
else
low++;
}
return -1;
}
int main()
{
int arr[MAX]={ 8,14,26,38,72,115,306,321,329,387,409,512,540,567,583,592,602,611,618,741,798,811,814,876};
int index[(MAX/8)+1]={0};
createIndex(&index[0],(MAX/8)+1,&arr[0],MAX);
int opt=0,pos=0;
while(opt < MAX)
{
pos = indexSeqSearch(arr[opt],&index[0],(MAX/8)+1,&arr[0],MAX);
if( pos != -1)
{
printf("\n%d found at position %d",arr[opt],pos);
}
else
printf("\n%d not found.",arr[opt]);
opt++;
}
return 0;
}
PL Practical Exam Variation List
2. Perform Set operations using linked list
3. String operations without using standard library functions
4. Matrix operations : Add, Sub, Multiply, Saddle Point
5. Matrix operations : Add, Sub, Multiply, Transpose
6. Matrix operations : Add, Sub, Transpose, Check for Magic Square
7. Matrix operations : Multiplication, Transpose, Check for magic Square
8. Create a Database using array of structures and perform following operations
a. Add
b. Delete
c. Modify
d. Display
e. Search and
f. Sort
9. Create a Database using text files and perform following operations
a. Add
b. Delete
c. Modify
d. Display
e. Search and
f. Sort
10. Implement Sorting methods using functions
a. Bubble
b. Selection
11. Implement Sorting methods using functions
a. Bubble
b. Insertion
12. Implement Sorting methods using functions
a. Insertion
b. Selection
13. Implement Sorting methods using functions
a. Shell Sort
b. Bubble Sort
14. Implement Sorting methods using functions
a. Shell Sort
b. Selection
15. Implement Sorting methods using functions
a. Shell
b. Insertion
16. Implement sorting methods using recursion
a. Quick Sort
b. Merge Sort
17. Implement Searching Methods
a. Sequential Search
b. Binary Search
18. Implement Searching Methods
a. Indexed Sequential Search
b. Binary Search
19. Implement Searching Methods
a. Sequential Search
b. Fibonacci Search
20. Represent Polynomial using structures and write a menu driven program to perform addition, Multiplication and Evaluation
21. Represent Sparse matrix using array and perform matrix addition, simple and fast transpose
22. Create SLL and Write a menu driven program to perform operations on it like
a. insert an element: at start, In between, At end
b. Search
c. Delete
d. Reverse
e. Display
23. Create CLL and Write a menu driven program to perform operations on it like
a. insert an element : at start, In between, At end
b. Search
c. Delete
d. Reverse
e. Display
24. Create DLL and Write a menu driven program to perform operations on it like
a. insert an element: at start, In between, At end
b. Search
c. Delete
d. Reverse
e. Display
25. Create CDLL and Write a menu driven program to perform operations on it like
a. insert an element: at start, In between, At end
b. Search
c. Delete
d. Reverse
e. Display
26. Create two SLLs, sort one after creation and one while creation using pointer manipulation. Merge these two lists into one list without creating a new node or swapping of the data
27. Create two DLLs, sort one after creation and one while creation using pointer manipulation. Merge these two lists into one list without creating a new node or swapping of the data
28. Represent Polynomial using CLL and write a menu driven program to perform addition, Multiplication and Evaluation
29. Implement stack as an ADT using array. Use this ADT to perform expression conversion and evaluation- Prefix to postfix
30. Implement stack as an ADT using array. Use this ADT to perform expression conversion and evaluation- Postfix to Prefix
31. Implement stack as an ADT using array. Use this ADT to check the correctness of parenthesized expression e.g. (a))-wrong, (a+b)+c-correct
32. Represent a circular queue using linked list and write a program to perform operations like Insert, Delete, finding front and rear element
33. Create a Database using linked list and perform following operations
a. Add
b. Delete
c. Modify
d. Display
e. Search and
f. Sort
Saturday, April 24, 2010
DSL Practical Exam Variation List From Anil Bhadgale Sir
ASSIGNMENTS LIST
Group A (C++ programming)
• Create binary search tree and perform recursive traversals (Preorder, Inorder and Postorder)
• Create binary search tree and perform non recursive traversals (Preorder, Inorder and Postorder)
• Create a binary expression tree for any expression (infix/prefix/postfix) and perform non recursive traversals.
Eg. A+B
+AB
+
/ \
A B
• Create a binary expression tree for any expression (infix/prefix/postfix) and perform recursive traversals.
• Create a binary expression tree for any expression(infix/prefix/postfix) and perform non recursive Inorder and Preorder traversals and recursive Postorder traversal( any combination can be asked in examination)
• For any of above tree assignment perform deletion of node operation, The tree should be updated after deleting the node( assume different cases like lea, non leaf node with single child/double child)
• Create binary search tree and find height of the tree, print leaf nodes.
• Create binary tree for string as information and find height of the tree, print leaf nodes and display siblings of each other, find the number of subtrees that can be generated.
• Create binary tree by asking the user to insert (left/right).Find mirror image, print original and mirror image using level-wise printing
• Create in-order threaded binary tree and perform traversals(also deletion of node)
• Represent graph using adjacency list (Adjacency matrix) and perform DFS(Non recursive/recursive )
• Represent graph using adjacency list (Adjacency matrix) and perform BFS (Non recursive/recursive )
• Represent graph using adjacency list or matrix and generate minimum spanning tree using Prism’s algorithm
• Represent graph using adjacency list or matrix and generate minimum spanning tree using Kruskal’s algorithm (prims and kruskals having same minimum weight)
• Represent graph using adjacency list or matrix and find shortest distance and path using Dijkstra’s Algorithm
• Implementation of AVL tree
• Implementation of direct access file using different collision resolution techniques(using linear probing/chaining)
• Different File operations using command line arguments on sequential file.
Group B (STL implementation)
• Write a program to add binary numbers (assume one bit as one number)
• Implement Dqueue (Double ended queue)
• Use STL for Sorting and searching with user-defined records such as Person Record
(Name, birth date, telephone no), item record (item code, item name, quantity and cost)
• .Implementation of SLL , DLL and CLL
• Implementation of stack & queue using SLL
Group C
• Write a C++ program to implement a small database mini project to understand persistent objects and operations on sequential files (eg library information, inventory systems, automated banking system, reservation systems etc.) For example, write a program to create a database for reservation
system using information such as Name, sex, age, starting place of journey and destination. Program should have following facilities
a) To display entire passenger list
b) To display particular record
c) To update record
d) To delete and sort record
Use Exception Handling for data verification
(Subject I/c)
Thursday, April 15, 2010
Object Oriented Design
This chapter from Jalote gives us insight into the object oriented design and analysis.
The OO concepts which are learned from C++ point of view, will be much more clear and their applications in real world projects and thier relevancy will be clear too.
OOP Variations
2. Write a C++ program to find the factorial of a given number using Function
3. Write a C++ program using SWITCH CASE structure to display the given number in words. (enter number between 1 and 9).
4. Write a C++ program to check whether the given string is palindrome or not
5. Write a C++ program to find the number of Odd and Even numbers in a given array.
6. Write a C++ program to transpose a 3x3 matrix.
7. Write a C++ program to add two 3x3 matrices
8. Write a C++ program using function to determine whether the given number is prime or not
9. Write a C++ program to define a class employee with the following specification
private members of class employee
empno – integer
ename - 20 characters
basic – float
Netpay, hra, da, float
calculate() - A function to find the basic+da+hra with float return type
public member functions
havedata() - A function to accept values for empno, ename, basic,hra,da and call
calculate() to compute netpay
dispdata() - A function to display all the data members on the screen
10. Write a C++ program that uses function overloading to do the following tasks
a) find the maximum of two numbers (integers)
b) find the maximum of three numbers (integers)
11. Write a C++ program to find the sum and difference of two numbers using inheritance
ADD SUBTRACT
public add(), accept(), plus() subtract(), minus()
private sum() sub()
protected num1, num2
12. Write a C++ program to get the following output
C
CO
COM
COMP
COMPU
COMPUT
COMPUTE
13. Animal insurance
Write a program that prints the insurance fee to pay for a pet according to the following rules:
• A dog that has been neutered costs $50.
• A dog that has not been neutered costs $80.
• A cat that has been neutered costs $40.
• A cat that has not been neutered costs $60.
• A bird or reptile costs nothing.
• Any other animal generates an error message.
The program should prompt the user for the appropriate information, using a code to determine the kind of animal (i.e. D or d represents a dog, C or c represents a cat, B or b represents a bird, R or r represents a reptile, and anything else represents some other kind of animal).
After printing the insurance fee, the program should ask the user if (s)he wants to insure another animal.
Remember to write the program in a clear style with indentation.
14. Pupils' heights
The health visitor at a school is going to measure the heights of all pupils. For each class she makes a statistics giving the number of pupils of each height and the average height.
Make a C++ program that helps the health visitor making the statistics.
Example:
In a class with 20 pupils the heights of the individual pupils, in centimeters, are:
175, 167, 160, 164, 183, 187, 188, 179, 176, 175,
169, 175, 176, 178, 165, 160, 173, 165, 187, 178
The program should read in all the numbers and make a table like this:
height number of pupils
160 2
164 1
165 2
167 1
... ...
... ...
188 1
average height 174.0
15. Pocket calculator
The program should read in a text string containing a list of numbers separated by + or - and output the sum. The program should also tell how many positive numbers and how many negative (subtracted) numbers there are.
Example:
input: 8.4 + 2.6 - 3.5 + 1
output: result = 8.5, positive numbers: 3, negative numbers: 1.
The input cannot contain any other operators than + and -. Spaces are allowed.
The program should be organized so that main reads the input as a single text string and outputs the results. The interpretation of the text string and calculation of results should be in a separate sub-function. Do not use global variables.
Tip: the function atof can read a number from a text string. Anything that comes after the number is ignored by atof.
16. The political oracle
In the year 2097, the president of the United States of Europe doesn't have the time to write his own political speeches because he is busy hosting a lottery show on TV. His secretary has asked you to make a computer program which can write political speeches by combining popular clichés randomly. A statement is generated by combining randomly selected phrases from each of the categories G, A, S, and V below according to the scheme G - A - S - V - G - A - S. For example:
"My improved freedom benefits our common responsible national security."
Hint: The function random(n) will give you a random number in the interval from 0 to n-1. Use this function to choose a cliché from a category containing n clichés. The function randomize() must be called in the start of the main program before the first call to random(n).
Write #include
Category G
my, our common, the party's, my family's, our children's, my fellow Europeans', the government's, the industry's, the consumers', the immigrants', the only truly
Category A
improved, responsible, peacekeeping, free, pro-life, politically correct, integrated, federal, progressive, anti-crime, drug-addicted, gradual, democratic, genetically engineered, racial
Category S
freedom, national security, abuse, opportunity, tax cut, congress, task force, Europe, decision, dialogue, future, community, answer, environment, set of family-values, legislation, discrimination
Category V
benefits, improves, decreases, supports, is built on, is the best guarantee for, creates an opportunity for, forms, is necessary for, will be established to combat
17. Matrix operations
Write a program that can do the following:
• addition of two matrices
• subtraction of two matrices
• multiplication of a matrix by a scalar
• multiplication of a matrix by a matrix
• transpose a matrix
The order of the matrices could be 3 x 3, or variable if you want.
Equations
18. Make a function that can solve two linear equations with two unknowns. The solution should be returned through pointer parameters or reference parameters. Make a program that inputs the six coefficients, calls the function, and outputs the solution.
19. Make a function that solves a quadratic equation, and a program that uses this function. The function should return the number of solutions as well as the solutions (if any) to the calling program.
In case you've forgotten everything you've learned in math, here are the formulae:
Discriminant
20. Bit manipulation
Write a function that prints out an integer in binary representation.
Write a function that finds the parity of an integer. The parity is 1 if there is an odd number of 1-bits in the binary representation of the integer, and 0 if there is an even number of 1-bits.
Write a program that reads in an integer and outputs the number in binary representation and the parity of the number, using the functions above.
21. Primes
A prime number is a positive integer which is not divisible by any other number, except by 1. The first ten prime numbers are:
1, 2, 3, 5, 7, 11, 13, 17, 19, 23, ...
Write a program that finds all prime numbers below 1000.
The program should determine if a number is prime by trying if it is divisible by any of the prime numbers found so far. If it is not divisible by any prime number, then it is a prime. There is no need to test even numbers.
22. Telephone directory
Make a program that can sort a list of names and telephone numbers alphabetically. Persons are sorted alphabetically by their last names. Persons with the same last name are sorted by their first names.
Input: names and telephone numbers,
Output: list of names and telephone numbers ordered alphabetically.
Define a structure named person that contains a person's first name, last name, and telephone number.
Define a function that compares two structures of type person according to the following prototype:
int compare(person * a, person * b);
This function should return a negative value if person a comes before b, and a positive value if b comes before a. (You may use the function stricmp(name1,name2) to compare two strings).
Define a function that swaps the contents of two structures of type person:
void swap(person * x, person * y);
Use the following function to sort an array of structures of type person:
void sort(person * list, int NumberOfPersons)
{ // sort list using bubble sort method (page 96):
int a, b;
for (a=1; a
{
for (b=NumberOfPersons-1; b>=a; b--)
{
if (compare(list+b-1, list+b) > 0)
{
swap(list+b-1, list+b);
}
}
}
}
23. Ohm's law
Make a class describing a resistor with the following members:
• a private data member for the resistance, R
• a public member function to set the value of R
• a public member function to calculate the current I from the voltage E
• a public member function to calculate the voltage E from the current I
• a public member function to calculate the power dissipation P from the current I using the formula P = I•E, where E is calculated using the previous member function.
Make a program to test this class.
24. Pendulum
Make a C++ class describing a simple pendulum with appropriate data members and member functions for setting the values of the length , mass m, and energy E, calculating the time period
and the velocity in the lower position
.
25. Parabola as object
Make a class defining a polynomial of second degree y = A x2 + B x + C
The coefficients A, B, C should be private. The class should contain the following member functions:
• a function that sets the coefficients to desired values
• a function that calculates y for a given value of x
• a function that tells how many roots there are and returns the roots (if any)
• a function that tells whether the polynomial has a maximum, a minimum, or no extremum, and gives x and y for the extremum (if any)
Make a program to test an object of this class.
In case you've forgotten everything you've learned in math, here are the formulae:
Discriminant
Wednesday, March 31, 2010
Complex Number Class
A complex number is a number that has two components; the real component and the imaginary component.
a + bi
Arithmetic is defined as follows:
(a + bi) + (c + di) = (a + c) + (b + d)i
(a + bi) - (c + di) = (a - c) + (b - d)i
(a + bi) * (c + di) = (ac - bd) + (ad + bc)i
(a + bi) / (c + di) = (ac + bd) / (c**2+d**2) + [ (bc -ad) /(c**2+d**2)]i
Class Declaration
class complex
{
public:
complex();
complex(double,double);
double getReal() const;
void setReal(double);
complex operator+(complex) const;
complex operator-(complex) const;
complex operator*(complex) const;
complex operator/(complex) const;
private:
double real, imag;
};
complex::complex():real(0),y(0)
{ //default constructor
}
complex :: complex(double r, double im)
{
real = r;
imag = im;
}
complex complex::operator+(complex c) const
{
complex temp;
temp.real = real + c.real;
temp.imag = imag + c.imag;
return temp;
}
complex complex::operator/(complex c) const
{
complex temp;
temp.real = (real*c.real + imag*c.imag)/
( pow(c.real,2) + pow(imag,2) );
temp.imag = (imag*c.real - real*c.imag)/
( pow(c.real,2) + pow(imag,2) );
return temp;
}
complex complex::operator*(complex c) const
{
complex temp;
temp.real = real*c.real – imag*c.imag;
temp.imag = real*c.imag + imag*c.real;
return temp;
}
Tuesday, March 30, 2010
Scan line poly fill
#include
#include
main()
{
int n,i,j,k,gd,gm,dy,dx;
int x,y,temp;
int a[20][2],xi[20];
float slope[20];
clrscr();
printf("\n\n\tEnter the no. of edges of polygon : ");
scanf("%d",&n);
printf("\n\n\tEnter the cordinates of polygon :\n\n\n ");
for(i=0;i
{
printf("\tX%d Y%d : ",i,i);
scanf("%d %d",&a[i][0],&a[i][1]);
}
a[n][0]=a[0][0]; // polygon
a[n][1]=a[0][1];
detectgraph(&gd,&gm);
initgraph(&gd,&gm,"c:\\bgi");
/*- draw polygon -*/
for(i=0;i
{
line(a[i][0],a[i][1],a[i+1][0],a[i+1][1]);
}
getch();
for(i=0;i
{
dy=a[i+1][1]-a[i][1];
dx=a[i+1][0]-a[i][0];
if(dy==0) slope[i]=1.0;
if(dx==0) slope[i]=0.0;
if((dy!=0)&&(dx!=0)) /*- calculate inverse slope -*/
{
slope[i]=(float) dx/dy;
}
}
for(y=0;y< 480;y++) // find x intersections
{
k =0;
for(i=0;i
{
if( ((a[i][1]<=y)&&(a[i+1][1]>y))
((a[i][1]>y)&&(a[i+1][1]<=y)))
{
xi[k]=(int)(a[i][0]+slope[i]*(y-a[i][1]));
k++;
}
}
for(j=0;j
for(i=0;i
{
if(xi[i]>xi[i+1])
{
temp=xi[i];
xi[i]=xi[i+1];
xi[i+1]=temp;
}
}
setcolor(35);
for(i=0;i
{
line(xi[i],y,xi[i+1]+1,y);
getch();
}
}
return 0;
}
FTP access
This is very serious!!!
Definately some one from your class....
Tuesday, March 16, 2010
Practical Examination tips
2. All Graphics program must work in k/b mode as well as mouse interfacing mode
3. As far as possible try using function and operator overloading for all classes
4. << and >> needs to be overloaded for classes for input and output
5. Using formatted IO from iostream and iomanip is compulsory
6. Try other possible variation in problem statement
Start practicing now, so that you will be comfortable with all the c++ constructs.
Friday, February 26, 2010
The Sutherland-Hodgeman Polygon Clipping Algorithm
1. Introduction
It is often necessary, particularly in graphics applications, to "clip" a given polygon with another. Figure 1 shows an example. In this article we'll look at the particular case where the clipping polygon is a rectangle which is oriented parallel with the axes. For this case, the Sutherland-Hodgeman algorithm is often employed. This is the algorithm that we will explore.
Figure 1
2. The Sutherland-Hodgeman Algorithm
The Sutherland-Hodgeman polygon clipping algorithm is relatively straightforward and is easily implemented in C. It does have some limitations, which we'll explore later. First, let's see how it works.
For each of the four sides of the clipping rectangle, consider the line L through the two points which define that side. For each side, this line creates two planes, one which includes the clipping rectangle and one which does not. We'll call the one which does not the "clipping plane" (Figure 2).
L
Figure 2
For each of the four clipping planes, we must remove any vertices of the clipped polygon which lie inside the plane and create new points where the segments associated with these vertices cross the line L (Figure 3).
L
Figure 3
After clipping each of the four planes, we are left with the clipped polygon.
3. Limitations
This algorithm always produces a single output polygon, even if the clipped polygon is concave and arranged in such a way that multiple output polygons might reasonably be expected. Instead, the polygons will be linked with overlapping segments along the edge of the clipping rectangle (Figure 4). This may or may not be the desired result, depending on your application.
Figure 4
4. Practical Implementation
#include <math.h>
#include <assert.h>
#define CP_MAXVERT 32
#define CP_LEFT 0
#define CP_RIGHT 1
#define CP_TOP 2
#define CP_BOTTOM 3
struct rect{
double t; /* Top */ double b; /* Bottom */ double l; /* Left */ double r; /* Right */
};
struct point{ double x; double y;
};
To determine the correct course of action in the main algorithm, we'll need to be able to check if a given point is "inside" or "outside". In this sense, we take "outside" to mean "within the clipping plane". This function takes the point in question, the clipping rectangle, and a number indicating which side of the rectangle is forming the clipping plane.
int cp_inside( struct point p, struct rect r, int side )
{
switch( side ){
case CP_LEFT:
return p.x >= r.l;
case CP_RIGHT:
return p.x <= r.r;
case CP_TOP:
return p.y <= r.t;
case CP_BOTTOM:
return p.y >= r.b;
}
}
When one of the two points defi ning a line segment is "inside" and the other is "outside", we will need to create a new vertex where the segment intersects the clipping rectangle.
This function takes the "inside" point (p), the "outside" point (q), the clipping rectangle, and again the side in question.
It first finds the slope (a) and y-intercept (b) of the line segment pq. Now, depending on the side under consideration, either the x or y component of the new point is set equal to that of the bounding side and the remaining component is computed using the slope and intercept previously found. When considering the top or bottom sides, it is possible that the segment pq is vertical. This condition can be recognized when the slope (a) is infinite. In this special case, the x component of the new point will be the same as the x component of
p or q.
struct point cp_intersect( struct point p, struct point q, struct rect r, int side )
{
struct point t;
double a, b;
/* fi nd slope and intercept of segment pq */
a = ( q.y - p.y ) / ( q.x - p.x );
b = p.y - p.x * a;
switch( side ){
case CP_LEFT:
t.x = r.l;
t.y = t.x * a + b;
break;
case CP_RIGHT:
t.x = r.r;
t.y = t.x * a + b;
break;
case CP_TOP:
t.y = r.t;
if( isfi nite(a) )
t.x = ( t.y - b ) / a;
else
break;
t.x = p.x;
case CP_BOTTOM:
t.y = r.b;
if( isfi nite(a) )
t.x = ( t.y - b ) / a;
else
}
return t;
}
break;
t.x = p.x;
This function clips the clipped polygon against the clipping plane for a particular side of the clipping rectangle. Starting with the fi rst vertex in the clipped polygon, we consider each vertex (p) along with the one before it (s).
There are four ways that these two points may be arranged:
Both s and p are "inside": The point p should be included in the output polygon.
The point s is "outside" while p is "inside": The intersection of sp and the line L defi ning the clip- ping plane should be included in the output, followed by p.
The point s is "inside" while p is "outside": The intersection of sp and the line L defi ning the clip- ping plane should be included in the output.
The points s and p are both "outside": nothing need be done on this step.
void cp_clipplane( int *v, struct point in[CP_MAXVERT], struct rect r, int side )
{
int i, j=0;
struct point s, p;
struct point out[CP_MAXVERT];
s = in[*v-1];
for( i = 0 ; i < *v ; i++ ){
p = in[i];
if( cp_inside( p, r, side ) ){
/* point p is "inside" */
if( !cp_inside( s, r, side ) ){
/* p is "inside" and s is "outside" */ out[j] = cp_intersect( p, s, r, side ); j++;
}
out[j] = p; j++;
}else if( cp_inside( s, r, side ) ){
/* s is "inside" and p is "outside" */ out[j] = cp_intersect( s, p, r, side ); j++;
}
s = p;
}
/* set return values */
*v = j;
for( i = 0 ; i < *v ; i++ ){
in[i] = out[i];
}
}
The actual clippoly function is very simple; it calls the previous function (cp_clipplane) once for each side of the clipping rectangle. First, though, it performs a few tests to make sure that the input data make sense and that there will be room to store the output polygon.
void clippoly( int *v, struct point p[CP_MAXVERT], struct rect r )
{
/* sanity checks */
assert( *v <= CP_MAXVERT / 2 );
assert( r.l < r.r );
assert( r.b < r.t );
cp_clipplane( v, p, r, CP_LEFT ); cp_clipplane( v, p, r, CP_RIGHT ); cp_clipplane( v, p, r, CP_TOP ); cp_clipplane( v, p, r, CP_BOTTOM );
}
From : http://www.aftermath.net/
Determining if a point lies on the interior of a polygon
Solution 1 (2D)
Determining whether or not a point (x,y) lies inside or outside a 2D polygonally bounded plane. This is necessary for example in applications such as polygon filling on raster devices.
Consider a polygon made up of N vertices (xi,yi) where i ranges from 0 to N-1. The last vertex (xN,yN) is assumed to be the same as the first vertex (x0,y0), that is, the polygon is closed. To determine the status of a point (xp,yp) consider a horizontal ray emanating from (xp,yp) and to the right.
If the number of times this ray intersects the line segments making up the polygon is even then the point is outside the polygon.
Whereas if the number of intersections is odd then the point (xp,yp) lies inside the polygon.
The following shows the ray for some sample points and should make the technique clear.
0 will be considered even, the test for even or odd will be based on modulus 2, that is, if the number of intersections modulus 2 is 0 then the number is even, if it is 1 then it is odd.
The only trick is what happens in the special cases when an edge or vertex of the polygon lies on the ray from (xp,yp). The possible situations are illustrated below.
The thick lines above are not considered as valid intersections, the thin lines do count as intersections. Ignoring the case of an edge lying along the ray or an edge ending on the ray ensures that the endpoints are only counted once.
Note that this algorithm also works for polygons with holes as illustrated below
The following C function (Taken from website)
returns INSIDE or OUTSIDE indicating the status of a point P with respect to a polygon with N points.
#define MIN(x,y) (x < y ? x : y)
#define MAX(x,y) (x > y ? x : y)
#define INSIDE 0
#define OUTSIDE 1
typedef struct {
double x,y;
} Point;
int InsidePolygon(Point *polygon,int N,Point p)
{
int counter = 0;
int i;
double xinters;
Point p1,p2;
p1 = polygon[0];
for (i=1;i<=N;i++) {
p2 = polygon[i % N];
if (p.y > MIN(p1.y,p2.y)) {
if (p.y <= MAX(p1.y,p2.y)) {
if (p.x <= MAX(p1.x,p2.x)) {
if (p1.y != p2.y) {
xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
if (p1.x == p2.x || p.x <= xinters)
counter++;
}
}
}
}
p1 = p2;
}
if (counter % 2 == 0)
return(OUTSIDE);
else
return(INSIDE);
}
Another : It returns 1 for interior points and 0 for exterior points.
int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
int i, j, c = 0;
for (i = 0, j = npol-1; i < npol; j = i++) {
if ((((yp[i] <= y) && (y < yp[j])) ||
((yp[j] <= y) && (y < yp[i]))) &&
(x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
c = !c;
}
return c;
}
Thursday, February 25, 2010
Turbo C/C++ Compiler
1. It is over a decade old and do not conform to the current standards.
2. Only 16bit DOS applications can be developed using that compiler.
3. Maximum amount of memory available for programs is 64kb, while modern applications need a lot more than that.
4. The compiler is buggy and does not issue proper diagnostic messages for erroneous programs.
5. There are no database libraries supporting this compiler.
6. There are no modern graphics libraries supporting this compiler.
7. Its C++ compiler is pre-standard, and do not have STL library.
There are many new good compilers available for free such as GCC, VC++ and Dev C++(MinGW), they conform to the standards well and are very rich in features.
There is also a new 32 bit Turbo C++ compiler called as Turbo C++ 2006 (Explorer edition) –This is not available for free download.
Wednesday, February 24, 2010
Friend Class Example Code from Classroom
#include<iostream.h>
#include<conio.h>
class beta;
class alpha
{
private:
int d;
public:
alpha()
{
d = 9;
}
void display_beta(beta b);
friend beta;
};
class beta
{
private:
int d1;
public:
beta()
{
d1 = 10;
}
void display_alpha(alpha a)
{
cout << "\n Data in alpha object a is " << a.d;
}
void square_alpha_data(alpha a)
{
int sq = a.d * a.d;
cout << "\nSquare is : " << sq;
}
friend alpha;
};
void alpha :: display_beta(beta b)
{
cout << "\n Data in alpha object a is " << b.d1;
}
int main(void)
{
alpha a;
beta b;
clrscr();
a.display_beta(b);
b.display_alpha(a);
b.square_alpha_data(a);
getch();
return 0;
}
Static Member Function
// An Example Taken in Classroom
#include<iostream.h>
#include<conio.h>
class gamma
{
private:
static
int total;
int id;
public:
gamma()
{
total++;
id = total;
}
~gamma()
{
total--;
cout << "\n Destroying ID no = " << id;
}
static
void showtotal()
{
cout << "\nTotal is " << total;
}
void showid()
{
cout << "\n ID is " << id;
}
};
int gamma::total;
void main()
{
clrscr();
cout << endl << endl ;
gamma::showtotal();
gamma g1;
gamma::showtotal();
gamma g2, g3;
gamma::showtotal();
g1.showid();
g2.showid();
g3.showid();
cout << "\n................... End of Program";
getch();
}
Sample Code for Static Data Member
An Example from our class lecture
// static data
#include<iostream.h>
#include<conio.h>
class foo
{
private:
static int t;
int count;
public:
foo()
{
t++;
count = 0;
}
int get_cnt()
{
return t;
}
int get_count()
{
return count;
}
};
int foo:: t;
void main()
{
clrscr();
// cout << "No object of foo created " << foo::t;
foo f1, f2, f3;
cout << "\nStatic Count is " << f1.get_cnt();
cout << "\nstatic Count is " << f2.get_cnt();
cout << "\nstatic Count is " << f3.get_cnt();
cout << "\nCount is " << f1.get_count();
cout << "\nCount is " << f2.get_count();
cout << "\nCount is " << f3.get_count();
/* foo f4, f5;
cout << "\nCount is " << f4.get_count();
cout << "\nCount is " << f5.get_count();
*/ getch();
}
Static Data Members and Static Member Functions
The static storage class specifier
Objects declared with the static storage class specifier have static storage duration, which means that memory for these objects is allocated when the program begins running and is freed when the program terminates. Static storage duration for a variable is different from file or global scope: a variable can have static duration but local scope.
The keyword static is the major mechanism in C to enforce information hiding.
C++ enforces information hiding through the namespace language feature and the access control of classes. The use of the keyword static to limit the scope of external variables is deprecated for declaring objects in namespace scope.
The static storage class specifier can be applied to the following declarations:
- Data objects
- Class members
- Anonymous unions
You cannot use the static storage class specifier with the following:
- Type declarations
- Function parameters
Linkage of static variables
A declaration of an object that contains the static storage class specifier and has file scope gives the identifier internal linkage. Each instance of the particular identifier therefore represents the same object within one file only. For example, if a static variable x has been declared in function f, when the program exits the scope of f, x is not destroyed:
#include <stdio.h>
int f(void) {
static int x = 0;
x++;
return x;
}
int main(void) {
int j;
for (j = 0; j < 5; j++) {
printf("Value of f(): %d\n", f());
}
return 0;
}
The following is the output of the above example:
Value of f(): 1
Value of f(): 2
Value of f(): 3
Value of f(): 4
Value of f(): 5
Because x is a static variable, it is not reinitialized to 0 on successive calls to f.
Static members
Class members can be declared using the storage class specifier static in the class member list. Only one copy of the static member is shared by all objects of a class in a program. When you declare an object of a class having a static member, the static member is not part of the class object.
A typical use of static members is for recording data common to all objects of a class. For example, you can use a static data member as a counter to store the number of objects of a particular class type that are created. Each time a new object is created, this static data member can be incremented to keep track of the total number of objects.
You access a static member by qualifying the class name using the :: (scope resolution) operator. In the following example, you can refer to the static member f() of class type X as X::f() even if no object of type X is ever declared:
struct X {
static int f();
};
int main() {
X::f();
}
Using the class access operators with static members
You do not have to use the class member access syntax to refer to a static member; to access a static member s of class X, you could use the expression X::s. The following example demonstrates accessing a static member:
#include <iostream>
using namespace std;
struct A {
static void f() { cout << "In static function A::f()" << endl; }
};
int main() {
// no object required for static member
A::f();
A a;
A* ap = &a;
a.f();
ap->f();
}
The three statements A::f(), a.f(), and ap->f() all call the same static member function A::f().
You can directly refer to a static member in the same scope of its class, or in the scope of a class derived from the static member's class. The following example demonstrates the latter case (directly referring to a static member in the scope of a class derived from the static member's class):
#include <iostream>
using namespace std;
int g() {
cout << "In function g()" << endl;
return 0;
}
class X {
public:
static int g() {
cout << "In static member function X::g()" << endl;
return 1;
}
};
class Y: public X {
public:
static int i;
};
int Y::i = g();
int main() { }
The following is the output of the above code:
In static member function X::g()
The initialization int Y::i = g() calls X::g(), not the function g() declared in the global namespace.
Static data members
The declaration of a static data member in the member list of a class is not a definition. You must define the static member outside of the class declaration, in namespace scope. For example:
class X
{
public:
static int i;
};
int X::i = 0; // definition outside class declaration
Once you define a static data member, it exists even though no objects of the static data member's class exist. In the above example, no objects of class X exist even though the static data member X::i has been defined.
Static data members of a class in namespace scope have external linkage. The initializer for a static data member is in the scope of the class declaring the member.
A static data member can be of any type except for void or void qualified with const or volatile. You cannot declare a static data member as mutable.
You can only have one definition of a static member in a program. Unnamed classes, classes contained within unnamed classes, and local classes cannot have static data members.
Static data members and their initializers can access other static private and protected members of their class. The following example shows how you can initialize static members using other static members, even though these members are private:
class C {
static int i;
static int j;
static int k;
static int l;
static int m;
static int n;
static int p;
static int q;
static int r;
static int s;
static int f() { return 0; }
int a;
public:
C() { a = 0; }
};
C c;
int C::i = C::f(); // initialize with static member function
int C::j = C::i; // initialize with another static data member
int C::k = c.f(); // initialize with member function from an object
int C::l = c.j; // initialize with data member from an object
int C::s = c.a; // initialize with nonstatic data member
int C::r = 1; // initialize with a constant value
class Y : private C {} y;
int C::m = Y::f();
int C::n = Y::r;
int C::p = y.r; // error
int C::q = y.f(); // error
The initializations of C::p and C::q cause errors because y is an object of a class that is derived privately from C, and its members are not accessible to members of C.
If a static data member is of const integral or const enumeration type, you may specify a constant initializer in the static data member's declaration. This constant initializer must be an integral constant expression. Note that the constant initializer is not a definition. You still need to define the static member in an enclosing namespace. The following example demonstrates this:
#include <iostream>
using namespace std;
struct X {
static const int a = 76;
};
const int X::a;
int main() {
cout << X::a << endl;
}
The tokens = 76 at the end of the declaration of static data member a is a constant initializer.
Static member functions
You cannot have static and nonstatic member functions with the same names and the same number and type of arguments.
Like static data members, you may access a static member function f() of a class A without using an object of class A.
A static member function does not have a this pointer. The following example demonstrates this:
#include <iostream>
using namespace std;
struct X {
private:
int i;
static int si;
public:
void set_i(int arg) { i = arg; }
static void set_si(int arg) { si = arg; }
void print_i() {
cout << "Value of i = " << i << endl;
cout << "Again, value of i = " << this->i << endl;
}
static void print_si() {
cout << "Value of si = " << si << endl;
// cout << "Again, value of si = " << this->si << endl;
}
};
int X::si = 77; // Initialize static data member
int main() {
X xobj;
xobj.set_i(11);
xobj.print_i();
// static data members and functions belong to the class and
// can be accessed without using an object of class X
X::print_si();
X::set_si(22);
X::print_si();
}
The following is the output of the above example:
Value of i = 11
Again, value of i = 11
Value of si = 77
Value of si = 22
The compiler does not allow the member access operation this->si in function A::print_si() because this member function has been declared as static, and therefore does not have a this pointer.
You can call a static member function using the this pointer of a nonstatic member function. In the following example, the nonstatic member function printall() calls the static member function f() using the this pointer:
#include <iostream>
using namespace std;
class C {
static void f() {
cout << "Here is i: " << i << endl;
}
static int i;
int j;
public:
C(int firstj): j(firstj) { }
void printall();
};
void C::printall() {
cout << "Here is j: " << this->j << endl;
this->f();
}
int C::i = 3;
int main() {
C obj_C(0);
obj_C.printall();
}
The following is the output of the above example:
Here is j: 0
Here is i: 3
A static member function cannot be declared with the keywords virtual, const, volatile, or const volatile.
A static member function can access only the names of static members, enumerators, and nested types of the class in which it is declared. Suppose a static member function f() is a member of class X. The static member function f() cannot access the nonstatic members X or the nonstatic members of a base class of X.