ISE LAB PROGRAMS : November 2012

Sunday, 25 November 2012

FS PROGRAM HASHING

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
using namespace std;
class student
{
public:
    string USN;
    string Name;
    string Branch;
    int Semester;
     string buffer;

    void read_data();
    void pack();
    void write_to_file();
    void unpack(int);
    void search(string);
    int hash(string);

};

int student::hash(string key)
{
    int t;
    t = (((key[7]-48) *100) + ((key[8]-48)*10) + (key[9]-48)) % 9;
    if (t==0) return 9;
    else return t;
}

void student::read_data()
{
    cout<<"\nUsn:";
    cin>>USN;
    cout<<"\nName:";
    cin>>Name;
    cout<<"\nBranch:";
    cin>>Branch;
    cout<<"\nSemster:";
    cin>>Semester;
}
void student::pack()
{
    string sem,temp;
    stringstream out;
    out << Semester;
    sem = out.str();
    buffer.erase();
    temp.erase();
    temp+=USN+'|'+Name+'|'+Branch+'|'+sem;
    for(;temp.size()<100;) temp+='$';
    buffer=temp+'\n';

}

void student::write_to_file()
{
    fstream file;
    string temp;
    int count, pos;

    pos=hash(USN);
    pos--;
    pos=pos*304;

    file.open("1.txt");
    file.seekp(pos,ios::beg);
    getline(file,temp);
    file.close();

    count=temp[0]-48;

    file.open("1.txt");

    if (count<0)
    {
        file.seekp(pos,ios::beg);
        file.put('1');
        pos=pos+1;
    }
    else if (count==1)
    {
        file.seekp(pos,ios::beg);
        file.put('2');
        pos=pos+102;
    }
    else if (count==2)
    {

        file.seekp(pos,ios::beg);
        file.put('3');
        pos=pos+203;
    }
    cout<<"\nInserting at:"<<pos;
    file.seekp(pos,ios::beg);
    file<<buffer;
    file.close();

    if (count==3) cout<<"\n\nCannot Insert....Overflow";


}

void student::unpack(int flag)
{

    string sem;
    int ch=1,i=0;
    USN.erase();

    if (flag==1) i++;       //skip the count value

    while (buffer[i]!='|')
    USN+=buffer[i++];

    Name.erase();
    i++;
    while (buffer[i]!='|')
    Name+=buffer[i++];

    Branch.erase();
    i++;
    while (buffer[i]!='|')
    Branch+=buffer[i++];

    sem.erase();
    i++;
    while (buffer[i]!='$')
    sem+=buffer[i++];
    istringstream out(sem);
    out>>Semester;

}

void student::search(string key)
{
    fstream file;
    int flag=0, pos=0, count,i=1;
    string temp;

    pos=hash(key);
    pos--;
    pos=pos*304;

    file.open("1.txt");
    file.seekp(pos,ios::beg);
    getline(file,temp);

    count=temp[0]-48;

    file.seekp(pos,ios::beg);

    while (i<=count)
    {
        buffer.erase();
        getline(file,buffer);
        unpack(i++);
        if (key==USN) flag=1;
    }

    if (!flag) cout<<"\n\nKey not found:";
    else {
        cout<<"\nThe Record details are-\n";
        cout<<"\nUSN:"<<USN<<"\nName:"<<Name<<"\nBranch:"<<Branch<<"\nSemester:"<<Semester;
         }
    file.close();
}


int main()
{
    int choice;
    student s1;
    string key;
    while (1){
    cout <<"\n\nMain Menu\n 1.Add \n\n 2.Search \n\n 3.Exit\n\nEnter the choice:";
    cin>>choice;
    switch (choice)
    {
        case 1: cout<<"Data\n";
            s1.read_data();
            s1.pack();
            s1.write_to_file();
            break;

        case 2: cout <<"\n\nEnter the key";
            cin>>key;
            s1.search(key);
            break;

        case 3: return 0;

        default: cout<<"\n\nWrong Choice";
    }}

}

B+ trees FS

#include <iostream>
#include <cmath>

using namespace std;

struct node
{
    int ele[4];
    int child[4];
    node *next;
};

class bptree
{
public:
    node *tree[10][10];
    int count[10];
    int leaf;
    int path[10];
    node *head;

    bptree();
    node* create_node();
    void insert(int);
    void main_search(int);
    void display_tree();
    void insert_node(node*,int);
    void search(int);
    int search_node (node*,int);
    int nodefull(node*);
    void split(node*);
    void display_seqset();
};

bptree::bptree()
{
    leaf=-1;
    for (int i=0;i<10;i++)
    {count[i]=-1;path[i]=-1;}
}

node* bptree::create_node()
{
node *n;
n = new node;
for (int i=0;i<4;i++) {n->ele[i]=-1;n->child[i]=-1;}
n->next=NULL;
return n;
}

