CSE 109 Final Examination   8 AM Wednesday  21 December 2011
========================SUGGESTED ANSWERS====================
1.  Consider the ADT for a calculator for miles computing per gallon. Such
a calculator accumulates entries of miles and gallons and then returns
the corresponding "miles per gallon."  This question asks you to implement
this ADT, while the next question asks you to implement a subclass of the
class you implement here. In implementing the class for this question be
sure it is compatible with your implementation of the sublass. Write a class
Mpg for which the following code compiles and produces the indicated
output.
int main(){
  Mpg x;
  x.enter(205.5,15.4).enter(94.5,4.6);
  cout<<"You went "<<x[x.M]<<" miles, used "<<x[Mpg::G]<<" gallons, "
    <<"for an mpg of "<<x[x.MPG]<<endl;
  //OUTPUT: You went 300 miles, used 20 gallons, for an mpg of 15
  cout<<x<<endl;     //OUTPUT: Mpg(300/20-->15)
}
===========================================================================
#include <iostream>
using namespace std;

class Mpg{
protected:
  double miles,gallons;
public:
  static const int M=0,G=1,MPG=2;
  Mpg();
  double operator[](int index)const;
  friend ostream & operator<<(ostream &out,const Mpg&x);
  Mpg & enter(double m,double g);
protected:
  static void check(bool b, const char *mess);
};

Mpg::Mpg():miles(0),gallons(0){
}

double Mpg::operator[](int index)const{
  check(index>=0 && index<3,"Index must be 0, 1, or 2");
  switch(index){
  case M: return miles;
  case G: return gallons;
  case MPG:
    check( gallons>0,"Amount of gallons  must be positive");
    return miles/gallons;
  };
  return 0;
}

Mpg& Mpg::enter(double m, double g){
  check(m>0 && g>0,"Amounts of miles and gallons  must be positive");
  miles+=m;
  gallons+=g;
  return *this;
}

ostream & operator<<(ostream &out,const Mpg&x){
  return out<<"Mpg("<<x.miles<<"/"<<x.gallons<<"-->"<<x.miles/x.gallons<<")";
}

void Mpg::check(bool b, const char * mess){
  if(!b){
    cerr<<"ERROR[Mpg]: "<<mess<<endl;
    exit(1);
  }
}

===========================================================================
2. Consider the ADT for an enhanced version of the calculator in question 1.
The enhanced calculator should enable the user to combine the contents of a
number of calculators. (Imagine having a number of cars and an Mpg calculator
for each. You then might want to combine the informatation in the individual
calculators to store mpg information for the "fleet.")  Write a class
MpgPlus that is a subclass of Mpg and for which the following code compiles
and produces the indicated output.

int main(){
   MpgPlus a(200.0,10.0), b(150,15.0), c[]={a, b, MpgPlus(150,10)};
   cout<<a<<endl; //OUTPUT:  Mpg(200/10-->20)
   a+=b;
   cout<<a<<endl; //OUTPUT:    Mpg(350/25-->14)
   cout<< MpgPlus::addFleet(c,3)<<endl; //OUTPUT:   Mpg(500/35-->14.2857)
   return 0;
}
===========================================================================
class MpgPlus:public Mpg{
public:
  MpgPlus(double m, double g);
  const MpgPlus& operator+=(const MpgPlus&p);
  static MpgPlus addFleet(MpgPlus f[],int n);
};

MpgPlus::MpgPlus(double m,double g){
  enter(m,g);
}

const MpgPlus&MpgPlus::operator+=(const MpgPlus&p){
  enter(p.miles,p.gallons);
  return *this;
}

MpgPlus MpgPlus::addFleet(MpgPlus f[],int n){
    MpgPlus temp(0,0);
    while(n>0){
      n--;
      temp+=f[n];
    }
  return temp;
}
===========================================================================
3. Assume that for each class mentioned below the declaration for the class
is in a .h file of the same name, but in lower case, and the code is in a
.cc of the same name, but in lower case.  Class B is a subclass of class A.
Class C is a subclass of class A, has the method void t(B&b), and uses a
templated class that is stored in the file x.t. Class D is a subclass of
class C. The main program is stored in the file prog.cc and has objects of
type B and of type D.
(1) For each .h file and each .cc file, write the necessary "include"
statement(s).
(2) Write a makefile that uses "separate compilation" for compiling prog.cc,
creating the executable file "prog", and for "cleaning up."
===========================================================================
a.h:      #include <iostream>   ????
a.cc:     #include "a.h"
b.h:      #include "a.h"
b.cc:     #include "b.h"
c.h:      #include "b.h"
          #include "x.t"  //here is the best place, to be sure
