// C++17特性示例：使用std::optional和范围for循环
#include <optional>
#include <vector>
#include <string>

// 使用std::optional返回可能缺失的值
std::optional<std::string> find_record(const std::vector<std::string>& records, const std::string& key) {
    for (const auto& record : records) {  // 范围for循环
        if (record.starts_with(key)) {    // C++20特性，由C++17演进而来
            return record;
        }
    }
    return std::nullopt;  // 返回空值
}

// 使用std::flat_map优化内存使用
#include <flat_map>

void process_data() {
    std::flat_map<std::string, int> data_map;
    // 插入数据
    data_map.emplace("key1", 42);  // emplace避免拷贝
    data_map.emplace("key2", 99);
    
    // 遍历
    for (const auto& [key, value] : data_map) {  // 结构化绑定
        // 处理数据
    }
}

// 线性索引节点结构
struct LinearIndexEntry {
    std::string key;      // 记录键值
    uint64_t offset;      // 物理偏移量（字节）
    uint32_t length;      // 记录长度（字节）
    uint32_t block_num;   // 所在块号
};

// 线性索引管理类
class LinearIndex {
public:
    void insert(const std::string& key, uint64_t offset, uint32_t length, uint32_t block);
    std::optional<LinearIndexEntry> find(const std::string& key) const;
    bool remove(const std::string& key);
    void sort(); // 保持索引表有序
    
private:
    std::vector<LinearIndexEntry> entries_;
};

// 二分查找算法实现
std::optional<LinearIndexEntry> LinearIndex::find(const std::string& key) const {
    // 使用std::lower_bound进行二分查找
    auto it = std::lower_bound(entries_.begin(), entries_.end(), key, 
        [](const LinearIndexEntry& entry, const std::string& k) {
            return entry.key < k;
        });
    
    // 检查是否找到匹配的键
    if (it != entries_.end() && it->key == key) {
        return *it;
    }
    
    // 未找到返回空
    return std::nullopt;
}

// 多级索引结构
class MultiLevelIndex {
public:
    // 一级索引条目
    struct Level1Entry {
        std::string key_range_start;  // 键值范围起始
        std::string key_range_end;    // 键值范围结束
        uint64_t level2_offset;       // 二级索引偏移量
    };
    
    // 二级索引条目
    struct Level2Entry {
        std::string key;              // 键值
        uint64_t data_offset;         // 数据偏移量
        uint32_t length;              // 数据长度
    };
    
    void build(const std::vector<DataRecord>& records);  // 构建索引
    std::optional<uint64_t> find(const std::string& key) const;  // 查找
    
private:
    std::vector<Level1Entry> level1_;  // 一级索引
    std::vector<Level2Entry> level2_;  // 二级索引
};

// 多级索引构建实现
void MultiLevelIndex::build(const std::vector<DataRecord>& records) {
    // 排序所有记录
    std::vector<DataRecord> sorted_records = records;
    std::sort(sorted_records.begin(), sorted_records.end(), 
        [](const DataRecord& a, const DataRecord& b) {
            return a.key < b.key;
        });
    
    // 构建二级索引
    size_t level2_size = sorted_records.size();
    level2_.reserve(level2_size);
    for (size_t i = 0; i < level2_size; ++i) {
        level2_.emplace_back(Level2Entry{
            sorted_records[i].key,
            sorted_records[i].offset,
            sorted_records[i].length
        });
    }
    
    // 构建一级索引（每100个二级索引项为一组）
    size_t group_size = 100;
    size_t group_count = (level2_size + group_size - 1) / group_size;
    level1_.reserve(group_count);
    
    for (size_t i = 0; i < group_count; ++i) {
        size_t start_idx = i * group_size;
        size_t end_idx = std::min((i + 1) * group_size, level2_size);
        
        Level1Entry entry;
        entry.key_range_start = level2_[start_idx].key;
        entry.key_range_end = level2_[end_idx - 1].key;
        entry.level2_offset = start_idx * sizeof(Level2Entry);
        
        level1_.emplace_back(std::move(entry));
    }
}

