frequency_list.h

#ifndef FREQUENCY_LIST_H
#define FREQUENCY_LIST_H
 
#ifdef LINKED_LIST_VISUALIZATION_H
#include "../../visualization/list_visual/linked_list_visualization.h"
#endif
 
#ifdef __cplusplus
#include <cstdint>
#include <vector>
#include <memory>
#include <string>
#include <iostream>
#endif
 
 
template<typename T>
class frequency_list {
    public:
    explicit frequency_list(std::vector<T> data = {}) noexcept
    : head(nullptr), tail(nullptr) {
        if(!data.empty()) {
            for (const auto &item: data) {
                this->push_back(item);
            }
        }
    }
 
    frequency_list(const frequency_list<T> &list) : head(nullptr), tail(nullptr), size(0) {
        for (auto iter = list.head; iter != nullptr; iter = iter->next) {
            this->push_back(iter->data);
        }
    }
 
    class Iterator;
 
    void push_back(T data);
 
    void push_front(T data);
 
    bool search(T key);
 
    int64_t get_frequency(T key);
 
 
    void erase(T key);
 
    void reset_frequency();
 
 
    std::vector<std::pair<T, int64_t> > elements();
 
 
    bool empty() { return head == nullptr; }
 
    Iterator begin() { return Iterator(head); }
 
    Iterator end() { return Iterator(nullptr); }
 
    void visualize();
 
    friend std::ostream& operator<<(std::ostream& os, const frequency_list<T>& flist) {
        auto iterator = flist.head;
        while (iterator != nullptr) {
            os << iterator->data << "(" << iterator->freq << ") ";
            iterator = iterator->next;
        }
        return os;
    }
 
    private:
    struct node {
        T data;
        int64_t freq;
        std::shared_ptr<node> next;
        std::weak_ptr<node> prev;
 
        node(T data, int64_t freq, std::weak_ptr<node> prev, std::shared_ptr<node> next)
        : data(data), freq(freq), prev(prev), next(next) {}
 
        void add_freq() { freq++; }
        void reset_freq() { freq = 1; }
    };
 
    std::shared_ptr<node> head;
    node *tail;
    uint64_t size{0};
 
    void update_list_sequence();
 
    void swap_nodes(std::shared_ptr<node> a, std::shared_ptr<node> b);
 
    std::string generate();
};
 
 
 
template<typename T>
void frequency_list<T>::swap_nodes(std::shared_ptr<node> a, std::shared_ptr<node> b) {
    if(a == nullptr || b == nullptr || a->next != b)
    return;
 
    // Attach b's next to a and a's prev to b
    a->next = b->next;
    b->prev = a->prev;
 
    // If b's next exists, attach a to its prev
    if(b->next)
    b->next->prev = a;
 
    // If a's prev exists(i.e., a is not the head), attach b to its next
    if(a->prev.lock())
    a->prev.lock()->next = b;
 
    // Now, attach a to b's next and b to a's prev
    b->next = a;
    a->prev = b;
 
    // If the node a was the head node, update the head to b
    if (head == a)
    head = b;
}
 
template<typename T>
void frequency_list<T>::update_list_sequence() {
    auto current_node = head;
 
    while (current_node != nullptr && current_node->next != nullptr) {
        if (current_node->freq < current_node->next->freq) {
            swap_nodes(current_node, current_node->next);
 
            if(current_node->prev.lock())
            current_node = current_node->prev.lock();
 
        } else
        current_node = current_node->next;
    }
}
 
template<typename T>
void frequency_list<T>::reset_frequency() {
    auto iterator = head;
 
    while (iterator != nullptr) {
        iterator->reset_freq();
        iterator = iterator->next;
    }
}
 
 
template<typename T>
void frequency_list<T>::push_front(T data) {
    auto Iterator = head;
 
    // Iterating over the list to find if the same data is already present
    while (Iterator != nullptr) {
        if (Iterator->data == data) {
            // if data is found, increase frequency and re-sort the list
            Iterator->freq++;
            update_list_sequence();
            return;
        }
        Iterator = Iterator->next;
    }
 
    // if data is not found in the list, add new node at front
    auto new_node = std::make_shared<node>(data, 1, std::weak_ptr<node>(), head);
 
    if (head != nullptr) {
        head->prev = new_node;
    }
 
    head = new_node;
 
    size++;
}
 
template<typename T>
void frequency_list<T>::erase(T key) {
    auto iterator = head;
 
    // special case: deleting the head node
    if (head != nullptr && head->data == key) {
        head = head->next;
        if(head)
        head->prev.reset();
        size--;
        return;
    }
 
    // iterate over the rest nodes
    while (iterator != nullptr) {
        if (iterator->data == key) {
            // connect previous node and next node
            if(auto sharedPrev = iterator->prev.lock()){
                sharedPrev->next = iterator->next;
            }
            if (iterator->next) {
                iterator->next->prev = iterator->prev;
            }
            // deleting the node by falling out of scope
            size--;
            return;
        }
        iterator = iterator->next;
    }
}
 
