frequency_list.h

#ifndef FREQUENCY_LIST_H
#define FREQUENCY_LIST_H
 
#ifdef ENABLE_LINKED_LIST_VISUALIZATION
#include "../../visualization/list_visual/linked_list_visualization.h"
#endif
 
#ifdef __cplusplus
#include <cstdint>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#endif

template <typename T> class frequency_list {
  public:
    inline explicit frequency_list(std::vector<T> data = {}) noexcept
        : head(nullptr), tail(nullptr) {
        if (!data.empty()) {
            for (const auto& item : data) {
                this->push_back(item);
            }
        }
    }

    inline 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>
inline 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> inline 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> inline void frequency_list<T>::reset_frequency() {
    auto iterator = head;
 
    while (iterator != nullptr) {
        iterator->reset_freq();
        iterator = iterator->next;
    }
}
 
template <typename T> inline 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> inline 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> inline 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> inline 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> inline 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> inline 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> inline 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 ENABLE_LINKED_LIST_VISUALIZATION
template <typename T> inline 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