CSE 109 Final Examination  Sunday 9 May 2010
============================SUGGESTED ANSWERS============================
1. Assume that class A has the following public methods
  virtual void a() { b(); }
  void b() { cout<<1<<endl; };
Assume that class B is a subclass of class A and only has one (public) method:
  void b(){ cout<<2<<endl; }
Finally, assume that the class declarations of A and B are included with the
code below. What is the output of the code when compiled with the g++ compiler
and then run?

void one(int *a, int *&b){
  *b=9;
  b=a;
  *b=10;
  a=new int;
  *a=15;
}

void two(int *a, int *b){
  *a=6;
  a=b;
  *a=12;
}

int main(){
  int u,v,*w,*s;
  w=&u;
  s=&v;
  one(w,s);
  cout<<u<<" "<<v<<" "<<*w<<" "<<*s<<endl;
   //
   //                                           10 9 10 10
  u=20;
  v=30;
  two(&u,&v);
  cout<<u<<" "<<v<<endl;
   //                                           6 12
   //
  B x;
  x.b();
   //                                           2
   //
  x.a();
   //                                           1
   //
  x.A::b();
   //                                           1
   //
}
2. Class A below is meant to parse a line of text that purports to satisfy the
syntax diagram S below. Provide the code for the method s() and for method(s)
it might call. In the diagram I use parentheses, (), to indicate ovals and
square brackets, [], to indicate rectangles. The characters in the ovals are
'+', '-', '*', '/',  ')', and ']'. Assume the Lex I provided for p5. The
program in main() illustrates the use of class A.
                                     +--( + )--[S]--( ] )----+
#include "lex.h"               S     |                       |
#include "word.h"              ------+                       |-------------
#include "check.h"                   |                       |
class A{                             +--( - )--[B]--( ) )----+
 private:
  Lex lex;
  int tok;                           +--( * )----------------+
 public:                       B     |                       |
  void parse(const char *str); ------+--( / )--[B]-------------------------
  void s();                                        ^       |
};                                                 |       |
void A::parse(const char *str){                    +--[S]--+
  lex.setString(str);
  tok=lex.next();
  s(); //if errors, exit() in s() or in a method it calls;
  check(tok==Lex::EOLN,"Junk at end of line",__LINE__,__FILE__);
  cout<<"Successful parse\n";
}
int main(){
  A a;
  a.parse("+-*)]");
  a.parse("++-/*-*)-*))]]");
}
 ===========================================================================
void A::s(){
  switch(tok){
  case Lex::PLUS: tok=lex.next();
    s();
    check(tok==Lex::RBRACK,"']' expected",__LINE__,__FILE__);
    break;
  case Lex::MINUS: tok=lex.next();
    b();
    check(tok==Lex::RPAR,"')' expected",__LINE__,__FILE__);
    break;
  default: check(false,"'+' or '-' expected",__LINE__,__FILE__);
  }
  tok=lex.next();
}

void A::b(){
  switch(tok){
  case Lex::TIMES: tok=lex.next(); break;
  case Lex::DIVIDE: tok=lex.next();
    b();
    while(tok==Lex::PLUS || tok==Lex::MINUS)
      s();
    break;
  default: check(false,"'*' or '/' expected",__LINE__,__FILE__);
  };
}
 ===========================================================================
3. I am in the process of developing software to handle bank accounts. I have
started with the struct below which is used to record (up to to the first 19
characters of) a person's last name and the balance in the person's account.
Assume that I have created a binary file consisting of the contents of a
number of such structs. Write a function update() (1) that assumes it has
been passed a file variable pointing to a binary file that has been opened for
both reading and writing; (2) that assume it has been passed a positive value
for interest;  and (3) that adds that amount of interest to each
entry in the file. For example, if before the update an entry has the value
$100 and the interest is 0.05, then after the update the value stored would
be $105. The code below the struct shows how the function update would be
called. (Note that problem 4 uses struct Account and update().)

struct Account{
  char name[20];
  double balance;
}

FILE* f;
........
........
update(f,0.05);
 ===========================================================================
