CS250 Unit 09 Project: Smart Dynamic-Length Array

Table of Contents


1. Introduction

About
For this project we will be implementing a “smart” dynamic-length array.
Goals
  • Implement a basic data structure
  • Utilize our data structure in a simple program
Overview
  1. First, you'll implement the SmartDynamicArray data structure, following the doxygen documentation (or documentation in the comments) and the unit tests to verify your work.
  2. Second, in the Program.h file you'll change the m_products from using a std::vector to using your SmartDynamicArray instead. You will also replace the function calls in Program.cpp.
Starter code
https://gitlab.com/moosadee/courses/-/tree/main/wip_projects/starter_code/c4_u09_SmartDynamicArray?ref_type=heads
Doxygen documentation
doxygen/c4_u09_SmartDynamicArray/classDataStructure_1_1SmartDynamicArray.html]]

1.1. Getting started

1.1.1. Creating a new branch

BEFORE getting started on the assignment, make sure to go back to the main or master branch and pull latest. This way, you will have the most up-to-date version of your repository, and you'll be starting from a shared base-point.

  1. git add . && git commit -m "backup" && git push to make sure to backup any work on your current branch.
  2. git checkout main to check out the main branch again.
  3. git pull to pull latest changes from the server.

Next, you will create a new branch to get started from:

  1. git checkout -b SmartDynamicArray to create a new branch for this assignment.

1.1.2. Getting the starter code

Download the starter code for this assignment here:

https://gitlab.com/moosadee/courses/-/tree/main/wip_projects/starter_code/c4_u09_SmartDynamicArray?ref_type=heads

Extract the contents somewhere within your course repository folder.

The following files are already part of this directory:

.
├── CuTest
│   ├── LICENSE
│   ├── README.md
│   ├── TesterBase.cpp
│   └── TesterBase.h
├── Data
│   └── products.txt
├── DataStructure
│   ├── Interfaces
│   │   └── ILinearDataStructure.h
│   └── SmartDynamicArray
│       ├── SmartDynamicArray.h
│       └── SmartDynamicArrayTester.h
├── Doxyfile
├── Exceptions
│   ├── InvalidIndexException.h
│   ├── ItemNotFoundException.h
│   ├── NotImplementedException.h
│   ├── NullptrException.h
│   ├── StructureEmptyException.h
│   └── StructureFullException.h
├── main.cpp
├── Program
│   ├── Product.cpp
│   ├── Product.h
│   ├── Program.cpp
│   └── Program.h
├── Project_CodeBlocks
│   ├── DataStructures.cbp
│   ├── DataStructures.depend
│   └── DataStructures.layout
├── Project_VisualStudio2022
│   ├── DataStructures.sln
│   ├── DataStructures.vcxproj
│   ├── DataStructures.vcxproj.filters
│   ├── DataStructures.vcxproj.user
│   ├── log.html
│   └── test_result_smart_dynamic_array.html
└── Utilities
    ├── Logger.cpp
    ├── Logger.h
    ├── Menu.cpp
    ├── Menu.h
    ├── StringUtil.cpp
    ├── StringUtil.h
    └── Timer.h

CuTest
The unit test framework.
Data
The path where the products.txt file is.
DataStructure/Interfaces
Contains an interface for our Linear Data Structure type.
DataStructure/SmartDynamicArray
Contains the templated class declaration for the SmartDynamicArray as well as the unit tests in the Tester file.
Program
Contains the Product class and Program class.
Utilities
Various helper functionality like string/int conversion, menu stuff, etc.

There are a lot of files, but you will be focusing on SmartDynamicArray.h and Program.h and Program.cpp.

Additionally, a Visual Studio solution file is included in the Project_VisualStudio2022 folder, and a Code::Blocks project file is included in the Project_CodeBlocks folder.


2. Implementing the data structure

2.1. Opening the data structure documentation

To access the data structure's auto-generated documentation, go to this page:

doxygen/c4_u09_SmartDynamicArray/classDataStructure_1_1SmartDynamicArray.html