void bptree::insert(int key)
{
    int n, parent;
    node *first_node;
    if (leaf==-1)
    {
        first_node=create_node();
        tree[0][0]=first_node;
        leaf++;count[0]++;
        first_node->ele[0]=key;
        head=first_node;        //header node of seq set
    }
    else if (leaf==0)
    {
        if (nodefull(tree[0][0])) {path[leaf]=0;split(tree[0][0]);insert(key);}
        else insert_node(tree[0][0],key);
    }
    else{
        search(key);
        n=path[leaf];
        parent=path[leaf-1];

        if ( (nodefull(tree[leaf][n])) )
        {
            split(tree[leaf][n]);
            insert(key);
        }
        else
            insert_node(tree[leaf][n],key);
       }
}

void bptree::main_search(int key)
{
    int flag=0, i;
    node *node1;
    search(key);
    node1=tree[leaf][path[leaf]];

    for (i=0;node1->ele[i]!=-1;i++)
        if (node1->ele[i]==key) {flag=1; break;}

    cout<<"\nThe path traversed is: ";
    for (i=0;path[i]!=-1;i++)
        cout<<path[i]<<" -> ";

    if (flag) cout <<"\nElement Found";
    else cout<<"\nNot Found";
}

void bptree::display_tree()
{
    int i,j,k;
    for (i=0;i<=leaf;i++)
    {
        cout<<"\n\nLevel------ " <<i<<"\n";
        for (j=0;j<=count[i];j++)
        {
            if (i!=leaf) k=1; else k=0;        //print first element only at leaf level
            for (;tree[i][j]->ele[k]!=-1;k++)
                cout<<" "<<tree[i][j]->ele[k];
            cout<<"\t";
        }
    }
}

void bptree::search(int key)
{
    int i,j,temp;
    path[0]=0;                //always start the path from root
    if (leaf){                // search only if there are more than 1 level
        j=0;
        for (i=0;i<leaf;i++)
        {
            temp=search_node(tree[i][j],key);
             path[i+1]=temp;
            j=temp;
        }}
}

int bptree::search_node(node *node1, int key)
{
    if (key<=node1->ele[0]) return node1->child[0];
    for (int i=1;i<4;i++)
    {

        if ((key >= node1->ele[i]) && (key < node1->ele[i+1])) return node1->child[i];
        else if (node1->ele[i+1]==-1) return node1->child[i];
    }
}

int bptree::nodefull(node *node1)
{
    if (node1->ele[3]!=-1) return 1;
    else return 0;
}

void bptree::insert_node(node *node1, int key)
{
    int flag=0, count=-1,i,j, x, y, l;
    node *newnode, *parent;
    for (i=0;i<4;i++) if (node1->ele[i]!=-1) ++count;
    i=0;
    while (!flag && node1->ele[i]!=-1)
    {
        if (node1->ele[i] > key)            //not considering duplicate entries
        {
            flag=1;
            for (int j=count;j>=i;j--)
               node1->ele[j+1]=node1->ele[j];
               node1->ele[i]=key;
        }
        i++;
    }
    if (!flag)     node1->ele[count+1]=key;            //highest element added at end

    if (node1->ele[0]==key)                        //new element is the lowest, hence propogate this till root
    {

        for (i=leaf-1;i>=0;i--)
        {
            x=path[i+1];
            if (tree[i][path[i]]->ele[x] > key) tree[i][path[i]]->ele[x]=key;
            else insert_node(tree[i][x],key);
    }    }

    for (i=0;i<=count+1;i++)
        cout<<"\t\t"<<node1->ele[i];
}


void bptree::split(node *oldnode)
{
    node *newnode, *parent, *n1, *n2;
    int i,j,k,n,t,x,y,pos;
    newnode = create_node();

    newnode->ele[0]=oldnode->ele[2];        //copy elements to new node
    newnode->ele[1]=oldnode->ele[3];


    oldnode->ele[2]=-1;                //delete entries in old node
    oldnode->ele[3]=-1;


    t=count[leaf];
    n=path[leaf];
    for (i=t,j=t+1;i>n;i--,j--)            //move the elements in leaf level one place right
        tree[leaf][j]=tree[leaf][i];

    newnode->next=tree[leaf][n]->next;        //updating the next pointers
    tree[leaf][n]->next=newnode;


    tree[leaf][n+1] = newnode;            //insert new node to the tree
    count[leaf]++;


    x=leaf;

    if (count[leaf]+1==1) t=1; else t=log(count[leaf]+1)/log(2);    //how many levels does the tree need?

    if (t!=leaf)                        //increase the level of the tree
    {
        ++leaf;
        count[leaf]=count[x];

        for (i=0;i<=count[leaf];i++)            //copy the leaf nodes to the new level
            std::swap(tree[leaf][i],tree[x][i]);
    }

    for (i=leaf-1;i>=0;i--) count[i]=-1;        //make the tree empty

    for (i=t,j=i-1;i>0;i--,j--)
    {
        for (k=0;k<=count[i]/3;k++)
        {
            n1=tree[i][2*k];
            n2=tree[i][(2*k)+1];

            //for (x=0;n1->ele[x]!=-1;x++);    //find last element in the nodes
            //for (y=0;n2->ele[y]!=-1;y++);

            newnode=create_node();
            count[j]++;
            tree[j][count[j]]=newnode;

            newnode->ele[0]=n1->ele[0];
            newnode->child[0]=2*k;
            newnode->ele[1]=n2->ele[0];
            newnode->child[1]=(2*k)+1;
        }


        if (count[i]!=1 && count[i]%2==0)            //one node is remaining
        {
            n2=tree[i][count[i]];
            //for (y=0;n2->ele[y]!=-1;y++);
            newnode->ele[2]=n2->ele[0];
            newnode->child[2]=count[i];
        }
    }
}

