Помоги мне с проектом. Мой проект - Реализовать библиотеку со Массив в persistent-варианте:
Мне также нужно сделать следующие дополнительные требования (я отмечу те, что уже сделал знаком "+", а те, которые не сделал я отмечу знаком "-")
1+) Обеспечить произвольную вложенность данных (по аналогии с динамическими языками), не отказываясь при этом полностью от типизации посредством generic/template.
2-) Реализовать универсальный undo-redo механизм для перечисленных структур с поддержкой каскадности (для вложенных структур)
3+) Реализовать более эффективное по скорости доступа представление структур данных, чем fat-node
Вот мой класс и его методы:

template <typename T>
struct Node
{
	Node<T>* left_child{};
	Node<T>* right_child{};
	T value{};
};

template <typename T>
class PersistentArray
{
private:

	// base version
	T* base{};

	// size of base version
	int size{};

	std::stack<int> undo_stack; // TODO: Индексы версий для undo
	std::stack<int> redo_stack; // TODO: Индексы версий для redo

	// container for roots of versions
	std::vector<Node<T>*> versions{};

	std::vector<std::pair<int, int>> parent_children_relation{};

	// recursive function to build tree with leafs as elemnts of _array in [_l..._r] and _node as root of version
	void buildTree(Node<T>* _node, T* _array, int _left_border, int _right_border);

	// recursive function to add new version by changing one value in one of previous version
	void add(Node<T>* _to, Node<T>* _from, int _left_border, int _right_border, int _position, T _new_value);

	// recursive function to get element of specific node
	T get(Node<T>* _node, int _left_border, int _right_border, int _position);

	// recursive function to count leaves in a tree
	int countLeaves(Node<T>* _node);

	// print from [_left] to [_right] 
	void printSlice(T* _arr, int _left, int _right);

public:

	// constructor with empty array of _size * elements
	PersistentArray(int _size);

	// constructor with _array of _size * elements
	PersistentArray(T* _arr, int _size);

	// destructor
	~PersistentArray();

	// set element to base version
	void setElementToBase(int _index, T _value);

	// change element by index in a specific version with new value  
	void changeVersion(int _number_of_version, int _change_index, T _new_value);

	// add new version by changing one value in one of previous version
	void addVersion(int _root_position, int _change_index, T _new_value);

	// print all versions as a table
	void printAllVersions();

	// get size of a specific version
	int versionSize(int _number_of_version);

	// get a specific version as array
	T* getArray(int _number_of_version);

	// delete element in a specific version
	void deleteElement(int _root_position, int _delete_index);

	// insert a new value in a specific version
	void insertElement(int _root_position, int _insert_index, T _new_value);

	// get a root of specific version
	Node<T>* getVersion(int _number_of_version);

	// get number of versions
	int sizeVersions();
};


template<typename T>
inline void PersistentArray<T>::buildTree(Node<T>* _node, T* _array, int _left_border, int _right_border)
{
	//std::cout << "\nin build with: l = " << _left_border << " r = " << _right_border << "\n";
	//printSlice(_left_border, r);

	if (_left_border == _right_border) // leaf node
	{
		_node->value = _array[_left_border - 1];
		//std::cout << "in if\t" << _node->val << "\n";
	}
	else // intermediate node
	{
		int middle = (_left_border + _right_border) / 2; //std::cout << "m = " << middle << "\n";
		//std::cout << "\nmaking left child";
		_node->left_child = new Node<T>();
		buildTree(_node->left_child, _array, _left_border, middle);
		//std::cout << "\nmaking right child";
		_node->right_child = new  Node<T>();
		buildTree(_node->right_child, _array, middle + 1, _right_border);
	}
}

