Data Structures

Lab 3

1. This assignment tests the concepts of:
   • Containers
   • Static arrays

Program Objective:

Implement 2 non-member functions and one member function.

1. The provided driver code reads in a bunch of integers from the command line and places them into a bag container.
2. We will explore two ways to remove all items in the bag
   1. The authors bag has only TWO ways to remove items, erase and erase_one. Both of these functions require you to send the target number you want removed.
   2. Problem: You need to empty all items from the bag with NO KNOWLEDGE of what numbers are, only knowing what the smallest and largest values are.
      • Implement emptyBag(bag& nums, const stats& bagStats) which loops over calling the erase member function on the bag until empty. On each iteration pick a random number min >= x <= max. Do not worry about trying to remove the same random number more than once.
   3. Problem: emptyBag took unnecessary runtime. Fix this by implementing a member function in the authors bag named grab_random. The function should REMOVE one item from the bag each time and return the number removed. Implement emptyBag(bag& nums) to take advantage of this new member function you implemented.
3. Think about, what is the BigOh of each function.

DELIVERABLES:

Description	filename
Your implementation of the 3 functions	lab03.cpp

You should not modify labdriver.cpp, bag1.h, bag1.cpp, or baglab.cpp.

Submitted assignments without the above file named correctly will render your assignment as uncompilable and will be detrimental to your assignment grade.

Instructions:

1. The provided driver is expecting command line arguments. It is best to add arguments to your IDE of choice.
   1. The program should compile, however, the harder part is adding command-line arguments to your favorite IDE.
      • For Eclipse CDT
        • Right click the project and choose properties
        • Go to Run/Debug Settings
        • Choose your launch configuration and click Edit
        • Click the Arguments tab
        • Type in some numbers separated by a space
      • For Microsoft Visual Studio
        • Right click the project and choose properties
        • Go to Configuration Properties->Debugging
        • On the right hand side, type in some numbers separated by a space in the Command Arguments text area.
      • For CLion
        • Open the menu Run->Edit Configurations
        • Type in some numbers separated by a space in the program arguments text area.
      • For Dev++
        • Stop using Dev++ and use one of the above IDEs
   2. Once you add the command line arguments to your IDE, these values will be appended to the program executable when executed (ie: run).

Additional requirements:

• No STL containers may be used. Include only iostream, cstdlib, ctime, and algorithm (if you wish to use copy).

Example output (from multiple runs with different arguments given):

$ ./lab03 1 2 4 8 16 2 8 256 0 255 All 10 items removed in 308 tries. All 10 items removed in 10 tries. $ ./lab03 1 -50 1256 All 3 items removed in 1535 tries. All 3 items removed in 3 tries.

Help

Starter shell for lab03.cpp

#include  //For assert #include  //For rand #include "bag1.h" #include "baglab.h" namespace DS { bag::value_type bag::grab_random() { //Remove a random item in the bag return value_type(); //Remove this line } size_t emptyBag(DS::bag& nums, const DS::stats& bagStats) { //Implement assuming grab_random does NOT exist //Use stats struct to know the max and min //Use cstdlib's rand for random function return 0; //Remove this line } size_t emptyBag(DS::bag& nums) { //Implement assuming member grab_random exist return 0; //Remove this line } } //End of DS namespace

 // FILE: bag1.cpp // From Chapter 3 of Data Structures and Other Objects (Second Edition) // ________________________________________________________________________ // // This file has been modified to work with Microsoft Visual C++ 6.0, // as described in www.cs.colorado.edu/~main/vc6.html // ________________________________________________________________________ // // 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 #include #include "bag1.h" using namespace std; namespace DS { bag::bag() { /* initialize random seed: */ srand (time(NULL)); used = 0; } 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 isnt 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; } }

// FILE: bag1.h // From Chapter 3 of Data Structures and Other Objects (Second Edition) // ________________________________________________________________________ // // 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. // // value_type grab_random(); // Precondition: size( ) > 0 // Postcondition: One random item will be removed and returned from the bag // TO BE IMPLEMENTED BY THE STUDENT // // 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 DS { class bag { public: // TYPEDEFS and MEMBER CONSTANTS typedef int value_type; typedef size_t size_type; static const size_type CAPACITY = 30; // CONSTRUCTOR bag( ); // 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; value_type grab_random(); protected: 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

#include // Provides cout and cin #include // Provides EXIT_SUCCESS and srand #include // assist to seed to pseudo random generator #include "bag1.h" // With value_type defined as an int #include "baglab.h" using namespace std; using namespace DS; int main(int argc, char const *argv[]) { srand(time(0)); bag nums; stats bagStats; bagStats = cStrArray2Bag(nums, &argv[1], static_cast(argc-1)); cout << endl; cout << "All " << argc-1 << " items removed in " << emptyBag(nums, bagStats) << " tries." << endl; //Load the bag again cStrArray2Bag(nums, &argv[1], static_cast(argc-1)); cout << "All " << argc-1 << " items removed in " << emptyBag(nums) << " tries." << endl; return EXIT_SUCCESS; } namespace DS { stats cStrArray2Bag(bag& b, const char* values[], size_t size) { stats retVal; int num; if ( size > 0 ) { retVal.min = retVal.max = atoi(values[0]); b.insert( retVal.min ); for (size_t argi=1 ; argi < size ; ++argi ) { num = atoi(values[argi]); b.insert( num ); if ( num < retVal.min ) retVal.min = num; else if ( num > retVal.max ) retVal.max = num; } } return retVal; } }

/* Programmer Name: Professor Miller File Purpose: Stats struct and some global convenience functions Date Updated: Jan 27th, 2019 Purpose for Update: Lab Global Variable List: n/a (avoid these) */ #ifndef BAGLAB_H_ #define BAGLAB_H_ #include #include "bag1.h" namespace DS { //Recall that a struct is very similar to a C++ class, however, ALL member items are public //This simple struct will keep struct stats { int min; int max; }; //Precondition: nums is a bag of integers with 0 or more items. // bagStats correctly holds the minimum and maximum values in the bag // The bag class does NOT have the member function grab_random available. //Postcondition: All items in the bag is removed. The number of times the loop iterated is returned. size_t emptyBag(bag& nums, const stats& bagStats); //IMPLEMENTED BY STUDENT //Precondition: nums is a bag of integers with 0 or more items. // The bag class HAS the member function grab_random available. //Postcondition: All items in the bag is removed. The number of times the loop iterated is returned. size_t emptyBag(bag& nums); //IMPLEMENTED BY STUDENT //Precondition: Values is an array of integers stored as character C strings, // size is equal to the number of items in the values array //Postcondition: All items in values is inserted into the bag b. // Stats are returned with the smallest integer inside the array set to min and largest value set to max; stats cStrArray2Bag(bag& b, const char* values[], size_t size); } //End DS namespace #endif /* BAGLAB_H_ */