void bptree::display_seqset()
{
    node *t;
    int k;
    t=head;
    cout<<"\n\nThe sequence set is:";
    while (t)
    {
        for (k=0;t->ele[k]!=-1;k++)
            cout<<" "<<t->ele[k];
        cout<<"\t";
        t=t->next;
    }
}

int main()
{
    bptree bt;
    int choice, key;

    while(1)
    {
        cout<<"\n\n\nMain Menu\n-------------------\n1.Insert\n2.Search\n3.Display Tree\n4.Display Sequence Set\n5.Exit\n\nEnter your choice:";
        cin>>choice;
        switch(choice)
        {
        case 1:    cout<<"\nEnter the element:";
            cin>>key;
            bt.insert(key);
            break;
        case 2:cout<<"Enter the key:";
            cin>>key;
            bt.main_search(key);
            break;
        case 3: bt.display_tree();
            break;
        case 4: bt.display_seqset();
            break;
        case 5: return 0;
        default: cout<<"\nEnter valid choice";
        }
    }
}

Saturday, 24 November 2012

FS PROGRAM FOR RE USE DELETED SPACE IN INDEXING

void student::pack()
{
string sem;
stringstream out;
out << Semester;
sem = out.str();
buffer.erase();
buffer+=USN+'|'+Name+'|'+Branch+'|'+sem;
for(;buffer.size()<100;) buffer+='$';
buffer+='\n';

}

void student::write_to_file()
{
fstream file;
int pos;
file.open("1.txt");
pos = avail[top];
if (pos){
file.seekp(pos,ios::beg);
file<<buffer;
top--;
cout<<"\n\nReusing Deleted Space at position:"<<pos;
}
else file<<buffer;
file.close();
}

void student::unpack()
{

string sem;
int ch=1,i=0;
USN.erase();
while (buffer[i]!='|')
USN+=buffer[i++];

Name.erase();
i++;
while (buffer[i]!='|')
Name+=buffer[i++];

Branch.erase();
i++;
while (buffer[i]!='|')
Branch+=buffer[i++];

sem.erase();
i++;
while (buffer[i]!='$')
sem+=buffer[i++];
istringstream out(sem);
out>>Semester;

}

int student::search(string key)
{
ifstream file;
int flag=0, pos=0;
file.open("1.txt",ios::in);
while (!file.eof())
{
buffer.erase();
getline(file,buffer);
unpack();
if (key==USN) {

cout<<"\nFound the key. The record is "<<buffer;pos=file.tellg(); flag=1;return pos;}
     }
file.close();
if (!flag) {cout<<"\n Not Found \n\n"; return pos;}

}

int student::delete_from_file(string key)
{
fstream file;
char del_mark='*',t;
int pos,flag=0;
pos=search(key);
if (pos){
file.open("1.txt");
pos-=101; //skip the $$$$$$ and \n characters
file.seekp(pos,ios::beg);
file.put(del_mark);
flag=1;
avail[++top]=pos;
cout<<"\n\nThe position of deleted record is:"<<pos;

}

file.close();
buffer.empty();
if (!flag) return 0;
else return 1;

}

void student::modify(string key)
{
int choice;
if (delete_from_file(key)){
cout<<"\n What to modify?";
cin>>choice;
switch(choice)
{
case 1: cout<<"\nUSN:"; cin>>USN; break;
case 2:   cout<<"\nName:";cin>>Name;break;
case 3:   cout<<"\nBranch:";cin>>Branch;break;
case 4:   cout<<"\nSemster:";cin>>Semester;break;
default: cout <<"Wrong Choice";
}
buffer.erase();
pack();
write_to_file();
}
}

int main()
{
int count,choice,len,i;
student s1;
s1.initialize();
string key;
while(1){
cout <<"\nMain Menu\n 1.Add \n\n 2.Delete \n\n 3.Modify \n\n 4.Search \n\n 5.Exit\n\nEnter the choice:";
cin>>choice;
switch (choice)
{
case 1: cout<<"Data\n";
s1.read_data();
s1.pack();
s1.write_to_file();
break;
case 2: cout <<"\n\nEnter the key";
cin>>key;
i=s1.delete_from_file(key);
break;
case 3: cout <<"\n\nEnter the key";
cin>>key;
s1.modify(key);
break;
case 4: cout <<"\n\nEnter the key";
cin>>key;
i=s1.search(key);
break;
case 5: return 0;
default: cout<<"\n\nWrong Choice";
}

}
}

Wednesday, 21 November 2012

OS MVT PROGRAM

