#include <stdio.h>
#include "algorithm.h"
#include "functional.h"
#include "list.h"
#include "vector.h"

#include "algorithm.c++"

void print_int(int i)
{
  printf("%i\n", i);
}

bool equal_plus_1(int x, int y)
  { return x == y+1; }

bool lt_plus_1(int x, int y)
  { return x < y+1; }

bool equal_3_or_4(int x, int y)
  { return (x == 3 || x == 4) && (y == 3 || y == 4); }

bool equal_and_lt_5(int x, int y)
  { return x == y && x < 5 && y < 5; }

bool equal_or_5_and_6(int x, int y)
  { return x == y || ((x == 5 || x == 6) && (y == 5 || y == 6)); }

bool gt(int x, int y)
  { return x > y; }

bool lt(int x, int y)
  { return x < y; }

bool equal_7(int x)
  { return x == 7; }

bool lt_5(int x)
  { return x < 5; }

int add_1(int x)
  { return x+1; }

int add(int x, int y)
  { return x+y; }

int gen_fn()
  {
    static int count = 0;
    return count++;
  }

TEMPLATE_ptr_fun_unary(int, bool)
TEMPLATE_ptr_fun_binary(int, int, bool)

pointer_to_unary_function<int, bool> equal_7_fn_obj(equal_7);

int sequence[] =
{
  0,
  1,
  2,
  3,
  4,
  5,
  6,
  7,
  8,
  8,
  9
};

int sequence2[] =
{
  0,
  1,
  2,
  3,
  4,
  5,
  6,
  7,
  8,
  9,
  9
};

int sub_sequence[] =
{
  3,
  4,
  5,
  6,
};

int merge_seq_1[] =
{
  1,
  2,
  5,
  8,
  9
};

int merge_seq_2[] =
{
  1,
  3,
  6,
  7,
  8
};

int merge_seq_3[] =
{
  1,
  2,
  5,
  8,
  9,
  1,
  3,
  6,
  7,
  8
};

int disjoint_seq[] =
{
  12,
  13,
  15,
  23,
  34
};

