Lab 06 - Railroad (10/31/2022)

References

railroad.pptx

FAQ

Railroad FAQ, Valgrind

Files

Car.h, Station.h
Stack.h, Queue.h, Vector.h
DequeInterface.h, Deque.h

Description

Create a railroad train station that uses a central turntable and roundhouses to store and order train cars. Cars enter the train station if the turntable is empty. From the turntable cars can be moved to a "stack" roundhouse facility (LIFO) or a "queue" roundhouse facility (FIFO). Train cars exit the train station by moving from the turntable to a "vector" of outbound cars.

Learning Outcomes

By completing the Railroad Lab, you will be able to:

Discussion

The Deque

A deque (also called a double-ended queue) is an abstract data type that generalizes a queue, as elements can be added to or removed from either the front (head) or back (tail). There are two restricted type of deques as well:

The deque is an Abstract Data Type and can be implemented in two ways: contiguous and linked. A modified dynamic array that is contiguous and offers constant time (O(1)) operations.

The circular dynamic array approach uses a variant of an array that can grow from both ends These array deques have all the properties of a dynamic array, namely

  1. constant-time random access,
  2. good locality of reference,
  3. and amortized constant-time insertion/removal at both ends, instead of just one end.
They are, however, still inefficient (O(n)) with insertion and removal in the middle.

Circular Buffer

A deque can be implemented with a dynamic circular array. The array is resized when an item is added to the array and the array is full. This decreases the frequency of resizing’s and amortizes the cost over subsequent additions to the deque.

The C++ standard library defines the class std::deque to be a sequence that, like the std::vector, supports random-access iterators (not supported by either the stack or the queue) in addition to constant-time addition and removal from either end.

Adapter Design Patterns and Wrapper Classes

An adapter pattern converts the public face (interface) of a class into another public face (interface) that the client expects. Adapters let classes work together that have incompatible interfaces.

A real world example would be a USB to Ethernet adapter. We need this adapter when we have an Ethernet interface on one end and USB on the other. Since each has a different communication protocol, an adapter can convert one to the other.

A "wrapper class" is a de facto term meaning a class that "wraps around" a resource, such as another class. An adapter pattern is often implemented by a class (client) wrapping another class (server) and delegating or forwarding member functionality from the client to the server. In other words, delegation refers to evaluating a member (property or method) of one object (the client) in the context of another, original object (the server). In the simplest case, an object that simply uses another object is referred to as "aggregation".

The ADT deque class can be used to implement a vector, stack, or queue using an adapter design pattern. A vector class can wrap a deque class and use the deque's functionality to define the vector class' behavior. Although this approach has its strengths and weaknesses, it definitely simplifies implementation of the vector and enhances code reuse.

In this course, we have been discussing many of the underlying data structures that are used to implement data containers. The ADT deque class can be used to implement a vector, stack, or queue using an adapter pattern.

Consider the following:

#include "Deque.h"
template <typename T>
class myVector
{
private:
   Deque<T> vector_;
public:
   void push_back(T data)
   {
      vector_.push_back(data);
      return;
   }
   T& pop_back()
   {
      T temp = vector_.back();
      vector_.pop_back();
      return temp;
   }
   ...
};

The class myVector can easily be implemented by "wrapping" the Deque class and using the already-existing functions of the deque's underlying data structure, thus saving ourselves a lot of work. Wrapper classes are a very convenient use of abstraction, especially in rapid software development.

Of course, we should care about which type of underlying data structure a container uses and you will make design decisions based on those data structures. For example, a set implemented with a tree structure will have O(log(n)) find-time whereas a set implemented with a hash table will have a O(1) find-time. If find was the most critical function for your set, it would be more efficient to use a set class that wraps a hash table.

Vector

Train cars leaving the station turntable are pushed onto a vector wrapper class.

Queue

Train cars can be warehoused in a queue roundhouse. Cars move to and from the queue and the station turntable.

Stack

Train cars can be warehoused in a stack roundhouse. Cars move to and from the stack and the station turntable.

The Lab

The Station

The Railroad Station is a container facility for railroad cars. Central to the station is a turntable through which all station car movement occurs. The turntable is surrounded by two types of roundhouses: a stack house and a queue house. In addition, train cars exit the turntable to a vector house used to assemble the outgoing train.

Station Diagram

The following is a UML diagram of the station objects:

Station UML Diagram

Station Commands

  1. Add:station adds a train car (a struct containing a non­negative integer) to the station turntable. The car is added to the station turntable if the turntable is empty. Return "OK" if successful, else report an error.

  2. Remove:station removes the current car on the station turntable and adds the car to an outgoing vector assembly object. Return "OK" if successful, else report an error.

  3. Add:xxxx removes a car from the station turntable and adds to the designated data structure. Return an error if the turntable is empty, else "OK".

  4. Remove:xxxx removes a car the designated data structure and adds to the station turntable. Return an error if the turntable is occupied or the data structure is empty, else "OK".

  5. Top:xxxx displays the current "top" car in the designated data structure. Return an error if the data structure is empty. (Do not remove the car from the data structure.)

  6. Size:xxxx displays the number of cars in the station designated data structure.

  7. Find finds the current location of a car in the station data structures. Display the data structure name (or station, vector) and index if found, else error.

  8. Queue/Stack displays the cars in the station queue/stack roundhouse.

  9. Train displays the cars in the vector assembly object that have exited the Station.

Station Diagram

The following summarizes the commands used to direct railroad car traffic in and out of the railroad station:

