/**
 * Get two lists of integers from the user, then print the union of them.
 * 
 * @Author		Mario Lopez
 * @Version		1.0
 * @Date		   Feb 23 2007
 */

#include <iostream>
#include <string>
#include <list>
using namespace std;

// Function to read an inputted number
int readNumber(int &i) {
   char tempChar;
   
   tempChar = cin.get();
   
   // Makes sure the inputted stream is an integer
   if( tempChar > '0' && tempChar < '9' )
      cin.unget();
   else if( tempChar == '\n')
      return 0;
   cin >> i;
   return 1;
}

int main() {
   list<int> L1, L2, unionList;
   int tempInt, totalNum = 0;
   
   cout << "Input a sorted list of integers for List 1:" << endl;
   
   // Call the function to read in the numbers and put them in the list
   while(readNumber(tempInt))
      L1.push_back(tempInt);
   
   cout << "Input a sorted list of integers for List 2:" << endl;
   
   // Call the function to read in the numbers and put them in the list
   while(readNumber(tempInt))
      L2.push_back(tempInt);
   
   list<int>::iterator element1, element2;
   
   element1 = L1.begin();
   element2 = L2.begin();
   
   // Go through both lists until one of them is finished
   while( element1 != L1.end() && element2 != L2.end() ) {
      // If List2 element should go next
      if( *element1 > *element2 ) {
         unionList.push_back(*element2);
         element2++;
      }
      // If List1 element should go next
      else if( *element1 < *element2 ) {
         unionList.push_back(*element1);
         element1++;
      }
      // If both lists have same value
      else {
         unionList.push_back(*element1);
         element1++;
         element2++;
      }
   }
   
   // Finish up the remaining list.
   // Since time complexity isn't an issue here, I wrote the shortest solution
   //     for this part.
   while(true) {
      // If List1 wasn't finished writing to the final list
      if( element1 != L1.end() ) {
         unionList.push_back(*element1);
         element1++;
      }
      // If List2 wasn't finished writing to the final list
      else if( element2 != L2.end() ){
         unionList.push_back(*element2);
         element2++;
      }
      // Get out of while loop when both are done
      else break;
   }
   
   cout << "The union of those two lists is:" << endl;
   
   // Reusing an existing variable: element1
   // Go through the new list to print the output
   for( element1 = unionList.begin(); element1 != unionList.end(); element1++ )
      cout << *element1 << " ";
   cout << endl;

   return 0;
}