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

using namespace std;

typedef struct treeNode{
                int year;
                string title;
                list<string> actors;
                treeNode* left;
                treeNode* right;

        }* treePtr;

treePtr root = NULL;

treePtr fillTree(treePtr p, int y, string t, list<string> a);
void print_titles(treePtr root);
void print_before_year(treePtr root, int key);
void print_actors_movies();



int main(){

        ifstream inFile ("movies.txt");
        string x;
        treePtr root = NULL;
        int count = 0;
        if(inFile.is_open()){

                while(getline (inFile, x)){
                        if(x == ""){
                                        continue;
                                }
                        count++;

                        int index = x.find_last_of(" ");
                        string title = x.substr(0, index);
                        string year = x.substr(index + 2, x.length() - index - 3);

                        list<string> actor;
                        int counter = 0;

                        while(getline(inFile, x)){
                                if(x == ""){
                                        break;
                                }
                                else{
                                        actor.push_back(x);
                                }
                        }

                        root = fillTree(root, atoi(year.c_str()), title, actor);

                }
        }
        int choice;
		   do{
        cout <<"\nWelcome to the Movie Store. Would you like to: \n(1) See what movies are available? \n(2) Search for an actor? \n(3) Search for a year? \n(4) Search for a movie? \n(0) Exit the Store" << endl;
        cin >> choice;
        switch(choice){
        case 0:
                cout << "Thank you come again." << endl;
                break;
        case 1:
                print_titles(root);
                break;
        case 2:
			
        case 3:
                int year;
                cout << "Please enter the year you wish to search for: " << endl;
                cin >> year;
                cout << endl;
                cout << "Films made before " << year << ":" << endl;
                print_before_year(root, year);
                break;
        case 4:

        default:
                cout << "Try again." << endl;

        }}while(choice != 0);





return 0;
}


treePtr fillTree(treePtr p, int y, string t, list<string> a){
        treePtr n = new treeNode;
        n->year = y;
        n->title = t;
        n->actors = a;
        n->left = NULL;
        n->right = NULL;
        if(p == NULL){
                p = n;
        }
        else{
                treePtr prev = p;
                treePtr curr = p;
                while(curr != NULL){
                        if(curr->year > y){
                                prev = curr;
                                curr = curr->left;
                        }
                        else{
                                prev = curr;
                                curr = curr->right;
   }
                }
                if(prev->year > y){
                        prev->left = n;
                }
                else{
                        prev->right = n;
                }


        }

        return p;
}

void print_titles(treePtr root){
        if(root == NULL) return;
        if(root->left) print_titles(root->left);
        cout<<root->title<<endl;
        if(root->right) print_titles(root->right);
}

void print_before_year(treePtr root, int key){

        if(root == NULL) return;
        if(root->left) print_before_year(root->left, key);
        if(root->year < key){
                cout << root->title << endl;
        }
        else return;
        if(root->right) print_before_year(root->right, key);
}

void print_actors_movies(){
		

}