#include <bits/stdc++.h>

using namespace std;

typedef map < string, map < string, vector < int > > > dbtype ; // map< tablename, map< column_name, vector<values> > >

typedef map < string, map < int , string > > dbreftype ; // map <tablename , map<order, column_name>>

struct total_db{

dbtype data; //original database

dbreftype ref; //column reference to know the order

};

struct parsed_query{

};

struct mined_data{

};

bool error=false;

vector< vector < int > > join_table;

set< string > to_remove;

double g_avg=0;

long long int g_sum=0;

long long int g_min=INT_MAX;

long long int g_max=INT_MIN;

bool is_number(string input);

struct parsed_query * parseit(string input);

struct total_db * read_metadata();

struct total_db * populate_db(struct total_db * mydb);

struct parsed_query * verify_wrapper(struct total_db * mydb,struct parsed_query * input_query,string cur_column,int index_string,bool flag);

struct parsed_query * verify_extend_query(struct total_db * mydb,struct parsed_query * input_query);

void print_db(struct total_db * mydb);

void print_query(struct parsed_query * query_parsed);

struct mined_data * populate_mine(struct parsed_query * query_parsed, struct total_db * mydb);

struct mined_data * carry_over(struct mined_data * mymine, struct total_db * mydb,struct parsed_query * query_parsed);

void create_candidate(struct mined_data * mymine, struct total_db * mydb,struct parsed_query * query_parsed);

void miner(struct mined_data * mymine, struct total_db * mydb,struct parsed_query * query_parsed);

bool accept_on_where(struct mined_data * mymine,struct parsed_query * query_parsed);

bool check_where(struct mined_data *mymine,string op,struct parsed_query * query_parsed);

void select_from_db(struct mined_data * mymine,struct parsed_query * query_parsed);

bool agg_func_handler(string agg_func,struct total_db * mydb,struct parsed_query * query_parsed);

void parse_distinct(struct mined_data* mymine,struct parsed_query * query_parsed);

int main(int argc,char * argv[])

}

void parse_distinct(struct mined_data* mymine,struct parsed_query * query_parsed)

}

bool agg_func_handler(string agg_func,struct total_db * mydb,struct parsed_query * query_parsed)

}

void select_from_db(struct mined_data * mymine,struct parsed_query * query_parsed)

}

bool check_where(struct mined_data *mymine,string op,struct parsed_query * query_parsed)

}

bool accept_on_where(struct mined_data * mymine,struct parsed_query * query_parsed)

}

void create_candidate(struct mined_data * mymine, struct total_db * mydb,struct parsed_query * query_parsed)

}

struct mined_data * carry_over(struct mined_data * mymine, struct total_db * mydb,struct parsed_query * query_parsed)

{

int first=0;

int back=(mymine->total_tables)-1;

while(mymine->row_pointer[first]>=mymine->table_sizes[first])

{

if(first==back)

break;

mymine->row_pointer[first+1]+=1;

mymine->row_pointer[first]=0;

first++;

}

if(mymine->row_pointer[back]<mymine->table_sizes[back])

create_candidate(mymine,mydb,query_parsed);

return mymine;

}

void miner(struct mined_data * mymine, struct total_db * mydb,struct parsed_query * query_parsed)

}

struct mined_data * populate_mine(struct parsed_query * query_parsed, struct total_db * mydb)

{

struct mined_data * mymine=new struct mined_data;

vector < string > tab_cols;

string cur_table;

int col_count=0;

for(int i=0;i<query_parsed->tables.size();i++)

{

cur_table=query_parsed->tables[i];

tab_cols.clear();

mymine->table_order.push_back(cur_table);

map < string , vector < int > >:: iterator it;

for(it=mydb->data[cur_table].begin();it!=mydb->data[cur_table].end();it++)

{

tab_cols.push_back(it->first);

mymine->col_to_index[cur_table+"."+it->first]=col_count;

col_count++;

}

mymine->columns.push_back(tab_cols);

it--;

mymine->table_sizes.push_back(mydb->data[cur_table][it->first].size());

}

mymine->total_tables=mymine->table_sizes.size();

for(int i=0;i<col_count;i++)

mymine->candidate.push_back(0);

for(int i=0;i<mymine->total_tables;i++)

mymine->row_pointer.push_back(0);

return mymine;

}

