Learning Objectives

With this assignment you will demonstrate:

• The ability to write and test functions and user-defined types in C, C++, and Rust. (I will supply the unit tests for you, but you will need to understand them and wire them into to your application.)
• The ability to employ manual memory management techniques in the development of a dynamic abstract data type in a systems programming language.
• An appreciation for Rust.

Readings and Videos

Please:

• Read Chapters 13 and 15 of Programming Language Explorations, 2nd edition.
• Locate and have handy reference material for C, C++, and Rust. Among the best sites are these for C, C++, and Rust.
• Review the course notes for C, C++, and References.

Instructions

Work in teams of 1 to 4 students.

Continue working on the repository you forked in Homework #1. Please remember that you should have only one official (graded) forked repository per group.

Implement the stack data type described below in C, C++, and Rust. A full suite of unit tests are provided for you, so your job is to write code that make the tests pass. As specified in the README file for the homework template repository linked above, your grade depends not only on (1) all tests passing, but a significant portion will also be based on (2) following instructions, (3) maintaining a clean repository, (4) code hygiene, and (5) following all formatting, indentation, naming, and styling conventions of the programming language.

To submit your work, choose one and only one team member to submit to BrightSpace a single text file containing (1) the names of all team members and (2) the URL of your private forked repository. Your homework submission will be the state of your repository on your main branch, at 18:00 in the America/Los Angeles time zone on the due date.

Code

In this assignment, you will be adding files for the three languages to implement a user defined data type for the famous Stack data structure. For C, you will build a stack of strings; for C++ and Rust your stack will be generic. In C and C++, you will build the stack with manually-managed array storage, resized by doubling the capacity when an attempt is made to add an element beyond the current capacity, and shrink when popping to a size below one-fourth of the current capacity. Stacks will have a maximum capacity and a minimum capacity, which is that same as the initial capacity, which will be 16. Do not exceed the capacity bounds when resizing. You are expected to follow best practices for information hiding, hiding not only the fields for your objects, but also your reallocation method(s). In Rust, we’ll keep things simple and require only that you wrap a Rust vector, which handles its own resizing.

Language-specific requirements are given in the subsections below.

C

You are given a stack specification in string_stack.h and a complete test suite in string_stack_test.c. Flesh out the file string_stack.c to implement the specification and pass the tests. Note the that the specification is based on returning ”response objects” for several of the operations—pay attention to the comments that explain their intent. Note that information hiding is scaffolded for you in the opaque type declared in string_stack.h.

Your code needs to be free of memory leaks. As these are hard to look for in unit tests, the teaching staff will run valgrind on your program to find them. You should learn valgrind too, if time allows.

C++

Because the stack abstract data type is implemented as a template, you will need to complete the missing code in the file stack.h. The specification is given in the completed portion of the file. Please note that templates do not have a separate compilation step, so you will not be creating a stack.cpp file. The test suite is in stack_test.cpp. Information hiding will be accomplished via private data members. Errors are handled through throwing exceptions.

Rust

For this assignment, your stack type will be a trivial wrapper around the Rust generic Vec type. As the type is so simple, the struct, the impl, and the tests will all be in one file, stack/src/lib.rs. Unlike your C and C++ solutions, you’ll be required to add a peek method. For operations that may fail, use optionals.

Grading

You will gain 25 points for each passing language test suite. The other 25 points are earned by precisely following all instructions, writing code that is built according to each language’s conventions, keeping a clean repository, etc. Your feedback will be in the form of deductions for such things as:

• Not following the indentation, capitalization, and spacing conventions of each language
• Extra or too few spaces
• Extra or too few blank lines
• Poor indentation
• Unreadable names
• Naming an entity in a way that has nothing to do with the variable’s purpose
• Defining variables that are never used
• Unnecessary or missing comments
• Data that is mutable when immutability is called for
• Lack of information hiding (to the extent allowed by the language)
• Failing to meet any explicitly specified implementation requirement, since not every requirement is captured by the unit tests!
• Code that is needlessly inefficient
• Code that does not properly manage resources, such as that which fails to release allocated memory or close open file handles
• Code that is too complex and fails to take advantage of the language features covered in class that are designed to facilitate the assigned task
• Extra files in the GitHub repository
• Not following submission instructions, for example not supplying the names of every group member or not providing the URL of your repository

This list is not exhaustive, but should help in getting you used to paying attention to your submissions and taking pride in your work. Note that most code editors have plugins that will auto-format your code and even look for suspicious coding practices. You are strongly encouraged to use them.