template<typename T>
inline void PersistentArray<T>::add(Node<T>* _to, Node<T>* _from, int _left_border, int _right_border, int _position, T _new_value)
{
	//std::cout << "to->val = " << _to->val << "\t";// << "l: " << _to->lchild->val << "\tr: " << _to->rchild->val << "\t";
	//std::cout << "from->val = " << _from->val << "\t";
	//std::cout << "l = " << _left_border << "\tr = " << _right_border << "\t";
	//std::cout << "pos = " << _position << "\tnv = " << _new_value << "\n";

	if (_left_border == _right_border)
	{
		//std::cout << "in if:\t";
		_to->value = _new_value;
		//std::cout << to->val << "\n";
	}
	else
	{
		int middle = (_left_border + _right_border) / 2; //std::cout << "m = " << m << "\n";

		if (_position <= middle)
		{
			//std::cout << "npos(" << npos << ") <= m(" << m << ") : left manipulations\n";

			_to->right_child = _from->right_child;
			Node<T>* left = new Node<T>();
			add(left, _from->left_child, _left_border, middle, _position, _new_value);
			_to->left_child = left;
		}
		else
		{
			//std::cout << "npos(" << npos << ") > m(" << m << ") : right manipulations\n";

			_to->left_child = _from->left_child;
			Node<T>* right = new Node<T>();
			add(right, _from->right_child, middle + 1, _right_border, _position, _new_value);
			_to->right_child = right;
		}
	}
}

template<typename T>
inline T PersistentArray<T>::get(Node<T>* _node, int _left_border, int _right_border, int _position)
{
	if (_left_border == _right_border)
	{
		//std::cout << "l(" << _left_border << ") <= r(" << _right_border << ")\n"; 
		//if (node->lchild != nullptr) std::cout << "node->lchild->value = " << node->lchild->value << "\t";
		//else std::cout << "node->lchild = nullptr\t";
		//if (node->rchild != nullptr) std::cout << "node->rchild->value = " << node->rchild->value << "\n";
		//else std::cout << "node->rchild = nullptr\n";
		return _node->value;
	}

	else
	{
		int middle = (_left_border + _right_border) / 2;
		if (_position <= middle)
		{
			//std::cout << "pos(" << _position << ") <= m(" << middle << ")\n"; 
			//std::cout << "node->lchild->value = " << node->lchild->value << "\t";
			//std::cout << "node->rchild->value = " << node->rchild->value << "\n";
			return get(_node->left_child, _left_border, middle, _position);
		}
		else
		{
			//std::cout << "pos(" << _position << ") > m(" << middle << ")\n";
			//std::cout << "node->rchild->value = " << node->rchild->value << "\t";
			//std::cout << "node->lchild->value = " << node->lchild->value << "\n";
			return get(_node->right_child, middle + 1, _right_border, _position);
		}
	}
}

template<typename T>
inline int PersistentArray<T>::countLeaves(Node<T>* _node)
{
	if (_node == nullptr)
	{
		return 0;
	}

	// the node is a leaf
	if (_node->left_child == nullptr && _node->right_child == nullptr)
	{
		return 1;
	}

	int left_count = countLeaves(_node->left_child);
	int right_count = countLeaves(_node->right_child);

	return left_count + right_count;
}

template<typename T>
inline void PersistentArray<T>::printSlice(T* _arr, int _left, int _right)
{
	//std::cout << "in printArr with: size = " << _right - _left + 1 << "\n";
	if (_arr == nullptr)
	{
		std::cout << "nullptr\n";
		return;
	}

	std::cout << "arr:\t";
	for (int i = _left - 1; i < _right; i++)
	{
		std::cout << _arr[i] << "\t";
	}
	std::cout << "\n";
}

template<typename T>
inline PersistentArray<T>::PersistentArray(int _size)
{
	// Create the base version
	this->base = new T[_size];
	// Set size of base version
	this->size = _size;

	// Add new root to versions
	versions.push_back(new Node<T>());

	// From fisrt element to the last (=_size)
	int left_border = 1;
	int right_border = _size;
	T* arr = base;

	// Build tree with arr
	buildTree(versions.at(0), arr, left_border, right_border);

	std::pair<int, int> temp = { -1, versions.size() - 1 };
	parent_children_relation.push_back(temp);
}

