#include #ifndef SJTU_VECTOR_HPP #define SJTU_VECTOR_HPP #include #include #include #include #include namespace sjtu { /** * a data container like std::vector * store data in a successive memory and support random access. */ template class vector { static std::allocator alloc; size_t allocated_length; size_t current_length; T *raw_beg, *raw_end; public: /** * you can see RandomAccessIterator at CppReference for help. */ class const_iterator; class iterator { // The following code is written for the C++ type_traits library. // Type traits is a C++ feature for describing certain properties of a type. // For instance, for an iterator, iterator::value_type is the type that the // iterator points to. // STL algorithms and containers may use these type_traits (e.g. the // following typedef) to work properly. In particular, without the following // code, // @code{std::sort(iter, iter1);} would not compile. // See these websites for more information: // https://en.cppreference.com/w/cpp/header/type_traits // About value_type: // https://blog.csdn.net/u014299153/article/details/72419713 About // iterator_category: https://en.cppreference.com/w/cpp/iterator friend class vector; public: using difference_type = std::ptrdiff_t; using value_type = T; using pointer = T *; using reference = T &; using iterator_category = std::random_access_iterator_tag; private: vector *domain; T *raw_pointer; iterator(vector *domain, T *raw_pointer) : domain(domain), raw_pointer(raw_pointer) {} public: /** * return a new iterator which pointer n-next elements * as well as operator- */ iterator operator+(const int &n) const { iterator temp = *this; temp.raw_pointer += n; return temp; } iterator operator-(const int &n) const { iterator temp = *this; temp.raw_pointer -= n; return temp; } // return the distance between two iterators, // if these two iterators point to different vectors, throw // invaild_iterator. int operator-(const iterator &rhs) const { return raw_pointer - rhs.raw_pointer; } iterator &operator+=(const int &n) { raw_pointer += n; return *this; } iterator &operator-=(const int &n) { raw_pointer -= n; return *this; } /** * TODO iter++ */ iterator operator++(int) { iterator temp = *this; raw_pointer++; return temp; } /** * TODO ++iter */ iterator &operator++() { raw_pointer++; return *this; } /** * TODO iter-- */ iterator operator--(int) { iterator temp = *this; raw_pointer--; return temp; } /** * TODO --iter */ iterator &operator--() { raw_pointer--; return *this; } /** * TODO *it */ T &operator*() const { return *raw_pointer; } /** * a operator to check whether two iterators are same (pointing to the same * memory address). */ bool operator==(const iterator &rhs) const { return raw_pointer == rhs.raw_pointer; } bool operator==(const const_iterator &rhs) const { return raw_pointer == rhs.raw_pointer; } /** * some other operator for iterator. */ bool operator!=(const iterator &rhs) const { return raw_pointer != rhs.raw_pointer; } bool operator!=(const const_iterator &rhs) const { return raw_pointer != rhs.raw_pointer; } }; /** * TODO * has same function as iterator, just for a const object. */ class const_iterator { friend class vector; public: using difference_type = std::ptrdiff_t; using value_type = T; using pointer = T *; using reference = T &; using iterator_category = std::random_access_iterator_tag; private: const vector *domain; const T *raw_pointer; inline const_iterator(const vector *domain, const T *raw_pointer) : domain(domain), raw_pointer(raw_pointer) {} public: /** * return a new iterator which pointer n-next elements * as well as operator- */ const_iterator operator+(const int &n) const { const_iterator temp = *this; temp.raw_pointer += n; return temp; } const_iterator operator-(const int &n) const { const_iterator temp = *this; temp.raw_pointer -= n; return temp; } // return the distance between two iterators, // if these two iterators point to different vectors, throw // invaild_iterator. int operator-(const const_iterator &rhs) const { return raw_pointer - rhs.raw_pointer; } const_iterator &operator+=(const int &n) { raw_pointer += n; return *this; } const_iterator &operator-=(const int &n) { raw_pointer -= n; return *this; } /** * TODO iter++ */ const_iterator operator++(int) { const_iterator temp = *this; raw_pointer++; return temp; } /** * TODO ++iter */ const_iterator &operator++() { raw_pointer++; return *this; } /** * TODO iter-- */ const_iterator operator--(int) { const_iterator temp = *this; raw_pointer--; return temp; } /** * TODO --iter */ const_iterator &operator--() { raw_pointer--; return *this; } /** * TODO *it */ const T &operator*() const { return *raw_pointer; } /** * a operator to check whether two iterators are same (pointing to the same * memory address). */ bool operator==(const iterator &rhs) const { return raw_pointer == rhs.raw_pointer; } bool operator==(const const_iterator &rhs) const { return raw_pointer == rhs.raw_pointer; } /** * some other operator for iterator. */ bool operator!=(const iterator &rhs) const { return raw_pointer != rhs.raw_pointer; } bool operator!=(const const_iterator &rhs) const { return raw_pointer != rhs.raw_pointer; } }; /** * TODO Constructs * At least two: default constructor, copy constructor */ vector() { raw_beg = alloc.allocate(1); raw_end = raw_beg; allocated_length = 1; current_length = 0; } vector(const vector &other) { raw_beg = alloc.allocate(other.allocated_length); raw_end = raw_beg + other.current_length; allocated_length = other.allocated_length; current_length = other.current_length; for (size_t i = 0; i < current_length; ++i) { std::allocator_traits::construct(alloc, raw_beg + i, other.raw_beg[i]); } } vector(vector &&other) noexcept { raw_beg = other.raw_beg; raw_end = other.raw_end; allocated_length = other.allocated_length; current_length = other.current_length; other.raw_beg = nullptr; other.raw_end = nullptr; other.allocated_length = 0; other.current_length = 0; } ~vector() { if (raw_beg != nullptr) { for (size_t i = 0; i < current_length; ++i) { std::allocator_traits::destroy(alloc, raw_beg + i); } alloc.deallocate(raw_beg, allocated_length); } } /** * TODO Assignment operator */ vector &operator=(const vector &other) { if (this == &other) return *this; if (raw_beg != nullptr) { for (size_t i = 0; i < current_length; ++i) { std::allocator_traits::destroy(alloc, raw_beg + i); } alloc.deallocate(raw_beg, allocated_length); } raw_beg = alloc.allocate(other.allocated_length); raw_end = raw_beg + other.current_length; allocated_length = other.allocated_length; current_length = other.current_length; for (size_t i = 0; i < current_length; ++i) { std::allocator_traits::construct(alloc, raw_beg + i, other.raw_beg[i]); } return *this; } vector &operator=(vector &&other) noexcept { if (this == &other) return *this; if (raw_beg != nullptr) { for (size_t i = 0; i < current_length; ++i) { std::allocator_traits::destroy(alloc, raw_beg + i); } alloc.deallocate(raw_beg, allocated_length); } raw_beg = other.raw_beg; raw_end = other.raw_end; allocated_length = other.allocated_length; current_length = other.current_length; other.raw_beg = nullptr; other.raw_end = nullptr; other.allocated_length = 0; other.current_length = 0; return *this; } /** * assigns specified element with bounds checking * throw index_out_of_bound if pos is not in [0, size) */ T &at(const size_t &pos) { return raw_beg[pos]; } const T &at(const size_t &pos) const { return raw_beg[pos]; } /** * assigns specified element with bounds checking * throw index_out_of_bound if pos is not in [0, size) * !!! Pay attentions * In STL this operator does not check the boundary but I want you to do. */ T &operator[](const size_t &pos) { return raw_beg[pos]; } const T &operator[](const size_t &pos) const { return raw_beg[pos]; } /** * access the first element. * throw container_is_empty if size == 0 */ const T &front() const { return raw_beg[0]; } /** * access the last element. * throw container_is_empty if size == 0 */ const T &back() const { return raw_end[-1]; } /** * returns an iterator to the beginning. */ iterator begin() { return iterator(this, raw_beg); } const_iterator cbegin() const { return const_iterator(this, raw_beg); } /** * returns an iterator to the end. */ iterator end() { return iterator(this, raw_end); } const_iterator cend() const { return const_iterator(this, raw_end); } /** * checks whether the container is empty */ bool empty() const { return current_length == 0; } /** * returns the number of elements */ size_t size() const { return current_length; } /** * clears the contents */ void clear() { if (raw_beg != nullptr) { for (size_t i = 0; i < current_length; ++i) { std::allocator_traits::destroy(alloc, raw_beg + i); } alloc.deallocate(raw_beg, allocated_length); } raw_beg = alloc.allocate(1); raw_end = raw_beg; allocated_length = 1; current_length = 0; } /** * inserts value before pos * returns an iterator pointing to the inserted value. */ iterator insert(iterator pos, const T &value) { if (current_length == allocated_length) { size_t new_allocated_length = allocated_length * 2; T *new_raw_beg = alloc.allocate(new_allocated_length); pos.raw_pointer = new_raw_beg + (pos.raw_pointer - raw_beg); for (size_t i = 0; i < current_length; ++i) { std::allocator_traits::construct( alloc, new_raw_beg + i, std::move(raw_beg[i])); std::allocator_traits::destroy(alloc, raw_beg + i); } alloc.deallocate(raw_beg, allocated_length); raw_beg = new_raw_beg; raw_end = raw_beg + current_length; allocated_length = new_allocated_length; } for (T *i = raw_end; i != pos.raw_pointer; --i) { std::allocator_traits::construct(alloc, i, std::move(*(i - 1))); std::allocator_traits::destroy(alloc, i - 1); } std::allocator_traits::construct(alloc, pos.raw_pointer, value); raw_end++; current_length++; return pos; } /** * inserts value at index ind. * after inserting, this->at(ind) == value * returns an iterator pointing to the inserted value. * throw index_out_of_bound if ind > size (in this situation ind can be size * because after inserting the size will increase 1.) */ iterator insert(const size_t &ind, const T &value) { if (current_length == allocated_length) { size_t new_allocated_length = allocated_length * 2; T *new_raw_beg = alloc.allocate(new_allocated_length); for (size_t i = 0; i < current_length; ++i) { alloc.construct(new_raw_beg + i, std::move(raw_beg[i])); alloc.destroy(raw_beg + i); } alloc.deallocate(raw_beg, allocated_length); raw_beg = new_raw_beg; raw_end = raw_beg + current_length; allocated_length = new_allocated_length; } for (T *i = raw_end; i != raw_beg + ind; --i) { alloc.construct(i, std::move(*(i - 1))); alloc.destroy(i - 1); } alloc.construct(raw_beg + ind, value); raw_end++; current_length++; return iterator(this, raw_beg + ind); } /** * removes the element at pos. * return an iterator pointing to the following element. * If the iterator pos refers the last element, the end() iterator is * returned. */ iterator erase(iterator pos) { for (T *i = pos.raw_pointer; i != raw_end - 1; ++i) { std::allocator_traits::construct(alloc, i, std::move(*(i + 1))); std::allocator_traits::destroy(alloc, i + 1); } raw_end--; current_length--; if (current_length != 0 && current_length <= allocated_length / 4) { size_t new_allocated_length = allocated_length / 2; T *new_raw_beg = alloc.allocate(new_allocated_length); for (size_t i = 0; i < current_length; ++i) { std::allocator_traits::construct( alloc, new_raw_beg + i, std::move(raw_beg[i])); std::allocator_traits::destroy(alloc, raw_beg + i); } alloc.deallocate(raw_beg, allocated_length); raw_beg = new_raw_beg; raw_end = raw_beg + current_length; allocated_length = new_allocated_length; } return pos; } /** * removes the element with index ind. * return an iterator pointing to the following element. * throw index_out_of_bound if ind >= size */ iterator erase(const size_t &ind) { for (T *i = raw_beg + ind; i != raw_end - 1; ++i) { alloc.construct(i, std::move(*(i + 1))); alloc.destroy(i + 1); } raw_end--; current_length--; if (current_length != 0 && current_length <= allocated_length / 4) { size_t new_allocated_length = allocated_length / 2; T *new_raw_beg = alloc.allocate(new_allocated_length); for (size_t i = 0; i < current_length; ++i) { alloc.construct(new_raw_beg + i, std::move(raw_beg[i])); alloc.destroy(raw_beg + i); } alloc.deallocate(raw_beg, allocated_length); raw_beg = new_raw_beg; raw_end = raw_beg + current_length; allocated_length = new_allocated_length; } return iterator(this, raw_beg + ind); } /** * adds an element to the end. */ void push_back(const T &value) { if (current_length == allocated_length) [[unlikely]] { size_t new_allocated_length = allocated_length * 2; T *new_raw_beg = alloc.allocate(new_allocated_length); for (size_t i = 0; i < current_length; ++i) { std::allocator_traits::construct( alloc, new_raw_beg + i, std::move(raw_beg[i])); std::allocator_traits::destroy(alloc, raw_beg + i); } alloc.deallocate(raw_beg, allocated_length); raw_beg = new_raw_beg; raw_end = raw_beg + current_length; allocated_length = new_allocated_length; } std::allocator_traits::construct(alloc, raw_end, value); raw_end++; current_length++; } /** * remove the last element from the end. * throw container_is_empty if size() == 0 */ void pop_back() { std::allocator_traits::destroy(alloc, raw_end - 1); raw_end--; current_length--; if (current_length != 0 && current_length <= allocated_length / 4) [[unlikely]] { size_t new_allocated_length = allocated_length / 2; T *new_raw_beg = alloc.allocate(new_allocated_length); for (size_t i = 0; i < current_length; ++i) { std::allocator_traits::construct( alloc, new_raw_beg + i, std::move(raw_beg[i])); std::allocator_traits::destroy(alloc, raw_beg + i); } alloc.deallocate(raw_beg, allocated_length); raw_beg = new_raw_beg; raw_end = raw_beg + current_length; allocated_length = new_allocated_length; } } }; template std::allocator vector::alloc; } // namespace sjtu #endif typedef unsigned long long hash_t; static inline hash_t Hash(std::string str) noexcept { /* Reference: http://xorshift.di.unimi.it/splitmix64.c */ static const std::string salt1 = "23af0j29d"; static const std::string salt2 = "09dkl020"; constexpr static char inner_salt[17] = "si9aW@zl#2$3%4^!"; str = salt1 + str + salt2; hash_t ret = 0; int i = 0; for (; i + 8 <= str.length(); i += 8) { ret ^= *reinterpret_cast(str.c_str() + i); ret ^= *reinterpret_cast(inner_salt + (i & 15)); ret += 0x9e3779b97f4a7c15; ret = (ret ^ (ret >> 30)) * 0xbf58476d1ce4e5b9; ret = (ret ^ (ret >> 27)) * 0x94d049bb133111eb; ret ^= ret >> 31; } for (; i < str.length(); ++i) { ret ^= str[i]; ret ^= inner_salt[i & 15]; ret += 0x9e3779b97f4a7c15; ret = (ret ^ (ret >> 30)) * 0xbf58476d1ce4e5b9; ret = (ret ^ (ret >> 27)) * 0x94d049bb133111eb; ret ^= ret >> 31; } return ret; } namespace sjtu { template class unordered_map { }; // implementation of unordered_map for Key = std::string template class unordered_map { static const size_t kMaxBucketSize = 1 << 10; struct Node { std::string key; T value; Node *next; Node() : next(nullptr) {} Node(const std::string &key, const T &value, Node *next = nullptr) : key(key), value(value), next(next) {} }; Node *buckets[kMaxBucketSize]; size_t bucket_size; size_t element_size; public: unordered_map() : bucket_size(kMaxBucketSize), element_size(0) { for (size_t i = 0; i < kMaxBucketSize; ++i) { buckets[i] = nullptr; } } ~unordered_map() { for (size_t i = 0; i < kMaxBucketSize; ++i) { Node *cur = buckets[i]; while (cur != nullptr) { Node *temp = cur; cur = cur->next; delete temp; } } } T &operator[](const std::string &key) { size_t hash = Hash(key) & (kMaxBucketSize - 1); Node *cur = buckets[hash]; while (cur != nullptr) { if (cur->key == key) return cur->value; cur = cur->next; } cur = new Node(key, T(), buckets[hash]); buckets[hash] = cur; element_size++; return cur->value; } T &at(const std::string &key) { size_t hash = Hash(key) & (kMaxBucketSize - 1); Node *cur = buckets[hash]; while (cur != nullptr) { if (cur->key == key) return cur->value; cur = cur->next; } throw std::out_of_range("Key not found"); } const T &at(const std::string &key) const { size_t hash = Hash(key) & (kMaxBucketSize - 1); Node *cur = buckets[hash]; while (cur != nullptr) { if (cur->key == key) return cur->value; cur = cur->next; } throw std::out_of_range("Key not found"); } size_t count(const std::string &key) const { size_t hash = Hash(key) & (kMaxBucketSize - 1); Node *cur = buckets[hash]; while (cur != nullptr) { if (cur->key == key) return 1; cur = cur->next; } return 0; } void erase(const std::string &key) { size_t hash = Hash(key) & (kMaxBucketSize - 1); Node *cur = buckets[hash]; if (cur == nullptr) return; if (cur->key == key) { buckets[hash] = cur->next; delete cur; element_size--; return; } while (cur->next != nullptr) { if (cur->next->key == key) { Node *temp = cur->next; cur->next = cur->next->next; delete temp; element_size--; return; } cur = cur->next; } } void clear() { for (size_t i = 0; i < kMaxBucketSize; ++i) { Node *cur = buckets[i]; while (cur != nullptr) { Node *temp = cur; cur = cur->next; delete temp; } buckets[i] = nullptr; } element_size = 0; } size_t size() const { return element_size; } bool Have(const std::string &key) const { size_t hash = Hash(key) & (kMaxBucketSize - 1); Node *cur = buckets[hash]; while (cur != nullptr) { if (cur->key == key) return true; cur = cur->next; } return false; } }; } // namespace sjtu class ClassType { public: enum ImportType { kPublicImport, kProtectedImport, kPrivateImport }; enum StatusType { kPublic = 4, kProtected = 3, kPrivate = 2, kUnvisible = 1, kNone = 0 }; void Import(ClassType &src, ImportType import_type) { if (import_type == ImportType::kPublicImport) { pub_anc.push_back(&src); } else if (import_type == ImportType::kProtectedImport) { prot_anc.push_back(&src); } else { priv_anc.push_back(&src); } } void AddElement(const std::string &name, StatusType status) { elements[name] = status; } StatusType QueryElement(const std::string &name) { return DFSSearch(this, name); } private: static StatusType DFSSearch(ClassType *rt, const std::string name) { StatusType res = StatusType::kNone; if (rt->elements.Have(name)) res = rt->elements[name]; for (int i = 0; i < rt->pub_anc.size(); i++) { StatusType sub_res = DFSSearch(rt->pub_anc[i], name); if (sub_res == StatusType::kPrivate) sub_res = StatusType::kUnvisible; res = (sub_res > res) ? sub_res : res; } for (int i = 0; i < rt->prot_anc.size(); i++) { StatusType sub_res = DFSSearch(rt->prot_anc[i], name); if (sub_res == StatusType::kPrivate) sub_res = StatusType::kUnvisible; if ((sub_res == StatusType::kPublic) || (sub_res == StatusType::kProtected)) sub_res = StatusType::kProtected; res = (sub_res > res) ? sub_res : res; } for (int i = 0; i < rt->priv_anc.size(); i++) { StatusType sub_res = DFSSearch(rt->priv_anc[i], name); if (sub_res == StatusType::kPrivate) sub_res = StatusType::kUnvisible; if ((sub_res == StatusType::kPublic) || (sub_res == StatusType::kProtected)) sub_res = StatusType::kPrivate; res = (sub_res > res) ? sub_res : res; } return res; } sjtu::unordered_map elements; sjtu::vector pub_anc, prot_anc, priv_anc; }; int main() { #ifdef local freopen("pro.in", "r", stdin); #endif // ifdef local int n; sjtu::unordered_map class_registery; std::cin >> n; for (int i = 0; i < n; i++) { std::string name; std::cin >> name; class_registery[name]; int k0; std::cin >> k0; for (int j = 0; j < k0; j++) { std::string method, srcname; std::cin >> method >> srcname; if (method == "public") class_registery[name].Import(class_registery[srcname], ClassType::ImportType::kPublicImport); else if (method == "private") class_registery[name].Import(class_registery[srcname], ClassType::ImportType::kPrivateImport); else class_registery[name].Import(class_registery[srcname], ClassType::ImportType::kProtectedImport); } int k1; std::cin >> k1; for (int j = 0; j < k1; j++) { std::string mode, element_name; std::cin >> mode >> element_name; if (mode == "public") class_registery[name].AddElement(element_name, ClassType::StatusType::kPublic); else if (mode == "private") class_registery[name].AddElement(element_name, ClassType::StatusType::kPrivate); else class_registery[name].AddElement(element_name, ClassType::StatusType::kProtected); } } int m; std::cin >> m; for (int i = 0; i < m; i++) { std::string class_name, element_name; std::cin >> class_name >> element_name; ClassType::StatusType stat = class_registery[class_name].QueryElement(element_name); switch (stat) { case ClassType::StatusType::kNone: std::cout << "None\n"; break; case ClassType::StatusType::kPrivate: std::cout << "Private\n"; break; case ClassType::StatusType::kProtected: std::cout << "Protected\n"; break; case ClassType::StatusType::kPublic: std::cout << "Public\n"; break; case ClassType::StatusType::kUnvisible: std::cout << "Can not Fetch\n"; break; } } return 0; }