QBTreeSort

//Author: Ignacio Gea
//File: QB.h

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string>

using namespace std;

//QB class declaration

class QB{
public: 
    QB();
    QB(string player, int att, int yards, float rating);
    ~QB();

    string getPlayer();
    int getAtt();
    int getYards();
    float getRating();

    void setPlayer(const string player);
    void setAtt(const int att);
    void setYards(const int yards);
    void setRating(const float rating);

    void Print();
    void Read(ifstream &din);

private:
    string Player;
    int Att, Yards;
    float Rating;
    
};

//-----------------------------------------------------------
//  Purpose:    Header file for the BinaryTree class.
//  Author:     John Gauch
//-----------------------------------------------------------

#include "QB.h"


//-----------------------------------------------------------
// BinaryTree data node definition
//-----------------------------------------------------------
class Node
{
 public:
   QB Value;
   Node *Left;
   Node *Right;
   int low, high;
};

//-----------------------------------------------------------
// Define the BinaryTree class interface 
//-----------------------------------------------------------
class BinaryTree
{
 public:
   // Constructor functions
   BinaryTree();
   BinaryTree(char *Name);
   BinaryTree(const BinaryTree & tree);
  ~BinaryTree();

   // General binary tree operations
   bool Search(QB Value);
   bool Insert(QB Value);
   bool Delete(QB Value);
   void Print();

   // Special operation for tree_sort
   void Extract(int data[], int low, int high);
   void ExtractHelper(int data[], int &index, Node * Tree);
   void Range_Query(int low, int high);

 private:
   // Helper functions
   void CopyHelper(Node * Tree1, Node * &Tree2);
   void DestroyHelper(Node * Tree);
   bool SearchHelper(QB Value, Node * Tree);
   bool InsertHelper(QB Value, Node * &Tree);
   bool DeleteNode(Node * &Tree);
   bool DeleteHelper(QB Value, Node * &Tree);
   void PrintHelper(Node * Tree);
   void Range_QueryHelper(int low, int high, Node *&Tree);

   // Tree pointer
   Node *Root;
};

//Author: Ignacio Gea
//File: QB.cpp

#include "QB.h"

QB::QB(){
    Player = "";
    Att = 0;
    Yards = 0;
    Rating = 0.0;
}

QB::QB(string player, int att, int yards, float rating){
    Player = player; 
    Att = att; 
    Yards = yards; 
    Rating = rating;
}

QB::~QB(){
}

string QB::getPlayer(){
    return Player; 
}

int QB::getAtt(){
    return Att; 
}

int QB::getYards(){
    return Yards;
}

float QB::getRating(){
    return Rating; 
}

void QB::setPlayer(const string player){
    Player = player; 
}

void QB::setAtt(const int att){
    Att = att; 
}

void QB::setYards(const int yards){
    Yards = yards; 
}

void QB::setRating(const float rating){
    Rating = rating; 
}

void QB::Print(){
    cout << "Player: " << Player << endl;
    cout << "Attempts: " << Att << endl;
    cout << "Yards: " << Yards << endl;
    cout << "Rating: " << Rating << endl << endl;
    
}

void QB::Read(ifstream &din){
    int size = 17;
    string Data[size];
    for(int i = 0; i < size; i++){
        din >> Data[i];
    }
    
    string player = Data[0] + " " + Data[1];
    string att_str = Data[5];
    string yards_str = Data[9];
    string rating_str = Data[16];
    
    int att = atoi(att_str.c_str());
    int yards = atoi(yards_str.c_str());
    float rating = atof(rating_str.c_str());
    
    Player = player; 
    Att = att; 
    Yards = yards; 
    Rating = rating; 
    
}

//-----------------------------------------------------------
//  Purpose:    Implementation of BinaryTree class.
//  Author:     John Gauch
//-----------------------------------------------------------
#include "tree.h"

//-----------------------------------------------------------
// Constructor function.
//-----------------------------------------------------------
BinaryTree::BinaryTree()
{
   Root = NULL;
}

//-----------------------------------------------------------
// Constructor function that reads tree from file.
//-----------------------------------------------------------
BinaryTree::BinaryTree(char *Name)
{
   Root = NULL;

   // Open input file
   ifstream din;
   din.open(Name);
   if (din.fail())
      cout << "Error: could not open input file\n";
   
    //Read in the first column of the file 
    string dummy; 
    getline(din, dummy);
    

   // Read the data
   QB Value;
   Value.Read(din);
   while (!din.eof())
   {
      InsertHelper(Value, Root);
      Value.Read(din);
   }

   // Close the file
   din.close();
}