bool is_number(string input)

}

struct parsed_query * verify_wrapper(struct total_db * mydb,struct parsed_query * input_query,string cur_column,int index_string,bool flag)

{

size_t found_pos;

found_pos=cur_column.find("("); //check for agg functions

if(found_pos!=string::npos)

{

input_query->agg.push_back(cur_column.substr(0,found_pos));

cur_column=cur_column.substr(found_pos+1);

found_pos=cur_column.find(")");

cur_column=cur_column.substr(0,found_pos);

}

else

{

input_query->agg.push_back("");

}

found_pos=cur_column.find(".");

if(found_pos!=string::npos) // if table1.c types check if c in table1

{

if(mydb->data.find(cur_column.substr(0,found_pos))==mydb->data.end())

error=true;

else if(mydb->data[cur_column.substr(0,found_pos)].find(cur_column.substr(found_pos+1))==mydb->data[cur_column.substr(0,found_pos)].end())

error=true;

}

else//if B, then does b exist in a table and if more than one error and replace B with tablex.B

{

int count=0;

string newcolname="",token="",mycomp="";

for(int i=0;i<(input_query->tables).size();i++)

{

if(mydb->data[input_query->tables[i]].find(cur_column)!=mydb->data[input_query->tables[i]].end())

{

count++;

if(flag)

{

newcolname="";

newcolname+=input_query->tables[i]+"."+cur_column;

input_query->columns[index_string]=newcolname;

}

else if(flag==0)

{

newcolname="";

token="";

stringstream comp;

newcolname+=input_query->tables[i]+"."+cur_column;

mycomp=input_query->comparisions[index_string];

input_query->comparisions[index_string]="";

comp<<mycomp;

while(comp>>token)

{

if(token.compare(cur_column)==0)

{

input_query->comparisions[index_string]+=newcolname+" ";

}

else

{

input_query->comparisions[index_string]+=token+" ";

}

}

input_query->comparisions[index_string].pop_back();

}

}

}

if(count!=1)

{

error=true;

return input_query;

}

}

return input_query;

}

struct parsed_query * verify_extend_query(struct total_db * mydb,struct parsed_query * input_query)

{

//to handle *

if(input_query->columns.size()==1 and input_query->columns[0].compare("*")==0)

{

input_query->columns.clear();

string newcolumns="";

map< string, vector< int > >::iterator colit;

for(int i=0;i<((input_query->tables).size());i++)

{

for(colit=mydb->data[input_query->tables[i]].begin();colit!=mydb->data[input_query->tables[i]].end();colit++)

{

newcolumns="";

newcolumns+=input_query->tables[i]+"."+colit->first;

input_query->columns.push_back(newcolumns);

}

}

}

//input query tables exist in db or not

for(int i=0;i<((input_query->tables).size());i++)

{

if(mydb->data.find(input_query->tables[i])==mydb->data.end())

{

error=true;

return input_query;

}

}

string cur_column;

//for input column check

for(int i=0;i<(input_query->columns).size();i++)

{

cur_column=input_query->columns[i];

input_query=verify_wrapper(mydb,input_query,cur_column,i,true);

if(error==true)

return input_query;

}

//where check

string token="";

int count_t=0;

for(int i=0;i<input_query->comparisions.size();i++)

{

cur_column=input_query->comparisions[i];

stringstream comp;

token="";

comp<<cur_column;

count_t=0;

while(comp>>token)

{

if((count_t==0) or (count_t==2))

{

// Check if token is not number

if(!is_number(token))

{

input_query=verify_wrapper(mydb,input_query,token,i,false);

if(error==true)

return input_query;

}

}

token="";

count_t++;

}

}

return input_query;

}

void print_db(struct total_db * mydb)

}

void print_query(struct parsed_query * query_parsed)

}

