CSE 109 Test 2  Friday  14 November 2008
===========================SUGGESTED ANSWERS==========================
1. Many records are identified with the 9-digit social security number. Thus,
it would be useful to have a templated class for pairs whose first entry is
a social security number and whose second entry is of some given type. Write
the template for such a class, calling the class SSBox. It need only have
the functionality that would enable the code below to be compiled and to
produce the indicated output when run.
  SSBox<int>  a(887654321,22), b(a);
  cout<<a<<endl; // {SS# 887654321, 22}
  if(a==b)
    cout<<"Equal\n"<<endl;  // Equal
=======================================================================
#include <iostream>
using namespace std;
template <class X>
class SSBox{
public:
  SSBox(int n,const X &x);
  SSBox(const SSBox &s);
  bool operator == (const SSBox &s)const;
  template <class Y>
  friend ostream & operator<<(ostream &out,const SSBox<Y> &s);
private:
  int num;
  X data;
};
template <class X>
  SSBox<X>::SSBox(int n,const X &x):num(n),data(x){
    if(n<0){
      cerr<<"Bad SS#\n";
      exit(1);
    }
  }
template <class X>
  SSBox<X>::SSBox(const SSBox &s):num(s.num),data(s.data){}

  template <class X>
  bool SSBox<X>::operator == (const SSBox &s)const{
    return num==s.num && data==s.data;
  }
template <class Y>
ostream & operator<<(ostream &out,const SSBox<Y> &s){
  out<<"{SS# "<<s.num<<", "<<s.data<<"}";
  return out;
}
=======================================================================
2.  Below is the declaration of the class Name that implements the ADT for a
person's first and last name, using the class Word that we developed in
class. Write the declaration and definition (code) for the subclass, PName,
of Name that adds the ability to store the person's 7-dgit phone number.
It need only have the functionality that would enable the code below to be
compiled and to produce the indicated output when run.
 class Name{
   public:
     Name(const Word &firstName, const Word & lastName);
     const Word & getFirst()const;  //return the person's first name
     const Word & getLast()const;   //return the person's last name
     Word & setFirst(const Word &w);
     Word & setLast(const Word &w);
   private:
     Word first,last;
 };

  PName a("Thomas", "Mix",7582626);
  a.setLast("Johnson");
  a.number()=8342342;
  cout<<a<<endl;  // [Thomas Johnson, Ph: 8342342]
==========================================================================
#include "word.h"
class PName:public Name{
public:
  PName(const Word&firstName,const Word&lastName,int n);
  int & number();
  friend ostream & operator<<( ostream &out,const PName&p);
private:
  int num;
};

PName::PName(const Word&firstName,const Word&lastName,int n):
  Name(firstName,lastName),num(n){}

int & PName::number(){return num;}

ostream & operator<<( ostream &out,const PName&p){
  out<<"["<<p.getFirst()<<" "<<p.getLast()<<", Ph: "<<p.num<<"]";
  return out;
}
==========================================================================

3.  a) Why should the size of an array used for a hash table be prime?
          Dividing the hash number by a prime number makes the choice
          of storage location more "random."  The quadratic probe is
          guaranteed to work if the table size is prime (and if the table
          is less than half full).
    b) Why should a hash table never be more than half full?
          If the hash number is random and the subsequent probing is
          random, then the average number of "looks" will be less than
          2.  Further, if the table size is prime, then the quadratic
          probe is quaranteed to succeed.
    c) Assume that the hash number of an int is the int itself. For
       each hash table below, show where 107 would be stored, using a
       the methods developed in class and using the quadratic probe to
       handle collisions.
       0    1    2    3    4    5    6
     ------------------------------------
     |    |  1 | 107|  3 |    |    |    |
     ------------------------------------

       0    1    2    3    4    5    6    7     8    9   10
     --------------------------------------------------------
     |    |    |    | 36 |    |    |    |    | 118| 107|    |
     --------------------------------------------------------

       0    1    2    3    4    5    6    7     8    9   10
     --------------------------------------------------------
     |    | 1  | 107|    |    |    | 72 |    | 118| 9  |    |
     --------------------------------------------------------

4. Assume the class Word developed in class. Write a program that
reads a list of words from a file and displays on the screen the number of
times either the word "true" or  "false" appears in the file. Your program
can assume that there is exactly one word on the line and that each word
starts in the first column.  The output take the form, "The total is 6."
If the executable program is stored in the file a.out and the words in
the file aFile, the call would be(omitting the quotes)  "a.out < aFile".
===========================================================================
#include "word.h"

int main(){
  char ch,str[6];
  bool goodLength;
  int tot,loc;
  tot=0;
  cin.get(ch);
  while(cin.good()){
    loc=0;
    while(cin.good() && ch!='\n'){
      if(loc<5)
	str[loc]=ch;
      cin.get(ch);
      loc++;
    }
    if(loc<=5){
      str[loc]='\0';
      if(Word(str)=="true" || Word(str)=="false")
	tot++;
    }
    cin.get(ch);
  }
  cout<<"The total is "<<tot<<endl;
}
======================================================================