CShelf009
[ Home ] [ Up ]

//CShelf009.cpp
//Author: AOU
//2005.12.11

/*
data structure:
  booksOnshelf (firstBook, count, widthOccupied)
  book (id, width, bookOnRight)
functions:
init
add(bookID, bookWidth)
remove(bookID)
displayAll
end/displayBrief
search(booID)

*/

#include<iostream>
#include <fstream>
#include <ctime>
using namespace std;

int const UNDEFINED       = -9;
int const MIN_SHELF_WIDTH =  5;
int const MAX_SHELF_WIDTH =  40;//100;
int const MIN_ID          =  1;
int const MAX_ID          =  9;
int const TEST_COUNT      =  10;


/*
book with ID=0 is an empty space
*/
class CBook
  {
  private:
    int id;
    int width;
    CBook *bookOnRight;
    CBook *bookOnLeft;
  public:
    CBook(void);

  friend class CShelf;
  };


class CShelf
  {
  private:
    CBook *firstBook;
    CBook *lastBook;
    int width;
    int count;
    int widthOccupied;//sum of bookWidths exclude empty space
  public:
    CShelf(void);
    CShelf(int width);
    CShelf(char ch);
    ~CShelf(void);
    bool insertAtLeft(int bookID, int bookWidth);
    bool remove(int bookID);
    void displayDetailed(void) const;
    void displaySimple(void) const;
    void displayBrief(void) const;
    CBook* search(int bookID) const;
    bool isEmpty(void){return (firstBook==lastBook);}
  };


void testInsertAtLeft(void);
void testConstructor(void);
void testRemove(void);


void main(void)
  {
  srand((unsigned int) time(NULL));
  //testInsertAtLeft();
  //testConstructor();
  testRemove();
  }


//destructor for CSheld
CShelf::~CShelf(void)
  {
  while (this->firstBook != NULL)
    {
    this->lastBook = this->firstBook->bookOnRight;
    cout << "Deleting " << this->firstBook->id << " " << this->firstBook->width << endl;
    delete this->firstBook;
    this->firstBook = this->lastBook;
    }

  cout << "....................................\n";
  }


void testConstructor(void)
  {
  cout << "---------------\n";
  cout << "testConstructor\n";
  cout << "---------------\n";
  for (int t=1; t<=TEST_COUNT; t++)
    {
    CShelf myShelf('r');

    myShelf.displayBrief(); cout << endl;
    myShelf.displaySimple();cout << endl;
    myShelf.displayDetailed();
    cout << "------------------------------------\n";
    }
  }

  

/*
A constructor to build a populated shelf
*/
CShelf::CShelf(char ch)
  {
  if ('r' == ch)
    {
    this->count = 0;
    this->width = rand()%(MAX_SHELF_WIDTH-MIN_SHELF_WIDTH+1) + MIN_SHELF_WIDTH;
    this->widthOccupied = 0;
    this->firstBook = NULL;
    this->lastBook = NULL;

    for (int b=1; b<=TEST_COUNT; b++)
      {
      int bookID = rand()% (MAX_ID-MIN_ID+1) + MIN_ID;
      int bookWidth = rand()%((MAX_SHELF_WIDTH-MIN_SHELF_WIDTH)/8+1) + 1;
      //cout << "bookID=" << bookID << ", booWidth=" << bookWidth << endl;
      if (this->width >= (this->widthOccupied + bookWidth)) 
        this->insertAtLeft(bookID, bookWidth);
      else
        ;//cout << "    No room on the shelf\n";
      }
    }
  else
    {
    this->count = 0;
    this->width = rand()%(MAX_SHELF_WIDTH-MIN_SHELF_WIDTH+1) + MIN_SHELF_WIDTH;
    this->widthOccupied = 0;
    this->firstBook = NULL;
    this->lastBook = NULL;
    }
  }


void testRemove(void)
  {
  cout << "==========\n";
  cout << "testRemove\n";
  cout << "==========\n";
  for (int t=1; t<=TEST_COUNT/TEST_COUNT; t++)
    {
    CShelf myShelf('r');

    for (int b=1; b<=TEST_COUNT*3; b++)
      {
      myShelf.displayBrief(); cout << endl;
      myShelf.displaySimple();cout << endl;
      myShelf.displayDetailed();cout << endl;

      int bookID = rand()% (MAX_ID-MIN_ID+1) + MIN_ID;
      
      cout << "About to delete\n";
      cout << "bookID    = " << bookID << endl << endl;

      if (myShelf.remove(bookID))
        cout << "Remove was a success\n";
      else
        cout << "Remove was not a success\n\n";

      myShelf.displayBrief(); cout << endl;
      myShelf.displaySimple();cout << endl;
      myShelf.displayDetailed();cout << endl;

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

      if (myShelf.isEmpty())
        break;
      }

    cout << "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n";
    }
  }


/*
Possibilities:
  shelf is empty
  sought book is not on the shelf
  book is the rightmost
  book is not the rightmost (change th id to 0)
  only book on the shelf

Algorithm:
  if shelf is empty then return false
  sought book is not on the shelf then return false
  set the id to 0
  delete the rightmost empty space
*/
bool CShelf::remove(int bookID)
  {
  //if shelf is empty then return false
  if (this->firstBook == NULL)
    return false;
  //sought book is not on the shelf then return false
  CBook *p;
  p = this->search(bookID);
  if (NULL == p) 
    return false;
  //set the id to 0
  p->id = 0;
  this->count--;
  this->widthOccupied -= p->width;

  //delete the righmost empty books
  while (this->lastBook->id == 0)
    {
    if (this->lastBook == this->firstBook)
      {
      delete this->lastBook;
      this->lastBook = this->firstBook = NULL;
      break;
      }
    else
      {
      p = this->lastBook;
      this->lastBook = this->lastBook->bookOnLeft;
      this->lastBook->bookOnRight = NULL;
      delete p;
      }
    }

  return true;
  }