c.cc      #include "c.h"
d.h:      #include "c.h"
d.cc:     #include "d.h"
prog.cc:  #include "d.h"
prog: prog.o a.o b.o c.o d.o
        g++  prog.o a.o b.o c.o d.o
prog.o: prog.cc a.h b.h c.h d.h x.t
        g++ -c -Wall -Werror prog.cc        
a.o: a.cc a.h
        g++ -c -Wall -Werror a.cc
b.o: b.cc a.h b.h
        g++ -c -Wall -Werror b.cc
c.o: c.cc a.h b.h c.h x.t
        g++ -c -Wall -Werror c.cc
d.o: d.cc a.h b.h c.h d.h x.t
        g++ -c -Wall -Werror d.cc
clean:
        rm -f *~ *.o prog
===========================================================================
4. Given the syntax diagrams below and given the C++ code below, write the
functions needed for the program to compile and determine whether a string
of characters given to an instance of Lex satisfies the syntax for S.
Recall the Lex tokens LT, GT, LPAREN, RPAREN, IDENT, NUMBER, and EOLN.
  S                                  A
   ---->('<')---[A]---('>')--->      ---->[NUMBER]-------------------------->
     |                                              ^                      |
     +-->('(')---[A]---(')')--->                    |                      |
     |                                              +--(')')--[S]--('(')<--+
     +--->[IDENT]----------->
void check(bool b,const char* mess){
  if(!b){
    cerr<<"<---ERROR: "<<mess<<endl;
    exit(1);
  }
}
int main(){
  Lex lex;
  int token;
  lex.set("< 6 ( aa ) ( bb )  >");  //good string
  next(lex,token); //call lex.next() and display lex.str()
  s(lex,token);
  check(token==lex.EOLN," end of line expected");
  cout<<"Success\n";
}
===========================================================================
void next(Lex&lex,int &token){
  token=lex.next();
  cerr<<lex.str()<<' ';
}
			      
void s(Lex &lex,int &token){
  switch(token){
  case Lex::LT:
    next(lex,token);
    a(lex,token);
    check(token==lex.GT," '>' expected");
    break;
  case Lex::LPAREN:
    next(lex,token);
    a(lex,token);
    check(token==lex.RPAREN," ')' expected");
    break;
  default:
    check(token==lex.IDENT," identifier expected");
  }
  next(lex,token);
}

void a(Lex &lex, int &token){
  check(token=lex.NUMBER," Number expected");
  next(lex,token);
  while(token==lex.LPAREN){
    next(lex,token);
    s(lex,token);
    check(token==lex.RPAREN,"')' expected");
    next(lex,token);
  }
}
===========================================================================
5. A triple is an ordered sequence of three items. Write the template for a
class Triple that implements the ADT for a triple and enables the code
below to compile and produce the indicated output.

    Triple<int> t(6,7,8);
    t[0]=14;
    cout<<t<<endl; //OUTPUT: (14, 7, 8)
    Triple<Word> w("ONE","two","Three");
    cout<<w<<"[1]='"<<w[1]<<"'\n";  // (ONE, two, Three)[1]='two'
===========================================================================
template <class X>
class Triple{
private:
  X data[3];
public:
  Triple(const X &a=X(), const X&b=X(), const X&c=X());
  X&operator[](int n);
  const X& operator[](int n)const;
  template<class Y>
  friend ostream & operator<<(ostream &out,const Triple<Y>&t);
  
};

template <class X>
Triple<X>::Triple(const X &a, const X&b, const X&c){
  data[0]=a;
  data[1]=b;
  data[2]=c;
}
  
