// Created by Igor L. Markov, 010123

/*  To compile this program, save it into  merge_examples.cxx
    and type   g++ -Wall -o merge_examples merge_examples.cxx
    Assuming compilation succeeds, this will create executable 
    merge_examples; print out the text of the program, run it,
    and print out the output. Go over the text, keeping track
    of what is being printed
*/

//  This program is all in one file to make it easier for you
//  to download/compile/print out/etc --- your homeworks and
//  projects need to be structured better, e.g., as suggested
//  in Proto.

#include <iostream.h>

#include <vector>
#include <list>
#include <algorithm>

/*
    This program gives sample implementations 
    of set_union(), aka no_dup_merge, and multiset_union(), aka merge.
    Both functions assume that a constant N is defined,
    which is why they are not completely self-contained
    (cannot be cut and pasted into an arbitrary file).

    In you homework, you will need to write similar implementations
    but will need to pass the sizes of containers to each function.

    This program also illustrates the use of STL for the same functions
*/

const unsigned N=9;

void eecs380_merge(const int *in1, const int *in2, int *out)
// merges array in1 with array in2, and writes results into array out
// assumption: arrays in1 and in2 have sizes N
// as a result, array out will always have size 2*N
{
   unsigned i,j,k;
   for(i=0, j=0, k=0; i<N && j<N; )
   { // curly braces unnecessary in this case, but useful to avoid confusion
       if (in1[i]<in2[j]) out[k++]=in1[i++];
       else               out[k++]=in2[j++];
   }
   while(i<N) out[k++]=in1[i++];
   while(j<N) out[k++]=in2[j++];
}

unsigned eecs380_no_dup_merge(const int *in1, const int *in2, int *out)
// merges array in1 with array in2, , and writes results into array out
// however, if the same number is mentioned in both arrays, it only gets
//   copied from one of them
// assumption: arrays in1 and in2 have sizes N
//   the size of array out (the number of elements copied) can be anywhere
//   from N to 2*N
{
   unsigned i,j,k;
   for(i=0, j=0, k=0; i<N && j<N; )
   { // curly braces unnecessary in this case, but useful to avoid confusion
       if (in1[i]<in2[j])       out[k++]=in1[i++];
       else if (in1[i]==in2[j]) { out[k++]=in1[i++]; j++; }
       else                     out[k++]=in2[j++];
   }
   while(i<N) out[k++]=in1[i++];
   while(j<N) out[k++]=in2[j++];
   return k;
}

void printArray(int *in, unsigned size)
{
   unsigned k;
   for(k=0; k<size; k++) cout << "  " << in[k];
   cout << endl;
}

void printVector(vector<int> in)
{
   unsigned k;
   for(k=0; k < in.size(); k++) cout << "  " << in[k];
   cout << endl;
}

void printList(list<int> in)
{
   list<int>::iterator listIt;
   for(listIt=in.begin(); listIt != in.end(); listIt++) 
       cout << "  " << *listIt;
   cout << endl;
}

int main()
{
  // note that dynamically allocated arrays cannot be initialized like this
  // however, you will need to work with dynamically allocated arrays in HW
  int a[N]={-12,-8,-8,-3,0,5,100,101,105}; 
  int b[N]={-11,-9,-8,-3,0,5,100,101,101};

  int a1[N]={-12,-9,-7,-1,0,5, 96, 98,105};
  int b1[N]={-11,-9,-8,-3,0,5,100,101,105};

  int res[2*N];  // uninitialized

  cout << " ** First, consider two sorted arrays WITH repetitions" << endl;
  cout << " Array a: ";
  printArray(a,N);
  cout << " Array b: ";
  printArray(b,N);

  eecs380_merge(a,b,res);
  cout << " Result of eecs380_merge(a,b): ";
  printArray(res,2*N);

  unsigned newSize=eecs380_no_dup_merge(a,b,res);
  cout << " Result of eecs380_no_dup_merge(a,b): ";
  printArray(res,newSize);

  cout << " ** Now, consider two sorted arrays WITHOUT repetitions" << endl;
  cout << " Array a1: ";
  printArray(a1,N);
  cout << " Array b1: ";
  printArray(b1,N);

  eecs380_merge(a1,b1,res);
  cout << " Result of merge(a1,b1): ";
  printArray(res,2*N);

  newSize=eecs380_no_dup_merge(a1,b1,res);
  cout << " Result of eecs380_no_dup_merge(a1,b1): ";
  printArray(res,newSize);
// ===========================================================================

  cout << " =============================================================" 
       << endl;
  cout << " ** Do the same ops using STL ..."<< endl;
  cout << " ** First, using same arrays: "<<endl;

  merge(a1,a1+N,b1,b1+N,res);
  cout << " Result of merge(a1,b1,res): ";
  printArray(res,2*N);

  int *endPtr=set_union(a1,a1+N,b1,b1+N,res);  
  // endPtr is a special case of an "iterator", we'll get to iterators soon
  cout << " Result of set_union(a1,b1,res): ";
  printArray(res,endPtr-res);
  
  cout << " ** Next, using STL's vectors (expandable arrays): "<<endl;

  vector<int>  vec_a1(N), vec_b1(N), vec_res(2*N);
  copy(a1,a1+N,vec_a1.begin());
  copy(b1,b1+N,vec_b1.begin());

  cout << " vector vec_a1, copied from a1: ";
  printVector(vec_a1);   
  cout << " vector vec_b1, copied from b1: ";
  printVector(vec_b1);   

  merge(vec_a1.begin(),vec_a1.end(),vec_b1.begin(), vec_b1.end(), vec_res.begin());
  cout << " Result of merge(vec_a,vec_b,vec_res): ";
  printVector(vec_res);   

  endPtr=set_union(vec_a1.begin(),vec_a1.end(),vec_b1.begin(), vec_b1.end(), vec_res.begin());
  vec_res.resize(endPtr-vec_res.begin());
  cout << " Result of set_union(vec_a,vec_b,vec_res): ";
  printVector(vec_res);   

  cout << " ** Next, using STL's lists : "<<endl;

  list<int>  list_a1(N), list_b1(N), list_res(2*N);
  copy(a1,a1+N,list_a1.begin());
  copy(b1,b1+N,list_b1.begin());

  cout << " list list_a1, copied from a1: ";
  printList(list_a1);   
  cout << " list list_b1, copied from b1: ";
  printList(list_b1);   

  merge(list_a1.begin(),list_a1.end(),list_b1.begin(), list_b1.end(), list_res.begin());
  cout << " Result of merge(list_a,list_b,list_res): ";
  printList(list_res);   

  list<int>::iterator endIt=set_union(list_a1.begin(),list_a1.end(),list_b1.begin(), list_b1.end(), list_res.begin());
  list_res.erase(endIt, list_res.end());
  cout << " Result of set_union(list_a,list_b,list_res): ";
  printList(list_res);   

  cout << " ** Note that STL's list is a double-link list.\n" 
       << " Try to get the same code working with single-linked list: slist"
       << endl;

  cout << " For more details on STL see "
       << " http://www.sgi.com/Technology/STL/ " << endl;

  return 0;
}