COMMAND DESCRIPTION OUTPUT
Add:station <data>
Add:queue <data>
Add:stack <data>		 Train car enters the station turntable.
Train car is removed from the turntable and pushed to the Queue roundhouse.
Train car is removed from the turntable and pushed to the Stack roundhouse.		 OK
Turntable empty!
Turntable occupied!
Remove:station
Remove:queue
Remove:stack		 A train car is removed from the turntable and pushed into the train vector.
A train car is removed from Queue roundhouse and moved to the station turntable.
A train car is removed from Stack roundhouse and moved to the station turntable.		 OK
Turntable empty!
Turntable occupied!
Queue empty!
Stack empty!
Top:station
Top:queue
Top:stack		 Display the current train car on station turntable,
Display the train car at head of Queue roundhouse.
Display the train car at head of Stack roundhouse.		 <data>
Turntable empty!
Queue empty!
Stack empty!
Size:queue
Size:stack
Size:train		 Output number of train cars in Queue/Stack roundhouses and train vector. Size of Queue
Size of Stack
Size of Train
Queue
Stack
Train		 Display the contents of the station Queue roundhouse.
Display the contents of the station Stack roundhouse.
Display the contents of the train vector.		 List of train cars.
Find <data> Find and display the current location and position of a car in the station data structures (turntable, queue, stack, or vector). Turntable
Queue[<index>]
Stack[<index>]
Train[<index>]
Not Found!

Lab guidelines:

  1. You may NOT use any predefined data structures from the STL (vector, stack, queue, or deque.) (Don't inherit from an STL container class either!)

  2. Implement your deque with a single dynamic circular array (OR a dynamic circular array of pointers to multiple smaller fixed-size dynamically allocated arrays).

  3. Each data structure should be able to store any number of cars.

  4. A train car is a struct (Car) containing a non-negative integer.

  5. Instantiate your station template classes (and deque class) as type Car.

  6. A major objective of this lab is to give you practice with the principle of code reuse. After implementing your deque class, use a has-a pattern to implement your vector, stack, and queue.

Lab requirements:

  1. Your main program input/output files names come from argv[1] and argv[2], respectively.

  2. You are required to implement a deque template class that is derived from the DequeInterface class.

  3. You deque implementation uses a dynamic circular array (OR a modified dynamic circular array) and can store any number of items.

  4. Begin with a default array size and then double the size for each reallocation. 
    static const size_t DEFAULT_CAPACITY = 4;

  5. You are required to implement separate template classes for each data container in the station facility, (i.e. separate classes for vector, stack, and queue) by wrapping your template deque class.

  6. Each container will be of type Car.

  7. NO STL CONTAINERS MAY BE USED IN THIS LAB!

Steps to Success:

Helps and Hints

Car struct

  1. The train station cars are a struct and used to instantiate all containers and the turntable. Your Car struct might look something like the following: 

    struct Car
{
   unsigned int id;
   Car() : id(0) {}
   ~Car() {}

   bool operator==(const Car car) { return this->id == car.id; }
   bool operator!=(const Car car) { return this->id != car.id; }

   /** Return the Car as a string */
   string toString() const
   {
      stringstream out;
      out << id;
      return out.str();
   } // end toString()

     /** Make insertion operator friend for a Car */
   friend std::ostream& operator<< (ostream& os, const Car& c)
   {
      os << c.toString();
      return os;
   } // end operator<<
};

Circular Dynamic Arrays

  1. Begin with a default array size and then double the size for each reallocation. 

    static const size_t DEFAULT_CAPACITY = 4;

  2. Example Deque constructor: 

    Deque(void) :
   capacity(DEFAULT_CAPACITY),
   num_items(0),
   front_index(0),
   rear_index(DEFAULT_CAPACITY - 1),
   the_data(new T[DEFAULT_CAPACITY]) {}

Finding Memory Leaks.

  1. Place the following code near the beginning of the file containing your main function: 

    #ifdef _MSC_VER
#define _CRTDBG_MAP_ALLOC  
#include <crtdbg.h>
#define VS_MEM_CHECK _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#else
#define VS_MEM_CHECK
#endif

  2. Put the following C pre-processor macro at the beginning of your main code: 

    int main(int argc, char * argv[])
{
   VS_MEM_CHECK
   // Your program...
   return 0;
}

  3. If you get something like the following when your program exits, YOU HAVE A MEMORY LEAK! You are required to remove all memory leaks. 

    The thread 0x34bc has exited with code 0 (0x0).
Detected memory leaks!
Dumping objects ->
{149} normal block at 0x00365008, 4000 bytes long.
 Data: <                > 01 00 00 00 02 00 00 00 03 00 00 00 04 00 00 00 
Object dump complete.
The program '[4984] Lab 03 - Iterator (nested).exe' has exited with code 0 (0x0).

  4. Refer to this link for resolving memory leaks.

Understanding Valgrind Output.(collapse)

  • You can find helpful hints and explanations of Valgrind output here.

Railroad Criteria

Instructions for submitting your lab:

Use the following input and resulting output files in testing the Railroad lab. Content should match exactly (excluding white-space) to receive full credit. Remember, purposely submitting inaccurate peer reviews is dishonest.

Input FileOutput File
Test #1 lab06_in_01.txt lab06_out_01.txt
Test #2 lab06_in_02.txt lab06_out_02.txt
Test #3 lab06_in_03.txt lab06_out_03.txt
Test #4 lab06_in_04.txt lab06_out_04.txt
Test #5 lab06_in_05.txt lab06_out_05.txt

The auto-grader will be expecting to find in your output file the following sections:

Fail
Pass
 Score = 0

 

The lab source will be peer reviewed using the following rubric:

No
Partial
Yes
 Score = 0
Overall
Rating		 Easy to follow, readable, organized, and well commented.
                      
***NOTE: Any attempt to circumvent any lab requirement (ie, hard coding
output, using loops instead of iterators where required, modifying a class interface, etc.) will be reported by peer reviewers and result in a zero score for the lab.
Total Score = 0