Помоги мне, пожалуйста, проверить все реализованные на данный момент методы моего класса…
- User
Помоги мне, пожалуйста, проверить все реализованные на данный момент методы моего класса Этот класс работает с персистентными массивами, он использует подход path-copying, который в отличие от fat-node позволяет не хранить в памяти все версии одновременно template struct Node { Node* left_child{ nullptr }; Node* right_child{ nullptr }; T value{};
Node(T val) : value(val), left_child(nullptr), right_child(nullptr) {}};
template class PersistentArray { private:
// base version T* base{ nullptr }; // size of base version int size{ 0 }; // 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* arr, int left_border, int right_border) { if (node == nullptr) { throw std::runtime_error("Node pointer is null."); } if (arr == nullptr) { // TODO } // Out-of-border check if (left_border < 0 || right_border < left_border || right_border > size) { throw std::out_of_range("Invalid left or right index for building the tree."); } if (left_border == right_border) // leaf node { node->value = arr[left_border - 1]; // Move value to node std::cout << "in if\t" << node->val << "\n"; } else // Intermediate node { int middle = (left_border + right_border) / 2; std::cout << "m = " << middle << "\n"; // Recursively creating left child std::cout << "\nmaking left child"; node->left_child = new Node<T>(); buildTree(node->left_child, arr, left_border, middle); // Recursively creating right child std::cout << "\nmaking right child"; node->right_child = new Node<T>(); buildTree(node->right_child, arr, middle + 1, 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) { 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) { // Create a new node with a new value 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 = " << middle << "\n"; if (position <= middle) { // Create a new node for left child std::cout << "npos(" << position << ") <= m(" << middle << ") : left manipulations\n"; to->right_child = from->right_child; // right child stay the same to->left_child = new Node<T>(); // new node for left child add(to->left_child, from->left_child, left_border, middle, position, new_value); } else { // Create a new node for right child std::cout << "npos(" << position << ") > m(" << middle << ") : right manipulations\n"; to->left_child = from->left_child; // left child stay the same to->right_child = new Node<T>(); // new node for right child add(to->right_child, from->right_child, middle + 1, right_border, position, new_value); } } } // recursive function to get element of specific node T get(Node<T>* node, int left_border, int right_border, int position) { if (node == nullptr) { throw std::runtime_error("Node pointer is null."); } if (position < left_border || position > right_border) { throw std::out_of_range("Position is out of bounds."); } 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; std::cout << "m = " << middle << "\n"; 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); } } } // 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) { // base version this->size = size; this->base = new T[size]; std::fill_n(this->base, size, T()); // deafult initialisation // new root versions.push_back(new Node<T>()); // borders for tree int left_border = 0; int right_border = size - 1; T* arr = base; // build a tree buildTree(versions.at(0), arr, left_border, right_border); std::pair<int, int> temp = { -1, versions.size() - 1 }; parent_children_relation.push_back(temp); } // constructor with _array of _size * elements PersistentArray(T* arr, int size) { if (arr == nullptr) { throw std::invalid_argument("Empty array."); } // base version this->size = size; this->base = new T[size]; // copy from _arr to base std::copy(arr, arr + size, this->base); // new root versions.push_back(new Node<T>()); // borders for tree int left_border = 0; int right_border = size - 1; T* arr = base; // build a tree buildTree(versions.at(0), arr, left_border, right_border); std::pair<int, int> temp = { -1, versions.size() - 1 }; parent_children_relation.push_back(temp); } // destructor ~PersistentArray() { // free memory from all nodes for (auto nodePtr : versions) { delete nodePtr; } // free base array delete[] base; } // set element to base version void setElementToBase(int index, T value) { if (index >= 0 && index < this->size) { base[index] = value; // Изменяем базовое значение // Создаем новую версию с изменением changeVersion(0, index, value); } else { throw std::out_of_range("Index out of bounds: valid range is from 0 to " + std::to_string(size - 1)); } } // 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 number_of_version, int change_index, T new_value) { // previous versions for (const auto& pair : parent_children_relation) { if (pair.first == number_of_version) { std::cerr << "Impossible to change a version which has children. "; std::cerr << "Version [" << pair.first << "] has at least one child [" << pair.second << "]\n"; return; } } number_of_version += 1; // Увеличиваем номер версии // Проверка на корректность номера версии if (number_of_version >= versions.size()) // Изменено для проверки { std::cerr << "Version number out of bounds.\n"; return; } int left_border = 0; // Изменено на 0 для соответствия 0-индексации int right_border = versionSize(number_of_version); // Проверка на корректность индекса для изменений if (change_index < left_border || change_index >= right_border) { throw std::out_of_range("Change index out of bounds."); } // Добавление новой версии add(versions[number_of_version - 1], versions.at(number_of_version - 1), left_border, right_border, change_index, new_value); } // print all versions as a table void printAllVersions() { for (size_t i = 0; i < versions.size(); i++) { auto version_size = versionSize(i); if (i >= parent_children_relation.size()) { std::cerr << "Error: Parent-Children relation index out of bounds for version [" << i << "]\n"; continue; } std::cout << "Version [" << i << "]: \t"; std::cout << "Parent ID: [" << parent_children_relation[i].first << "]\t"; std::cout << "{"; for (int j = 0; j < version_size; j++) { std::cout << "'"; std::cout << get(versions.at(i), 0, version_size - 1, j); std::cout << "'"; if (j < version_size - 1) { std::cout << ", "; } } std::cout << "}\n"; } } // 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();};
- Assistant
Давайте проверим и улучшим ваш класс
PersistentArray, который реализует персистентный массив с использованием подхода path-copying. Я выделю несколько моментов, где может потребоваться доработка, а также предложу улучшения.Общие замечания:
-
Ошибки в коде: В функции
buildTree, когда вы назначаете значение в листовой узел, вместоnode->val, вам нужно использоватьnode->value. Вы многократно используетеval, но правильно объявленоvalue. -
Проверка входных данных: Убедитесь, что везде, где вы принимаете массивы или указатели, вы проверяете их на
nullptr, чтобы избежать проблем сегментации. -
Отсутствующие реализации: У вас есть некоторые методы, которые упоминаются, но не реализованы, такие как
changeVersion,deleteElement,insertElement,versionSize, иgetArray. Без этих методов класс будет неполным. -
Удаление узлов: Метод деструктора удаляет только корневые узлы. Следует реализовать рекурсивное удаление всех узлов дерева, чтобы избежать утечек памяти.
Рекомендации по улучшению:
-
Используйте умные указатели: Вместо обычных указателей
Node<T>*, рассмотрите возможность использованияstd::unique_ptr<Node<T>>, чтобы избежать утечек памяти и упрощения управления временем жизни объектов. -
Оптимизация: Избегайте большой глубины рекурсии в
add,get, иbuildTree. Это может привести к переполнению стека для больших массивов. Возможно, стоит рассмотреть итеративный подход. -
Функции для работы с массивами версий: Добавьте больше ясности для работы с версиями. Определите, как будете обрабатывать индексы версий, и упростите операции.
-
Документация и примеры: Добавьте комментарии и примеры использования вашего класса, чтобы облегчить понимание.
-
Ошибка памяти в случае исключений: Убедитесь, что при возникновении исключений в вашем коде память очищается корректно. Рассмотрите возможность использования RAII для управления ресурсами.
Код для улучшения
Вот несколько улучшений в вашем коде, чтобы устранить некоторые проблемы и улучшить читаемость:
// Упрощенный вариант деструктора с учетом рекурсивного удаления ~PersistentArray() { for (auto nodePtr : versions) { deleteTree(nodePtr); } delete[] base; } void deleteTree(Node<T>* node) { if (node) { deleteTree(node->left_child); deleteTree(node->right_child); delete node; } } // В функции изменения версии следует добавить корректный механизм // для переподмены версий. Обработайте это с явным указанием текущей версии. void changeVersion(int number_of_version, int change_index, T new_value) { // Ваша логика для изменения версии }Это всего лишь некоторые общие рекомендации. Ваш класс хороший старт, и вы можете продолжать его развивать и расширять. Если требуются более специфические доработки или функции, дайте знать!
-
- User
Напиши, пожалуйста в функции main простое тестирование моего кода
- Assistant
Конечно! Давайте напишем простое тестирование в функции
main, чтобы проверить основные функции вашего классаPersistentArray. Мы протестируем создание массива, добавление версий и получение значений.Вот примерный код для функции
main:#include <iostream> #include <vector> #include <stdexcept> #include <algorithm> template <typename T> struct Node { Node<T>* left_child{ nullptr }; Node<T>* right_child{ nullptr }; T value{}; Node(T val) : value(val), left_child(nullptr), right_child(nullptr) {} }; template <typename T> class PersistentArray { // Ваш код класса PersistentArray здесь... }; // Функция main для тестирования int main() { try { // Создаем массив с 5 элементами int initial_size = 5; PersistentArray<int> persistentArray(initial_size); // Устанавливаем начальные значения for (int i = 0; i < initial_size; ++i) { persistentArray.setElementToBase(i, i + 1); // Устанавливаем значения 1, 2, 3, 4, 5 } // Выводим все версии std::cout << "All versions after initializing:\n"; persistentArray.printAllVersions(); // Создаем новую версию, изменяя элемент с индексом 2 на 10 persistentArray.addVersion(0, 2, 10); // Изменяем версию 0, элемент по индексу 2 std::cout << "All versions after adding a new version by changing index 2 to 10:\n"; persistentArray.printAllVersions(); // Создаем еще одну версию, изменяя элемент с индексом 1 на 20 persistentArray.addVersion(1, 1, 20); // Изменяем версию 1 std::cout << "All versions after adding a new version by changing index 1 to 20:\n"; persistentArray.printAllVersions(); // Получаем значение из версии 2 по индексу 1 int value_from_version_2 = persistentArray.get(persistentArray.getVersion(2), 0, persistentArray.versionSize(2) - 1, 1); std::cout << "Value from version 2 at index 1: " << value_from_version_2 << std::endl; // Проверяем, не изменилось ли значение в базовой версии int base_value = persistentArray.get(persistentArray.getVersion(0), 0, persistentArray.versionSize(0) - 1, 1); std::cout << "Value from base version at index 1: " << base_value << std::endl; } catch (const std::exception& e) { std::cerr << "An error occurred: " << e.what() << std::endl; } return 0; }Объяснение кода:
- Создание массива: Мы создаем персистентный массив
PersistentArrayс размером 5. - Инициализация: Устанавливаем базовые значения (от 1 до 5) в базовую версию.
- Ввод и вывод: Выводим все версии массива после инициализации.
- Добавление версий: Создаем новые версии, изменяя элементы в исходных версиях.
- Получение значений: Получаем значения из определенной версии, чтобы проверить правильность работы.
- Обработка ошибок: Используем
try-catchблок для обработки любых исключений.
Этот пример покрывает основные функции вашего класса. Вы можете адаптировать и расширять тесты по мере появления новых функций в вашем классе!
- Создание массива: Мы создаем персистентный массив