CShelf
[ Home ] [ Up ]

//CShelf015.cpp
//Author: AOU
//2006.04.17

/*
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;                                               //  book id, 0 for book removed
    int width;                                            //  book width
    CBook *bookOnRight;                                   //  pointer to book on right side
    CBook *bookOnLeft;                                    //  pointer to book on left side
  public:
    CBook(void);

  friend class CShelf;
  };


class CShelf
  {
  private:
    CBook *firstBook;                                     //  points to the leftmost book     //
    CBook *lastBook;                                      //  points to the rightmost book    //
    int width;                                            //  width of the bookshelf          //
    int count;                                            //  number of books on the shelf    //
    int widthOccupied;                                    //  total width of book on shelf    //
  public:
    CShelf(void);                                         //  test_constructorDefault         //
    bool isValid(void);                                   //  test_isValid
    CShelf(char ch);                                      //  test_constructorRandom
    CShelf(int width);                                    //  test_constructorWidth           //
                                                          //  test_constructorFragmented
    ~CShelf(void);
    bool insertAtLeft(int bookID, int bookWidth);         //  test_insertAtLeft
    void displayDetailed(void) const;                     //  test_displayDetailed
    void displaySimple(void) const;                       //  test_displaySimple
    void displayBrief(void) const;                        //  test_displayBrief
    bool isEmpty(void)const;                              //  test_isEmpty
    int randomBook(void) const;                           //  test_randomBook
    CBook *randomBookPointer(void) const;                 //  test_randomBookPointer
    CBook* search(int bookID) const;                      //  test_search
    bool remove(int bookID);                              //  test_remove_byID
    bool remove(CBook *p);                                //  test_remove_byPointer
    int reclaimSpace(int space);                          //  test_reclaimSpace
    int reclaimableSpace(void) const;                     //  test_reclaimableSpace
  };


void display_test_header(char *test_name);

void test_constructorDefault(void);
void test_isValid(void);
void test_insertAtLeft(void);
void test_constructorRandom(void);
void test_constructorWidth(void);
void test_constructorFragmented(void);
void test_remove_byID(void);
void test_reclaimSpace(void);
void test_randomBook(void);
void test_randomBookPointer(void);
void test_isEmpty(void);
void test_search(void);
void test_remove_byPointer(void);
void test_reclaimableSpace(void);
void test_displayDetailed(void);
void test_displaySimple(void);
void test_displayBrief(void);


bool CShelf::isEmpty(void)const 
  {
  return (firstBook==NULL);
  }

void test_isValid(void)
  {
  }

/*
bool CShelf::isValid(void)
Possibilities:
  Empty shelf
  invalid count
  invalid book id
  invalid book width
  empty space on the righmost side
  widthOccupied more than width of shelf
  virtual width more than width
  duplicate book ids
Algorithm:
  if firstBook==lastBook==null then 
    return true

  if count <> the number of books then
    return false

  if book id of any book is out of range then 
    return false

  if book width of any book is > width of shelf then
    return false

  if empty space on rightmost position then
    return false

  if widthOccupied > width of shelf then
    return false

  if total of books widths and empty spaces > width of shelf then
    return false

  if there is a duplicate book then
    return false

  return true
*/
bool CShelf::isValid(void)
  {
  //if firstBook==lastBook==null then return true
  if ((NULL == this->firstBook) && (NULL == this->lastBook))
    return true;

  //if count <> the number of books then return false
  CBook *p=this->firstBook;
  int tCount = 0;
  while (p != NULL)
    {
    tCount++;
    p = p->bookOnRight;
    }

  if (this->count != tCount)
    return false;

  p=this->lastBook;
  tCount = 0;
  while (p != NULL)
    {
    tCount++;
    p = p->bookOnLeft;
    }

  if (this->count != tCount)
    return false;

  //if book id of any book is out of range then return false
  p=this->firstBook;
  while (p != NULL)
    {
    if ((p->id < MIN_ID) || (p->id > MAX_ID))
      return false;

    p = p->bookOnRight;
    }

  //if book width of any book is > width of shelf then return false
  p=this->firstBook;
  while (p != NULL)
    {
    if (p->id > this->width)
      return false;

    p = p->bookOnRight;
    }

  //if empty space on rightmost position then return false
  if (0 == this->lastBook->id)
    return false;

  //if widthOccupied > width of shelf then return false
  if (this->widthOccupied > this->width)
    return false;

  //if total of books and empty spaces > width of shelf then return false
  p=this->firstBook;
  int tWidth = 0;
  while (p != NULL)
    {
    tWidth = tWidth + p->width;
    p = p->bookOnRight;
    }
  
  if (tWidth > this->width)
    return false;

  //if there is a duplicate book then return false
  p=this->firstBook;
  CBook *q;
  while (p->bookOnRight != NULL)
    {
    //check if there is a book on right with same id
    q = p->bookOnRight;
    while (q != NULL)
      {
      if (p->id == q->id)
        return false;

      q = q->bookOnRight;
      }
    
    p = p->bookOnRight;
    }
  



  return true;
  }