#include<stdio.h>
#include<stdlib.h>
void main()
{
int m=0,m1=0,m2=0,p,count=0,i;
printf("\n enter the memory capacity:");
scanf("%d",&m);
printf("\n enter the no of processes:");
scanf("%d",&p);
for(i=0;i<p;i++)
{
printf("\n Enter memory required for process%d: ",i+1);
scanf("%d",&m1);
count=count+m1;
if(m1<=m)
{
if(count==m)
printf("\n there is no further memory remaining:");
printf(" \n the memory allocated for process%d is: %d \n ",i+1,m);
m2=m-m1;
printf("\n remaining memory is: %d",m2);
m=m2;
}
else
{
printf("\n memory is not allocated for process%d",i+1);
}
printf("\n external fragmentation for this process is:%d \n",m2);
}
}

Tuesday, 20 November 2012

IP PHP PROGRAM TO CREATE A RANDOM GREETING

Monday, 19 November 2012

OS BANKERS ALGORITHM PROGRAM

#include<stdio.h>
#include<string.h>
void main()
{
int max[10][10],need[10][10],alloc[10][10],finish[10]={0},avail[10],work[10];
int i,j,count=0,t,p,r;
printf("Enter the no of processes:\n");
scanf("%d",&p);
printf("Enter the no of resources:\n");
scanf("%d",&r);
printf("Enter the max for each process:");
for(i=0;i<p;i++)
{
printf("\nFor process %d",i);
for(j=0;j<r;j++)
{
scanf("%d",&max[i][j]);
}
}
printf("Enter the allocation for each process:\n");
for(i=0;i<p;i++)
{
printf("\nFor process %d",i);
for(j=0;j<r;j++)
{
scanf("%d",&alloc[i][j]);
}
}
printf("Enter availability of each resource:");
for(j=0;j<r;j++)
scanf("%d",&avail[j]);
do{
for(j=0;j<r;j++)
work[j]=avail[j];

for(i=0;i<p;i++)
{
for(j=0;j<r;j++)
{
need[i][j]=max[i][j]-alloc[i][j];

}
}
count=0;
while(count<8)
{

for(i=0;i<p;i++)
{

for(j=0;j<r;j++)
{

if(finish[i]==0 && need[i][j]<=work[j])
;
else
break;
}
if(j>=r)
{

for(t=0;t<r;t++)
{
work[t]+=max[i][t];
}
finish[i]=1;
printf("\t%d",i);
}
}
count++;
}
for(i=0;i<p;i++)
if(finish[i]!=1)
break;
if(i==p)
printf("\nsystem is in safe state");
else
printf("\nunsafe state");
for(i=0;i<p;i++)
finish[i]=0;
printf("\nAre there any extra resource requests?.....");
scanf("%d",&i);
if(i)
{
printf("\nBy which process...");
scanf("%d",&t);
printf("\nEnter request...");
for(j=0;j<r;j++)
{
scanf("%d",&i);
alloc[t][j]+=i;
avail[j]-=i;
}
}
else
break;
}while(1);
}

OS PRODUCER CONSUMER PROBLEM USING SEMAPHORES

#include<stdio.h>

#define BUFFER_SIZE 3

int buffer[BUFFER_SIZE],item;

int fillCount = 0; // items produced

int emptyCount = BUFFER_SIZE; // remaining space

