//       CS210 - Algorithms and Data Structures I

//            Department of Computer Science

//       National University of Ireland, Maynooth

//

//           Solutions to Laboratory Exam 2

//                     Tom Naughton

//                     January 2001

//

//---------------------------------------------------------

//http://www.cs.may.ie/~tnaughton/cs210/

//=========================================================



// Problem I



  public Comparable[] merge(Comparable a[], Comparable b[]) {

    /* Function takes two sorted unique-valued arrays of Comparables and

    ** returns a (unique-valued and sorted) merged array. The returned

    ** array will be sorted, be the exact length to accomodate its elements,

    ** contain all elements that were in a[] and b[], and only contain

    ** unique elements (if an element is in both a[] and b[] then it appears

    ** only once in the returned array.

    ** If either array is null, treat as an empty array.

    ** The ordered nature of set elements admits an algorithm with O(n)

    ** copies and comparisons between elements.

    */

    Comparable newArray[];   // ref to array of merged elements

    int newSize;             // size of new array

    Comparable tempArray[];  // ref to temporary array storage

    int ca, cb;              // counters



    if (a == null) && (b == null) {

      return new Comparable[0];



    } else if (a == null) {

      return b; // could also return a copy of the elements of b



    } else if (b == null) {

      return a; // could also return a copy of the elements of a



    } else {



      /* Make the temporary storage as large as will possibly be needed:

      ** the sum of the sizes of the two arrays.

      */

      tempArray = new Comparable[(a.length + b.length)];



      newSize = 0; // so far nothing in the merged array



      ca = 0; // counter for a

      cb = 0; // counter for b

      // stop iteration only when both indexes go out of range

      while ((ca < a.length) || (cb < b.length)) {



        /* Since both arrays are sorted in ascending order, we can keep

        ** adding to the merged array any value in one array that is lower

        ** than the lowest value in the other array. If we find the

        ** same value in each, add only one of them to the mergeed array.

        ** If one array has been exhausted add all remaining elements of

        ** the other array to the merged array.

        */

        if (ca >= a.length) {

          // a[] is empty, so add next element from b[]

          tempArray[newSize] = b[cb]; // copy reference

          newSize++; // merged array has just got one bigger

          cb++;

        } else if (cb >= b.length) {

          // b[] is empty, so add next element from a[]

          tempArray[newSize] = a[ca]; // copy reference

          newSize++; // merged array has just got one bigger

          ca++;

        } else if (a[ca].compareTo(b[cb]) < 0) {

          // a[ca] must not be in b[]

          tempArray[newSize] = a[ca]; // copy reference

          newSize++; // merged array has just got one bigger

          ca++;

        } else if (a[ca].compareTo(b[cb]) > 0) {

          // b[cb] must not be in a[]

          tempArray[newSize] = b[cb]; // copy reference

          newSize++; // merged array has just got one bigger

          cb++;

        } else {

          // they must be the same, just add one of them

          tempArray[newSize] = a[ca]; // copy reference

          newSize++; // merged array has just got one bigger

          ca++;

          cb++;

        }

      }



      /* Copy newSize elements from tempArray to newArray. newArray

      ** will be exactly the right size to accomodate the merged

      ** array's contents.

      */

      newArray = new Comparable[newSize];

      ca = 0;

      while (ca < newSize) {

        newArray[ca] = tempArray[ca];

        ca++;

      }



      return newArray;

    }

  }