/* slist.h */

#ifndef _slist_h
#define _slist_h

class SListNode;                     // Warns compiler of external declaration.

class SortedList {

  // Invariants:
  //   1) The SListNodes accessible from "head" contain ints that are sorted
  //      in ascending order.
  //   2) A SortedList is never circularly linked; there is always a tail
  //      SListNode accessible from "head" whose "next" reference is null.
  //   3) "size" is equal to the number of SListNodes accessible from "head".
 private:
  int size;
  SListNode *head;

 public:
  // Constructs an empty SortedList.
  SortedList();

  // Constructs a SortedList that is a deep copy of l.
  SortedList(const SortedList &l);

  // Deallocates a SortedList.
  ~SortedList();

  // Returns true if this SortedList is empty, false otherwise.
  bool isEmpty();

  // Returns the length of this list.
  int length();

  // 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 insert(int newItem);

  // Returns true if elem is in the list, false if not.
  bool isIn(int elem);

  // Removes all instances of elem in this list.
  void remove(int elem);

  // 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 merge(SortedList *sl);

  // Prints the list using the syntax "[ ]" for an empty list and "[ 2 3 4 ]"
  //   (for example) for a list of three integers.
  void print();

 private:
  // Returns a copy of "ln" and all the list nodes that follow it in the list.
  SListNode *copyAll(SListNode *ln);

  // Deallocates "ln" and all the list nodes that follow it in the list.
  void destroyAll(SListNode *ln);
};

#endif /* _slist_h */