DShelf012
[ Home ] [ Up ]

// file     DShelf012.cpp
// authors  AOU
// date     2006.03.08

/*
-----------------------------------------------
    2006.03.03   
    moveToRight(void); completed
    test_moveToRight
-----------------------------------------------
    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 =  20;
int const MAX_SHELF_WIDTH =  30;//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; //id=0 => no book or empty space
    int width;
  public:
    CBook(void);

    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 
      books with invalid id
      books with invalid width
      duplicate book
      too many books
      invalid shelf width
      invalid count
      invalid widthOccupied
    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);
void test_moveToRight(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_moveToRight();
  }


///////////////////////////////////////////////////////////////////////////////
// test_moveToRight
///////////////////////////////////////////////////////////////////////////////
void test_moveToRight(void)
  {
  cout << "-----------------------------------\n";
  cout << "test_moveToRight\n";
  cout << "-----------------------------------\n";

  bool result;
  
  CDShelf myShelf;
  myShelf.displayDetailed();
  myShelf.displaySimple();

  myShelf.moveToRight();

  cout << "\nAfter myShelf.moveToRight();\n";
  myShelf.displayDetailed();
  myShelf.displaySimple();
  cout << "---------------------------------\n";
  
  result = myShelf.insertAtLeft(3, 5);
  cout << "\nAfter 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();

  myShelf.moveToRight();
  cout << "\nAfter myShelf.moveToRight();\n";
  myShelf.displayDetailed();
  myShelf.displaySimple();

  myShelf.moveToRight();
  cout << "\nAfter myShelf.moveToRight();\n";
  myShelf.displayDetailed();
  myShelf.displaySimple();

  cout << "---------------------------------\n";
  }


///////////////////////////////////////////////////////////////////////////////
// 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)
  {
  //bookshelf is empty
  //  do nothing
  if (this->count == 0)
    return;
  
  //bookshelf is already full
  //  drop the last book
  //  move to right

  //bookshelf is not full
  //  move to right
  //  for i=count-1 to 0 step -1
  //    books[i+1] = books[i]
  //  books[0].id = 0
  //  count++
  if (this->count < this->width)
    {
    for (int i=this->count-1; i>=0; i--)
      this->books[i+1] = this->books[i]; //don't have to move id and width

    this->books[0].id = 0;
    this->count++;

    return;
    }
  }


///////////////////////////////////////////////////////////////////////////////
// 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";

  result = myShelf.insertAtLeft(4, 5);
  cout << "After myShelf.insertAtLeft(4, 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(5, 7);
  cout << "After myShelf.insertAtLeft(5, 7);\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
  // full <= widthOccupied .ge. shelf.width
  //

  //(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
  // not full <= widthOccupied .lt. shelf.width
  if (this->widthOccupied < this->width)
    {
    this->moveToRight();
    this->books[0].id=id;
    this->books[0].width = width;
    this->widthOccupied += width;
    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 << "Simple view:\n";
  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 << "Detailed view:\n";
  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;
    }
  }


///////////////////////////////////////////////////////////////////////////////
// CBook::CBook
///////////////////////////////////////////////////////////////////////////////
CBook::CBook(void)
  {
  id = 0;
  width = 0;
  };