// 多级索引查找实现
std::optional<uint64_t> MultiLevelIndex::find(const std::string& key) const {
    // 在一级索引中查找键值范围
    auto it = std::lower_bound(level1_.begin(), level1_.end(), key,
        [](const Level1Entry& entry, const std::string& k) {
            return entry.key_range_start <= k && k <= entry.key_range_end;
        });
    
    if (it == level1_.end()) {
        return std::nullopt;
    }
    
    // 在二级索引中查找具体条目
    size_t start_idx = it->level2_offset / sizeof(Level2Entry);
    size_t end_idx = std::min((it + 1)->level2_offset / sizeof(Level2Entry), level2_.size());
    
    auto sub_it = std::lower_bound(level2_.begin() + start_idx, 
        level2_.begin() + end_idx, key,
        [](const Level2Entry& entry, const std::string& k) {
            return entry.key < k;
        });
    
    if (sub_it != level2_.begin() + end_idx && sub_it->key == key) {
        return sub_it->data_offset;
    }
    return std::nullopt;
}

// 磁带设备模拟类
class TapeDevice {
public:
    // 构造函数，默认容量1GB
    TapeDevice(size_t capacity = 1024 * 1024 * 1024) : 
        capacity_(capacity), 
        current_position_(0),
        data_(capacity, 0) {
        // 初始化磁带状态
        status_.total_blocks = capacity_ / BLOCK_SIZE;
        status_.free_blocks = status_.total_blocks;
        status_.current_position = 0;
    }
    
    // 磁带操作方法
    void rewind() {  // 回绕到起始位置
        current_position_ = 0;
        status_.current_position = 0;
    }
    
    void fast_forward(size_t blocks) {  // 快进
        current_position_ = std::min(current_position_ + blocks * BLOCK_SIZE, capacity_);
        status_.current_position = current_position_ / BLOCK_SIZE;
    }
    
    void fast_reverse(size_t blocks) {  // 快退
        current_position_ = std::max(current_position_ - blocks * BLOCK_SIZE, 0u);
        status_.current_position = current_position_ / BLOCK_SIZE;
    }
    
    void seek(size_t block) {  // 定位到指定块
        if (block < status_.total_blocks) {
            current_position_ = block * BLOCK_SIZE;
            status_.current_position = block;
        }
    }
    
    // 读取数据
    size_t read(char* buffer, size_t size) {
        if (current_position_ + size > capacity_) {
            size = capacity_ - current_position_;
        }
        
        std::copy(data_.begin() + current_position_, 
            data_.begin() + current_position_ + size, buffer);
        current_position_ += size;
        status_.current_position = current_position_ / BLOCK_SIZE;
        
        return size;
    }
    
    // 写入数据
    size_t write(const char* buffer, size_t size) {
        if (current_position_ + size > capacity_) {
            size = capacity_ - current_position_;
        }
        
        std::copy(buffer, buffer + size, data_.begin() + current_position_);
        current_position_ += size;
        status_.current_position = current_position_ / BLOCK_SIZE;
        status_.free_blocks = (capacity_ - current_position_) / BLOCK_SIZE;
        
        return size;
    }
    
    TapeStatus get_status() const { return status_; }  // 获取磁带状态
    
private:
    const size_t capacity_;      // 磁带总容量（字节）
    size_t current_position_;    // 当前位置（字节）
    std::vector<char> data_;     // 磁带数据存储
    TapeStatus status_;          // 磁带状态信息
};

// 文件控制块（FCB）
struct FileControlBlock {
    std::string filename;        // 文件名
    OpenMode mode;               // 打开模式（读/写/追加）
    size_t position;             // 文件内当前位置
    bool eof;                    // 是否到达文件末尾
    IndexType index_type;        // 索引类型
    std::shared_ptr<BaseIndex> index;  // 索引对象
};

// 磁带文件系统类
class TapeFileSystem {
public:
    bool create_file(const std::string& filename, IndexType index_type = IndexType::Linear);
    bool delete_file(const std::string& filename);
    bool open_file(const std::string& filename, OpenMode mode);
    bool close_file(const std::string& filename);
    size_t read_file(const std::string& filename, char* buffer, size_t size);
    size_t write_file(const std::string& filename, const char* buffer, size_t size);
    bool seek_file(const std::string& filename, size_t position);
    size_t tell_file(const std::string& filename) const;
    bool is_eof(const std::string& filename) const;
    
