/**************************************************************** 
 * PrLinkedListImpl.cpp
 *
 * This is an implementation of linked list methods.
 *
 * A generic priority list (increasing order).     
 *
 ****************************************************************/

/*
 * modification history
 *----------------------
 *
 * 02/19/98: K.C. Chang: created.
 */

#include "PrLinkedListImpl.h" 
#include "PrBitmap.h"

PrLinkedListImpl::PrLinkedListImpl (int maxLength)
: maxLength_(maxLength), items_(0) 
{
    assert(maxLength_>=0);

    sentinel_ = new PrListEntry(0);
    sentinel_->prevEntry(sentinel_);
    sentinel_->nextEntry(sentinel_);

    if (maxLength_ != PR_LINKEDLISTIMPL_SIZE_UNLIMITED)
      {
	  bitmap_ = new PrBitmap(maxLength_);
	  heap_ = new PrListEntry[maxLength_];
	  for (int i=0;i<maxLength_;i++)
	    heap_[i].id(i);
      }
}

/*
 * ~PrLinkedListImpl
 * destructor deletes entries in list not items 
 */
PrLinkedListImpl::~PrLinkedListImpl ()
{
    if (maxLength_ != PR_LINKEDLISTIMPL_SIZE_UNLIMITED)
      {
	  assert(items_ == maxLength_ - bitmap_->numClear());
	  delete[] heap_;
	  delete bitmap_;
      }
    else
      {
	  while(items_ > 0)
	    deleteItem(HeadEntry()->data());
      }

    delete sentinel_;
}

/*
 * item
 * return item if found, otherwise return null
 */
void *
PrLinkedListImpl::item (void *AVoid) const
{
    PrListEntry *curEntry = FindEntry(AVoid);

    if (curEntry != NULL)
      return AVoid;
    else
      return (NULL);    // did not find the item
}

/*
 * firstItem
 * return head of list and set for nextItem () call
 */
void *
PrLinkedListImpl::firstItem () const
{
  void *item = HeadEntry()->data();
  ((PrLinkedListImpl *)this)->curEntry_ = HeadEntry()->nextEntry ();
  return (item);
}

/*
 * nextItem
 * return next item and update the current entry
 */
void *
PrLinkedListImpl::nextItem () const
{
  void *item = curEntry_->data();
  ((PrLinkedListImpl *)this)->curEntry_ = curEntry_->nextEntry();

  return (item);
}

/*
 * newItem
 * add a new item to the list                          
 */
void
PrLinkedListImpl::newItem (void *NewVoid)
{
    // insert newEntry front
    PrListEntry *curEntry  = TailEntry();

    for(int i=0;i<items_;i++)
      { 
	  //	   int compare(void *x, void *y) 
	  //		returns 1 if x > y
	  //		returns 0 if x == y
	  //		returns -1 if x < y
	  // increasing order
	  if (compare(NewVoid,curEntry->data()) < 0)
	    curEntry = curEntry->prevEntry();
	  else
	    break;
      }

    // insert newEntry before curEntry
    PrListEntry *newEntry;
    if (maxLength_ != PR_LINKEDLISTIMPL_SIZE_UNLIMITED)
      {
	  int n=bitmap_->findAndSet();
	  assert(n>-1);
	  newEntry = heap_+n;
	  assert(n == newEntry->id());
	  newEntry->data(NewVoid);
      }
    else
      newEntry  = new PrListEntry (NewVoid);

    newEntry->nextEntry(curEntry->nextEntry());
    newEntry->prevEntry(curEntry);

    curEntry->nextEntry()->prevEntry(newEntry);
    curEntry->nextEntry(newEntry);
  
    items_++;
}

/*
 * deleteItem
 * remove item from list but don't delete it
 */
void *
PrLinkedListImpl::deleteItem (void *DeleteVoid)
{
    PrListEntry *curEntry = FindEntry(DeleteVoid);

    if (curEntry != NULL)
      {
	  curEntry->prevEntry()->nextEntry(curEntry->nextEntry());
	  curEntry->nextEntry()->prevEntry(curEntry->prevEntry());
      
	  if (maxLength_ != PR_LINKEDLISTIMPL_SIZE_UNLIMITED)
	    bitmap_->clear(curEntry->id());
	  else
	    delete curEntry;

	  items_--;
      
	  return (DeleteVoid);
      }
    else 
      return (NULL);
}

// private methods

inline PrListEntry *
PrLinkedListImpl::HeadEntry() const
{
  return sentinel_->nextEntry();
}

inline PrListEntry *
PrLinkedListImpl::TailEntry() const
{
  return sentinel_->prevEntry();
}

inline PrListEntry *
PrLinkedListImpl::FindEntry(void *AVoid) const
{
    PrListEntry *curEntry  = HeadEntry();
    for(int i=0;i<items_;i++)
      {
        if (curEntry->data() != AVoid)
	  curEntry  = curEntry->nextEntry ();
	else
	  return curEntry;
      }
    return (NULL);     // did not find the item
}


