CS 215 – Fundamentals of Programming IIFall 2007 (Harlaxton) – Project 640 pointsOut: October 25, 2007Due: November 18, 2007 (Thursday after long weekend)Note: Although this project is due after Exam 2 (and after the long weekend), the material covered by this project will be included in Exam 2. Therefore, it is in your best interest to have substantially started this project prior to Exam 2. Consider a filing cabinet. Each cabinet consists of one or more drawers that contain zero or more folders in each drawer. We will assume that the folders contain information that can be arranged in some ascending order by an integer key value (e.g., ID number) and that they are stored in the cabinet in that order. To make folders easier to find, the maximum key value that may be contained in a drawer is marked on the front of the drawer and the drawers are ordered by their maximum key values. This implies that a folder is stored in the drawer with the smallest maximum key value larger than the folder key. We can model such a filing cabinet as a (singly) linked list of drawers with each drawer containing a (singly) linked list of folders. Figure 1 on the next page illustrates the structure (only) of the filing cabinet. Project Specifications The specifications for this project are as follows. There are three template structs and classes where the template parameter is the type of the information being kept in the folders: a folder list node (FolderNode<T>), a drawer list node (DrawerNode<T>), and the filing cabinet object itself (FilingCabinet<T>). For this project, we specify the maximum number of folders that will fit into a drawer, but we can add another drawer to a filing cabinet anywhere and at anytime. FolderNode struct template The FolderNode struct template is used to form a linked list of folders in a drawer. The user is required to provide an integer, called a key, for each information object that is suitable for ordering the folders within the cabinet. Attributes Object Type Namekey value int keyinformation to store T itemlink to next folder FolderNode<T>* nextOperations There is just one operation other than direct access, the explicit-value constructor that creates a folder (node) by initializing the item, key, and link to the given arguments (or defaults). ● Analysis Objects Default Type Kind Movement Namekey value 0 int variable received aKeyinformation T() T variable received anItemlink to next folder nullFolderNode<T>*variable received aLink10/28/2007 1 of 6Figure 1: Structure of FilingCabinet class10/28/2007 2 of 6DrawerNode struct template The DrawerNode struct template is used to form a linked list of drawers in a filing cabinet. Attributes Object Type Namemaximum key value int maximumKeynumber of folders in the drawer int numFolderslink to folder list FolderNode<T>* folderListlink to next drawer DrawerNode<T>* nextOperations There is just one operation other than direct access, the explicit-value constructor creates an empty drawer (node) by initializing the number of folders to 0, the pointer to the folder list to null, and the maximum key value and the link to the given arguments (or defaults - the constant INT_MAX is defined in library <climits>). ● Analysis Objects Default Type Kind Movement Namemaximum key in the drawer INT_MAX int variable received maxKeylink to next drawer null DrawerNode<T>* variable received aLinkFilingCabinet class template The FilingCabinet class template ties everything together. Attributes Object Type Namelink to first drawer DrawerNode<T>* drawerListmaximum number of folders per drawer int maxFolderstotal number of folders in cabinet int totalFoldersOperations Default constructor - creates an empty filing cabinet by initializing totalFolders to 0 and maxFolders to 25, and creating one (empty) drawer initialized with a maximum key of INT_MAX. ● Analysis - no objects Explicit-value constructor - creates a filing cabinet from a vector of items whose keys are in a corresponding vector of integers, and also initializes the maximum number of folders per drawer and the maximum key value to the given arguments (or defaults). Each item is put into a folder (node) that is then put in a drawer (node). ● Analysis Objects Default Type Kind Movement Namelist of items --- vector<T> variable received initItemslist of corresponding keys --- vector<int> variable received initKeys10/28/2007 3 of 6Objects Default Type Kind Movement Namemaximum number of folders 25 int variable received initMaxFoldersmaximum key value INT_MAX int variable received initMaxKeyCopy constructor - creates a new FilingCabinet object that is a copy of an existing FilingCabinet object. ● Analysis Objects Type Kind Movement Nameoriginal FilingCabinet object FilingCabinet<T> variable received originalDestructor - deallocates the folder and drawer nodes. ● Analysis - no objects operator= - overloaded assignment operator function. Makes this FilingCabinet object into a copy of the original FilingCabinet object. ● Analysis Objects Type Kind Movement Nameoriginal FilingCabinet object FilingCabinet<T> variable received originalthis FilingCabinet object FilingCabinet<T>& variable returned *thisAddFolder - inserts the given item with the given key in order into the drawer with the smallest maximum key value larger than the given key, and increments the number of folders in the drawer it is placed in and the total number of folders. If the given key is already in the cabinet, throw a DuplicateError with an appropriate message (see below regarding exception objects). If the given key is larger than largest maximum key value, then throw a RangeError. If the drawer is full (i.e., it holds the maximum number of folders), insert a new drawer and put half of the folder list of the original drawer into it, appropriately setting the number of folders and the maximum key value, then proceed to add the new item to the appropriate drawer. ● Analysis Objects Type Kind Movement Nameitem to be added T variable received itemkey for item int variable received keyRemoveFolder - removes the item with the given key, decrements total number of folders and the number of folders in the drawer it is removed from. If the key is not in the cabinet, throw a NotFoundError with an appropriate message (see below regarding exception objects). Note that this may result in an empty drawer, which is allowable. ● Analysis Objects Type Kind Movement Namekey for item int variable received
View Full Document
Unlocking...