/*
   A program to demonstrate linked lists of strings.  The list
   is used to store a list of words in sorted (lexicographic) order.
*/


#include <iostream>
#include <string>


struct ListNode {      // A Node in a linked list of strings.
   string item;    // The string stored in this node.
   ListNode *next; // A pointer to the next node, or 0 if there is none.
};


ListNode *head = 0;  // Pointer to a linked list of strings,
                     // where the list is initially empty.


/*
 *  Insert a new string, insertItem, into a sorted linked list of strings.
 *  Precondition:  list is 0 if the list is empty, or is a pointer to the
 *     first node in the list.  All the items currently in the list are
 *     in sorted order.
 *  Postcondition:  A new node has been added to the list containing the
 *     string insertItem, and the modified list is in sorted order.
 *  
 */
void insert(ListNode* &list, string insertItem) {

   ListNode *newNode = new ListNode;  // The new node to be added to the list.

   newNode->item = insertItem;   // Put the new string into the new node.
   
   if (list == 0 || list->item >= insertItem) {
          // Insert the new node at the head of the list.
      newNode->next = list;
      list = newNode;
   }
   else {
         // Insert the new node in the middle of the list.
      ListNode *node = list;  // This pointer will be set to point to
                              // the node the precedes the new node.
      while (node->next && node->next->item < insertItem) {
            // Advance node along the list until we get to the last
            // node in the list or until the item in the following
            // node is >= insertItem.
         node = node->next;
      }
      newNode->next = node->next;   // Insert newNode after node.
      node->next = newNode;
   }
}


int main() {
   
   cout << "\nType some words and press return.\n";
   cout << "The words will be listed in increasing order.\n\n";
   cout << "? ";
   
   while (true) {
      char ch;
      while (cin.peek() == ' ' || cin.peek() == '\t') {
            // Skip spaces and tabs, but not end-of-lines.
         cin.get(ch);
      }
      if (cin.peek() == '\n') {
            // Break when we reach the end of the line.
         break;
      }
      string newitem;  // Read a word and insert it into the list.
      cin >> newitem;
      insert(head,newitem);
   }
   
   if (head == 0) {
      cout << "\nYou didn't enter any words.\n";
   }
   else {   
      cout << "\nThe words are:\n\n";
      ListNode *runner = head;
      while (runner) {
             // Print out each item in the list.
         cout << "     " << runner->item << endl;
         runner = runner->next;
      }
      cout << endl;
   }
      
}