代写 C++ data structure graph Introduction

Introduction
ECE 2574: Project II Ryan M. Gerdes
rgerdes@vt.edu
Virginia Tech — 2019-10-02
In project two you will use the LCS class you completed in homework two to create a command-line program that displays the difference between two files.
1 diff
The principle of the diff program is used throughout computing: in patching source or binary code or record- ing the changes to files often we only care about the differences between two files. Consider the following scenario in which we both have copies of the same C++ source files. You make changes (fixing my bugs) and wish to send me the fixes. You could either send me the complete source (not efficient for large code bases) or a list of differences between your (fixed) code and my (buggy) code. This is the purpose of diff: determine which lines differ between two files and indicate the differences; i.e., tell me the changes I need to change my code into yours. The same principle works for binary files (e.g., consider a patch for a browser vulnera- bility: you don’t want to have to download an entire browser every time someone discovers a vulnerability in your browser. Rather, you’d like to download just the few hundred kilobytes that change from the vulnerable version to the patched version).
1.1 Input and Output of diff
The diff program takes two files, denoted by original and new, as input and as output (output) indicates which lines from original need to be deleted to produce new and which lines of new need to be added to original to produce new. Lines that need to be deleted from original are preceded by < while lines that need to be added from new are preceded by >. Consider Listing 1 for original and Listing 2 for new with Listing 3 as the output. The lines preceding the additions (>) and deletions (<) indicate, respectively, which lines of new need to be added to original and which lines of original need to be deleted from new. The letter a indicates add the following line(s) and the letter d indicates delete the following line(s). That is, for Listing 3 after line 0 of original add lines 1–6 of new; delete lines 10–14 of original; delete line 17 of original; add line 18 of new after line 17 of original; and after line 24 of original add lines 26–29 of new. 1 Listing 1: original 1 This part of the 1 2 document has stayed the 2 3 same from version to 3 10 11 This paragraph contains 11 12 text that is outdated. 12 13 It will be deleted in the13 14 near future. 14 15 15 16 It is important to spell 16 17 check this dokument. On 17 Listing 2: new This is an important notice! It should therefore be located at the beginning of this document! This part of the document has stayed the same from version to version. It shouldn ’t be shown if it doesn’t change. Otherwise, that would not be helping to compress the size of the changes. It is important to spell check this document. On the other hand , a misspelled word isn ’t the end of the world. Nothing in the rest of this paragraph needs to be changed. Things can be added after it. This paragraph contains important new additions to this document. Listing 3: output This is an important It shouldn ’t 4 if it doesn ’t 5 Otherwise , that 6 notice! It should therefore be located at the beginning of this document! 4 version. 5 be shown 6 change. 7 would not be helping to 7 8 compress the size of the 8 9 changes. 9 10 10 < This paragraph contains 11 < text that is outdated. hand , a 18 word isn ’t 19 the world. 20 the rest of 21 17 > check this document. On 18 24a26,29
19 >
20 >
18 the other
19 misspelled
20 the end of
21 Nothing in
22 this paragraph needs to 22
23 be changed. Things can 23
24 be added after it.} 24
21 > 22 >
This paragraph contains important new additions to this document.
25 26 27 28 29
1.2 diff and the LCS Problem
The diff program can be seen as an instance of the LCS problem where the objects are lines instead of characters in a string, as in homework two. That is, assume that the sequence X is equal to original and the sequence Y is equal to new. Calling the printDiff() method would produce:
+This is an important +notice! It should +therefore be located at +the beginning of this +document! + This part of the document has stayed the same from version to version. It shouldn’t be shown if it doesn ’t change. Otherwise , that would not be helping to compress the size of the changes. – -This paragraph contains -text that is outdated. -It will be deleted in the -near future. It is important to spell -check this dokument. On +check this document. On the other hand, a misspelled word isn’t the end of the world. Nothing in the rest of this paragraph needs to be changed. Things can be added after it. + +This paragraph contains +important new additions +to this document.
The only difference between printDiff() and diff is that the latter doesn’t show the common sequences between X and Y .
1.3 diff Requirements
You are to create a command-line program, diff, that takes three inputs: an original file, a new file, and
an output file. The output file will produce the diff between the original and new file according to the
2
1 0a1,6 2 >
3 >
4 >
5 >
6 >
7 >
8 10,14d 9 < 12 < 13 < 14 17d 15 < check this dokument. On 16 17 a18 It will be deleted in the near future. specification above. The basic usage is as follows: diff.exe