producer() {

while (1) {

item = produceItem();

if(item==0)

return;

if(emptyCount==0)

{printf("\nbuffer full");

break;

}

emptyCount--;

buffer[emptyCount]=item;

printf("\n %d put into the buffer..",item);

fillCount++;

}

consumer() {

while (1) {

if(fillCount==0)

{printf("\nbuffer empty");

break;

}

fillCount--;

item=buffer[emptyCount];

printf("\n %d removed from buffer..",item);

emptyCount++;

printf("\n %d consumed..",item);

}

int produceItem()

{

int n;

printf("\n Enter the number for production (0 to stop)..\n");

scanf("%d",&n);

return n;

}

int main()

{

char i;

while(i!='y' && i!='Y')

{

producer();

consumer();

printf("\nDo you want to exit...(Y or N)....");

scanf("%c",&i);

}

return 1;

}

OS SJF AND FCFS SCHEDULING PROGRAMS

#include<stdio.h>

int main()

{

int p[10],bt[10],wt[10],n,key,tmp,i,j;

floatawt=0.0,awt2=0.0;

printf("Enter the no. of processes: ");

scanf("%d",&n);

printf("Enter the burst times\n");

for(i=0;i<n;i++)

{

p[i]= i+1;

scanf("%d",&bt[i]);

}

wt[0]=0,tmp=0;

for(i=0;i<n;i++)

{

awt += tmp;

tmp += bt[i];

wt[i+1]= tmp;

printf("\nWaiting time of process %d is %d \n turn around time= %d ",i,wt[i],wt[i+1]);

}

awt/=n;

printf("Average waiting time for FCFS = %.3f\n",awt);

tmp=0;

for(i=1;i<n;i++)

{key=bt[i];

tmp=p[i];

for(j=i-1;j>=0 &&bt[j]>key ; j--)

{

bt[j+1]=bt[j];

p[j+1]=p[j];

}

bt[j+1]=key;

p[j+1]=tmp;

}

tmp=0,wt[0]=0;

for(i=0;i<n;i++)

{

awt2 += tmp;

tmp += bt[i];

wt[i+1]= tmp;

printf("\nWaiting time of process %d is %d \n turn around time= %d ",i,wt[i],wt[i+1]);

}

awt2 /= n;

printf("Average waiting time for SJF= %.3f\n",awt2);

if(awt<awt2)

printf("For the given processes, FCFS is better than SJF since %f<%f", awt,awt2);

else

printf("For the given processes, SJF is better than FCFS since %f>%f", awt,awt2);

return 0;

}

FS BTREES

#include <iostream>
#include <cmath>

using namespace std;

struct node
{
int ele[4];
int child[4];
};

class btree
{
public:
node *tree[10][10];
int count[10];
int leaf;
int path[10];

btree();
node* create_node();
void insert(int);
void main_search(int);
void display_tree();
void insert_node(node*,int);
void search(int);
int search_node (node*,int);
int nodefull(node*);
void split(node*);
};

btree::btree()
{
leaf=-1;
for (int i=0;i<10;i++)
{count[i]=-1;path[i]=-1;}
}

node* btree::create_node()
{
node *n;
n = new node;
for (int i=0;i<4;i++) {n->ele[i]=-1;n->child[i]=-1;}
return n;
}

void btree::insert(int key)
{
int n, parent;
node *first_node;
if (leaf==-1)
{
first_node=create_node();
tree[0][0]=first_node;
leaf++;count[0]++;
first_node->ele[0]=key;
}
else if (leaf==0)
{
if (nodefull(tree[0][0])) {path[leaf]=0;split(tree[0][0]);insert(key);}
else insert_node(tree[0][0],key);
}
else{
search(key);
n=path[leaf];
parent=path[leaf-1];

if ( (nodefull(tree[leaf][n])) )
{
split(tree[leaf][n]);
insert(key);
}
else
insert_node(tree[leaf][n],key);
}
}

void btree::main_search(int key)
{
int flag=0, i;
node *node1;
search(key);
node1=tree[leaf][path[leaf]];

for (i=0;node1->ele[i]!=-1;i++)
if (node1->ele[i]==key) {flag=1; break;}

cout<<"\nThe path traversed is: ";
for (i=0;path[i]!=-1;i++)
cout<<path[i]<<" -> ";

if (flag) cout <<"\nElement Found";
else cout<<"\nNot Found";
}

void btree::display_tree()
{
int i,j,k;
for (i=0;i<=leaf;i++)
{
cout<<"\n\nLevel------ " <<i<<"\n";
for (j=0;j<=count[i];j++)
{
for (k=0;tree[i][j]->ele[k]!=-1;k++)
cout<<" "<<tree[i][j]->ele[k];
cout<<"\t";
}
}
}

void btree::search(int key)
{
int i,j,temp;
path[0]=0;                //always start the path from root
if (leaf){                // search only if there are more than 1 level
j=0;
for (i=0;i<leaf;i++)
{
temp=search_node(tree[i][j],key);
path[i+1]=temp;
j=temp;
}}
}

int btree::search_node(node *node1, int key)
{
for (int i=0;i<4;i++)
{
if (key<=node1->ele[i]) return node1->child[i];
else if (node1->ele[i+1]==-1) return node1->child[i];
}
}

int btree::nodefull(node *node1)
{
if (node1->ele[3]!=-1) return 1;
else return 0;
}

void btree::insert_node(node *node1, int key)
{
int flag=0, count=-1,i,j, x, y, l,t;
node *newnode, *n1;
for (i=0;i<4;i++) if (node1->ele[i]!=-1) ++count;
i=0;
while (!flag && node1->ele[i]!=-1)
{
if (node1->ele[i] > key)            //not considering duplicate entries
{
flag=1;
for (int j=count;j>=i;j--)
node1->ele[j+1]=node1->ele[j];
node1->ele[i]=key;
}
i++;
}
if (!flag)                        //highest element added at end
{
node1->ele[count+1]=key;
for (i=leaf-1;i>=0;i--)
{
n1=tree[i][path[i]];
for (t=0;n1->ele[t]!=-1;t++);
n1->ele[t-1]=key;
}    }

for (i=0;i<=count+1;i++)
cout<<"\t\t"<<node1->ele[i];
}

void btree::split(node *oldnode)
{
node *newnode, *parent, *n1, *n2;
int i,j,k,n,t,x,y,pos;
newnode = create_node();

newnode->ele[0]=oldnode->ele[2];        //copy elements to new node
newnode->ele[1]=oldnode->ele[3];

oldnode->ele[2]=-1;                //delete entries in old node
oldnode->ele[3]=-1;

t=count[leaf];
n=path[leaf];
for (i=t,j=t+1;i>n;i--,j--)            //move the elements in leaf level one place right
tree[leaf][j]=tree[leaf][i];

tree[leaf][n+1] = newnode;            //insert new node to the tree
count[leaf]++;

x=leaf;

if (count[leaf]+1==1) t=1; else t=log(count[leaf]+1)/log(2);    //how many levels does the tree need?

if (t!=leaf)                        //increase the level of the tree
{
++leaf;
count[leaf]=count[x];

for (i=0;i<=count[leaf];i++)            //copy the leaf nodes to the new level
std::swap(tree[leaf][i],tree[x][i]);
}

for (i=leaf-1;i>=0;i--) count[i]=-1;        //make the tree empty

for (i=t,j=i-1;i>0;i--,j--)
{
for (k=0;k<(count[i]+1)/2;k++)
{
n1=tree[i][2*k];
n2=tree[i][(2*k)+1];

for (x=0;n1->ele[x]!=-1;x++);    //find last element in the nodes
for (y=0;n2->ele[y]!=-1;y++);

newnode=create_node();
count[j]++;
tree[j][count[j]]=newnode;

newnode->ele[0]=n1->ele[x-1];
newnode->child[0]=2*k;
newnode->ele[1]=n2->ele[y-1];
newnode->child[1]=(2*k)+1;
}

if (count[i]!=1 && count[i]%2==0)            //one node is remaining
{
n2=tree[i][count[i]];
for (y=0;n2->ele[y]!=-1;y++);
newnode->ele[2]=n2->ele[y-1];
newnode->child[2]=count[i];
}
}
}

int main()
{
btree bt;
int choice, key;

while(1)
{
cout<<"\n\n\nMain Menu\n-------------------\n1.Insert\n2.Search\n3.Display Tree\n4.Exit\n\nEnter your choice:";
cin>>choice;
switch(choice)
{
case 1:    cout<<"\nEnter the element:";
    cin>>key;
    bt.insert(key);
    break;
case 2:cout<<"Enter the key:";
    cin>>key;
    bt.main_search(key);
    break;
case 3: bt.display_tree();
    break;
case 4: return 0;
default: cout<<"\nEnter valid choice";
}
}
}

Fs cosequential processing

#include <iostream>
#include <fstream>
#include <string>
using namespace std;
class coseq
{
public:
string list1[100], list2[100];
int count1, count2;

void load_list();
void sort_list();
void match();
};

void coseq::load_list()
{
fstream file;
string name;
count1=-1;count2=-1;
file.open("name1.txt");
while (!file.eof()){
name.erase();
getline(file,name);
list1[++count1]=name;
}
file.close();
file.open("name2.txt");
while (!file.eof()){
name.erase();
getline(file,name);
list2[++count2]=name;
}
file.close();
}

void coseq::sort_list()
{
int i,j;
string temp;
for (i=0;i<=count1;i++)
{
for (j=i+1;j<=count1;j++)
{
if (list1[i]>list1[j])
{
temp=list1[i];
list1[i]=list1[j];
list1[j]=temp;
}}}

for (i=0;i<=count2;i++)
{
for (j=i+1;j<=count2;j++)
{
if (list2[i]>list2[j])
{
temp=list2[i];
list2[i]=list2[j];
list2[j]=temp;
}}}
}

void coseq::match()
{
int i=0,j=0;
while (i<=count1 && j<=count2)
{
if (list1[i]==list2[j]) {cout<<"\n"<<list1[i];i++;j++;}
if (list1[i] < list2[j]) i++;
if (list1[i] > list2[j]) j++;
}
}


int main()
{
coseq c1;
c1.load_list();
c1.sort_list();
c1.match();
return 0;
}

Sunday, 18 November 2012

Fs lab program for variable lenght record using RRN

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
using namespace std;
class student
{
public:
      string USN;
      string Name;
      string Branch;
      int Semester;
      string buffer;
      int count;

      int rrn_list[100];

      void read_data();
      void pack();
      void write_to_file();
      void unpack();
      void create_rrn();
      void search_by_rrn(int);
};
void student::read_data()
{
      cout<<"\nUsn:";
      cin>>USN;
      cout<<"\nName:";
      cin>>Name;
      cout<<"\nBranch:";
      cin>>Branch;
      cout<<"\nSemster:";
      cin>>Semester;
}

void student::pack()
{
      string sem;
      stringstream out;
      out << Semester;
      sem = out.str();
      buffer.erase();
      buffer=USN+'|'+Name+'|'+Branch+'|'+sem+'$'+'\n';
}

void student::write_to_file()
{
      int pos;
      fstream file;
      file.open("1.txt",ios::out|ios::app);
      pos=file.tellp();
      file<<buffer;
      file.close();
      rrn_list[++count]=pos;
}

void student::unpack()
{

      string sem;
      int ch=1,i=0;
      USN.erase();
      while (buffer[i]!='|')
      USN+=buffer[i++];

      Name.erase();
      i++;
      while (buffer[i]!='|')
      Name+=buffer[i++];

      Branch.erase();
      i++;
      while (buffer[i]!='|')
      Branch+=buffer[i++];

      sem.erase();
      i++;
      while (buffer[i]!='$')
      sem+=buffer[i++];
      istringstream out(sem);
      out>>Semester;

}

void student::create_rrn()
{
      ifstream file;
      int pos;
      count=-1;
      file.open("1.txt",ios::in);
      while (!file.eof())
      {
            pos=file.tellg();
            buffer.erase();
            getline(file,buffer);
            rrn_list[++count]=pos;
      }
      file.close();
}

void student::search_by_rrn(int rrn)
{
      int pos=-1;
      fstream file;
      if (rrn>count)    cout<<"\n Not Found";
      else{
      buffer.erase();
      file.open("1.txt");
      pos=rrn_list[rrn];
      file.seekp(pos,ios::beg);
      getline(file,buffer);
      cout<<"\n"<<buffer<<"\n" ;
      }
}


int main()
{
      int choice,rrn;
      student s1;

      s1.create_rrn();

      while(1){
      cout <<"\nMain Menu\n 1.Add \n\n 2.Search 3.EXIT\n\nEnter the choice:";
      cin>>choice;
      switch (choice)
      {
            case 1: cout<<"Data\n";
                  s1.read_data();
                  s1.pack();
                  s1.write_to_file();
                  break;
            case 2: cout <<"\n\nEnter the RRN";
                  cin>>rrn;
                  s1.search_by_rrn(rrn);
                  break;
            case 3: return 0;
            default:cout<<"\n\nWrong Choice";
                  break;
      }}
}

Fs lab program for fixed length record

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
using namespace std;
class student
{
public:
      string USN;
      string Name;
      string Branch;
      int Semester;
      string buffer;

      void read_data();
      void pack();
      void write_to_file();
      void unpack();
      int search(string);
      int delete_from_file(string);
      void modify(string);
};
void student::read_data()
{
      cout<<"\nUsn:";
      cin>>USN;
      cout<<"\nName:";
      cin>>Name;
      cout<<"\nBranch:";
      cin>>Branch;
      cout<<"\nSemster:";
      cin>>Semester;
}
void student::pack()
{
      string sem,temp;
      stringstream out;
      out << Semester;
      sem = out.str();
      temp.erase();
      temp+=USN+'|'+Name+'|'+Branch+'|'+sem;
      for(;temp.size()<100;) temp+='$';
      buffer+=temp+'\n';

}

void student::write_to_file()
{
      fstream file;
      file.open("1.txt",ios::out|ios::app);
      file<<buffer;
      file.close();
}

void student::unpack()
{

      string sem;
      int ch=1,i=0;
      USN.erase();
      while (buffer[i]!='|')
      USN+=buffer[i++];

      Name.erase();
      i++;
      while (buffer[i]!='|')
      Name+=buffer[i++];

      Branch.erase();
      i++;
      while (buffer[i]!='|')
      Branch+=buffer[i++];

      sem.erase();
      i++;
      while (buffer[i]!='$')
      sem+=buffer[i++];
      istringstream out(sem);
      out>>Semester;

}

int student::search(string key)
{
      ifstream file;
      int flag=0, pos=0;
      file.open("1.txt",ios::in);
      while (!file.eof())
      {
            buffer.erase();
            getline(file,buffer);
            unpack();
            if (key==USN) {cout<<"\nFound the key. The record is "<<buffer;pos=file.tellg(); flag=1;return pos;}
      }
      file.close();
      if (!flag) {cout<<"\n Not Found \n\n"; return pos;}

}

int student::delete_from_file(string key)
{
      fstream file;
      char del_mark='*',t;
      int pos,flag=0;
      pos=search(key);
      if (pos){
            file.open("1.txt");
            pos-=101; //skip the $$$$$$ and \n characters
            file.seekp(pos,ios::beg);
            file.put(del_mark);
            flag=1;
            }
      file.close();
      if (!flag) return 0;
      else return 1;

}

void student::modify(string key)
{
      int choice;
      if (delete_from_file(key)){
      cout<<"\n What to modify?";
      cin>>choice;
      switch(choice)
      {
            case 1: cout<<"\nUSN:"; cin>>USN; break;
            case 2:     cout<<"\nName:";cin>>Name;break;
            case 3:     cout<<"\nBranch:";cin>>Branch;break;
            case 4:     cout<<"\nSemster:";cin>>Semester;break;
            default: cout <<"Wrong Choice";
      }
      buffer.erase();
      pack();
      write_to_file();
      }
}

int main()
{
      int count,choice,len,i;
      student s1;
      string key;
      cout <<"\nMain Menu\n 1.Add \n\n 2.Delete \n\n 3.Modify \n\n 4.Search \n\nEnter the choice:";
      cin>>choice;
      switch (choice)
      {
            case 1: cout<<"\n\nhow many records to insert?\n";
                  cin>>count;
                  for (i=0;i<count;i++)
                  {
                        cout<<"Data\n";
                        s1.read_data();
                        s1.pack();
                  }
                  s1.write_to_file();
                  break;
            case 2: cout <<"\n\nEnter the key";
                  cin>>key;
                  i=s1.delete_from_file(key);
                  break;
            case 3: cout <<"\n\nEnter the key";
                  cin>>key;
                  s1.modify(key);
                  break;
            case 4: cout <<"\n\nEnter the key";
                  cin>>key;
                  i=s1.search(key);
                  break;
            default: cout<<"\n\nWrong Choice";
      }
      return 0;
}

FS lab program for secondary indexing

#include <iostream>

#include <fstream>

#include <string>

#include <sstream>

using namespace std;

class secondary_index

{

public:

string Name_list[100];

int Address_list[100];

int count;

void create_index();

void insert();

void remove(string);

void delete_from_file(int);

void search(string);

int search_index(string);

void read_from_file(int);

string extract_Name(string);

void sort_index();

};

void secondary_index::create_index()

{

fstream file;

int pos;

string buffer,Name;

count=-1;

file.open("1.txt",ios::in);

while (!file.eof())

{

pos=file.tellg();

buffer.erase();

getline(file,buffer);

if (buffer.empty()) break; //imp since it reads the last \n and goes to new line

Name=extract_Name(buffer);

Name_list[++count]=Name;

Address_list[count]=pos;

}

file.close();

sort_index();

}

string secondary_index::extract_Name(string buffer)

{

string USN,Name;

int i=0;

USN.erase();

while (buffer[i]!='|')

USN+=buffer[i++];

Name.erase();

i++;

while (buffer[i]!='|')

Name+=buffer[i++];

return Name;

}

void secondary_index::sort_index()

{

int i,j,temp_Address;

string temp_Name;

for (int i=0;i<=count;i++)

{

for (int j=i+1;j<=count;j++)

{

if (Name_list[i]>Name_list[j])

{

temp_Name=Name_list[i];

Name_list[i]=Name_list[j];

Name_list[j]=temp_Name;

temp_Address=Address_list[i];

Address_list[i]=Address_list[j];

Address_list[j]=temp_Address;

}}}

}

void secondary_index::insert()

{

string USN, Name, Branch, sem, buffer;

int Semester,pos;

fstream file;

cout<<"\nUsn:";

cin>>USN;

cout<<"\nName:";

cin>>Name;

cout<<"\nBranch:";

cin>>Branch;

cout<<"\nSemster:";

cin>>Semester;

stringstream out;

out << Semester;

sem = out.str();

buffer.erase();

buffer=USN+'|'+Name+'|'+Branch+'|'+sem+'$'+'\n';

file.open("1.txt",ios::out|ios::app);

pos=file.tellp();

file<<buffer;

file.close();

Name_list[++count]=Name;

Address_list[count]=pos;

sort_index();

}

int secondary_index::search_index(string key)

{

int low=0,high=count,mid=0,flag=0,pos;

while (low<=high)

{

mid=(low+high)/2;

if (Name_list[mid]==key) {flag=1; break;}

if (Name_list[mid]>key) high=mid-1;

if (Name_list[mid]<key) low=mid+1;

}

if (flag) return mid;

else return 0;

}

void secondary_index::search(string key)

{

int pos=0,t;

string buffer;

buffer.erase();

pos=search_index(key);

if (pos){

read_from_file(pos);

t=pos;

while (Name_list[++t]==key) read_from_file(t);

t=pos;

while (Name_list[--t]==key) read_from_file(t);

}

else cout<<"\nNot Found";

}

void secondary_index::read_from_file(int pos)

{

int address;

string buffer;

fstream file;

file.open("1.txt");

address=Address_list[pos];

file.seekp(address,ios::beg);

getline(file,buffer);

cout<<"\nFound the record: "<<buffer;

file.close();

}

void secondary_index::remove(string key)

{

int pos=0,t,choice;

string buffer;

buffer.erase();

pos=search_index(key);

if (pos){

read_from_file(pos);

cout<<"\n Delete?";

cin>>choice;

if (choice) delete_from_file(pos);

t=pos;

while (Name_list[++t]==key){

read_from_file(t);

cout<<"\n Delete?";

cin>>choice;

if (choice) delete_from_file(t);

}

t=pos;

while (Name_list[--t]==key){

read_from_file(t);

cout<<"\n Delete?";

cin>>choice;

if (choice) delete_from_file(t);

}

else cout<<"\n Not Found";

}

void secondary_index::delete_from_file(int pos)

{

char del_ch='*';

int i, address;

fstream file;

file.open("1.txt");

address=Address_list[pos];

file.seekp(address,ios::beg);

file.put(del_ch);

cout<<"\nRecord Deleted: ";

for (i=pos;i<count;i++)

{

Name_list[i]=Name_list[i+1];

Address_list[i]=Address_list[i+1];

}

count--;

}

int main()

{

int choice;

string key;

secondary_index i1;

i1.create_index();

while(1){

cout <<"\nMain Menu\n------------\n1.Add \n2.Search \n3.Delete \n4.EXIT\n---------------\nEnter the choice:";

cin>>choice;

switch (choice)

{

case 1: cout<<"Data\n";

i1.insert();

break;

case 2: cout <<"\n\nEnter the name";

cin>>key;

i1.search(key);

break;

case 3:cout <<"\n\nEnter the name";

cin>>key;

i1.remove(key);

break;

case 4: return 0;

default:cout<<"\n\nWrong Choice";

break;

}}

}