template<typename T>
inline PersistentArray<T>::PersistentArray(T* _arr, int _size)
{
	if (_arr == nullptr)
	{
		throw std::invalid_argument("Empty array");
	}

	// Create the base version
	this->base = new T[_size];
	// Set size of base version
	this->size = _size;

	// Fill base with elements of _arr
	for (int i = 0; i < _size; i++)
	{
		this->base[i] = _arr[i];
	}

	// Add new root to versions
	versions.push_back(new Node<T>());

	// From fisrt element to the last (=_size)
	int left_border = 1;
	int right_border = _size;
	T* arr = base;

	// Build tree with arr
	buildTree(versions.at(0), arr, left_border, right_border);

	std::pair<int, int> temp = { -1, versions.size() - 1 };
	parent_children_relation.push_back(temp);
}

template<typename T>
inline PersistentArray<T>::~PersistentArray()
{
	for (auto nodePtr : versions)
	{
		delete nodePtr;
	}

	delete[] base;
}

template<typename T>
inline void PersistentArray<T>::setElementToBase(int _index, T _value)
{
	if (_index >= 0 && _index < size)
	{
		base[_index] = _value;
		changeVersion(0, _index, _value);
	}
	else
	{
		throw std::out_of_range("Index out of borders");
	}
}

template<typename T>
inline void PersistentArray<T>::changeVersion(int _number_of_version, int _change_index, T _new_value)
{
	bool child_exists = false;
	for (const auto& pair : parent_children_relation)
	{
		if (pair.first == _number_of_version)
		{
			child_exists = true;
			std::cout << "Impossible to change a version which has children. ";
			std::cout << "Version [" << pair.first << "] has at least one child [" << pair.second << "]\n";
			return;
		}
	}

	_number_of_version += 1;
	_change_index += 1;

	if (_number_of_version > versions.size())
	{
		return;
	}

	int left_border = 1;
	int right_border = versionSize(_number_of_version);

	if (_change_index > right_border)
	{
		throw std::out_of_range("Index out of borders");
	}

	add(versions[_number_of_version - 1], versions.at(_number_of_version - 1), left_border, right_border, _change_index, _new_value);

}

template<typename T>
inline void PersistentArray<T>::addVersion(int _root_position, int _change_index, T _new_value)
{
	_root_position += 1;
	_change_index += 1;

	if (_root_position > versions.size())
	{
		return;
	}

	int left_border = 1;
	int right_border = versionSize(_root_position);

	if (_change_index > right_border)
	{
		throw std::out_of_range("Index out of borders");
	}

	versions.push_back(new Node<T>());
	add(versions.back(), versions.at(_root_position - 1), left_border, right_border, _change_index, _new_value);

	std::pair<int, int> temp = { _root_position - 1, versions.size() - 1 };
	parent_children_relation.push_back(temp);
}

template<typename T>
inline void PersistentArray<T>::printAllVersions()
{
	for (size_t i = 0; i < versions.size(); i++)
	{
		auto version_size = versionSize(i + 1);
		std::cout << "Version [" << i << "]: \t";
		std::cout << "Parent ID: [" << parent_children_relation[i].first << "]\t";
		std::cout << "{";
		for (int j = 1; j < version_size + 1; j++)
		{
			//std::cout << "'" << keys.at(j - 1) << "' : '";
			std::cout << "'";
			//std::cout << "n = " << number_of_elements << " i = " << i << " j = " << j << " ";
			std::cout << get(versions.at(i), 1, version_size, j);
			if (j < version_size)
			{
				std::cout << "', ";
			}
			else
			{
				std::cout << "'";
			}
		}
		//std::cout << "\tParent ID: " << parent_children_relation[i].first << " Children ID: " << parent_children_relation[i].second;
		//std::cout << "VS: " << versions.size() << " KVS: " << key_versions.size() << "\t";
		std::cout << "}\n";
	}
}

template<typename T>
inline int PersistentArray<T>::versionSize(int _number_of_version)
{
	if (_number_of_version <= 0 || _number_of_version > versions.size())
	{
		return -1;
	}

	return countLeaves(versions[_number_of_version - 1]);
}