//-----------------------------------------------------------
// Copy constructor helper function.
//-----------------------------------------------------------
void BinaryTree::CopyHelper(Node * Tree1, Node * &Tree2)
{
   // Check terminating condition
   if (Tree1 == NULL)
      Tree2 = NULL;

   // Copy node and it's children
   else
   {
      Tree2 = new Node;
      Tree2->Value = Tree1->Value;
      CopyHelper(Tree1->Left, Tree2->Left);
      CopyHelper(Tree1->Right, Tree2->Right);
   }
}

//-----------------------------------------------------------
// Copy constructor.
//-----------------------------------------------------------
BinaryTree::BinaryTree(const BinaryTree & B)
{
   // Call tree copy function
   CopyHelper(B.Root, Root);
}

//-----------------------------------------------------------
// Destructor function helper function.
//-----------------------------------------------------------
void BinaryTree::DestroyHelper(Node * Tree)
{
   // Delete node and it's children
   if (Tree != NULL)
   {
      DestroyHelper(Tree->Left);
      DestroyHelper(Tree->Right);
      delete Tree;
   }
}

//-----------------------------------------------------------
// Destructor function.
//-----------------------------------------------------------
BinaryTree::~BinaryTree()
{
   // Call tree destroy function
   DestroyHelper(Root);
}

//-----------------------------------------------------------
// Search helper function.
//-----------------------------------------------------------
bool BinaryTree::SearchHelper(QB Value, Node * Tree)
{
   // Data value not found 
   if (Tree == NULL)
      return false;

   // Data value found 
   else if (Tree->Value.getYards() == Value.getYards())
      return true;

   // Recursively search for data value
   else if (Tree->Value.getYards() > Value.getYards())
      return (SearchHelper(Value, Tree->Left));
   else if (Tree->Value.getYards() < Value.getYards())
      return (SearchHelper(Value, Tree->Right));
   else
      return false;
}

//-----------------------------------------------------------
// Search for data in the binary tree.
//-----------------------------------------------------------
bool BinaryTree::Search(QB Value)
{
   // Call tree searching function
   return (SearchHelper(Value, Root));
}

//-----------------------------------------------------------
// Insert helper function.
//-----------------------------------------------------------
bool BinaryTree::InsertHelper(QB Value, Node * &Tree)
{
   // Insert data into the tree
   if (Tree == NULL)
   {
      Tree = new Node;
      Tree->Value = Value;
      Tree->Left = NULL;
      Tree->Right = NULL;
      return true;
   }

   // Recursively search for insertion position
   else if (Tree->Value.getYards() > Value.getYards())
      return (InsertHelper(Value, Tree->Left));
   else 
      return (InsertHelper(Value, Tree->Right));
}

//-----------------------------------------------------------
// Insert data into the binary tree.
//-----------------------------------------------------------
bool BinaryTree::Insert(QB Value)
{
   // Call tree insertion function
   return (InsertHelper(Value, Root));
}

//-----------------------------------------------------------
// Delete a single node from the binary tree.
//-----------------------------------------------------------
bool BinaryTree::DeleteNode(Node * &Tree)
{
   Node *Temp = Tree;

   // Node has 0 children
   if ((Tree->Left == NULL) && (Tree->Right == NULL))
      Tree = NULL;

   // Node has 1 child
   else if (Tree->Left == NULL)
      Tree = Tree->Right;
   else if (Tree->Right == NULL)
      Tree = Tree->Left;


   // Node has 2 children
   else
   {
      // Find leftmost node in right subtree
      Node *Parent = Tree;
      Temp = Tree->Right;
      while (Temp->Left != NULL)
      {
	 Parent = Temp;
	 Temp = Parent->Left;
      }

      // Replace deleted data with leftmost value
      if (Parent == Tree)
	 Parent->Right = Temp->Right;
      else
	 Parent->Left = Temp->Right;
      Tree->Value = Temp->Value;
   }

   // Delete node
   delete Temp;
   return true;
}

//-----------------------------------------------------------
// Delete helper function.
//-----------------------------------------------------------
bool BinaryTree::DeleteHelper(QB Value, Node * &Tree)
{
   // Data value not found
   if (Tree == NULL)
      return false;

   // Data value found and deleted
   else if (Tree->Value.getYards() == Value.getYards())
      return (DeleteNode(Tree));

   // Recursively search for node to delete
   else if (Tree->Value.getYards() > Value.getYards())
      return (DeleteHelper(Value, Tree->Left));
   else if (Tree->Value.getYards() < Value.getYards())
      return (DeleteHelper(Value, Tree->Right));
   else
      return false;
}

