сделай короткое текстовое описание этого класса: #ifndef PERSISTENTDOUBLYLINKEDLISTH…
- User
сделай короткое текстовое описание этого класса: #ifndef PERSISTENT_DOUBLY_LINKED_LIST_H #define PERSISTENT_DOUBLY_LINKED_LIST_H
#include #include #include #include <unordered_map>
template struct DL_node { T value; std::shared_ptr<DL_node> prev; std::shared_ptr<DL_node> next;
DL_node(T data) : value(data), prev(nullptr), next(nullptr) {}};
template class PersistentDoublyLinkedList { private: std::vector<std::shared_ptr<DL_node>> versions; // Store head versions of the list //std::unordered_map<T, std::shared_ptr<DL_node>> node_map; // For storing already created nodes
int current_version;public: // Constructor that accepts an array and its size PersistentDoublyLinkedList(T* arr, int size) { if (size <= 0) { return; // If the array is empty, just return }
// Create the head of the list auto head = std::make_shared<DL_node<T>>(arr[0]); std::shared_ptr<DL_node<T>> current = head; // Store pointer to the current node // Iterate through the array and create the doubly linked list for (int i = 1; i < size; ++i) { auto new_node = std::make_shared<DL_node<T>>(arr[i]); current->next = new_node; // Attach the new node to the current new_node->prev = current; // Set the previous node reference current = new_node; // Move to the new node } // Store the head of the list in the versions vector versions.push_back(head); current_version = 0; } PersistentDoublyLinkedList(const std::vector<T>& vec, int vec_size) { int size = vec_size; if (size <= 0) { return; // If the vector is empty, just return } // Create the head of the list auto head = std::make_shared<DL_node<T>>(vec[0]); std::shared_ptr<DL_node<T>> current = head; // Store pointer to the current node // Iterate through the vector and create the doubly linked list for (int i = 1; i < size; ++i) { auto new_node = std::make_shared<DL_node<T>>(vec[i]); current->next = new_node; // Attach the new node to the current new_node->prev = current; // Set the previous node reference current = new_node; // Move to the new node } // Store the head of the list in the versions vector versions.push_back(head); current_version = 0; } // Method to add a new node to the front of the list void push_front(T value) { auto new_head = std::make_shared<DL_node<T>>(value); new_head->next = versions.back(); // The new node points to the current head // Update the previous head's pointer if it exists if (versions.back() != nullptr) { versions.back()->prev = new_head; } // Store the new version (head) of the list versions.push_back(new_head); current_version++; } // Method to print all versions of the list without using PrintList void printAllVersions() { for (int i = 0; i < versions.size(); ++i) { std::cout << "Version " << i << ": "; auto current = versions[i]; // Traverse through all nodes of the current version and print their values while (current) { std::cout << current->value << " (" << &(current->value) << ") "; current = current->next; } std::cout << std::endl; // Move to a new line after printing one version } } // Method to make UNDO action void undo() { if (current_version <= 0) { std::cout << "No actions to undo!" << std::endl; return; } current_version--; versions.push_back(versions[current_version]); } // Method to make REDO action void redo() { if (current_version >= versions.size() - 1) { std::cout << "No actions to redo!" << std::endl; return; } current_version++; // Move to the next version versions.push_back(versions[current_version]); } // Method to add a new node to the end of the list void push_back(T value) { auto new_node = std::make_shared<DL_node<T>>(value); // If this is the first version of the list, the new node will be the head if (versions.empty()) { versions.push_back(new_node); current_version = 0; return; } auto last = versions.back(); // Get the current version (head) // Find the last node (tail) in the current version while (last->next) { last = last->next; } last->next = new_node; // Attach the new node to the tail new_node->prev = last; // Set the previous node reference // Store the new version (head) of the list versions.push_back(versions.back()); current_version++; } std::vector<T> getVersion(size_t idx) const { if (idx < versions.size()) { std::vector<T> result; auto current = versions[idx]; // Traverse through all nodes of the current version and add their values to the vector while (current){ result.push_back(current->value); current = current->next; } return result; // Return the vector of values } throw std::out_of_range("Invalid version index"); } };
#endif // PERSISTENT_DOUBLY_LINKED_LIST_H
- Assistant
Класс
PersistentDoublyLinkedListреализует структуру данных — устойчивый двусвязный список. Он позволяет хранить несколько версий списка, что позволяет поворачивать изменения, подобно операциям "отмены" (undo) и "повтора" (redo). Основные функции класса включают:- Конструктор для инициализации списка из массива или вектора.
- Методы для добавления новых элементов в начало и конец списка.
- Методы для отмены и повтора последних действий.
- Возможность получения значений элементов определённой версии списка.
Каждый элемент списка представлен узлом (
DL_node), который хранит значение, а также указатели на предыдущий и следующий узлы. Упрощая работу с историей версий, класс предоставляет удобные интерфейсы для отслеживания изменений. - User
А этот класс: #ifndef PERSISTENT_ASSOCIATIVE_ARRAY_H #define PERSISTENT_ASSOCIATIVE_ARRAY_H
#include #include #include #include
template <typename KeyType, typename ValueType> struct AA_node { KeyType key{}; ValueType value{}; std::shared_ptr<AA_node<KeyType, ValueType>> left{}; std::shared_ptr<AA_node<KeyType, ValueType>> right{};
AA_node(KeyType k, ValueType v) : key(k), value(v), left(nullptr), right(nullptr) {}};
template <typename KeyType, typename ValueType> class PersistentAssociativeArray { private: std::vector<std::shared_ptr<AA_node<KeyType, ValueType>>> versions{};
std::shared_ptr<AA_node<KeyType, ValueType>> insert(std::shared_ptr<AA_node<KeyType, ValueType>> root, KeyType key, ValueType value) { if (!root) { return std::make_shared<AA_node<KeyType, ValueType>>(key, value); } if (key < root->key) { root->left = insert(root->left, key, value); } else if (key > root->key) { root->right = insert(root->right, key, value); } else { root->value = value; // Update value when the key matches } return root; // Return the root for usage } // Recursive function to copy the tree std::shared_ptr<AA_node<KeyType, ValueType>> copyTree(std::shared_ptr<AA_node<KeyType, ValueType>> root) { if (!root) { return nullptr; } auto newNode = std::make_shared<AA_node<KeyType, ValueType>>(root->key, root->value); newNode->left = copyTree(root->left); newNode->right = copyTree(root->right); return newNode; } int current_version{}; std::vector<KeyType> keys;public: PersistentAssociativeArray(const std::vector& keys, ValueType* values_array, size_t values_array_size) { if (keys.size() != values_array_size || keys.empty()) { throw std::invalid_argument("Keys and values must have the same non-zero length."); }
std::shared_ptr<AA_node<KeyType, ValueType>> root = nullptr; // Issue occurred here for (size_t i = 0; i < keys.size(); ++i) { root = insert(root, keys[i], values_array[i]); } versions.push_back(root); current_version = 0; this->keys = keys; } PersistentAssociativeArray(const std::vector<KeyType>& keys, const std::vector<ValueType>& values, size_t values_array_size) { if (keys.size() != values.size() || keys.empty()) { throw std::invalid_argument("Keys and values must have the same non-zero length."); } std::shared_ptr<AA_node<KeyType, ValueType>> root = nullptr; for (size_t i = 0; i < keys.size(); ++i) { root = insert(root, keys[i], values[i]); } versions.push_back(root); current_version = 0; this->keys = keys; } // Function to add a new version with a value change void addVersion(int root_position, KeyType change_key, ValueType new_value) { if (current_version < 0 || current_version >= versions.size() || root_position < 0 || root_position >= versions.size()) { throw std::out_of_range("Invalid root position"); } // Copy the tree from the specified version auto new_root = copyTree(versions[root_position]); // Insert the new value into the copied tree insert(new_root, change_key, new_value); // Add the new version to the vector versions.push_back(new_root); current_version++; } // Test function for output void print() { for (const auto& version : versions) { // Print information for each node std::cout << "Version root key: " << version->key << ", value: " << version->value << std::endl; } } // Method to make UNDO action void undo() { if (current_version <= 0) { std::cout << "No actions to undo!" << std::endl; return; } current_version--; versions.push_back(versions[current_version]); } // Method to make REDO action void redo() { if (current_version >= versions.size() - 1) { std::cout << "No actions to redo!" << std::endl; return; } current_version++; // Move to the next version versions.push_back(versions[current_version]); } // Function to print all versions void printAllVersions() { for (size_t i = 0; i < versions.size(); ++i) { std::cout << "Version [" << i << "]\t"; std::cout << "{"; for (size_t j = 0; j < keys.size(); ++j) { std::cout << "'" << keys[j] << "': " << findValueInNode(versions[i], keys[j]); if (j < keys.size() - 1) { std::cout << ", "; } } std::cout << "}" << std::endl; } } ValueType findValueInNode(std::shared_ptr<AA_node<KeyType, ValueType>> root, const KeyType& key) { if (!root) { throw std::runtime_error("Key not found"); // or return a default value } if (key < root->key) { return findValueInNode(root->left, key); } else if (key > root->key) { return findValueInNode(root->right, key); } else { return root->value; // Found the node with the corresponding key } } std::vector<ValueType> getVersion(size_t idx) const { if (idx < versions.size()) { std::vector<ValueType> result; collectValues(versions[idx], result); return result; // Return the vector of values } throw std::out_of_range("Invalid version index"); } // Recursive function to collect values from the tree void collectValues(std::shared_ptr<AA_node<KeyType, ValueType>> node, std::vector<ValueType>& result) const { if (!node) { return; } // First traverse the left subtree collectValues(node->left, result); // Then add the current value result.push_back(node->value); // And traverse the right subtree collectValues(node->right, result); }};
#endif // PERSISTENT_ASSOCIATIVE_ARRAY_H
- Assistant
Класс
PersistentAssociativeArrayреализует устойчивый ассоциативный массив на основе бинарного дерева поиска. Это структура данных позволяет хранить ключи и связанные с ними значения, сохраняя несколько версий данных, что позволяет выполнять операции "отмены" (undo) и "повтора" (redo). Основные функции класса включают:- Конструкторы для инициализации массива из векторов ключей и значений, проверяя их совместимость.
- Метод для добавления новой версии с изменением значения по определённому ключу, при этом сохраняется предыдущая версия дерева.
- Методы для выполнения операций отмены и повтора.
- Метод для получения значений из определённой версии дерева.
Каждый узел дерева (
AA_node) содержит ключ, значение и указатели на левые и правые дочерние узлы. Класс также предоставляет возможность извлечения значений и печати всех доступных версий ассоциативного массива, что делает его удобным для работы с историей изменений данных. - User
#ifndef CONVERT_H #define CONVERT_H
#include "persistent_array.h" #include "persistent_doubly_linked_list.h"
template class Convert { public: // Convert from PersistentArray to PersistentDoublyLinkedList static PersistentDoublyLinkedList convertArrayToList(const PersistentArray& array, size_t idx = 0) { // Get the base version of the array auto base_version = array.getVersion(idx); return PersistentDoublyLinkedList(base_version, base_version.size()); }
// Convert from PersistentDoublyLinkedList to PersistentArray static PersistentArray<T> convertListToArray(const PersistentDoublyLinkedList<T>& list, size_t idx = 0) { // Get the base version of the list auto head = list.getVersion(idx); return PersistentArray<T>(head, head.size()); } // Convert from PersistentArray to PersistentAssociativeArray template<typename KeyType> static PersistentAssociativeArray<KeyType, T> convertArrayToAssociativeArray(const PersistentArray<T>& array, const std::vector<KeyType>& keys, size_t idx = 0) { // Get the base version of the array auto base_version = array.getVersion(idx); if (keys.size() != base_version.size()) { throw std::invalid_argument("Number of keys must match the number of elements in the array."); } return PersistentAssociativeArray<KeyType, T>(keys, base_version, base_version.size()); } // Convert from PersistentDoublyLinkedList to PersistentAssociativeArray template<typename KeyType> static PersistentAssociativeArray<KeyType, T> convertListToAssociativeArray(const PersistentDoublyLinkedList<T>& list, const std::vector<KeyType>& keys, size_t idx = 0) { // Get the base version of the list auto values = list.getVersion(idx); if (keys.size() != values.size()) { throw std::invalid_argument("Number of keys must match the number of elements in the list."); } return PersistentAssociativeArray<KeyType, T>(keys, values, values.size()); } // Convert from PersistentAssociativeArray to PersistentDoublyLinkedList template<typename KeyType> static PersistentDoublyLinkedList<T> convertAssociativeArrayToList(const PersistentAssociativeArray<KeyType, T>& associative_array, size_t idx = 0) { std::vector<T> values = associative_array.getVersion(idx); return PersistentDoublyLinkedList<T>(values, values.size()); } // Convert from PersistentAssociativeArray to PersistentArray template<typename KeyType> static PersistentArray<T> convertAssociativeArrayToArray(const PersistentAssociativeArray<KeyType, T>& associative_array, size_t idx = 0) { std::vector<T> values = associative_array.getVersion(idx); return PersistentArray<T>(values, values.size()); }};
#endif // CONVERT_H
- Assistant
Класс
Convertобеспечивает функции преобразования между различными структурами данных, такими как устойчивые массивы, двусвязные списки и ассоциативные массивы. Он предоставляет статические методы для конвертации данных с учетом их версий. Основные функции класса включают:-
Преобразование из
PersistentArrayвPersistentDoublyLinkedList: МетодconvertArrayToListизвлекает базовую версию массива и создает двусвязный список. -
Преобразование из
PersistentDoublyLinkedListвPersistentArray: МетодconvertListToArrayполучает базовую версию списка и создает массив. -
Преобразование из
PersistentArrayвPersistentAssociativeArray: МетодconvertArrayToAssociativeArrayсоздает ассоциативный массив, используя входные ключи и значения из массива, при этом проверяя соответствие количества ключей и элементов. -
Преобразование из
PersistentDoublyLinkedListвPersistentAssociativeArray: МетодconvertListToAssociativeArrayвыполняет аналогичную операцию для двусвязного списка. -
Преобразование из
PersistentAssociativeArrayвPersistentDoublyLinkedList: МетодconvertAssociativeArrayToListизвлекает значения из ассоциативного массива для создания списка. -
Преобразование из
PersistentAssociativeArrayвPersistentArray: МетодconvertAssociativeArrayToArrayсоздает массив на основе значений из ассоциативного массива.
Класс
Convertпредоставляет гибкий и мощный способ взаимодействия между разными структурами данных, упрощая работу с историей изменений и обеспечивая согласованность версий. -