void update(FILE*f,double val){
  struct Account a;
  int count;
  fseek(f,0,SEEK_SET);
  count=0;
  while(fread(&a,sizeof(a),1,f)>0)
    count++;
  while(count>0){
    count--;
    fseek(f,count*sizeof(a),SEEK_SET);
    fread(&a,sizeof(a),1,f);
    a.amt*=1+val;
    fseek(f,count*sizeof(a),SEEK_SET);
    fwrite(&a,sizeof(a),1,f);
  }
}
 ===========================================================================
4. Write a program that opens a file whose name is given on the command line,
that assumes the file is a binary file of structs of type Account given in
(3), that has a copy of the C code for the function update() in (3), and that
adds 2% interest to each entry in the file. You may include any libraries,
but you may not assume that you have available any local files. If the
executable code for the program is stored in a.out, the call to the program
would look like
    a.out aFile.bin
 ===========================================================================
void check(int b,const char *mess,int line, const char * f);

int main(int ct,char **arg){
  FILE *f;
  check(ct==2," Usage: a.out <afile>",__LINE__,__FILE__);
  f=fopen(arg[1],"r+b");
  check(f!=NULL,"Failure to open input file",__LINE__,__FILE__);
  update(f,0.02);
}

void check(int b,const char *mess,int line, const char * f){
  if(!b){
    printf("ERROR: at line #%d in file '%s': %s\n",line,f,mess);
    exit(1);
  }
}
 ===========================================================================

5. Create a struct Link that implements the ADT for link in a linked list,
where the key also serves as the datum and is of type int. Then write the
function addToList() that adds a link to the list in ascending order. Below
is code that demonstrates its use. The resulting code should be able to be
compiled in C, i.e., using "g++ -xc".

   int x[]={2,7, 9, -5, 22, 13}, j;
   stuct Link *head;
   head=NULL;
   for(j=0;j<6;j++)
      head=addToList(head,x[j]);

 ===========================================================================
#include <stdlib.h>
#include <stdio.h>

struct Link{
  int k;
  struct Link*next;
};

struct Link* addToList(struct Link*hd,int j){
 struct  Link*temp;
  if(hd==NULL || j<=hd->k){
    temp=malloc(sizeof(struct Link));
    if(temp==NULL){
      printf("Heap overflow\n");
      exit(1);
    }
    temp->k=j;
    temp->next=hd;
    return temp;
  }
  hd->next=addToList(hd->next,j);
  return hd;
}
 =========================================================================
6. Consider the ADT for the module in a coin counter that keeps track of
the coins put into the machine. Write the declaration and definitions (code)
for this class, so that the code below compiles and produces the given
output. You may assume you have access to the usual function check().
 Counter a(2,4,5,6), b(a);  //start a with 2 Pennies, 4 Nickels, 5 Dimes,
                            //and 6 quarters
 a.add(Counter::P,2).add(a.N,3).add(Counter::D,10).add(a.Q,1);
     //add 2 pennies, 3 nickels, 10 dimes, and 1 quarter
 cout<<a<<endl;  //  Counter(4 pennies, 7 nickels, 15 dimes, 7 quarters)

 ===========================================================================
class Counter{
 protected:
  int count[4];
 public:
  static const int P=0,N=1,D=2,Q=3;
  Counter(int a=0,int b=0, int c=0, int d=0);
  Counter(const Counter &c);
  Counter & add(int type,int amt);
  friend ostream &operator<<(ostream &out, const Counter&c);
};

Counter::Counter(int a, int b, int c, int d){
  count[P]=a;
  count[N]=b;
  count[D]=c;
  count[Q]=d;
  check(a>=0 && b>=0 && c>=0 && d>=0,"Negative value(s) not allowed",
                    __LINE__,__FILE__);
}

Counter::Counter(const Counter&c){
  for(int j=0;j<4; j++)
    count[j]=c.count[j];
}

Counter&Counter::add(int type,int amt){
  check(amt>=0,"Only positive values can be added",__LINE__,__FILE__);
  check(type>=0 && type<=3,"Bad coin type",__LINE__,__FILE__);
  count[type]+=amt;
  return *this;
}