//-----------------------------------------------------------
// Delete data from the binary tree.
//-----------------------------------------------------------
bool BinaryTree::Delete(QB Value)
{
   // Call tree deletion function
   return (DeleteHelper(Value, Root));
}

//-----------------------------------------------------------
// Print helper function.
//-----------------------------------------------------------
void BinaryTree::PrintHelper(Node * Tree)
{
   // Check terminating condition
   if (Tree != NULL)
   {
      // Print left subtree
      cout << "(";
      PrintHelper(Tree->Left);

      // Print node value
      Tree->Value.Print();

      // Print right subtree
      PrintHelper(Tree->Right);
      cout << ")";
   }
}

//-----------------------------------------------------------
// Range Query method
//-----------------------------------------------------------
void BinaryTree::Range_Query(int low, int high){
    Range_QueryHelper(low, high, Root);
}

//-----------------------------------------------------------
// Range Query method
//-----------------------------------------------------------
void BinaryTree::Range_QueryHelper(int low, int high, Node *&Tree){
    if (Tree != NULL){
    //Print the left subtree
        Range_QueryHelper(low, high, Tree->Left);
    //Print the node value
    if ((Tree->Value.getYards() > low) && (high > Tree->Value.getYards()))
        Tree->Value.Print();
    //Print the right subtree
        Range_QueryHelper(low, high, Tree->Right);
    }
}

//-----------------------------------------------------------
// Print all records in the binary tree.
//-----------------------------------------------------------
void BinaryTree::Print()
{
   // Call tree printing function
   PrintHelper(Root);
   cout << endl;
}

/* 
 * File:   main.cpp
 * Author: Ignacio Gea
 *
 * Created on April 28, 2015, 1:46 AM
 */

#include "tree.h"



int main(int argc, char** argv) {
    
   // din.open("QB.txt");
   
    BinaryTree tree("QB.txt");
    
    int low, high;
    
    //User menu
    int select; 
    cout << "Press 1 to enter a search query.\n"
         << "Press 2 to exit the program.\n\n";
    
    do{
        cin >> select;
        cout << endl;
    }
    while (select < 1 || select > 2);
    
    switch(select){
        case 1: 
            //Prompt the user for a range to search for. 
            cout << "Enter the range of total yards to search for. (i.e. 1960 2000)\n";
            cin >> low >> high;
            cout << endl;
            tree.Range_Query(low, high);
            break;
            
        case 2:
            return 0; 
            break;
    }

}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////
FILE qb.txt
///////////////////////////////////////////////////////////////////////////////////////////////////////////////