int main()
{
  list<int> pl(sequence, sequence+11);
  list<int> pl2(sequence2, sequence2+11);
  list_iterator<int> i;

  for_each(pl.begin(), pl.end(), print_int);
  printf("\n");

  // should print '5'
  i = find(pl.begin(), pl.end(), 5);
  print_int(*i);
  printf("\n");

  // should print '7'
  i = find_if(pl.begin(), pl.end(), equal_7);
  print_int(*i);
  printf("\n");

  // should print '6'
  i = find_end(pl.begin(), pl.end(), sub_sequence, sub_sequence+4);
  print_int(*i);
  printf("\n");

  // should print '7'
  i = find_end(pl.begin(), pl.end(), sub_sequence, sub_sequence+4, equal_plus_1);
  print_int(*i);
  printf("\n");

  // should print '3'
  i = find_first_of(pl.begin(), pl.end(), sub_sequence, sub_sequence+4);
  print_int(*i);
  printf("\n");

  // should print '4'
  i = find_first_of(pl.begin(), pl.end(), sub_sequence, sub_sequence+4, equal_plus_1);
  print_int(*i);
  printf("\n");

  // should print '8'
  i = adjacent_find(pl.begin(), pl.end());
  print_int(*i);
  printf("\n");

  // should print '3'
  i = adjacent_find(pl.begin(), pl.end(), equal_3_or_4);
  print_int(*i);
  printf("\n");

  // should print '2'
  int n = 0;
  count(pl.begin(), pl.end(), 8, n);
  print_int(n);
  printf("\n");

  // should print '1'
  n = 0;
  count_if(pl.begin(), pl.end(), equal_7_fn_obj, n);
  print_int(n);
  printf("\n");

  // should print '8, 9'
  pair<list_iterator<int>, list_iterator<int> > ip = mismatch(pl.begin(), pl.end(), pl2.begin());
  print_int(*(ip.first));
  print_int(*(ip.second));
  printf("\n");

  // should print '5, 5'
  ip = mismatch(pl.begin(), pl.end(), pl2.begin(), equal_and_lt_5);
  print_int(*(ip.first));
  print_int(*(ip.second));
  printf("\n");

  // should print 'false'
  if(equal(pl.begin(), pl.end(), pl2.begin()))
    printf("true\n");
  else
    printf("false\n");
  printf("\n");

  // should print 'true'
  if(equal(pl.begin(), pl.end(), pl.begin()))
    printf("true\n");
  else
    printf("false\n");
  printf("\n");

  // should print 'false'
  if(equal(pl.begin(), pl.end(), pl2.begin(), equal_and_lt_5))
    printf("true\n");
  else
    printf("false\n");
  printf("\n");

  // should print '3'
  i = search(pl.begin(), pl.end(), sub_sequence, sub_sequence+4);
  print_int(*i);
  printf("\n");

  // should print '4'
  i = search(pl.begin(), pl.end(), sub_sequence, sub_sequence+4, equal_plus_1);
  print_int(*i);
  printf("\n");

  // should print '8'
  i = search_n(pl.begin(), pl.end(), 2, 8);
  print_int(*i);
  printf("\n");

  // should print '8'
  i = search_n(pl.begin(), pl.end(), 2, 7, equal_plus_1);
  print_int(*i);
  printf("\n");

  // copy exercised in vector<T> and deque<T>

  // copy_backward exercised in vector<T> and deque<T>

  // swap excercised almost everywhere

  // should print '9, 1, 2, 3, 4, 5, 6, 7, 8, 8, 0'
  iter_swap(pl.begin(), pl.rbegin());
  for_each(pl.begin(), pl.end(), print_int);
  printf("\n");

  // should print '10, 2, 3, 4, 5, 6, 7, 8, 9, 9, 1'
  transform(pl.begin(), pl.end(), pl2.begin(), add_1);
  for_each(pl2.begin(), pl2.end(), print_int);
  printf("\n");

  // should print '18, 2, 4, 6, 8, 10, 12, 14, 16, 16, 0'
  transform(pl.begin(), pl.end(), pl.begin(), pl2.begin(), add);
  for_each(pl2.begin(), pl2.end(), print_int);
  printf("\n");

  // should print '9, 1, 2, 19, 4, 5, 6, 7, 8, 8, 0'
  replace(pl.begin(), pl.end(), 3, 19);
  for_each(pl.begin(), pl.end(), print_int);
  printf("\n");

  // should print '9, 1, 2, 19, 4, 5, 6, 19, 8, 8, 0'
  replace_if(pl.begin(), pl.end(), equal_7, 19);
  for_each(pl.begin(), pl.end(), print_int);
  printf("\n");

  // should print '9, 1, 2, 7, 4, 5, 6, 7, 8, 8, 0'
  replace_copy(pl.begin(), pl.end(), pl2.begin(), 19, 7);
  for_each(pl2.begin(), pl2.end(), print_int);
  printf("\n");

  // should print '9, 1, 2, 23, 4, 5, 6, 23, 8, 8, 0'
  replace_copy_if(pl2.begin(), pl2.end(), pl2.begin(), equal_7, 23);
  for_each(pl2.begin(), pl2.end(), print_int);
  printf("\n");

  // should print '17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17'
  fill(pl.begin(), pl.end(), 17);
  for_each(pl.begin(), pl.end(), print_int);
  printf("\n");

  // should print '5, 5, 5, 5, 17, 17, 17, 17, 17, 17, 17'
  fill_n(pl.begin(), 4, 5);
  for_each(pl.begin(), pl.end(), print_int);
  printf("\n");

  // should print '0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10'
  generate(pl.begin(), pl.end(), gen_fn);
  for_each(pl.begin(), pl.end(), print_int);
  printf("\n");

  // should print '11, 12, 13, 14, 4, 5, 6, 7, 8, 9, 10'
  generate_n(pl.begin(), 4, gen_fn);
  for_each(pl.begin(), pl.end(), print_int);
  printf("\n");

  // should print '11, 13, 14, 4, 5, 6, 7, 8, 9, 10, 0'
  fill(pl2.begin(), pl2.end(), 0);
  remove_copy(pl.begin(), pl.end(), pl2.begin(), 12);
  for_each(pl2.begin(), pl2.end(), print_int);
  printf("\n");

  // should print '11, 12, 13, 14, 4, 5, 6, 8, 9, 10, 0'
  fill(pl2.begin(), pl2.end(), 0);
  remove_copy_if(pl.begin(), pl.end(), pl2.begin(), equal_7);
  for_each(pl2.begin(), pl2.end(), print_int);
  printf("\n");

  // should print '11, 13, 14, 4, 5, 6, 7, 8, 9, 10, 10'
  remove(pl.begin(), pl.end(), 12);
  for_each(pl.begin(), pl.end(), print_int);
  printf("\n");

  // should print '11, 13, 14, 4, 5, 6, 8, 9, 10, 10, 10'
  remove_if(pl.begin(), pl.end(), equal_7);
  for_each(pl.begin(), pl.end(), print_int);
  printf("\n");

  // should print '11, 13, 14, 4, 5, 6, 8, 9, 10, 0, 0'
  fill(pl2.begin(), pl2.end(), 0);
  unique_copy(pl.begin(), pl.end(), pl2.begin());
  for_each(pl2.begin(), pl2.end(), print_int);
  printf("\n");

  // should print '11, 13, 14, 4, 5, 8, 9, 10, 0, 0, 0'
  fill(pl2.begin(), pl2.end(), 0);
  unique_copy(pl.begin(), pl.end(), pl2.begin(), equal_or_5_and_6);
  for_each(pl2.begin(), pl2.end(), print_int);
  printf("\n");

  // should print '5, 6, 8, 9, 10, 6, 8, 9, 10, 10, 10'
  fill_n(pl.begin(), 4, 5);
  unique(pl.begin(), pl.end());
  for_each(pl.begin(), pl.end(), print_int);
  printf("\n");

  // should print '5, 8, 9, 10, 6, 8, 9, 10, 10, 10, 10'
  unique(pl.begin(), pl.end(), equal_or_5_and_6);
  for_each(pl.begin(), pl.end(), print_int);
  printf("\n");

  // should print '10, 10, 10, 10, 9, 8, 6, 10, 9, 8, 5'
  reverse(pl.begin(), pl.end());
  for_each(pl.begin(), pl.end(), print_int);
  printf("\n");

  // should print '5, 8, 9, 10, 6, 8, 9, 10, 10, 10, 10'
  reverse_copy(pl.begin(), pl.end(), pl2.begin());
  for_each(pl2.begin(), pl2.end(), print_int);
  printf("\n");

  // should print '10, 10, 10, 9, 8, 6, 10, 9, 8, 5, 10'
  list_iterator<int> middle = pl.begin();
  ++middle;
  rotate(pl.begin(), middle, pl.end());
  for_each(pl.begin(), pl.end(), print_int);
  printf("\n");

  // should print '10, 10, 9, 8, 6, 10, 9, 8, 5, 10, 10'
  rotate_copy(pl.begin(), middle, pl.end(), pl2.begin());
  for_each(pl2.begin(), pl2.end(), print_int);
  printf("\n");
}
