818 lines
25 KiB
C++
818 lines
25 KiB
C++
#include <iostream>
|
|
#ifndef SJTU_VECTOR_HPP
|
|
#define SJTU_VECTOR_HPP
|
|
|
|
#include <climits>
|
|
#include <cstddef>
|
|
#include <exception>
|
|
#include <iterator>
|
|
#include <memory>
|
|
|
|
namespace sjtu {
|
|
/**
|
|
* a data container like std::vector
|
|
* store data in a successive memory and support random access.
|
|
*/
|
|
template <typename T>
|
|
class vector {
|
|
static std::allocator<T> 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<T>;
|
|
|
|
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<T> *domain;
|
|
T *raw_pointer;
|
|
iterator(vector<T> *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<T>;
|
|
|
|
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<T> *domain;
|
|
const T *raw_pointer;
|
|
inline const_iterator(const vector<T> *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<decltype(alloc)>::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<decltype(alloc)>::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<decltype(alloc)>::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<decltype(alloc)>::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<decltype(alloc)>::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<decltype(alloc)>::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<decltype(alloc)>::construct(
|
|
alloc, new_raw_beg + i, std::move(raw_beg[i]));
|
|
std::allocator_traits<decltype(alloc)>::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<decltype(alloc)>::construct(alloc, i,
|
|
std::move(*(i - 1)));
|
|
std::allocator_traits<decltype(alloc)>::destroy(alloc, i - 1);
|
|
}
|
|
std::allocator_traits<decltype(alloc)>::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<decltype(alloc)>::construct(alloc, i,
|
|
std::move(*(i + 1)));
|
|
std::allocator_traits<decltype(alloc)>::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<decltype(alloc)>::construct(
|
|
alloc, new_raw_beg + i, std::move(raw_beg[i]));
|
|
std::allocator_traits<decltype(alloc)>::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<decltype(alloc)>::construct(
|
|
alloc, new_raw_beg + i, std::move(raw_beg[i]));
|
|
std::allocator_traits<decltype(alloc)>::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<decltype(alloc)>::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<decltype(alloc)>::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<decltype(alloc)>::construct(
|
|
alloc, new_raw_beg + i, std::move(raw_beg[i]));
|
|
std::allocator_traits<decltype(alloc)>::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 <typename T>
|
|
std::allocator<T> vector<T>::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<const hash_t *>(str.c_str() + i);
|
|
ret ^= *reinterpret_cast<const hash_t *>(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 <typename Key, typename T>
|
|
class unordered_map {
|
|
|
|
};
|
|
// implementation of unordered_map for Key = std::string
|
|
template <typename T>
|
|
class unordered_map<std::string, T> {
|
|
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<std::string, StatusType> elements;
|
|
sjtu::vector<ClassType *> pub_anc, prot_anc, priv_anc;
|
|
};
|
|
int main() {
|
|
#ifdef local
|
|
freopen("pro.in", "r", stdin);
|
|
#endif // ifdef local
|
|
int n;
|
|
sjtu::unordered_map<std::string, ClassType> 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;
|
|
} |