2
\$\begingroup\$

I wrote a program which visualizes a doubly linked list in C++/SFML. The code is working as intended, and does exactly what I want. Could you give me some feedback / criticism on some do's and or don'ts?

This Node class represent a node within the doubly linked list. It inherits both from sf::RectangleShape and sf::Vertex so I can a)visualise the node, and b)put the nodes into an sf::VertexArray so I can draw the links in between them easily.

#ifndef NODE_H
#define NODE_H
#include <SFML/Graphics.hpp>
#include "Globals.h"
template<typename T>
struct Node : public sf::RectangleShape, public sf::Vertex
{
    T data;
    Node<T>* next = nullptr;
    Node<T>* previous = nullptr;

    sf::Vector2f initialposition; // unsorted position
    sf::Vector2f sortedposition; //sorted position which is based on its position in the list array.
    sf::Vector2f distance; //used to calculate velocity.
    sf::Vector2f velocity;

    Node(const T& data, sf::Vector2f&& position);
    void setAllPositions(const sf::Vector2f& position); //since it is both an sf vertex and sf rectangleshape, this function allows me to move both at once
    void moveall(const sf::Vector2f& vel);   //ditto with velocity.
};
template<typename T>
Node<T>::Node(const T& value, sf::Vector2f&& position)
    :data(value), initialposition(position)
{
    setAllPositions(position);
    this->setFillColor(sf::Color::Transparent);
    this->setOutlineColor(sf::Color::White);
    this->setOutlineThickness(3);
    this->setSize(sf::Vector2f{ static_cast<float>(NODE_WIDTH), static_cast<float>(NODE_WIDTH) });
    this->setOrigin(this->getSize() / static_cast<float>(2));
}
template<typename T>
void Node<T>::setAllPositions(const sf::Vector2f& pos)
{
    this->setPosition(pos);
    position = pos;
}
template<typename T>
void Node<T>::moveall(const sf::Vector2f& vel)
{
    this->move(vel);
    position += vel;
}
#endif

This is my List class, which manages all the nodes. I have chosen to inherit from sf::Drawable so as to make it directly drawable. It contains so that I am able to spawn nodes at random locations.

#ifndef LIST_H
#define LIST_H
#include <deque>
#include <random>
#include "Node.h"
#include <algorithm>
template<typename T>

class List : public sf::Drawable
{
protected:
    mutable sf::VertexArray arr{ sf::LineStrip }; //this stores the nodes as individual verticies.
    std::deque<Node<T>*> m_nodeStorage;
    Node<T>* head = nullptr;
    Node<T>* tail = nullptr;

    virtual void draw(sf::RenderTarget& target, sf::RenderStates state) const override; //draws nodes, as well as the verticies in the array above.

    static inline Node<T>* createnode(const T& val);
    static inline sf::Vector2f getrandompos(); //creates a random vector within screen using distributions below
    static std::mt19937 m_randomGenerator;
    static std::uniform_real_distribution<float> m_gaussian_position;

public:
    List();
    List(const T& val); //value constructor
    List(const List<T>& other); //copy constructor
    List(const List<T>&& other); //move constructor
    List<T>& operator= (List<T>& other); //copy assignment operator
    List<T>& operator=(List<T>&& other); //move assignment operator
    ~List();

    void append(const T& val);
    bool insert(const T& val, const int& index);
    bool indexerase(const int& index);
    bool valueerase(const T& val);
    void clear();
    void pop();
    inline void setheadandtail(); //called after insertion or deletion, makes sure head and tail are correct

    bool isempty() const;
    decltype(auto) getnodestorage() const;
    void traverseforward();
    void traversebackward();

};


template<typename T>
List<T>::List(const T& val)
{
    head = createnode(val);
    m_nodeStorage.push_back(head);
    setheadandtail();
}
template<typename T>
List<T>::List()
{

}
template<typename T>
List<T>::List(const List<T>& other)
{
    for (const Node<T>* node : other.m_nodeStorage)
    {
        append(node->data);
    }
    setheadandtail();
}
template<typename T>
List<T>::List(const List<T>&& other)
{
    for (const Node<T>* node : other.m_nodeStorage)
    {
        m_nodeStorage.push_back(node);
    }
    setheadandtail();
}
template<typename T>
List<T>& List<T>::operator=(List<T>& other)
{
    m_nodeStorage.clear();
    for (const Node<T>* node : other.m_nodeStorage)
    {
        append(node->data);
    }
    setheadandtail();
}
template<typename T>
List<T>& List<T>::operator=(List<T>&& other)
{
    for (const Node<T>* node : other.m_nodeStorage)
    {
        m_nodeStorage.push_back(node);
    }
    setheadandtail();
}
template<typename T>
List<T>::~List()
{
    clear();
}
template<typename T>
void List<T>::draw(sf::RenderTarget& target, sf::RenderStates state) const
{
    arr.clear();
    for (Node<T>* node : this->m_nodeStorage)
    {
        target.draw(*node);
        arr.append(*node);
    }
    target.draw(arr);
}

