//===----------------------------------------------------------------------===//
//
//                         BusTub
//
// b_plus_tree_debug.h
//
// Identification: src/include/storage/index/b_plus_tree_debug.h
//
// Copyright (c) 2015-2025, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include <sstream>
#include <string>

#include "common/exception.h"
#include "common/logger.h"
#include "common/rid.h"
#include "storage/index/b_plus_tree.h"
#include "storage/page/b_plus_tree_page.h"

namespace bustub {

/*
 * All the methods in this file are used for test and debug only.
 * You don't need to modify them.
 */

/*****************************************************************************
 * UTILITIES AND DEBUG
 *****************************************************************************/

/**
 * This method is used for test only
 * Read data from file and insert one by one
 */
FULL_INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::InsertFromFile(const std::filesystem::path &file_name) {
  int64_t key;
  std::ifstream input(file_name);
  while (input) {
    input >> key;

    KeyType index_key;
    index_key.SetFromInteger(key);
    RID rid(key);
    Insert(index_key, rid);
  }
}

/**
 * This method is used for test only
 * Read data from file and remove one by one
 */
FULL_INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::RemoveFromFile(const std::filesystem::path &file_name) {
  int64_t key;
  std::ifstream input(file_name);
  while (input) {
    input >> key;
    KeyType index_key;
    index_key.SetFromInteger(key);
    Remove(index_key);
  }
}

FULL_INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::Print(BufferPoolManager *bpm) {
  auto root_page_id = GetRootPageId();
  if (root_page_id != INVALID_PAGE_ID) {
    auto guard = bpm->ReadPage(root_page_id);
    PrintTree(guard.GetPageId(), guard.template As<BPlusTreePage>());
  }
}

FULL_INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::PrintTree(page_id_t page_id, const BPlusTreePage *page) {
  if (page->IsLeafPage()) {
    auto *leaf = reinterpret_cast<const LeafPage *>(page);
    std::cout << "Leaf Page: " << page_id << "\tNext: " << leaf->GetNextPageId() << std::endl;

    // Print the contents of the leaf page.
    std::cout << "Contents: ";
    for (int i = 0; i < leaf->GetSize(); i++) {
      std::cout << leaf->KeyAt(i);
      if ((i + 1) < leaf->GetSize()) {
        std::cout << ", ";
      }
    }
    std::cout << std::endl;
    std::cout << "Tombstoned keys: ";
    auto tombs = leaf->GetTombstones();
    for (size_t i = 0; i < tombs.size(); i++) {
      std::cout << tombs[i];
      if ((i + 1) < tombs.size()) {
        std::cout << ", ";
      }
    }
    std::cout << std::endl;
    std::cout << std::endl;

  } else {
    auto *internal = reinterpret_cast<const InternalPage *>(page);
    std::cout << "Internal Page: " << page_id << std::endl;

    // Print the contents of the internal page.
    std::cout << "Contents: ";
    for (int i = 0; i < internal->GetSize(); i++) {
      if (i == 0) {
        std::cout << internal->ValueAt(i);
      } else {
        std::cout << internal->KeyAt(i) << ": " << internal->ValueAt(i);
      }
      if ((i + 1) < internal->GetSize()) {
        std::cout << ", ";
      }
    }
    std::cout << std::endl;
    std::cout << std::endl;
    for (int i = 0; i < internal->GetSize(); i++) {
      auto guard = bpm_->ReadPage(internal->ValueAt(i));
      PrintTree(guard.GetPageId(), guard.template As<BPlusTreePage>());
    }
  }
}

/** @brief draw the B+ tree */
FULL_INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::Draw(BufferPoolManager *bpm, const std::filesystem::path &outf) {
  if (IsEmpty()) {
    LOG_WARN("Drawing an empty tree");
    return;
  }

  std::ofstream out(outf);
  out << "digraph G {" << std::endl;
  auto root_page_id = GetRootPageId();
  auto guard = bpm->ReadPage(root_page_id);
  ToGraph(guard.GetPageId(), guard.template As<BPlusTreePage>(), out);
  out << "}" << std::endl;
  out.close();
}

/** @brief Debug Routines for FREE!! */
FULL_INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::ToGraph(page_id_t page_id, const BPlusTreePage *page, std::ofstream &out) {
  std::string leaf_prefix("LEAF_");
  std::string internal_prefix("INT_");
  if (page->IsLeafPage()) {
    auto *leaf = reinterpret_cast<const LeafPage *>(page);
    // Print node name
    out << leaf_prefix << page_id;
    // Print node properties
    out << "[shape=plain color=green ";
    // Print data of the node
    out << "label=<<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"4\">\n";
    // Print data
    out << "<TR><TD COLSPAN=\"" << leaf->GetSize() << "\">P=" << page_id << "</TD></TR>\n";
    out << "<TR><TD COLSPAN=\"" << leaf->GetSize() << "\">"
        << "max_size=" << leaf->GetMaxSize() << ",min_size=" << leaf->GetMinSize() << ",size=" << leaf->GetSize()
        << "</TD></TR>\n";

    auto tombs = leaf->GetTombstones();
    out << "<TR>";
    for (size_t i = 0; i < tombs.size(); i++) {
      out << "<TD>" << tombs[i] << "</TD>\n";
    }
    if (static_cast<size_t>(leaf->GetSize()) > tombs.size()) {
      out << "<TD COLSPAN=\"" << leaf->GetSize() - tombs.size() << "\"> </TD>";
    }
    out << "</TR>";
    out << "<TR>";
    for (int i = 0; i < leaf->GetSize(); i++) {
      out << "<TD>" << leaf->KeyAt(i) << "</TD>\n";
    }
    out << "</TR>";
    // Print table end
    out << "</TABLE>>];\n";
    // Print Leaf node link if there is a next page
    if (leaf->GetNextPageId() != INVALID_PAGE_ID) {
      out << leaf_prefix << page_id << " -> " << leaf_prefix << leaf->GetNextPageId() << ";\n";
      out << "{rank=same " << leaf_prefix << page_id << " " << leaf_prefix << leaf->GetNextPageId() << "};\n";
    }
  } else {
    auto *inner = reinterpret_cast<const InternalPage *>(page);
    // Print node name
    out << internal_prefix << page_id;
    // Print node properties
    out << "[shape=plain color=pink ";  // why not?
    // Print data of the node
    out << "label=<<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"4\">\n";
    // Print data
    out << "<TR><TD COLSPAN=\"" << inner->GetSize() << "\">P=" << page_id << "</TD></TR>\n";
    out << "<TR><TD COLSPAN=\"" << inner->GetSize() << "\">"
        << "max_size=" << inner->GetMaxSize() << ",min_size=" << inner->GetMinSize() << ",size=" << inner->GetSize()
        << "</TD></TR>\n";
    out << "<TR>";
    for (int i = 0; i < inner->GetSize(); i++) {
      out << "<TD PORT=\"p" << inner->ValueAt(i) << "\">";
      if (i > 0) {
        out << inner->KeyAt(i);
      } else {
        out << " ";
      }
      out << "</TD>\n";
    }
    out << "</TR>";
    // Print table end
    out << "</TABLE>>];\n";
    // Print leaves
    for (int i = 0; i < inner->GetSize(); i++) {
      auto child_guard = bpm_->ReadPage(inner->ValueAt(i));
      auto child_page = child_guard.template As<BPlusTreePage>();
      ToGraph(child_guard.GetPageId(), child_page, out);
      if (i > 0) {
        auto sibling_guard = bpm_->ReadPage(inner->ValueAt(i - 1));
        auto sibling_page = sibling_guard.template As<BPlusTreePage>();
        if (!sibling_page->IsLeafPage() && !child_page->IsLeafPage()) {
          out << "{rank=same " << internal_prefix << sibling_guard.GetPageId() << " " << internal_prefix
              << child_guard.GetPageId() << "};\n";
        }
      }
      out << internal_prefix << page_id << ":p" << child_guard.GetPageId() << " -> ";
      if (child_page->IsLeafPage()) {
        out << leaf_prefix << child_guard.GetPageId() << ";\n";
      } else {
        out << internal_prefix << child_guard.GetPageId() << ";\n";
      }
    }
  }
}

/**
 * @brief draw a B+ tree, below is a printed
 * B+ tree(3 max leaf, 4 max internal) after inserting key:
 *  {1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 18, 19, 20}
 *
 *                               (25)
 *                 (9,17,19)                          (33)
 *  (1,5)    (9,13)    (17,18)    (19,20,21)    (25,29)    (33,37)
 *
 * @return std::string
 */
FULL_INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::DrawBPlusTree() -> std::string {
  if (IsEmpty()) {
    return "()";
  }

  PrintableBPlusTree p_root = ToPrintableBPlusTree(GetRootPageId());
  std::ostringstream out_buf;
  p_root.Print(out_buf);

  return out_buf.str();
}

/**
 * @brief Read batch operations from input file, below is a sample file format
 * insert some keys and delete 8, 9 from the tree with one step.
 * { i1 i2 i3 i4 i5 i6 i7 i8 i9 i10 i30 d8 d9 } //  batch.txt
 * B+ Tree(4 max leaf, 4 max internal) after processing:
 *                            (5)
 *                 (3)                (7)
 *            (1,2)    (3,4)    (5,6)    (7,10,30) //  The output tree example
 * @note This method is used for test only. Read data from file and insert/remove one by one.
 */
FULL_INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::BatchOpsFromFile(const std::filesystem::path &file_name) {
  int64_t key;
  char instruction;
  std::ifstream input(file_name);
  if (!input.is_open()) {
    std::cerr << "Failed to open file: " << file_name << std::endl;
    return;
  }
  while (input >> instruction >> key) {
    RID rid(static_cast<int32_t>(key >> 32), static_cast<int>(key & 0xFFFFFFFF));
    KeyType index_key;
    index_key.SetFromInteger(key);
    switch (instruction) {
      case 'i':
        Insert(index_key, rid);
        break;
      case 'd':
        Remove(index_key);
        break;
      default:
        std::cerr << "Unknown instruction: " << instruction << std::endl;
        break;
    }
  }
  if (input.bad()) {
    std::cerr << "Error reading file: " << file_name << std::endl;
  }
  input.close();
}

/**
 * @brief Convert A B+ tree into a Printable B+ tree
 *
 * @param root_id
 * @return PrintableNode
 */
FULL_INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::ToPrintableBPlusTree(page_id_t root_id) -> PrintableBPlusTree {
  auto root_page_guard = bpm_->ReadPage(root_id);
  auto root_page = root_page_guard.template As<BPlusTreePage>();
  PrintableBPlusTree proot;

  if (root_page->IsLeafPage()) {
    auto leaf_page = root_page_guard.template As<LeafPage>();
    proot.keys_ = leaf_page->ToString();
    proot.size_ = proot.keys_.size() + 4;  // 4 more spaces for indent

    return proot;
  }

  // draw internal page
  auto internal_page = root_page_guard.template As<InternalPage>();
  proot.keys_ = internal_page->ToString();
  proot.size_ = 0;
  for (int i = 0; i < internal_page->GetSize(); i++) {
    page_id_t child_id = internal_page->ValueAt(i);
    PrintableBPlusTree child_node = ToPrintableBPlusTree(child_id);
    proot.size_ += child_node.size_;
    proot.children_.push_back(child_node);
  }

  return proot;
}
}  // namespace bustub