Data Structures and Algorithms

 CS 3100 – Data Structures and Algorithms

Project #1 – Building a magic bag 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 build a “Magic Bag” data type. You will be given a .h file with function prototypes for the magic bag. You will implement the functions according to the following specifications.

 

The Magic Bag

 

The magic bag data type will be implemented as follows:

 

·         Objects can be inserted into the magic bag using the MagicBag::insert(item) member function. The magic bag can hold any number of items, within the bounds of the available RAM. Duplicate items are allowed.

 

·         Objects are removed from the magic bag using the MagicBag::draw() member function. This function returns a random item and removes it from the bag. The returned item should be randomized. In other words, if there are five items in the bag, and only one of them is a 7, then there should be a 1 in 5 chance of drawing a 7 with the draw() function. If the bag is empty, the draw() function should throw an exception.

 

·         You can check if an object is in the bag using MagicBag::peek(item), which should return 0 if there is no item in the bag matching the item parameter. If there are items matching

the item parameter in the bag, the number (count) of matching items should be returned.

 

·         Override the << operator for your Magic Bag class via a friend function. The representation of the Magic Bag should be enclosed in square brackets, and the values should be separated by spaces. For example, if the bag contains the integers 2, 1, and 3, it would look like this: [2 1 3]

 

·         You should have a copy constructor and also be able to assign the contents of a MagicBag using the = operator. This should result in a copy of the magic bag that is not linked to the original bag. In other words, if a and b are magic bags, the line "a = b;" should result in

bags a and b having the same contents. If I then draw elements from bag b, this should not change the contents of bag a.

 

·         Your magic bag should be capable of holding any primitive data type. (You might want to start with just integers and get everything working before converting your class to a template.)

 

·         You can implement the magic bag using an array, a linked list, or any other data structure that you feel is appropriate. You need to design and implement the underlying data structure

yourself. You may not, for example, use C++ standard template library vectors for the underlying data structure.

 

·         You will be provided with a main program for testing your magic bag.

 

·         No points will be awarded for submissions that do not compile.

 

Turn in and Grading

 

Please build your class in-line in the MagicBag.h file provided. To ease the grading process, please put all of your code (including your exception class) in the .h file rather than having a separate .cpp file.

Please turn in MagicBag.h (with that name) to the dropbox. Do not turn in the main program provided to you for testing. Do not zip, archive, or compress your file(s).

 

Your project will be graded according to the following rubric. The number in [ ] is the number of points each item is worth. Projects that do not compile will receive a zero.

 

[10] You can create a magic bag of integers and insert integers into the bag.

 

[10] You can create a magic bag of any primitive data type and insert items into the bag.

 

[10] The capacity of the magic bag is limited only by the amount of available RAM.

 

[10] The peek() member function returns the correct value without deleting any items from the bag.

 

[10] The draw() member function returns and removes an item from the bag.

 

[10] The probability of drawing an item from the bag is equal for all items.

 

[10] Calling draw on an empty bag throws an exception.

 

[10] You can print Magic Bags to cout using <<

 

[10] Magic bags can be copied (using a copy constructor) and assigned (using =), resulting in a new, independent bag with the same contents as the original bag.

 

[10] You code has no memory leaks.