. See bsn_stl.cpp from Lecture 7 for an example of how to take input from the command line.
2 Supplementary Code
Given your LCS class, you need a way to access the lines of files using the operator[], the ability to add lines to files and files to files using the operator+, and a way to determine the number of lines (objects) in a file via length(). In addition, it might be helpful for the LCS class to indicate which lines needed to be added/deleted from a file to produce the diff output above.
2.1 A File Class
The class you are to implement will allow you to read and write lines from a file, as well as allowing you to
query (read) arbitrary lines from the file and add lines to the file. The class, named File, should support: • a constructor that will allocate a std::vector of size 100 to hold lines of the type std::string.
• a method to set an input file
• a method to read the lines of an input file
• a method to set an output file
• a method to write lines to an output file
• a method to return the number of lines in a file
• an operator+ (concatenation operator) to add a line (std::string) to a file (instructor provided) • an operator+ (concatenation operator) to add a file to a file (instructor provided)
• an operator[] (access operator) to access a line of a file (instructor provided)
• a method to print a file to std::cout (instructor provided)
2.2 getDiff() for LCS
While your original LCS would print the difference between two sequences, which would allow you to imple- ment diff, it wouldn’t be straightforward. Let’s supplement LCS with an additional public method, Diff getDiff(), which saves the output of printDiff() to a data structure that the diff program can easily parse. This function will return the diff between two sequences via the Diff structure:
template struct Diff
{
T d;
std::vector std::vector std::vector op;
};
Here d represents the lines that need to be added to/deleted from the original file to obtain the new file, while obj_ x and obj_ y indicate the lines of orignal and new (i,j in our sequences) that are to be added/deleted. op should be either std::string(“a”) for addition of a line or std::string(“d”) for a deletion of a line.
obj_x; obj_y;
3

i
Info: Let’s modify printDiff() for the addition operation. Originally you had:
else if(j > 0 && (i == 0 || C[i][j-1] >= C[i-1][j])) {
printDiff(i,j-1);
std::cout << "␣+" << Y[j-1]; } We could capture this using the Diff struct using: else if(j > 0 && (i == 0 || C[i][j-1] >= C[i-1][j])) {
getDiff(i,j-1);
//add // add // add //add
3 Testing
Y[j-1] to d
i to obj_x
j to obj_y std::string(“a”) to op
}
The correctness of your implementation will be partially based on it producing the correct output for a given orignal/new pair. An example has been provided for you to test against. Unit tests should be written for the File class and the revised LCS class (only the new method). When approaching the problem I would recommend the following tasks in the following order:
1. Write and test the File class
2. Extend the LCS class to support getDiff()
3. Plan out how File and LCS will be used in diff.cpp
4 Grader
After your have tested your code against the provided examples, you can use the grader to check your im- plementation against our tests. You should submit to the grader only after you’ve established that your code is able to the example. For this assignment you should upload a zip file containing only the files: file.hpp, file.cpp, lcs.hpp, lcs.txx, diff.cpp, and student_tests.cpp. There is a build target called “submission” configured by default to create this file with the correct contents in your build directory.
5 Submission
Once you are satisfied with your code, upload a zip file containing (only) file.hpp, file.cpp, lcs.hpp, lcs.txx, diff.cpp, and student_tests.cpp through Canvas at the assignment link. You should not submit the other files from the starter code, nor your build directory. There is a build target called “submission” configured by default to create this file with the correct contents in your build directory.
6 Grading
There are 60 points allocated to this assignment.
• Correctly submitting the required files: 2 points
4

• Your tests compile: 3 points
• Your tests pass: 15 points (proportional)
• Instructor tests compile with your code: 3 points
• Instructor tests pass: 25 points (proportional)
• No tests leak memory: 5 points
• Design requirements met (e.g., code and test quality, comments): 7 points
As per the syllabus, good faith efforts must be made to write comprehensive tests. Since there is no way to test for this at compile or run time (at this point), should the grader (person) deem your tests to be woefully lacking you will lose not only design points but also the points given by the autograder. Each method, excluding those written for you, should be tested and each test case should consist of multiple assertions.
5