I want help in the following C++ programming task. Please do coding in C++.
Persistent Data Structures
A persistent data structure is one in which we can make changes (such as inserting and removing elements) while still preserving the original data structure Of course, an easy way to do this is to create a new copy of the entire data structure every time we perform an operation that changes the data structure, but it is much more efficient to only make a copy of the smallest possible portion of the data structure.
First, let\'s look at one of the easiest possible data structures — a stack, implemented using a linked list.
Persistent Stack
Let\'s say that we have a stack S1, and we want to create a new stack S2, which is the result of pushing a new element X onto S1, without changing S1 at all. This is easy — we just add a new element that points to S1:
Starting with the stack S1:
We push X on S1, to get S2, leaving S1 as it was. So after the operation we have two versions of the stack S1 the older version with elements A, B and C and S2 the newer version with elements X, A, B and C.
What about popping? That works in the same way. Starting with our original S1 (elements A, B and C), we can pop off the first element (A), to get S2:
What if we want to push something on to this new stack? It works in the same was as before – if we push an X onto S2 above to get S3, we have
So for every operation you make a new version of the stack while reusing any existing stack elements.
You will have to make a linked list of pointers that will point to the head of the different stack versions.
Also each stack is also implemented as a linked list of elements
SAB
#include
#include #include #include #include #include #include #include #include #include #include namespace dts { template > class PersistentSet { public: PersistentSet(); PersistentSet(Func); bool add(const T&); bool add(T&&); bool remove(const T& key); bool empty() const; size_t history_size() const; class TreeIterator : public std::iterator, std::ptrdiff_t, const T*, const T&> { using node = typename dts::PersistentSet< std::remove_cv_t, Func>::Nodeptr; node itr; node nil; std::stack path; node find_successor(node n) { n = n->rigth; if (n != nil) { while (n->left != nil) { path.push(n); n = n->left; } } else { n = path.top(); path.pop(); } return n; } public: explicit TreeIterator(node n, node pnil) : nil(pnil) //begin { if (n == nil) itr = nil; else { path.push(nil); while (n->left != nil) { path.push(n); n = n->left; } itr = n; } } explicit TreeIterator(node pnil) // end : itr(pnil), nil(pnil) { } TreeIterator& operator++ () { itr = find_successor(itr); return *this; } TreeIterator operator++ (int) { TreeIterator tmp(*this); itr = find_successor(itr); return tmp; } bool operator == (const TreeIterator& rhs) const { return itr == rhs.itr; } bool operator != (const TreeIterator& rhs) const { return itr != rhs.itr; } const T& operator* () const { return itr->key; } const T& operator-> () const { return itr->key; } }; typedef TreeIterator const_iterator; const_iterator begin() const { return begin(roots.size() - 1); } const_iterator begin(size_t index) const { if (index >= roots.size()) throw std::out_of_range(\"out of range\"); return const_iterator(roots[index], nil); } const_iterator end() const { return const_iterator(nil); } private: struct Node; using Nodeptr = std::shared_ptr; struct Node { T key; bool isRed; Nodeptr left; Nodeptr rigth; Node(const T& pkey, bool pisRed, Nodeptr pleft, Nodeptr prigth) : key(pkey), isRed(pisRed), left(pleft), rigth(prigth) { } Node(T&& pkey, bool pisRed, Nodeptr pleft, Nodeptr prigth) : key(std::move(pkey)), isRed(pisRed), left(pleft), rigth(prigth) { } }; std::vector roots; Func cmp; Nodeptr nil; template Nodeptr create_node(TT&& key); Nodeptr copy_node(Nodeptr) const; template bool generic_add(TT&&); template Nodeptr BST_add_recursive(std::queue&, TT&& key, Nodeptr& node); void fixed_add(std::queue &x); template void generic_fixed_add(Nodeptr&, Nodeptr&, std::queue&, ChildA, ChildB); Nodeptr build_path(const T& key, Nodeptr root, std::deque& path); void delete_node(std::deque &); Nodeptr build_min_path(Nodeptr node ,std::deque& path); void transplant(Nodeptr p, Nodeptr x, Nodeptr y); void fixed_remove(Nodeptr x, std::deque& path); template void generic_fixed_delete(Nodeptr&, Nodeptr&, std::deque & path, ChildA, ChildB); template Nodeptr generic_rotate(Nodeptr, Nodeptr ,ChildA, ChildB); static Nodeptr& left(Nodeptr x) { return x->left; }; static Nodeptr& rigth(Nodeptr x) { return x->rigth; }; }; template size_t PersistentSet::history_size() const { return roots.size(); } template bool PersistentSet::empty() const { return roots.back() == nil; } template void PersistentSet::transplant(Nodeptr p , Nodeptr x, Nodeptr y) { if (p == nil) { roots.pop_back(); roots.push_back(y); } else if (p->left == x) p->left = y; else p->rigth = y; } template PersistentSet::PersistentSet() : PersistentSet(Func()) {} template PersistentSet::PersistentSet(Func pcmp) : cmp(pcmp), roots(std::vector()), nil(std::make_shared(T(), false, nullptr, nullptr) ) { roots.push_back(nil); } template template typename PersistentSet::Nodeptr PersistentSet::generic_rotate( Nodeptr p, Nodeptr x, ChildA childA, ChildB childB ) { Nodeptr y = childB(x); childB(x) = childA(y); if (x == roots.back()) { roots.pop_back(); roots.push_back(y); } else if (x == childA(p)) childA(p) = y; else childB(p) = y; childA(y) = x; return y; } template template bool PersistentSet::generic_add(TT&& element) { std::queue path; auto newRoot = BST_add_recursive( path, std::forward(element), roots.back() ); bool added = newRoot != nullptr; if (added) { roots.push_back(newRoot); path.push(nil); fixed_add(path); } return added; } template template typename PersistentSet::Nodeptr PersistentSet::BST_add_recursive(std::queue& path, TT &&element, Nodeptr & node) { if (node == nil) { auto copy = create_node(std::forward(element)); path.push(copy); return copy; } bool isless = cmp(element, node->key); if (!isless && !cmp(node->key, element)) return nullptr; auto dir = isless ? left : rigth; auto child = BST_add_recursive( path, std::forward(element), dir(node) ); if (child == nullptr) return child; auto copy = copy_node(node); path.push(copy); dir(copy) = child; return copy; } template typename PersistentSet::Nodeptr PersistentSet::build_path(const T& element, Nodeptr node, std::deque& path) { if (node == nil) return nullptr; bool isless = cmp(element, node->key); if (!isless && !cmp(node->key, element)) { auto copy = copy_node(node); path.push_back(copy); return copy; } auto dir = isless ? left : rigth; auto child = build_path(element, dir(node), path); if (child == nullptr) return child; auto copy = copy_node(node); path.push_back(copy); dir(copy) = child; return copy; } template bool PersistentSet::add(const T& element) { return generic_add(const_cast (element)); } template bool PersistentSet::add(T&& element) { return generic_add(std::move(element)); } template typename PersistentSet::Nodeptr PersistentSet::copy_node(Nodeptr node) const { if (node == nil) return nil; return std::make_shared(node->key, node->isRed, node->left, node->rigth); } template template typename PersistentSet::Nodeptr PersistentSet::create_node(TT&& key) { return std::make_shared(std::forward(key), true, nil, nil); } template void PersistentSet::delete_node(std::deque & path) { auto z = path.front(); auto x = z->rigth, y = z; if (z->left == nil) { path.pop_front(); transplant(path.front(), z, x); } else if (z->rigth == nil) { path.pop_front(); transplant(path.front(), z, x = z->left); } else { z->rigth = copy_node(z->rigth); y = build_min_path(z->rigth, path); x = y->rigth; z->key = std::move(y->key); transplant(path.front(), y, x); } if (!y->isRed) fixed_remove(x, path); } template typename PersistentSet::Nodeptr PersistentSet::build_min_path(Nodeptr node, std::deque& path) { while (node->left != nil) { node->left = copy_node(node->left); path.push_front(node); node = node->left; } return node; } template void PersistentSet::fixed_remove(Nodeptr x, std::deque& path) { auto p = path.front(); path.pop_front(); while (x != roots.back() && !x->isRed) { if (p->left == x) generic_fixed_delete(x, p, path, left, rigth); else generic_fixed_delete(x, p, path, rigth, left); } auto newX = copy_node(x); transplant(p, x, newX); newX->isRed = false; } template template void PersistentSet::generic_fixed_delete( Nodeptr& x, Nodeptr& p, std::deque & path, ChildA childA, ChildB childB ) { Nodeptr w = childB(p); if (w->isRed) { w = childB(p) = copy_node(w); std::swap(w->isRed, p->isRed); generic_rotate(path.front(), p, childA, childB); path.push_front(w); w = childB(p); } if (!w->left->isRed && !w->rigth->isRed) { w = childB(p) = copy_node(w); w->isRed = true; x = p; p = path.front(); path.pop_front(); } else { if (!childB(w)->isRed) { w = childB(p) = copy_node(w); childA(w) = copy_node(childA(w)); std::swap(w->isRed, childA(w)->isRed); w = generic_rotate(p, w, childB, childA); } w = childB(p) = copy_node(w); childB(w) = copy_node(childB(w)); w->isRed = p->isRed; p->isRed = false; childB(w)->isRed = false; generic_rotate(path.front(), p, childA, childB); x = roots.back(); p = nil; } } template bool PersistentSet::remove(const T& element) { std::deque dq; auto node = build_path(element, roots.back(), dq); bool exist = node != nullptr; if (exist) { roots.push_back(node); dq.push_back(nil); delete_node(dq); } return exist; } template void PersistentSet::fixed_add(std::queue& path) { auto x = path.front(); path.pop(); auto p = path.front(); path.pop(); while (p->isRed) { if (path.front()->left == p) generic_fixed_add(p, x, path, left, rigth); else generic_fixed_add(p, x, path, rigth, left); } roots.back()->isRed = false; } template template void PersistentSet:: generic_fixed_add(Nodeptr &p, Nodeptr &x, std::queue& path, ChildA childA, ChildB childB) { Nodeptr &uncle = childB(path.front()); if (uncle->isRed) { uncle = copy_node(uncle); childB(path.front()) = uncle; p->isRed = false; uncle->isRed = false; path.front()->isRed = true; x = path.front(); path.pop(); p = path.front(); path.pop(); } else { if (x == childB(p)) { std::swap(x, p); generic_rotate(path.front(), x, childA, childB); } auto gp = path.front(); path.pop(); std::swap(gp->isRed, p->isRed); generic_rotate(path.front(), gp, childB, childA); } } }
Homework Sourse
