Skip to content
TheChatArchiveThe Chat Archive
gpt-4o-mini-2024-07-18· OpenAIAi2 WildChat-4.8M (AI2)

сделай короткое текстовое описание этого класса: #ifndef PERSISTENTDOUBLYLINKEDLISTH…

  1. 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

  2. Assistant

    Класс PersistentDoublyLinkedList реализует структуру данных — устойчивый двусвязный список. Он позволяет хранить несколько версий списка, что позволяет поворачивать изменения, подобно операциям "отмены" (undo) и "повтора" (redo). Основные функции класса включают:

    • Конструктор для инициализации списка из массива или вектора.
    • Методы для добавления новых элементов в начало и конец списка.
    • Методы для отмены и повтора последних действий.
    • Возможность получения значений элементов определённой версии списка.

    Каждый элемент списка представлен узлом (DL_node), который хранит значение, а также указатели на предыдущий и следующий узлы. Упрощая работу с историей версий, класс предоставляет удобные интерфейсы для отслеживания изменений.

  3. 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

  4. Assistant

    Класс PersistentAssociativeArray реализует устойчивый ассоциативный массив на основе бинарного дерева поиска. Это структура данных позволяет хранить ключи и связанные с ними значения, сохраняя несколько версий данных, что позволяет выполнять операции "отмены" (undo) и "повтора" (redo). Основные функции класса включают:

    • Конструкторы для инициализации массива из векторов ключей и значений, проверяя их совместимость.
    • Метод для добавления новой версии с изменением значения по определённому ключу, при этом сохраняется предыдущая версия дерева.
    • Методы для выполнения операций отмены и повтора.
    • Метод для получения значений из определённой версии дерева.

    Каждый узел дерева (AA_node) содержит ключ, значение и указатели на левые и правые дочерние узлы. Класс также предоставляет возможность извлечения значений и печати всех доступных версий ассоциативного массива, что делает его удобным для работы с историей изменений данных.

  5. 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

  6. Assistant

    Класс Convert обеспечивает функции преобразования между различными структурами данных, такими как устойчивые массивы, двусвязные списки и ассоциативные массивы. Он предоставляет статические методы для конвертации данных с учетом их версий. Основные функции класса включают:

    1. Преобразование из PersistentArray в PersistentDoublyLinkedList: Метод convertArrayToList извлекает базовую версию массива и создает двусвязный список.

    2. Преобразование из PersistentDoublyLinkedList в PersistentArray: Метод convertListToArray получает базовую версию списка и создает массив.

    3. Преобразование из PersistentArray в PersistentAssociativeArray: Метод convertArrayToAssociativeArray создает ассоциативный массив, используя входные ключи и значения из массива, при этом проверяя соответствие количества ключей и элементов.

    4. Преобразование из PersistentDoublyLinkedList в PersistentAssociativeArray: Метод convertListToAssociativeArray выполняет аналогичную операцию для двусвязного списка.

    5. Преобразование из PersistentAssociativeArray в PersistentDoublyLinkedList: Метод convertAssociativeArrayToList извлекает значения из ассоциативного массива для создания списка.

    6. Преобразование из PersistentAssociativeArray в PersistentArray: Метод convertAssociativeArrayToArray создает массив на основе значений из ассоциативного массива.

    Класс Convert предоставляет гибкий и мощный способ взаимодействия между разными структурами данных, упрощая работу с историей изменений и обеспечивая согласованность версий.