CSE 109 Test 2  Friday 16 April 2010
========================SUGGESTED ANSWERS====================
1. Consider the ADT for a "Range," which is a variable of some type that
can only take on a restricted range of values.  Write the template for a class
Range that implements this ADT.  What you write need only be sufficient for
the code below to compile and produce the indicated output. You can assume
you have available  void check(bool b, const char *mess, int n, const char*t);
  Range<double> a(2.7, 3.9, 2.9);  //only allow values from 2.7 to 3.9,
                                   //inclusive, initial value 2.9
  Range<int> b(0, 9, 2),c(3, 8, 5);
  cout<<a<<endl;  //  Range<2.7, 3.9>(2.9)
  cout<< (b<c) << (c<b) << endl;  // 10
==========================================================================
#include <iostream>
using namespace std;

template<class T>
class Range{
  private:
    T x,low,high;
    static void check(bool b, const char *mess); //not dictated by question
  public:
    Range(const T&a, const T&b,const T&c);
    bool operator<(const Range&a)const;
    template<class X>
    friend ostream & operator<<(ostream & out,const Range<X> & r);
};

template<class T>
Range<T>::Range(const T&a,const T&b, const T&c):x(c),low(a),high(b){
 check(a<b,"Bad range");
 check(a<=c && c<=b,"Value out of range");
}

template<class T>
bool Range<T>::operator<(const Range&a)const{return x<a.x;}

template<class T>
ostream & operator<<(ostream &out,const Range<T> &r){
  return out<<"Range<"<<r.low<<", "<<r.high<<">("<<r.x<<")";
}

template<class T>
void Range<T>::check(bool b,const char *mess){
  if(!b){
    cerr<<"ERROR: "<<mess<<endl;
    exit(1);
  }
}
==========================================================================
2. Write a program that counts the number of times the character '\n' occurs
in a file whose name is given by the first command line argument following the
name of the excecutable file and displays the count (which is zero if there is
no argument or if there is a name, but the file does not exist).
==========================================================================
#include <iostream>

#include <fstream>

using namespace std;



int count(istream &f);



int main(int cnt, char **arg){

  int ct;

  ifstream f;

  if(cnt==1)

    ct=0;

  else{

    f.open(arg[1]);

    ct=count(f);

  }

  cout<<"I counted "<<ct<<" '\\n's\n";


}



int count(istream &f){

  int temp;

  temp=0;

  char ch;

  f.get(ch);

  while(f.good()){

    if(ch=='\n')

      temp++;

    f.get(ch);

  }

  return temp;

}

==========================================================================
3. Consider a hash table for storing words (string of characters).
   a. If I use the hash table to store the last names of the 32 students
      in this class, what size table should I use and why?
   b. Suppose I have a hash table of size 59 for storing such names,
      assume that locations 52 through 58 are occupied, assume the string
      "Kay" has the hash number 112, and assume the string "Kay" is not
      in the table. Give the sequence of indices of the locations that
      would be probed when placing the string "Kay" in the table, using a
      quadratic probe.
   c. Suppose all the keys in the hash table have exactly two letters
      (either upper or lower case). Provide a rule for generating a hash code
      based on the two letters.
==========================================================================
   a. The table should be at least twice as big, so that it is never more
      than half full, and the size should be prime, so that when the remainder
      is found when dividing the hash number by the tables size, all of the
      hash number contributes to the result, and so that when using a
      quadratic probe to avoid collisions at least half the table is probed
      before probing the same place twice (thus guaranteeing success). I
      choose the table size of 67, which is the smallest prime larger than
      2*32.
   b. Try  112%59=53, then (53+1)%=54, then (53+4)%59=57, try (53+9)%59=3
      and succeed.
   c. I will take the prime number 67. Let the two letters be stored in
      the variables char a,b; Suppose we also have the variables int x,y;
       if('a'<=a && a<='z')
         x=a-'a';
       else
         x=a-'A'+26;
       if('a'<= b && b<='z')
         y=b-'a';
       else
         y=b-'A'+26;
       Thus x and y are both between 0 and 25.
       Set hash=x+67*y
==========================================================================
4. Class A below is meant to parse lines of text that purport to satisfy the
syntax diagram S below. Provide the code for the method s(). In the diagram I
Provide the method A::s(). In the diagram I use
use parentheses, (), for ovals and square brackets, [], for rectangles.
#include "lex.h"
#include "word.h"
#include "check.h"       S
class A{                 --(write)--+->( ( )----------------( ) )---+
private:                            |        ^            |         |
  Lex lex;                          |        |            |         |---->
  int tok;                          |        +-[S]--(*)<--+         |
public:                             |                               |
  void parse(const char *str);      +--------------------(-)--------+
  void s();
};
void A::parse(const char *str){
  lex.setString(str);
  tok=lex.next();
  s(); //if errors, exit() in s();
  cout<<"Successful parse\n";
}
int main(){
  A a;
  a.parse("write(*write())");
}
==========================================================================
void A::s(){
  check(tok==lex.WRITE,"'write' expected",__LINE__,__FILE__);
  tok=lex.next();
  if(tok==lex.LPAR){
    tok=lex.next();
    while(tok==lex.TIMES){
      tok=lex.next();
      s();
    }
    check(tok==lex.RPAR,"')' expected",__LINE__,__FILE__);
    tok=lex.next();
  }
  else{
    check(tok==lex.MINUS,"'-' expected",__LINE__,__FILE__);
    tok=lex.next();
  }
}
========================================================================