Fluent Essays

Need to do project in c++ #include <iostream> using namespace std; template <class T> class Entry { private: int row; int col; T value; public: Entry() { row = -1; col = -1; } Entry(int row, int col, T value) { this->row = row; this->col = col; this->value = value; } Entry(const Entry& other) { row = other.row; col = other.col; value = other.value; } Entry& operator=(const Entry& other) { row = other.row; col = other.col; value = other.value; return *this; } int getRow() { return row; } int getCol() { return col; } T getValue() { return value; } void setValue(T value) { this->value = value; } }; #include <exception> using namespace std; class NoSuchEntry : public exception { public: virtual const char* what() const throw() { return "No entry exists at this location"; } }; #include <iostream> #include "SparseMatrix.h" using namespace std; template <class T> void printState(const SparseMatrix<T>& matrix) { cout << matrix << endl; cout << "rows = " << matrix.getNumRows() << endl; cout << "cols = " << matrix.getNumCols() << endl; cout << "numEntries = " << matrix.getNumEntries() << endl; cout << endl; } int main() { cout << "Initial creation" << endl; SparseMatrix<int> matrix; printState(matrix); cout << "Fresh add" << endl; matrix.add(0, 0, 4); printState(matrix); cout << "Another fresh add" << endl; matrix.add(4, 1, 10); printState(matrix); cout << "One more fresh add" << endl; matrix.add(3, 5, 10); printState(matrix); cout << "Overwrite add" << endl; matrix.add(0, 0, 9); printState(matrix); cout << "Invalid remove" << endl; try { matrix.remove(1, 5); } catch (NoSuchEntry& e) { cout << e.what() << endl << endl; } cout << "Valid remove (last add)" << endl; matrix.remove(3, 5); printState(matrix); cout << "Valid remove (not last add)" << endl; matrix.remove(0, 0); printState(matrix); cout << "Copy constructor" << endl; SparseMatrix<int> copy1(matrix); cout << "Done with copy constructor" << endl; copy1.add(2, 1, 6); printState(copy1); printState(matrix); cout << "Assignment operator (fresh assignment)" << endl; SparseMatrix<int> copy2 = matrix; copy2.add(1, 1, 7); printState(copy2); printState(matrix); cout << "Assignment operator (overwriting assignment)" << endl; copy2 = matrix; copy2.add(2, 2, 9); printState(copy2); printState(matrix); cout << "Template" << endl; SparseMatrix<char> otherMatrix; otherMatrix.add(0, 0, 'A'); printState(otherMatrix); } #include <exception> #include <iostream> #include "Entry.h" #include "NoSuchEntry.h" using namespace std; template <class T> class SparseMatrix { private: Entry<T>** entries; int capacity; int size; public: SparseMatrix() { } SparseMatrix(const SparseMatrix& other) { } SparseMatrix& operator=(const SparseMatrix& other) { } ~SparseMatrix() { } void add(int row, int col, T value) { } void remove(int row, int col) { } T getValue(int row, int col) const { } int getNumEntries() const { } int getNumRows() const { } int getNumCols() const { } template <class U> friend ostream& operator<<(ostream& os, const SparseMatrix<U>& sm); }; template <class U> ostream& operator<<(ostream& os, const SparseMatrix<U>& sm) { } Initial creation rows = 0 cols = 0 numEntries = 0 Fresh add 4 rows = 1 cols = 1 numEntries = 1 Another fresh add 4 - - - - - - - - 10 rows = 5 cols = 2 numEntries = 2 One more fresh add 4 - - - - - - - - - - - - - - - - - - - - - - 10 - 10 - - - - rows = 5 cols = 6 numEntries = 3 Overwrite add 9 - - - - - - - - - - - - - - - - - - - - - - 10 - 10 - - - - rows = 5 cols = 6 numEntries = 3 Invalid remove No entry exists at this location Valid remove (last add) 9 - - - - - - - - 10 rows = 5 cols = 2 numEntries = 2 Valid remove (not last add) - - - - - - - - - 10 rows = 5 cols = 2 numEntries = 1 Copy constructor Done with copy constructor - - - - - 6 - - - 10 rows = 5 cols = 2 numEntries = 2 - - - - - - - - - 10 rows = 5 cols = 2 numEntries = 1 Assignment operator (fresh assignment) - - - 7 - - - - - 10 rows = 5 cols = 2 numEntries = 2 - - - - - - - - - 10 rows = 5 cols = 2 numEntries = 1 Assignment operator (overwriting assignment) - - - - - - - - 9 - - - - 10 - rows = 5 cols = 3 numEntries = 2 - - - - - - - - - 10 rows = 5 cols = 2 numEntries = 1 Template A rows = 1 cols = 1 numEntries = 1 CS 3100 – Data Structures and Algorithms Project #1 – Sparse Matrix Learning Objectives • Apply basic object-oriented programming concepts in C++ • Construct and use C++ objects making effective use of references and pointers • Implement an abstract data type conforming to specific design specifications Overview Your task for this assignment is to implement a “Sparse Matrix” data type. A matrix is a two- dimensional array. The term sparse means that most of the slots in the array are empty. A novice programmer might store this type of data structure by simply creating a two-dimensional array of the appropriate data type, but this would waste a lot of space since most of the memory allocated would not be holding any value due to the sparsity of the matrix. A much better implementation is to keep a list (either as an array or a linked list) of the non-empty slot. Entries can be represented as objects of an Entry class, that contains fields for the row and column of this entry in the sparse matrix, as well as its value. Since a data structure generally needs to be able to store values of any data type, the Entry class is a template. You have been provided with the code for this class on Pilot. You have given a SparseMatrix.h file with method prototypes for the sparse matrix (this is on Pilot). Your task is to implement the methods according to the following specifications. You may add any supplementary methods that you would like, but the only ones that are absolutely required are those already present in the file. You have been provided with a file called test.cpp, and the expected output (output.txt) to partially check you work. Please keep in mind that we will use a different test file when grading, so you might want to develop your own additional tests to make sure your implementation is robust. You can implement the sparse matrix using an array, a linked list, or any other data structure that you feel is appropriate. Because this is a data structures class, you need to design and implement the underlying data structure yourself. You may not, for example, use C++ standard template library vectors (or any other existing code) for the underlying data structure. Failure to follow this requirement will result in a zero on the project, so please contact me if you have any questions. The Sparse Matrix The sparse matrix data type will be implemented as follows: • Default constructor – creates a new sparse matrix that contains no entries • Copy constructor – creates an independent copy of the other sparse matrix • Assignment operator overload – creates an independent copy of the other sparse matrix without leaking any memory • Destructor – destroys the sparse matrix without leaking any memory • void add(int row, int col, T value) – adds the value to the specified row and column of the sparse matrix, overwriting an existing entry if one is already present at that location (without leaking any memory); there should be no limit on the number of entries that can be added, within the bounds of the available RAM • void remove(int row, int col) – clears the entry at the indicated row and column without leaking any memory; if there is no entry at the specified row and column, throw a NoSuchEntry exception (you have been provided with this class in the file NoSuchEntry.h on Pilot). • T getValue(int row, int col) – returns the value of the entry at the indicated row and column; throws a NoSuchEntry exception if there is no entry there. • int getNumRows() – returns the number of rows in the sparse matrix (i.e. the row of the largest entry in the matrix plus one) • int getNumCols() – returns the number of columns in the sparse matrix (i.e. the column of the largest entry in the matrix plus one) • int getNumEntries() – returns the number of non-empty elements in the sparse matrix • << operator overload – displays the sparse matrix as a two-dimensional array, with empty slots indicated by a hyphen Turn in and Grading Please implement your class in-line in the SparseMatrix.h file provided (do not make a separate .cpp file). Turn in any source code required to build and run your implementation. This likely includes SparseMatrix.h, Entry.h and NoSuchEntry.h. Do not turn in test.cpp. You may turn in your files either individually or zipped into a single file. Your project will be graded according to the following rubric. Each item is worth 10 points, for a total of 100. Projects that do not compile will receive a zero. Projects that use classes from the standard template library (STL) or any other existing library, such as the vector or list classes, will also receive a zero. You can create a sparse matrix of any data types and insert values into the matrix at new locations. Inserting a value into a sparse matrix where one is already present overwrites the old value and does not introduce a memory leak. The capacity of the sparse matrix is limited only by the amount of available RAM (note, there is no test for this in the driver program provided). You can remove an item from a specified row and column within the sparse matrix without introducing a memory leak; trying to remove an item from an empty location throws a NoSuchEntry exception. You can retrieve the value (via getValue) from a specified row and column within the sparse matrix; trying to get a value from an empty location throws a NoSuchEntry exception. The getNumRows, getNumCols and getNumEntries methods return accurate values, including for an empty sparse matrix. You can print sparse matrices to cout in the format specified in the requirements above using << A sparse matrix can be copied (using a copy constructor) resulting in a new, independent matrix with the same contents as the original matrix. A sparse matrix can be assigned (using =), resulting in a new, independent matrix with the same contents as the original matrix. This works for both initial assignments and re-assignments and does not introduce any memory leaks. Your code follows standard coding conventions, including consistent indentation and meaningful identifier names. Any tricky parts of the implementation are clearly commented. Your code does not print out any extraneous debugging information when it is run.