Homework 2 (CS 300, Parallel and Distributed Computing (PDC))

Homework 2

CS 300, Parallel and Distributed Computing (PDC)

Homework 2 Due 10/5/2018

STL queue container
1. [c]
  The Standard Template Library (STL) is a collection of common data structures and algorithms that are predefined for C++.
  - The STL containers are classes that implement data structures including vector (a dynamically resizable array), list (a doubly linked list), queue (a first-in first-out queue), and map (an ordered collection of key-value pairs).
  - STL iterators are objects for traversing (moving along) containers, whether in a forward direction, both forward or backward, or for random access.
  - STL algorithms implement common algorithms for containers such as sort, binary_search (for searching an ordered container), random_shuffle, and max.
  - STL functionals (also called functions) are objects that behave as functions, for comparing, combining, or operating on elements of one or two containers, such as negate, equal_to, plus, and divides.
  The STL uses C++ templates in order to make STL containers versatile (and hence also their iterators, algorithms, and functionals), so that elements of an STL container can have arbitrary types. Templates make it possible to specify a type as a parameter. For example, in the Software Design course, we implemented IntArray and FloatArray, two classes that were identical except replacing the type int by float. A templated definition
```
template <type T>
class Array {
protected:
  T *vec;
  int size;
...
}
```
  would define a templated class Array such that the type name Array<int> is equivalent to the IntArray class, and Array<float> is equivalent to the FloatArray class. Likewise, the algorithm sort is a templated function that sorts a range within a container (where the endpoints of that range are specified as iterators).
  
  We will begin exercises with the STL by using the STL queue container to create partial code for a simulation of the checkout area of a store. That simulation will use queue objects to represent checkout registers, where each element of a Register queue is an integer representing the number of items in a single store cart. Over time, new carts are added to the end of that queue, and the oldest cart in that queue is removed once all of that cart's items have been processed.
  
  Although we are using a store checkout area as an application of queues, similar code could be used for other uses of queues. For example, instead of representing a cash register, a queue might represent a line of voters at a polling station, a segment of a freeway in a traffic simulation, or a collection of chemicals awaiting a reaction.
  
  DO THIS: Implement a file ~/PDC/hw2/Register.h that implements a class Register satisfying this Doxygen spec, and build an executable using Register.h, checkout.cpp, and Makefile that simulates a store's checkout area.
  
  Suggestions:
  - On a Link machine, create a subdirectory PDC/hw2 for your work on this homework, and copy the files checkout* and Makefile from /usr/local/cs/cs300/hw to your hw2 subdirectory.
