// file DShelf009.cpp
// authors AOU
// date 2006.03.01
/*
-----------------------------------------------
2006.03.01
void moveToRight(void); algorithm started
-----------------------------------------------
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);
void moveToRight(void);
/*
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();
}
///////////////////////////////////////////////////////////////////////////////
// CDShelf::moveToRight
///////////////////////////////////////////////////////////////////////////////
/*
it is only making room for a book record/entry
we will have to make sure that the new book
depending on its width does not cause any
book(s) to be dropped (calling dropRightmost)
Possibilities
bookshelf is already full
drop the last book
move to right
bookshelf is not full
move to right
bookshelf is empty
do nothing
*/
void CDShelf::moveToRight(void)
{
}
///////////////////////////////////////////////////////////////////////////////
// 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)
{
cout << "-----------------------------------\n";
cout << "test_insertAtLeft\n";
cout << "-----------------------------------\n";
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";
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";
}
///////////////////////////////////////////////////////////////////////////////
// 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
if(this->search(id) != UNDEFINED)
{
cout << "Duplicate book\n";
return false;
}
//(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;
}
}
|