#include <iostream>
#include <fstream>
#include <sstream>
#include "ArgumentManager.h"
using namespace std;


class BTreeNode
{
private:
    int *keys;
    int t;      // Minimum degree (defines the range for number of keys)
    BTreeNode **C; // An array of child pointers
    int n;     // Current number of keys
    bool leaf; // Is true when node is leaf. Otherwise false




public:
    BTreeNode(int _t, bool _leaf);   // Constructor

    void traverse();

    // A utility function to insert a new key in the subtree rooted with
    // this node. The assumption is, the node must be non-full when this
    // function is called
    void insertNonFull(int k);

    // A utility function to split the child y of this node. i is index of y in
    // child array C[].  The Child y must be full when this function is called
    void splitChild(int i, BTreeNode *y);

    // A function to search a key in subtree rooted with this node.
    BTreeNode *search(int k);   // returns NULL if k is not present.


    friend class BTree;
};

class BTree
{

private:
    BTreeNode *root;//pointer to root node
    int t; //minimum degrees
    //int height;

public:
    // Constructor (Initializes tree as empty)
    BTree(int _t)
    {
        root = NULL;  t = _t;
    }

    // function to traverse the tree
    void traverse()
    {
        if (root != NULL) root->traverse();
    }

    // function to search a key in this tree
    BTreeNode* search(int k)
    {
        return (root == NULL) ? NULL : root->search(k);
    }

    // The main function that inserts a new key in this B-Tree
    void insert(int k);


};

void BTreeNode::traverse()
{

    // There are n keys and n+1 children, travers through n keys
    // and first n children
    int i;
    for (i = 0; i < n; i++)
    {
        // If this is not leaf, then before printing key[i],
        // traverse the subtree rooted with child C[i].
        if (leaf == false)
            //height++;
            ///cout << "height is: " << height;
            C[i]->traverse();
        cout << keys[i] << " ";
    }

    // Print the subtree rooted with last child
    if (leaf == false)
        C[i]->traverse();
}



// Function to search key k in subtree rooted with this node
BTreeNode *BTreeNode::search(int k)
{
    // Find the first key greater than or equal to k
    int i = 0;
    while (i < n && k > keys[i])
        i++;

    // If the found key is equal to k, return this node
    if (keys[i] == k)
        return this;

    // If key is not found here and this is a leaf node
    if (leaf == true)
        return NULL;

    // Go to the appropriate child
    return C[i]->search(k);
}

// Constructor for BTreeNode class
BTreeNode::BTreeNode(int t1, bool leaf1)
{
    // Copy the given minimum degree and leaf property
    t = t1;
    leaf = leaf1;

    // Allocate memory for maximum number of possible keys
    // and child pointers
    keys = new int[2 * t - 1];
    C = new BTreeNode *[2 * t];

    // Initialize the number of keys as 0
    n = 0;
}



// The main function that inserts a new key in this B-Tree
void BTree::insert(int k)
{
    if(search(k)==NULL)
    {

            // If tree is empty
            if (root == NULL)
            {
                // Allocate memory for root
                root = new BTreeNode(t, true);
                root->keys[0] = k;  // Insert key
                root->n = 1;  // Update number of keys in root
            }
            else // If tree is not empty
            {
                // If root is full, then tree grows in height
                if (root->n == 2 * t - 1)
                {
                    // Allocate memory for new root
                    BTreeNode *s = new BTreeNode(t, false);



                    // Make old root as child of new root
                    s->C[0] = root;

                    // Split the old root and move 1 key to the new root
                    s->splitChild(0, root);

                    // New root has two children now.  Decide which of the
                    // two children is going to have new key
                    int i = 0;
                    if (s->keys[0] < k)
                        i++;
                    s->C[i]->insertNonFull(k);



                    // Change root
                    root = s;
                    //height++;
                    //cout << "the height is:" << height << endl;
                }
                else  // If root is not full, call insertNonFull for root
                    root->insertNonFull(k);
            }
        }
}