(All the documentation on the doxygen page is also written out in the data structure's comments.)

You can click on a function name to view the detailed notes about the structure and how to implement it. For future data structures assignments you will be heavily relying on the doxygen documentation rather than this type of manually created documentation page. (Hi!)


2.2. The important member variables!

There are three important variables that are part of the Smart Fixed-Length Array that you want to keep in mind while implementing everything:

  • T* m_array is the pointer that will be used to allocate space to become the array of data.
  • int m_arraySize is the total capacity of the array, which can change during runtime.
  • int m_itemCount is the amount of items currently stored in the array. This begins at 0.

2.3. Working with dynamic arrays and pointers

2.3.1. Allocating space for an array:

To allocate space for a dynamic array we need a pointer (in the project we'll be using m_array). We use the new keyword and specify a size while allocating space for the array.

T* somePointer = nullptr;

if ( somePointer == nullptr )
{
  somePointer = new T[ SIZE ];
}

2.3.2. Deallocating space for an array:

We need to amke sure that the array pointer is not pointing to nullptr. If it is pointing to some address, then we can free the memory with the delete function. When a pointer is not in use, we should be assigning the pointer to nullptr.

if ( somePointer != nullptr )
{
  delete [] somePointer;
  somePointer = nullptr;
}

2.3.3. "Resizing" a dynamic array:

To resize a dynamic array we need to do the following things:

  1. Create a new dynamic array with a new pointer, with a size of the bigger amount.
  2. Use a for loop to iterate over all the elements of the full array. Copy everything from the old array to the new array.
  3. After copying the array, free the memory at the old pointer with the delete [] command.
  4. Set the old array pointer to point to the same address as the new array pointer with an assignment statement: oldArrayPtr = newArrayPtr;
  5. Update your array size variable to have the larger size now.

2.4. Running the unit tests

There are unit tests already provided for the entire structure. Use these to validate your work. If all your unit tests pass (and the tester doesn't crash before the end ;) then you can assume that your data structure probably works correctly.

When you run the tests, the console will show a summary:

Running testset 14 out of 15: 	PushAt()
[FAIL] 0a. Check if function PushAt is implemented

Running testset 15 out of 15: 	Search()
[FAIL] 0. Check if function Search is implemented

- RESULTS ------------------------------------------------------------
- Total tests:           15
- Total tests passing:   0
- Total tests failing:   0
- 
- NOTE: CHECK "test_result_smart_fixed_array.html" in the directory --
(...)/Project_CodeBlocks
- - for full information on test results,
- including expected output vs. actual output and notes.

But to get the full summary of the tests, go to the test_result_smart_fixed_array.html file that gets generated - it will be located wherever your project file is.

c4_u08_SmartFixedArray_test-results.png

The HTML report will give you more detailed information, such as what the expected output was and what the actual output ended up being, as well as the inputs that were used. These can help you diagnose any logic errors with your code.


2.5. Smart Dynamic-Length Array functionality

Make sure to read through the textbook for an overview of this structure's functionality. This, the video lecture, plus the doxygen documentation should help you implement it.


3. Updating the program

3.1. Program overview

When you run the program it will prompt you on whether you want to run the unit tests or the program itself:

STARTUP
1. Run unit tests
2. Run program

>>

When you run the program there will be a list of products loaded in, as well as a menu with functionality for Add, Edit, and Delete products:

------------------------------------------------------------------------------
 | MAIN MENU |
 -------------

ID   NAME                                              PRICE     QUANTITY  
-----------------------------------------------------------------------------
0    Generic Micro USB Cable 3 pack                    $8.99     20        
1    Generic USB Wall Charger Adapter 5 pack           $14.99    50        
2    Earz Deluxe Wired Earbuds                         $27.99    10        
3    Blahgitech RGB Gaming Mouse                       $159.99   30        
4    Blahgitech RGB Gaming Keyboard                    $199.99   40        
5    Achoo 1080P HDR Gaming Monitor                    $399.99   100       
6    Generic Basic Mouse Pad, Black                    $10.87    20        
7    Generic Basic Mouse Pad, Red                      $10.87    15        
8    LAZOR Gaming Chair Professional Grade             $179.99   20        

OPTIONS
 0.	Quit
 1.	Add product
 2.	Edit product
 3.	Delete product

With our data structures, we will be implementing Push (add) functions, Get, and Pop (delete) functions. And, for each of these, we will need to be able to work with the front of the list, the back of the list, and the middle (some arbitrary index) of the list. At the moment, the Program class declaration in Program.h is storing a vector of Products:

std::vector<Product> m_products;

3.2. Testing the program

Use the unit tests to validate your work. All unit tests should pass.

Make sure the functionality of the Program also works.


Author: Rachel Wil Sha Singh

Created: 2023-11-02 Thu 23:07

Validate