SLelement.h

Go to the documentation of this file.

#ifndef SLELEMENT_H
#define SLELEMENT_H
 
#include "DataStructure.h"
#include "Element.h" //string, using std
 
 
namespace bridges {
    namespace datastructure {
        template <typename E>
        class SLelement : public Element<E>, public DataStructure {
 
            protected:
                SLelement* next = nullptr;
 
            public:
                SLelement(SLelement* next, const E& val = E(), const string& lab =
                        string()) : Element<E>(val, lab) {
                    setNext(next);
                }
                SLelement(const E& val = E(), const string& lab = string())
                    : SLelement(nullptr, val, lab) {
                }
                virtual const string getDStype() const override {
                    return "SinglyLinkedList";
                }
 
                virtual SLelement* getNext() {
                    return next;
                }
 
                virtual const SLelement* getNext() const {
                    return next;
                }
 
                void setNext(SLelement* n) {
                    //if different, remove old link data
                    if (next != n) {
                        this->links.erase(next);
                    }
 
                    next = n;
                    this->links[next]; //this creates an entry in links if it does not exist
                }
 
            private:
                virtual const string getDataStructureRepresentation() const override {
 
                    vector<const SLelement<E>*> nodes;
                    // get the list of nodes
                    getListElements(nodes);
                    // generate the JSON string
 
                    if (MAX_ELEMENTS_ALLOWED <= nodes.size()) {
                        // cant exceed max number of elements
                        throw "Max allowed elements(for visualization) exceeded.. " +
                        to_string(nodes.size()) + " Must be less than " +
                        to_string(MAX_ELEMENTS_ALLOWED);
                    }
 
                    pair<string, string> json_nodes_links = generateJSON(nodes);
 
                    string sl_list_json =
                        QUOTE + "nodes"  + QUOTE + COLON +
                        OPEN_BOX + json_nodes_links.first + CLOSE_BOX + COMMA +
                        QUOTE + "links" + QUOTE + COLON + OPEN_BOX +
                        json_nodes_links.second + CLOSE_BOX +
                        CLOSE_CURLY;
 
 
                    return sl_list_json;
                }
            protected:
                virtual const pair<string, string> generateJSON(
                    vector<const SLelement<E>*> nodes) const {
                    // map the nodes to a sequence of ids, 0...N-1
                    // then get the JSON string for nodes placeholder
                    // nullptr prevents insertion of other nullptrs
                    unordered_map<const SLelement*, int> node_map { {nullptr, -1} };
 
                    string nodes_JSON, links_JSON;
 
                    int i = 0;      // get the JSON string for nodes
                    for (const auto* e : nodes) {
                        if (node_map.emplace(e, i).second)  {
                            // successful emplacement
                            i++;
                            nodes_JSON += e->getElementRepresentation() + COMMA;
                        }
                    }
                    //Remove trailing comma and nullptr entry
                    node_map.erase(nullptr);
                    if (nodes_JSON.size()) {
                        nodes_JSON = nodes_JSON.erase(nodes_JSON.size() - 1);
                    }
                    // for each pair<SLelement*,int> in map
                    for (unsigned int k = 0; k < nodes.size(); k++) {
                        if (nodes[k]->next != nullptr) { // link exists
                            links_JSON += this->getLinkRepresentation(nodes[k]->links.at(nodes[k]->next),
                                    to_string(node_map[nodes[k]]),
                                    to_string(node_map[nodes[k]->next]) ) + COMMA;
                        }
                    }
 
                    //Remove trailing comma
                    if (links_JSON.size()) {
                        links_JSON = links_JSON.erase(links_JSON.size() - 1);
                    }
 
                    return pair<string, string> (nodes_JSON, links_JSON);
                }
            protected:
                virtual void getListElements(vector<const SLelement<E>*>& nodes) const  {
 
                    //prevents potential infinite loop
                    unordered_set<const SLelement<E>*> visited;
                    auto it = this;
 
                    // using the visited array handles both regular and
                    // circular lists
                    while (it != nullptr && visited.emplace(it).second) {
                        nodes.push_back(it);
                        it = it->next;
                    }
                }
 
            public:
 
                class SLelement_listhelper {
                        typename bridges::datastructure::SLelement<E> * start;
 
                    public:
                        SLelement_listhelper (typename bridges::datastructure::SLelement< E > * s)
                            : start(s)
                        {}
 
                        class iterator {
                                typename bridges::datastructure::SLelement<E> *current;
                            public:
                                iterator(typename bridges::datastructure::SLelement<E> * c )
                                    : current(c)
                                {}
 
                                bool operator!= (const iterator& it) const {
                                    return this->current != it.current;
                                }
 
                                E const &  operator* () const {
                                    return current->getValue();
                                }
 
                                E &  operator* ()  {
                                    return current->getValue();
                                }
 
                                iterator& operator++ () {
                                    current = current->getNext();
                                    return *this;
                                }
                                iterator operator++ (int) {
                                    iterator clone(*this);
                                    current = current->getNext();
                                    return clone;
                                }
                        };
 
                        iterator begin() {
                            return iterator(start);
                        }
 
                        iterator end() {
                            return iterator(nullptr);
                        }
                };
 
 
                class SLelement_constlisthelper {
                        typename bridges::datastructure::SLelement<E> const * start;
 
                    public:
                        SLelement_constlisthelper (typename bridges::datastructure::SLelement< E > const * s)
                            : start(s)
                        {}
 
                        class iterator {
 
                                typename bridges::datastructure::SLelement< E > const  * current;
                            public:
                                iterator(    typename bridges::datastructure::SLelement< E > const   * c )
                                    : current(c)
                                {}
 
                                bool operator!=(const iterator& it) const {
                                    return this->current != it.current;
                                }
 
                                E const &  operator*() const {
                                    return current->getValue();
                                }
 
                                iterator& operator++() {
                                    current = current->getNext();
                                    return *this;
                                }
                        };
 
                        iterator begin() {
                            return iterator(start);
                        }
 
                        iterator end() {
                            return iterator(nullptr);
                        }
                };
 
 
        }; //end of SLelement class
        // use some aliases for accessing iterators
        template <class E>
        using SLelement_List = typename SLelement<E>::SLelement_listhelper;
        template <class E>
        using SLelement_ConstList = typename SLelement<E>::SLelement_constlisthelper;
    }
}//end of bridges namespace
#endif