book.cpp file

BookList Sequence Containers Homework Last updated: Friday, February 12, 2021 The following class diagrams should help you visualize the BookList interface, and to remind you what the Book interface looks like. Book class summary BookList class summary Book Clas: BookList Class 7 public author(): string (+ 1 overload) isbn) : string (+ 1 overload) 0 price(): double + 1 overload) title(): string(+1 overload) private e author : string isbn:string price: double _title: string public compare(): int find(): size_t insert:void(+1 overload) moveToTopl): void operator+=(): BookList& (+ 1 overload) removed] : void [+ 1 overload) size: size_t swap():void private _books_array: array books sulist_size): size_t Nested Types Book list function summaries: 1. Compare () returns a negative number if this book list is less than the other book list, zero if this book list is equal to the other book list, and a positive number if this book list is greater than the other book list. 2. find() takes a book as a parameter and returns the zero-based offset of that book, or the total number of books in the book list if the book was not found. For example, if your book list contains the books in the picture above, a request to find "East of Eden" returns 0, "The Good Earth" returns 5, and "Eat Pray Love" returns 48. 3. insert() takes a book and either a position (TOP or BOTTOM) or an offset into the list as parameters and inserts the provided book before the insertion point. For example, again if your book list contains the books in the picture above, inserting "Eat Pray Love" with an offset of 5 places "Eat Pray Love" between Anna Karenina" and "The Good Earth". Silently discard duplicate books from getting added to the book list. 4. moveToTop() takes a book as a parameter, locates and removes that book, and then places it at the top of the list. For example, a request to move "Les Mis to the top removes "Les Mis from its current location and places it before "East of Eden". Of course, "Hunger Games" would then immediately follow "A Tale of 2 Cities". The book list remains unchanged if the provided book is not in the book list. 5. operator+=() concatenates the provided book list to the bottom of this book list. Silently discard duplicate books during concatenation. 6. remove () takes either a book or a zero-based offset from the top as a parameter and removes that book from the book list. No change occurs if the given book is not in the book list, or the offset is past the size of the book list. For example, a request to remove "Les Mis" from your above pictured book list reduces the size of the book list by one and causes "Hunger Games" to immediately follow "A Tale of 2 Cities". 7. size () takes no parameters and returns the number of books in the book list. For example, the size of your above pictured book list is 48. The size of an empty book list is zero. 8. swap() exchanges one book list with another. CPSC 131, Data Structures - Spring 2021 Bettens Page 2 of 4 How to Proceed: The following sequence of steps are recommended to get started and eventually complete this assignment. 1. Review the solution to the last homework assignment. Use the posted solution to fix your solution and verify it now works. Your Book class needs to be working well before continuing with this assignment. Book's constructor's parameter order is important for this assignment. You must allow books to be constructed with at least zero, one, or two arguments. If one argument is given, it must be the title. If two arguments are given, the first one must be the title, and the second one must be the author. Take a close look at last assignment's posted solution and double check your books constructor's parameter order. When you're ready, replace the Book.cpp file stub packaged with this assignment with your updated Book.cpp file from last assignment. 2. Compile your program using Build.sh. There will likely be warnings, after all it's only partial solution at this point. If there are errors, solve those first. For example, implement books_sl_list_size() first to remove the "must return a value error. Your program should now execute. 3. Once you have an executable program, start implementing functions with the fewest dependencies and work up. Consider this order: books_si_list_size(), size (), insert(), find(), remove (), moveToTop (), and finally opertor+=(). 4. Implementing insert() and remove() is really implementing insert and remove on each of the four STL containers. For example, upon receipt of an "insert request, Booklist::insert() inserts the book into the_books_array, then into the _books_vector, then the_books_dl_list, and finally into the_books_sl_list. myBookist Booklist _books_array array _books_vector: std vector _books_dUlist siddist books_si_ist: std forward_list insertbook: const Book, offeetFrom Top 29_) void side array has no insert operation, so yu need to perform the equivalent operation yourself insert(position: Bookbook Book) Book insert position : Book, book: Book): Bock insert_afterposition Bookbook Book.): Book You may want to: a. Work the insert() and remove() functions together for arrays, then for vectors, lists, and finally forward_lists. Insertion and removal (or as the STL calls it, erasure) are very close complements of each other. b. While working insert and remove for each container, you may want to temporary turn off container consistency checking by commenting out those functions. But don't forget to uncomment them before you're finished. Rules and Constraints: 1. You are to modify only designated TO-DO sections. Do not modify or reformat anything outside such designated areas. Designated TO-DO sections are identified with the following comments: //// TO-DO (X) ///// END-TO-DO (X) // Keep these comments and insert your code between them. In this assignment, there are 17 such sections of code you are being asked to complete. 16 of them are in Booklist.cpp, and 1 in main.cpp. Hint: In many cases, the requested implementation requires only a single line of code. Of course, finding that single line is non-trivial. Most all can be implemented with less than 5 or 6 lines of code. If you are writing significantly more than that, you may have gone astray. Reminders: The C++ using directive using namespace std; is never allowed in any header or source file in any deliverable product. Being new to C++, you may have used this in the past. If you haven't done so already, it's now time to shed this crutch and fully decorate your identifiers. Always initialize your class's attributes, either with member initialization, within the constructor's initialization list, or both. Avoid assigning initial values within the body of constructors. Use Build.sh on Tuffix to compile and link your program. The grading tools use it, so if you want to know if you compile error and warning free (required to earn any credit) than you too should use it. Filenames are case sensitive on Linux operating systems, like Tuffix. You may redirect standard input from a text file, and you must redirect standard output to a text file named output.txt. Failure to include output.txt in your delivery indicates you were not able to execute your program and will be scored accordingly. A screenshot of your terminal window is not acceptable. See How to build and run your programs. Also see How to use command redirection under Linux if you are unfamiliar with command line redirection. . . Deliverable Artifacts: Provided files Files to deliver Book.hpp BookList.hpp 1. Book.hpp 2. BookList.hpp Book.cpp 3. Book.cpp main.cpp BookList.cpp 4. main.cpp 5. Booklist.cpp Comments You shall not modify these files. The grading process will overwrite whatever you deliver with the ones provided. It is important that you deliver complete solutions that compile clean, so don't omit these files in your delivery. Replace these provided file stubs with your (potentially) updated files from the previous assignment. Start with the files provide Make your changes in the designated TO-DO sections (only) and deliver with your final solution. The grading process will detect and reject all other changes. Capture your program's output to this text file and include it in your delivery. Failure to deliver this file indicates you could not get your program to execute. When you're far enough along and ready to have your classes regression tested, then place these files somewhere in your working directory and Build.sh will find them. Simply having these files in the directory (or sub directory) will add it to your program and run the tests - you do not need to #include anything or call any functions. These tests will be added to your delivery and executed during the grading process. A sample of a working program's output. Your output may vary. 6. output.txt BookListTests.cpp BookTests.cpp CheckResults.hpp sample_output.txt Book.hpp 1 #pragma once // include guard 2 13 14 15 16 17 18 19 20 21 22 23 24 25 3 #include 4 #include 5 #include 6 7 8 9 10 class Book 11 { 12 // Insertion and Extraction Operators friend std::ostream& operator>( std::istream& stream, Book & book ); // Relational Operators friend bool operator==( const Book & lhs, const Book & rhs ); friend bool operator ( const Book & lhs, const Book & rhs ); 53 bool operator>=( const Book & lhs, const Book & rhs ); 54 1 #include 2 #include 3 #include 4 #include // move() 5 #include // abs() 6 7 #include "Book.hpp" 8 9 namespace // unnamed, autonomous namespace 10 { 11 const double EPSILON = 1.0E-4; 12 } 13 14 // Constructors 15 Book:: Book( std::string_view title, 16 std::string_view author, 17 std::string_view isbn, 18 double price) 19 : _isbn (isbn), 20 _title (title), 21 _author(author), 22 _price (price) 23 {} 24 25 // Queries 26 std::string Book::isbn() const 27 { 28 return _isbn; 29 } 30 std::string Book::title() const 31 { 32 return _title; 33 } 34 std::string Book::author() const 35 { 36 return _author; 37 } 38 double Book :: price() const 39 { 40 return _price; 41 } 42 | 43 // Mutators 44 void Book::isbn(std::string_view newISBN) 45 { 46 _isbn = newISBN; 47 } 48 void Book::title(std::string_view newtitle) 49 { 50 _title = newTitle; 51 } 52 void Book::author(std::string_view newAuthor) 53 { 54 _author = newAuthor; 55 } 56 void Book::price(double newPrice) 57 { 58 _price = newPrice; 59 } 60 61 // Insertion Operator and Extraction Operators 62 std::ostream& operator>( std::istream & stream, Book & book ) 74 { 75 Book workingItem; 76 char delimiter = ', '; 81 83 91 77 78 stream >> std::quoted workingItem._isbn > >> delimiter 79 >> std::quoted workingItem._title ) >> delimiter 80 >> std::quoted workingItem._author ) >> delimiter >> workingItem._price; 82 if(stream) book = std::move (workingItem); 84 return stream; 85 } 86 87 // Relational Operators 88 bool operator==( const Book & lhs, const Book & rhs ) 89 { 90 return lhs._isbn == rhs._isbn && lhs._title rhs._title 92 && lhs._author == rhs._author 93 // lihs._price rhs._pricel = EPSILON) 106 return lhs._price ( const Book & lhs, const Book & rhs ) {return (rhs =( const Book & lhs, const Book & rhs ) {return !(lhs 2 #include 3 #include 4 #include "Book.hpp" 5 #include "Booklist.hpp" 6 namespace 7{ 8 void basicScenario) 9 { 10 // Let's start a book list 11 Booklist booksToRead = {{"Inviable Man" }, 12 {"Moby Dick" }, 13 {"Les Mis" }, 14 {"A Tale of Two Cities" }}; 15 16 // Changed my mind, I want to make sure I read Les Mis first so I'm going to move that to the top of my list 17 booksToRead.moveToTop( {"Les Mis"} );|| 18 // Let's see what's on the list so far 19 std::cout 3 #include // size t 4 #include 5 #include 6 #include 7 #include // domain_error, length_error, logic_error 8 #include 9 #include 10 #include "Book.hpp" 11 class Booklist 12 { 13 // Insertion and Extraction Operators 14 friend std::ostream& operator>( std::istream& stream, Booklist & booklist); 16 17 public: 18 // Types and Exceptions 19 enum class Position {TOP, BOTTOM}; 28 21 struct InvalidInternalState_Ex : std:: domain_error { using domain_error::domain_error; }; // Thrown if internal data structures become inconsistent with each other 22 struct CapacityExceeded Ex : std:: length error { using length error:: length error; }; // Thrown if more books are inserted than will fit 23 struct Invalidoffset Ex : std:: logic_error { using logic_error :: logic_error; }; // Thrown of inserting beyond current size 24 25 26 // Constructors, destructor, and assignment operators 27 BooklistO; // construct an empty book list 28 29 Booklist( const Booklist & other ); 11 construct a book list as a copy of another book list 38 Booklist Booklist 8& other); 1/ construct a book list by taking the contents of another book list 31 32 Booklist & operator=( Booklist rhs); // intentionally passed by value and not const ref 33 Booklist & operator=( Booklist && rhs); 34 35 Booklist ( const std::initializer_list & initlist); // constructs a book list from a braced list of books 36 Booklist & operator+= { const std::initializer list & rhs ); // concatenates a braced list of books to this list 37 Booklist & operator+={ const BookList & rhs ); // concatenates the rhs list to the end of this list 38 39 -BookList(); 40 // Queries 41 std::size_t size() const; 42 std::size_t find( const Book & book ) const; // returns the (zero-based) offset from top of list 43 // returns the (zero-based) position of the book, size() if book not found 44 // Mutators 45 void insert( const Book & book, Position position - Position:: TOP ); 11 add the book to the top (beginning) of the book list 46 void insert( const Book & book, std::size_t offsetFronTop ); // inserts before the existing book currently at that offset 47 48 void remove( const Book & book ); // no change occurs if book not found 49 void remove( std::size_t offsetFromTop ); 11 no change occurs if (zero-based) offsetFromTop >= size() 50 51 void moveToTop( const Book & book ); 52 53 void swap( Booklist & rhs ) noexcept; // exchange one book list with another 54 // Lexicographical Comparison 55 int compare( const Booklist & other ) const; // returns a negative number if this book list is less than the other book 56 1/ list, zero if this book list is equal to the other book list, and a 57 // positive number if this book list is greater than the other book list. 58 private: 59 // Helper functions 60 bool containersAreConsistant() const; 61 std::size_t books_si_list_size() const; // std::forward_list doesn't maintain size, so calculate it on demand 62 // Instance Attributes 63 std::size t books array_size - B; 11 std::array's size is constant so manage that attributes ourself 64 std:: array _books_array: 65 std::vector _books_vector; 66 std::list _books_di_list; 67 std:: forward_list _books_si_list; 68 ); 69 // Relational Operators 70 bool operator==const Booklist & ihs, const Booklist & rhs ); 71 bool operator!=( const Booklist & lhs, const Booklist & rhs ); 72 73 bool operators (const Booklist & lhs, const Booklist & rhs ); 74 bool operator ( const BookList & lhs, const Booklist & rhs); 76 bool operator>=( const Booklist & lhs, const Booklist & rhs ); 77 X Booklist.cpp 1 #include // find(), move(), move_backward(), equal(), swap(), lexicographical_compare() 2 #include // size_t 3 #include 4 #include // setwo 5 #include // distance(), next() 6 #include // logic_error 7 #include 8 #include "Book.hpp" 9 #include "BookList.hpp" 10 // As a rule, I strongly recommend avoiding macros, unless there is a compelling reason - this is such a case. This really does need 11 // to be a macro and not a function due to the way the preprocessor expands the source code location information. It's important to 12 // have these expanded where they are used, and not here. But I just can't bring myself to writing this, and getting it correct, 13 // everywhere it is used. Note: C++20 will change this technique with the introduction of the source_location class. Also note the 14 // usage of having the preprocessor concatenate two string literals separated only by whitespace. 15 #define exception_location " detected in function (*" std::string(_func_) + "\"" 16 " at line " + std::to_string( _LINE__) + 17 * in file ** FILE **** 18 / ***************************** 19** Private implementations, types, and objects 20 ************************************************* 21 bool Booklist::containersAreconsistant() const 22 { 23 // Sizes of all containers must be equal to each other 24 if( _books_array_size != _books_vector.size() 25 __books_array_size !- _books_di_list.size() 26 _books_array_size !- books_sl_list_size()) return false; 27 28 // Element content and order must be equal to each other 29 auto current_array_position - _books_array.cbegin(); 30 auto current_vector_position = _books_vector .cbegin(); 31 auto current_di_list_position = _books_di_list.cbegin(); 32 auto current_si_list_position = _books_51_list.cbegin(); 33 34 while( current_vector_position != _books_vector.cend()) 35 { 36 if( *current_array_position !- *current_vector_position 37 || *current_array_position 1= *current_di_list_position 38 || current_array_position != *current_si_list_position ) return false; 39 40 // Advance the iterators to the next element in unison 41 #current_array_position; 42 current_vector_position; 43 +*current_di_list_position; Hcurrent_si_list_position; 45 } 46 47 return true; 48} 49 // Calculate the size of the singly linked list on demand 50 std::size_t Booklist:: books_sl_list_size() const 51 { 52 IIIIIIIIIIIIIIIIIIIIIII TO-DO (1) SITTINTIIN 53 II/ Some implementations of a singly linked list maintain the size (number of elements in the list). std:: forward_list does 54 11/ not. The size of singly linked list must be calculated on demand by walking the list from beginning to end counting the 55 // number of elements visited. The STL's std::distance() function does that, or you can write your own loop. 56 IIIIIIIIIIIIIIIIIIIIII/ END-TO-DO (1) IIIIIIIIIIIIIIIIIIIIIIIIIIII 57 ) 58 ****** ************** ********* 59 - Constructors, destructor, and assignment operators 60 ************************************************************ ********** 61 // Rule of 6 - I wanted a tailored assignment operator, so I should (best practice) write the other too 62 Booklist::Booklist() =default; 63 64 Booklist::BookList( const Booklist & other ) - default; 65 Booklist::Booklist Booklist && other ) - default; 66 67 Booklist & Booklist::operator-( Booklist rhs) { swap( rhs ); return *this; } 68 BookList & Booklist::operator-( BookList && rhs ) - default; 69 70 Booklist::--Booklist) = default; 71 Booklist::BookList( const std::initializer_list & initlist ) 72 : _books_vector ( initList.begin(), initlist.end() ), 73 _books_di_list( initList.begin(), initList.end() ), 74 _books_51_list( initList.begin(), initList.end()) 75 { 76 // Unlike the other containers that are expandable, the array has a fixed capacity N. copy only the first N elements of the 77 // initialization list into the array. 78 for( auto p - initList.begin(); _books_array_size & rhs ) 84 { 85 IIIIIIIIIIIII TO-DO (2) VITAMIN 86 1/1 Concatenate the right hand side book list of books to this list by repeatedly inserting at the bottom of this book list. 87 II/ The input type is a container of books accessible with iterators like all the other containers. The constructor above gives 88 /// an example. Use BookList::insert to insert at the bottom. 44 88 /// an example. Use Booklist::insert to insert at the bottom. 89 MITTITTTTTTTTTTTT END-TO-DO (2) IIIIIIIIIIIIIIIIIIIIIIIIIIII 90 // Verify the internal book list state is still consistent amongst the four containers 91 if( ! containersAreConsistant()) throw Booklist:: InvalidInternalState_Ex( "Container consistency error" exception_location ); 92 return this; 93 } 94 BookList & Booklist::operator+-( const Booklist & rhs ) 95 { 96 MITTTTTTTTTTTTTTTTTTTTTTT TO-DO (3) MITTITTTIIIIIIIIIIIIIIIIII 97 111 Concatenate the right hand side book list of books to this list by repeatedly inserting at the bottom of this book list. 98 /// All the rhs containers (array, vector, list, and forward_list) contain the same information, so pick just one to traverse. 99 /// Walk the container you picked inserting its books to the bottom of this book list. Use Booklist::insert() to insert at the 100 /// bottom. 101 III END-TO-DO (3) / 102 // Verify the internal book list state is still consistent amongst the four containers 103 if( !containersAreConsistant()) throw Booklist:: Invalid InternalState_Ex( "Container consistency error" exception_location ); 104 return *this; 105) 106 /****** ***** 107 ** Queries 108 *************************** 109 std::size_t Booklist::size() const 118 { 111 // Verify the internal book list state is still consistent amongst the four containers 112 if( !containersAreConsistant()) throw Booklist:: InvalidInternalState_Ex( "Container consistency error" exception_location); 113 114 IIIIIIIIIIIIIIIIIIIIIIII TO-DO (4) //ITTTTTTTTTTTTTTTTTTTTTTTT 115 !!! All the containers are the same size, so pick one and return the size of that. Since the forward_list has to calculate the 116 Ill size on demand, stay away from using that one. 117 IIIIIIIIIIIIIIIIIIIIII END-TO-DO (4) MITTITIL 118 } 119 std::size_t Booklist::find( const Book & book) const 120 121 // Verify the internal book list state is still consistent amongst the four containers 122 if( ! containersAreconsistant()) throw Booklist:: InvalidInternalState_Ex("Container consistency error" exception_location ); 123 ////// TO-DO (5) /////////// 124 III Locate the book in this book list and return the zero-based position of that book. If the book does not exist, return the 125 Il size of this book list as an indicator the book does not exist. The book will be in the same position in all the containers 126 1/1 (array, vector, list, and forward_list) so pick just one of those to search. The STL provides the find function that is a 127 /// perfect fit here, but you may also write your own loop. 128 TIITTIMETTITITITI END-TO-DO (5) IIIIIIIIIIIIIIIIIII 129) 138 /*** 131 ** Mutators 132 *************************** ******/ 133 void Booklist::insert( const Book & book, Position position ) 134 { { 135 // Convert the TOP and BOTTOM enumerations to an offset and delegate the work 136 if (position -- Position:: TOP ) insert( book, @ ); 137 else if( position -- Position::BOTTOM) insert book, size() ); 138 else throw std::logic_error( "Unexpected insertion position" exception_location); // Programmer error. Should never hit this! 139} 140 void Booklist::insert( const Book & book, std::size_t offsetFrom Top ) // insert new book at offsetFromTop, which places it before the current book at offsetFronTop 141 142 // Validate offset parameter before attempting the insertion. std::size_t is an unsigned type, so no need to check for negative 143 // offsets, and an offset equal to the size of the list says to insert at the end (bottom) of the list. Anything greater than the 144 // current size is an error. 145 if( offsetFromTop > size()) throw Invalidoffset_Ex( "Insertion position beyond end of current list size" exception_location ); 146 /********** Prevent duplicate entries ***********************/ 147 ATTITITI TO-DO (6) ATTILIITTTTTTTTTTTTTTTTT 148 11/ Silently discard duplicate items from getting added to the book list. If the to-be-inserted book is already in the list, 149 1/1 simply return. 150 WIIIIIEND-TO-DO (6) // 151 // Inserting into the book list means you insert the book into each of the containers (array, vector, list, and forward_list). 152 // Because the data structure concept is different for each container, the way a book gets inserted is a little different for 153 // each. You are to insert the book into each container such that the ordering of all the containers is the same. A check is 154 // made at the end of this function to verify the contents of all four containers are indeed the same. 155 /********** Insert into array ***********************/ 156 { 157 IIIIIIIIIIIIIIIIIIIIIII TO-DO (7) IIIIIIIIIIIIIIIIIIIIIIIIIIIIII 158 /// Unlike the other containers, std:: array has no insert() function, so you have to write it yourself. Insert into the array 159 /// by shifting all the items at and after the insertion point (offsetFromTop) to the right opening a gap in the array that 160 1/1 can be populated with the given book. Remember that arrays have fixed capacity and cannot grow, so make sure there is 161 /// room in the array for another book before you start by verifying _books_array_size is less than _books_array.size(). If 162 /// not, throw CapacityExceeded_ex. Also remembe Also remember that you must keep track of the number of valid books in your array, so 163 /// don't forget to adjust _books_array_size. 164 165 /// open a hole to insert new book by shifting to the right everything at and after the insertion point. 166 /// For example: a[8] - a[7]; a[7] - a[6]; a[6] - a[5]; and so on. 167 1/1 std::move_backward will be helpful, or write your own loop. 168 169 /// See function FixedVector::insert() in FixedVector.hpp in our Sequence Container Implementation Examples, and 170 /// RationalArray::insert() in RationalArray.cpp in our Rational Number Case Study examples. 171 IIIIIIIIIIIIIIIIIIIIIII END-TO-DO (7) IIIIIIIIIIIIIIIIIIIIIIIIIII 172 } // Insert into array 173 /********** Insert into vector 174 { { 174 175 ATTIVITITTI TO-DO (8) IITTITTINTI 176 /// The vector STL container std::vector has an insert function, which can be directly used here. But that function takes a 177 /// pointer (or more accurately, an iterator) that points to the book to insert before. You need to convert the zero-based 178 /// offset from the top to an iterator by advancing _books_vector.begin() offsetFromTop times. The STL has a function called 179 /// std::next that does that, or you can use simple pointer arithmetic to calculate it. 180 181 /// Behind the scenes, std::vector::insert() shifts to the right everything at and after the insertion point, just like you 182 /// did for the array above. 183 MITTITTTTTTTTTTTIIIEND-TO-DO (8) //TITTIT, 184 } // Insert into vector 185 * /********** Insert into doubly linked list **********/ 186 { 187 IIIIIIIIIIIIIIIIIIIIIIIII TO-DO (9) IIIIIIIIIIIIIIIIIIIIIIIIIIIIII 188 II/ The doubly linked list STL container std::list has an insert function, which can be directly used here. But that function 189 /// takes a pointer (or more accurately, an iterator) that points to the book to insert before. You need to convert the 190 11/ zero-based offset from the top to an iterator by advancing _books_di_list.begin() offsetFromTop times. The STL has a 191 /// function called std:: next() that does that, or you can write your own loop. 192 IIIIIIIIIIIIIIIIIIIIII/ END-TO-DO (9) TIL -TIIT 193 } // Insert into doubly linked list 194 /********** Insert into singly linked list **********/ 195 { 196 VIII/ TO-DO (10) 11/11/ 197 /// The singly linked list STL container std:: forward_list has an insert function, which can be directly used here. But that 198 /// function inserts AFTER the book pointed to, not before like the other containers. A singly linked list cannot look 199 /// backwards, only forward. You need to convert the zero-based offset from the top to an iterator by advancing 280 111 _books_si_list.before_begin offsetFromTop times. The STL has a function called std:: next that does that, or you can 201 /// write your own loop. 202 IIIIIIIIIIIIIIIIIIII END-TO-DO (10) IIIIIII 293 } // Insert into singly linked list 294 // Verify the internal book list state is still consistent amongst the four containers 285 if( !containersAreConsistant()) throw Booklist:: Invalid InternalState_Ex("Container consistency error" exception_location); 206 } // insert( const Book & book, std::size_t offsetFromTop ) 287 void Booklist::remove( const Book & book) 288 { 299 remove( find(book)); 218 ) 211 void Booklist: :remove( std::size_t offsetFromTop ) 212 { 213 // Removing from the book list means you remove the book from each of the containers (array, vector, list, and forward_list). 214 // Because the data structure concept is different for each container, the way an book gets removed is a little different for 215 // each. You are to remove the book from each container such that the ordering of all the containers is the same. A check is 216 // made at the end of this function to verify the contents of all four containers are indeed the same. 217 if( offsetFromTop >= size()) return; // no change occurs if (zero-based) offsetFromTop >= size() 218 /********** Remove fron array ****** ********** / 219 { 220 MWILI I TO-DO (11) MILITI 221 /// Close the hole created by shifting to the left everything at and after the remove point. 222 /// For example: a[5] = a[6]; a[6] = a[7]; a[7] = a[8]; and so on 223 224 1/1 std::move() will be helpful, or write your own loop. Also remember that you must keep track of the number of valid books 225 111 in your array, so don't forget to adjust _books_array_size. 226 /// 227 /// See function FixedVector::erase() in FixedVector.hpp in our Sequence Container Implementation Examples, and 228 /// RationalArray: :remove() in RationalArray.cpp in our Rational Number Case Study examples. 229 LITTIIIIIIIIIIII/ END-TO-DO (11) ITIL 230 } // Remove from array 231 /********** Remove from vector ****** ***********/ 232 { 233 ///////// TO-DO (12) 1/1/1/// 234 /// The vector STL container std::vector has an erase function, which can be directly used here. But that function takes a 235 111 pointer (or more accurately, an iterator) that points to the book to be removed. You need to convert the zero-based 236 /// offset from the top to an iterator by advancing _books_vector.begin() offsetFromTop times. The STL has a function called 237 111 std::next() that does that, or you can use simple pointer arithmetic to calculate it. 238 /// 239 /// Behind the scenes, std::vector::erase() shifts to the left everything after the insertion point, just like you did for the 240 /// array above. 241 IIIIIII/ END-TO-DO (12) 242 } // Remove from vector 243 / /********** Remove from doubly linked list **********/ 244 { 245 IIIIIIIIIIIIIIIIIIIIIIII/ TO-DO (13) 111111111 246 /// The doubly linked list STL container std::list has an erase function, which can be directly used here. But that function 247 /// takes a pointer (or more accurately, an iterator) that points to the book to remove. You need to convert the zero-based 248 /// offset from the top to an iterator by advancing _books_dl_list.begin() offsetFromTop times. The STL has a function called 249 /// std:: next that does that, or you can write your own loop. 250 /////////////////////// END-TO-DO (13) ////////// 251 } // Remove from doubly linked list 252 /********** Remove from singly linked list **********/ 253 { { 254 III TO-DO (14) III But that 255 /// The singly linked list STL container std::forward_list has an erase function, which can be directly used here. 256 /// function erases AFTER the book pointed to, not the one pointed to like the other containers. A singly linked list cannot 257 111 look backwards, only forward. You need to convert the zero-based offset from the top to an iterator by advancing 258 111 _books_sl_list.before_begin() offsetFromTop times. The STL has a function called std:: next() that does that, or you can 259 /// write your own loop. 260 M ) 11/ END-TO-DO (14) ///////// 261 } // Remove from singly linked list 261 } // Remove from singly linked list 262 // Verify the internal book list state is still consistent amongst the four containers 263 if( ! containersAreConsistant()) throw Booklist:: InvalidInternalState_Ex( "Container consistency error" exception_location); 264 } // remove( std::size_t offsetFromTop ) 265 void Booklist::moveToTop( const Book & book ) 266 { 267 LIITTITILLITI TILTI TO-DO (15) ULTIMIIIIIIIIIIIIII 268 III If the book exists, then remove and reinsert it. Else do nothing. Use Booklist::find to determine if the book exists in 269 /// this book list. 270 UTTI END-TO-DO (15) WIL 271 } 272 void Booklist::swap( Booklist & rhs ) noexcept 273 { 274 if( this == &rhs ) return; 275 _books_array.swap( rhs. _books_array 276 _books_vector .swap( rhs._books_vector ); 277 _books_di_list.swap( rhs._books_di_list ); 278 _books_si_list.swap( rhs._books_51_list ); 279 std::swap( _books_array_size, rhs._books_array_size ); 280 } 281 /*: 282 ** Insertion and Extraction Operators 283 ********************************************* ******* 284 std::ostream& operator>( std::istream& stream, Booklist & booklist ) 293 { 294 if( ! booklist.containersAreConsistant() ) throw Booklist:: Invalid InternalState_Ex( "Container consistency error" exception_location ); 295 for( Book book; stream >> book; ) booklist.insert( book, Booklist::Position:: BOTTOM ); 296 return stream; 297 } 298 /** 299 ** Relational Operators 300 *************************** 301 int Booklist::compare( const Booklist & other ) const 302 { 303 if( !containersAreConsistant() || !other.containersAreConsistant()) throw Booklist:: InvalidInternalstate_Ex( "Container consistency error" exception_location); 304 Win TO-DO (16) W 305 III Compare this Booklist object with the other Booklist object. Return a negative number if this Booklist object is less than 306 III the other Booklist object, zero if this Booklist object is equal to the other Booklist object, and a positive number if this 307 II/ Booklist object is greater than the other Booklist object. 308 309 III Compare the size of the two Booklist objects first. If the sizes are different, you have your answer: if size() ( const Booklist & lhs, const Booklist & rhs ) { return lhs.compare( rhs) > 0; } 321 bool operator>=( const BookList & lhs, const BookList & rhs ) { return lhs.compare( rhs ) >= 0; } 322 BookList Sequence Containers Homework Last updated: Friday, February 12, 2021 The following class diagrams should help you visualize the BookList interface, and to remind you what the Book interface looks like. Book class summary BookList class summary Book Clas: BookList Class 7 public author(): string (+ 1 overload) isbn) : string (+ 1 overload) 0 price(): double + 1 overload) title(): string(+1 overload) private e author : string isbn:string price: double _title: string public compare(): int find(): size_t insert:void(+1 overload) moveToTopl): void operator+=(): BookList& (+ 1 overload) removed] : void [+ 1 overload) size: size_t swap():void private _books_array: array books sulist_size): size_t Nested Types Book list function summaries: 1. Compare () returns a negative number if this book list is less than the other book list, zero if this book list is equal to the other book list, and a positive number if this book list is greater than the other book list. 2. find() takes a book as a parameter and returns the zero-based offset of that book, or the total number of books in the book list if the book was not found. For example, if your book list contains the books in the picture above, a request to find "East of Eden" returns 0, "The Good Earth" returns 5, and "Eat Pray Love" returns 48. 3. insert() takes a book and either a position (TOP or BOTTOM) or an offset into the list as parameters and inserts the provided book before the insertion point. For example, again if your book list contains the books in the picture above, inserting "Eat Pray Love" with an offset of 5 places "Eat Pray Love" between Anna Karenina" and "The Good Earth". Silently discard duplicate books from getting added to the book list. 4. moveToTop() takes a book as a parameter, locates and removes that book, and then places it at the top of the list. For example, a request to move "Les Mis to the top removes "Les Mis from its current location and places it before "East of Eden". Of course, "Hunger Games" would then immediately follow "A Tale of 2 Cities". The book list remains unchanged if the provided book is not in the book list. 5. operator+=() concatenates the provided book list to the bottom of this book list. Silently discard duplicate books during concatenation. 6. remove () takes either a book or a zero-based offset from the top as a parameter and removes that book from the book list. No change occurs if the given book is not in the book list, or the offset is past the size of the book list. For example, a request to remove "Les Mis" from your above pictured book list reduces the size of the book list by one and causes "Hunger Games" to immediately follow "A Tale of 2 Cities". 7. size () takes no parameters and returns the number of books in the book list. For example, the size of your above pictured book list is 48. The size of an empty book list is zero. 8. swap() exchanges one book list with another. CPSC 131, Data Structures - Spring 2021 Bettens Page 2 of 4 How to Proceed: The following sequence of steps are recommended to get started and eventually complete this assignment. 1. Review the solution to the last homework assignment. Use the posted solution to fix your solution and verify it now works. Your Book class needs to be working well before continuing with this assignment. Book's constructor's parameter order is important for this assignment. You must allow books to be constructed with at least zero, one, or two arguments. If one argument is given, it must be the title. If two arguments are given, the first one must be the title, and the second one must be the author. Take a close look at last assignment's posted solution and double check your books constructor's parameter order. When you're ready, replace the Book.cpp file stub packaged with this assignment with your updated Book.cpp file from last assignment. 2. Compile your program using Build.sh. There will likely be warnings, after all it's only partial solution at this point. If there are errors, solve those first. For example, implement books_sl_list_size() first to remove the "must return a value error. Your program should now execute. 3. Once you have an executable program, start implementing functions with the fewest dependencies and work up. Consider this order: books_si_list_size(), size (), insert(), find(), remove (), moveToTop (), and finally opertor+=(). 4. Implementing insert() and remove() is really implementing insert and remove on each of the four STL containers. For example, upon receipt of an "insert request, Booklist::insert() inserts the book into the_books_array, then into the _books_vector, then the_books_dl_list, and finally into the_books_sl_list. myBookist Booklist _books_array array _books_vector: std vector _books_dUlist siddist books_si_ist: std forward_list insertbook: const Book, offeetFrom Top 29_) void side array has no insert operation, so yu need to perform the equivalent operation yourself insert(position: Bookbook Book) Book insert position : Book, book: Book): Bock insert_afterposition Bookbook Book.): Book You may want to: a. Work the insert() and remove() functions together for arrays, then for vectors, lists, and finally forward_lists. Insertion and removal (or as the STL calls it, erasure) are very close complements of each other. b. While working insert and remove for each container, you may want to temporary turn off container consistency checking by commenting out those functions. But don't forget to uncomment them before you're finished. Rules and Constraints: 1. You are to modify only designated TO-DO sections. Do not modify or reformat anything outside such designated areas. Designated TO-DO sections are identified with the following comments: //// TO-DO (X) ///// END-TO-DO (X) // Keep these comments and insert your code between them. In this assignment, there are 17 such sections of code you are being asked to complete. 16 of them are in Booklist.cpp, and 1 in main.cpp. Hint: In many cases, the requested implementation requires only a single line of code. Of course, finding that single line is non-trivial. Most all can be implemented with less than 5 or 6 lines of code. If you are writing significantly more than that, you may have gone astray. Reminders: The C++ using directive using namespace std; is never allowed in any header or source file in any deliverable product. Being new to C++, you may have used this in the past. If you haven't done so already, it's now time to shed this crutch and fully decorate your identifiers. Always initialize your class's attributes, either with member initialization, within the constructor's initialization list, or both. Avoid assigning initial values within the body of constructors. Use Build.sh on Tuffix to compile and link your program. The grading tools use it, so if you want to know if you compile error and warning free (required to earn any credit) than you too should use it. Filenames are case sensitive on Linux operating systems, like Tuffix. You may redirect standard input from a text file, and you must redirect standard output to a text file named output.txt. Failure to include output.txt in your delivery indicates you were not able to execute your program and will be scored accordingly. A screenshot of your terminal window is not acceptable. See How to build and run your programs. Also see How to use command redirection under Linux if you are unfamiliar with command line redirection. . . Deliverable Artifacts: Provided files Files to deliver Book.hpp BookList.hpp 1. Book.hpp 2. BookList.hpp Book.cpp 3. Book.cpp main.cpp BookList.cpp 4. main.cpp 5. Booklist.cpp Comments You shall not modify these files. The grading process will overwrite whatever you deliver with the ones provided. It is important that you deliver complete solutions that compile clean, so don't omit these files in your delivery. Replace these provided file stubs with your (potentially) updated files from the previous assignment. Start with the files provide Make your changes in the designated TO-DO sections (only) and deliver with your final solution. The grading process will detect and reject all other changes. Capture your program's output to this text file and include it in your delivery. Failure to deliver this file indicates you could not get your program to execute. When you're far enough along and ready to have your classes regression tested, then place these files somewhere in your working directory and Build.sh will find them. Simply having these files in the directory (or sub directory) will add it to your program and run the tests - you do not need to #include anything or call any functions. These tests will be added to your delivery and executed during the grading process. A sample of a working program's output. Your output may vary. 6. output.txt BookListTests.cpp BookTests.cpp CheckResults.hpp sample_output.txt Book.hpp 1 #pragma once // include guard 2 13 14 15 16 17 18 19 20 21 22 23 24 25 3 #include 4 #include 5 #include 6 7 8 9 10 class Book 11 { 12 // Insertion and Extraction Operators friend std::ostream& operator>( std::istream& stream, Book & book ); // Relational Operators friend bool operator==( const Book & lhs, const Book & rhs ); friend bool operator ( const Book & lhs, const Book & rhs ); 53 bool operator>=( const Book & lhs, const Book & rhs ); 54 1 #include 2 #include 3 #include 4 #include // move() 5 #include // abs() 6 7 #include "Book.hpp" 8 9 namespace // unnamed, autonomous namespace 10 { 11 const double EPSILON = 1.0E-4; 12 } 13 14 // Constructors 15 Book:: Book( std::string_view title, 16 std::string_view author, 17 std::string_view isbn, 18 double price) 19 : _isbn (isbn), 20 _title (title), 21 _author(author), 22 _price (price) 23 {} 24 25 // Queries 26 std::string Book::isbn() const 27 { 28 return _isbn; 29 } 30 std::string Book::title() const 31 { 32 return _title; 33 } 34 std::string Book::author() const 35 { 36 return _author; 37 } 38 double Book :: price() const 39 { 40 return _price; 41 } 42 | 43 // Mutators 44 void Book::isbn(std::string_view newISBN) 45 { 46 _isbn = newISBN; 47 } 48 void Book::title(std::string_view newtitle) 49 { 50 _title = newTitle; 51 } 52 void Book::author(std::string_view newAuthor) 53 { 54 _author = newAuthor; 55 } 56 void Book::price(double newPrice) 57 { 58 _price = newPrice; 59 } 60 61 // Insertion Operator and Extraction Operators 62 std::ostream& operator>( std::istream & stream, Book & book ) 74 { 75 Book workingItem; 76 char delimiter = ', '; 81 83 91 77 78 stream >> std::quoted workingItem._isbn > >> delimiter 79 >> std::quoted workingItem._title ) >> delimiter 80 >> std::quoted workingItem._author ) >> delimiter >> workingItem._price; 82 if(stream) book = std::move (workingItem); 84 return stream; 85 } 86 87 // Relational Operators 88 bool operator==( const Book & lhs, const Book & rhs ) 89 { 90 return lhs._isbn == rhs._isbn && lhs._title rhs._title 92 && lhs._author == rhs._author 93 // lihs._price rhs._pricel = EPSILON) 106 return lhs._price ( const Book & lhs, const Book & rhs ) {return (rhs =( const Book & lhs, const Book & rhs ) {return !(lhs 2 #include 3 #include 4 #include "Book.hpp" 5 #include "Booklist.hpp" 6 namespace 7{ 8 void basicScenario) 9 { 10 // Let's start a book list 11 Booklist booksToRead = {{"Inviable Man" }, 12 {"Moby Dick" }, 13 {"Les Mis" }, 14 {"A Tale of Two Cities" }}; 15 16 // Changed my mind, I want to make sure I read Les Mis first so I'm going to move that to the top of my list 17 booksToRead.moveToTop( {"Les Mis"} );|| 18 // Let's see what's on the list so far 19 std::cout 3 #include // size t 4 #include 5 #include 6 #include 7 #include // domain_error, length_error, logic_error 8 #include 9 #include 10 #include "Book.hpp" 11 class Booklist 12 { 13 // Insertion and Extraction Operators 14 friend std::ostream& operator>( std::istream& stream, Booklist & booklist); 16 17 public: 18 // Types and Exceptions 19 enum class Position {TOP, BOTTOM}; 28 21 struct InvalidInternalState_Ex : std:: domain_error { using domain_error::domain_error; }; // Thrown if internal data structures become inconsistent with each other 22 struct CapacityExceeded Ex : std:: length error { using length error:: length error; }; // Thrown if more books are inserted than will fit 23 struct Invalidoffset Ex : std:: logic_error { using logic_error :: logic_error; }; // Thrown of inserting beyond current size 24 25 26 // Constructors, destructor, and assignment operators 27 BooklistO; // construct an empty book list 28 29 Booklist( const Booklist & other ); 11 construct a book list as a copy of another book list 38 Booklist Booklist 8& other); 1/ construct a book list by taking the contents of another book list 31 32 Booklist & operator=( Booklist rhs); // intentionally passed by value and not const ref 33 Booklist & operator=( Booklist && rhs); 34 35 Booklist ( const std::initializer_list & initlist); // constructs a book list from a braced list of books 36 Booklist & operator+= { const std::initializer list & rhs ); // concatenates a braced list of books to this list 37 Booklist & operator+={ const BookList & rhs ); // concatenates the rhs list to the end of this list 38 39 -BookList(); 40 // Queries 41 std::size_t size() const; 42 std::size_t find( const Book & book ) const; // returns the (zero-based) offset from top of list 43 // returns the (zero-based) position of the book, size() if book not found 44 // Mutators 45 void insert( const Book & book, Position position - Position:: TOP ); 11 add the book to the top (beginning) of the book list 46 void insert( const Book & book, std::size_t offsetFronTop ); // inserts before the existing book currently at that offset 47 48 void remove( const Book & book ); // no change occurs if book not found 49 void remove( std::size_t offsetFromTop ); 11 no change occurs if (zero-based) offsetFromTop >= size() 50 51 void moveToTop( const Book & book ); 52 53 void swap( Booklist & rhs ) noexcept; // exchange one book list with another 54 // Lexicographical Comparison 55 int compare( const Booklist & other ) const; // returns a negative number if this book list is less than the other book 56 1/ list, zero if this book list is equal to the other book list, and a 57 // positive number if this book list is greater than the other book list. 58 private: 59 // Helper functions 60 bool containersAreConsistant() const; 61 std::size_t books_si_list_size() const; // std::forward_list doesn't maintain size, so calculate it on demand 62 // Instance Attributes 63 std::size t books array_size - B; 11 std::array's size is constant so manage that attributes ourself 64 std:: array _books_array: 65 std::vector _books_vector; 66 std::list _books_di_list; 67 std:: forward_list _books_si_list; 68 ); 69 // Relational Operators 70 bool operator==const Booklist & ihs, const Booklist & rhs ); 71 bool operator!=( const Booklist & lhs, const Booklist & rhs ); 72 73 bool operators (const Booklist & lhs, const Booklist & rhs ); 74 bool operator ( const BookList & lhs, const Booklist & rhs); 76 bool operator>=( const Booklist & lhs, const Booklist & rhs ); 77 X Booklist.cpp 1 #include // find(), move(), move_backward(), equal(), swap(), lexicographical_compare() 2 #include // size_t 3 #include 4 #include // setwo 5 #include // distance(), next() 6 #include // logic_error 7 #include 8 #include "Book.hpp" 9 #include "BookList.hpp" 10 // As a rule, I strongly recommend avoiding macros, unless there is a compelling reason - this is such a case. This really does need 11 // to be a macro and not a function due to the way the preprocessor expands the source code location information. It's important to 12 // have these expanded where they are used, and not here. But I just can't bring myself to writing this, and getting it correct, 13 // everywhere it is used. Note: C++20 will change this technique with the introduction of the source_location class. Also note the 14 // usage of having the preprocessor concatenate two string literals separated only by whitespace. 15 #define exception_location " detected in function (*" std::string(_func_) + "\"" 16 " at line " + std::to_string( _LINE__) + 17 * in file ** FILE **** 18 / ***************************** 19** Private implementations, types, and objects 20 ************************************************* 21 bool Booklist::containersAreconsistant() const 22 { 23 // Sizes of all containers must be equal to each other 24 if( _books_array_size != _books_vector.size() 25 __books_array_size !- _books_di_list.size() 26 _books_array_size !- books_sl_list_size()) return false; 27 28 // Element content and order must be equal to each other 29 auto current_array_position - _books_array.cbegin(); 30 auto current_vector_position = _books_vector .cbegin(); 31 auto current_di_list_position = _books_di_list.cbegin(); 32 auto current_si_list_position = _books_51_list.cbegin(); 33 34 while( current_vector_position != _books_vector.cend()) 35 { 36 if( *current_array_position !- *current_vector_position 37 || *current_array_position 1= *current_di_list_position 38 || current_array_position != *current_si_list_position ) return false; 39 40 // Advance the iterators to the next element in unison 41 #current_array_position; 42 current_vector_position; 43 +*current_di_list_position; Hcurrent_si_list_position; 45 } 46 47 return true; 48} 49 // Calculate the size of the singly linked list on demand 50 std::size_t Booklist:: books_sl_list_size() const 51 { 52 IIIIIIIIIIIIIIIIIIIIIII TO-DO (1) SITTINTIIN 53 II/ Some implementations of a singly linked list maintain the size (number of elements in the list). std:: forward_list does 54 11/ not. The size of singly linked list must be calcula