    // 磁带特有操作
    void rewind_file(const std::string& filename);
    void fast_forward_file(const std::string& filename, size_t blocks);
    void fast_reverse_file(const std::string& filename, size_t blocks);
    
private:
    std::map<std::string, FileControlBlock> open_files_;  // 打开的文件
    TapeDevice& tape_;  // 磁带设备引用
    IndexFactory index_factory_;  // 索引工厂
};

// 创建文件实现
bool TapeFileSystem::create_file(const std::string& filename, IndexType index_type) {
    // 检查文件是否已存在
    if (open_files_.find(filename) != open_files_.end()) {
        return false; // 文件已存在
    }
    
    // 使用工厂模式创建索引结构
    std::shared_ptr<BaseIndex> index = index_factory_.create(index_type);
    
    // 初始化文件控制块
    FileControlBlock fcb;
    fcb.filename = filename;
    fcb.mode = OpenMode::None;
    fcb.position = 0;
    fcb.eof = true;
    fcb.index_type = index_type;
    fcb.index = std::move(index);
    
    // 添加到打开文件列表
    open_files_[filename] = fcb;
    
    // 在磁带上创建文件头信息
    FileHeader header;
    header.magic = FILE_MAGIC;
    header.index_type = static_cast<uint8_t>(index_type);
    header.size = 0;
    
    size_t header_size = sizeof(FileHeader);
    size_t block = tape_.allocate_block();
    
    if (block == 0) {
        return false; // 磁带空间不足
    }
    
    // 写入文件头
    tape_.write_block(block, reinterpret_cast<char*>(&header), header_size);
    
    return true;
}

// 线性索引查找性能测试
BENCHMARK(BM_LinearIndex_Find) -> Range(100, 100000);
void BM_LinearIndex_Find(benchmark::State& state) {
    LinearIndex index;
    std::vector<std::string> keys;
    
    // 生成测试数据
    for (int i = 0; i < state.range(0); ++i) {
        std::string key = "record_" + std::to_string(i);
        keys.push_back(key);
        index.insert(key, i * 4096, 1024, i);
    }
    
    // 执行查找测试
    for (auto _ : state) {
        for (const std::string& key : keys) {
            benchmark::DoNotOptimize(index.find(key));
        }
    }
}

// 线性索引插入性能测试
BENCHMARK(BM_LinearIndex_Insert) -> Range(100, 100000);
void BM_LinearIndex_Insert(benchmark::State& state) {
    LinearIndex index;
    
    for (auto _ : state) {
        for (int i = 0; i < state.range(0); ++i) {
            std::string key = "record_" + std::to_string(i);
            index.insert(key, i * 4096, 1024, i);
        }
    }
}

// 多级索引查找性能测试
BENCHMARK(BM_MultiLevelIndex_Find) -> Range(100, 100000);
void BM_MultiLevelIndex_Find(benchmark::State& state) {
    MultiLevelIndex index;
    std::vector<std::string> keys;
    
    for (int i = 0; i < state.range(0); ++i) {
        std::string key = "record_" + std::to_string(i);
        keys.push_back(key);
        index.insert(key, i * 4096, 1024, i);
    }
    
    for (auto _ : state) {
        for (const std::string& key : keys) {
            benchmark::DoNotOptimize(index.find(key));
        }
    }
}

// 多级索引构建时间测试
BENCHMARK(BM_MultiLevelIndex_Build) -> Range(100, 100000);
void BM_MultiLevelIndex_Build(benchmark::State& state) {
    std::vector<DataRecord> records;
    
    for (int i = 0; i < state.range(0); ++i) {
        DataRecord record;
        record.key = "record_" + std::to_string(i);
        record.offset = i * 4096;
        record.length = 1024;
        record.block = i;
        records.push_back(record);
    }
    
    MultiLevelIndex index;
    
    for (auto _ : state) {
        index.build(records);
    }
}