From c1b6ffe70bd281c6c230fd63fabcaac2aff47514 Mon Sep 17 00:00:00 2001 From: Fuwn Date: Sun, 7 Apr 2024 23:18:32 -0700 Subject: feat: initial commit --- chapter3/bag1.cxx | 100 +++++++++++++++++++++++++++++++++++++ chapter3/bag1.h | 87 +++++++++++++++++++++++++++++++++ chapter3/bag_demo.cxx | 62 +++++++++++++++++++++++ chapter3/sequence1.h | 105 +++++++++++++++++++++++++++++++++++++++ chapter3/sequence_test.cxx | 119 +++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 473 insertions(+) create mode 100644 chapter3/bag1.cxx create mode 100644 chapter3/bag1.h create mode 100644 chapter3/bag_demo.cxx create mode 100644 chapter3/sequence1.h create mode 100644 chapter3/sequence_test.cxx (limited to 'chapter3') diff --git a/chapter3/bag1.cxx b/chapter3/bag1.cxx new file mode 100644 index 0000000..9672bc0 --- /dev/null +++ b/chapter3/bag1.cxx @@ -0,0 +1,100 @@ +// FILE: bag1.cxx +// CLASS IMPLEMENTED: bag (see bag1.h for documentation) +// INVARIANT for the bag class: +// 1. The number of items in the bag is in the member variable used; +// 2. For an empty bag, we do not care what is stored in any of data; for a +// non-empty bag the items in the bag are stored in data[0] through +// data[used-1], and we don't care what's in the rest of data. + +#include // Provides copy function +#include // Provides assert function +#include "bag1.h" +using namespace std; + +namespace main_savitch_3 +{ + const bag::size_type bag::CAPACITY; + + bag::size_type bag::erase(const value_type& target) + { + size_type index = 0; + size_type many_removed = 0; + + while (index < used) + { + if (data[index] == target) + { + --used; + data[index] = data[used]; + ++many_removed; + } + else + ++index; + } + + return many_removed; + } + + bool bag::erase_one(const value_type& target) + { + size_type index; // The location of target in the data array + + // First, set index to the location of target in the data array, + // which could be as small as 0 or as large as used-1. If target is not + // in the array, then index will be set equal to used. + index = 0; + while ((index < used) && (data[index] != target)) + ++index; + + if (index == used) + return false; // target isn’t in the bag, so no work to do. + + // When execution reaches here, target is in the bag at data[index]. + // So, reduce used by 1 and copy the last item onto data[index]. + --used; + data[index] = data[used]; + return true; + } + + void bag::insert(const value_type& entry) + // Library facilities used: cassert + { + assert(size( ) < CAPACITY); + + data[used] = entry; + ++used; + } + + void bag::operator +=(const bag& addend) + // Library facilities used: algorithm, cassert + { + assert(size( ) + addend.size( ) <= CAPACITY); + + copy(addend.data, addend.data + addend.used, data + used); + used += addend.used; + } + + bag::size_type bag::count(const value_type& target) const + { + size_type answer; + size_type i; + + answer = 0; + for (i = 0; i < used; ++i) + if (target == data[i]) + ++answer; + return answer; + } + + bag operator +(const bag& b1, const bag& b2) + // Library facilities used: cassert + { + bag answer; + + assert(b1.size( ) + b2.size( ) <= bag::CAPACITY); + + answer += b1; + answer += b2; + return answer; + } +} diff --git a/chapter3/bag1.h b/chapter3/bag1.h new file mode 100644 index 0000000..907e58b --- /dev/null +++ b/chapter3/bag1.h @@ -0,0 +1,87 @@ +// FILE: bag1.h +// CLASS PROVIDED: bag (part of the namespace main_savitch_3) +// +// TYPEDEF and MEMBER CONSTANTS for the bag class: +// typedef ____ value_type +// bag::value_type is the data type of the items in the bag. It may be any of +// the C++ built-in types (int, char, etc.), or a class with a default +// constructor, an assignment operator, and operators to +// test for equality (x == y) and non-equality (x != y). +// +// typedef ____ size_type +// bag::size_type is the data type of any variable that keeps track of how many items +// are in a bag. +// +// static const size_type CAPACITY = _____ +// bag::CAPACITY is the maximum number of items that a bag can hold. +// +// CONSTRUCTOR for the bag class: +// bag( ) +// Postcondition: The bag has been initialized as an empty bag. +// +// MODIFICATION MEMBER FUNCTIONS for the bag class: +// size_type erase(const value_type& target); +// Postcondition: All copies of target have been removed from the bag. +// The return value is the number of copies removed (which could be zero). +// +// void erase_one(const value_type& target) +// Postcondition: If target was in the bag, then one copy has been removed; +// otherwise the bag is unchanged. A true return value indicates that one +// copy was removed; false indicates that nothing was removed. +// +// void insert(const value_type& entry) +// Precondition: size( ) < CAPACITY. +// Postcondition: A new copy of entry has been added to the bag. +// +// void operator +=(const bag& addend) +// Precondition: size( ) + addend.size( ) <= CAPACITY. +// Postcondition: Each item in addend has been added to this bag. +// +// CONSTANT MEMBER FUNCTIONS for the bag class: +// size_type size( ) const +// Postcondition: The return value is the total number of items in the bag. +// +// size_type count(const value_type& target) const +// Postcondition: The return value is number of times target is in the bag. +// +// NONMEMBER FUNCTIONS for the bag class: +// bag operator +(const bag& b1, const bag& b2) +// Precondition: b1.size( ) + b2.size( ) <= bag::CAPACITY. +// Postcondition: The bag returned is the union of b1 and b2. +// +// VALUE SEMANTICS for the bag class: +// Assignments and the copy constructor may be used with bag objects. + +#ifndef MAIN_SAVITCH_BAG1_H +#define MAIN_SAVITCH_BAG1_H +#include // Provides size_t + +namespace main_savitch_3 +{ + class bag + { + public: + // TYPEDEFS and MEMBER CONSTANTS + typedef int value_type; + typedef std::size_t size_type; + static const size_type CAPACITY = 30; + // CONSTRUCTOR + bag( ) { used = 0; } + // MODIFICATION MEMBER FUNCTIONS + size_type erase(const value_type& target); + bool erase_one(const value_type& target); + void insert(const value_type& entry); + void operator +=(const bag& addend); + // CONSTANT MEMBER FUNCTIONS + size_type size( ) const { return used; } + size_type count(const value_type& target) const; + private: + value_type data[CAPACITY]; // The array to store items + size_type used; // How much of array is used + }; + + // NONMEMBER FUNCTIONS for the bag class + bag operator +(const bag& b1, const bag& b2); +} + +#endif diff --git a/chapter3/bag_demo.cxx b/chapter3/bag_demo.cxx new file mode 100644 index 0000000..3ee7900 --- /dev/null +++ b/chapter3/bag_demo.cxx @@ -0,0 +1,62 @@ +// FILE: bag_demo.cxx +// This is a small demonstration program showing how the bag class is used. +#include // Provides cout and cin +#include // Provides EXIT_SUCCESS +#include "bag1.h" // With value_type defined as an int +using namespace std; +using namespace main_savitch_3; + +// PROTOTYPES for functions used by this demonstration program: +void get_ages(bag& ages); +// Postcondition: The user has been prompted to type in the ages of family +// members. These ages have been read and placed in the ages bag, stopping +// when the bag is full or when the user types a negative number. + +void check_ages(bag& ages); +// Postcondition: The user has been prompted to type in the ages of family +// members once again. Each age is removed from the ages bag when it is typed, +// stopping when the bag is empty. + + +int main( ) +{ + bag ages; + + get_ages(ages); + check_ages(ages); + cout << "May your family live long and prosper." << endl; + return EXIT_SUCCESS; +} + + +void get_ages(bag& ages) +{ + int user_input; + + cout << "Type the ages in your family." << endl; + cout << "Type a negative number when you are done:" << endl; + cin >> user_input; + while (user_input >= 0) + { + if (ages.size( ) < ages.CAPACITY) + ages.insert(user_input); + else + cout << "I have run out of room and can’t add that age." << endl; + cin >> user_input; + } +} + +void check_ages(bag& ages) +{ + int user_input; + + cout << "Type those ages again. Press return after each age:" << endl; + while (ages.size( ) > 0) + { + cin >> user_input; + if (ages.erase_one(user_input)) + cout << "Yes, I've got that age and will remove it." << endl; + else + cout << "No, that age does not occur!" << endl; + } +} diff --git a/chapter3/sequence1.h b/chapter3/sequence1.h new file mode 100644 index 0000000..1a1aea7 --- /dev/null +++ b/chapter3/sequence1.h @@ -0,0 +1,105 @@ +// FILE: sequence1.h +// CLASS PROVIDED: sequence (part of the namespace main_savitch_3) +// There is no implementation file provided for this class since it is +// an exercise from Section 3.2 of "Data Structures and Other Objects Using C++" +// +// TYPEDEFS and MEMBER CONSTANTS for the sequence class: +// typedef ____ value_type +// sequence::value_type is the data type of the items in the sequence. It +// may be any of the C++ built-in types (int, char, etc.), or a class with a +// default constructor, an assignment operator, and a copy constructor. +// +// typedef ____ size_type +// sequence::size_type is the data type of any variable that keeps track of +// how many items are in a sequence. +// +// static const size_type CAPACITY = _____ +// sequence::CAPACITY is the maximum number of items that a sequence can hold. +// +// CONSTRUCTOR for the sequence class: +// sequence( ) +// Postcondition: The sequence has been initialized as an empty sequence. +// +// MODIFICATION MEMBER FUNCTIONS for the sequence class: +// void start( ) +// Postcondition: The first item on the sequence becomes the current item +// (but if the sequence is empty, then there is no current item). +// +// void advance( ) +// Precondition: is_item returns true. +// Postcondition: If the current item was already the last item in the +// sequence, then there is no longer any current item. Otherwise, the new +// current item is the item immediately after the original current item. +// +// void insert(const value_type& entry) +// Precondition: size( ) < CAPACITY. +// Postcondition: A new copy of entry has been inserted in the sequence +// before the current item. If there was no current item, then the new entry +// has been inserted at the front of the sequence. In either case, the newly +// inserted item is now the current item of the sequence. +// +// void attach(const value_type& entry) +// Precondition: size( ) < CAPACITY. +// Postcondition: A new copy of entry has been inserted in the sequence after +// the current item. If there was no current item, then the new entry has +// been attached to the end of the sequence. In either case, the newly +// inserted item is now the current item of the sequence. +// +// void remove_current( ) +// Precondition: is_item returns true. +// Postcondition: The current item has been removed from the sequence, and the +// item after this (if there is one) is now the new current item. +// +// CONSTANT MEMBER FUNCTIONS for the sequence class: +// size_type size( ) const +// Postcondition: The return value is the number of items in the sequence. +// +// bool is_item( ) const +// Postcondition: A true return value indicates that there is a valid +// "current" item that may be retrieved by activating the current +// member function (listed below). A false return value indicates that +// there is no valid current item. +// +// value_type current( ) const +// Precondition: is_item( ) returns true. +// Postcondition: The item returned is the current item in the sequence. +// +// VALUE SEMANTICS for the sequence class: +// Assignments and the copy constructor may be used with sequence objects. + +#ifndef MAIN_SAVITCH_SEQUENCE_H +#define MAIN_SAVITCH_SEQUENCE_H +#include // Provides size_t + +namespace main_savitch_3 +{ + class sequence + { + public: + // TYPEDEFS and MEMBER CONSTANTS + typedef double value_type; + typedef std::size_t size_type; + static const size_type CAPACITY = 30; + // CsONSTRUCTOR + sequence( ); + // MODIFICATION MEMBER FUNCTIONS + void start( ); + void advance( ); + void insert(const value_type& entry); + void attach(const value_type& entry); + void remove_current( ); + // CONSTANT MEMBER FUNCTIONS + size_type size( ) const; + bool is_item( ) const; + value_type current( ) const; + private: + value_type data[CAPACITY]; + size_type used; + size_type current_index; + }; +} + +#endif + +// g++ -o seq sequence1.cpp sequence_test.cxx + diff --git a/chapter3/sequence_test.cxx b/chapter3/sequence_test.cxx new file mode 100644 index 0000000..f140203 --- /dev/null +++ b/chapter3/sequence_test.cxx @@ -0,0 +1,119 @@ +// FILE: sequence_test.cxx +// An interactive test program for the new sequence class +#include // Provides toupper +#include // Provides cout and cin +#include // Provides EXIT_SUCCESS +#include "sequence1.h" // With value_type defined as double +using namespace std; +using namespace main_savitch_3; + +// PROTOTYPES for functions used by this test program: +void print_menu( ); +// Postcondition: A menu of choices for this program has been written to cout. + +char get_user_command( ); +// Postcondition: The user has been prompted to enter a one character command. +// The next character has been read (skipping blanks and newline characters), +// and this character has been returned. + +void show_sequence(sequence display); +// Postcondition: The items on display have been printed to cout (one per line). + +double get_number( ); +// Postcondition: The user has been prompted to enter a real number. The +// number has been read, echoed to the screen, and returned by the function. + + +int main( ) +{ + sequence test; // A sequence that we’ll perform tests on + char choice; // A command character entered by the user + + cout << "I have initialized an empty sequence of real numbers." << endl; + + do + { + print_menu( ); + choice = toupper(get_user_command( )); + switch (choice) + { + case '!': test.start( ); + break; + case '+': test.advance( ); + break; + case '?': if (test.is_item( )) + cout << "There is an item." << endl; + else + cout << "There is no current item." << endl; + break; + case 'C': if (test.is_item( )) + cout << "Current item is: " << test.current( ) << endl; + else + cout << "There is no current item." << endl; + break; + case 'P': show_sequence(test); + break; + case 'S': cout << "Size is " << test.size( ) << '.' << endl; + break; + case 'I': test.insert(get_number( )); + break; + case 'A': test.attach(get_number( )); + break; + case 'R': test.remove_current( ); + cout << "The current item has been removed." << endl; + break; + case 'Q': cout << "Ridicule is the best test of truth." << endl; + break; + default: cout << choice << " is invalid." << endl; + } + } + while ((choice != 'Q')); + + return EXIT_SUCCESS; +} + +void print_menu( ) +// Library facilities used: iostream.h +{ + cout << endl; // Print blank line before the menu + cout << "The following choices are available: " << endl; + cout << " ! Activate the start( ) function" << endl; + cout << " + Activate the advance( ) function" << endl; + cout << " ? Print the result from the is_item( ) function" << endl; + cout << " C Print the result from the current( ) function" << endl; + cout << " P Print a copy of the entire sequence" << endl; + cout << " S Print the result from the size( ) function" << endl; + cout << " I Insert a new number with the insert(...) function" << endl; + cout << " A Attach a new number with the attach(...) function" << endl; + cout << " R Activate the remove_current( ) function" << endl; + cout << " Q Quit this test program" << endl; +} + +char get_user_command( ) +// Library facilities used: iostream +{ + char command; + + cout << "Enter choice: "; + cin >> command; // Input of characters skips blanks and newline character + + return command; +} + +void show_sequence(sequence display) +// Library facilities used: iostream +{ + for (display.start( ); display.is_item( ); display.advance( )) + cout << display.current( ) << endl; +} + +double get_number( ) +// Library facilities used: iostream +{ + double result; + + cout << "Please enter a real number for the sequence: "; + cin >> result; + cout << result << " has been read." << endl; + return result; +} -- cgit v1.2.3