ZIPcmu 15445 2023spring project0 8.74KB

weixin_47734949需要积分:7(1积分=1元)

资源文件列表:

project0.zip 大约有15个文件
  1. project0/
  2. project0/src/
  3. project0/src/include/
  4. project0/src/include/execution/
  5. project0/src/include/execution/expressions/
  6. project0/src/include/execution/expressions/string_expression.h 3.15KB
  7. project0/src/include/primer/
  8. project0/src/include/primer/trie.h 4.3KB
  9. project0/src/include/primer/trie_answer.h 185B
  10. project0/src/include/primer/trie_store.h 1.64KB
  11. project0/src/planner/
  12. project0/src/planner/plan_func_call.cpp 2.04KB
  13. project0/src/primer/
  14. project0/src/primer/trie.cpp 5.5KB
  15. project0/src/primer/trie_store.cpp 2.46KB

资源介绍:

2023的入门实验，cow Trie。
#include "primer/trie.h" #include <string_view> #include "common/exception.h" namespace bustub { template <class T> auto Trie::Get(std::string_view key) const -> const T * { // You should walk through the trie to find the node corresponding to the key. If the node doesn't exist, return // nullptr. After you find the node, you should use `dynamic_cast` to cast it to `const TrieNodeWithValue<T> *`. If // dynamic_cast returns `nullptr`, it means the type of the value is mismatched, and you should return nullptr. // Otherwise, return the value. std::shared_ptr<const TrieNode> cur_node = root_; std::size_t key_size = key.size(); decltype(key_size) idx = 0; while (idx < key_size && cur_node) { char ch = key[idx++]; cur_node = cur_node->children_.find(ch) != cur_node->children_.end() ? cur_node->children_.at(ch) : nullptr; } if (idx != key_size || !cur_node || !cur_node->is_value_node_) { return nullptr; } const auto *leaf = dynamic_cast<const TrieNodeWithValue<T> *>(cur_node.get()); return leaf ? leaf->value_.get() : nullptr; } template <class T> auto Trie::Put(std::string_view key, T value) const -> Trie { // Note that `T` might be a non-copyable type. Always use `std::move` when creating `shared_ptr` on that value. // You should walk through the trie and create new nodes if necessary. If the node corresponding to the key already // exists, you should create a new `TrieNodeWithValue`. std::shared_ptr<T> shared_value = std::make_shared<T>(std::move(value)); std::vector<std::shared_ptr<const TrieNode>> node_stack; // store the same node std::shared_ptr<const TrieNode> cur_node = root_; std::size_t key_size = key.size(); decltype(key_size) idx = 0; // 1.store the same node while (idx < key_size && cur_node) { char ch = key[idx++]; node_stack.push_back(cur_node); cur_node = cur_node->children_.find(ch) != cur_node->children_.end() ? cur_node->children_.at(ch) : nullptr; } // 2.create diff node // 2.1create leaf node std::shared_ptr<const TrieNodeWithValue<T>> leaf_node = cur_node ? std::make_shared<const TrieNodeWithValue<T>>(cur_node->children_, shared_value) : std::make_shared<const TrieNodeWithValue<T>>(shared_value); // 2.2create diff inner node std::shared_ptr<const TrieNode> child_node = leaf_node; while (idx < key_size) { char ch = key[--key_size]; std::map<char, std::shared_ptr<const TrieNode>> children{{ch, child_node}}; cur_node = std::make_shared<const TrieNode>(children); child_node = cur_node; } // 3.copy same node cur_node = child_node; for (size_t i = node_stack.size() - 1; i < node_stack.size(); --i) { cur_node = std::shared_ptr<const TrieNode>(node_stack[i]->Clone()); const_cast<TrieNode *>(cur_node.get())->children_[key[i]] = child_node; child_node = cur_node; } return Trie(cur_node); } auto Trie::Remove(std::string_view key) const -> Trie { // You should walk through the trie and remove nodes if necessary. If the node doesn't contain a value any more, // you should convert it to `TrieNode`. If a node doesn't have children any more, you should remove it. std::vector<std::shared_ptr<const TrieNode>> node_stack; // store the same node std::shared_ptr<const TrieNode> cur_node = root_; std::size_t key_size = key.size(); decltype(key_size) idx = 0; // 1.store the same node while (idx < key_size && cur_node) { char ch = key[idx++]; node_stack.push_back(cur_node); cur_node = cur_node->children_.find(ch) != cur_node->children_.end() ? cur_node->children_.at(ch) : nullptr; } if (idx != key_size || !cur_node || !cur_node->is_value_node_) { return *this; } // 2.create end node std::shared_ptr<const TrieNode> end_node = cur_node->children_.empty() ? nullptr : std::make_shared<const TrieNode>(cur_node->children_); // 3.copy same node std::shared_ptr<const TrieNode> child_node = end_node; cur_node = end_node; for (size_t i = node_stack.size() - 1; i < node_stack.size(); --i) { cur_node = std::shared_ptr<const TrieNode>(node_stack[i]->Clone()); const_cast<TrieNode *>(cur_node.get())->children_[key[i]] = child_node; child_node = cur_node; } return Trie(cur_node); } // Below are explicit instantiation of template functions. // // Generally people would write the implementation of template classes and functions in the header file. However, we // separate the implementation into a .cpp file to make things clearer. In order to make the compiler know the // implementation of the template functions, we need to explicitly instantiate them here, so that they can be picked up // by the linker. template auto Trie::Put(std::string_view key, uint32_t value) const -> Trie; template auto Trie::Get(std::string_view key) const -> const uint32_t *; template auto Trie::Put(std::string_view key, uint64_t value) const -> Trie; template auto Trie::Get(std::string_view key) const -> const uint64_t *; template auto Trie::Put(std::string_view key, std::string value) const -> Trie; template auto Trie::Get(std::string_view key) const -> const std::string *; // If your solution cannot compile for non-copy tests, you can remove the below lines to get partial score. using Integer = std::unique_ptr<uint32_t>; template auto Trie::Put(std::string_view key, Integer value) const -> Trie; template auto Trie::Get(std::string_view key) const -> const Integer *; template auto Trie::Put(std::string_view key, MoveBlocked value) const -> Trie; template auto Trie::Get(std::string_view key) const -> const MoveBlocked *; } // namespace bustub
100+评论
captcha
    相关资源
    类型标题大小时间
    ZIPJava Web 的jar包2.96MB2月前
    ZIPJava实现ocr图片识别（PaddleOCR）飞桨1.64MB2月前
    ZIPspringboot3+ vue3前后端分离项目搭建代码34.85MB2月前
    ZIP图像处理常用的McMaster数据集7.5MB2月前
    ZIPJDK1.8 API帮助文档（纯源，无广告）49.24MB2月前
    ZIPHEX-Float转换工具 16进制转成float 或double类型数据的一个小工具616.29KB2月前
    ZIPN_m3u8DL-CLI_v2.6.3_with_ffmpeg_and_SimpleG.zip5.87MB2月前
    ZIPPython数据分析初探项目 基于Python数据可视化的网易云音乐歌单分析系统 大学编程作业（TUST 天津科技大学 202220.47MB2月前