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.
