COS30008 Data Structures and
Patterns - Assignment 02 Data Structures and Patterns in C++
Table of Contents
MarkSheet Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Assignment Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Lab Exercises (20% in total, 10 Lab Exercises, 2% each). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ................................................. . . . . 2 Problem Sets (10% in total) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Conditional Compilation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Problem Set 3 Object Adapter with a Buffer (4%) ....................................... . . . . . 3 Problem Set 4 Priority Queue (6%) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Table 1. Modification History
MarkSheet Summary
Table 2. Marks for Assignment 2
Date (created / modified) Purposes
2022-08-10 Modified based on the work of Markus Lumpe mlumpe@swin.edu.au
2022-11-18 Finalize the assignment
Component Tasks Total Marks Student Marks Date Checked
Lab Exercises
Lab 07 2%
Lab 08 2%
Lab 09 2%
Lab 10 2%
Lab 11 2%
Lab 12 2%
Lab 13 2%
Lab 14 2%
Lab 15 2%
Lab 16 2%
Sub-Total 20%
1
Component Tasks Total Marks Student Marks Date Checked
Problem Sets
Problem Set 3 4%
Problem Set 4 6%
Sub-Total 10%
Total 30%
In Assignment 1, we have Problem Sets 1 and 2. In Assignment 2, we have Problem Sets 3 and 4 (the counting continues from Assignment 1.)
Assignment Overview
Assignment Deadline: 16 Dec 2022 (subject to change, please confirm this with your co-teacher)
Assignment Submission: Please discuss with your co-teacher about how and what to submit. This assignment has two components:
1. Lab Exercises (20% total) - 10 Lab Exercises from Lab 07 to Lab 16 - worth 2% each
2. Problem Sets (10% total) - 2 Problem Sets, extensions on selected Lab exercises (Labs 07 and 13)
Lab Exercises (20% in total, 10 Lab Exercises, 2% each)
1. Complete Labs 07 - 16 as per the instructions
2. Demo your work in the presence of your co-teacher for each Lab
Marking Criteria for Lab Exercises
Below is the marking criteria of each Lab exercise
a. Complete all work required (e.g. implement the solutions correctly and programs run correctly) - 2%
b. Partially complete the work required (e.g. partial solution and program have some minor errors) - 1%
c. Cannot complete the work required (e.g. program cannot compile) - 0%
Problem Sets (10% in total)
Problem Sets 3 and 4 are designed to extend your work on Labs 07 and 13, respectively. 2
1. Problem Set 3 (4%) extends your work on Lab 07. In Lab 07, we develop an object adapter pattern. Here, we extend the work so that the application can work on a buffer of bytes (e.g. 128 bytes) at a time.
2. Problem Set 4 (6%) extends your work on Lecture and Lab 13. In Lab 13, we deal with Stack and Queue. Here we extend our work so that we can handle Priority Queue.
Conditional Compilation
We will not be using conditional compilation in the following two Problem Sets.
Problem Set 3 Object Adapter with a Buffer (4%) Getting the files ready
1. Download and Expand A02_src_adapter.zip from Cloud Campus
This zip file contains the following three groups of files:
1. Header file: ofstream12.h
2. Create a project, named A2_Adapter (or Adapter, or something else of your choosing), either in Visual Studio (MS Windows) or Xcode (Mac OSX), depending on your machine
3. Add the following C++ files in the project first a. Main.cpp
b. ofstream12.h
c. ofstream12.cpp
Please be very careful in modifying any of these given files as instructed in the relevant tasks.
The new specification of class ofstream12
In order to add support for a larger buffer size of characters, we use the following revised
specification of class ofstream12 in ofstream12.h, which is shown below Revised specification of class ofstream12 [code segment]
// COS30008 SDUST, Assignment 2 Problem Set 3 Object Adapter, 2022
#pragma once
#include
2. CPP file: Main.cpp and ofstream12.cpp
3. Sample output files: mySample4096.lzw and mySample0171.lzw - for you to check your work
3
#define MAX_BITS 8
using byte = unsigned char;
class ofstream12
{
private:
std::ofstream fOStream;
// revised for A2
byte* fBuffer;
size_t fBufferSize;
size_t fByteIndex;
int fBitIndex;
void init();
index
void prepareOneByte();
void prepareBit0();
void prepareBit1();
void writeBuffer();
// output buffer
// output buffer size, default is 128
// current byte index, starts at 0
// current bit index (can be negative), starts at 0
// initialize buffer, buffer size, byte index and bit
// prepare one byte in the buffer
// store bit 0 to the appropriate byte in the buffer
// store bit 1 to the appropriate byte in the buffer
// output entire buffer
public:
// using C++11's nullptr
ofstream12(const char* aFileName = nullptr, size_t aBufferSize = 128);
~ofstream12();
void close();
bool good() const;
bool isOpen() const;
void flush();
ofstream12& operator<<(size_t aValue);
};
The implementation of the following methods have been given to you in ofstream12.cpp as is (Please do not modify these methods):
1. the constructor ofstream12() and the destructor ~ofstream12() methods 2. the isOpen() method
3. the prepareBit0() and prepareBit1() methods
4. the operator<<() method
4
What you need to do
1. Program the following six methods in ofstream12.cpp a. the good() method
This method checks whether the output stream is good for output. Which method in the std::ofstream class can help?
b. the init() method
This method initializes the characters stored in fBuffer to \0 (null character) and set the relevant byte index (fByteIndex) and bit index (fBitIndex) values.
c. the flush() method
This method flushes all remaining bytes and bits in the buffer to the output file.
d. the close() method
This method closes the output file. But, before the closing of the file, you need to flush all buffer out first.
e. the writeBuffer() method
2. Use the following code segment in your Main.cpp to test your solution Code segment in Main.cpp
void write4096(const char* aFilename)
{
cout << "Write 4096 codes from 4095 to 0" << endl;
ofstream12 lWriter(aFilename);
if (!lWriter.good())
{
cerr << "Error: Unable to open output file " << aFilename << " !" << endl;
exit(1);
This method writes the entire buffer to the output file. f. the prepareOneByte() method
This method prepares one complete byte in the buffer. When the buffer is full, you need to write the entire buffer (via writeBuffer()) to the output and reset all the buffer.
5
6
}
for (size_t i = 4096; i > 0; )
{
lWriter << --i;
}
}
void write0171(const char* aFilename)
{
cout << "Write 171 codes from 4095 to 3925" << endl;
ofstream12 lWriter(aFilename);
if (!lWriter.good())
{
cerr << "Error: Unable to open output file " << aFilename << " !" << endl;
exit(1); }
for (size_t i = 4096; i > 3925; )
{
lWriter << --i;
}
}
int main() {
write4096("sample4096.lzw");
write0171("sample0171.lzw");
cout << "SUCCESS" << endl;
return 0;
}
The outputs should be similar to the relevant files as shown below
Figure 1. Output in sample4096.lzw (the first few bytes)
Figure 2. Output in sample0171.lzw (all 257 bytes shown) Sample Output Files
There are two sample output files that you can use to check your solution: mySample4096.lzw and mySample0171.lzw.
1. The mySample4096.lzw is the same as your Lab 07’s standard output file. You can view this using any binary editor. It has 6144 (= 4096 * 12 / 8) bytes
2. The mySample0171.lzw is a new one. This is to check whether you are careful when there is some extra remaining bits that need to be output. For 171 12-bits, it is equivalent to 256.5 (= 171 x 12 / 8) 8-bits. This means that after two rounds of writeBuffer() assuming buffer size is 128, there are 4 remaining bits (0.5 bytes) in the system waiting to be output. It has 257 bytes. Remember,
7
we need to round 0.5 byte up to 1 byte.
Marking Criteria of Problem 3
Below is the marking criteria of Problem 3
a. Complete implementation of all six methods - 3% (0.5% each)
Award 1 to 2% if program cannot be compiled with some coding depending on the situation
b. Correct results as recorded in sample4096.lzw and sample0171.lzw - 1% (0.5% each)
Table 3. Marks for Problem Set 3
Assume the implementation can compile.
C++ Component Methods Total Marks Student Marks
ostream12.cpp
good()
0.5%
init()
0.5%
flush()
0.5%
close()
0.5%
writeBuffer()
0.5%
prepareOneByte()
0.5%
Execution Result
correct 1%
Total 4%
Problem Set 4 Priority Queue (6%) Getting the files ready
1. Download and Expand A02_src_priorityq.zip from Cloud Campus This zip file contains the following two groups of files:
1.Header file: PriorityQueue.h, SortedList.h, SinglyLinkedNode.h, SinglyLinkedListIterator.h, NoSuchElementException.h and Product.h
2. CPP file: Main.cpp and Product.cpp
2. Create a project, named A2_PriorityQ (or PriorityQ, or something else of your choosing), either
in Visual Studio (MS Windows) or Xcode (Mac OSX), depending on your machine
3. Add the following C++ files in the project first
a. Main.cpp
b. SinglyLinkedNode.h
8
c. SinglyLinkedListIterator.h d. NoSuchElementException.h e. SortedList.h
f. PriorityQueue.h g. Product.h
h. Product.cpp
The following UML class diagram shows the relations among Main, PriorityQueue, SortedList, SinglyLinkedNode, SinglyLinkedListIterator, Product and NoSuchElementException.
Please be very careful in modifying any of these given files as instructed in the relevant tasks.
NoSuchElementException -fMessage : string
+no_such_element_exception(string)
std::exception
+what() : char*
SortedList
-fHead : SinglyLinkedNode* -fCount : size_t
generics T
calls
generics T
SinglyLinkedNode
generics T
PriorityQueue -fElements : SortedList
-fData : T
-fNext : SinglyLinkedNode*
Main
calls
Product
-fProductId : string -fName : string -fQuantity : uint16_t -fPrice : double
calls
+PriorityQueue() +PriorityQueue(const PriorityQueue&) +~PriorityQueue()
+isEmpty() : bool
+size() : size_t
+enqueue(const T&)
+dequeue()
+top() : const T&
+SortedList()
+SortedList(const SortedListed&) +~SortedList();
+operator=(const SortedListed&) : SortedList& +isEmpty() : bool
+size() : size_t
+insert(const T&)
+remove(const T&)
+operator[](size_t) : const T&
+begin() : SinglyLinkedListIterator
+end() : SinglyLinkedListIterator
+SinglyLinkedNode(const T&, SinglyLinkedNode*) +getData() : const T&
+getNext() : SinglyLinkedNode* +insertBefore(SinglyLinkedNode*) : SinglyLinkedNode* +insertAtFirst(SinglyLinkedNode*) : SinglyLinkedNode* +insertAfter(SinglyLinkedNode*) +insertAtEnd(SinglyLinkedNode*) +deleteFirst(SinglyLinkedNode**) : SinglyLinkedNode* +deleteNext() : SinglyLinkedNode*
+deleteEnd() : SinglyLinkedNode*
+Product(string, string, uint16_t, double) +getProductId() : string
+getName() : string
+getQuantity() : uint16_t
+getPrice() : double +setProductId(string) +setName(string) +setQuantity(uint16_t) +setPrice(double) +operator<(const Product&) : bool +operator<=(const Product&) : bool +operator==(const Product&) : bool +operator!=(const Product&) : bool
SinglyLinkedListIterator
-fList : SinglyLinkedNode* -fIndex : SinglyLinkedNode*
generics T
+SinglyLinkedListIterator(const SinglyLinkedNode*) +operator*() : const T&
+operator++() : SinglyLinkedListIterator& +operator++(int) : SinglyLinkedListIterator +operator==(const SinglyLinkedListIterator&) : bool +operator!=(const SinglyLinkedListIterator&) : bool +begin() : SinglyLinkedListIterator
+end() : SinglyLinkedListIterator
Figure 3. UML Class Diagram relating Main, PriorityQueue, SortedList, SinglyLinkedNode, SinglyLinkedListIterator, Product and NoSuchElementException
What you need to do
In this Problem Set, you need to program the relevant methods in SortedList.h and PriorityQueue.h. As we are doing this using template class, you need to implement all methods before you can run the test code in Main.cpp.
In Lecture 13, we use the Pair