/*
 *        File: orderedlist.cpp
 *        Author: Leonid Reyzin
 *        Date:  January 2003
 *        Class: CS112B1
 *        Assignment: Implementation of an ordered linked list
 * --------------------------------------------------------------------
 */

#include "orderedlist.h"      /* declarations of the class */

/*------------------------------------------------------------*/

        /* OrderedListNode::OrderedListNode()  constructor
        *  Initializes a OrderedListNode to point to NULL
        */

OrderedListNode::OrderedListNode()
{
  next  = NULL;
}

/*------------------------------------------------------------*/

        /* OrderedListNode::OrderedListNode(newitem, newnext)  constructor
        *  Initializes a OrderedListNode to contain newitem and point
	*  to newnext
        */
OrderedListNode::OrderedListNode(ItemType newitem, OrderedListNode * newnext)
{
  item = newitem;
  next = newnext;
}

/*------------------------------------------------------------*/

        /* OrderedList::OrderedList  constructor
        * creates an ordered list and initializes it to empty
        */

OrderedList::OrderedList()
{
  list = NULL;
}

OrderedList::~OrderedList()
{
  Init();
}

/*------------------------------------------------------------*/

       /* OrderedList::Init:
        * Usage:  orderedlist.Init();
        * Empties and re-initializes an ordered list.
        */
bool OrderedList::Init()
{
  OrderedListNode * newlist;

  while (list != NULL) {
    newlist = list->next;
    delete list;
    list = newlist;
  }
  list=NULL;
  return true;
}

/*------------------------------------------------------------*/

       /* OrderedList::IsEmpty:
        * Usage:  if(orderedlist.IsEmpty()) {...}
        * checks whether an ordered list is empty.
        */
bool OrderedList::IsEmpty() const
{
  return (list==NULL);
}

/*------------------------------------------------------------*/

       /* OrderedList::IsFull:
        * Usage:  if(orderedlist.IsFull()) {...}
        * checks whether an ordered list is full.
	* It never happens in this implementation.
        */
bool OrderedList::IsFull() const
{ 
  return  false;
}

/*------------------------------------------------------------*/

       /* OrderedList::Insert:
        * Usage:  flag= ordered.Insert(item);
        * Inserts the item in order into the list.
        * returns true if successful, false if out of memory
        */

bool OrderedList::Insert(ItemType item)
{
  OrderedListNode *newnode, *biggernode, *smallernode=NULL;
  
  // Find the location where to insert.  At the end of this loop,
  // biggernode will point to the node after the insertion point
  // (or NULL if insertion is at the end of the list), while smallernode
  // will point to the node before the insertion point
  // (or NULL if insertion is at the beginnig of the list)
  for (biggernode = list; biggernode != NULL; biggernode = biggernode->next) {
    if (biggernode->item > item)
      break;
    smallernode = biggernode;
  }

  newnode = new OrderedListNode(item, biggernode);

  if (newnode == NULL)
    return false;

  if (smallernode == NULL)  // special case: insertion at the beginning
    list = newnode;
  else                      // general case
    smallernode->next = newnode;

  return true;
}

/*------------------------------------------------------------*/

       /* OrderedList::Smallest:
        * Usage:  flag= orderedlist.Smallest(item);
        * Gives back the smallest item in the list; returns true unless
	* the list is empty and there is nothing to return.
	* Does not modify the list.
        */

bool OrderedList::Smallest(ItemType &item) const
{
  if (IsEmpty())
    return false;
  item = list -> item;
  return true;
}

/*------------------------------------------------------------*/

       /* OrderedList::Remove:
        * Usage:  flag= orderedlist.Remove(item);
        * If the item is in the list, removes it and returns true
        * else returns false and does not change the list
        */

bool OrderedList::Remove(ItemType item)
{
  OrderedListNode *correctnode, *prevnode=NULL;
  
  // Find the location where to remove.  At the end of this loop,
  // correctnode will point to the node to remove
  // (or NULL if it does not exist), while prevnode
  // will point to the node before the node to remove
  // (or NULL if the node to remove is at the beginning of the list)
  for (correctnode = list; correctnode != NULL; 
       correctnode = correctnode->next) {
    if (correctnode->item == item)   // we found the node to remove
      break;
    if (correctnode->item > item) {  // we passed the correct spot, 
      correctnode = NULL;            // so there is no node to remove
      break;
    }
    prevnode = correctnode;
  }

  if (correctnode == NULL)
    return false;

  if (prevnode == NULL)       // special case: removal from the beginning
    list = correctnode->next;
  else
    prevnode -> next = correctnode -> next;

  delete correctnode;
  return true;
}

/* ----------- END OF FILE: orderedlist.cpp ---------- */