CShelf006
[ Home ] [ Up ]

//CShelf006.cpp
//Author: AOU
//2005.12.05

/*
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 = 20;//100;
int const MIN_ID    = 1;
int const MAX_ID    = 9;
int const TEST_COUNT=4;


/*
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);
    bool insertAtLeft(int bookID, int bookWidth);
    bool remove(int bookID);
    void displayDetailed(void) const;
    void displaySimple(void) const;
    void displayBrief(void) const;
    bool search(int bookID) const;
  };


void testInsertAtLeft(void);


void main(void)
  {
  srand(100);
  testInsertAtLeft();
  }

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

  p = this->firstBook;

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

  return false;
  }

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))
    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 << "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;
  }