```
% mkdir ~/PDC/hw2 
% cd !$
% cp /usr/local/cs/cs300/hw/{checkout*,Makefile} .
```
    (Don't overlook the final dot in that cp command.) Here the shell notation !$ refers to the final command-line argument in the previous command, which is ~/PDC/hw2 in this case, and the notation /usr/local/cs/cs300/hw/{checkout*,Makefile} (no spaces around commas) is a shell notation for
```
/usr/local/cs/cs300/hw/checkout* /usr/local/cs/cs300/hw/Makefile
```
  - The copied file checkout is an executable that results from a solution to this problem, and the text file checkout.out consists of the first 30 lines of output from a run of checkout, as an illustration. You can run checkout as follows:
```
% ./checkout | more
```
    Piping output to more (or less) isn't required, but displaying the output one page at a time prevents the simulation from scrolling through thousands of iterations before you can examine them.
  - Your task is to create a file Register.h that implements a class Register that is a FIFO (first-in, first-out) queue. A queue data structure contains zero or more objects (or values) of the same type, and supports operations to add a new element to the "end of the line," remove an element from the "beginning of the line," determine whether any elements exist in that queue, etc.
  - Implement the Register class that satisfies this spec. Register should be a subclass of the STL container queue<int>, a queue of int values. Each integer queue element will represent a count of items to be purchased in one shopping cart, among that Register's waiting line of carts.
    
    Note: In Software Design we always specified public access for superclasses, e.g.,
```
class OwnedDog : public Dog {
  ...
};
```
    This indicates a limit for the most accessible members inherited from that superclass Dog. But use private access for the superclass queue<int> of Register.
```
class Register : private queue<int> {
  ...
};
```
    The reasons for this access choice are technical: destructors of STL containers are not virtual, so applications involving multiple inheritance or deallocating through a pointer may be unsafe. The standard advice is not to use STL containers as superclasses, and to make containers available to algorithms using iterators. But we suggest simplifying this early assignment by using C++ private inheritance, which prevents the superclass queue<int> from factoring in multiple inheritance, and prevents unsafe deallocation of a Register through a pointer to a queue<int> superclass object.
    Terminology
    - base class: C++ term for a superclass.
    - derived class: C++ term for a subclass
  - The documentation for the STL queue container indicates the header file required to use queues near the upper right hand corner. Thus, be sure to enter
```
#include <queue>
```
    near the top of your file Register.h. Also, you must use std::queue to refer to an STL queue unless you enter a directive such as
```
using namespace std;
```
  - The spec for Register was generated by the Doxygen system (to be described later). Here are some comments about interpreting that spec.
    - The inheritance diagram section indicates that Register should be private subclass of std::queue<int>, i.e., "derived from the base class std::queue<int>". The red dotted arrow in that inheritance diagram indicates private access, which means that queue<int> members (e.g., methods) are accessible within the scope Register:: but not outside of that scope. A green dotted arrow indicates protected access to base-class members, and a solid blue arrow indicates public access.
    - The public member functions section lists the methods for Register. Clicking on the name of a method (or scrolling down the web page) provides details of the spec for each method.
      Terminology
      
      member function: C++ term for a method, operator, constructor, or destructor in a class
      
      data member: C++ term for a state variable.
    - The Attribute sections list the state variables, i.e., data members, expected for the Register class. Clicking on the name of a data member (or scrolling down) provides documentation of those members.
      
      These attribute sections show one per-instance state variable (data member) named remaining, and one class variable (static data member) called transact_time.
    - The detailed description of the Register class begins after these initial lists.
      - The detailed description section gives an overview of the class.
      - The member function documentation provides specs for each of the desired methods.
      - The "member data documentation" section describes each data member.
    - Here is an explanation of some of the state variables and methods:
      - This simulation of a store checkout area proceeds in iterations that each represent the passage of a certain amount of time.
      - Between iterations, an individual Register may have processed part, but not all, of the items in it's first cart. The data member remaining indicates how much more processing is (still) needed for the first shopping cart in in the queue for a particular Register.
      - The Register::push() method calls the queue<int>::push() method to add an integer (representing a cart) to the queue. But if we push() a cart onto to an empty queue, then the data member remaining also needs to be assigned the work needed to process that whole cart.
      - Time is measured in this simulation according to the number of items scanned at registers: one unit of time corresponds to scanning one item. The (static) data member transactTime is the amount of time added to each cart, representing the time to pay for scanned item and for the next cart to arrive for scanning. (Thus transactTime + i should be assigned to the data member remaining when a new cart containing i items arrives at the beginning of the queue.
      - Pseudocode is provided for the member function advanceTime(), which is at the heart of the simulation.
      - Note that we don't need to define a default constructor, copy constuctor, destructor, or assignment operator for Register since that class has no dynamically allocated state variables.
  - Comments on the main program for the simulation checkout.cpp:
    - The program defines a class CheckoutArea that contains an array of Register, and defines main() to use a CheckoutArea object to carry out the simulation.
    - The CheckoutArea class definition defines a default constructor, copy constructor, destructor, and assignment operator, since that class dynamically allocates memory (namely, the array reg[]). CheckoutArea also defines an index operator for convenient access to individual Registers in the array.
    - The constructor
```
  CheckoutArea(int sz = DFLT_REGISTERS) {
    ...
  }
```
      provides a default value DFLT_REGISTERS (defined earlier), so that constructor may be used with 0 or 1 argument. It thus serves as the default constructor for CheckoutArea when no argument is provided.
    - The member function CheckoutArea::advanceTime() primarily calls the advanceTime() method for each Register in its array.
    - The main program uses rand() to generate a random number of carts per simulation iteration, determine a random number of items per cart, and assign each cart to a randomly chosen Register within a CheckoutArea array. Then, it advances time by itemsPerIter units, and repeats.
    - The code provides for no exit from the simulation loop. (You will have to stop the program, for example, by entering CTRL-C.)
  - To compile and run your program, enter the shell commands
```
%  make checkout
%  ./checkout | more
```
    You can visually compare your first page of output to checkout.out. To compare character-by-character, enter the command
```
%  ./checkout | head -30 | diff - checkout.out
```
    Here, head -30 copies the first 30 lines (only) of standard input to standard output, and diff - checkout.out compares standard input to the file checkout.out, printing any differences it finds.
  - If you run the program without piping its output to more, head, etc., then you will have to enter CTRL-C to stop it.
2. [c]
  Make a commit of your code:
```
link%  git add checkout.cpp Makefile Register.h 
link%  git commit -m "hw2: Implement Register queue"
```
Submitting this homework