struct parsed_query * parseit(string input)

{

struct parsed_query * myquery=new parsed_query;

int query_len=input.size();

replace (input.begin(), input.end(), ',' , ' ');

stringstream input_stream;

input_stream<<input;

string token;

string between="";

string tok_query="";

int identifier=-1;

while(input_stream>>token)

{

if(token.compare("SELECT")==0 or token.compare("select")==0 or token.compare("FROM")==0 or token.compare("from")==0 or token.compare("WHERE")==0 or token.compare("where")==0)

{

identifier++;

continue;

}

switch(identifier)

{

case 0:

{

(myquery->columns).push_back(token);

break;

}

case 1:

{

(myquery->tables).push_back(token);

break;

}

case 2:

{

if(token=="AND")

token="and";

else if(token=="OR")

token="or";

if(token=="and" or token=="or")

{

(myquery->operators).push_back(token);

if(between.compare("")!=0)

{

string s1="",s2="",s3="";

int check=0;

for(int i=0;i<between.size();i++)

{

if(between[i]=='<' or between[i]=='>' or between[i]=='=' or between[i]=='!')

check=1; //opertor check

else if(check==1 and between[i]!='=')

check=2; // = came

if(check==0 and between[i]!=' ')

s1+=between[i]; //

if(check==1 and between[i]!=' ')

s2+=between[i];

if(check==2 and between[i]!=' ')

s3+=between[i];

tok_query=s1+" "+s2+" "+s3;

}

(myquery->comparisions).push_back(tok_query);

}

between="";

tok_query="";

continue;

}

between+=token;

between+=" ";

break;

}

default:

break;

}

}

if(between!="")

{

string s1="",s2="",s3="";

int check=0;

for(int i=0;i<between.size();i++)

{

if(between[i]=='<' or between[i]=='>' or between[i]=='=' or between[i]=='!')

check=1; //opertor check

else if(check==1 and between[i]!='=')

check=2; // = came

if(check==0 and between[i]!=' ')

s1+=between[i]; //

if(check==1 and between[i]!=' ')

s2+=between[i];

if(check==2 and between[i]!=' ')

s3+=between[i];

tok_query=s1+" "+s2+" "+s3;

}

(myquery->comparisions).push_back(tok_query);

}

return myquery;

}

struct total_db * populate_db(struct total_db * mydb)

{

dbtype::iterator it;

int col_counter=1;

string filename,linedata,int_data;

for(it=(mydb->data).begin();it!=(mydb->data).end();it++)

{

filename="";

int_data="";

filename.append(it->first);

filename.append(".csv");

ifstream datafile(filename);

while(datafile>>linedata)

{

linedata.erase(remove(linedata.begin(),linedata.end(),'\"'),linedata.end()); //remove all quotes

replace (linedata.begin(), linedata.end(), ',' , ' ');

stringstream linestream(linedata);

col_counter=1;

while(linestream>>int_data)

{

mydb->data[it->first][((mydb->ref)[it->first][col_counter])].push_back(stoi(int_data));

col_counter++;

}

}

datafile.close();

}

return mydb;

}

struct total_db * read_metadata()

{

ifstream mfile("metadata.txt");

bool flag=0;// 1 if file is open 0 if file close

string metadata,tablename;

dbtype data;

dbreftype dataref;

int col_counter=1;

while(mfile>>metadata)

{

if(flag==1)

{

if(metadata[0]=='<')

flag=0; //file close

else

{

vector < int > tmp;

tmp.clear();

data[tablename][metadata]=tmp;

dataref[tablename][col_counter]=metadata;

col_counter++;

}

}

else

{

if(metadata[0]=='<')

flag=1;//file open

mfile>>tablename;

map < string , vector < int > > temp2;

temp2.clear();

data[tablename]=temp2;

map < int ,string > temp3;

temp3.clear();

dataref[tablename]=temp3;

col_counter=1;

}

}

total_db * mydb=new total_db;

mydb->data=data;

mydb->ref=dataref;

mfile.close();

return mydb;

}