CShelf004
[ Home ] [ Up ]

//CShelf004.cpp
//Author: AOU
//2005.11.30

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

/*
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;
  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 main(void)
  {
  CShelf myShelf(9);
  myShelf.insertAtLeft(3, 2);
  myShelf.displayBrief(); cout << endl;
  myShelf.displaySimple();cout << endl;
  myShelf.displayDetailed();cout << endl;
  cout << "----------------------------\n";
  myShelf.insertAtLeft(2, 1);
  myShelf.displayBrief(); cout << endl;
  myShelf.displaySimple();cout << endl;
  myShelf.displayDetailed();cout << endl;
  cout << "----------------------------\n";
  myShelf.insertAtLeft(5, 4);
  myShelf.displayBrief(); cout << endl;
  myShelf.displaySimple();cout << endl;
  myShelf.displayDetailed();cout << endl;


  }

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

/*
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 (0 == this->count)
    {
    CBook *p;
    p = new CBook;
    
    p->bookOnLeft = NULL;
    p->bookOnRight = NULL;
    p->id = bookID;
    p->width = bookWidth;

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

    this->firstBook = p;
    this->lastBook = p;

    return true;
    }

  if (this->count > 0)
    {
    CBook *p;
    p = new CBook;
    
    p->id = bookID;
    p->width = bookWidth;

    p->bookOnRight = this->firstBook;
    p->bookOnLeft = NULL;
    this->firstBook->bookOnLeft = p;
    this->firstBook = p;

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

  }


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