Data Structures & Algorithms, Fall 2008

Programming Assignment 1b - An Example Solution


Table of Contents

Introduction

This page gives a solution to part 2 of the first programming assignment.
<main.cc>=

#include <iostream>
#include <stdlib.h>
#include <cassert>
#include "read.h"
#include "elevations.h"


// Deja vu c++ style.

   static std::string read_size(std::istream &, unsigned &, unsigned &)
   static std::string read_data(std::istream &, unsigned &, unsigned &)


static void
compute(unsigned rainfall, double & wlevel, unsigned & usquares) 

  wlevel = elevations::min_elevation()
  usquares = 0

  while elevations::more() ∧ (rainfall > 0)
    unsigned sea_level_squares, height
    elevations::next(sea_level_squares, height)
    usquares += sea_level_squares
    const unsigned 
      lake_area = usquares*100,
      increment = std::min(lake_area*height, rainfall)
    wlevel += increment/static_cast<double>(lake_area)
    rainfall -= increment

  if (not elevations::more()) ∧ (rainfall > 0)
    usquares = elevations::count()

  if rainfall > 0
    assert(usquares > 0)
    wlevel += rainfall/(usquares*100.0)


int
main() 

  unsigned cnt, rainfall
  int rv = EXIT_SUCCESS

  const std::string emsg = read_data(std::cin, cnt, rainfall)
  if not emsg.empty()
    std::cerr << "!!! " << emsg << ".\n"
    rv = EXIT_FAILURE
  else 
    double water_level
    unsigned underwater_squares

    compute(rainfall, water_level, underwater_squares)

    std::cout.setf(std::ios::fixed, std::ios::floatfield)
    std::cout.precision(2)

    assert(cnt > 0)
    std::cout << water_level << "\n"
              << (underwater_squares/static_cast<double>(cnt))*100.0 << "\n"

  elevations::finalize()
  exit(rv)


static std::string
read_data(
  std::istream & ins, unsigned & cnt, unsigned & rain) 

  // Read from the given input stream, the count, elevations, and rain 
  // and store them in the given references.  Return an error message if 
  // anything goes wrong, an empty string otherwise.

  unsigned h, w
  std::string emsg = read_size(ins, h, w)
  cnt = h*w

  if emsg.empty()
    elevations::init()
    emsg = elevations::read(ins, cnt)
    if emsg.empty()
      emsg = read_unsigned(ins, rain, "rainfall")

  return emsg


static std::string
read_size(std::istream & ins, unsigned & h, unsigned & w) 
  
  // Read the height and width from the given input stream; store the values
  // read in the given references.  Return true if no errors occurred, false
  // otherwise.

  std::string emsg = read_unsigned(ins, h, "height")

  if emsg.empty()
    emsg = read_unsigned(ins, w, "width")

  return emsg
Defines main.cc (links are to index).

Reading

<read.h>=

#ifndef _read_h_defined_
#define _read_h_defined_

#include <string>
#include <istream>

// Read an int from the given input stream; store the value read in the
// given pointer.  Return true if no errors occurred, false otherwise.

  extern std::string read_signed(std::istream &, int &, const char * const)


// Read an int from the given input stream; store the value read in the
// given pointer.  Return true if no errors occurred, false otherwise.

  extern std::string read_unsigned(std::istream &, unsigned &, const char * const)

#endif
Defines read.h (links are to index).

<read.cc>=

#include "read.h"

std::string
read_signed(std::istream & ins, int & value, const char * const what) 

  ins >> value
  if ins.eof()
    return std::string("Unexpected eof; ") + what + " expected"
  if ins.fail()
    return std::string("Unexpected value; integer ") + what + " expected"
  if ins.bad()
    return std::string("Unrecoverable I-O error occurred during ") + what + " read"

  return ""


std::string
read_unsigned(std::istream & ins, unsigned & value, const char * const what) 

  int i
  std::string emsg = read_signed(ins, i, what)

  if emsg.empty()
    if i < 0
      emsg = std::string("Negative ") + what + " value read, non-negative value expected"
    else
      value = static_cast<unsigned>(i)

  return emsg
Defines read.cc (links are to index).

Representing Elevations

<elevations.h>=

#ifndef _elevations_h_defined_
#define _elevations_h_defined_

#include <string>
#include <istream>

namespace elevations 

  // Return the number of elevations.

     unsigned count()


  // Prepare the elevation set for its trip to the great beyond.

     void finalize()


  // Initialize the elevation set to be empty.

     void init()


  // Return the smallest elevation.

     int min_elevation()


  // Return true iff there are more elevations to consider.

     bool more()


  // Figure out the number of squares at sea level and the difference in
  // height between the sea-level squares and the next highest squares
  // store the values in the given references.

     void next(unsigned & sea_level_squares, unsigned & height)


  // Read the given number of elevations from the given input stream; this
  // replaces any elevations currently in the set.  Return an error
  // message if something went wrong; otherwise return an empty string.

     std::string read(std::istream &, unsigned)

#endif
Defines elevations.h (links are to index).

<elevations.cc>=

#include <cassert>
#include <algorithm>
#include "elevations.h"
#include "read.h"


// The largest and smallest elevations in the set.

   static int mn, mx


// The elevations and their count.

   static int * e = 0
   unsigned ecnt = 0


// The iterator index.

   static unsigned next_i = 0


namespace elevations 

   unsigned
   count() 
     return ecnt


   void finalize() 
     delete [] e


   void init() 
     ecnt = 0
     e = 0
     next_i = 0


   int
   min_elevation() 
     assert(ecnt > 0)
     return e[0]


   bool
   more()  
     for unsigned i = next_i + 1; i < ecnt; i++
       if e[next_i] ≠ e[i]
         return true

     return false

   void 
   next(unsigned & sea_level_squares, unsigned & height) 

     const unsigned s = next_i

     while e[s] == e[++next_i]
       assert(next_i < ecnt)

     sea_level_squares = next_i - s
     height = e[next_i] - e[s]


   std::string 
   read(std::istream & is, unsigned cnt) 

     std::string emsg

     ecnt = cnt
     delete [] e
     e = new int [ecnt]

     for unsigned i = 0; (i < cnt) and emsg.empty(); i++
       emsg = read_signed(is, e[i], "elevation")
     std::sort(e, e + cnt)

     next_i = 0

     return emsg


#ifdef ELEVATIONSTESTING

  // g++ -o elevationstesting -g -DELEVATIONSTESTING -ansi -pedantic -Wall elevations.cc read.cc ∧ ./elevationstesting

# include <sstream>

  int 
  main() 
    elevations::init()
    std::istringstream iss("0 2 "); // The trailing space is necessary.
    assert(elevations::read(iss, 2).empty())
    assert(elevations::count() == 2)
    assert(elevations::min_elevation() == 0)
    assert(elevations::more())

    unsigned sls, h
    elevations::next(sls, h)
    assert(not elevations::more())
    assert(sls == 1)
    assert(h == 2)

    iss.str("0 2 2 0 ")
    iss.clear()
    elevations::init()
    elevations::read(iss, 4)
    assert(elevations::count() == 4)
    assert(elevations::min_elevation() == 0)
    assert(elevations::more())
    elevations::next(sls, h)
    assert(not elevations::more())
    assert(sls == 2)
    assert(h == 2)

#endif
Defines elevations.cc (links are to index).

Index


This page last modified on 6 November 2008.

Creative
    Commons License