Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <chrono>
- #include <iostream>
- #include <iterator>
- #include <memory>
- #include <vector>
- #include <cstdlib>
- #include <set>
- #include <random>
- std::vector<int> depths;
- template <typename ValueType>
- struct Node {
- Node(Node* left, Node* right, Node* parent, const ValueType& value)
- : left(left), right(right), parent(parent), value(value) {
- }
- Node* left;
- Node* right;
- Node* parent;
- ValueType value;
- };
- template <typename ValueType>
- class Set;
- template <typename ValueType>
- class SetIterator : public std::iterator<struct bidirectional_iterator_tag, ValueType, size_t,
- ValueType*, ValueType&> {
- public:
- friend class Set<ValueType>;
- SetIterator() : node(nullptr) {
- }
- explicit SetIterator(Node<ValueType>* node) : node(node) {
- }
- SetIterator(const SetIterator&) = default;
- SetIterator& operator=(const SetIterator&) = default;
- SetIterator& operator++() {
- if (node->right) {
- node = node->right;
- while (node->left) {
- node = node->left;
- }
- } else {
- while (node->parent->right == node) {
- node = node->parent;
- }
- node = node->parent;
- }
- return *this;
- }
- SetIterator& operator--() {
- if (node->left) {
- node = node->left;
- while (node->right) {
- node = node->right;
- }
- } else {
- while (node->parent->left == node) {
- node = node->parent;
- }
- node = node->parent;
- }
- return *this;
- }
- SetIterator operator++(int) {
- SetIterator<ValueType> result(node);
- ++*this;
- return result;
- }
- SetIterator operator--(int) {
- SetIterator<ValueType> result(node);
- --*this;
- return result;
- }
- bool operator==(SetIterator other) {
- return node == other.node;
- }
- bool operator!=(SetIterator other) {
- return node != other.node;
- }
- const ValueType& operator*() {
- return node->value;
- }
- const ValueType* operator->() {
- return &(node->value);
- }
- private:
- Node<ValueType>* node;
- };
- template <typename ValueType>
- class Set {
- private:
- void SetRoot(Node<ValueType>* node) {
- root_ = node;
- begin_ = node;
- end_->left = root_;
- root_->parent = end_;
- }
- Node<ValueType>* DeepCopy(Node<ValueType>* cur) {
- auto new_cur = new Node<ValueType>(nullptr, nullptr, nullptr, cur->value);
- if (!(new_cur->value < begin_->value) && !(begin_->value < new_cur->value)) {
- delete begin_;
- begin_ = new_cur;
- }
- if (cur->left) {
- new_cur->left = DeepCopy(cur->left);
- new_cur->left->parent = new_cur;
- }
- if (cur->right) {
- new_cur->right = DeepCopy(cur->right);
- new_cur->right->parent = new_cur;
- }
- return new_cur;
- }
- void ZigZig(Node<ValueType>* node) const {
- auto parent = node->parent;
- auto grand_parent = parent->parent;
- auto grand_grand_parent = grand_parent->parent;
- bool is_root = root_ == grand_parent;
- parent->parent = grand_parent->parent;
- if (grand_grand_parent->left == grand_parent) {
- grand_grand_parent->left = parent;
- } else {
- grand_grand_parent->right = parent;
- }
- grand_parent->left = parent->right;
- if (parent->right) {
- parent->right->parent = grand_parent;
- }
- grand_parent->parent = parent;
- parent->right = grand_parent;
- if (is_root) {
- const_cast<Set<ValueType>*>(this)->root_ = parent;
- }
- }
- void ZagZag(Node<ValueType>* node) const {
- auto parent = node->parent;
- auto grand_parent = parent->parent;
- auto grand_grand_parent = grand_parent->parent;
- bool is_root = grand_parent == root_;
- parent->parent = grand_parent->parent;
- if (grand_grand_parent->left == grand_parent) {
- grand_grand_parent->left = parent;
- } else {
- grand_grand_parent->right = parent;
- }
- grand_parent->right = parent->left;
- if (parent->left) {
- parent->left->parent = grand_parent;
- }
- grand_parent->parent = parent;
- parent->left = grand_parent;
- if (is_root) {
- const_cast<Set<ValueType>*>(this)->root_ = parent;
- }
- }
- void ZagZig(Node<ValueType>* node) const {
- auto parent = node->parent;
- parent->parent->left = node;
- node->parent = parent->parent;
- parent->right = node->left;
- if (node->left) {
- node->left->parent = parent;
- }
- node->left = parent;
- parent->parent = node;
- ZigZig(parent);
- }
- void ZigZag(Node<ValueType>* node) const {
- auto parent = node->parent;
- parent->parent->right = node;
- node->parent = parent->parent;
- parent->left = node->right;
- if (node->right) {
- node->right->parent = parent;
- }
- parent->parent = node;
- node->right = parent;
- ZagZag(parent);
- }
- void Zig(Node<ValueType>* node) const {
- auto parent = node->parent;
- parent->parent->left = node;
- node->parent = parent->parent;
- parent->left = node->right;
- if (node->right) {
- node->right->parent = parent;
- }
- node->right = parent;
- parent->parent = node;
- const_cast<Set<ValueType>*>(this)->root_ = node;
- }
- void Zag(Node<ValueType>* node) const {
- auto parent = node->parent;
- parent->parent->left = node;
- node->parent = parent->parent;
- parent->right = node->left;
- if (node->left) {
- node->left->parent = parent;
- }
- node->left = parent;
- parent->parent = node;
- const_cast<Set<ValueType>*>(this)->root_ = node;
- }
- void SplayNode(Node<ValueType>* node) const {
- while (node != root_) {
- if (node->parent == root_) {
- if (root_->left == node) {
- Zig(node);
- } else {
- Zag(node);
- }
- continue;
- }
- auto parent = node->parent;
- bool is_left_child = node->parent->left == node;
- bool is_parent_left_child = parent->parent->left == parent;
- if (is_parent_left_child) {
- if (is_left_child) {
- ZigZig(node);
- } else {
- ZagZig(node);
- }
- } else {
- if (is_left_child) {
- ZigZag(node);
- } else {
- ZagZag(node);
- }
- }
- }
- }
- SetIterator<ValueType> LowerBound(Node<ValueType>* node, const ValueType& value) const {
- if (!(value < node->value) && !(node->value < value)) {
- return SetIterator{node};
- }
- auto child = node;
- bool is_left = true;
- if (value < node->value) {
- is_left = true;
- child = node->left;
- } else {
- is_left = false;
- child = node->right;
- }
- if (!child) {
- if (is_left) {
- return SetIterator{node};
- } else {
- auto iter = SetIterator<ValueType>(node);
- ++iter;
- return iter;
- }
- } else {
- return LowerBound(child, value);
- };
- }
- void Delete(Node<ValueType>* cur) {
- if (cur->left) {
- Delete(cur->left);
- }
- if (cur->right) {
- Delete(cur->right);
- }
- delete cur;
- }
- Node<ValueType>* root_ = nullptr;
- Node<ValueType>* end_ = new Node<ValueType>(nullptr, nullptr, nullptr, ValueType());
- Node<ValueType>* begin_ = end_;
- size_t size_ = 0;
- public:
- typedef SetIterator<ValueType> iterator;
- Set() {
- }
- template <typename ForwardIT>
- Set(ForwardIT begin, ForwardIT end) {
- for (auto it = begin; it != end; ++it) {
- insert(*it);
- }
- }
- explicit Set(std::initializer_list<ValueType> ilist) {
- for (const auto& elem : ilist) {
- insert(elem);
- }
- }
- Set(const Set& other) {
- if (other.size_ == 0) {
- return;
- }
- begin_ = new Node<ValueType>(nullptr, nullptr, nullptr, ValueType());
- begin_->value = other.begin_->value;
- root_ = DeepCopy(other.root_);
- end_->left = root_;
- root_->parent = end_;
- size_ = other.size_;
- }
- Set& operator=(const Set& other) {
- if (this == &other) {
- return *this;
- }
- this->~Set();
- end_ = new Node<ValueType>(nullptr, nullptr, nullptr, ValueType());
- if (other.size_ == 0) {
- size_ = 0;
- root_ = nullptr;
- begin_ = end_;
- end_->left = root_;
- return *this;
- }
- begin_ = new Node<ValueType>(nullptr, nullptr, nullptr, ValueType());
- begin_->value = other.begin_->value;
- root_ = DeepCopy(other.root_);
- end_->left = root_;
- root_->parent = end_;
- size_ = other.size_;
- return *this;
- }
- ~Set() {
- if (end_) {
- std::vector<Node<ValueType>*> nodes(size_);
- int counter = 0;
- for (auto iter = begin(); iter != end(); ++iter) {
- nodes[counter] = iter.node;
- ++counter;
- }
- for (size_t i = 0; i < nodes.size(); ++i) {
- delete nodes[i];
- }
- delete end_;
- }
- }
- size_t size() const {
- return size_;
- }
- bool empty() const {
- return size_ == 0;
- }
- void insert(const ValueType& value) {
- auto node = new Node<ValueType>(nullptr, nullptr, nullptr, value);
- if (!root_) {
- SetRoot(node);
- ++size_;
- return;
- }
- find(value);
- if (!(root_->value < value) && !(value < root_->value)) {
- delete node;
- return;
- }
- if (value < root_->value) {
- node->right = root_;
- root_->parent = node;
- if (root_->left) {
- node->left = root_->left;
- root_->left->parent = node;
- root_->left = nullptr;
- }
- } else {
- node->left = root_;
- root_->parent = node;
- if (root_->right) {
- node->right = root_->right;
- root_->right->parent = node;
- root_->right = nullptr;
- }
- }
- node->parent = end_;
- end_->left = node;
- root_ = node;
- if (node->value < begin_->value) {
- begin_ = node;
- }
- ++size_;
- }
- void erase(const ValueType& value) {
- if (!root_) {
- return;
- }
- find(value);
- if ((root_->value < value) || (value < root_->value)) {
- return;
- }
- if (begin_ == root_) {
- auto iter = SetIterator<ValueType>(root_);
- ++iter;
- begin_ = iter.node;
- }
- if (!root_->left) {
- auto old_root = root_;
- end_->left = root_->right;
- if (root_->right) {
- root_->right->parent = root_->parent;
- root_ = root_->right;
- } else {
- root_ = nullptr;
- }
- delete old_root;
- --size_;
- return;
- }
- auto right_tree = root_->right;
- Node<ValueType>* old_root = root_;
- root_ = root_->left;
- find(value);
- root_->right = right_tree;
- if (right_tree) {
- right_tree->parent = root_;
- }
- end_->left = root_;
- root_->parent = end_;
- --size_;
- delete old_root;
- }
- SetIterator<ValueType> find(const ValueType& value) const {
- if (size_ == 0) {
- return SetIterator{end_};
- }
- int depth = 0;
- Node<ValueType>* node = root_;
- while (node) {
- if (!(node->value < value) && !(value < node->value)) {
- depths.push_back(depth);
- SplayNode(node);
- return SetIterator(node);
- }
- Node<ValueType>* child = nullptr;
- if (node->value < value) {
- child = node->right;
- } else {
- child = node->left;
- }
- if (!child) {
- depths.push_back(depth);
- SplayNode(node);
- return SetIterator{end_};
- } else {
- node = child;
- }
- ++depth;
- }
- return SetIterator{end_};
- }
- SetIterator<ValueType> lower_bound(const ValueType& value) const {
- if (size_ == 0) {
- return SetIterator{end_};
- }
- return LowerBound(root_, value);
- }
- SetIterator<ValueType> begin() const {
- return SetIterator{begin_};
- }
- SetIterator<ValueType> end() const {
- return SetIterator{end_};
- }
- };
- std::ostream& operator<<(std::ostream& os, const std::vector<int> vec) {
- for (auto elem : vec) {
- os << elem;
- }
- return os;
- }
- void TestInsert() {
- std::vector<int> sorted = {1, 2, 3, 4, 5, 6, 7, 8};
- std::vector<int> shuffled = sorted;
- while (std::next_permutation(shuffled.begin(), shuffled.end())) {
- Set<int> s(shuffled.begin(), shuffled.end());
- std::vector<int> from_set;
- for (auto elem : s) {
- from_set.push_back(elem);
- }
- if (from_set != sorted) {
- std::cout << shuffled;
- exit(0);
- }
- }
- }
- void TestFind() {
- Set<int> s{1, 6, 3, 8, 2, 4, 7, 5};
- auto iter = s.find(1);
- assert(*iter == 1);
- assert(iter == s.begin());
- assert(iter != s.end());
- iter = s.find(9);
- assert(iter == s.end());
- assert(iter != s.begin());
- }
- void TestErase() {
- Set<int> s{1, 6, 3, 8, 2, 4, 7, 5};
- for (int i = 0; i <= 9; ++i) {
- s.erase(i);
- assert(s.find(i) == s.end());
- }
- assert(s.empty());
- s = Set{1, 6, 3, 8, 2, 4, 7, 5};
- s.erase(9u);
- assert(s.size() == 8u);
- s.erase(4);
- s.erase(4);
- s.erase(4);
- assert(s.size() == 7u);
- }
- void TestLowerBound() {
- Set<int> s = Set{1, 5, 6, 9, 12};
- std::vector<int> ans = {1, 1, 5, 5, 5, 5, 6, 9, 9, 9, 12, 12, 12};
- for (int i = 0; i <= 12; ++i) {
- auto iter = s.lower_bound(i);
- assert(*iter == ans[i]);
- }
- assert(s.lower_bound(13) == s.end());
- }
- void TestBig() {
- Set<int> s;
- std::vector<int> vec;
- for (int i = 0; i < 1000000; ++i) {
- vec.push_back(i);
- }
- std::shuffle(vec.begin(), vec.end(), std::mt19937());
- for (auto i : vec) {
- s.insert(i);
- }
- std::shuffle(vec.begin(), vec.end(), std::mt19937());
- for (int i = 0; i < 1000000; ++i) {
- s.find(vec[i]);
- }
- std::shuffle(vec.begin(), vec.end(), std::mt19937());
- for (int i = 0; i < 1000000; ++i) {
- s.erase(vec[i]);
- }
- }
- int main() {
- // TestLowerBound();
- // TestInsert();
- // TestErase();
- // TestFind();
- TestBig();
- std::cout << depths.size() << std::endl;
- int64_t sum = 0;
- for (int i = 0; i < depths.size(); ++i) {
- sum += (int64_t)depths[i];
- }
- std::cout << sum / (double)depths.size() << std::endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement