// Demonstrating the generic merge algorithm with an array, a
// list, and a deque.
#include <iostream>
#include <string.h>
#include <assert.h>
#include <list>
#include <deque>
#include <algorithm>
using namespace std; 

list<char> lst(const char* s)
  // Return list<char> containing the characters of s
  // (not including the terminating null).
{
  list<char> x;
  while (*s != '\0')
    x.push_back(*s++);
  return x;
}

deque<char> deq(const char* s)
  // Return deque<char> containing the characters of s
  // (not including the terminating null).
{
  deque<char> x;
  while (*s != '\0')
    x.push_back(*s++);
  return x;
}

int main()
{
  cout << "Demonstrating generic merge algorithm with "
       << "an array, a list, and a deque." << endl;
  char* s = "acegikm";
  int len = strlen(s);
  list<char> list1 = lst("bdfhjlnopqrstuvwxyz");

  // Initialize deque1 with 26 copies of the letter x:
  deque<char> deque1(26, 'x');

  // Merge array s and list1, putting result in deque1:
  merge(&s[0], &s[len], list1.begin(), list1.end(),
        deque1.begin());
  assert(deque1 == deq("abcdefghijklmnopqrstuvwxyz"));
  return 0;
}
