#include <iostream>
#include <string>
#include <utility>
#include <cassert>

#include "cs2set.h"
int
main()
{
  cs2set<std::string> set1;
  
  //  Gather statistics to make sure insert is still working
  int correct_insert = 0, incorrect_insert = 0;
  std::pair< cs2set<std::string>::iterator, bool > insert_result;
  std::string to_insert = std::string("hello");
  insert_result = set1.insert( to_insert );

  if ( insert_result.second )
    correct_insert ++;
  else
    incorrect_insert ++ ;

  insert_result = set1.insert( std::string("good-bye") );
  if ( insert_result.second )
    correct_insert ++;
  else
    incorrect_insert ++ ;

  insert_result = set1.insert( std::string("friend") );
  if ( insert_result.second )
    correct_insert ++;
  else
    incorrect_insert ++ ;

  insert_result = set1.insert( std::string("abc") );
  if ( insert_result.second )
    correct_insert ++;
  else
    incorrect_insert ++ ;

  insert_result = set1.insert( std::string("puppy") );
  if ( insert_result.second )
    correct_insert ++;
  else
    incorrect_insert ++ ;

  insert_result = set1.insert( std::string("zebra") );
  if ( insert_result.second )
    correct_insert ++;
  else
    incorrect_insert ++ ;

  insert_result = set1.insert( std::string("daddy") );
  if ( insert_result.second )
    correct_insert ++;
  else
    incorrect_insert ++ ;

  insert_result = set1.insert( std::string("puppy") );
  if ( !insert_result.second && * insert_result.first == std::string("puppy") )
    correct_insert ++;
  else
    incorrect_insert ++ ;

  std::cout << "At the end of the initial insert:  correct = " 
            << correct_insert << ", incorrect_insert = " 
            << incorrect_insert << '\n';

  cs2set<std::string>::iterator p = set1.begin();
  if ( p == set1.end() || *p != std::string("abc") )
    std::cout << "Begin failed\n";
  
  std::cout << "The set size is " << set1.size()
	    << "\nHere are the elements: \n" << set1 << std::endl;

  p = set1.find( "foo" );
  if ( p == set1.end() )
    std::cout << "\"foo\" is not in the set\n";
  else
    std::cout << "\"foo\" is in the set\n"
	      << "The iterator points to " << *p << std::endl;

  p = set1.find("puppy");
  if ( p == set1.end() )
    std::cout << "\"puppy\" is not in the set\n";
  else
    std::cout << "\"puppy\" is in the set\n"
	      << "The iterator points to " << *p << std::endl;

  p = set1.find("daddy");
  if ( p == set1.end() )
    std::cout << "\"daddy\" is not in the set\n";
  else
    std::cout << "\"daddy\" is in the set\n"
	      << "The iterator points to " << *p << std::endl;

  std::cout << "\nHere is the tree, printed sideways.\n"
	    << "The indentation is proportional to the depth of the node\n"
	    << "so that the value stored at the root is the only value printed\n"
	    << "without indentation.  Also, for each node, the right subtree\n"
	    << "can be found above where the node is printed and indented\n"
	    << "relative to it\n\n";
  set1.print_as_sideways_tree( std::cout );

  //  Copy the set
  cs2set<std::string> set2( set1 );
  std::cout << "set1.size() = " << set1.size() << ", set2.size() = " << set2.size() << std::endl;
  std::cout << "\nHere is set2 printed sideways:\n";
  set2.print_as_sideways_tree( std::cout );
  
  //  Now add more stuff to set2. 
  insert_result = set2.insert( std::string("a") );
  assert( insert_result.second );
  insert_result = set2.insert( std::string("b") );
  assert( insert_result.second );
  std::cout << "\nAfter two inserts:\n"
	    << "set1.size() = " << set1.size() << ", set2.size() = " << set2.size() << "\n"
	    << "\nThe contents of set2:\n" << set2 << std::endl;

  //  Now test erase given a particular value
  std::cout << "\nHere is set2 printed sideways\n";
  set2.print_as_sideways_tree( std::cout );
  int num = set2.erase( std::string("hello") );
  std::cout << "Tried erase \"hello\" and got num (should be 1) = " << num
	    << "\nHere is the tree:" << std::endl;
  set2.print_as_sideways_tree( std::cout );
  num = set2.erase( std::string("a") );
  std::cout << "Tried erase \"a\" and got num (should be 1) = " << num << std::endl;
  num = set2.erase( std::string("hello") );
  std::cout << "Tried erase \"hello\" and got num (should be 0) = " << num << std::endl;
  num = set2.erase( std::string("abc") );
  std::cout << "Tried erase \"abc\" and got num (should be 1) = " << num << std::endl;
  num = set2.erase( std::string("friend") );
  std::cout << "Tried erase \"friend\" and got num (should be 1) = " << num
	    << "\nHere is the tree:" << std::endl;
  set2.print_as_sideways_tree( std::cout );

  //  Back to set1.  Adding a bit more to make the height and average
  //  depth calculations interesting.
  insert_result = set1.insert( std::string("car") ) ;
  assert( insert_result.second );
  insert_result = set1.insert( std::string("cabbage") );
  assert( insert_result.second );

  std::cout << "\nBack to set1, after inserting \"car\" and \"cabbage\"\n"
            << "the tree looks like\n";
  set1.print_as_sideways_tree( std::cout );  


  std::cout << "\n========================\n"
            << "==  Main HW 8 tests: ===\n"
            << "========================\n\n";

  std::cout << "The tree's height is " << set1.height()
            << ", and its average depth is " << set1.average_depth() << '\n';

  std::cout << "\nHere is the tree in level order\n";
  set1.level_order( std::cout );

  std::cout << "\nIs the tree balanced? ";
  bool bal = set1.is_balanced();
  std::cout << ( bal ? "yes\n" : "no\n");
  
  set1.rebalance();
  std::cout << "\nAfter rebalancing the tree is now\n";
  set1.print_as_sideways_tree( std::cout );

  std::cout << "\nIs the tree balanced? ";
  bal = set1.is_balanced();
  std::cout << ( bal ? "yes\n" : "no\n");

  set1.insert( "dog" );
  bal = set1.is_balanced();
  std::cout << "After inserting \"dog\", the tree should still be balanced. Is it?  " 
            << ( bal ? "yes\n" : "no\n");
  set1.insert( "grade" );
  bal = set1.is_balanced();
  std::cout << "After inserting \"grade\", the tree should no longer be balanced. Is it?  " 
            << ( bal ? "yes\n" : "no\n");

  std::cout << "\nBefore lower_bound and upper_bound operations, the tree is \n";
  set1.print_as_sideways_tree( std::cout );  

  std::cout << "\nAnd in level order it is\n";
  set1.level_order( std::cout );

  std::cout << "\n" << "Forward iteration through the tree produces:\n";
  for ( p = set1.begin(); p != set1.end(); ++p )
    std::cout << *p << '\n';

  p = set1.lower_bound( "friend" );
  std::cout << "Lower bound of \"friend\" should reference \"friend\".  It "
            << ( (p != set1.end() && *p == "friend" ) ? " DOES\n" : " does NOT\n" );

  p = set1.lower_bound( "dear" );
  std::cout << "Lower bound of \"dear\" should reference \"dog\".  It "
            << ( (p != set1.end() && *p == "dog" ) ? " DOES\n" : " does NOT\n" );

  p = set1.lower_bound( "zoo" );
  std::cout << "Lower bound of \"zoo\" should be the end iterator.  It "
            << ( p == set1.end() ? "IS\n" : "is NOT\n" );

  p = set1.upper_bound( "friend" );
  std::cout << "Upper bound of \"friend\" should reference \"good-bye\".  It "
            << ( (p != set1.end() && *p == "good-bye" ) ? " DOES\n" : " does NOT\n" );

  p = set1.upper_bound( "dear" );
  std::cout << "Upper bound of \"dear\" should reference \"dog\".  It "
            << ( (p != set1.end() && *p == "dog" ) ? " DOES\n" : " does NOT\n" );

  p = set1.upper_bound( "zoo" );
  std::cout << "Upper bound of \"zoo\" should be the end iterator.  It "
            << ( p == set1.end() ? "IS\n" : "is NOT\n" );

  std::cout << "\n" << "Forward iteration through the tree produces:\n";
  for ( p = set1.begin(); p != set1.end(); p++ )
    std::cout << *p << '\n';
  
  p = set1.lower_bound( "friend" );
  set1.erase(p);
  p = set1.upper_bound( "dear" );
  set1.erase(p);   // should erase "dog"
  set1.erase( "friend" );
  set1.erase( "dog" );

  std::cout << "\nAfter two erases with iterators, which should remove \"friend\" and \"dog\"\n"
            << "the tree looks like\n";
  set1.print_as_sideways_tree( std::cout );  

  std::cout << "\n" << "Forward iteration through the tree produces:\n";
  for ( p = set1.begin(); p != set1.end(); ++p )
    std::cout << *p << '\n';


  p = set1.begin();
  std::string begin_string = *p;
  std::vector< std::string > strings;
  strings.push_back( *p ); p++;
  strings.push_back( *p ); p++;
  strings.push_back( *p ); p++;
  strings.push_back( *p ); p++;
  --p;
  int k = strings.size()-1;

  std::cout << "Going backwards to test decrement operator\n";
  while ( k >= 0 )
    {
      std::cout << "strings[" << k << "] = " << strings[k] 
                << ",  *p = " << *p << '\n';
      k--;
      p--;
    }
  

  std::cout << "\n***  Now building an int set and testing operator == \n";

  cs2set<int> int_set;
  int_set.insert(10);
  int_set.insert(5);
  int_set.insert(7);
  int_set.insert(3);
  int_set.insert(1);
  int_set.insert(4);
  int_set.insert(19);
  int_set.insert(12);
  std::cout << "Here is the tree\n";
  int_set.print_as_sideways_tree( std::cout );
  std::cout << "----\n";
  
  int_set.erase(3);
  std::cout << "\nAfter erasing 3\n";
  int_set.print_as_sideways_tree( std::cout );

  cs2set<int> int_set2( int_set );
  int_set2.rebalance();

  bool equal = ( int_set == int_set2 );
  std::cout << "After copying, int_set == int_set2 is "
            << ( equal ? "true" : "false") << '\n';

  int_set.erase( 10 );   int_set2.erase( 19 );
  equal = ( int_set == int_set2 );
  std::cout << "After erasing 10 from int_set and 19 from int_set2,"
            << " int_set == int_set2 is "
            << ( equal ? "true" : "false") << '\n';

  int_set.erase( 19 );   int_set2.erase( 10 );
  equal = ( int_set == int_set2 );
  std::cout << "After erasing 19 from int_set and 10 from int_set2,"
            << " int_set == int_set2 is "
            << ( equal ? "true" : "false") << '\n';

    
  return 0;
}