template <class X>
X & Triple<X>::operator[](int n){
  if(n<0 || n>2){
    cerr<<"Range error in operator[]";
    exit(1);
  }
  return data[n];
}

template <class X>
const X & Triple<X>::operator[](int n)const{
  if(n<0 || n>2){
    cerr<<"Range error in operator[]";
    exit(1);
  }
  return data[n];
}

template <class X>
ostream & operator<<(ostream &out,const Triple<X>&t){
  return out<<"("<<t[0]<<", "<<t[1]<<", "<<t[2]<<")";
}
===========================================================================
6. Assume the declaration of the class Node3, which is below. (A templated
version of Node3 was the basis of programming assignment p7.) Assume we have
the declaration Node3 *rt, and assume that rt points to the root of a valid
3-tree. Write a function sum() that returns the sum of the keys in the
tree. A typical use of the method would be
   cout<<"The sum of the keys in the tree is "<<sum(rt)<<endl;
The method sum() can call other methods that you write.
class Node3{
public:
  Node3 *child[3];  //pointers to (up to) three children.
  int key[2];   //the keys, where key[0]<key[1]
  double data[2];  //the corresponding data
  bool full;  // false if only one key, true if two
  Node3(int k,double d);
  ....
  ....
};
===========================================================================
int sum(Node3 * rt){
  int tot;
  if(rt==NULL)
    return 0;
  if(!rt->full)
    return rt->key[0];
  tot=0;
  for(int j=0;j<3;j++){
    if(j<2)
      tot+=rt->key[j];
    tot+=sum(rt->child[j]);
  }
  return tot;
}
===========================================================================
7.  Write a C program that will compile with the gcc option -xc (e.g.,
gcc -xc -Wall -Werror prog.c), that reads pairs consisting of an int and
a double from the text file 'q7.dat' into an array of structs, and that
subsequently prints out the pairs that have been read. You can assume that
the file exists and contains no more than 100 pairs.
===========================================================================
#include <stdio.h>

struct A{
  int k;
  double d;
};

int main(){
  FILE *f;
  struct A x[101];
  int j,n;
  f=fopen("q7.dat","r");
  n=0;
  while(fscanf(f," %d %lf",&x[n].k,&x[n].d)==2)
    n++;
  for(j=0;j<n;j++)
    printf(" %d %lf\n",x[j].k,x[j].d);
  return 0;
}
===========================================================================
8. Below is the (partial) declaration of the class Tree3, which is a specific
version of my templated solution to programming assignment 7. Note that it
uses the class Node3, (partially) declared in question 6. The class should be
fully documented. To help me get started with this documentation, provide
full documentation for the locations indicated, the purpose of the class,
and the method add().
/* (a) PROVIDE DOCUMENTATION TO BE PUT HERE
/*
class Tree3{
private:
  Node3 *root;
public:
  Tree3();
  ~Tree3();
  bool inTree3(int k)const;
/* (b) PROVIDE DOCUMENTATION TO BE PUT HERE
/*
  Tree3 & add(int k,double d);
  friend ostream & operator<<(ostream &out,const Tree3&t);
  double & operator[](int k);
  const double&operator[](int k)const;
private:
  .....
  .....
};
===========================================================================
/* (a) Tree3 implements the ADT for a 3-search-tree (3ST). All non-leaf
       nodes of a 3ST have two keys and 0 to 3 children. Leaf nodes have
       one or two keys. When a node has two keys, the keys are in ascending
       order. All keys in the subtree whose root is the first child of a
       node are less than the first key in a node. All keys in the subtree
       whose root is the second child of a node are between the first and
       second keys of the node.  All keys in the subtree whose root is the
       third child key of a node are greater than the second key in the node.
       Corresponding to each key (an int) is a datum (double). Tree3 has
       methods for adding entries to the tree, for accessing entries in
       the tree, and for displaying the tree in order.
/*

/* (b) Precondition: The tree is a 3ST
       Postcondition: The tree remains unchanged, except that the pair
       (k,d) has been added to the tree. Either a new node containing the
       pair (k,d) has been added to the tree, keeping the 3ST property,
       or the pair (k,d) has been added to a leaf which had only one entry.
       The resulting leaf, has the two keys in ascending order.
*/
===========================================================================