CSE 109 Test 1  Monday  4 October 2004
<<<<<<<<<<<<<<<<<<<<<SUGGESTED ANSWERS
1.  Assume that we want to compile a program and each of the classes
it uses separately, assume we have the four classes A, B, C, and D,
assume that the declarations for a class are in a .h file with the
corresponding letter (e.g., a.h) and that the code for a non-templated
class is in a .cc file (e.g., a.cc), assume that class B declares variable(s)
of type A, assume that class C declares variables of type A and of type B,
assume that class D declares variable(s) of type C, and assume the code
for the program is in the file prog.cc.
a) Write the makefile assuming the program uses class D, where all the
classes are non-templated.
b) Write the makefile assuming the program uses classes B and C, where
class C is templated and all the other classes are not templated.
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
a.  OPTS= -c -Wall -Werror
    prog: prog.o a.o b.o c.o d.o
        g++ -o prog prog.o a.o b.o c.o d.o
    prog.o: prog.cc a.h b.h c.h d.h
        g++ $(OPTS) prog.cc
    a.o: a.h a.cc
        g++ $(OPTS) a.cc
    b.o: a.h b.h b.cc
        g++ $(OPTS) b.cc
    c.o: a.h b.h c.h c.cc
        g++ $(OPTS) c.cc
    d.o: a.h b.h c.h d.h d.cc
        g++ $(OPTS) d.cc

b.  OPTS= -c -Wall -Werror
    prog: -o prog prog.o b.o a.o
        g++ prog.o b.o a.o
    prog.o: prog.cc a.h b.h c.h
        g++ $(OPTS) prog.cc
    a.o: a.h a.cc
        g++ $(OPTS) a.cc
    b.o: a.h b.h b.cc
        g++ $(OPTS) b.cc

2.  The binary tree considered in class had its keys "in order." A "heap"
is binary tree where the keys are instead ordered as follows: for every node
the key at the node is larger than the keys stored in (any of) its two
children.  Below is the relevant part of the declaration of BinTree. Write
the declaration and definition (code) for a member function heap() that
returns true if an only if the tree is a heap.  Your function can call other
functions (that you write).
  class BinTree
  {public:
     static const int LEFT=0, RIGHT=1;
      {public:                    
         Node(int k=0, double x=0.0,Node*lft=NULL,Node*rt=NULL);
         int key;
         double x;
         Node *child[2];
      };
    ......
    private:
      Node *root;
     ....
  };
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
add to the above class the prototypes (the first public, the second private)
bool heap()const;
static bool heap(Node*rt);

bool BinTree::heap()const {return heap(root);}

bool BinTree::heap(Node*rt)
{return rt==NULL ||
     (rt->child[LEFT]==NULL || rt->key>rt->child[LEFT]->key)
  && (rt->child[RIGHT]==NULL || rt->key>rt->child[RIGHT]->key)
  && heap(rt->child[LEFT])
  && heap(rt->child[RIGHT]);
}


3.  Write the template for a class Point that behaves like the one we
discussed in class. In particular, the following code should compile
and produce the output indicated:
   Point<int> a(2,3);
   a.set(Point<int>::X,32);
   //Note: This could also be written a.set(a.X,32);
   cout<<"The point "<<a<<" has y component "<<a.get(Point<int>::Y)<<endl;
   //  Output: The point (32,3) has y component 3
   //Note: The above code could also be
   //cout<<"The point "<<a<<" has y component "<<a.get(a.Y)<<endl;
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
template <class T>
class Point
{public:
  static const int X=0,Y=1;
  Point(const T & ex, const T & why);
  void set(int k,const T &t);
  T get(int k) const;
  template <class V>
  friend ostream & operator<<(ostream &out,const Point<V> & p);
 private:
   T x,y;
};

template <class T>
Point<T>::Point(const T & ex, const T & why):x(ex),y(why){}

template <class T>
void Point<T>::set(int k, const T &t)
{if(k==X)
  x=t;
 else
  y=t;//doesn't detect t!=Y
}

template <class T>
T Point<T>::get(int k)const
{if(k==X)
  return x;
 else
  return y; //doesn't detect t!=Y
}
  template <class V>
  ostream & operator<<(ostream &out,const Point<V> & p)
{out<<"("<<p.x<<", "<<p.y<<")";
 return out;
}

4.  The declaration for the class Rectangle below is meant to represent a
geometric rectangle.  Write declaration and definitions (code) for Box, a
subclass of the class Rectangle so that the code below the declaration
has the indicated affect.
 class Rectangle
 {public:
   Rectangle(int lngth=10, int wide = 10);
   int getLength()const;
   int getWidth()const;
   int getArea()const;
  private:
   int length,width;
 };

 Box a(2,3,4);
 cout<<"The box "<<a<<" has length "<<a.getLength()
     <<", width "<<a.getWidth()<<", height "<<a.getHeight()
     <<", and volume "<<a.getVolume()<<endl;
 //Output: The box (2,3,4) has length 2, width 3, height 4, and volume 24
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<,
 class Box: public Rectangle
 {public:
   Box(int length=10, int wide=10, int ht=10);
   int getHeight()const;
   int getVolume()const;
   friend ostream & operator<<(ostream &out,const Box &b);
  private:
   int height;
 };

 Box::Box(int len,int wd, int ht):Rectangle(len,wd),height(ht){}

 int Box::getHeight()const {return height;}

 int Box::getVolume()const {return height*getLength()*getWidth();}

 ostream & operator<<(ostream &out, const Box &b)
 {out<<"("<<b.getLength()<<", "<<b.getWidth()<<", "<<b.height<<")";
  return out;
 }