template<typename T>
inline T* PersistentArray<T>::getArray(int _number_of_version)
{
	if (_number_of_version > versions.size())
	{
		return nullptr;
	}

	Node<T>* root = versions[_number_of_version - 1];
	auto version_size = versionSize(_number_of_version);
	T* result = new T[version_size];

	for (int i = 1; i <= version_size; i++)
	{
		result[i - 1] = get(root, 1, version_size, i);
	}

	return result;
}

template<typename T>
inline void PersistentArray<T>::deleteElement(int _root_position, int _delete_index)
{
	_root_position += 1;
	_delete_index += 1;

	T* source_array = getArray(_root_position);
	auto source_size = versionSize(_root_position);

	if (_delete_index < 1 || _delete_index > source_size)
	{
		std::cerr << "Index out of borders\n";
		delete[] source_array;
		return;
	}

	//std::cout << "Size = " << source_size << "; ";
	//std::cout << "arr[excludeIndex] = " << source_array[_exclude_index - 1] << ": \t";

	/*for (size_t j = 0; j < source_size; j++)
	{
		std::cout << source_array[j] << "\t";
	}
	std::cout << "\n";*/

	int new_size = source_size - 1;

	T* modified_array = new T[source_size];
	//std::vector<T> modified_vector{};

	// Copy elements from source_size to modified_array
	for (int i = 0; i < source_size; i++)
	{
		if (i != _delete_index - 1)
		{
			modified_array[i] = source_array[i];
			//modified_vector.push_back(source_array[i]);
		}
	}

	//T* modified_array = new T[modified_vector.size()];
	/*for (int i = 0; i < modified_vector.size(); ++i)
	{
		modified_array[i] = modified_vector[i];
	}*/

	/*std::cout << "Size = " << new_size << "; ";
	for (size_t j = 0; j < new_size; j++)
	{
		std::cout << modified_array[j] << "\t";
	}

	std::cout << "\n";*/

	// Create a new version by building a tree
	versions.push_back(new Node<T>());
	buildTree(versions.back(), modified_array, 1 + 1, new_size + 1);

	delete[] source_array;
	delete[] modified_array;

	std::pair<int, int> temp = { _root_position - 1, versions.size() - 1 };
	parent_children_relation.push_back(temp);
}

template<typename T>
inline void PersistentArray<T>::insertElement(int _root_position, int _insert_index, T _new_value)
{
	_root_position += 1;
	_insert_index += 1;

	T* source_array = getArray(_root_position);
	auto source_size = versionSize(_root_position);

	if (_insert_index < 1 || _insert_index > source_size + 1)
	{
		std::cerr << "Index out of borders\n";
		delete[] source_array;
		return;
	}

	/*std::cout << "Size = " << source_size << "; ";
	for (size_t j = 0; j < source_size; j++)
	{
		std::cout << source_array[j] << "\t";
	}

	std::cout << "\n";*/

	int new_size = source_size + 1;

	T* modified_array = new T[new_size];

	for (int i = 0, j = 0; j < new_size; j++)
	{
		if (j == _insert_index - 1)
		{
			modified_array[j] = _new_value;
		}
		else
		{
			modified_array[j] = source_array[i++];
		}
	}

	/*std::cout << "Size = " << new_size << "; ";
	for (size_t j = 0; j < new_size; j++)
	{
		std::cout << modified_array[j] << "\t";
	}

	std::cout << "\n";*/

	versions.push_back(new Node<T>());
	buildTree(versions.back(), modified_array, 1, new_size);

	delete[] source_array;
	delete[] modified_array;

	std::pair<int, int> temp = { _root_position - 1, versions.size() - 1 };
	parent_children_relation.push_back(temp);
}

template<typename T>
inline Node<T>* PersistentArray<T>::getVersion(int _number_of_version)
{
	_number_of_version += 1;

	if (_number_of_version <= 0 || _number_of_version > versions.size())
	{
		std::cerr << "There is no version [" << _number_of_version - 1 << "]\n";
		return nullptr;
	}

	return versions[_number_of_version - 1];
}

template<typename T>
inline int PersistentArray<T>::sizeVersions()
{
	return versions.size();
}