Software Design Document
for
Programming Assignment #3
April 3rd, 2014
Prepared by Sanjay Kapoor
Prepared For:
Dr. Rick Coleman, Instructor
CS 221, Data Structures in C++
Computer Science Department
University of Alabama in Huntsville
1.0 System Overview………………………………………………………………..3
2.0 Referenced Documents………………………………………………………..3
3.0 Architectural Design…………………………………………………………….3
3.1 Concept of Execution…………………………………………………..3
3.2 Code Outline……………………………………………………………..3
4.0 Detailed Design………………………………………………………………….4
4.1 Source File: Possessions.cpp
4.2 Source File: Possessions.h
4.3 Modified Source File: Character.cpp
4.4 Modified Source File: Character.h
1.0 System Overview
The Purpose of this program is to enumerate a Possessions class implemented using a Binary Tree which will be used to store items for our Character classes.
2.0 Referenced Documents
Programming Assignment 1 Statement of Work
Dale, Nell C++ Plus Data Structures (2011)
3.0 Architectural Design
3.1 Concept of Execution
The purpose of this program is to enumerate a Possessions class implemented
using a Binary Tree which will be used to store items for our Character classes.
This class will use the Binary Tree abstract data dype
3.2 Code Outline
The program will consist of the following files:
Possessions.h, Possessions.cpp, along with a modified form of Item.h and
Character.cpp
bool addItem(Item *newItem) -- this function takes a single argument, a pointer
to an Item structure. It will then add this item to the binary tree of items. This ffunction shall use the name of the item as the key for insertion into the binary tree. It will return true if the item was successfully added to the tree or false if it failed to add the item. This function shall be public.
Item *dropItem(char *itemName)-- this function takes an item name as it's only argument. It shall locate the item in the tree of items and remove this item from the binary tree of items. It will set the left and right pointers of the removed Item structure to NULL and return a pointer to the item. If the item was not found in the tree it shall return NULL.
Remember that if the node to be removed from the tree has two children it
actually get's overwritten. So in this case you will need to create a duplicate Item structure, and copy the data out of the one to be overwritten. Then after completing the deletion for a node with two children return the pointer to the new duplicate Item.
Item *getItem(char *itemName)-- this function takes an item name as its' only argument. It will then locate this item in the appropriate tree of items and return a pointer to the item. If the item was not found it shall return NULL. You may assume, in this case, that it is OK to return a pointer to an item in the tree without worrying about it giving access to other items in the tree. This function shall be public
void printTree()-- this is a public function which will just call the private function printAll() as defined in section 2.2.8.
void printOne(Item *item)-- this function shall take a pointer to an Item
structure and print on the screen all information in the structure. This shall include the item name, item description, weight, and value. This function shall be private as it should only be called by the printAll() function defined in section 2.2.8.
void destroyTree(Item *rt)-- this shall be a private function which can be called by the class destructor. It will recursively traverse the tree and delete all nodes from the tree. This function shall be private.
void printAll(Item *rt)-- this shall be a private function which is called by the public function printTree(). It takes a single argument, a pointer to the root of a tree. It will recursively traverse the tree in order and print all information in each item in the tree. It will call the function printOne() to print the information in the Item passed in as an argument.
4.1 Source File: Posessions.cpp
4.1.1 Function bool addItem(Item *newItem)
4.1.1.1 Purpose and Procedure
This driver function shall test how the function adds items to full or complete trees
and also to empty trees by adding five items in somewhat alphabetical and
somewhat nonalphabetical order
4.1.1.2 Inputs
Item *newItem
4.1.1.3 Expected Outputs
A boolean reporting whether the add was successful or not.
4.1.1.4 Success Criteria
That the printout from printAll() reveals that the items were added in the correct order, and
that the boolean returned matches whether the add was successful or not -- also, we should
not change the tree when attempting to add a node with the same key as one already in the
tree.
4.1.2 Function Item *dropItem(char *itemName)
4.1.2.1 Purpose and Procedure
This driver function will test if the dropItem() function successfully drops an item from
multiple places in the tree, and returns NULL when the item is not in the tree.
4.1.2.2 Inputs
A char array containing the name of the Item to be dropped.
4.1.2.3 Expected Outputs
NULL if the Item was not in the tree and the Item if it was dropped
4.1.2.4 Success Criteria
That the printout reveals that the Item was successfully dropped in the case that it was in
the tree, and that no change occurs in the tree if the Item was not contained.
4.1.3 Function public Item * getItem(char * itemName)
4.1.3.1 Purpose and Procedure
This driver function shall test if the getItem function returns a pointer to the Item indicated by
itemName if it was in the tree, and a NULL pointer if it was not contained.
4.1.3.2 Inputs
char * itemName
4.1.3.3 Expected Outputs
A pointer to the Node in the tree which is the Item we’re searching for if contained and a
NULL pointer otherwise.
4.1.3.4 Success Criteria
That the function returns Item contained within the tree if found, and NULL otherwise.
4.1.5 Function void printTree()
4.1.5.1 Purpose and Procedure
Test that the function prints the entire tree on the screen and verify that it works by printing
multiple trees of varying sizes and shapes.
4.1.5.2 Inputs
None
4.1.5.3 Expected Outputs
None.
4.1.5.4 Success Criteria
That the function correctly prints the trees contained in the Possessions objects.
4.1.6 Function private void printOne(Item *item)
4.1.6.1 Purpose and Procedure
This driver function shall test that the printOne function prints all the fields contained in the
Item object indicated by the item pointer by calling it passing multiple distinct items.
4.1.6.2 Inputs
A pointer to an Item, item.
4.1.6.3 Expected Outputs
None
4.1.6.4 Success Criteria
That the printOne function successfully prints out all the fields in the Items pointed to by
the item pointers.
4.1.7 Function private void destroyTree(Item *rt)
4.1.7.1 Purpose and Procedure
This function shall verify that the tree has been destroyed by testing that the root node
points to NULL -- there’s no way to verify that I can think of that the other nodes have
been destroyed.
4.1.7.2 Inputs
The tree to be destroyed.
4.1.7.3 Expected Outputs
None.
4.1.7.4 Success Criteria
A printout showing that the root node points to NULL and perhaps also print statements
surrounding each delete and rt == NULL statement.
4.1.8 Function private void printAll(Item *rt)
4.1.8.1 Purpose and Procedure
This driver function shall test the the printAll function prints whatever subtree it’s passed by
trying it with multiple subtrees -- it will mainly be used to print the whole tree, but should work
also in general for any subtree.
4.1.8.2 Inputs
A pointer to an Item, *rt
4.1.8.3 Expected Outputs
None.
4.1.8.4 Success Criteria
That the printAll() function prints whatever subtree it’s passed properly.
4.1.8.5 Traceability
4.3 Source File: Character.cpp
4.3.1 Function bool addItem(Item *item)
4.3.1.1 Purpose and Procedure
Test the function by passing in an item of type BattleItems or TreasureItems and ensuring
that it was added to the proper Item tree.
4.3.1.2 Inputs
Item *item
4.3.1.3 Expected Outputs
A boolean reporting whether the add was successful or not.
4.3.1.4 Success Criteria
A printout showing that the Item was added to the proper subtree.
4.3.2 Function Item *dropItem(char *itemName)
4.3.2.1 Purpose and Procedure
Test the function by ensuring that it was dropped from the proper subtree, and if not
contained, that NULL was returned instead.
4.3.2.2 Inputs
char *itemName
4.3.2.3 Expected Outputs
A pointer to a copy of the Item structure deleted, or NULL if the Item was either not
deleted or found.
4.3.2.4 Success Criteria
A printout showing that the Item was either successfully dropped, or NULL was returned
the proper matching tree was not modified if that Item of that type (BattleItems or
TreasureItems) was not contained there.
4.3.2.5 Traceability
This function satisfies requirement 2.4.5 in the SoW.