void main(void)
  {
  //srand(133);
  //srand((unsigned int) time(NULL));
  //test_constructorDefault();
  //test_constructorWidth();
  //test_insertAtLeft();
  //test_constructorFragmented();
  //test_constructorRandom();
  //test_isValid();
  //test_remove_byID();
  //test_randomBook();
  //test_randomBookPointer();
  //test_reclaimSpace();

  int a;
  a = 3;
  cout << a << endl;

  int *pa;
  pa = NULL;
  cout << *pa << endl;
  cout << pa << endl;
  cout << &a << endl;
  cout << &pa << endl;

  }


int CShelf::reclaimableSpace(void) const
  {
  if (this->isEmpty())
    return 0;
  
  int space = 0;
  CBook *p = this->firstBook;

  while (p != NULL)
    {
    if (p->id == 0)
      space += p->width;

    p = p->bookOnRight;
    }

  return space;
  }


void test_randomBookPointer(void)
  {
  cout << "======================\n";
  cout << "test_randomBookPointer\n";
  cout << "======================\n";

  for (int t=1; t<=TEST_COUNT/TEST_COUNT; t++)
    {
    cout << "Test Count " << t << endl;

    CShelf myShelf('r');

    cout << "CShelf myShelf('r'); executed\n";

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

    for (int b=1; b<=TEST_COUNT; b++)
      {
      CBook *p = myShelf.randomBookPointer();
      cout << "random bookPointer " << p     << endl;

      if (myShelf.remove(p))
        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;

      if (myShelf.isEmpty())
        break;
      }

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


/*
Randomly selects a book pointer from the shelf
*/
CBook * CShelf::randomBookPointer(void) const
  {
  if (0==this->count)
    return NULL;

  int turn = rand()%this->count;
  CBook *p = this->firstBook;
  while (turn > 0)
    {
    p = p->bookOnRight;
    if (p->id > 0)
      turn--;
    }

  return p;
  }


void test_randomBook(void)
  {
  cout << "=================\n";
  cout << "test_reclaimSpace\n";
  cout << "=================\n";

  for (int t=1; t<=TEST_COUNT/TEST_COUNT; t++)
    {
    cout << "Test Count " << t << endl;

    CShelf myShelf('r');

    cout << "CShelf myShelf('r'); executed\n";

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

    for (int b=1; b<=TEST_COUNT; b++)
      {
      int bookID = myShelf.randomBook();
      cout << "random bookID    = " << bookID << 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";
    }
  }


/*
Randomly selects a book id from the shelf
if the shelf has no book then return 0
skips the empty slots
*/
int CShelf::randomBook(void) const
  {
  if (0==this->count)
    return 0;

  CBook *p;
  p = this->firstBook;
  int n=0;
  while (p != NULL)
    {
    n++;
    p=p->bookOnRight;
    }

  do
    {
    int step = rand()%n;
    p=this->firstBook;
    while (step > 0)
      {
      p = p->bookOnRight;
      step--;
      }
    }
    while (p->id == 0);

  return p->id;
  }


/*
bool CShelf::remove(CBook *p)
Possibilities:
  invalid value in p
  empty list
  only one node in the list
  p is pointing to the first node
  p is pointing to the last node
  p is pointing to node between first and last
Algorithm:
  //invalid value in p
  if p is null then return false

  //empty list
  if list is empty then return false

  //only one node in the list
  set firstBook and lastBook to nuul
  delete p
  set count to 0
  return true

  //p is pointing to the first node
  firstBook = p->bookOnRight
  firstBook->bookOnLeft = null
  delete p
  count--
  return true

  //p is pointing to the last node
  lastBook = p->bookOnLeft
  lastBook->bookOnRight = null
  delete p
  count--
  return true

  //p is pointing to node between first and last
  p->bookOnLeft->bookOnRight = p->bookOnRight
  p->bookOnRight->bookOnLeft = p->bookOnLeft
  delete p
  count--
  return true
*/

bool CShelf::remove(CBook *p)
  {
  //invalid value in p
  if (NULL == p)
    return false;

  //empty list
  if (this->firstBook == NULL)
    return false;

  //only one node in the list
  if ((this->firstBook == p) && (p == this->lastBook))
    {
    this->firstBook = this->lastBook = NULL;
    delete p;
    this->count = 0;
    return true;
    }

  //p is pointing to the first node
  if (this->firstBook == p)
    {
    this->firstBook = p->bookOnRight;
    this->firstBook->bookOnLeft = NULL;
    delete p;
    this->count--;
    return true;
    }

  //p is pointing to the last node
  if (p == this->lastBook)
    {
    this->lastBook = p->bookOnLeft;
    this->lastBook->bookOnRight = NULL;
    delete p;
    this->count--;
    return true;
    }

  //p is pointing to node between first and last
  p->bookOnLeft->bookOnRight = p->bookOnRight;
  p->bookOnRight->bookOnLeft = p->bookOnLeft;
  delete p;
  this->count--;
  return true;
  }


void test_reclaimSpace(void)
  {
  cout << "=================\n";
  cout << "test_reclaimSpace\n";
  cout << "=================\n";

  for (int t=1; t<=TEST_COUNT; t++)
    {
    cout << "Test Count " << t << endl;

    CShelf myShelf('f');

    cout << "CShelf myShelf('f'); executed\n";

    for (int b=1; b<=TEST_COUNT; b++)
      {
      if (myShelf.reclaimableSpace() == 0) 
        break;
      //myShelf.displayBrief();   cout << endl;
      myShelf.displaySimple();  cout << endl;
      //myShelf.displayDetailed();cout << endl;

      int spaceToReclaim = rand()%((MAX_SHELF_WIDTH-MIN_SHELF_WIDTH)/8+1);
      int spaceReclaimed = myShelf.reclaimSpace(spaceToReclaim);

      cout << "       Space to reclaim = " << spaceToReclaim << endl;
      cout << "       Space reclaimed  = " << spaceReclaimed << endl;

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

      if (myShelf.isEmpty())
        break;
      }

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


/*int CShelf::reclaimSpace(int spaceToClaim)
Description:
  reclaim empty space on the shelf due removal of books
  return the amount of space reclaimed
Example:
  000111000222, 2 => 0111000222, 2
  111222, 2       => 111222, 0
  000111000222, 6 => 111222, 6
  000111000222, 7 => 111222, 6
  000111000222, 0 => 000111000222, 0
  111222223333, 5 => 111222223333, 0
Algorithm:
  if space <=0 then
    return 0
  if widthOccupied >= widthShelf then
    return 0
  spaceClaimed = 0
  from first entry to the last entry do the following
    if entry is empty space then
        if entry width < (spaceToClaim-spaceClaimed) then 
            spaceClaimed += entry width
            delete this entry
          elseif entry width == (spaceToClaim-spaceClaimed) then 
            spaceClaimed += entry width
            delete this entry
            return spaceClaimed
          elseif entry width > (spaceToClaim-spaceClaimed) then 
            decrease the entry width by (spaceToClaim-spaceClaimed)
            spaceClaimed += (spaceToClaim-spaceClaimed)
            return spaceClaimed
          end if
      end if
    go to the next entry
    end loop

*/
int CShelf::reclaimSpace(int spaceToClaim)
  {
  //cout << "????   space to reclaim " << spaceToClaim << endl;
  if (spaceToClaim <=0)
    return 0;

  if (this->widthOccupied >= this->width)
    return 0;

  int spaceClaimed = 0;
  CBook *p=this->firstBook; 
  while (p!=NULL)
    {
    //cout << "????   p= " << p << endl;
    if (p->id == 0)
        {
        //cout << "************** p->id = " << p->id << "  p->width = " << p->width << endl;
        if (p->width < (spaceToClaim-spaceClaimed))
            {
            //cout << "????   if (p->width < (spaceToClaim-spaceClaimed))\n";
            spaceClaimed += p->width;
            CBook *q = p;
            p = p->bookOnRight;
            this->remove(q);
            }
          else if (p->width == (spaceToClaim-spaceClaimed))
            {
            //cout << "????   else if (p->width == (spaceToClaim-spaceClaimed))\n";
            spaceClaimed += p->width;
            this->remove(p);
            return spaceClaimed;
            }
          else if (p->width > (spaceToClaim-spaceClaimed))
            {
            //cout << "????   else if (p->width > (spaceToClaim-spaceClaimed))\n";
            p->width -= (spaceToClaim-spaceClaimed);
            spaceClaimed += (spaceToClaim-spaceClaimed);
            return spaceClaimed;
            }
        }
      else
        {
        //cout << "????   p=p->bookOnRight;\n";
        p=p->bookOnRight;
        }
    }
  
  //cout << "????   Getting out of reclaimSpace\n";
  return spaceClaimed;
  }


//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 test_constructorFragmented(void)
  {
  cout << "--------------------------\n";
  cout << "test_constructorFragmented\n";
  cout << "--------------------------\n";
  for (int t=1; t<=TEST_COUNT; t++)
    {
    CShelf myShelf('f');

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


void test_constructorRandom(void)
  {
  cout << "---------------\n";
  cout << "test_constructorRandom\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 if ('f' == ch) //fragmented (with empty bookshelf
    {
    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";
      }

    //fragment this bookshelf
    CBook *p = this->lastBook;

    if (p != NULL)
      {
      while (p->bookOnLeft != NULL)
        {
        p = p->bookOnLeft;
        if (rand()%2 == 1)
          {
          p->id = 0;
          this->widthOccupied -=p->width;
          }
        }
      }
    }
   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 test_remove_byID(void)
  {
  cout << "==========\n";
  cout << "test_remove_byID\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:
  bookID is <= 0
  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 bookID is 0 or negative return false
  if (bookID <= 0)
    return false;

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

  cout << "First to last order:\n";
  CBook *p;
  p = this->firstBook;
  while (p != NULL)
    {
    cout << "@" << p 
         <<" [" << p->bookOnLeft << ", "
         << p->id << ", " 
         << p->width << ", "
         << p->bookOnRight << "]\n";
    p = p->bookOnRight;
    }
 
  cout << "\nLast to first order:\n";
  p = this->lastBook;
  while (p != NULL)
    {
    cout << "@" << p 
         <<" [" << p->bookOnLeft << ", "
         << p->id << ", " 
         << p->width << ", "
         << p->bookOnRight << "]\n";
    p = p->bookOnLeft;
    }
 
  }


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

  p = this->firstBook;
  cout << "[c:" << this->count << " w:"
    << this->width <<   " o:"
    << this->widthOccupied <<   " e:"
    << this->reclaimableSpace() << "]=";

  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 test_insertAtLeft(void)
  {
  display_test_header("test_insertAtLeft");

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


void test_constructorWidth(void)
  {
  char *test_name = "test_constructorWidth";
  display_test_header(test_name);

  for (int t=1; t<=TEST_COUNT; t++)
    {
    int width = rand()%(MAX_SHELF_WIDTH-MIN_SHELF_WIDTH+1) + MIN_SHELF_WIDTH;
    CShelf myShelf(width);

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


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


void test_constructorDefault(void)
  {
  char *test_name = "test_constructorDefault";
  display_test_header(test_name);

  for (int t=1; t<=TEST_COUNT; t++)
    {
    CShelf myShelf;

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


void display_test_header(char *test_name)
  {
  cout << '+';
  for (unsigned int i=1; i<=strlen(test_name)+2; i++)
    cout << '-';

  cout << '+' << endl;
  
  cout << "| " << test_name << " |" << endl;

  cout << '+';
  for (unsigned int i=1; i<=strlen(test_name)+2; i++)
    cout << '-';

  cout << '+' << endl << endl;
  }


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