template<typename T>
int64_t frequency_list<T>::get_frequency(T key) {
    auto iterator = head;
 
    while(iterator != nullptr) {
        if(iterator->data == key) {
            return iterator->freq;
        }
 
        iterator = iterator->next;
    }
 
    return -1;
}
 
template<typename T>
bool frequency_list<T>::search(T key) {
    auto iterator = head;
 
    while (iterator != nullptr) {
        if (iterator->data == key) {
            iterator->add_freq();
            update_list_sequence();
            return true;
        }
 
        iterator = iterator->next;
    }
 
    return false;
}
 
template<typename T>
void frequency_list<T>::push_back(T data) {
    if (this->empty()) {
        head = std::make_shared<node>(data, 1, std::weak_ptr<node>(), nullptr);
        return;
    }
 
    auto iterator = head;
    while (iterator) {
        if (iterator->data == data) {
            iterator->add_freq();
            update_list_sequence();
            return;
        }
        if (!iterator->next)
        break;
        iterator = iterator->next;
    }
 
    auto newNode = std::shared_ptr<node>(new node(data, 1, iterator, nullptr));
    if (iterator) iterator->next = newNode;
    size++;
}
 
 
template<typename T> std::vector<std::pair<T, int64_t> > frequency_list<T>::elements(){
    std::vector<std::pair<T, int64_t> > ans;
    std::shared_ptr<node> root = head;
    while(root){
        ans.push_back(std::make_pair(root -> data, root -> freq));
        root = root -> next;
    }
    return ans;
}
 
 
template <typename T> std::string frequency_list<T>::generate() {
    std::string gen = "";
    gen += "rankdir=LR;";
    gen += '\n';
    gen += "node [shape=record;]";
    gen += '\n';
    std::vector<std::pair<T, int64_t> > els = this->elements();
    if (std::is_same_v<T, std::string> || std::is_same_v<T, char>) {
        for (auto &x : els) {
            gen += x.first;
            gen += " [label=<{ ";
            gen += x.first;
            gen += " | ";
            gen += x.second;
            gen += " | }>] ;";
            gen += '\n';
        }
 
        std::shared_ptr<node> curr = head;
        while (curr->next) {
            gen += curr->data;
            gen += ":ref -> ";
            gen += curr->next->data;
            gen += ":data [arrowhead=vee, arrowtail=dot, dir=both];";
            gen += '\n';
 
            gen += curr->next->data;
            gen += ":data -> ";
            gen += curr->data;
            gen += ":ref [arrowhead=vee, arrowtail=dot, dir=both];";
            gen += '\n';
 
            curr = curr->next;
        }
    } else {
        for (auto &x : els) {
            std::cout << std::to_string(x.first) << " " << std::to_string(x.second) << '\n';
            gen += std::to_string(x.first);
            gen += " [label=<{ ";
            gen += std::to_string(x.first);
            gen += " | ";
            gen += std::to_string(x.second);
            gen += " | }>] ;";
            gen += '\n';
        }
 
        std::shared_ptr<node> curr = head;
        while (curr->next) {
            gen += std::to_string(curr->data);
            gen += ":ref -> ";
            gen += std::to_string(curr->next->data);
            gen += ":data [arrowhead=vee, arrowtail=dot, dir=both];";
            gen += '\n';
 
            gen += std::to_string(curr->next->data);
            gen += ":data -> ";
            gen += std::to_string(curr->data);
            gen += ":ref [arrowhead=vee, arrowtail=dot, dir=both];";
            gen += '\n';
 
            curr = curr->next;
        }
    }
    return gen;
}
 
#ifdef LINKED_LIST_VISUALIZATION_H
template <typename T> void frequency_list<T>::visualize() {
    std::string generated = this->generate();
    linked_list_visualization::visualize(generated);
}
#endif
 
 
 
template<typename T>
class frequency_list<T>::Iterator {
    private:
    std::shared_ptr<node> current;
    public:
    explicit Iterator(const std::shared_ptr<node> &ptr) noexcept
    : current(ptr) {}
 
 
    Iterator &operator=(const std::shared_ptr<node> &ptr) {
        current = ptr;
        return *this;
    }
 
    Iterator &operator++() {
        if(current) {
            current = current->next;
        }
        return *this;
    }
 
    Iterator operator++(int) {
        Iterator tmp = *(this);
        ++*(this);
        return tmp;
    }
 
    Iterator & operator --(){
        if(current){
            current = current -> prev;
        }
        return *(this);
    }
 
    Iterator operator --(int){
        Iterator tmp = *(this);
        --*(this);
        return tmp;
    }
 
    bool operator==(const Iterator &it) { return it.current == this->current; }
 
    bool operator!=(const Iterator &it) { return it.current != this->current; }
 
    T operator*() { return current->data; }
 
};
 
#endif //FREQUENCY_LIST_H