// Provide your implementation for the BSTIndex class here
#include "BST.hpp"
#include "FileSystem.hpp"

BSTIndex::BSTIndex() : root(nullptr) {}

BSTIndex::~BSTIndex() {
    destroyTree(root);
}

void BSTIndex::destroyTree(TreeNode* node) {
    if (node != nullptr) {
        destroyTree(node->left);
        destroyTree(node->right);
        delete node;
    }
}

void BSTIndex::CreateIndex(const vector<FileSystemEntry>& Data, const string& IndexType) {
    for (int i = 0; i < Data.size(); ++i) {
        if (IndexType == "Filename") {
            Add(root, i, Data[i].Filename);
        } else if (IndexType == "modifiedOn") {
            Add(root, i, Data[i].modifiedOn);
        } else if (IndexType == "Size") {
            Add(root, i, to_string(Data[i].Size));
        } else if (IndexType == "Type") {
            Add(root, i, Data[i].Type);
        } else {
            // Handle other index types if needed
        }
    }
}


void BSTIndex::Add(TreeNode*& node, const int i, const string &Key;) {
    insertUtil(node, Key, i);
}


void BSTIndex::insertUtil(TreeNode*& node, const string& key, int idx) {
    if (node == nullptr) {
        node = new TreeNode(key, idx);
    } else if (key < node->key) {
        insertUtil(node->left, key, idx);
    } else if (key > node->key) {
        insertUtil(node->right, key, idx);
    } else {
        // Key already exists, add index to existing node
        node->indices.push_back(idx);
    }
}

pair<vector<int>, int> BSTIndex::Search(const string& Key, int& nodesVisited) {
    nodesVisited = 0; // Initialize the counter for nodes visited
    TreeNode* result = searchUtil(root, Key, nodesVisited);
    if (result != nullptr) {
        return {result->indices, nodesVisited}; // Return indices along with the number of nodes visited
    } else {
        return {{}, nodesVisited}; // Return empty vector if key not found along with the number of nodes visited
    }
}

TreeNode* BSTIndex::searchUtil(TreeNode* node, const string& key, int& nodesVisited) {
    if (node == nullptr || node->key == key) {
        return node;
    }
    nodesVisited++; // Increment nodes visited for each node traversed
    if (key < node->key) {
        return searchUtil(node->left, key, nodesVisited);
    }
    return searchUtil(node->right, key, nodesVisited);
}