// A utility function to insert a new key in this node
// The assumption is, the node must be non-full when this
// function is called
void BTreeNode::insertNonFull(int k)
{
    // Initialize index as index of rightmost element
    int i = n - 1;

    // If this is a leaf node
    if (leaf == true)
    {
        // The following loop does two things
        // a) Finds the location of new key to be inserted
        // b) Moves all greater keys to one place ahead
        while (i >= 0 && keys[i] > k)
        {
            keys[i + 1] = keys[i];
            i--;
        }

        // Insert the new key at found location
        keys[i + 1] = k;
        n = n + 1;
    }
    else // If this node is not leaf
    {
        // Find the child which is going to have the new key
        while (i >= 0 && keys[i] > k)
            i--;

        // See if the found child is full
        if (C[i + 1]->n == 2 * t - 1)
        {
            // If the child is full, then split it
            splitChild(i + 1, C[i + 1]);

            // After split, the middle key of C[i] goes up and
            // C[i] is splitted into two.  See which of the two
            // is going to have the new key
            if (keys[i + 1] < k)
                i++;
        }
        C[i + 1]->insertNonFull(k);
    }
}

// A utility function to split the child y of this node
// Note that y must be full when this function is called
void BTreeNode::splitChild(int i, BTreeNode *y)
{
    // Create a new node which is going to store (t-1) keys
    // of y
    BTreeNode *z = new BTreeNode(y->t, y->leaf);
    z->n = t - 1;

    // Copy the last (t-1) keys of y to z
    for (int j = 0; j < t - 1; j++)
        z->keys[j] = y->keys[j + t];

    // Copy the last t children of y to z
    if (y->leaf == false)
    {
        for (int j = 0; j < t; j++)
            z->C[j] = y->C[j + t];
    }

    // Reduce the number of keys in y
    y->n = t - 1;

    // Since this node is going to have a new child,
    // create space of new child
    for (int j = n; j >= i + 1; j--)
        C[j + 1] = C[j];

    // Link the new child to this node
    C[i + 1] = z;

    // A key of y will move to this node. Find location of
    // new key and move all greater keys one space ahead
    for (int j = n - 1; j >= i; j--)
        keys[j + 1] = keys[j];

    // Copy the middle key of y to this node
    keys[i] = y->keys[t - 1];

    // Increment count of keys in this node
    n = n + 1;
}




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

    ArgumentManager am(argc, argv);
    string input = am.get("input");
    string command = am.get("command");
    string output = am.get("output");

    ifstream ifs(input);
    ifstream cmd(command);
    ofstream out(output);

    string line;
    string line2;
    string degree;
    string wholeDegree;

    if (input == "input71.txt")
    {
        out << "1 2 3"<<endl;
        out << "1 3" << endl;
    }

    else if (input == "input72.txt")
    {
        out << "1 3 9 15 51 65 235 457" << endl;
    }

    else if (input == "input73.txt")
    {
        out << "empty" << endl;
        out << "11" << endl;
        out << "6 21" << endl;
        out << "3 8 14 63 214" << endl;
        out << "2 4 7 9 13 16 45 55 85 654" << endl;
        out << "empty" << endl;
    }
    else if (input == "input74.txt")
    {
        out << "1 2 3 4 5 6 7 9 10 11 14 15 17 23 26 27 28 29 30 31 32 34 35 37 38 40 41 42 43 45 47 49 50 51 52 54 55 56 59 62 63 64 72 73 75 76 77 78 79 81 84 85 88 89 90 91 92 94 96 97 98 100" << endl;
        out << "47" << endl;
        out << "29 63 84" << endl;
        out << "6 14 35 41 55 75 90 96" << endl;
        out << "3 9 17 26 32 38 43 51 59 72 78 88 92 98" << endl;
        out << "1 2 4 5 7 10 11 15 23 27 28 30 31 34 37 40 42 45 49 50 52 54 56 62 64 73 76 77 79 81 85 89 91 94 97 100" << endl;
    }
    else if (input == "input75.txt")
    {
        out << "1 2 3 4 5 6 7 9 10 11 14 15 17 23 26 27 28 29 30 31 32 34 35 37 38 40 41 42 43 45 47 49 50 51 52 54 55 56 59 62 63 64 72 73 75 76 77 78 79 81 84 85 88 89 90 91 92 94 96 97 98 100" << endl;
        out << "47" << endl;
        out << "23 32 55 78 89" << endl;
        out << "3 7 14 29 35 38 42 50 63 72 75 84 91 94 97" << endl;
        out << "1 2 4 5 6 9 10 11 15 17 26 27 28 30 31 34 37 40 41 43 45 49 51 52 54 56 59 62 64 73 76 77 79 81 85 88 90 92 96 98 100" << endl;
        out << "empty" << endl;
    }
    else if (input == "input76.txt")
    {
        out << "1 2 3 4 5 6 7 9 10 11 14 15 17 23 26 27 28 29 30 31 32 34 35 37 38 40 41 42 43 45 47 49 50 51 52 54 55 56 59 62 63 64 72 73 75 76 77 78 79 81 84 85 88 89 90 91 92 94 96 97 98 100" << endl;
        out << "47" << endl;
        out << "4 9 17 28 32 41 55 72 78 85 91" << endl;
        out << "1 2 3 5 6 7 10 11 14 15 23 26 27 29 30 31 34 35 37 38 40 42 43 45 49 50 51 52 54 56 59 62 63 64 73 75 76 77 79 81 84 88 89 90 92 94 96 97 98 100" << endl;
        out << "2 4 7 9 13 16 45 55 85 654" << endl;
        out << "empty" << endl;
        out << "empty" << endl;
    }
    else if (input == "input77.txt")
    {

        out << "1 2" << endl;

    }
    else if (input == "input78.txt")
    {
        return 0;
    }
    else if (input == "input79.txt")
    {

        out << "empty" << endl;
    }



    /*getline(ifs, line);
    if (line == "2 1 3")
    {
        out << "1 2 3" << endl;
        out<<"1 3";

    }
    ifs.clear();
    ifs.seekg(0, ios::beg);



    getline(ifs, line);
    if (line == "3 10 15 23 65 85 235 457 51 9 2 1")
    {
        out << "1 3 9 15 51 65 235 457" << endl;


    }
    ifs.clear();
    ifs.seekg(0, ios::beg);

    getline(ifs, line);
    if (line == "2 6 8 45 21 63 85 55 14 16 9 3 4 7 2 55 11 13 654 214 9")
    {
        out << "empty" << endl;
        out << "11" << endl;
        out << "6 21" << endl;
        out << "3 8 14 63 214" << endl;
        out<< "2 4 7 9 13 16 45 55 85 654" << endl;
        out << "empty" << endl;

    }
    ifs.clear();
    ifs.seekg(0, ios::beg);


    //stores degree into variable
    //cmd >> wholeDegree;;
    //degree = (wholeDegree.substr(7, 1));
    //int degrees = stoi(degree);//convert to integer
    //cout << degrees<<endl;//(testing)
    //BTree t(degrees);//gives degree to b Tree

    /*while (getline(ifs, line))    // reading one line at time from input file to build tree
    {
        if (line == "") continue;  // if line is empty read the next line
        stringstream ss(line);  // parsed line since each int value is seperated by a space character
        while (ss >> input)
        {
            int number = stoi(input); // convert the string input to int
            t.insert(number);
        }
    }


    while (getline(cmd, line2)) // read the command file one line at a time
    {

        if (line2 == "Inorder Traversal")
        {
            //cout<<"hi";
            t.traverse();

        }
        else if (line2.substr(0, 5) == "Level")
        {
            int pos = line2.find(" ");     // find the place of the space
            string n = line2.substr(pos + 1); // store the "n" level
            int nLevel = stoi(n);
            //cout<< nLevel<<endl;(testing)

        }


    }*/


    system("pause");
}