ostream &operator<<(ostream &out, const Counter&c){
  return out<<"Counter("<<c.count[0]<<" pennies, "<<c.count[1]
     <<" nickels, "<<c.count[2]<<" dimes, "<<c.count[3]<<" quarters)";
}
 ===========================================================================
7. Now create a subclass of the class Counter above, where the subclass adds
the ability to retrieve the amount of money stored and enables two instances
to be compared with "==" and with "<", where two instances are equal if they
have the same amount of money stored, and where instance a is less than
instance b if the amount of money stored in a is less than the amount in b.
Call the class CountUp. Your declaration and definitions should be such that
the code below compiles and produces the indicated output.

CountUp a(2,3,4,5), b(2,4,6,4);
cout<<a.balance()<<" "<<b.balance()<<endl; // 182 182
cout<<(a==b)<<" "<<(a<b)<<" "<<(b<a)<<endl;   //  1 0 0
 a.add(Counter::D,2);
cout<<a.balance()<<endl;  //  202
cout<<(a==b)<<" "<<(a<b)<<" "<<(b<a)<<endl;  // 0 0 1
cout<<(202==a)<<" "<<(202<a)<<endl;   /  1 0

 ===========================================================================
class CountUp: public Counter{
 public:
  CountUp(int a=0, int b=0, int c=0, int d=0);
  int balance()const;
  friend bool operator==(const CountUp&a, const CountUp &b);
  friend bool operator<(const CountUp&a, const CountUp &b);
};

CountUp::CountUp(int a, int b, int c, int d):Counter(a,b,c,d){}

int CountUp::balance()const{
  int total, vals[]={1,5,10,25};
  total=0;
  for(int j=0;j<4;j++)
    total+=count[j]*vals[j];
  return total;
}

bool operator==(const CountUp&a, const CountUp &b){
  return a.balance()==b.balance();
}

bool operator<(const CountUp&a, const CountUp &b){
  return a.balance()<b.balance();
}
 ===========================================================================
8.  Write the template for a binary search tree, where the key also serves
as the datum.  You need only implement the code needed to compile and run the
lines of the sample code below that are indicated with an arrow ( <------ ).
You may assume the existence of the templated class for a Node, where the
code below indicates the behavior of the templated class Node.

 Node <CountUp> n(CountUp(2,3,4,5));
 cout<<(n.child[0]==NULL)<<" "<<n.key<<endl;
   // 1  Counter(2 pennies, 3 nickels, 4 dimes, 5 quarters)
 cout<<n<<endl; //  Counter(2 pennies, 3 nickels, 4 dimes, 5 quarters)

 Tree<CountUp> t;  // <---------------------- PROVIDE CODE
 t.add(CountUp(2,3,45)).add(CountUp(1,3,4,2)).add(CountUp()); //DON'T CODE
 cout<<t<<endl;  // <------------------- PROVIDED CODE
                 //display tree in order to console
 ===========================================================================
template <class X>
class Tree{
 private:
  Node<X> * root;
 public:
  Tree();
  Tree & add(const X &x);  //not provided by student
  template <class V>
    friend ostream & operator<<(ostream &out,const Tree<V> &t);
 private:
  static void add(const X &x,Node<X> * &rt);   //not provided by student
  static void display(ostream &out,Node<X>*rt);
};

template <class X>
Tree<X>::Tree(){root=NULL;}

/**********************************************not provided by student
template <class X>
Tree<X>& Tree<X>::add(const X&x){
  add(x,root);
  return *this;
}

template <class X>
void Tree<X>::add(const X&x,Node<X> *&rt){
  if(rt==NULL)
    rt=new Node<X>(x);
  else if (x<rt->key)
    add(x,rt->child[0]);
  else
    add(x,rt->child[1]);
}
****************************************************not provided by student**/
template <class V>
ostream & operator<<(ostream &out,const Tree<V> &t){
  t.display(out,t.root);
  return out;
}

template <class X>
void Tree<X>::display(ostream &out,Node<X> *rt){
  if(rt!=NULL){
    display(out,rt->child[0]);
    out<<rt->key<<endl;
    display(out,rt->child[1]);
  }
}
 ===========================================================================