/* assertdebug.cpp - The assert statement allows us to check
 *               that some predicate is true. If so the program
 *               continues normally. If not, the program terminates
 *               printing the assertion that failed.
 *               If you want to disable the assert mechanism, define NDEBUG
 *               before the statement "#include <cassert>". NDEBUG of 
 *               course is useful also for printing debugging information
 *               only during debugging.
 *               Here we see the use of assert/debug mechanism in the
 *               context of a merge function. We will define NDEBUG 
 *               in the "production" code, we will leave it undefined
 *               while debugging. BEWARE: some people believe that 
 *               the assert checking should be done at all times.
 *
 *              The symbol NDEBUG can be set on the command line.
 *              For example we can eliminate debugging with
 *                    % g++ -DNDEBUG assertdebug.cpp
 *                    % a.out 
 */

#include <iostream>

//#define NDEBUG   //assert is checked only when NDEBUG is not defined
#include <cassert> //in C you would say include <assert.h>

// Return true iff the first n elements of a are sorted in non 
// decreasing order.
bool isSorted(const int a[], int n)
{
  for (int k = 0; k < n-1; ++k) {
    if (a[k] > a[k+1]) return false;
  }
  return true;
}

// Store in c the merge of the sorted sequences a and b.
// We assume that a, b, c have respectively na, nb,
// and nc elements. 
void merge(const int a[], int na, const int b[], int nb, int c[], int nc)
{
  assert(nc >= na+nb);
  assert(isSorted(a, na));
  assert(isSorted(b, nb));
  int cursora(0), cursorb(0), cursorc(0);

  while (cursora < na && cursorb < nb) 
    if (a[cursora] <= b[cursorb])
      c[cursorc++] = a[cursora++];
    else
      c[cursorc++] = b[cursorb++];
  
  while (cursora < na) 
    c[cursorc++] = a[cursora++];

  while (cursorb < nb)
    c[cursorc++] = b[cursorb++];
}

void main(void){
  int table1[] = {1, 3, 5, 7, 9};
  int table2[] = {0, 2, 4, 6, 8, 9, 10, 12};
  int table3[20];
  int n1(5), n2(8), n3(20);

#ifndef NDEBUG  // Thus this printing is done only when debugging
  cout << "table 1: " << endl;
    for (int k = 0; k<n1; ++k) 
      cout << '\t' << table1[k];
    cout << endl << endl;
    cout << "table 2: " << endl;
    for (int k = 0; k<n2; ++k) 
      cout << '\t' << table2[k];
    cout << endl << endl;
#endif

  merge(table1, n1, table2, n2, table3, n3);
  cout << "The merged table is: " << endl;
  for (int k = 0; k<n1+n2; ++k) 
    cout << '\t' << table3[k];
  cout << endl << endl;
}