template<typename T>
bool List<T>::insert(const T& val, const int& index)
{
    if (index > m_nodeStorage.size()) return false;
    if (index < 0) return false;
    Node<T>* newnode = createnode(val);

    if (index == 0 )
    {
        if (m_nodeStorage.size() != 0) //if a head already exists
        {
            newnode->next = head;
            head->previous = newnode;
        }
        head = newnode;
        m_nodeStorage.push_front(newnode);
        return true;
    }
    else //if inserted at non 0 index.
    {

        if (index == m_nodeStorage.size()) // if appending
        {
            Node<T>* lastnode = m_nodeStorage.back();
            lastnode->next = newnode;
            newnode->previous = lastnode;
            m_nodeStorage.push_back(newnode);
        }
        else
        {
            Node<T>* previousNode = m_nodeStorage[index -1];
            Node<T>* nextNode = m_nodeStorage[index];
            previousNode->next = newnode;
            newnode->previous = previousNode;
            nextNode->previous = newnode;
            newnode->next = nextNode;
            m_nodeStorage.insert(m_nodeStorage.begin() + index, newnode);
        }
        tail = m_nodeStorage.back();
        return true;
    }

    return false;
}
template<typename T>
void List<T>::clear()
{
    for (Node<T>* node : m_nodeStorage)
    {
        delete node;
    }
    m_nodeStorage.clear();
}
template<typename T>
void List<T>::append(const T& val)
{
    insert(val, m_nodeStorage.size());
}
template<typename T>
bool List<T>::valueerase(const T& val)
{
    auto deletenode = std::find_if(m_nodeStorage.begin(), m_nodeStorage.end(),[&](Node<T>* node)
    {
        return node->data == val;
    });
    if (deletenode != m_nodeStorage.end())
    {
        return indexerase(static_cast<int>(std::distance(m_nodeStorage.begin(), deletenode)));
    }
    return false;
}
template<typename T>
bool List<T>::indexerase(const int& index)
{
    if (index < 0 || index >= m_nodeStorage.size()) return false;
    if (m_nodeStorage.empty()) return false;
    Node<T>* currentnode = m_nodeStorage[index];
    if(index > 0 && index < m_nodeStorage.size() - 1)
    {
        Node<T>* previousnode = m_nodeStorage[index - 1];
        Node<T>* nextnode = m_nodeStorage[index + 1];

        previousnode->next = nextnode;
        nextnode->previous = previousnode;
    }
    delete currentnode;
    m_nodeStorage.erase(m_nodeStorage.begin() + index);
    setheadandtail();
    return true;
}
template<typename T>
void List<T>::pop()
{
    indexerase(static_cast<int>(m_nodeStorage.size() - 1));
}
template<typename T>
void List<T>::setheadandtail()
{
    if (!m_nodeStorage.empty())
    {
        head = m_nodeStorage[0];
        tail = m_nodeStorage[m_nodeStorage.size() - 1];
        head->previous = nullptr;
        tail->next = nullptr;
    }
}
template<typename T>
bool List<T>::isempty() const
{
    return m_nodeStorage.empty();
}
template<typename T>
void List<T>::traverseforward()
{
    Node<T>* currentNode = head;
    while (currentNode != nullptr)
    {
        currentNode->setOutlineColor(sf::Color::Green);
        currentNode = currentNode->next;
    }
}
template<typename T>
void List<T>::traversebackward()
{
    Node<T>* currentnode = m_nodeStorage.back();
    while (currentnode != nullptr)
    {
        currentnode->setOutlineColor(sf::Color::Red);
        currentnode = currentnode->previous;
    }
}
template<typename T>
decltype(auto) List<T>::getnodestorage() const
{
    return &m_nodeStorage;
}


//statics
template<typename T>
Node<T>* List<T>::createnode(const T& val)
{
    Node<T>* newnode = new Node<T>(val, getrandompos());
    return newnode;
}
template<typename T>
sf::Vector2f List<T>::getrandompos()
{
    return sf::Vector2f{ m_gaussian_position(m_randomGenerator), m_gaussian_position(m_randomGenerator) };
}

template<typename T>
std::mt19937 List<T>::m_randomGenerator{ 3 };
template<typename T>
std::uniform_real_distribution<float> List<T>::m_gaussian_position{ 0,WIDTH };



#endif

This is my engine class, which manages the velocities of each node.

#ifndef ENGINE_H
#define ENGINE_H

#include "List.h"

template<typename T>
class Engine : public List<T>
{
protected:
    float maximumvelocity = 1000; 
    float maximumdistance = sqrt(pow(WIDTH, 2) + pow(HEIGHT, 2));
    float G = maximumvelocity / maximumdistance;
public:
    Engine(const T& val);
    void calculatesortedpositions();
    void update();

    static sf::Vector2f normalisedvector(const sf::Vector2f& vec);
    static float vectormagnitude(const sf::Vector2f& vec);
};

