/* slist.cc */

#include "slist.h"
#include <iostream.h>

class SListNode {
public:
  SListNode(int first, SListNode *rest): item(first), next(rest) {
  };
  SListNode(int first): item(first), next(NULL) {
  };
  int item;
  SListNode *next;
};

// Constructs an empty SortedList.
SortedList::SortedList(): size(0), head(NULL) {
}

// Constructs a SortedList that is a deep copy of l.
SortedList::SortedList(const SortedList &l) : size(l.size) {
  if (l.head == NULL) {     
    // original list is empty
    head = NULL;
  } else {
    head = copyAll(l.head);
  }
}

// Deallocates a SortedList.
SortedList::~SortedList() {
  destroyAll(head);
}

// Returns true if this SortedList is empty, false otherwise.
bool SortedList::isEmpty() {
  return size == 0;
}

// Returns the length of this list.
int SortedList::length() {
  return size;
}

// Inserts newItem into the list so that the list remains sorted.  If
//   NewItem is already in the list, the new copy should be inserted in front
//   of the previous copy(s) of the same value.
// Precondition:  The list is sorted.
void SortedList::insert(int newItem) {
  size = size + 1;
  SListNode *curr = head;
  if (head == NULL || head->item >= newItem) {
    head = new SListNode(newItem, curr);
    return;
  } else {
    SListNode *prev = head;
    curr = prev->next;
    while (curr != NULL && curr->item < newItem) {
      prev = curr;
      curr = curr->next;
    }
    prev->next = new SListNode(newItem, curr);
  }
}

// Returns true if elem is in the list, false if not.
bool SortedList::isIn(int elem) {
  // Part I:  replace the following line with your solution.
  return false;
}

// Removes all instances of elem in this list.
void SortedList::remove(int elem) {
  // Part II:  fill in your solution here.
}

// Merges this list and "sl" into a sorted list containing the elements of
//   both input lists.  Afterward, this list contains the merged list and
//   sl is empty.
// Precondition:  This SortedList and sl are both sorted.
void SortedList::merge(SortedList *sl) {
  // Part III:  fill in your solution here.
}

// Prints the list using the syntax "[ ]" for an empty list and "[ 2 3 4 ]"
//   (for example) for a list of three integers.
void SortedList::print() {
  SListNode *tmp = head;
  cout << "[ ";
  while (tmp != NULL) {
    cout << tmp->item << " ";
    tmp = tmp->next;
  }
  cout << "]" << endl;
}

// Returns a copy of "ln" and all the list nodes that follow it in the list.
SListNode *SortedList::copyAll(SListNode *ln) {
  if (ln == NULL) {
    return ln;
  } else {
    return new SListNode(ln->item, copyAll(ln->next));
  }
}

// Deallocates "ln" and all the list nodes that follow it in the list.
void SortedList::destroyAll(SListNode *ln) {
  if (ln == NULL) {
    return;
  } else {
    destroyAll(ln->next);
    delete ln;
  }
}