CBook* CShelf::search(int bookID) const
  {
  CBook *p;

  p = this->firstBook;

  while (p != NULL)
    {
    if (p->id == bookID)
      return p;
    p = p->bookOnRight;
    }

  return NULL;
  }

void CShelf::displayDetailed(void) const
  {
  cout << "Shelf\n";
  cout << "  count         = " << this->count << endl;
  cout << "  width         = " << this->width << endl;
  cout << "  widthOccupied = " << this->widthOccupied << endl;
  cout << "  firstBook @   = " << this->firstBook << endl;
  cout << "  lastBook @    = " << this->lastBook << endl;

  CBook *p;
  p = this->firstBook;
  while (p != NULL)
    {
    cout << "@" << p 
         <<" [" << p->bookOnLeft << ", "
         << p->id << ", " 
         << p->width << ", "
         << p->bookOnRight << "]\n";
    p = p->bookOnRight;
    }
 
  }


void CShelf::displaySimple(void) const
  {
  CBook *p;

  p = this->firstBook;
  while (p != NULL)
    {
    for (int i=1; i<=p->width; i++)
      cout << p->id;

    p = p->bookOnRight;
    }
  }


void CShelf::displayBrief(void) const
  {
  CBook *p;
  p = this->firstBook;
  while (p != NULL)
    {
    cout << "[" << p->id << ", " << p->width << "] ";
    p = p->bookOnRight;
    }
 
  }

void testInsertAtLeft(void)
  {
  for (int t=1; t<=TEST_COUNT/TEST_COUNT; t++)
    {
    int shelfWidth = 
      rand()% (MAX_SHELF_WIDTH-MIN_SHELF_WIDTH+1) + MIN_SHELF_WIDTH;
    CShelf myShelf(shelfWidth);

    cout << "Shelf width = " << shelfWidth << "\n";

    for (int b=1; b<=TEST_COUNT; b++)
      {
      int bookID = rand()% (MAX_ID-MIN_ID+1) + MIN_ID;
      int bookWidth = rand()%(shelfWidth/2+1) + 1;
      
      cout << "About to insert\n";
      cout << "bookID    = " << bookID << endl;
      cout << "bookWidth = " << bookWidth << endl;

      if (myShelf.insertAtLeft(bookID, bookWidth))
        cout << "Insert was a success\n";
      else
        cout << "Insert was not a success\n";

      myShelf.displayBrief(); cout << endl;
      myShelf.displaySimple();cout << endl;
      myShelf.displayDetailed();cout << endl;
      cout << "------------------------------------\n";
      }
    cout << "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n";
    }
  }

  
/*
insertAtLeft(booID, bookWidth)
Description:
  A new book is pushed on the left end of the shelf, 
  pushing other books to the right as needed. 
  No book moves to the right unless it is pushed by 
  an adjacent (touching) book on its left. Any book 
  that is not entirely on the shelf falls off the 
  right edge. No single book will ever be wider than 
  the given shelf. No book that is currently on the 
  shelf will be added again. 
  
Algorithm:
  if bookWidth > shelfWidth then return false
  if search(bookID) is true then return false
  insert book(bookID, bookWidth) at the front
  count++
  if count >1 then
    occupy empty space (ID=0) on right if necessary
    space occupied should be equal to bookWidth
    if widthOccupied > shelfWidth then
      drop the last book(s), 
      update widthOccupied, 
      update count
*/
bool CShelf::insertAtLeft(int bookID, int bookWidth)
  {
  if (bookWidth > this->width)
    return false;

  if (this->search(bookID) != NULL)
    return false;

  CBook *p;
  p = new CBook;
  p->id = bookID;
  p->width = bookWidth;
  p->bookOnLeft = NULL;

  if (0 == this->count)
    {
    p->bookOnRight = NULL;
    this->firstBook = p;
    this->lastBook = p;
    }
  else
    {
    p->bookOnRight = this->firstBook;
    this->firstBook->bookOnLeft = p;
    this->firstBook = p;
    }

  this->widthOccupied +=bookWidth;
  this->count++;

  //drop the last book(s) if necessary
  while (widthOccupied > this->width)
    //drop the last book(s), 
    {
    CBook *p;
    p = this->lastBook;
    this->lastBook = this->lastBook->bookOnLeft;
    this->lastBook->bookOnRight = NULL;
    this->widthOccupied -=p->width;
    //cout << "Book id=" << p->id << " of width=" << p->width << " was dropped\n";
    delete p;
    this->count--;
    }

  return true;
  }


CShelf::CShelf(int width)
  {
  this->count = 0;
  this->width = width;
  this->widthOccupied = 0;
  this->firstBook = NULL;
  this->lastBook = NULL;
  }

CShelf::CShelf(void)
  {
  this->count = 0;
  this->width = MIN_SHELF_WIDTH;
  this->widthOccupied = 0;
  this->firstBook = NULL;
  this->lastBook = NULL;
  }

CBook::CBook(void)
  {
  this->id = this->width = UNDEFINED;
  this->bookOnLeft = this->bookOnRight = NULL;
  }