Player			Pos	Team	G	Att	Att/G	Cmp	Pct	Yds	Yds/G	Lng	TD	Int	Sck	SckYL	Rating
Charlie Batch		QB	PIT	2	70	35.0	45	64.3	475	237.5	43	1	4	3	12	64.9
Sam Bradford		QB	STL	16	551	34.4	328	59.5	3702	231.4	80	21	13	35	233	82.6
Tom Brady		QB	NE	16	637	39.8	401	63.0	4827	301.7	83	34	8	27	182	98.7
Drew Brees		QB	NO	16	670	41.9	422	63.0	5177	323.6	80	43	19	26	190	96.3
Jason Campbell		QB	CHI	6	51	8.5	32	62.7	265	44.2	45	2	2	6	49	72.8
Matt Cassel		QB	KC	9	277	30.8	161	58.1	1796	199.6	46	6	12	19	101	66.7
Kirk Cousins		QB	WAS	3	48	16.0	33	68.8	466	155.3	77	4	3	3	27	101.6
Jay Cutler		QB	CHI	15	434	28.9	255	58.8	3033	202.2	60	19	14	38	250	81.3
Andy Dalton		QB	CIN	16	528	33.0	329	62.3	3669	229.3	59	27	16	46	229	87.4
Ryan Fitzpatrick	QB	BUF	16	505	31.6	306	60.6	3400	212.5	68	24	16	30	161	83.3
Joe Flacco		QB	BAL	16	531	33.2	317	59.7	3817	238.6	61	22	10	35	227	87.7
Nick Foles		QB	PHI	7	265	37.9	161	60.8	1699	242.7	46	6	5	20	131	79.1
Josh Freeman		QB	TB	16	558	34.9	306	54.8	4065	254.1	95	27	17	26	161	81.6
Blaine Gabbert		QB	JAC	10	278	27.8	162	58.3	1662	166.2	80	9	6	22	158	77.4
Robert Griffin-III	QB	WAS	15	393	26.2	258	65.6	3200	213.3	88	20	5	30	217	102.4
Matt Hasselbeck		QB	TEN	8	221	27.6	138	62.4	1367	170.9	37	7	5	14	103	81.0
Chad Henne		QB	JAC	10	308	30.8	166	53.9	2084	208.4	81	11	11	28	169	72.2
Brian Hoyer		QB	ARI	2	53	26.5	30	56.6	330	165.0	53	1	2	4	30	65.8
Colin Kaepernick	QB	SF	13	218	16.8	136	62.4	1814	139.5	57	10	3	16	112	98.3
Kevin Kolb		QB	ARI	6	183	30.5	109	59.6	1169	194.8	46	8	3	27	159	86.1
Byron Leftwich		QB	PIT	2	53	26.5	25	47.2	272	136.0	37	0	1	3	24	54.9
Matt Leinart		QB	OAK	2	33	16.5	16	48.5	115	57.5	20	0	1	1	9	44.4
Thaddeus Lewis		QB	CLE	1	32	32.0	22	68.8	204	204.0	23	1	1	3	14	83.3
Ryan Lindley		QB	ARI	6	171	28.5	89	52.0	752	125.3	28	0	7	12	91	46.7
Jake Locker		QB	TEN	11	314	28.5	177	56.4	2176	197.8	71	10	11	25	151	74.0
Andrew Luck		QB	IND	16	627	39.2	339	54.1	4374	273.4	70	23	18	41	246	76.5
Eli Manning		QB	NYG	16	536	33.5	321	59.9	3948	246.8	80	26	15	19	136	87.2
Peyton Manning		QB	DEN	16	583	36.4	400	68.6	4659	291.2	71	37	11	21	137	105.8
Colt McCoy		QB	CLE	3	17	5.7	9	52.9	79	26.3	21	1	0	4	25	85.2
Greg McElroy		QB	NYJ	2	31	15.5	19	61.3	214	107.0	30	1	1	11	71	79.2
Matt Moore		QB	MIA	2	19	9.5	11	57.9	131	65.5	37	1	0	2	9	96.6
Cam Newton		QB	CAR	16	485	30.3	280	57.7	3869	241.8	82	19	12	36	244	86.2
Carson Palmer		QB	OAK	15	565	37.7	345	61.1	4018	267.9	64	22	14	26	199	85.3
Christian Ponder	QB	MIN	16	483	30.2	300	62.1	2935	183.4	65	18	12	32	184	81.2
Terrelle Pryor		QB	OAK	3	30	10.0	14	46.7	155	51.7	38	2	1	0	0	70.8
Brady Quinn		QB	KC	10	197	19.7	112	56.9	1141	114.1	57	2	8	21	123	60.1
Philip Rivers		QB	SD	16	527	32.9	338	64.1	3606	225.4	80	26	15	49	311	88.6
Aaron Rodgers		QB	GB	16	552	34.5	371	67.2	4295	268.4	73	39	8	51	293	108.0
Ben Roethlisberger	QB	PIT	13	449	34.5	284	63.3	3265	251.2	82	26	8	30	182	97.0
Tony Romo		QB	DAL	16	648	40.5	425	65.6	4903	306.4	85	28	19	36	263	90.5
Matt Ryan		QB	ATL	16	615	38.4	422	68.6	4719	294.9	80	32	14	28	210	99.1
Mark Sanchez		QB	NYJ	15	453	30.2	246	54.3	2883	192.2	66	13	18	34	209	66.9
Matt Schaub		QB	HOU	16	544	34.0	350	64.3	4008	250.5	60	22	12	27	216	90.7
John Skelton		QB	ARI	7	201	28.7	109	54.2	1132	161.7	40	2	9	15	98	55.4
Alex Smith		QB	SF	10	218	21.8	153	70.2	1737	173.7	55	13	5	24	137	104.1
Matthew Stafford	QB	DET	16	727	45.4	435	59.8	4967	310.4	57	20	17	29	212	79.8
Ryan Tannehill		QB	MIA	16	484	30.2	282	58.3	3294	205.9	80	12	13	35	234	76.1
Tyrod Taylor		QB	BAL	7	29	4.1	17	58.6	179	25.6	25	0	1	3	30	62.3
Michael Vick		QB	PHI	10	351	35.1	204	58.1	2362	236.2	77	12	10	28	153	78.1
Brandon Weeden		QB	CLE	15	517	34.5	297	57.4	3385	225.7	71	14	17	28	186	72.6
Russell Wilson		QB	SEA	16	393	24.6	252	64.1	3118	194.9	67	26	10	33	203	100.0