|
// file DShelf008.cpp // authors AOU // date 2006.02.27 /* ----------------------------------------------- 2006.02.27 Search test_search ----------------------------------------------- 2006.02.20 Algorithm for insertAtLeft ----------------------------------------------- 2006.02.17 New insertAtLeft ..started test_insertAtLeft displaySimple ----------------------------------------------- CDShelf(void); //constructorDefault void test_constructorDefault(void); void displayDetailed(void); ----------------------------------------------- */ /* for a book of width 5 and id 1: 15 CBook books[MAX_SHELF_WIDTH] 11111 int a[MAX_SHELF_WIDTH] function | int a[MAX_SHELF_WIDTH] vs CBook books[MAX_SHELF_WIDTH] ------------------------------------------------------------------------------ constructorDefault | | isValid | |better constructorRandom | |better constructorWidth | | constructorFragmented| |better insertAtLeft | |better displayDetailed | | displaySimple |better | displayBrief | | isEmpty | | randomBook | |better randomBookPointer | |better search | |better remove_byID | |better remove_byPointer | |better reclaimSpace |better | reclaimableSpace | |better ------------------------------------------------------------------------------ */ /////////////////////////////////////////////////////////////////////////////// // includes /////////////////////////////////////////////////////////////////////////////// #include <iostream> using namespace std; /////////////////////////////////////////////////////////////////////////////// // Constants /////////////////////////////////////////////////////////////////////////////// // Constants int const UNDEFINED = -9; int const MIN_SHELF_WIDTH = 10; int const MAX_SHELF_WIDTH = 20;//100; int const MIN_BOOK_ID = 1; int const MAX_BOOK_ID = 9;//100; int const TEST_COUNT = 10; /////////////////////////////////////////////////////////////////////////////// // CBook /////////////////////////////////////////////////////////////////////////////// class CBook { private: int id; int width; public: CBook(void) { id = 0; width = 0; }; friend class CDShelf; }; /////////////////////////////////////////////////////////////////////////////// // CDShelf /////////////////////////////////////////////////////////////////////////////// class CDShelf { private: int width; // width of the bookshelf int count; // number of books on shelf int widthOccupied; // total width of book on shelf // should it include empty holes? // should not include empty holes // instead use spaceAvailable CBook books[MAX_SHELF_WIDTH]; public: CDShelf(void); //constructorDefault void displayDetailed(void); bool insertAtLeft(int id, int width); void displaySimple(void); int search(int id); /* isValid constructorRandom constructorWidth constructorFragmented displayBrief isEmpty randomBook randomBookPointer remove_byID remove_byPointer reclaimSpace reclaimableSpace */ }; /////////////////////////////////////////////////////////////////////////////// // test functions prototypes /////////////////////////////////////////////////////////////////////////////// void test_constructorDefault(void); void test_insertAtLeft(void); void test_search(void); // test_isValid // test_constructorRandom // test_constructorWidth // test_constructorFragmented // test_insertAtLeft // test_displayDetailed // test_displaySimple // test_displayBrief // test_isEmpty // test_randomBook // test_randomBookPointer // test_remove_byID // test_remove_byPointer // test_reclaimSpace // test_reclaimableSpace /////////////////////////////////////////////////////////////////////////////// // main /////////////////////////////////////////////////////////////////////////////// void main(void) { cout << "Hello\n"; //test_constructorDefault(); //test_insertAtLeft(); test_search(); } /////////////////////////////////////////////////////////////////////////////// // test_search /////////////////////////////////////////////////////////////////////////////// void test_search(void) { cout << "-----------------------------------\n"; cout << "test_search\n"; cout << "-----------------------------------\n"; bool result; CDShelf myShelf; myShelf.displayDetailed(); myShelf.displaySimple(); cout << "myShelf.search(2) = " << myShelf.search(2) << endl; cout << "---------------------------------\n"; result = myShelf.insertAtLeft(3, 5); cout << "After myShelf.insertAtLeft(3, 5);\n"; if (result) cout << "myShelf.insertAtLeft was a success\n"; else cout << "myShelf.insertAtLeft was NOT a success\n"; myShelf.displayDetailed(); myShelf.displaySimple(); cout << "myShelf.search(2) = " << myShelf.search(2) << endl; cout << "myShelf.search(3) = " << myShelf.search(3) << endl; cout << "---------------------------------\n"; } /////////////////////////////////////////////////////////////////////////////// // CDShelf::search /////////////////////////////////////////////////////////////////////////////// /* Search for a book with given id and return the location 0 to count-1 for i=0 to count-1 if books[i].id is equal to id then return i end for return UNDEFINED */ int CDShelf::search(int id) { for (int i=0; i<this->count; i++) if (books[i].id == id) return i; return UNDEFINED; } /////////////////////////////////////////////////////////////////////////////// // test_insertAtLeft /////////////////////////////////////////////////////////////////////////////// /* Algorithm0: Possibilities: (1) Empty shelf (2) Invalid book (3) Duplicate book (4) Full shelf We will have to drop one or more books (5) Shelf is not full and not empty We may have to move one or more books We may have to drop one or more books */ void test_insertAtLeft(void) { bool result; CDShelf myShelf; myShelf.displayDetailed(); myShelf.displaySimple(); cout << "---------------------------------\n"; result = myShelf.insertAtLeft(3, 5); cout << "After myShelf.insertAtLeft(3, 5);\n"; if (result) cout << "myShelf.insertAtLeft was a success\n"; else cout << "myShelf.insertAtLeft was NOT a success\n"; myShelf.displayDetailed(); myShelf.displaySimple(); cout << "---------------------------------\n"; result = myShelf.insertAtLeft(-1, 5); cout << "After myShelf.insertAtLeft(-1, 5);\n"; if (result) cout << "myShelf.insertAtLeft was a success\n"; else cout << "myShelf.insertAtLeft was NOT a success\n"; myShelf.displayDetailed(); myShelf.displaySimple(); cout << "---------------------------------\n"; result = myShelf.insertAtLeft(2, -1); cout << "After myShelf.insertAtLeft(2, -1);\n"; if (result) cout << "myShelf.insertAtLeft was a success\n"; else cout << "myShelf.insertAtLeft was NOT a success\n"; myShelf.displayDetailed(); myShelf.displaySimple(); cout << "---------------------------------\n"; } /////////////////////////////////////////////////////////////////////////////// // CDShelf::insertAtLeft /////////////////////////////////////////////////////////////////////////////// /* Algorithm0: Possibilities: (1) Empty shelf (2) Invalid book (3) Duplicate book (4) Full shelf We will have to drop one or more books (5) Shelf is not full and not empty We may have to move one or more books We may have to drop one or more books */ bool CDShelf::insertAtLeft(int id, int width) { //(1) Empty shelf if (0 == this->count) { this->books[0].id=id; this->books[0].width=width; this->count++; this->widthOccupied += width; return true; } //(2) Invalid book if (id < MIN_BOOK_ID || id > MAX_BOOK_ID) return false; if (width <= 0 || width > this->width) return false; //(3) Duplicate book //(4) Full shelf // We will have to drop one or more books //(5) Shelf is not full and not empty // We may have to move one or more books // We may have to drop one or more books return true; } /////////////////////////////////////////////////////////////////////////////// // CDShelf::displaySimple /////////////////////////////////////////////////////////////////////////////// /* void CDShelf::displaySimple(void) Algorithm0: for each book b do the following display id width times Algorithm1: for each book b do the following do the following b.width times display b.id Algorithm2: for i=0 to count-1 do the following for j=0 to b[i].width-1 do the following display b[i].id */ void CDShelf::displaySimple(void) { cout << "width = " << width << endl; cout << "count = " << count << endl; cout << "widthOccupied = " << widthOccupied << endl; for (int i=0; i<this->count; i++) for (int j=0; j<books[i].width; j++) cout << books[i].id; cout << endl; } /////////////////////////////////////////////////////////////////////////////// // CDShelf::displayDetailed /////////////////////////////////////////////////////////////////////////////// void CDShelf::displayDetailed(void) { cout << "width = " << width << endl; cout << "count = " << count << endl; cout << "widthOccupied = " << widthOccupied << endl; for (int i=0; i<MAX_SHELF_WIDTH; i++) { cout << books[i].id ; cout << books[i].width << ' '; } cout << endl; } /////////////////////////////////////////////////////////////////////////////// // test_constructorDefault /////////////////////////////////////////////////////////////////////////////// void test_constructorDefault(void) { CDShelf myShelf; myShelf.displayDetailed(); myShelf.displaySimple(); } /////////////////////////////////////////////////////////////////////////////// // CDShelf::CDShelf /////////////////////////////////////////////////////////////////////////////// CDShelf::CDShelf(void) { this->width = MIN_SHELF_WIDTH; this->count = 0; this->widthOccupied = 0; for (int i=0; i<MAX_SHELF_WIDTH; i++) { books[i].id = 0; books[i].width = 0; } } |