template<typename T>
Engine<T>::Engine(const T& freq)
    :List<T>(freq)
{
    for (int i = 0; i < freq; i++)
    {
        this->append(freq);
    }
    calculatesortedpositions();
}
template<typename T>
void Engine<T>::calculatesortedpositions()
{
    int i = 0;
    for (Node<T>* node : this->m_nodeStorage)
    {
        node->sortedposition.x = (NODE_WIDTH / 2) + ((i) % (NCOLS)) * NODE_WIDTH;
        node->sortedposition.y = (NODE_WIDTH / 2) + ((i) / (NCOLS)) * NODE_WIDTH;

        i++;
    }
}
template<typename T>
void Engine<T>::update()
{
    for (Node<T>* node : this->m_nodeStorage)
    {
        node->distance = node->sortedposition - node->getPosition();
        node->velocity = normalisedvector(node->distance) * G;
        node->moveall(node->velocity);
    }
}

//statics
template<typename T>
float Engine<T>::vectormagnitude(const sf::Vector2f& vec)
{
    return sqrt(pow(vec.x, 2) + pow(vec.y, 2));
}
template<typename T>
sf::Vector2f Engine<T>::normalisedvector(const sf::Vector2f& vec)
{
    return vec / vectormagnitude(vec);
}
#endif

Here are my globals variables

#ifndef GLOBALS_H
#define GLOBALS_H
#define WIDTH 700
#define HEIGHT 700
#define NODE_WIDTH 30
#define NCOLS WIDTH / NODE_WIDTH
#endif

Here is main.cpp

#include <iostream>
#include "Node.h"
#include "Globals.h"
#include "Engine.h"

int main()
{
    sf::RenderWindow myWindow(sf::VideoMode(WIDTH, HEIGHT), "Doubly Linked List", sf::Style::Default);
    sf::View screen;
    screen.setCenter(sf::Vector2f{ WIDTH / 2,HEIGHT / 2 });
    screen.setSize(sf::Vector2f{ WIDTH,HEIGHT });
    Engine<float> myEngine(600);

    while (myWindow.isOpen())
    {
        sf::Event evnt;
        while (myWindow.pollEvent(evnt))
        {
            switch (evnt.type)
            {
                case sf::Event::EventType::Closed:
                {
                    myWindow.close();
                }
                case sf::Event::EventType::KeyPressed:
                {
                    if (sf::Keyboard::isKeyPressed(sf::Keyboard::Key::W))
                    {
                        screen.zoom(0.99);
                        myWindow.setView(screen);
                    }
                    if (sf::Keyboard::isKeyPressed(sf::Keyboard::Key::S))
                    {
                        screen.zoom(1.01);
                        myWindow.setView(screen);
                    }
                }
            }

        }
        myWindow.clear();
        myWindow.draw(myEngine);
        myEngine.update();
        myWindow.display();
    }
}
\$\endgroup\$
1
\$\begingroup\$

Globals.h

  1. I generally don't mind globals as much; I think there are scenarios where they are useful, but this isn't it. These NODE_WIDTH and NCOLS are part of your Node class, and as such should be tightly coupled with it.
  2. Don't use #define unless you need to. It's the C way of defining globals, it does not maintain type safety of the expression; instead use constexpr size_t or constexpr unsigned int.
  3. Instead of defining them in a separate header, define them as static constexpr members in your class. Better yet, define them as regular data members, so you customize the appearance of each linked list.

Node.h

  1. Prefer using smart pointer to raw pointers; it's fine in this case, since you're deleting them, but it's something to keep in mind for future.
  2. Naming is out of place. You have a method setAllPositions which is pascal case, but you have moveall which all lower caps. Also your data members are all lower case, which makes it harder to read.
  3. Don't use this unless you need to explicitly address the current object.
  4. velocity serves no role; the moveall method acts directly upon the positions. You don't need a velocity member since you're not using it.
  5. Naming could a lot better. moveall makes me think that Node contains more than one positions that need to be updated. A simple move is good enough. Similarly, setPosition works just as well, without confusing the reader.

List.h

  1. Again, naming is bit weird. You have members arr, head, tail, but also have m_nodeStorage, m_randomGenerator, etc. with the m_ prefix. Pick a single style. Also there is weird mix of pascal case and snake case. Methods are hard to read because they're all lower.
  2. Why do you have an std::deque? A list should only contain pointers to head and tail. Storing all the nodes again defeats the purpose of a list.
  3. You don't need inline. The compiler is smarter than anyone who decides to inline their functions and methods.
  4. Why are the random utilities static? A better approach would be have them as instance members, so each list has its own random utilities. You're also seeding the generator with the same value, which defeats the purpose of a random generator.
  5. Why is an uniform_real_distribution called m_gaussian_position? It's just confusing; C++ has a normal distribution if you want to use it.

Engine.h

  1. I don't understand the purpose of this class. All it is doing is inheriting from a List, with a few additional functions. And it seems like some methods can be directly be a part of List, such as calculatedsortedpositions. A better approach would be to have List as a member of the class.
  2. G provides me with no information about its purpose.
  3. normalisedvector and vectormagnitude have absolutely nothing to with any of those class. A better approach would be have them as standalone functions, wrapped in a namespace.
  4. Naming.

Also, use a namespace.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.